Цель преподавания дисциплины:
обучить студентов теоретическим основам параллельной обработки данных в вычислительных машинах;
привить студентам навыки разработки параллельных алгоритмов и программ.
заложить понимание фундаментальных основ моделирования и анализа параллельных вычислений.
Содержание:
Ограничение максимальной производительности однопроцессорных ЭВМ. Необходимость решения задач, превышающих возможности современных ЭВМ (проблемы "большого вызова") и коллективного режима решения задач. Различие многозадачных, параллельных и распределенных вычислений.
Существование последовательных алгоритмов (закон Амдаля). Повышение производительности последовательных компьютеров (закон Мура). Потери на взаимодействие и передачу данных (гипотеза Минского). Высокая стоимость параллельных систем (закон Гроша). Зависимость эффективности параллельных вычислений от учета особенностей аппаратуры. Сложность разработки параллельных алгоритмов. Трудоемкость проверки правильности параллельных программ.
Функциональные вычислительные устройства. Многоуровневая и модульная память. Конвейерные и векторные вычисления. Процессорные матрицы. Многопроцессорные вычислительные системы с общей и распределенной памятью (мультипроцессоры и мультикомпьютеры). Микропроцессорные системы.
Способы построения многопроцессорных вычислительных систем. Анализ параллельных алгоритмов и типовые топологии схем коммутации – кольцо, линейка, решетки, полный граф, гиперкуб, тор, дерево.
СуперЭВМ. Многопроцессорные вычислительные комплексы. Многомашинные вычислительные комплексы. Сети ЭВМ. Систематики Флинна и Шора. Потоки данных (команд). Структурная нотация Хокни и Джесхоупа.
Общее выражение для оценки производительности для разного типа МВС. Максимальная (пиковая) производительность. Степень параллелизма (длина полупроизводительности). Удельная производительность. Значения показателей для ряда МВС.
Компьютер с неограниченным параллелизмом (паракомпьютер). Модели многопроцессорных систем с общей и распределенной памятью. Модель конвейерной системы.
Представление алгоритма в виде графа потока данных. Расписание параллельных вычислений. Показатель временной сложности алгоритма. Оценка времени выполнения алгоритма для паракомпьютера (предельное распараллеливание) и для систем с конечным количеством процессоров.
Понятие процесса. Синхронизация параллельных процессов. Аппарат событий. Взаимоисключение параллельных процессов. Концепция ресурса. Механизмы взаимоисключения: алгоритм Деккера, семафоры (Дейкстра), мониторы (Вирт).
Взаимодействие параллельных процессов посредством механизма передачи сообщений. Механизмы передачи: очереди, почтовые ящики, порты. Принцип рандеву в языках Ада и ОККАМ.
Проблемы взаимодействия процессов. Понятие тупика и условия его возникновения. Предотвращение тупиков. Алгоритм банкира. Обнаружение тупиков и восстановление состояния процессов. Многозадачный режим как частный случай параллельной обработки.
Показатель эффекта распараллеливания (ускорение). Эффективность использования вычислительной системы. Способы оценки показателей. Основные характеристики вычислительной системы, влияющие на величины ускорения и эффективности (архитектура, количество процессоров, топология каналов передачи данных).
Характеристики топологий сети передачи данных. Алгоритмы маршрутизации. Методы передачи данных. Анализ трудоемкости основных операций передачи данных. Передача данных между двумя процессорами сети. Одиночная и множественная рассылка сообщений. Операция циклического сдвига. Методы логического представления топологии коммуникационной среды. Отображение кольцевой топологии и топологии решетки на гиперкуб.
Распараллеливание вычислений на уровне команд, выражений, программных модулей, отдельно выполняемых заданий.
Выбор параллельного алгоритма. Реализация алгоритма в виде параллельной программы. Построение исполняемой программы для параллельной вычислительной системы. Параллельное исполнение машинной программы.
Декомпозиция алгоритма на параллельно исполняемые фрагменты вычислений. Распределение заданий по процессорам и балансировка. Синхронизация и взаимоисключение. Организация взаимодействия.
Создание параллельных областей. Разделение вычислительной нагрузки между потоками. Работа с данными. Синхронизация. Функции и переменные окружения. Сравнительная характеристика подходов параллельного программирования для систем с распределенной и общей памятью.
Система MPI. Общая характеристика. Поддержка модели взаимодействия параллельных вычислителей при помощи передачи сообщений. Основные программные примитивы системы MPI.
Выявление функциональной независимости отдельных фрагментов алгоритма (параллелизм команд). Геометрическое разделение вычислений (параллелизм данных). Иерархическая декомпозиция обработки данных.
Проблема рекурсивной зависимости этапов обработки данных. Каскадная схема. Подход для получения асимптотически ненулевой эффективности. Метод Оутса. Пример для вычисления частичных и общей сумм.
Способы разбиения матриц (горизонтальная, вертикальная, блочные схемы). Методы вычисления произведения матриц с использованием разных схем разбиения матриц. Обеспечение предельно допустимого параллелизма. Обращение матриц. Параллельные методы решения систем линейных уравнений.
В результате изучения дисциплины студент должен:
иметь представление о целях и задачах параллельной обработки данных, параллельных вычислительных методах и принципах построения параллельных вычислительных систем.
знать архитектурные принципы реализации и языковые механизмы конструирования параллельных программ;
уметь разрабатывать параллельные алгоритмы для решения типовых задач вычислительной математики и обработки данных.
иметь навыки использования стандартных систем разработки параллельных программ.
Разработчик к.т.н., доцент Мунерман В.И.