Основы параллельного программирования

Программа учебного курса ОСНОВЫ ПАРАЛЛЕЛЬНОГО ПРОГРАММИРОВАНИЯ I. Организационно-методический раздел. Курс реализуется в рамках направления 552800 «Информатика и вычислительная техника», относится к циклу общепрофессинальных дисциплин, федеральный компонент. 1.1.Цели и задачи курса Цели курса - изучение основ параллельного программирования, развитие мышления связанного с параллельным программированием. параллельного - систематизация знаний о методах и алгоритмах программирования, моделях параллельных вычислений. Задачи курса - изучить и закрепить методы и способы распараллеливания и построения параллельных программ - исследовать и реализовать набор параллельных алгоритмов для стандартных типовых задач: а) решение систем линейных алгебраических уравнений б) решение задач сеточными методами. 1.2.Требования к уровню освоения содержания курса По окончании изучения указанной дисциплины студент должен иметь представление - о параллельном алгоритме - о моделях вычислений с параллельно-последовательными структурами управления - о модели взаимодействующих процессов - о моделях параллельно-последовательного программирования - о моделях асинхронных вычислений - о моделях синхронных вычислений знать - определение алгоритма (по Мальцеву), представление алгоритма, общее представление параллельного алгоритма. - методы параллельного программирования с разделяемыми переменными, синхронизацию процессов через доступ к общим ресурсам, понятие о критических интервалах, семафорах, программирование параллельных алгоритмов с помощью критических интервалов и семафоров. - методы распределенного параллельного программирования, синхронизацию процессов, взаимодействие распределенных процессов. - модели асинхронных вычислений: Э.Дейкстры и Ч.Хоара - что такое ускорение и эффективность параллельных программ. Закон Амдала - системы параллельного программирования MPI и OpenMP. уметь - создавать параллельные программы для алгоритмов матричных задач: параллельное умножение матрицы на вектор и матрицы на матрицу несколькими способами. - создавать параллельные программы для задач решения систем линейных уравнений методом Гаусса - создавать параллельные программы для задач решения систем линейных уравнений итерационными методами.

-

создавать параллельные программы для задач сортировок разными методами. создавать параллельные программы для алгоритмов матричных задач на вычислительных системах с топологией двух и трех мерных решеток. создавать параллельные программы для задач, решаемых сеточными методами.

1.3.Формы контроля Итоговый контроль. Для контроля усвоения дисциплины учебным планом предусмотрен зачет по лабораторным работам. Текущий контроль. В течение семестра выполняется лабораторные работы. Выполнение указанной работы обязательно для всех студентов, а ее результаты служат основанием для выставления оценок в ведомость контрольной недели на факультете. 2. Содержание дисциплины. 2.1. Новизна и актуальность курса Учебный курс концентрирует внимание на фундаментальных знаниях предметной области – методах параллельного программирования на системах с распределенной памяти и системах с разделяемой памятью и способах построения параллельных программ для решения задач СЛАУ и задач решаемых сеточными методами. 2.2.Тематический план курса (распределение часов). Наименование разделов и тем 1. Введение 2. Распределенное программирование. Краткий обзор система распределенного параллельного программирования – MPI 3. Программирование с разделяемыми переменными. Система параллельного программирования, с разделяемыми переменными OpenMP 4. Взаимодействующие процессы 5. Модели с параллельнопоследовательными структурами управления. 6. Модели асинхронных вычислений 7. Модели синхронных вычислений Итого по курсу:

Лек ции 2 2

Количество часов ЛабораторСамостоятельСеминар ные работы ная работа ы 2 4 2

Всего часов 4 8

2

6

2

10

8 8

6 6

2 2

16 16

2

8

4

14

2

8

4

14

32

32

16

80

2.3.Содержание отдельных разделов и тем. А) Теоретическая часть 1. Введение 1.1. Распределенное программирование. 1.2. Краткий обзор системы распределенного параллельного программирования – MPI Введение. Виртуальные топологии. Парные взаимодействия. Коллективные взаимодействия. MPI - типы данных. 1.3. Параллельное программирование с разделяемыми переменными.

1.4. Система параллельного программирования, с разделяемыми переменными – OpenMP. Краткий обзор функций OpenMP. 2. Общее представление алгоритма 3.1. Определение алгоритма (по ак. Мальцеву) 3.2. Представление алгоритма 3.3. Требования к представлению параллельного алгоритма 3. Сети Петри 4.1. Определение сети Петри 4.2. Разметка сети 4.3. Срабатывание переходов (правила) 4. Взаимодействующие процессы 5.1. Определение процесса 5.2. Синхронизация процессов через доступ к общим ресурсам 5.2.1. Задача взаимного исключения 5.2.2. Семафоры 5.2.2.1. Задача взаимного исключения 5.2.2.2. Моделирование P и V операций над семафором S сетью Петри 5.2.2.3. Взаимное исключение, моделируемое сетью Петри 5.2.2.4. Задача производитель-потребитель с ограниченным буфером 5.2.2.5. Задача читатели-писатели 5.2.2.6. Взаимная блокировка (deadlok) 5.2.2.7. Задача о 5-ти обедающих философах 5.2.3. Условные критические интервалы 5.2.4. Монитор Хоара 5.3. Синхронизация процессов через обмен данными 5.3.1. Передача сообщений в системах параллельного программирования 5.3.2. Параллельная программа разделения множеств (Дейкстра) 6. Модели с параллельно-последовательными структурами управления 6.1. Модель вычислений методом параллельных операторов (яроусно-пар. формы) 6.2. Модель вычислений методом параллельных ветвей 6.3. Модель параллельно-последовательного программирования с fork, join 6.4. MPMD – модель вычислений 6.5. SPMD – модель вычислений 6.6. Необходимость явного распараллеливания 6.7. Ускорение и эффективность (примеры алгоритмов Бэтчера и Хоара) 6.8. Закон Амдала 6.9. Архитектуры ВС, поддерживающие рассмотренные модели вычислений 7. Модели асинхронных вычислений 7.1. Событийное управление 7.2. Потоковые вычисления 7.3. Динамическое управление 7.3.1. Модель асинхронного динамического программирования 7.3.2. Модель вычислений Дейкстры (охраняемые команды) 7.3.3. Модель вычислений Хоара 8. Синхронные вычисления 9. Языки параллельного программирования. Язык Оккам. Язык МИНИМАКС.

Б) Практические занятия

1. Создание простейших параллельных программ, компиляция и запуск параллельных программ. Студент получает представление о параллельных программах. Обучается компилировать и запускать параллельные программы. 2. Создание параллельных программ с использованием виртуальных топологий. Студент обучается создавать виртуальные топологии в системе MPI. Изучает обменные функции в системе MPI. 3. Создание параллельных программ алгоритма умножения матрицы на вектор (и на матрицу) в двух вариантах: в топологии “кольцо” и “полный граф”. Обучается создавать простые параллельные программы для матричных задач. 4. Создание параллельных программ для решения систем линейных алгебраических уравнений методом простой итерации в двух вариантах. Студент обучается писать программы для решения СЛАУ итерационными методами. 5. Создание параллельных программ для решения систем линейных алгебраических уравнений методом Гаусса в двух вариантах: с горизонтальным распределением полос матриц коэффициентов и горизонтально-циклическим. Обучается писать программы для решения СЛАУ методом Гаусса. Студент обучается понимать разницу между параллельными алгоритмами в зависимости от способа распределения данных по компьютерам. 6. Создание параллельных программ сортировки множеств. Студент обучается писать параллельные программы для сортировок множеств. 7. Создание параллельных программ алгоритма умножения матрицы на матрицу: в топологии “двумерная решетка”. Студент углубляет знания по созданию виртуальных топологий. Обучается создавать MPI–типы данных, обмен MPIтипами. 8. Создание параллельных программ для решения уравнений Пуассона в двух и трехмерных областях. Студент обучается создавать программа для задач, решаемых сеточными методами. 3. Учебно-методическое обеспечение дисциплины 3.1.Образцы вопросов для подготовки к экзамену 1. Модели параллельно-последовательного программирования. MPMD и SPMD модели программирования. Необходимость явного распараллеливания. 2. Определение процесса. Два главных типа взаимодействия параллельных процессов. Задача взаимного исключения (определение). Понятие критического интервала, разделяемого и неразделяемого ресурса. Пример сети Петри, моделирующей взаимное исключение. 3. Сконструировать сеть Петри из фрагментов: a

b

c

d

e

По формуле: *((((a;b),(a;c)) || d);e) 4. Сконструировать тип данных нижней триангуляции матрицы размером 100х100 с помощью функции MPI_Type_indexed(ind count_bloks, int blocklen, int disp, MPI_Datatype old_type, MPI_Datatype *new_type)

3.2. Список основной и дополнительной литературы 1. Snir M., Otto S. W., Huss-Lederman S., Walker D., and Dongarra J.. MPI: The Complete Reference. MIT Press. Boston, 1996. 2. В.Э.Малышкин, В.А..Вшивков, М.А.Краева. О реализации метода частиц на мультипроцессорах. – Новосибирск, 1995. – 37 с. – (Препринт / РАН. Сиб. отд-ние. ВЦ; 1052). 3. Евреинов Э.В., Косарев Ю.Г. Однородные универсальные вычислительные системы высокой производительности. – Новосибирск: Наука, 1966. – 308 с. 4. Миренков Н.Н. Параллельное программирование для многомодульных вычислительных систем. – Москва: Радио и связь, 1989. – 320 с. 5. Малышкин В.Э. Линеаризация массовых вычислений. //Системная информатика / Под ред. В.Е.Котова. – Новосибирск: Наука. – 1991, №1. – С. 229–259. 6. Корнеев В.Д. Система и методы программирования мультикомпьютеров на примере вычислительного комплекса PowrXplorer. – Новосибирск, 1998. – 56 с. – (Препринт / РАН. Сиб. отд-ние. ИВМиМГ; 1123) 7. Корнеев В.Д. Параллельные алгоритмы решения задач линейной алгебры – Новосибирск, 1998. – 27 с. – (Препринт / РАН. Сиб. отд-ние. ИВМиМГ; 1124) 8. Корнеев В.Д. Параллельное программирование в MPI. – Новосибирск: Издательство СО РАН, 2000. - 220 с. 9. Дейкстра Э. Дисциплина программирования: Пер. с англ. –М.:Мир,1978 –247 с. 10. Петерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. – М.:Мир,1984 –264 с. 11. Джоунз Г. Программирование на языке Оккам: Пер. с англ. – М.:Мир,1989 –208 12. Кук С. Матричные процессоры на СБИС: Пер. с англ. –М.:Мир,1991 –672 с. 13. В.Е. Котов. Сети Петри. Наука, Сибирское отделение, 1991. 14. Корнеев В.Д. Краткое руководство по параллельному программированию на вычислительной системе POWERXPLORER. – Новосибирск, 1997. – (Методическое пособие, Изд-во НГТУ; 1521) – 72 с. 15. Малышкин В.Э. Основы параллельных вычислений. – Новосибирск, 1999. – (Методическое пособие, Изд-во НГТУ; ) – 55 с. Программу подготовили: д.т.н., профессор к.ф.-м.н., доцент

В.Э.Малышкин В.Д. Корнеев

Программа утверждена на заседании Ученого совета факультета информационных технологий Новосибирского государственного университета 18 декабря 2003 г., протокол заседания №16. Декан ФИТ НГУ, д.ф.-м.н.

М.М.Лаврентьев