---

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

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

• 09.03.04 - Программная инженерия.

Лектор (ы):

• Дмитрий Жоржевич Корзун <dkorzun@cs.karelia.ru>

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

• 24.04 11:30
• 17.04 11:30
• 10.04 11:30

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

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. Разбор алгоритма флаговой синхронизации для барьера. Детальное понимание и обоснование известного алгоритма флаговой синхронизации для реализации барьера (см. учебник Эндрюс). Понимание сути алгоритма и как он обеспечивает эффективную синхронизацию.

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

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

• Гл.0. Введение. Сущность взаимодействующих (параллельных) вычислений. Взаимодействие => синхронизация: взаимное исключение и условная синхронизация. Типы приложений: многопоточные системы, распределенные вычисления, синхронные параллельные вычисления.
• Гл.1. Программирование взаимодействующих параллельных вычислений. Парадигмы взаимодействующих параллельных вычислений. Итеративный параллелизм (умножение матриц), рекурсивный параллелизм (адаптивная квадратура), производитель–потребитель (конвейер), клиент–сервер, взаимодействующие равные. Программная нотация.
• Гл.2. Процессы, потоки и синхронизация. Процессы/потоки вычислений, «тяжелые» и «легковесные» процессы. Взаимосвязь между процессами: передача сообщений и разделяемая память. Состояния, действия, истории и свойства. Возможные истории и синхронизация. Свойства безопасности и живучести. Неделимые действия и операторы ожидания. Мелкомодульная и крупномодульная неделимость. Оператор await.
• Гл.3. Замки и барьеры. Задача критической секции. Ключевые свойства. Циклические замки (активная блокировка). Реализация оператора await. Решения со справедливой стратегией. Алгоритм «разрыв узла». Алгоритм «билета». Алгоритм «поликлиники». Синхронизация барьером: разделяемый счетчик, флаги и координаторы.
• Гл.4. Семафоры. Механизм синхронизации на примерах задач: "Об обедающих философах", "Читатели и писатели", "Управление ресурсами (выделение и распределение)".

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

• Тема 1. Парадигмы взаимодействующих параллельных вычислений. Разработка и анализ параллельной версии известного алгоритма для демонстрации различных парадигм.
• Тема 2. Типовые задачи. Критическая секция (протоколы входа и выхода). Потребитель-производитель (синхронизация). Задача об обедающих философах (взаимная блокировка). Задача о читателях и писателях (исключительное использование ресурса). Задача о спящем парикмахере (принцип рандеву).
• Тема 3. Состояния, истории и свойства параллельных программ. Разбор задач "Поиск образца в файле (распараллеливание, парадигма производитель-потребитель)", "Поиск максимального элемента (синхронизация, принцип перепроверки)" и других [Andrews, гл. 2].
• Тема 4. Критическая секция. Разбор возможных механизмов синхронизации: циклические замки, алгоритм Деккера, инструкции DEC и INC, инструкции «test-test-set», семафоры.
• Тема 5. Задача условной синхронизации (барьеры). Разбор примеров задач: "Об обедающих философах", "Читатели и писатели", "Управление ресурсами".

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

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

---