Рабочая программа учебной дисциплины «Параллельное программирование» (стр. 3 )

Тема 3. Моделирование и анализ параллельных алгоритмов

Лекций - 6 часа, самостоятельная работа - 4 часа.

Модели параллельных вычислительных процессов. Концепция неограниченного параллелизма. Компьютер с неограниченным параллелизмом (паракомпьютер). Модели многопроцессорных систем с общей и распределенной памятью. Модель конвейерной системы.

Модель алгоритма в виде графа "операнд - операции". Представление алгоритма в виде графа потока данных. Расписание параллельных вычислений. Показатель временной сложности алгоритма. Оценка времени выполнения алгоритма для паракомпьютера (предельное распараллеливание) и для систем с конечным количеством процессоров. Зависимость оценок от топологии графа алгоритма и необходимость оптимизации структуры графа. Способы получения оптимального расписания вычислений.

Модель параллельных вычислений в виде сети Петри. Основные понятия теории сетей Петри. Использование сетей Петри для описания параллельных вычислений. Основные проблемы параллельных вычислений: синхронизация, взаимоисключение, блокировка (тупики).

Модель параллельных вычислений в виде графа "процесс-ресурс". Понятие процесса. Проблемы взаимодействия процессов. Синхронизация параллельных процессов. Аппарат событий. Концепция ресурса. Механизмы взаимоисключения: алгоритм Деккера, семафоры (Дейкстра), мониторы (Вирт). Примеры решения стандартных задач взаимоисключения: кольцевой буфер, проблема "читатели и писатели". Взаимодействие параллельных процессов посредством механизма передачи сообщений. Механизмы передачи: очереди, почтовые ящики, порты. Принцип рандеву в языках Ада и ОККАМ. Понятие тупика и условия его возникновения. Предотвращение тупиков. Алгоритм банкира. Обнаружение тупиков и восстановление состояния процессов.

Тема 4. Принципы разработки параллельных алгоритмов и программ

Лекций - 6 часа, самостоятельная работа - 2 часа.

Две модели программирования: последовательная и параллельная. Параллелизм данных и параллелизм задач. Показатель эффективности распараллеливания (ускорение). Эффективность использования вычислительной системы. Способы оценки показателей. Основные характеристики вычислительной системы, влияющие на величины ускорения и эффективности (архитектура, количество процессоров, топология каналов передачи данных).

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

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

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

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

Тема 5. Средства разработки параллельных программ

Лекций - 2 часа, самостоятельная работа - 2 часа.

Использование распространенных языков программирования и коммуникационных библиотек и интерфейсов. Традиционные последовательные языки и распараллеливающие компиляторы, проблема выделения потенциального параллелизма последовательных программ. Специальные комментарии и директивы компилятору.

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

Тема 6. Интерфейс передачи сообщений MPI

Лекций - 9 часов, самостоятельная работа - 6 часов.

Общие принципы построения и реализации MPI. Разработчики, история создания. Шесть общих функций MPI, коммуникаторы. Функции обмена сообщениями типа «точка-точка»: блокирующий и неблокирующий обмен, синхронные и стандартные посылки сообщений. Предотвращение тупиков. Коллективные функции обмена данных: широковещательная рассылка, функции сбора и рассыпания данных. Функции редукции данных. Создание групп процессов, области связи, коммуникаторы. Обмен данными внутри группы, межгрупповой обмен. Топология обменов. Декартовы топологии. Топологии произвольного графа. Примеры параллельных программ на основе обработки массивов.

Тема 7. Технология программирования OpenMP.

Лекций - 2 часа, самостоятельная работа - 2 час.

Последовательные и параллельные нити программы. Организация параллельных секций. Параллельные циклы. Директивы синхронизации. Классы переменных. Спецификации OpenMP для языков C и С++.

Тема 8. DVM система разработки параллельных программ.

Лекций – 2 часа, самостоятельная работа ­– 1 час.

Основные возможности системы. Мобильность и эффективность выполнения программ. Состав DVM-системы. Основные директивы распараллеливания. Использование отладчика и анализатора производительности DVM-программ.

Тема 9. Заключение

Лекций – 1 час, самостоятельная работа ­– 1 час.

Трудности и перспективы развития МВС и параллельного программирования.

4.4. Лабораторные занятия

1 Разработка, отладка и исполнение параллельной программы с использованием функций MPI (9 часов)

2 Анализ параллельных программ с использованием MPI (4 часа)

3 Параллельное программирование в среде OpenMP / DVM (4 часа)

4.5. Формы самостоятельной работы

	Наименование работы	Часов	Форма контроля
1	Проработка лекционного материала	27	Опрос на зачете
2	Освоение программной системы для изучения и исследования параллельных вычислений	24	Защита отчетов

Всего часов, отводимых на самостоятельную

работу по учебному плану 51

5. СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

Основная литература

1.  Теория и практика параллельных вычислений: БИНОМ. Лаборатория знаний, Интернет университет информационных технологий – ИНТУИТ. ру, 2007

2.  , Воеводин Вл. В. Параллельные вычисления, – СПБ.: БХВ-Петербург, 2002.

3.  Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. – СПб.: БХВ-Перербург, 2002.

4.  , Основы параллельных вычислений для многопроцессорных вычислительных систем. – Н. Новгород, ННГУ, 2003.

5.  Параллельное программирование в MPI. – Ижевск, 2004.

6.  , Программирование для многопроцессорных систем в стандарте MPI. – Минск:БГУ, 2002.

Дополнительная литература

7.  Антонов в параллельные вычисления. – М.:МГУ, 2002.

8.  , , Многопроцессорные системы и параллельное программирование. – Ростов-на-Дону: РГУ, 2000.

9.  , Параллельные вычисления на многопроцессорных вычислительных системах. – Томск: ТГУ, 2002

10.  Параллельные ЭВМ. Архитектура, программирование, алгоритмы. – М.: Радио и связь, 1986.

11.  Основы параллельного программирования. – М.:БИНОМ. Лаборатория знаний, 2003.

Информационные ресурсы сети Интернет

12.  Информационно-аналитические материалы по параллельным вычислениям Научно-исследовательский вычислительный центр МГУ (http://www. parallel. ru)

13.  Теория и практика параллельных вычислений. (http://www. intuit. ru/department/calculate/paraltp/index. html)

14.  Средства программирования для многопроцессорных вычислительных систем. – СПб: СПбГУ, 2007 (http://www. phys. spb. ru/content/File/Library/studentlectures/Nemnugin/Metod_Nemnygin_Intel. pdf)

15.  Foster I. Designed and Building Parallel Programs. – Addison Wesley, 1994. (http://www. mcs. anl. gov/dvpp. html)

16.  Introduction to parallel Computing (Teaching Course). (http://www. ece. northwestern. edu/cource/358.html)

6. КОНТРОЛИРУЮЩИЕ МАТЕРИАЛЫ

6.1. Список вопросов к зачету

1.  Каковы ограничения максимальной производительности однопроцессорных ЭВМ.

2.  Параллельные и распределенные вычисления и их техническая основа – вычислительные кластеры, ГРИД-системы и суперкомпьютеры.

3.  Виды параллелизма.

4.  Основные проблемы использования параллельной обработки данных.

5.  Закон Амдаля о существовании последовательных алгоритмов.

6.  Закон Мура о росте производительности последовательных компьютеров.

7.  Закон Гроша о стоимости параллельных систем.

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

9.  Конвейерные и векторные вычисления. Процессорные матрицы. Многопроцессорные вычислительные системы с общей и распределенной памятью.

10.  Схемы коммутации.

11.  Схемы взаимодействия ветвей параллельных алгоритмов

12.  Типовые топологии схем коммутации.

13.  Аппаратная реализация и программная эмуляция топологий.

14.  Классификация многопроцессорных вычислительных систем.

15.  Систематика Флинна. Потоки данных (команд).

16.  Виды многопроцессорных систем и кластеров

17.  Модели параллельных вычислительных процессов.

18.  Концепция неограниченного параллелизма. Компьютер с неограниченным параллелизмом (паракомпьютер).