УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС
Министерство общего и профессионального образования РФ
Кемеровский государственный университет
Кафедра новых информационных технологий


Рабочая программа по спецкурсу
"Высокопроизводительные параллельные вычисления"
Факультет - Математический
для специальности 01.02 – (ДО)

Cоставители: доцент, к.ф.-м.н. Стуколов С.В.,Кемерово 2003 г.

Факультет  Математический
Курс  4
Семестр 7
Лекции  36 часов
Пр. занятия  -
Лабораторные занятия 36 часов
Консультации 2 часа
Семестровые 10 часов
Экзамен 4 часа
Зачёт 3 часа
Всего часов  91 час


Пояснительная записка

Цели и задачи курса – ознакомить студентов с основными направлениями в развитии суперкомпьютерных вычислительных технологий, дать обзор средств параллельного программирования, детально рассмотреть идеи параллельного программирования с помощью интерфейса передачи сообщений.
Актуальность и причины ведения учебной дисциплины обусловлены развитием высокопроизводительных вычислений в России и важностью данного направления в решении актуальных научных задач для Кузбасса.
Студенты четвертого курса имеют навыки последовательного программирования, обладают знаниями матричной алгебры, прослушали спецкурс “последовательное программирование на Фортране”.
Рабочая программа соответствует Государственному образовательному стандарту высшего профессионального образования. На лекционных занятиях дается обзор многопроцессорных вычислительных систем и их классификации, обзор средств параллельного программирования, основы распараллеливания алгоритмов. На практических занятиях, которые будут проходить в компьютерном классе кафедры Юнеско по НИТ, студенты реализуют набор простейших параллельных алгоритмов и проводят исследование их параллельных свойств.


Тематический план

Лекционные занятия
2. Векторные и параллельные компьютеры
1. Архитектуры многопроцессорных систем 2 часа
2 часа
3. Классификации современных вычислительных систем 4 часа
4. Оценки производительности вычислительных систем 2 часа
5. Обзор средств параллельного программирования 4 часа
6. Пример организации кластерной системы 2 часа
7. Основные понятия параллелизма: степень параллелизма алгоритма, ускорение параллельного алгоритма, эффективность параллельного алгоритма 2 часа
8. Простейшие алгоритмы и их степень параллелизма 4 часа
9. Крупно и мелкозернистые алгоритмы. Равномерная загрузка процессоров 2 часа
10. Алгоритм сдваивания. Параллельный алгоритм скалярного умножения векторов и его ускорение по сравнению с последовательным алгоритмом 2 часа
11. Параллельный алгоритм умножения матрицы на вектор и его ускорение по сравнению с последовательным алгоритмом 2 часа
12. Параллельный алгоритм умножения матрицы на матрицу и его ускорение по сравнению с последовательным алгоритмом 2 часа
13. Параллельный алгоритм решения СЛАУ прямым методом Гаусса и его ускорение по сравнению с последовательным алгоритмом 4 часа
14. Параллельный алгоритм решения СЛАУ итерационными методами Якоби, Гаусса - Зейделя и их ускорение по сравнению с последовательным алгоритмом 2 часа
Итого 36 часов

Семинарские занятия
1. Установка и настройка операционной системы Linux (два варианта загрузки ОС: Linux, Windows98), установка и настройка MPI. 4 часа
2. Установка пакета Scalapack для матричных параллельных вычислений 2 часа
3. Тестирование основных функций MPI. 2 часа
4. Тестирование производительности кластера. 2 часа
5. Создание простейшей параллельной программы. Обрамляющие функции, инициализация MPI, вывод имен узлов кластера. 2 часа
6. Распределение данных по процессорам с помощью функций типа “точка-точка” 2 часа
7. Распределение данных по процессорам с помощью коллективных функций 2 часа
8. Реализация параллельного алгоритма вычисления суммы ряда в случае, когда все данные расположены на головном процессоре. Вычисление ускорения и эффективности параллельного алгоритма по сравнению с последовательным. 2 часа
9. Реализация параллельного алгоритма вычисления скалярного произведения векторов в случае, когда оба вектора расположены на головном процессоре. Вычисление ускорения и эффективности параллельного алгоритма по сравнению с последовательным. 2 часа
10. Реализация параллельного алгоритма умножения матрицы на вектор в случае, когда все данные расположены на головном процессоре. Вычисление ускорения и эффективности параллельного алгоритма по сравнению с последовательным. 2 часа
11. Реализация параллельного алгоритма умножения матрицы на вектор в случае, когда матрица распределена построчно на все процессора, а вектор хранится на всех. Вычисление ускорения и эффективности параллельного алгоритма по сравнению с последовательным. 2 часа
12. Реализация параллельного алгоритма умножения матрицы на вектор в случае, когда матрица распределена по столбцам на все процессора, а вектор хранится на всех. Вычисление ускорения и эффективности параллельного алгоритма по сравнению с последовательным. 2 часа
13. Реализация параллельного алгоритма умножения матрицы на матрицу в случае, когда 1 матрица распределена построчно на все процессора, а другая по столбцам. Вычисление ускорения и эффективности параллельного алгоритма по сравнению с последовательным. 2 часа
14. Реализация параллельного алгоритма умножения матрицы на матрицу в случае, когда 1 матрица распределена по столбцам на все процессора, а другая построчно. Вычисление ускорения и эффективности параллельного алгоритма по сравнению с последовательным. 2 часа
15. Реализация параллельного алгоритма решения СЛАУ прямым методом Гаусса и вычисления его ускорение по сравнению с последовательным алгоритмом. 4 часа
16. Реализация параллельного алгоритма решения СЛАУ итерационными методами Якоби, Гаусса - Зейделя и вычисление их ускорения по сравнению с последовательным алгоритмом. 2 часа
Итого 36 часов

Семестровое задание

Создание параллельной программы заданного алгоритма из области матричной алгебры, проведение исследования параллельных свойств алгоритма.


Учебно-методические материалы по дисциплине

Основная литература
1. Афанасьев К.Е. Многопроцессорные вычислительные системы и параллельное программирование: Учебное пособие/ Афанасьев К.Е., Стуколов С.В., Демидов А.В., Малышенко В.В.; Кемеровский госуниверситет. - Кемерово: Кузбассвузиздат, 2003. - 182 с.
2. Корнеев В.В. Параллельные вычислительные системы. М:”Нолидж”, 1999. - 320 с.
3. Голуб Дж., Ван Лоун Ч. Матричные вычисления: Пер. с англ. – М.: Мир, 1999. - 548 с.
4. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем: Пер. с англ. – М.: Мир, 1991. – 367с.
5. Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем. – СПб.: БХВ-Петербург, 2002. - 400с.
6. Материалы информационно-аналитического центра НИВЦ МГУ – www.parallel.ru 7. Tutorial on MPI: The Message-Passing Interface William Gropp Mathematics and Computer Science Division Argonne National Laboratory Argonne, IL 60439 www-unix.mcs.anl.gov/mpi/tutorial

Контрольные вопросы и контрольные срезы

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


Вопросы к экзамену

  1. Векторные компьютеры.
  2. Параллельные компьютеры.
  3. Классификация многопроцессорных вычислительных систем по организации памяти.
  4. Классификация Флинна.
  5. Организация связи между элементами вычислительных систем
  6. Оценки производительности вычислительных систем.
  7. Средства параллельного программирования.
  8. Пример создания вычислительного кластера.
  9. Основные характеристик производительности кластера.
  10. Степень параллелизма алгоритма.
  11. Ускорение параллельного алгоритма.
  12. Эффективность параллельного алгоритма.
  13. Простейшие алгоритмы и их степень параллелизма.
  14. Крупно и мелкозернистые алгоритмы.
  15. Алгоритм сдваивания.
  16. Параллельный алгоритм скалярного умножения векторов и его ускорение по сравнению с последовательным алгоритмом.
  17. Параллельный алгоритм умножения матрицы на вектор и его ускорение по сравнению с последовательным алгоритмом.
  18. Параллельный алгоритм умножения матрицы на матрицу и его ускорение по сравнению с последовательным алгоритмом.
  19. Параллельный алгоритм решения СЛАУ прямым методом Гаусса и его ускорение по сравнению с последовательным алгоритмом.
  20. Параллельный алгоритм решения СЛАУ итерационными методами Якоби, Гаусса - Зейделя и их ускорение по сравнению с последовательным алгоритмом.
  21. MPI( Message Passing Interface ) - интерфейс передачи сообщений, сравнение с другим ПО.
  22. Основные возможности MPI.
  23. Обрамляющие функции MPI.
  24. Коммуникационные функции типа "точка-точка"
  25. Коллективные функции.
  26. Блокирующие и неблокирующие функции.