Введение в параллельные алгоритмы

Информация о курсе

Рассматриваются параллельные алгоритмы и методы решения задач различных классов на многопроцессорных вычислительных системах. Рассматриваются факторы, влияющие на время выполнения параллельных программ и на эффективность использования вычислительной мощности многопроцессорных систем.

Рассматриваются параллельные алгоритмы решения задач различных классов. Курс содержит следующие учебные разделы: cредства описания параллельных алгоритмов;
методы построения параллельных алгоритмов; параллельные алгоритмы сортировки данных;
параллельные алгоритмы генерации псевдослучайных чисел; динамическая балансировка загрузки процессоров на примере параллельных алгоритмов интегрирования функций; параллельные алгоритмы решения систем линейных уравнений специального вида.

Цель

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

Предварительные знания

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

Записаться на программу

Расписание

Время	Лекции	Тесты
15:00 - 16:00 (Москва) 06 октября	Введение Параллельные алгоритмы для многопроцессорных вычислительных систем (МВС). Задачи, решаемые на многопроцессорных системах. Алгоритмы для суперкомпьютеров.
15:00 - 16:00 (Москва) 13 октября	Основные понятия Многопроцессорные системы с общей и с распределенной памятью. Канал передачи данных, его свойства. Синхронная и асинхронная передача данных. Семафоры. Ускорение и эффективность параллельных алгоритмов. Внутренний параллелизм. Пример неэффективного, но быстрого алгоритма.	тест
15:00 - 16:00 (Москва) 20 октября	Методы построения параллельных программ Методы геометрического параллелизма, конвейерного параллелизма, коллективного решения. Их свойства. Проблема балансировки загрузки процессоров. Пример задачи, для параллельного решения которой необходимо создание нового алгоритма.	тест
15:00 - 16:00 (Москва) 27 октября	Сортировка данных с точки зрения МВС (начало) Построение эталонного последовательного алгоритма сортировки. Описание «плохого» последовательного, но быстрого параллельного метода сортировки. Оценка времени выполнения алгоритма в наилучшем, среднем и наихудшем случае. Зависимость времени сортировки от вида исходной последовательности.	тест
15:00 - 16:00 (Москва) 03 ноября	Сортировка данных с точки зрения МВС (окончание) Параллельный алгоритм сортировки. Оценка времени выполнения. Оценка требуемого объема оперативной памяти. Пути сокращения объема передаваемых данных и требуемой оперативной памяти.	тест
15:00 - 16:00 (Москва) 24 ноября	Параллельная генерация псевдослучайных чисел Задачи, решаемые с использованием последовательностей псевдослучайных чисел (ПСЧ). Требования к генераторам ПСЧ для МВС. Параллельные алгоритмы генерации ПСЧ. Тестирование последовательностей.	тест
15:00 - 16:00 (Москва) 01 декабря	Параллельные алгоритмы интегрирования функций Простой параллельный алгоритм интегрирования. Адаптивный алгоритм. Параллельный алгоритм интегрирования с динамической балансировкой загрузки.	тест
15:00 - 16:00 (Москва) 08 декабря	Решение систем линейных уравнений Задачи, приводящие к появлению систем линейных уравнений (СЛАУ) с трехдиагональной матрицей коэффициентов. Параллельные алгоритмы решения трехдиагональных СЛАУ. Итерационные методы. Диффузная балансировка загрузки процессоров.	тест