МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Саратовский государственный университет имени
Факультет компьютерных наук и информационных технологий
УТВЕРЖДАЮ
_______________________
"_____"__________________20___ г.
ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ
Технология параллельных и распределенных вычислений
Направление подготовки
010300 – Фундаментальная информатика и информационные технологии
Профиль подготовки
Информатика и компьютерные науки
Квалификация (степень) выпускника
Бакалавр
Форма обучения
Очная
Саратов
2011
1. Цели освоения дисциплины.
Целями освоения дисциплины «Технология параллельных и распределенных вычислений» являются знакомство с основами параллельного и распределенного программирования, изучение моделей параллельных вычислений, формирование практических навыков разработки параллельных и распределенных программ.
Потребность решения сложных прикладных задач с большим объемом вычислений и принципиальная ограниченность максимального быстродействия "классических" - по схеме фон Неймана - ЭВМ привели к появлению многопроцессорных вычислительных систем (МВС). Использование таких средств вычислительной техники позволяет существенно увеличивать производительность ЭВМ при любом существующем уровне развития компьютерного оборудования. При этом, однако, необходимо "параллельное" обобщение традиционной - последовательной - технологии решения задач на ЭВМ. Так, численные методы в случае МВС должны проектироваться как системы параллельных и взаимодействующих между собой процессов, допускающих исполнение на независимых процессорах. Применяемые алгоритмические языки и системное программное обеспечение должны обеспечивать создание параллельных программ, организовывать синхронизацию и взаимоисключение асинхронных процессов и т. п.
Предметом рассмотрения настоящего курса и является изучение перечисленного круга вопросов. Цель курса состоит в изложении математических моделей и методов параллельного программирования для многопроцессорных вычислительных систем.
2. Место дисциплины в структуре ООП бакалавриата.
Данная учебная дисциплина входит в раздел «Профессиональный цикл. Вариативная часть» ФГОС-3 и является частью модуля «Параллельное и распределенное программирование». Читается в 7 семестре.
Для успешного освоения дисциплины необходимы компетенции, сформированные в ходе изучения курса «Параллельные вычисления».
Компетенции, сформированные у студентов в результате изучения необходимы для дальнейшего изучения дисциплин «Архитектура распределенных приложений» и «Введение в GRID-технологии».
Предполагается наличие у обучаемых общих сведений по курсам «Основы программирования», «Дискретная математика», «Архитектура вычислительных систем», «Операционные системы». При выполнении практических и лабораторных заданий обучаемые должны владеть методами программирования на алгоритмическом языке С.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины:
Данная дисциплина способствует формированию следующих компетенций:
способность работать с информацией в глобальных компьютерных сетях (ОК 13);
умение понять поставленную задачу (ПК 2);
детальное знание парадигм и методологий программирования, особенностей языков программирования общего и специального назначения, наиболее широко используемых средств программирования (ПК-18);
владение методами и навыками использования и конфигурирования сетевых технологий (ПК-23);
понимание теоретических основ и общих принципов использования следующих профессиональных областей (ПК-26): Анализ бизнес-требований; Электронная коммерция; Экономика программной инженерии; Сопровождение программного обеспечения; Процессы жизненного цикла программного обеспечения; Качество программного обеспечения; Технология вычислительных систем; Системное администрирование; Системная интеграция; Основы программной инженерии; Верификация и испытания программного обеспечения; Встроенные системы; Распределенные системы; Управление безопасностью ИТ; Управление инфокоммуникациями;
способность решать задачи производственной и технологической деятельности на высоком профессиональном уровне, включая: разработку алгоритмических и программных решений в области системного и прикладного программирования; разработку математических, информационных и имитационных моделей по тематике выполняемых опытно-конструкторских работ и проектов; создание информационных ресурсов глобальных сетей, образовательного контента, прикладных баз данных; разработку тестов и средств тестирования систем и средств на соответствие стандартам и исходным требованиям; разработку эргономичных человеко-машинных интерфейсов в соответствии с профилизацией (ПК-28);
В результате освоения дисциплины обучающийся должен знать:
О моделях параллелизма в построении многопоточных и распределенных решений;
О методах применения подходов распараллеливания для решения фундаментальных и прикладных задач линейной алгебры, математической статистики, теории обработки сигналов и численных методов;
О средствах параллельного программирования на системах с распределенной и общей памятью
О методах параллельного программирования
О моделях параллельно-последовательного программирования
О моделях асинхронных вычислений
О моделях синхронных вычислений
уметь:
использовать языки параллельного программирования для программирования параллельных и распределенных решений,
анализировать необходимость и целесообразность применения методов параллелизма для решения поставленных задач;
использовать примитивы синхронизации и средства распараллеливания потоков исполнения POSIX Threads.
использовать средства параллельного программирования MPI
владеть:
инструментами параллельного программирования, а также инструментами отладки и тестирования параллельных программ.
навыками практического распараллеливания алгоритмов реальных задач
инструментами разработки и управления для современных вычислительных кластеров
4. Структура и содержание дисциплины.
Общая трудоемкость дисциплины составляет 3 зачетных единиц, 108 часа.
№ п/п | Раздел дисциплины | Семестр | Неделя семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) Формы промежуточной аттестации (по семестрам) | |||
Лек | Лаб | Сам | ||||||
1 | ЦЕЛИ И ЗАДАЧИ ВВЕДЕНИЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ | 1 | 1-2 | 2 | 1 | 1 | ||
2 | ПРИНЦИПЫ ПОСТРОЕНИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ | 1 | 3-4 | 2 | 2 | 2 | ||
3 | МОДЕЛИРОВАНИЕ И АНАЛИЗ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ | 1 | 4-5 | 2 | 8 | 4 | Отчет по практике. 2 практических задания. | |
4 | ПРИНЦИПЫ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ И ПРОГРАММ | 1 | 6 | 1 | 4 | 2 | Контрольная работа 1 (на 6 неделе) | |
5 | СИСТЕМЫ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ | 1 | 7-9 | 3 | 10 | 5 | Отчет по практике. 2 практических задания. | |
6 | ПАРАЛЛЕЛЬНЫЕ ЧИСЛЕННЫЕ АЛГОРИТМЫ ДЛЯ РЕШЕНИЯ ТИПОВЫХ ЗАДАЧ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ | 1 | 10-12 | 3 | 12 | 6 | Отчет по практике. 3 практических задания. | |
7 | Промежуточная аттестация | 1 | 13 | 1 | 2 | 0 | Контрольная работа 2 (на 13 неделе) | |
Итого | Экзамен | |||||||
13 | 39 | 20 |
1. ЦЕЛИ И ЗАДАЧИ ВВЕДЕНИЯ ПАРАЛЛЕЛЬНОЙ ОБРАБОТКИ ДАННЫХ
1.1.Необходимость.
Ограничение максимальной производительности однопроцессорных ЭВМ. Постоянная необходимость решения задач, превышающих возможности современных ЭВМ (проблемы "большого вызова"). Автоматизация управления распределенных технических систем. Технические требования по снижению стоимости и повышению надежности.
1.2. История введения параллелизма (ENIAC, IBM-701, 704, 709, ATLAS, CDC 6600, 7600, ILLIAC IV, Cray-1, Эльбрус)
1.3. Различие многозадачных, параллельных и распределенных вычислений
1.4. Проблемы использования параллелизма
Существование последовательных алгоритмов (закон Амдаля). Повышение производительности последовательных компьютеров (закон Мура). Потери на взаимодействие и передачу данных (гипотеза Минского). Высокая стоимость параллельных систем (закон Гроша). "Последовательность" существующих алгоритмов и программного обеспечения. Зависимость эффективности параллельных вычислений от учета особенностей аппаратуры. Сложность разработки параллельных алгоритмов. Трудоемкость проверки правильности параллельных программ.
1.5. Требования к представлению параллельного алгоритма.
Методы и средства параллельной обработки информации: параллельные вычислительные методы, параллельные вычислительные системы, параллельное программирование.
2. ПРИНЦИПЫ ПОСТРОЕНИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ
2.1. Пути достижения параллелизма
Функциональные вычислительные устройства. Многоуровневая и модульная память. Конвейерные и векторные вычисления. Процессорные матрицы. Многопроцессорные вычислительные системы с общей и распределенной памятью (мультипроцессоры и мультикомпьютеры). Микропроцессорные системы.
2.2. Способы построения многопроцессорных вычислительных систем
Схемы коммутации (полная коммутация - общая память, перекрестные коммутаторы, локальные схемы коммутации - общая шина, решетки, кластеры). Анализ параллельных алгоритмов и типовые топологии схем коммутации - кольцо, линейка, решетки, полный граф, гиперкуб, тор, дерево. Аппаратная реализация и программная эмуляция топологий.
2.3. Виды параллельных вычислительных систем
СуперЭВМ. Многопроцессорные вычислительные комплексы (МВС). Многомашинные вычислительные комплексы. Сети ЭВМ.
Примеры современных высокопроизводительных вычислительных систем (Cray T932, IBM SP2, HP Exemplar, ASCI RED). Суперкомпьютерные вычислительные системы в России.
2.4. Классификация МВС
Систематики Флинна и Шора. Потоки данных (команд). Структурная нотация Хокни и Джесхоупа.
2.5. Оценка производительности МВС
Общее выражение для оценки производительности для разного типа МВС. Максимальная (пиковая) производительность. Степень параллелизма (длина полупроизводительности). Удельная производительность. Значения показателей для ряда МВС.
2.6. Взаимодействующие процессы
Средства спецификации параллельных процессов; механизмы взаимодействия асинхронных параллельных процессов; синхронизирующие примитивы.
3. МОДЕЛИРОВАНИЕ И АНАЛИЗ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ
3.1. Модели параллельных вычислительных систем
Компьютер с неограниченным параллелизмом (паракомпьютер). Модели многопроцессорных систем с общей и распределенной памятью. Модель конвейерной системы.
3.2. Модель алгоритма в виде графа "операнд - операции"
Представление алгоритма в виде графа потока данных. Расписание параллельных вычислений. Показатель временной сложности алгоритма. Оценка времени выполнения алгоритма для паракомпьютера (предельное распараллеливание) и для систем с конечным количеством процессоров. Зависимость оценок от топологии графа алгоритма и необходимость оптимизации структуры графа. Способы получения оптимального расписания вычислений.
3.3. Модель параллельных вычислений в виде сети Петри
Основные понятия теории сетей Петри. Использование сетей Петри для описания параллельных вычислений. Демонстрация основных проблем параллельных вычислений: синхронизация, взаимоисключение, блокировка (тупики).
3.4. Модель параллельных вычислений в виде графа "процесс-ресурс"
Понятие процесса. Синхронизация параллельных процессов. Аппарат событий. Пример реализации в операционной системе Unix.
Взаимоисключение параллельных процессов. Концепция ресурса. Механизмы взаимоисключения: алгоритм Деккера, семафоры (Дейкстра), мониторы (Вирт). Примеры решения стандартных задач взаимоисключения: кольцевой буфер, проблема "читатели и писатели".
Взаимодействие параллельных процессов посредством механизма передачи сообщений. Механизмы передачи: очереди, почтовые ящики, порты. Принцип рандеву в языках Ада и ОККАМ.
3.5. Проблемы взаимодействия процессов.
Понятие тупика и условия его возникновения. Предотвращение тупиков. Алгоритм банкира. Обнаружение тупиков и восстановление состояния процессов.
Многозадачный режим работы ЭВМ как частный случай параллельной обработки.
3.6. Синхронизация процессов через доступ к общим ресурсам
Критические секции. Задача взаимного исключения. Барьерная синхронизация. Синхронизация типа: "производитель-потребитель". Семафоры. Задача взаимного исключения с семафорами. Задача "производитель-потребитель" с ограниченным буфером. Задача "читатели-писатели". Взаимная блокировка. Задача о 5-ти обедающих философах. Мониторы. Определение монитора. Задача "производитель-потребитель". Задача "читатели-писатели".
4. ПРИНЦИПЫ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ И ПРОГРАММ
4.1. Оценка эффективности параллельных вычислений
Показатель эффекта распараллеливания (ускорение). Эффективность использования вычислительной системы. Способы оценки показателей. Основные характеристики вычислительной системы, влияющие на величины ускорения и эффективности (архитектура, количество процессоров, топология каналов передачи данных).
4.2. Оценка коммуникационной трудоемкости параллельных алгоритмов
Характеристики топологий сети передачи данных. Алгоритмы маршрутизации. Методы передачи данных.
Анализ трудоемкости основных операций передачи данных. Передача данных между двумя процессорами сети. Одиночная и множественная рассылка сообщений. Операция циклического сдвига.
Методы логического представления топологии коммуникационной среды. Отображение кольцевой топологии и топологии решетки на гиперкуб.
4.3. Уровни распараллеливания вычислений
Распараллеливание вычислений на уровне команд, выражений, программных модулей, отдельно выполняемых заданий.
4.4. Этапы построения параллельных алгоритмов и программ
Выбор параллельного алгоритма. Реализация алгоритма в виде параллельной программы. Построение исполняемой программы для параллельной вычислительной системы. Параллельное исполнение машинной программы. Частные постановки: выбор оптимального алгоритма для конкретной вычислительной системы, нахождение наилучшей топологии вычислительной системы для решения определенной задачи, распараллеливание существующего алгоритма.
4.5. Технологические аспекты распараллеливания
Декомпозиция алгоритма на параллельно исполняемые фрагменты вычислений. Распределение заданий по процессорам и балансировка. Синхронизация и взаимоисключение. Организация взаимодействия.
4.6. Синхронизация процессов через обмен данными.
Асинхронная передача сообщений. Синхронная передача сообщений. Параллельная программа разделения множеств (анализ корректности).
5. СИСТЕМЫ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ
5.1. Расширение существующих языков программирования
Общая характеристика стандарта OpenMP. Создание параллельных областей. Разделение вычислительной нагрузки между потоками. Работа с данными. Синхронизация. Функции и переменные окружения. Сравнительная характеристика подходов параллельного программирования для систем с распределенной и общей памятью.
5.2. Разработка специализированных библиотек
Система PVM. Концепция параллельной виртуальной вычислительной машины и ее представление в виде распределенной неоднородной системы компьютеров. Представление программной системы на виртуальной машине. Основные программные примитивы системы PVM. Пример использования.
Система MPI. Общая характеристика. Поддержка модели взаимодействия параллельных вычислителей при помощи передачи сообщений. Основные программные примитивы системы MPI. Пример использования.
Концепция виртуальных процессоров и каналов передачи данных. Виртуальные топологии системы: кольцо, линейка, звезда, решетка, дерево. Основные программные примитивы. Пример использования.
5.3. Краткий обзор языка MPI.
Модели вычислений, поддерживаемые MPI. Парные взаимодействия. Коллективные взаимодействия. Виртуальные топологии. MPI - типы данных.
Краткий обзор языка OpenMP. Введение. Директивы языка OpenMP.
5.4. Обзор библиотеки POSIX Threads. Основные функции, приемы параллельного программирования.
6. ПАРАЛЛЕЛЬНЫЕ ЧИСЛЕННЫЕ АЛГОРИТМЫ ДЛЯ РЕШЕНИЯ ТИПОВЫХ ЗАДАЧ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
6.1. Общие способы распараллеливания алгоритмов
Выявление функциональной независимости отдельных фрагментов алгоритма (параллелизм команд). Геометрическое разделение вычислений (параллелизм данных). Иерархическая декомпозиция обработки данных. Параллельно-последовательные модели программирования. MPMD - модель программирования. SPMD - модель программирования. Необходимость явного распараллеливания. Ускорение и эффективность. Закон Амдала.
6.2. Организация параллельного исполнения рекурсивных вычислений
Проблема рекурсивной зависимости этапов обработки данных. Каскадная схема. Подход для получения асимптотически ненулевой эффективности. Метод Оутса. Пример для вычисления частичных и общей сумм.
6.3. Параллельные численные алгоритмы линейной алгебры
Способы разбиения матриц (горизонтальная, вертикальная, блочные схемы). Методы вычисления произведения матриц с использованием разных схем разбиения матриц. Обеспечение предельно допустимого параллелизма. Обращение матриц. Параллельные методы решения систем линейных уравнений.
6.4. Параллельные численные алгоритмы решения дифференциальных уравнений в частных производных
Параллельная реализация прямых и итерационных методов решения дифференциальных уравнений в частных производных. Анализ разностных схем для эффективного разделения области определения решаемых задач.
5. Образовательные технологии
При проведении занятий по данному курсу используются следующие активные и интерактивные формы: организация дискуссий и обсуждений спорных вопросов, использование метода мозгового штурма, использование мультимедийных презентаций.
6. Учебно-методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины.
7. Учебно-методическое и информационное обеспечение дисциплины.
а) основная литература:
1. Богачев параллельного программирования. - М.: БИНОМ. Лаборатория знаний, 2010.
2. , Воеводин Вл. В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2004.
3. Организация параллельных ЭВМ и суперскалярных процессоров [Текст] : учеб. пособие для студентов вузов - Минск : Белгосуниверситет, 19, [1] с.
4. ; пер. с англ. и [др.] ; под ред. . Основы многопоточного, параллельного и распределённого программирования [Текст] = Foundations of Multithreaded, Parallel, and Distributed Programming : [учеб. пособие] - М. ; СПб. ; Киев : Вильямс, 2003. – 505
5. , , Параллельные численные алгоритмы. Решение задач многофазной гидродинамики и астрофизики [Текст] : учеб. пособие - Новосиб. гос. ун-т, Фак. информ. технологий. - Новосибирск : [б. и.], 2006. – 145
6. , . Параллельные вычисления [Текст] : учеб. пособие - СПб. : БХВ-Петербург, 2004. – 599
7. . Параллельная обработка данных [Текст] : учеб. пособие для студентов вузов - М. : Изд. центр "Академия", 20, [2] с. - (Университетский учебник. Прикладная математика и информатика). - Библиогр.: с. 328-330
б) дополнительная литература:
8. Параллельное программирование для многопроцессорных вычислительных систем - СПб.: БХВ-Петербург, 2002
9. . Параллельные вычислительные системы. - М.: Нолидж, 1999.
10. Корнеев программирование в MPI. Москва-Ижевск: Институт компьютерных исследований, 2003.
11. Информационно-аналитические материалы по параллельным вычислениям (http://www. *****)
12. Информационные материалы рабочей группы IEEE по кластерным вычислениям (http://www. ieeetfcc. org)
13. Introduction to Parallel Computing (Teaching Course) (http://www. ece. nwu. edu/~choudhar/C58/)
14. Foster I. Designing and Building Parallel Programs. - Addison Wesley, 1994.(http://www. mcs. anl. gov/dbpp)
8. Материально-техническое обеспечение дисциплины.
· лекционная аудитория с мультимедийным оборудованием с выходом в Интернет,
· компьютерные классы с программным обеспечением под управлением операционной системы Microsoft Windows 7 или Linux с подключением к Internet, рассчитанные на обучение группы студентов из 8 – 12 человек, удовлетворяющие санитарно-гигиеническим требованиям;
· Компилятор языка Си.
Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и Примерной ООП ВПО по направлению 010300 Фундаментальная информатика и информационные технологии и профилю подготовки Информатика и компьютерные науки.
Автор доцент | ___________ |
|
Программа одобрена на заседании базовой кафедры «Технологии программирования» от «15» апреля 2011 года, протокол
Заведующий базовой кафедрой «Технологии программирования» | ___________ |
|
Декан факультета КНиИТ, Доцент | ___________ |
|
