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

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

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

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

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

Расписание консультаций

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

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

Лектор оценивает решение и высылает комментарии по ее улучшению.

Шаги 1-4 повторяются еженедельно. Каждая еженедельная итерация эквивалентна проведению 3 часов аудиторных занятий (1 ч. лекции + 2 ч. практики). Ведется учет в журнале учебной дисциплины.

Часть задач ранее уже выполнялась обучающимися (с докладом на практике). В этом случае, обучающийся высылает лектору скорректированный (по результатам выполненного доклада) вариант решения.

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

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

  1. Параллельная версия известного алгоритма. Взять известный алгоритм (последовательная версия). Разработать его параллельную версию. Выполнить анализ параллельной версии (плюсы и минусы в сравнении с последовательной).
  2. Рекурсивный параллелизм с контролем числа процессов. На основе рассмотренного на лекции примера алгоритма с рекурсивным параллелизмом предложить общую схему алгоритма рекурсивного параллелизма. Расширить эту схему механизмом контроля числа процессов (задана граница N, число одновременно выполняемых параллельных процессов не должно превосходить N). Обосновать предложенную схему (какие коллизии возможны из-за параллельности).
  3. Распределенное умножение матриц. На основе рассмотренного на лекции алгоритма распределенного умножения матриц необходимо предложить модифицированный алгоритм умножения матриц, в котором сеть передачи данных используется более эффективно, а участвующие параллельные процессы не тратят много времени на ожидание поступления данных для вычислений.
  4. Задача 4.36 из учебника Эндрюса. Псевдоалгоритм для решения модели "Медведь и пчелы". Обоснование алгоритма (отсутствие коллизий между параллельными процессами).
  5. Разработать алгоритм, реализующий утилиту
    grep o f1 f2 … fn
    где o - шаблон для соответствия строки, f1 f2 … fn - текстовые фалы для поиска соответствующих шаблону строк. Параллельность необходимо заводить по чтению и поиску соответствия, т.е. следуя модели буфера, соединяющего производителей данных с потребителями данных.
  6. Разбор алгоритма поликлиники для n процессов Детальное понимание и обоснование известного алгоритма поликлиники (см. учебник Эндрюс). Понимание сути алгоритма и почему он обеспечивает свойство справедливости для параллельных процессов, использующих критическую секцию.
  7. Разбор алгоритма флаговой синхронизации для барьера. Детальное понимание и обоснование известного алгоритма флаговой синхронизации для реализации барьера (см. учебник Эндрюс). Понимание сути алгоритма и как он обеспечивает эффективную синхронизацию.

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

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

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

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

  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