Параллельные алгоритмы

(с) М.В.Якобовский, 2011

 

Л1 Введение

Области применения многопроцессорных систем (МВС), классы решаемых на МВС задач.

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

Примеры многопроцессорных и распределенных вычислительных систем. Транспьютеры.

Внутренний параллелизм. Ускорение и эффективность параллельных алгоритмов.

 

Л2 Архитектуры ЭВМ

Последовательные вычислительные системы. Принципы Фон-Неймана.

Общая память (UMA). Проблема использования общих переменных.

Проблема когерентности кэш памяти.

Распределенная память (двусторонние обмены). Смешанные архитектуры.

Односторонние обмены. NUMA. ссNUMA. Топологии вычислительных систем.

 

Л3 Базовые алгоритмы (начало)

Сдваивание, каскадное сдваивание. Геометрический параллелизм.

Канал передачи данных, его свойства (латентность и пропускная способность).

Виды обменов (синхронные, асинхронные, небуферизованные, буферизованные).

Проблема балансировки загрузки процессоров.

Статическая и динамическая балансировка. Диффузная балансировка загрузки процессоров.

 

Л4 Базовые алгоритмы (продолжение)

Конвейерный параллелизм.

Коллективное решение.

Семафоры, P и V операции, критические секции, мониторы.

Барьерная синхронизация.

Определение суммы ряда x^i/i!.

 

Л5 Сортировка данных с точки зрения МВС

Построение эталонного последовательного алгоритма сортировки.

Сети сортировки.

Четно-нечетные перестановки.

Четно-нечетное слияние Бэтчера.

 

Л6 Динамическая балансировка загрузки процессоров.

Cерверный параллелизм.

Адаптивное интегрирование

 

Л7 Общие проблемы применения МВС

Декомпозиция графов. Критерии декомпозиции.

Иерархические алгоритмы рационального разбиения графов. Локальное уточнение.

Спектральная бисекция. Инкрементный алгоритм.

Визуализация сеточных данных. Клиент-серверная технология.

Распределённый ввод-вывод. Огрубление данных с контролируемой точностью.

Параллельная генерация псевдослучайных чисел.

Линейно-конгруэнтные генераторы. M-последовательности