---

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

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

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

Лектор (ы):

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

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

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 из учебника Эндрюса («медведь и пчелы»).

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

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

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

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

• Тема 1. Парадигмы взаимодействующих параллельных вычислений. Разработка и анализ параллельной версии известного алгоритма для демонстрации различных парадигм.
• Тема 2. Типовые задачи. Критическая секция (протоколы входа и выхода). Потребитель-производитель (синхронизация). Задача об обедающих философах (взаимная блокировка). Задача о читателях и писателях (исключительное использование ресурса). Задача о спящем парикмахере (принцип рандеву).
• Тема 3. Состояния, истории и свойства параллельных программ. Разбор задач "Поиск образца в файле (распараллеливание, парадигма производитель-потребитель)", "Поиск максимального элемента (синхронизация, принцип перепроверки)" и других [Andrews, гл. 2].
• Тема 4. Критическая секция. Разбор возможных механизмов синхронизации. Циклические замки (активная блокировка). Разбор реализации оператора await. Разбор решений со справедливой стратегией: алгоритм разрыва узла, алгоритм билета, алгоритм поликлиники. Разбор алгоритма Деккера. Использование инструкций 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

---