Федеральное агентство по образованию

ГОУ ВПО «Кемеровский государственный университет»

Кафедра ЮНЕСКО по новым информационным технологиям

 

«Утверждаю»

Декан математического факультета

 

________________  Н.Н. Данилов

 «        »                               20    г.

 

 

РАБОЧАЯ ПРОГРАММА

 

по курсу "Параллельное программирование"

 

Специальность: 010503 «Математическое обеспечение и администрирование информационных систем», ДС.Ф.03

Факультет:  Математический

 

 

 

Курс:                                                 IV

 

Семестр:                                            7

 

 

 

Лекции:                                             34

Зачет:  7 семестр

практические занятия:                   

 

лабораторные занятия:                    34

 

Самостоятельная работа                 73

 

Всего часов:                                     141

 

Составитель:  доцент, Стуколов С.В.

 

 

 

Кемерово, 2008

 

Рабочая программа дисциплины федерального компонента цикла ДС.Ф.03 «Параллельное программирование» составлена на основании Государственного образовательного стандарта высшего профессионального образования второго поколения по специальности 010503 «Математическое обеспечение и администрирование информационных систем», утвержденном 10 марта 2000 г., № 72 мжд/ СП.

 

 

 

 

Рабочая программа обсуждена на заседании кафедры

Протокол №_____от «_____»_________200__г.

Зав.кафедрой ____________________________ К.Е. Афанасьев

 

 

 

 

 

Одобрено методической комиссией

Протокол №_____от «_____»_________200__г.

Председатель ____________________________


 

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

Рабочая программа полностью соответствует Государственному образовательному стандарту высшего профессионального образования второго поколения по специальности 010503 «Математическое обеспечение и администрирование информационных систем».

 

Актуальность и значимость дисциплины. Дисциплина является одной из основных в цикле дисциплин специализации, в рамках которой изучаются основные направления в развитии суперкомпьютерных вычислительных технологий, технологии средств параллельного программирования, способы распараллеливания алгоритмов матричной алгебры.

 

Цель и задачи изучения дисциплины. Главная цель преподавания курса  - освоение базовых знаний по вопросам организации параллельных вычислительных систем, а также основных технологий организации параллельных вычислений на многопроцессорных вычислительных комплексах с распределенной или общей оперативной памятью.

Объектами изучения в данной дисциплине являются: основные принципы организации параллельной обработки данных; модели, методы и технологии параллельного программирования; средства и методы отладки параллельных приложений; библиотеки, надстройки к компиляторам для создания параллельных приложений.

Основными задачами изучения дисциплины являются:

-       знакомство с основными направлениями в области организации параллельных вычислений на многопроцессорных вычислительных системах;

-       знакомство с технологиями параллельного программирования;

-       приобретение навыков параллельного программирования с использованием интерфейса передачи сообщений;

-       знакомство с технологией параллельного программирования на системах с общей оперативной памятью;

-       приобретение навыков распараллеливания алгоритмов матричной алгебры;

-       подготовка студентов к изучению других дисциплин по информационным технологиям.

 

Место дисциплины в профессиональной подготовке специалистов. Курс занимает особое место в учебном плане среди дисциплин факультета по его значению. Вместе с курсами по программированию, курс “Параллельное программирование” составляет основу образования студента в части современных информационных технологий. Курс рассчитан на студентов-математиков, имеющих подготовку по математике и информатике в объеме программы средней школы. В течение преподавания курса предполагается, что студенты знакомы с основными понятиями алгебры, комбинаторики, логики, информатики, которые читаются на факультете перед изучением данной дисциплины.

 

Требования ГОС ВПО к обязательному минимуму содержания дисциплины.

Индекс

Наименование дисциплин и их основные разделы

Всего

часов

ДС

дисциплины СПЕЦИАЛЬНОСТИ

 

ДС.Ф.03

ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ

методы и средства параллельной обработки информации: параллельные вычислительные методы, параллельные вычислительные системы, параллельное программирование; векторизация последовательных выражений алгоритмов, методология канонического отображения алгоритма в графы зависимостей и потока сигналов, в матричный процессор; средства спецификации параллельных процессов; механизмы взаимодействия асинхронных параллельных процессов; синхронизирующие примитивы; методы и языки параллельного программирования: язык Ада, матричный язык потоков данных, язык Оккам: основные конструкции и приемы программирования; применения языков для решения практических задач; сравнение языков; эффективность применения; мультипрограммные системы; параллельная обработка информации в транспьютерных системах.

 

 

Структура учебной дисциплины. Дисциплина включает следующие разделы: многопроцессорные вычислительные системы; парадигмы, модели и технологии параллельного программирования; параллельное программирование с использованием интерфейса передачи сообщений MPI, распараллеливание алгоритмов матричной алгебры.

 

Особенности изучения дисциплины. Особенностью курса является его «разделение» на два больших блока: изучение теоретического материала на лекционных занятиях и практическое изучение интерфейса передачи сообщений MPI, а также распараллеливание на его основе алгоритмов матричной алгебры на лабораторных занятиях и в рамках самостоятельной работы студента.

 

Форма организации занятий по дисциплине. По дисциплине читаются лекции в течение одного семестра по два часа в неделю. В течение одного семестра проводятся лабораторные занятия в объеме двух часов в неделю в компьютерном классе. Кроме того, студенту предлагается выполнить семестровое задание в рамках самостоятельной работы. Один раз в семестре проводится коллоквиум по дисциплине, состоящий из вопросов по теоретической части и практических заданий.

 

Требования к уровню усвоения содержания материала. В результате изучения курса студенты должны усвоить основные теоретические и практические вопросы, определенные содержанием дисциплины, научиться пользоваться полученными знаниями в смежных предметах, научиться применять технологии параллельного программирования, учебную и методическую литературу для решения поставленных задач.

 

Виды контроля знаний и их отчетности. По разделам основной части курса предусмотрены самостоятельные задания, семестровые задания, для выполнения которых требуются элементы исследовательской работы, коллоквиум, тест. По итогам изучения курса предусмотрен зачет.

 

Критерии оценки знаний студентов. Предусмотрена рейтинговая система оценки всех видов деятельности.  Максимальное число баллов – 100. Каждый вид деятельности оценивается следующим образом:

-       посещение лекций – 1 балл каждое занятие (максимально 17 баллов);

-       выполнение самостоятельных заданий – 2 балла каждое (максимально 50 баллов);

-       семестровые задания – 2 балла (сдано в срок) + 10-ти бальная оценка за выполнение работы;

-       коллоквиум – максимально 20 баллов (написаны 3 теоретических вопроса и решено 2 задачи).

Студент, набравший 50 баллов и более, выполнивший семестровое задание получает допуск на зачет.

Зачет проходит в 2 этапа: тестирование и опрос по дополнительным вопросам (если есть пропуски лекций и лабораторных занятий).

При выставлении оценки на зачете (зачет/незачет) учитываются следующие параметры:

1.     Результат теста (100 баллов максимум, ниже 50 баллов – студент получает оценку «незачет»);

2.     Работа студента в семестре (максимально 100 баллов, ниже 50 баллов студент не получает допуск к зачету).

 

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

Название и содержание разделов, тем, модулей

Объем часов

Формы  контроля

Общий

Аудиторная работа

Самостоятельная работа (в часах)

лекции

практические

1

2

3

4

5

6

7

Очная форма обучения

1.  

Основные направления развития высокопроизводительных компьютеров

12

2

 

10

тестовые задания

2.  

Однопроцессорная оптимизация алгоритмов

6

2

 

4

тестовые задания

3.  

Оценки производительности вычислительных систем

6

2

2

2

тестовые задания

4.  

Классификация многопроцессорных вычислительных систем

4

2

 

2

тестовые задания

5.  

Проблемы создания кластерных систем

8

2

2

4

тестовые задания

6.  

Парадигмы, модели и технологии параллельного программирования

4

2

 

2

тестовые задания

7.  

Параллельное программирование с использованием интерфейса передачи сообщений MPI

47

4

20

23

тестовые задания, самостоятельные задания

8.  

Параллельное программирование на системах с общей памятью (OpenMP)

18

4

4

10

тестовые задания

9.  

Параллельное программирование на системах смешанного типа

6

2

 

4

тестовые задания

10.   

Отладка, трассировка и профилирование параллельных программ

6

2

2

2

тестовые задания

11.   

Основные понятия параллелизма алгоритмов

2

2

 

 

тестовые задания

12.   

Алгоритмы матричной алгебры и их распараллеливание

22

8

4

10

тестовые задания,

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

 

Итого:

141

34

34

73

 

 

3.     Содержание дисциплины

3.1 Содержание теоретического курса

1.     Основные направления развития высокопроизводительных компьютеров

Пути достижения параллелизма: независимость функционирования отдельных функциональных устройств, избыточность элементов вычислительной системы, дублирование устройств. Векторная и конвейерная обработка данных. Многопроцессорная и многомашинная, параллельная обработка данных. Закон Мура, сдерживающие факторы наращивания количества транзисторов на кристалле и частоты процессоров. Привлекательность подхода параллельной обработки данных. Сдерживающие факторы повсеместного внедрения параллельных вычислений. Ведомственные, национальные и другие программы, направленные на развитие параллельных вычислений в России. Необходимость изучения дисциплины параллельного программирования. Перечень критических задач, решение которых без использования параллельных вычислений затруднено или вовсе невозможно. Содержание курса параллельного программирования – характеристика основных составляющих блоков лекционного курса, практических занятий. Список основной и дополнительной литературы.

 

2.     Однопроцессорная оптимизация

Повышение производительности процессора при обработке массивов с использованием циклов. Явные циклы с постоянными границами. Многократное использование КЭШа. Использование предварительной выборки при загрузке данных из оперативной памяти в кэш второго уровня. Изменение инструкций задачи для лучшего кэширования. Архитектурно-зависимая оптимизация; отличия развертывания циклов для векторных и кэш-ориентированных архитектур. Конвейерная обработка данных. Зависимость производительности процессора от способа описания и хранения данных.

 

 

3.     Оценки производительности вычислительных систем

Стандартные методики измерения производительности MIPS, MFLOPS и т.д. Производительность кластера – латентность, пропускная способность. Общепризнанные методики измерения производительности многопроцессорных вычислительных систем. TOP500 – мировой рейтинг суперкомпьютеров (краткая характеристика первых 5-и суперкомпьютеров мира). TOP50 – Российский рейтинг суперкомпьютеров (краткая характеристика первых 5-и суперкомпьютеров России). Перечень с характеристикой Сибирских суперкомпьютерных центров (Томск, Новосибирск, Красноярск, Омск). Состояние вопроса параллельных вычислений в Кемеровском государственном университете

 

4.     Классификация многопроцессорных вычислительных систем

Системы с распределенной, общей памятью, примеры систем. Массивно-параллельные системы (MPP). Симметричные мультипроцессорные системы (SMP). Параллельные векторные системы (PVP). Системы с неоднородным доступом к памяти (Numa), примеры систем. Компьютерные кластеры – специализированные и полнофункциональные. История возникновения компьютерных кластеров – проект Beowulf. Мета-компьютинг – примеры действующих проектов. Классификация Флинна, Шора и т.д. Организация межпроцессорных связей – коммуникационные топологии. Примеры сетевых решений для создания кластерных систем. Современные микропроцессоры, используемые при построении кластерных решений. Компания Т-платформы.

 

5.     Проблемы создания кластерных систем

Будущий кластер определяют существующие задачи. Плюсы и минусы своего кластера и арендуемого. Бюджет на обслуживание и содержание кластера. Кадровое обеспечение. Базовая инфраструктура: помещение, системы охлаждения воздуха, пол, безопасность. Проектирование архитектуры: базовые компоненты кластера, компоновка кластера, выбор процессора, оперативная память, диски, головной узел кластера, сетевая инфраструктура (коммуникационная, транспортная, сервисная). Поставка и монтаж оборудования. Установка и настройка программного обеспечения. Средства разработки и прикладное программное обеспечение. Мониторинг кластера. Обслуживание кластера. Информационно-вычислительный портал Кемеровского государственного университета.

 

6.     Парадигмы, модели и технологии параллельного программирования

Функциональный параллелизм, параллелизм по данным. Парадигма master-slave. Парадигма SPMD. Парадигма конвейеризации. Парадигма “разделяй и властвуй”. Спекулятивный параллелизм. Важность выбора технологии для реализации алгоритма. Модель обмена сообщениями – MPI. Модель общей памяти – OPENMP. Концепция виртуальной, разделяемой памяти – Linda. Российские разработки – Т-система, система DVM. Проблемы создания средства автоматического распараллеливания программ.

 

7.     Параллельное программирование с использованием интерфейса передачи сообщений MPI

Библиотека MPI. Модель SIMD. Инициализация и завершение MPI-приложения. Точечные обмены данными между процессами MPI-программы. Режимы буферизации. Проблема deadlock’ов. Коллективные взаимодействия процессов в MPI. Управление группами и коммуникаторами в MPI.

 

8.     Параллельное программирование на системах с общей памятью (OpenMP)

Введение в OpenMP. Стандарты программирования для систем с разделяемой памятью. Создание многопоточных приложений. Использование многопоточности при программировании для многоядерных платформ. Синхронизация данных между ветвями в параллельной программе. Директивы языка OpenMP.

 

9.     Параллельное программирование на системах смешанного типа

Гибридные модели программирования SMP-систем. Передача данных между узлами кластера функциями MPI, обмен данными внутри узла между ядрами процессора через потоки OpenMP. Правила запуска параллельных приложений, написанных с использованием OpenMP+MPI.

 

10.           Отладка, трассировка и профилирование параллельных программ

Классификация ошибок параллельных программ (сильные, слабые ошибки …). Особенности отладки параллельных приложений. Трассировка. Отладка с помощью последовательных отладчиков. Параллельный Отладчик TotalView. Профилирование. Библиотека MPE. Средства MPI для визуализации трассы параллельного приложения.

 

11.           Основные понятия параллелизма алгоритмов

Степень параллелизма численного алгоритма. Средняя степень параллелизма численного алгоритма. Зернистость алгоритма. Ускорение и эффективность. Закон Амдала. Алгоритм исследования свойств параллельного алгоритма. Определение параллелизма: анализ задачи с целью выделить подзадачи, которые могут выполняться одновременно. Выявление параллелизма: изменение структуры задачи таким образом, чтобы можно было эффективно выполнять подзадачи. Для этого часто требуется найти зависимости между подзадачами и организовать исходный код так, чтобы ими можно было эффективно управлять. Выражение параллелизма: реализация параллельного алгоритма в исходном коде с помощью системы обозначений параллельного программирования.

 

12.           Алгоритмы матричной алгебры и их распараллеливание

Параллельный алгоритм умножения матрицы на вектор и его ускорение по сравнению с последовательным алгоритмом. Параллельный алгоритм умножения матрицы на матрицу и его ускорение по сравнению с последовательным алгоритмом. Параллельный алгоритм решения СЛАУ прямым методом Гаусса и его ускорение по сравнению с последовательным алгоритмом. Параллельный алгоритм решения СЛАУ итерационными методами Якоби, Гаусса - Зейделя и их ускорение по сравнению с последовательным алгоритмом.

 

 

 

 

Основная литература

1.  Афанасьев К.Е., Стуколов С.В. Многопроцессорные вычислительные системы и параллельное программирование: Учебное пособие с грифом СибРУМЦ. Кемеровский госуниверситет. Кемерово: Кузбассвузиздат, 2003. 233с.

2.  Афанасьев К.Е., Домрачеев В.Г., Ретинская И.В., Скуратов А.К., Стуколов С.В. Многопроцессорные системы: построение, развитие, обучение / Учебно-справочное издание под ред. Тихонова А.Н. М.: КУДИЦ-ОБРАЗ, 2005. 224 с.

3.  Букатов А.А., Дацюк В.Н., Жегуло А.И. Программирование многопроцессорных вычислительных систем. Ростов-на-Дону. Издательство ООО «ЦВВР», 2003, 208 с. (http://rsusu1.rnd.runnet.ru/tutor/method/index.html)

4.  Воеводин В.В. Параллельные вычисления / Воеводин В.В., Воеводин Вл.В.  СПб: БХВ-Петербург, 2002. 608с.

5.  Немнюгин С.А., Стесик О.Л. Параллельное программирование для многопроцессорных вычислительных систем. – СПб.: БХВ-Петербург, 2002. - 400с.

6.  Ортега Дж. Введение в параллельные и векторные методы решения линейных систем: Пер. с англ.  М.: Мир, 1991. 367с.

7.  Эндрюс Г.Р. Основы многопоточного, параллельного программирования. Пер. с англ. М.: Издательский дом “Вильямс”, 2003. 512с.

8.  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

 

 

Дополнительная литература

 

9.  Антонов А.С. Параллельное программирование с использованием технологии MPI: Учебное пособие. // http://rsusu1.rnd.runnet.ru/tutor/antonov/

10.            Афанасьев К.Е., Стуколов С.В.  КМГЭ для решения плоских задач гидродинамики и его реализация на параллельных компьютерах: Учебное пособие / Кемерово: КемГУ, 2001. 208 с.

11.            Бахвалов Н.С. Численные методы. М.: Наука, 1975.

12.            Березин И.С. Методы вычислений / Березин И.С., Жидков Н.П. М.: Физматгиз, 1966. Т.1.

13.            Богданов А., Мареев В., Станнова Е., Корхов В. Архитектуры и топологии многопроцессорных вычислительных систем // электронный учебник http://www.informika.ru/text/teach/topolog/index.htm

14.            Валях Е. Последовательно-параллельные вычисления / Пер. с англ. М.: Мир, 1985. 456с.

15.            Голуб Дж., Ван Лоун Ч. Матричные вычисления: Пер. с англ. – М.: Мир, 1999. - 548 с.

16.            Корнеев В.В. Параллельные вычислительные системы. М: ”Нолидж”, 1999. 320 с.

17.            Материалы информационно-аналитического центра НИВЦ МГУ – www.parallel.ru

18.            Старченко А.В. Параллельные вычисления на многопроцессорных вычислительных системах / Старченко А.В., Есаулов А.О. Томск: ТГУ, 2002. 56 с.

19.            Таненбаум Э. Архитектура компьютера // СПб, Изд-во «Питер», 2002 г

20.            Шнитман В. Современные высокопроизводительные компьютеры. 1996. http://www.citforum.ru/hardware/svk/contents.shtml

21.            Форсайт Дж.  Машинные методы математических вычислений / Форсайт Дж., Малькольм М., Моулер К. М.: Мир, 1980.