Курс «Параллельные вычисления»

2016 год

Лекторы:

Лекции

Темы Слайды
1 Введение Вводная
2 Типы параллелизма. Классификация параллельных систем. Современные параллельные архитектуры. Архитектуры современных процессоров. Параллелизм уровня задач. Архитектуры
3 Процессы и потоки. Синхронизация процессов. Ошибки синхронизации. Взаимоисключение. Алгоритмы взаимоисключения Деккера, Питерсона, Лэмпорта Синхронизация
4 Примитивы синхронизации. Семафоры, мьютексы, мониторы, условные переменные, критические секции, барьеры Примитивы синхронизации
5 Языки параллельного программирования Языки параллельного программирования
6 Проектирование многопоточных программ на основе PThreads Многопоточные программы PThreads
7 Проектирование многопоточных программ на основе OpenMP Многопоточные программы OpenMP
8 Проектирование многопроцессных программ Многопроцессные программы MPI
9 Parallel programming in Java Java
10 Concurrency in C++11 CPP11
11 Actor Model. Примеры систем. Futures and Promises. Reactive Streams. Actor Model

Курсовой проект

В рамках курсового проекта студент выбирает один из алгоритмов, для которого выполняется:

  1. разработка алгоритма
  2. создание последовательной программы, реализующей алгоритм
  3. разработка тестового набора, оценка тестового покрытия
  4. выделение частей для параллельной реализации, определение общих данных, анализ потенциального выигрыша
  5. выбор способов синхронизации и защиты общих данных
  6. разработка параллельной программы
  7. отладка на имеющихся тестах, анализ и доработка тестового набора с учетом параллелизма
  8. измерение производительности, сравнение с производительностью последовательной программы
  9. анализ полученных результатов, доработка параллельной программы
  10. написание отчета и презентации
  11. защита проекта

Программная реализация создается:

  1. на языке Java, многопоточное приложение с использованием java.util.concurent
  2. на C++ 2011, многопоточное приложение c использованием встроенных механизмов распараллеливания

Лабораторные работы

Список лабораторных работ

  1. многопоточные программы на C/C++ с использованием Pthreads
  2. многопроцессное приложение на C/C++ с использованием объектов синхронизации POSIX
  3. многопроцессные приложения на C/C++ средствами MPI или многопоточные программы с использованием OpenMP

Лабораторные работы выполняются в ОС Linux. Для работы с OpenMP необходимо поставить пакет libgomp. Для работы с MPI необходимо поставить пакет openmpi.

Работа №1. Создание многопоточных программ на языке C с использованием Pthreads

Целью данной работы является получение студентами навыков создания многопоточных программ с использованием интерфейсов POSIX Threads.

Ключ компилятора -pthread.

Программа работы
  1. Для алгоритма из полученного задания написать последовательную программу на языке C или С++, реализующую этот алгоритм.
  2. Для созданной последовательной программы необходимо написать 3-5 тестов, которые покрывают основные варианты функционирования программы. Для создания тестов можно воспользоваться механизмом Unit-тестов среды NetBeans, или описать входные тестовые данные в файлах. При использовании NetBeans необходимо в свойствах проекта установить ключ компилятора -pthread.
  3. Проанализировать полученный алгоритм, выделить части, которые могут быть распараллелены, разработать структуру параллельной программы. Определить количество используемых потоков, а также правила и используемые объекты синхронизации.
  4. Согласовать разработанную структуру и детали реализации параллельной программы с преподавателем.
  5. Написать код параллельной программы и проверить ее корректность на созданном ранее наборе тестов. При необходимости найти и исправить ошибки.
  6. Провести эксперименты для оценки времени выполнения последовательной и параллельной программ. Проанализировать полученные результаты.
  7. Сделать общие выводы по результатам проделанной работы: Различия между способами проектирования последовательной и параллельной реализаций алгоритма, Возможные способы выделения параллельно выполняющихся частей, Возможные правила синхронизации потоков, Сравнение времени выполнения последовательной и параллельной программ, Принципиальные ограничения повышения эффективности параллельной реализации по сравнению с последовательной.
Варианты заданий
  1. Построить нерекурсивный фильтр для последовательности чисел с настраиваемой длиной импульсной реакции.
  2. Построить рекурсивный фильтр для последовательности чисел с фиксированной длиной импульсной реакции.
  3. Выполнить сортировку последовательности чисел.
  4. Вычислить пересечение трех множеств.
  5. Поиск кратчайшего пути в ориентированном графе (алгоритм БФ).
  6. Вершины дерева размечены числовыми значениями. Для каждой вершины рассчитать сумму чисел всех вершин, для которых данная вершина является корнем.
  7. Умножение двух матриц.
  8. Расчет определителя матрицы.
  9. Определение площади набора кругов, заданных массивом с координатами центров и радиусами, методом Монте-Карло.
  10. Определить частоту встречи слов в тексте на русском языке.
  11. Определить вероятность появления 3-грамм в тексте на русском языке.

Работа №2. Создание многопоточных программ на языке C с использованием OpenMP

Ключ компилятора -fopenmp.

Работа №3. Создание многопроцессного приложения средствами MPI

Ключ компилятора -lmpi.

Работа №4. Создание многопоточных программ на языке Java (java.util.concurent)

Литература

  1. Х.М. Дейтел,П.Дж. Дейтел, Д.Р. Чофнес. Операционные системы: Основы и принципы. Третье издание. Пер. с англ. - М.ООО"Бинм-Пресс", 2009 г. - 1024 с.
  2. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления — СПб: БХВ-Петербург, 2002. — 608 с.
  3. Немнюгин С., Стесик О. - Параллельное программирование для многопроцессорных вычислительных систем. - СПб. БХВ-Петербург,2002. – 400с.
  4. Робачевский А., Немнюгин С., Стесик О. - Операционная система UNIX, 2 изд., СПб: БХВ 2010.- 656c.
  5. Боресков А.В., Харламов А.А. Основы работы с технологией CUDA. М:ДМК-Пресс. 2010, -232с.
  6. B. Nichols, D. Buttlar, J.P. Farrell: Pthreads Programming - A POSIX Standard for Better Multiprocessing, O'Reilly, 1996.-288p.
  7. B. Eckel. Thinking in Java (4th Edition). Prentice Hall, 2006.-1150p.
  8. B. Goetiz, T. Peierls. Java concurrency in practice. Addison-Wesley Professional, 2006, - 384p.
  9. IEEE standard SystemC language reference manual, IEEE Std 1666, 2005 – http://standards.ieee.org/getieee/1666/download/1666-2005.pdf
  10. Официальный сайт OpenMP – http://openmp.org/wp/
  11. Message Passing Interface Forum – http://www.mpi-forum.org/

Архив за предыдущие годы