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