Параллельные вычисления (базовый курс)

Глава 1. Архитектура параллельных вычислительных систем

Глава 1.1. Основные классы параллельных вычислительных систем

1.1.1. Классификация параллельных вычислительных систем

Тест: Классификация вычислительных систем по Флину

Тест: Классификация вычислительных систем по типу строения памяти

1.1.2. Векторно-конвейерные системы и векторно-параллельные (SIMD-системы)

Тест: Классификация SIMD-вычислительных систем

1.1.3. Многопроцессорные системы (MIMD-системы)

Тест: Классификация MIMD-систем

1.1.4. Многопроцессорные системы (MIMD-системы). Вычислительные кластеры

Тест: Классификация вычислительных кластеров

1.1.5. Производительность параллельных вычислительных систем

Тест: Основные меры производительности параллельных вычислительных систем

Тест: Гипотеза Минского

Глава 1.2. Коммуникационная среда параллельных вычислительных систем

1.2.1. Компоненты коммуникационной среды

Тест: Компоненты коммуникационной среды

1.2.2. Топологии коммуникационных сетей

Тест: Расстояние между процессорами и диаметр и коммуникационной сети

Тест: Типовые топологии коммуникационной сети

1.2.3. Сетевые коммутаторы

Тест: Классификация сетевых коммутаторов

1.2.4. Основные характеристики коммуникационных сетей

Тест: Основные параметры коммуникационной сети

Глава 1.3. Параллельные системы нетрадиционной архитектуры

1.3.1. Нейросетевые вычислительные системы

Тест: Определение искусственного нейрона

Тест: Классификация нейронных сетей

1.3.2. Вычислительные машины потока данных и ассоциативные вычислительные машины

Тест: Формат команды машины потока данных

Тест: Структура ассоциативного запоминающего устройства

Глава 2. Программное обеспечение параллельных вычислительных систем

Глава 2.1. Классификация и основные понятия операционных систем параллельных вычислительных систем

2.1.1. Классификация мультипроцессорных операционных систем

Тест: Классификация операционных систем мультипроцессоров

2.1.2. Основные понятия многопроцессорных операционных систем

Тест: Основные функции операционных систем МВС

Тест: Понятия процесса, контекста процесса, потока (нити)

Глава 2.2. Операционные системы параллельных вычислительных систем. Синхронизация и коммуникации процессов.

2.2.1. Операционные системы мультипроцессоров. Синхронизация процессов

Тест: Необходимость синхронизации процессов

Тест: Критическая область (критическая секция)

Тест: Понятия семафора, двоичного семафора

Тест: Понятия спин-блокировки и двоичного экспоненциального отката

2.2.2. Операционные системы мультикомпьютеров. Коммуникации процессов

Тест: Варианты реализации обмена данными между процессами посредством передачи сообщений

Тест: Обмен данными между процессами посредством передачи сообщений. Вызов удаленной процедуры

Тест: Обмен данными между процессами посредством передачи сообщений. Простое рандеву

2.2.3. Операционные системы мультикомпьютеров. Управление распределенной памятью

Тест: Преимущества модели обмена данными через общую память

Тест: Основные функции подсистемы управления распределенной памятью в ОС мультикомпьютеров

Тест: Миграционный алгоритм управления распределенной памятью

Тест: Алгоритм репликации для управления распределенной памятью

Тест: Алгоритм полного размножения для управления распределенной памятью

Глава 2.3. Операционные системы параллельных вычислительных систем. Планирование процессов

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

Тест: Постановка задачи оптимального отображения

Тест: Балансировка загрузки

Тест: Статическая и динамическая балансировка загрузки

Тест: Динамическая балансировка загрузки

2.3.2. Операционные системы мультипроцессоров. Планирование процессов

Тест: Планирование процессов в мультипроцессоре

Тест: Планирование независимых процессов

Тест: Планирование зависимых процессов

2.3.3. Операционные системы мультикомпьютеров. Планирование процессов

Тест: Балансировка загрузки, инициируемая отправителем

Тест: Балансировка загрузки, инициируемая получателем

Тест: Иерархический графовый алгоритм балансировки загрузки

Тест: Рекурсивное огрубление графа на основе паросочетаний

Тест: Рекурсивное огрубление графа на основе паросочетаний из тяжелых клик

Тест: Рекурсивная бисекция графа

2.3.4. Операционные системы мультикомпьютеров. Спектральный алгоритм балансировки загрузки

Тест: Матрица Лапласа для графа

Тест: Спектральный алгоритм балансировки загрузки

2.3.5. Отображение процессов с регулярной структурой на типовые архитектуры мультикомпьютеров

Тест: Отображение кольца процессов на гиперкуб

Тест: Отображение двумерной решетки процессов на гиперкуб

Глава 2.4. Языки высокого уровня для программирования векторно-конвейерных и векторно-параллельных вычислительных систем

2.4.1. Выборка элементов массива

Тест: Проекционная выборка с помощью целочисленных массивов

Тест: Линейное отображение с помощью целочисленных массивов

Тест: Проекционная выборка с помощью булевых массивов

Тест: Линейное отображение с помощью булевых массивов

2.4.2. Функции обработки массивов для получения соответствия

Тест: Соответствие массивов

Тест: Функции понижения ранга

Тест: Операция переформирования массивов

2.4.3. Параллельные операторы

Глава 2.5. Языки высокого уровня для программирования MIMD-вычислительных систем

2.5.1. MPMD-языки высокого уровня. Средства описания процессов, средства инициализации и завершения процессов

Тест: MPMD- и SPMD-парадигмы параллельного программирования

Тест: Гранулированность параллельной программы

2.5.2. MPMD-языки высокого уровня. Средства синхронизации и обмена данными

2.5.3. MPMD-языки высокого уровня. Средства конфигурирования

Тест: Средства конфигурирования

2.5.4. SPMD-языки высокого уровня

Глава 2.6. Автоматическое распараллеливание последовательных программ

2.6.1. Степени параллелизма. Статическое и динамическое распараллеливание последовательных программ

2.6.2. Распараллеливание ациклических участков

Тест: Граф зависимостей по данным

Тест: Алгоритм построения ЯПФ

Тест: Параметры ЯПФ

2.6.3. Особенности распараллеливание выражений

Тест: Задача распараллеливания выражений

2.6.4. Распараллеливание циклических фрагментов программ

Тест: Пространство итераций

Тест: Задача распараллеливания циклов

Глава 2.7. Коммуникационные библиотеки для организации параллельного выполнения программ

2.7.1. Библиотека OpenMP

2.7.2. Библиотека MPI

2.7.3. Библиотека PVM

Глава 2.8. Средства отладки и профилирования параллельных программ

2.8.1. Средства отладки параллельных программ

2.8.2. Средства профилирования параллельных программ

Глава 3. Алгоритмы для параллельных вычислительных систем

Глава 3.1. Общие вопросы синтеза алгоритмов для параллельных вычислительных систем

3.1.1. Типы параллелизма и методы синтеза параллельных алгоритмов

Тест: Зернистость алгоритма

Тест: Параллелизм данных

Тест: Функциональный параллелизм

Тест: Геометрический параллелизм

3.1.2. Оценка эффективности параллельных алгоритмов

Тест: PRAM

Тест: Эффективный параллельный алгоритм

Тест: Ускорение параллельного алгоритма

Тест: Эффективность параллельного алгоритма

Тест: Закон Амдала

Тест: Парадокс параллелизма

3.1.3. Параллельные алгоритмы вычисления рекурсий

Глава 3.2. Параллельные методы и алгоритмы линейной алгебры

3.2.1. Базовые алгоритмы

3.2.2. Прямые методы решения систем линейных алгебраических уравнений. Метод исключения Гаусса

3.2.3. Итерационные методы решения систем линейных алгебраических уравнений. Метод Якоби

3.2.4. Методы минимизации для решения систем линейных алгебраических уравнений. Метод сопряженных направлений

Глава 3.3. Параллельные алгоритмы интегрирования обыкновенных дифференциальных уравнений

3.3.1. Задача Коши

3.3.2. Двухточечная краевая задача для уравнений второго порядка

Глава 3.4. Параллельные алгоритмы решения краевых задач для дифференциальных уравнений в частных производных

3.4.1. Нестационарная задача

3.4.2. Стационарная краевая задача

4. Литература