Белорусский государственный университет
УТВЕРЖДАЮ
Декан факультета прикладной математики
и информатики
________________
(подпись)
____________________
(дата утверждения)
Регистрационный № УД-______/р.
Параллельные и распределенные вычисления
Учебная программа для специальностей:
1-31 03 04 Информатика
Факультет _____ Прикладной математики и информатики______
(название факультета)
Кафедра _______ Вычислительной математики________
(название кафедры)
Курс (курсы) ___4____________________________
Семестр (семестры) ___8__________________________
Лекции ____34______ Экзамен ____8_________
(количество часов) (семестр)
Практические (семинарские)
занятия __________ Зачет _______8_________
(количество часов) (семестр)
Лабораторные
занятия _____34_______ Курсовой проект (работа) ________
(количество часов) (семестр)
Всего аудиторных
часов по дисциплине ___68______
(количество часов)
Всего часов Форма получения
по дисциплине __________ высшего образования ___очная____
(количество часов)
2012 г.
Учебная программа составлена на основе базовой учебной программы дисциплины «Параллельные и распределенные вычисления», утверждена
29 мая 2012 г.
Рассмотрена и рекомендована к утверждению на заседании кафедры вычислительной математики 21 мая 2012 года, протокол № 9.
Одобрена и рекомендована к утверждению на заседании методической комиссии ФПМИ 29 мая 2012 г., протокол № 5.
Пояснительная записка
Курс параллельных и распределенных вычислений знакомит студентов со способами организации параллельных и распределенных вычислительных процессов, с основными подходами к решению важнейших задач отображения алгоритмов, задаваемых последовательными программами, на параллельные вычислительные системы, параллельные компьютеры с распределенной памятью, многоядерные персональные компьютеры, графические процессоры. Рассматриваются, в частности, следующие задачи:
§ получение информационной структуры алгоритма,
§ выбор зерна вычислений,
§ организация параллельных и распределенных вычислительных процессов,
§ распараллеливание алгоритмов для реализации на графических процессорах,
§ построение параллельных алгоритмов, связанных с графами и сетями
§ улучшение локальности вычислений,
§ аффинные преобразования гнезд циклов,
§ автоматизация распараллеливания.
Основная цель курса – ввести студентов в проблематику организации параллельных и распределенных вычислений, ввести в проблематику статического распараллеливания, основанного на знании тонкой информационной структуры программ, изучить основные термины и понятия, математический аппарат и модели параллельных вычислений, дать теоретические и практические основы выявления параллелизма, распараллеливания алгоритмов, преобразования последовательных программ в параллельные.
В результате изучения дисциплины обучаемый должен:
знать:
– проблематику статического распараллеливания;
– основные термины и понятия, математический аппарат и модели параллельных и распределенных вычислений;
– теоретические основы организации параллельных и распределенных вычислительных процессов, распараллеливания алгоритмов, преобразования последовательных программ в параллельные;
уметь:
– обнаруживать параллелизм;
– распределять операции и данные алгоритма между процессорами;
– устанавливать порядок выполнения операций и обмена данными;
– использовать инструментальные средства для организации параллельных и распределенных вычислительных процессов.
Содержание учебного материала
Раздел 1. Введение в параллельные вычисления. Информационная структура алгоритма.
Основная цель и задача параллельных вычислений. Терминология параллельных вычислений.
Функции, задающие индексы массивов данных. Зависимости. Представление зависимостей. Функции зависимостей. Графы зависимостей. Типы зависимостей. Способы устранения ложных зависимостей. Параллельные и последовательные циклы.
Инструментальные средства для получения информационной структуры алгоритма. Визуализация информационной структуры алгоритма, получение информации о зависимостях, типах зависимостей, получение функций зависимостей и графов зависимостей с помощью инструментальных средств.
Параллельные множества операций, параллельная форма алгоритма, параллельные последовательности вычислений. Параллельные вычислительные свойства и параллельная структура алгоритма. Суть и основная цель концепции неограниченного параллелизма. Принцип сдваивания. Процесс рекуррентного сдваивания. Основные классы современных параллельных компьютеров. Классификация Флинна параллельных компьютеров.
Раздел 2. Организация параллельных и распределенных вычислений.
Основные задачи статического распараллеливания: получение информационной структуры алгоритма, обнаружение потенциального параллелизма алгоритма, выявление независимых частей программы, тайлинг, выбор зерна вычислений, организация параллельных вычислительных процессов, согласование распределения операций и данных, улучшение локальности, организация обмена данными.
Разбиение операций алгоритма на тайлы. Техника тайлинга. Допустимость тайлинга.
Задание зерна вычислений. Функции, задающие распределение зерен между процессорами. Условия параллельности последовательностей зернистых вычислений. Разработка и реализация на суперкомпьютере параллельных алгоритмов перемножения матриц, решения систем линейных алгебраических уравнений, решения дифференциальных уравнений в частных производных (распараллеливание, задание зерна вычислений, организация обмена данными).
Характеристика локальности параллельных алгоритмов, операции которых разбиты на тайлы. Оценка локальности альтернативных вариантов параллельных зернистых алгоритмов. Улучшение локальности для последовательных вычислений Пространственная локальность. Временная локальность. Тайлинг для улучшения локальности многомерных циклов. Выбор циклов для формирования тайлов.
Мультипроцессоры графического процессора. Виды памяти. Организация потоков и блоков потоков. Основные положения для распараллеливания алгоритмов при программирования общего назначения на графических процессорах.
Обоснование определения понятий производительности, загруженности, ускорения вычислительной системы. Формулы для нахождения максимальных характеристик. Законы Амдала. Закон Густавсона-Барсиса. Сравнительный анализ законов Амдала и Густавсона-Барсиса. Список Top 500. Список Graph 500.
Параллельные алгоритмы обработки графов: поиск в ширину, нахождение кратчайшего пути, нахождение минимального охватывающего дерева, оптимальное разделение графов. Модель вычислений MapReduce, система Hadoop. Комбинированное использование многопоточных и MapReduce вычислений.
Раздел 3. Параллельная структура алгоритма. Инструментальные средства для распараллеливания алгоритмов.
Распараллеливание, использующее уровни зависимостей. Алгоритм Аллена и Кеннеди распараллеливания гнезд тесно вложенных циклов.
Таймирующие функции. Строгие таймирующие функции. Расщепляющие функции. Скошенный параллелизм. Векторные таймирующие функции.
Получение таймирующих функций для однородных гнезд циклов. Получение параметров таймирующих расщепляющих, строгих таймирующих функций посредством решения вспомогательных систем неравенств и уравнений. Алгоритм получения таймирующих функций.
Преобразования тесно вложенных циклов, задаваемые векторными таймирующими функциями. Условия параллельности внутренних циклов после преобразования. Условия параллельности внешних циклов после преобразования.
Генерация кода: запись алгоритма после аффинного преобразования. Инструментальные средства для получения параллельных алгоритмов (в том числе и для генерации кода). Системы ParProc, LooPo, CLooG, PLUTO. Библиотеки ScaLAPACK, Cloud Numerics.
УЧЕБНО-МЕТОДИЧЕСКАЯ КАРТА
Номер раздела, темы, занятия | Название раздела, темы, занятия; перечень изучаемых вопросов | Количество аудиторных часов | Материальное обеспечение занятия (наглядные, методические пособия и др.) | Литература | Форма контроля знаний | |||
лекции | практические (семинарские) занятия | лабораторные занятия | управляемая самостоятельная работа студента | |||||
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
1. | Введение в параллельные вычисления. Информационная структура алгоритма (16ч.) | 8 | 8 | |||||
1.1. | Основные понятия параллельных вычислений (1 ч.) | 1 | Уч. пос. «Параллельные вычисления» Курс лекций «Вычислительная математика и структура алгоритмов» | [1, 2, 4-6] | ||||
1.1.1. | Цель и задача параллельных вычислений. Терминология параллельных вычислений. | 1 | ||||||
1.2. | Анализ зависимостей (10 ч.) | 4 | 6 | Уч. пос. «Параллельные вычисления». Курс лекций «Методы распараллеливания гнезд циклов» | [1, 3] | |||
1.2.1. | Функции, задающие индексы массивов данных. Зависимости. Представление зависимостей. Функции зависимостей. Графы зависимостей. Типы зависимостей: истинные зависимости, антизависимости, зависимости по выходу, зависимости по входу. | 3 | 4 | текущая | ||||
1.2.2. | Способы устранения ложных зависимостей: переобозначение, увеличение размерности; расщепление операторов. Параллельные и последовательные циклы. | 1 | ||||||
1.2.3. | Получение информационной структуры алгоритма (получение векторов, функций и графов зависимостей) | 2 | инд-ное задание | |||||
1.3. | Инструментальные средства для получения информационной структуры алгоритма (3 ч.) | 1 | 2 | [7- 10] | ||||
1.3.1. | Система Depend grapher, система LooPo, Открытая распараллеливающая система, V-Ray система. | 1 | ||||||
1.3.2. | Визуализация информационной структуры алгоритма, получение информации о зависимостях, типах зависимостей, получение функций зависимостей и графов зависимостей с помощью инструментальных средств. | 2 | индивидуальное задание на комп. | |||||
1.4. | Параллельная форма алгоритма. Концепция неограниченного параллелизма. Основные классы современных вычислительных систем. (2 ч.) | 2 | Уч. пос. «Параллельные вычисления». Курс лекций «Вычислительная математика и структура алгоритмов» | [1, 2, 4] | ||||
1.4.1. | Параллельные множества операций, параллельная форма алгоритма, параллельные последовательности вычислений. Параллельные вычислительные свойства и параллельная структура алгоритма. Суть и основная цель концепции неограниченного параллелизма. Принцип сдваивания. Процесс рекуррентного сдваивания. | 1 | ||||||
1.4.2. | Основные классы современных вычислительных систем. Классификация Флинна параллельных компьютеров. | 1 | ||||||
2. | Организация параллельных и распределенных вычислений. (30 ч.) | 14 | 16 | |||||
2.1. | Основные задачи статического распараллеливания (краткий обзор). Тайлинг (разбиение множества операций алгоритма на макрооперации) (4 ч.) | 2 | 2 | Уч. пос. «Параллельные вычисления». | [4, 11- 13] | |||
2.1.1. | Задачи статического распараллеливания: получение информ. структуры алгоритма, выявление потенциаль-ного параллелизма алгоритма, выбор зерна вычислений, согласование распределения операций и данных, улучшение локальности, организация обмена данными. | 1 | ||||||
2.1.2. | Разбиение множества операций алгоритма на тайлы. Примеры применения тайлинга. Техника тайлинга. Допустимость тайлинга. | 1 | 2 | текущая | ||||
2.2. | Организация параллельных вычислительных процессов. Параллельные последовательности зернистых вычислений. (12 ч.) | 2 | 10 | [4-6, 14, 15] | ||||
2.2.1. | Задание зерна вычислений. Функции, задающие распределение зерен между процессорами. Условия параллельности последовательностей зернистых вычислений. | 2 | ||||||
2.2.2. | Разработка параллельных алгоритмов для выполнения матричных операций, решения систем линейных алгебраических уравнений, параллельных алгоритмов решения дифференциальных уравнений (задание зерна вычислений, организация параллельных вычислитель-ных процессов, организация обмена данными). | 4 | текущая | |||||
Информационная структура алгоритма. Организация параллельных вычислительных процессов. | 2 | контр-я работа | ||||||
2.2.3. | Реализация на суперкомпьютере параллельных алгоритмов. | 4 | индивид. задан. на суперкомп | |||||
2.3. | Локальность параллельных зернистых алгоритмов (1 ч.) Улучшение локальности для последовательных вычислений (1 ч.) | 2 | Курс лекций «Методы распараллеливания гнезд циклов | [3, 4] | ||||
2.3.1. | Характеристика локальности параллельных алгоритмов, операции которых разбиты на тайлы. Оценка локальности альтернативных вариантов параллельных зернистых алгоритмов. | 1 | ||||||
2.3.2. | Пространственная локальность. Временная локальность. Тайлинг для улучшения локальности многомерных циклов. Выбор циклов для формирования тайлов. | 1 | ||||||
2.4. | Распараллеливание алгоритмов для реализации на графических процессорах (GPU) (2 ч.) | 2 | [4,16-18] | |||||
2.4.1. | Мультипроцессоры графического процессора. Виды памяти: регистры, локальная, глобальная, разделяемая, константная, текстурная. Организация потоков и блоков потоков. Основные положения для распараллеливания алгоритмов при программирования общего назначения на GPU. | 2 | ||||||
2.5. | Характеристики параллельных вычислительных процессов и систем. Списки Top 500 и Graph 500 (2 ч.) | 2 | Уч. пос. «Параллельные вычисления» | [1, 4] | ||||
2.5.1. | Определения производительности, загруженности, ускорения вычислительной системы: Формулы максимальных производительности, загруженности, ускорения. Законы Амдала. Сетевой закон Амдала. Закон Густавсона-Барсиса. Сравнительный анализ законов Амдала и Густавсона-Барсиса. Список Top 500. Список Graph 500. | 2 | ||||||
2.6. | Параллельные алгоритмы, связанные с графами и сетями. Модель вычислений MapReduce (8 ч.) | 4 | 4 | [4, 19-23] | ||||
2.6.1. | Параллельные алгоритмы обработки графов: поиск в ширину, нахождение кратчайшего пути, нахождение минимального охватывающего дерева, оптимальное разделение графов. | 4 | 2 | задание на комп. | ||||
2.6.2. | Модель вычислений MapReduce, система Hadoop. Комбинированное использование многопоточных и MapReduce вычислений. | 2 | задание на комп. | |||||
3. | Параллельная структура алгоритма. Инструментальные средства для распараллеливания алгоритмов (22 ч.) | 12 | 10 | |||||
3.1. | Распараллеливание, использующее уровни зависимостей (1 ч.) | 1 | Курс лекций «Методы распараллеливания гнезд циклов» | [3] | ||||
3.1.1. | Алгоритм Аллена и Кеннеди распараллеливания гнезд тесно вложенных циклов. | 1 | ||||||
3.2. | Таймирующие функции (1 ч.) | 1 | Уч. пос. «Паралл. вычисления». Курс лекций «Вычислительная математика и структура алг-мов». Курс лекций «Методы распаралл. гнезд циклов» | [1-4] | ||||
3.2.1. | Таймирующие функции. Строгие таймирующие функции. Расщепляющие функции. Скошенный параллелизм. Векторные таймирующие функции. Многомерное таймирование. | 1 | ||||||
3.3. | Получение таймирующих функций для однородных гнезд циклов (4 ч.) | 2 | 2 | Курс лекций «Методы распаралл. гнезд циклов» | [3] | |||
3.3.1. | Получение параметров таймирующих, расщепляющих, строгих таймирующих функций посредством решения вспомогательных систем неравенств и уравнения. Алгоритм получения таймирующих функций. | 2 | 2 | текущая | ||||
3.4. | Аффинные преобразования гнезд вложенных циклов (4 ч.) | 2 | 2 | Курс лекций «Методы распаралл-ния гнезд циклов | [3] | |||
3.4.1. | Преобразования вложенных циклов, задаваемые векторными таймирующими функциями. Условия параллельности внутренних циклов после преобразования. Условия параллельности внешних циклов после преобразования. | 2 | 2 | текущая | ||||
3.5. | Генерация кода. Инструментальные средства для получения параллельных алгоритмов (в том числе и для генерации кода). Специализирован-ные параллельные библиотеки (12 ч.) | 6 | 6 | Курс лекций «Методы распараллеливания гнезд циклов | [3, 8, 24-28] | |||
3.5.1. | Генерация кода: запись алгоритма после аффинного преобразования. | 2 | 2 | текущая | ||||
3.5.2. | Примеры получения параллельной структуры алгоритма и генерация кода. | 2 | ||||||
Параллельные алгоритмы, связанные с графами и сетями. Параллельная структура алгоритма. | 2 | контр-я работа | ||||||
3.5.2. | Системы ParProc, LooPo, CLooG, PLUTO. Библиотеки ScaLAPACK, Cloud Numerics. | 2 | 2 | задание на комп. |
Рекомендуемая литература
Основная
1. , Воеводин Вл. В. Параллельные вычисления. – Санкт-Петербург. БХВ-Петербург. 2002. – 600 с.
2. Воеводин математика и структура алгоритмов. – Москва: Изд-во МГУ, 2006. – 112 с. http://parallel. ru/info/parallel/voevodin/
3. Лиходед распараллеливания гнезд циклов: Курс лекций. – Мн.: БГУ. 2008. – 100 с.
4. [Электрон. ресурс – Персональная страница на ] Лекции.
[Электрон. ресурс –\\fpmi-stud\Subfaculty\Каф. Выч. Мат\Параллельные вычисления\Лекции]
Дополнительная
5. , , Серикова по работе на вычислительном кластере. – Минск, БГУ, 2004. – 171 с.
6. Шпаковский параллельных вычислений: кластеры, много-ядерные процесры, грид, квантовые компьютеры. – Минск, БГУ, 2010. – 155 с.
7. [Электрон. ресурс – \\fpmi-stud\Subfaculty\Каф. Выч. Мат\Параллельные вычисления\Инструментарий] Система Depend grapher.
8. LooPo. www. fmi. uni-passau. de/loopo.
9. Открытая распараллеливающая система: www. ops. rsu. ru.
10. V-Ray система: v-ray. parallel. ru
11. , Воеводин Вл. В. Эффективная адаптация последовательных программ для современных векторно-конвейерных и массивно-параллельных супер-ЭВМ. Программирование. 1996. № 4. С. 37–51.
12. Kim D., Rajopadhye S. Parameterized tiling for imperfectly nested loops. // Technical Report CS-09-101, Colorado State University, Department of Computer Science, February 2009.
13. Tavarageri S., Hartono A., Baskaran M., Pouchet L.-N., Ramanujam J., Sadayappan, P. Parametric tiling of affine loop nests // Proc. 15th Workshop on Compilers for Parallel Computers. Vienna, Austria, July 2010.
14. , Толстиков последовательности зернистых вычислений // Доклады НАН Беларуси. 2010. Т. 54, № 4. С. 36–41.
15. "Параллельное программирование с использованием технологии MPI".– М.: Изд-во МГУ, 2004.-71 с. http://parallel. ru/info/parallel/antonov/
16. ведение в технологию CUDA. // Компьютерная графика и мультимедиа. 2008. выпуск № 6 (1). putergraphics. ru/issues/issue16/cuda
17. Baskaran M., Bondhugula U, Krishnamoorthy S., Ramanujam J., Rountev A., Sadayappan, P. Automatic data movement and computation mapping for multi-level parallel architectures with explicitly managed memories // Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. February 2008.
18. Baskaran M., Ramanujam J., Sadayappan, P. Automatic C-to - CUDA code generation for affine programs // Proceedings of the Compiler Construction, 19th International Conference. Part of the Joint European Conferences on Theory and Practice of Software. Paphos, Cyprus, March 20–28, 2010.
19. Гергель и практика параллельных вычислений. – Москва: Интернет-Университет, БИНОМ. Лаборатория знаний, 2007.
20. Agarwal V., Petrini F., Pasetto D., Bader D. Scalable graph exploration on multicore processors // Proceedings of the ACM/IEEE Supercomputing 2010 Conference. New Orleans, LA, November 13–19, 2010.
21. Yoo A., Chow E., Henderson K., McLendon W., Hendrickson B., Catalyurek U. V: A scalable distributed parallel breadth-first search algorithm on BlueGene/L // Proceedings of the ACM/IEEE Supercomputing 2005 Conference. November 2005.
22. Buluc A., Madduri K.: Parallel breadth-first search on distributed memory systems // Proceedings of the ACM/IEEE Supercomputing 2011 Conference. November 2011.
23. Kang S., Bader D. Large scale complex network analysis using the hybrid combination of a MapReduce cluster and a highly multithreaded system // 4th Workshop on Multithreaded Architectures and Applications (MTAAP), Atlanta, GA, April 23, 2010.
24. Электрон. ресурс – \\fpmi-stud\Subfaculty\Каф. Выч. Мат\Параллельные вычисления\Лекции] Система ParProc.
25. Библиотеки BLAS, LAPACK, BLACS, ScaLAPACK: http://lib. org
26. PLUTO: pluto-compiler. .
27. CLooG: The Chunky Loop Generator. http://www. cloog. org.
28. Cloud Numerics:. http://www. microsoft. com/en-us/sqlazurelabs/labs/numerics. aspx
ПРОТОКОЛ СОГЛАСОВАНИЯ УЧЕБНОЙ ПРОГРАММЫ
ПО ИЗУЧАЕМОЙ УЧЕБНОЙ ДИСЦИПЛИНЕ
С ДРУГИМИ ДИСЦИПЛИНАМИ СПЕЦИАЛЬНОСТИ
Название дисциплины, с которой требуется согласование | Название кафедры | Предложения об изменениях в содержании учебной программы по изучаемой учебной дисциплине | Решение, принятое кафедрой, разработавшей учебную программу (с указанием даты и номера протокола) |
ДОПОЛНЕНИЯ И ИЗМЕНЕНИЯ К УЧЕБНОЙ ПРОГРАММЕ
ПО ИЗУЧАЕМОЙ УЧЕБНОЙ ДИСЦИПЛИНЕ
на _____/_____ учебный год
№№ пп | Дополнения и изменения | Основание |
Учебная программа пересмотрена и одобрена на заседании кафедры
(протокол № ____ от ________ 201_ г.)
Заведующий кафедрой
_____________________ _______________ __________________
(степень, звание) (подпись) ()
УТВЕРЖДАЮ
Декан факультета
_____________________ _______________ __________________
(степень, звание) (подпись) ()
