(c) Larry Ewing, Simon Budig, Garrett LeSage
с 1994 г.

Кафедра Информатики и Математического Обеспечения

ПетрГУ | ИМиИТ | О кафедре | Проекты | Лаборатория ИТС | Семинары НФИ/AMICT
Сотрудники | Учебный процесс | Табель-календарь | Курсовые и выпускные работы
Вычислительные ресурсы | Публикации | Архив новостей | Контактная информация

Взаимодействующие параллельные системы

2020/21 учебный год г., Институт математики и информационных технологий, II курс
3 семестр(ы)
Специальности: Лектор (ы):

Инструкции по дистанционному обучению

  1. В соответствии с темами лекционных и практических занятий ниже сформулированы условия задач на разработку и исследование параллельных программ.
  2. По теме каждой задачи обучающийся изучает теоретический материал в соответствии с указанным списком литературы и на дистанционных занятиях. При необходимости обучающийся по эл.почте консультируется с лектором, который уточняет конкретные разделы для изучения в литературе.
  3. Обучающийся готовит в эл.виде решения по задачам. Отправляет решение очередной задачи по email лектору. Данный пункт требует отправки не менее одного решения каждую неделю (либо первую версию решения по новой задаче, либо скорректированный вариант по одному из предыдущих решений).
  4. Лектор оценивает решение и высылает комментарии по ее улучшению. Соответствующее обсуждение также проводится во время дистанционных занятий (1 ч. лекции + 2 ч. практики).
  5. Шаги 1-4 повторяются еженедельно. Ведется учет в журнале учебной дисциплины.

В итоге, к концу семестра каждый обучающийся должен сформировать набор из решений задач, каждая должна быть скорректирована не менее 1 раза по результатам комментариев от лектора. Аттестационное занятие будет построено в виде индивидуального собеседования с обучающимся по представленным решениям. Представленный список задач следует рассматривать как список теоретических вопросов по учебной дисциплине.

Формулировки задач на разработку и исследование параллельных программ (для индивидуального решения каждым обучающимся)

  1. [общее понимание, лекции: гл.0-1]. Распараллеливание известного алгоритма с анализом свойств полученного решения. Взять известный алгоритм (последовательная версия). Разработать его параллельную версию. Выполнить анализ параллельной версии (плюсы и минусы в сравнении с последовательной).
  2. [простое упражнение, лекция: гл.1]. Итеративное умножение матриц: замена co <-> for. Взять представленную на лекции программу итеративного умножения матриц, выполнить замену. Что измениться в работе программы (сравнение).
  3. [развитие программы, рассмотренной на лекции: гл.1-2]. Итеративное умножение больших матриц. Рассмотреть случай, когда n<<p, где n – линейный размер квадратной матрицы, а p – число доступных программе процессоров. Предложить параллельную программу итеративного умножения матриц, когда число процессов не превосходит p.
  4. [понимание метода, рассмотренного на лекции: гл.1-2]. Рекурсивный параллелизм с контролем числа процессов. На основе рассмотренной на лекции программы с рекурсивным параллелизмом предложить общую схему алгоритма рекурсивного параллелизма. Расширить эту схему механизмом контроля числа процессов (задана граница N, число одновременно выполняемых параллельных процессов не должно превосходить N). Обосновать предложенную схему (какие коллизии возможны из-за параллельности).
  5. [развитие программы, рассмотренной на лекции: гл.1-2]. Распределенное умножение матриц. На основе рассмотренной на лекции программы распределенного умножения матриц необходимо предложить вариант умножения матриц, в котором сеть передачи данных используется эффективнее, а участвующие параллельные процессы не тратят много времени на ожидание поступления данных для вычислений.
  6. [типовая задача, лекция: гл.2]. Упр. 4.36 из учебника Эндрюса. Предложить программу, реализующую процессы медведя и n пчел. Рекомендуется использовать оператор await для синхронизации процессов. Выполнить анализ свойств параллельной программы (отсутствие коллизий между параллельными процессами).
  7. [понимание метода, лекция: гл.3]. Задача на понимание и обоснование свойств решения критической секции, рассмотренного на лекции. Используется циклический замок на основе машинной инструкции Test-and-Set (bool TS(bool)). Обосновать выполнение свойств 1-3 критической секции и показать, что свойство 4 критической секции не гарантируется.
  8. [понимание метода, лекция: гл.3]. Разбор алгоритма разрыва узла для n процессов (на основе листинга из лекции и учебника Андрюса).
  9. [опциональное упражнение-бонус, заменяет любые три задачи из №№ 1-8, лекция: гл.3]. Анализ ошибки в варианте алгоритма разрыва узла для 2-х процессов. В чем заключается ошибка? Предложите вариант корректного решения. Доведите до мелкомодульного решения (без <> и <await()>).
  10. [понимание метода, лекции: гл.1-3]. Задача на поиск максимума в массиве. Разобрать, в чем эффективность предложенной на лекции параллельной программы (из учебника Эндрюса) с повторной проверкой.
  11. [типовая задача, лекции: гл.1-3]. Разработать алгоритм, реализующий утилиту
    grep o f1 f2 … fn
    где o - шаблон для соответствия строки, f1 f2 … fn - текстовые фалы для поиска соответствующих шаблону строк. Параллельность необходимо заводить по чтению и поиску соответствия, т.е. следуя модели буфера, соединяющего производителей данных с потребителями данных.
  12. [понимание метода, лекция: гл.3]. Разбор алгоритма поликлиники для n процессов Детальное понимание и обоснование известного алгоритма поликлиники (см. учебник Эндрюс). Понимание сути алгоритма и почему он обеспечивает свойство справедливости для параллельных процессов, использующих критическую секцию.
  13. [понимание метода, лекция: гл.3]. Разбор алгоритма флаговой синхронизации для барьера. Детальное понимание и обоснование известного алгоритма флаговой синхронизации для реализации барьера (см. учебник Эндрюс). Понимание сути алгоритма и как он обеспечивает эффективную синхронизацию.
  14. [типовая задача, лекция: гл.4]. Предложить параллельную программу, использующую семафоры для синхронизации процессов. Например, можно взять упр. 4.36 из учебника Эндрюса («медведь и пчелы»).

Для каждой из задач выше нужно подготовить ПОДРОБНОЕ письменное решение (в эл.варианте). В описании решения использовать нотацию из учебника Эндрюса. Важно приводить не только окончательное решение, но и описать логику его построения, а также разобрать предлагаемое решение на примерах.

Содержание лекционных занятий.

Содержание практических занятий.

Список литературы.

  1. Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования / Г.Р.Эндрюс. - Москва : Вильямс, 2003. - 512 с.
  2. Бэкон Д. Операционные системы: Параллельные и распределенные системы / Д. Бэкон, Т. Харрис. – Санкт-Петербург : Питер ; Киев: Изд. группа BHV, 2004. – 800 с.
  3. Федотов И. Е. Модели параллельного программирования / И.Е.Федотов. - Москва : СОЛОН-ПРЕСС, 2012. - 384 с. [Электронный ресурс]. http://biblioclub.ru/index.php?page=book&id=227018
  4. Колпаков А.А. Повышение производительности гетерогенных компьютерных систем обработки данных / А.А. Колпаков, Ю.А. Кропотов. - Москва, Берлин: Директ-Медиа, 2019. -122 с. . [Электронный ресурс]. http://biblioclub.ru/index.php?page=book_red&id=496776