1. Введение

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

2. Параллелизм

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

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

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

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

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)

6. OpenMP

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

7. Intel TBB

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

8. Java.util.concurrent и Fork-Join Framework

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

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

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

10. Консенсус

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

11. Неблокирующие алгоритмы

1. Атомарный снимок регистров: lock-free алгоритм
2. Примеры неблокирующих алгоритмов на контейнерах

12. Алгоритмы без ожидания

1. Атомарный снимок регистров: wait-free алгоритм
2. Примеры алгоритмов без ожидания на контейнерах

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

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

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

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

15. Облачные вычисления

1. Концепция GRID
2. MapReduce на примере Hadoop

16. Оптимизации в компиляторах

1. Статические оптимизации
2. Оптимизации циклов:
   • Развёртывание
   • Повторение
   • Вынесение инварианта
3. Локальность кэша инструкций
4. JIT-оптимизации
5. Многопоточные оптимизации
   • Объединение захвата примитивов
   • Оптимистичный захват
   • Адаптивные блокировки
6. Замена виртуального вызова

17. Транзакционная память

1. Принцип работы Software transactional memory
2. Идея Hardware transactional memory
3. Преимущества и круг задач.

18. Асинхронный ввод/вывод

1. Шаблоны поведения реактора и проактора
2. Преимущества асинхронной работы и реализация со стороны операционной системы
3. Библиотеки асинхронного ввода/вывода.

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

1. Системы сборки проектов (maven + continuum + archiva)
2. Сборка rpm пакетов (mock)
3. Сервера приложений (WSDL + XSD + SOAP...)
4. Архитектурные особенности ОСРВ (на примере QNX)