Параллельные и высокопроизводительные вычисления

Программа курса

Введение

  1. Тенденции развития вычислительных систем, обуславливающие необходимость применения распределённых (параллельных) методов вычислений
  2. Примеры вычислительно ёмких задач из разных областей науки
  3. Классификация параллельных систем (SIMD, MISD...). Краткая история параллельных систем
  4. Современные высокопроизводительные системы как аппаратно-программные комплексы: начиная от расширений SSE, через многоядерность к узлам кластеров

Параллелизм

  1. Способы распараллеливания программ: по данным; по управлению (операциям)
  2. Проблема автоматизации распараллеливания: текущее состояние средств, способных выявлять некоторые виды параллелизма. Обоснование невозможности полного решения проблемы на текущий момент
  3. Понятия ускорения, эффективности (закон Амдала), масштабируемости распараллеленного алгоритма
  4. Напоминание о процессах и потоках (контексты, состояния)
  5. Приоритеты (java, Windows, Unix)
  6. Планирование
    • Демоны
    • Сироты
    • Зомби
  7. Причины некоторых преимуществ потоков над процессами
  8. Особенности реализации процессов и потоков в различных ОС

Основы программирования потоков

  1. Posix-потоки (Posix-threads)
  2. Java-потоки (Green-threads)
  3. Boost-потоки (группы потоков)
  4. Сравнение различных потоков (таблица соответствия операций)
  5. Обработка исключений
  6. Spurious wakeups

Синхронизация

  1. Примитивы
    • Критическая секции
    • Мьютекс (futex)
    • Семафор
    • Событие
    • Interlocked-функции
    • Условные переменные
  2. Виды мьютексов
    • рекурсивный/нерекурсивный
    • разделяемый (read/write), его целесообразность
    • spin_mutex
    • именованный
  3. Виды синхронизации
    • Грубая
    • Тонкая
    • Оптимистичная
    • Ленивая
    • Неблокирующая (Lock-free на примере списка)
  4. Неявная синхронизация в графических библиотеках
  5. Алгоритмы Петерсона и Лампорта

Поиск ошибок и анализ производительности

  1. Основные ошибки многопоточного программирования
    • Гонки данных (Data Race)
    • Взаимная блокировка (Deadlock)
    • Потерянный сигнал
  2. Специфические ошибки
    • Реакция потока на сигнал
    • Блокировки при fork многопоточных программ
    • Проблема ABA
    • Инверсия приоритетов
  3. Принципы проектирования многопоточных приложений
  4. Средства поиска ошибок
    • Intel Thread Checker
    • Intel Parallel Inspector
    • valgrind (модуль helgrind)
  5. Средства анализа производительности
    • Intel Thread Profiler
    • valgrind (модули callgrind, cachegrind)

OpenMP

  1. История стандарта
  2. Основные служебные функции
  3. Основные директивы препроцессора
    • Создание потоков, параллельные секции (parallel)
    • Работа с данными (shared, private...)
    • Синхронизация (critical, atomic)
    • Взаимодействие потоков (reduction, copyin...)
  4. Контроль числа потоков
  5. Применимость для вложенных вызовов

Intel TBB

  1. Структура библиотеки
  2. Аллокаторы памяти
  3. Потокобезопасные контейнеры
  4. Примитивы синхронизации
  5. Алгоритмы
    • parallel_for
    • parallel_reduce
    • parallel_scan
  6. Деревья задач
  7. Планировщик TBB
    • Возможность контроля пула потоков
    • Динамическое перераспределение задач (work stealing)
    • Порядок выполнения древовидных задач

Java.util.concurrent

  1. Пулы потоков, корректное завершение пула
  2. Контроль задач через Future
  3. Потокобезопасные контейнеры
  4. Примитивы синхронизации

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

  1. || алгоритмы в STL
  2. Алгоритмы на графах
  3. Сортировка
  4. Умножение матриц
  5. Общие подходы к переработке последовательных алгоритмов

Распределённые системы

  1. Определение. Задачи. Принципы построения
    • Открытость
    • Прозрачность
    • Масштабируемость
  2. Программные решения
    • Распределенные операционные системы
    • Сетевые операционные системы
    • Программное обеспечение промежуточного уровня
  3. Модель клиент-сервер. Варианты архитектуры клиент-сервер
  4. Системы без выделенного центра. Многоагентные системы
  5. Взаимодействие компонентов
    • Протоколы (TCP, UDP...)
    • Удаленный вызов процедур
    • Обращение к удаленным объектам (RMI)
    • Связь посредством сообщений
  6. Виды кластерных систем
    • Высокой доступности
    • Балансировки нагрузки
    • Высокой надёжности
    • Вычислительные

Вычислительные кластеры и стандарт MPI

  1. История и назначение стандарта
  2. Общая структура программы
  3. Обмен сообщениями
    • С блокировкой
    • Без блокировки
    • Отложенные запросы на взаимодействие
    • Тупиковые ситуации (deadlock)
  4. Взаимодействие процессов
    • Группы и коммуникаторы
    • Операции коллективного взаимодействия процессов
    • Виртуальные топологии
  5. Средства анализа производительности
    • Jumpshot
    • Intel® Trace Analyzer и Intel® Trace Collector

Консенсус

  1. Линеаризуемость
  2. Атомарный регистр
  3. Консенсусное число
    • Консенсусное число RMW-регистров
    • Универсальность CAS-операций
  4. Атомарный снимок регистров/li>
    • lock-free алгоритм
    • wait-free алгоритм

Шаблоны || программирования

  1. Декомпозиция по задачам
  2. Геометрическая декомпозиция
  3. Декомпозиция рекурсивных задач (Recursive data)
  4. Модели программ
    • SPMD
    • Parallel loops
    • Boss/Worker
    • Pipeline
  5. || алгоритмы в STL

GRID-системы

  1. Концепция GRID
  2. Области применения
  3. Требования к архитектуре GRID
  4. Cloud computing

Дополнительно

  1. Системы сборки проектов (maven + continuum)
  2. Сборка rpm пакетов (mock)
  3. Сервера приложений (WSDL + XSD + SOAP...)
  4. Лямбда-выражения (C++)
  5. Оптимизации в компиляторах