Инструменты паралельного программирования в системах с общей памятью

В учебнике описываются методы и инструментальные средства для разработки, отладки и профилировки параллельных программ, ориентированных на работу в системах с общей памятью. Рассматриваются программные пакеты Intel Thread Checker, Intel Thread Profiler, Intel Threading Building Blocks.
Дается вводная информация по пакету Intel Parallel Studio и библиотеке Intel MKL.
Демонстрируется весь цикл работ, включая создание последовательной реализации в качестве базы для сравнения, подготовку параллельной версии, ее отладку, профилировку и оптимизацию.
Изучение проводится на модельных задачах, не требующих наличия специфических знаний из конкретных предметных областей.
Подразумевается знакомство читателя с основами программирования (базовый язык - С/ С++), некоторые задачи требуют сведений из высшей математики (задача Дирихле).
Учебник разработан в лаборатории "Информационные технологии" (ITLab) факультета ВМК ННГУ с использованием материалов, подготовленных в рамках Приоритетного национального проекта "Образование" при поддержке корпорации Intel и Совета по грантам Президента Российской Федерации (грант № НШ-64729.2010.9).
Для преподавателей и научных сотрудников, а также аспирантов и студентов высших учебных заведений.

Содержание

Предисловие (В. А. Садовничий)
Предисловие
ЧАСТЬ I. ОТЛАДКА ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ
1. Intel Thread Checker. Краткое описание
1.1. Назначение Intel Thread Checker
1.2. Возможности Intel Thread Checker
1.3. Принцип сбора информации
1.4. Подготовка программы для анализа
1.5. Создание проекта в Intel Thread Checker
1.6. Сбор и анализ данных
1.7. Пример использования Intel Thread Checker
1.7.1. Описание примера
1.7.2. Изучение примера
1.7.3. Подготовка программы для анализа
1.7.4. Создание проекта в Intel Thread Checker
1.7.5. Анализ собранной информации
1.7.6. Причина гонки данных и ее устранение
1.8. Литература
2. Лабораторная работа. Отладка параллельной программы с использованием Intel Thread Checker
2.1. Введение
2.2. Методические рекомендации
2.2.1. Цели и задачи работы
2.2.2. Структура работы
2.2.3. Системные требования
2.2.4. Рекомендации по проведению занятий
2.3. Задача о скалярном произведении векторов
2.3.1. Постановка задачи
2.3.2. Последовательная реализация
2.3.3. Параллельная реализация 1
2.3.4. Анализ параллельной реализации 1
2.3.5. Параллельная реализация 2
2.3.6. Анализ параллельной реализации 2
2.4. Задача Дирихле
2.4.1. Постановка задачи
2.4.2. Метод решения
2.4.3. Последовательная реализация
2.4.4. Параллельная реализация 1
2.4.5. Анализ параллельной реализации 1
2.4.6. Параллельная реализация 2
2.4.7. Анализ параллельной реализации 2
2.5. Задача об обедающих философах
2.5.1. Постановка задачи
2.5.2. Параллельная реализация 1
2.5.3. Анализ параллельной реализации 1
2.5.4. Параллельная реализация 2
2.5.5. Анализ параллельной реализации 2
2.6. Задача о роботе
2.6.1. Постановка задачи
2.6.2. Модель
2.6.3. Метод решения
2.6.4. Последовательная реализация
2.6.4.1. Проектирование структур данных
2.6.4.2. Проектирование модульной структуры
2.6.5. Параллельная реализация
2.6.6. Анализ параллельной реализации
2.7. Дополнительные задания
2.8. Литература
ЧАСТЬ И. ОПТИМИЗАЦИЯ ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ
3. Intel Thread Profiler. Краткое описание
3.1. Введение
3.1.1. Семейство инструментов Intel для поддержки разработки многопоточных приложений
3.1.2. Определение и цели профилирования
3.1.3. Назначение Intel Thread Profiler
3.2. Технические характеристики Intel Thread Profiler
3.2.1. Поддерживаемые методы создания многопоточных приложений
3.2.2. Системные требования
3.3. Основные концепции и понятия профилирования
3.3.1. Понятие критического пути
3.3.2. Состояния потоков
3.3.3. Понятие категорий времени
3.4. Проблемы производительности, определяемые при помощи профилирования
3.4.1. Распределение вычислительной нагрузки
3.4.2. Синхронизация и производительность
3.4.2.1. Выбор примитивов синхронизации
3.4.2.2. Синхронизация между потоками
3.4.3. Непроизводительные издержки при работе с потоками
3.5. Общий порядок работы с инструментом
3.5.1. Инструментация приложения
3.5.2. Профилирование приложения
3.6. Пример использования Intel Thread Profiler
3.6.1. Изучение профилируемого приложения
3.6.2. Подготовка приложения для профилирования
3.6.3. Профилирование приложения
3.6.3.1. Создание проекта Intel Thread Profiler
3.6.3.2. Профилирование
3.6.4. Анализ производительности приложения
3.7. Контрольные вопросы
3.8. Литература
4. Лабораторная работа. Профилирование параллельной программы с использованием Intel Thread Profiler. Балансировка нагрузки
4.1. Цели лабораторной работы
4.2. Инструкция для выполнения лабораторной работы
4.2.1. Подход 1: разделение множества чисел на одинаковые части по числу потоков
4.2.2. Подход 2: разделение множества чисел на четные и нечетные
4.2.3. Подход 3: разделение множества чисел на небольшие группы
4.3. Самостоятельная работа. Выбор оптимальной степени гранулярности
4.4. Контрольные вопросы
4.5. Литература
5. Лабораторная работа. Профилирование параллельной программы с использованием пакета Intel Parallel Studio. Балансировка нагрузки
5.1. Методические указания
5.1.1. Цели и задачи работы
5.1.2. Структура работы
5.1.3. Тестовая инфраструктура
5.2. Инструмент Intel Parallel Studio
5.3. Разделение множества чисел на одинаковые части по количеству потоков
5.3.1. Задание 1. Открытие проекта OlEqualPartition
5.3.2. Задание 2. Реализация параллельного алгоритма. Поиск ошибок работы с памятью и ошибок многопоточности .
5.3.3. Задание 3. Анализ эффективности («горячие» точки)
5.3.4. Задание 4. Оценка степени параллелизма
5.4. Разделение множества чисел с чередованием
5.4.1. Задание 1. Открытие проекта 02JEvenOdd
5.4.2. Задание 2. Реализация параллельного алгоритма
5.4.3. Задание 3. Оценка степени параллелизма
5.5. Разделение множества чисел на группы
5.5.1. Задание 1. Открытие проекта 03_Blocks
5.5.2. Задание 2. Реализация параллельного алгоритма
5.5.3. Задание 3. Оценка степени параллелизма
5.6. Контрольные вопросы
5.7. Дополнительные задания
5.8. Литература
Приложение 1. Программный код основной функции
Приложение 2. Программный код потоковой функции, реализующей разделение чисел на одинаковые части по количеству потоков
Приложение 3. Программный код потоковой функции, реализующей разделение чисел между двумя потоками на четные и нечетные
Приложение 4. Программный код потоковой функции, реализующей разделение множества чисел на небольшие группы
6. Лабораторная работа. Профилирование параллельной программы с использованием Intel Thread Profiler. Синхронизация и накладные расходы на поддержку многопоточности
6.1. Цель лабораторной работы
6.2. Инструкция для выполнения лабораторной работы
6.2.1. Изучение профилируемого приложения
6.2.2. Профилирование приложения
6.2.2.1. Обработка всех запросов в одном потоке
6.2.2.2. Обработка каждого нового запроса в отдельном потоке
6.2.2.3. Организация пула потоков
6.2.3. Изменение архитектуры приложения: организация пула потоков
6.2.4. Выбор примитивов синхронизации
6.2.5. Снижение частоты синхронизации
6.3. Контрольные вопросы
6.4. Задания для самостоятельной работы
6.5. Литература
1АСТЬ III. СОЗДАНИЕ ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ
7. Библиотека Intel Threading Building Blocks. Краткое описание
7.1. Назначение библиотеки Intel Threading Building Blocks
7.2. Возможности библиотеки Intel Threading Building Blocks
7.3. Описание библиотеки Intel Threading Building Blocks
7.4. Инициализация и завершение библиотеки
7.5. Распараллеливание простых циклов
7.5.1. Циклы с известным числом повторений
7.5.2. Циклы с известным числом повторений с редукцией
7.6. Распараллеливание сложных конструкций
7.6.1. Сортировка
7.6.2. Циклы с условием
7.6.3. Конвейерные вычисления
7.7. Ядро библиотеки
7.7.1. Общая характеристика логических задач
7.7.2. Алгоритм работы
7.7.3. Создание и уничтожение логических задач
7.7.4. Планирование выполнения логических задач
7.7.5. Распараллеливание рекурсии
7.8. Примитивы синхронизации
7.9. Потокобезопасные контейнеры
7.10. Литература
Приложение 1. Заголовочные файлы библиотеки ТВВ
Приложение 2. Сборка и настройка проекта
Приложение 3. Совместное использование с ОрепМР
Приложение 4. Оценка эффективности приложений
Приложение 5. Динамическое выделение памяти
8. Лабораторная работа. Распараллеливание циклов с использованием библиотеки Intel Threading Building Blocks на примере задачи матрично-векторного умножения
8.1. Введение
8.2. Методические рекомендации
8.2.1. Цели и задачи работы
8.2.2. Структура работы
8.2.3. Системные требования
8.2.4. Рекомендации по проведению занятий
8.3. Постановка задачи
8.4. Последовательный алгоритм
8.5. Реализация последовательного алгоритма
Задание 1. Открытие проекта SerialMatrixVector
Задание 2. Ввод размеров объектов
Задание 3. Ввод данных
Задание 4. Завершение процесса вычислений
Задание 5. Реализация умножения матрицы на вектор
Задание 6. Проведение вычислительных экспериментов
Задание 7. Оценка эффективности
8.6. Параллельный алгоритм
8.6.1. Принципы распараллеливания
8.6.2. Определение подзадач
8.6.3. Выделение информационных зависимостей
8.6.4. Масштабирование и распределение подзадач по вычислительным элементам
8.7. Реализация параллельного алгоритма
Задание 1. Открытие проекта ParallelMatrixVectorMult
Задание 2. Настройка проекта для использования ТВВ
Задание 3. Инициализация библиотеки ТВВ
Задание 4. Распараллеливание цикла средствами библиотеки ТВВ
Задание 5. Проведение вычислительных экспериментов
Задание 6. Выбор значения параметра grainsize
Задание 7. Оценка эффективности
8.8. Контрольные вопросы
8.9. Задания для самостоятельной работы
8.10. Литература
Приложение 1. Программный код последовательного умножения матрицы на вектор
Приложение 2. Программный код параллельного матрично-векторного умножения
9. Лабораторная работа. Использование механизма логических задач библиотеки Intel Threading Building Blocks на примере вычисления быстрого преобразования Фурье
9.1. Введение
9.2. Методические рекомендации
9.2.1. Цели и задачи работы
9.2.2. Структура работы
9.2.3. Системные требования
9.2.4. Рекомендации по проведению занятий
9.3. Схема вычисления быстрого преобразования Фурье
9.3.1. Теоретическая справка
9.3.2. Алгоритм Cooley - Tukey
9.4. Разработка последовательного приложения
Задание 1. Открытие проекта SerialNonrecursiveFFT
Задание 2. Ввод и генерация исходных данных
Задание 3. Завершение процесса вычислений
Задание 4. Реализация БПФ
Задание 5. Проверка корректности
Задание 6. Проведение вычислительных экспериментов
Задание 7. Оценка эффективности
9.5. Разработка параллельного приложения
Задание 1. Открытие проекта ParallelNonrecursiveFFT
Задание 2. Настройка проекта для использования ТВВ
Задание 3. Инициализация библиотеки ТВВ
Задание 4. Разработка параллельной версии с использованием алгоритма tbb::parallel_for
Задание 5. Разработка параллельной версии с использованием
логических задач
Задание 6. Проведение вычислительных экспериментов
9.6. Контрольные вопросы
9.7. Задания для самостоятельной работы
9.8. Литература
Приложение 1. Программный код последовательного вычисления БПФ
Приложение 2. Программный код параллельного вычисления БПФ с использованием функции tbb::parallel_for
Приложение 3. Программный код параллельного вычисления БПФ с использованием логических задач
10. Лабораторная работа. Использование библиотеки Intel Math Kernel Library и пакета Intel Parallel Studio для параллельной реализации метода Монте-Карло
10.1. Введение
10.2. Методические указания
10.2.1. Цели и задачи работы
10.2.2. Структура работы
10.2.3. Тестовая инфраструктура
10.2.4. Рекомендации по проведению занятий
10.3. Оценивание опционов европейского типа
10.3.1. Модель финансового рынка
10.3.2. Понятие опциона и справедливой цены
10.3.3. Метод вычисления справедливой цены опциона
10.4. Интегрирование по методу Монте-Карло
10.5. Программная реализация
10.5.1. Последовательная версия. Расчет по аналитической формуле
10.5.2. Последовательная версия. Использование генератора ПСЧ
10.5.3. Последовательная версия. Использование генератора КСЧ
10.5.4. «Наивная» параллельная версия 1
10.5.5. «Наивная» параллельная версия 2
10.5.6. Корректная параллельная версия
10.6. Дополнительные задания
10.7. Литература