Реферат: Методические указания по самостоятельной работе для направления 010400 Прикладная математика и информатика Магистерская программа Математическое и программное обеспечение вычислительных комплексов и компьютерных сетей

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего

профессионального образования


ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ

И РАДИОЭЛЕКТРОНИКИ (ТУСУР)


Кафедра Автоматизированных систем управления


УТВЕРЖДАЮ


Зав. Кафедрой АСУ


________________А.М. Кориков


«______» _____________2011 г


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


МЕТОДИЧЕСКИЕ УКАЗАНИЯ


по самостоятельной работе

для направления 010400 – Прикладная математика и информатика

Магистерская программа – Математическое и программное обеспечение

вычислительных комплексов и компьютерных сетей


Разработчик


Доцент кафедры АСУ


Н.П. Фефелов


2011


Фефелов Н.П.


Методы и алгоритмы параллельного программирования: Методические указания по самостоятельной работе студентов для направления 010400 – Прикладная математика и информатика. Магистерская программа – Математическое и программное обеспечение вычислительных комплексов и компьютерных сетей. – Томск, ТУСУР, 2011. – 8 с.


Рассмотрены и утверждены на заседании кафедры АСУ


Протокол 1 от «30» августа 2011 г.


СОДЕРЖАНИЕ


^ 1 ОБЩИЕ РЕКОМЕНДАЦИИ 4

2. ТРЕБОВАНИЯ К РЕЗУЛЬТАТАМ ОСВОЕНИЯ ДИСЦИПЛИНЫ 4

Соответствие компетенций, формируемых при самостоятельном изучении дисциплины, и видов занятий 5

^ 3 СОДЕРЖАНИЕ ДИСЦИПЛИНЫ 5

3.1 Теоретический материал 5

4 МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО САМОСТОЯТЕЛЬНОМУ ИЗУЧЕНИЮ МАТЕРИАЛА 7

5 УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ 8

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

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

5.3 Учебно-методические руководства для лабораторных работ 8

5.4 Лицензионное программное обеспечение 9



^ 1 ОБЩИЕ РЕКОМЕНДАЦИИ

Дисциплина «Методы и алгоритмы параллельного программирования» (МАПП) относится к числу дисциплин профессионального цикла (базовой части). Успешное овладение дисциплиной предполагает предварительные знания вычислительных методов, архитектуры вычислительных систем и операционных систем.

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

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

Использование многопроцессорных вычислительных систем предполагает практическое освоение следующих разделов параллельного программирования:

цели и задачи параллельной обработки данных,

моделирование и анализ параллельных вычислений,

принципы разработки параллельных алгоритмов и программ,

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

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

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

Изложение дисциплины опирается на основные дисциплины:

– Архитектура вычислительных систем,

– Вычислительные системы и сети,

– Программное обеспечение сетей ЭВМ.

^ 2. ТРЕБОВАНИЯ К РЕЗУЛЬТАТАМ ОСВОЕНИЯ ДИСЦИПЛИНЫ
Процесс самостоятельного изучения дисциплины «Методы и алгоритмы параллельного программирования» направлен на формирование следующих компетенций:

общекультурные компетенции (ОК):

способность самостоятельно приобретать с помощью информационных технологий и использовать в практической деятельности новые знания и умения, расширять и углублять свое научное мировоззрение (ОК-4);

способность порождать новые идеи и демонстрировать навыки самостоятельной научно-исследовательской работы и работы в научном коллективе (ОК-5);

профессиональные компетенции (ПК):

способность разрабатывать концептуальные и теоретические модели решаемых научных проблем и задач (ПК-2);

способность углубленного анализа проблем, постановки и обоснования задач научной и проектно-технологической деятельности (ПК-3).

^ В результате изучения дисциплины студент должен:

Знать:

Методы параллельных вычислений для задач вычислительной математики (матричные вычисления, решение систем линейных уравнений, сортировка, обработка графов, уравнения в частных производных, многоэкстремальная оптимизация).

Основные подходы к разработке параллельных программ.

Уметь:

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

Оценивать эффективности параллельных вычислений.

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

Применять общие схемы разработки параллельных программ для реализаций собственных алгоритмов.

Оценивать основные параметры получаемых параллельных программ, таких как ускорение, эффективность и масштабируемость.




Владеть:

основами разработки параллельных программ для МВС с применением технологий MPI, OpenMP, CUDA.



^ Соответствие компетенций, формируемых при самостоятельном изучении дисциплины, и видов занятий
Перечень компетенций

СРС

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

(примеры)

ОК-4

+

Домашнее задание

ОК-5

+

Домашнее задание, тест

ПК-2

+

Домашнее задание

ПК-3

+

Тест


Ниже перечислены тематики самостоятельной работы и виды контроль выполнения их.

№ п/п

Тематика самостоятельной работы

(детализация)

ОК, ПК

Контроль выполнения работы (Опрос, тест, дом.задание, и т.д)

1.

Проработка лекционного материала

ОК-4


Опрос на занятиях (устно)

2.

Подготовка к лабораторным занятиям

ПК-2



Отчет,

защита лаб. работы

3.

Самостоятельное изучение тем теоретической части

Темы для самостоятельного изучения

Матричное умножение. Алгоритмы Фокса и Кэннона

Параллельные алгоритмы итерационного решения СЛАУ

Параллельное интегрирование. Метод Монте-Карло.

Параллельные методы сортировки.

Параллельная реализация в программах выпускной работы.

ОК-4, ОК-5,

ПК-2, ПК-3

Домашнее задание. Контрольная работа. Тест.


4.

Подготовка и сдача экзамена

ОК-4, ОК-5,

ПК-2, ПК-3

Оценка за экзамен



^ 3 СОДЕРЖАНИЕ ДИСЦИПЛИНЫ 3.1 Теоретический материал

Тема 1. Состояние и проблемы параллельных вычислений

Современное состояние суперкомпьютерной вычислительной техники. Списки ТОР500 и ТОР50. Российские достижения. Перспективы развития суперкомпьютерной техники и параллельных вычислений. Использование мировых сетевых ресурсов для параллельных вычислений.

Литература [1].


Тема 2. Моделирование и анализ параллельных алгоритмов


Концепция неограниченного параллелизма. Графовые модели параллельных алгоритмов в виде «операнды-операции». Ярусно-параллельная форма графа алгоритма, высота, ширина алгоритма. Описание параллельного выполнения алгоритма, расписание. Асимптотические оценки времени выполнения. Каскадные вычисления, их реализация на векторных процессорах. Оценки эффективности параллельных алгоритмов: ускорение и эффективность. Закон Амдала. Влияние времени передачи данных на эффективность алгоритма.

Литература [1,4].


Тема 3. Этапы разработки параллельных алгоритмов


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

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

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

Литература [1,4].


Тема 4. Интерфейс передачи сообщений - MPI


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

Коллективные функции обмена данных: широковещательная рассылка, функции сбора и рассыпания данных. Функции редукции данных.

Создание групп процессов, области связи, коммуникаторы. Обмен данными внутри группы, межгрупповой обмен.

Литература [1,8].


Тема 5. Технология программирования OpenMP.


Последовательные и параллельные нити программы. Директивы OpenMP, функции времени выполнения, переменные окружения. Классы переменных. Организация параллельных секций. Параллельные циклы. Директивы синхронизации.

Применение функций и переменных окружения для выполнения параллельных программ.

Литература [6,7,].


Тема 6. Технология параллельного программирования CUDA


Применение графических процессоров в па-раллельном программировании. Модель потоковых вычислений. Расширения языка С. Работа с памятью. Примера программ матричных вычислений.

Литература [8,9]


Тема 7. Параллельные численные алгоритмы и программы для решения типовых задач вычислительной математики.


Матрично-векторное умножение. Линейное и блочное разбиение матриц. Алгоритмы Фокса и Кэннона. Решение систем линейных уравнений, метод Гаусса, итерационные методы. Параллельная сортировка: пузырьковая, Шелла, быстрая сортировка. Задачи обработки графов.

Литература [1,3,12].


^ 3.2 Лабораторные занятия Литература


1 Основные функции передачи данных MPI в алгоритмах численного интегрирования [1,3]

2 Передача данных производными типами данных MPI [1,8]

3 Директивы OpenMP [6,7]

4 Взаимодействующие параллельные процессы в среде OpenMP [6,7]

5 Параллельные программы матричных вычислений [1,3]

6 Параллельные алгоритмы решения систем линейных уравнений [1,3]

7 Параллельные алгоритмы решения систем линейных уравнений [1,3]


^ 3.3 Темы для самостоятельного изучения Литература


1 Алгоритмы Фокса и Кэннона матричного умножения [1,3]

2 Параллельное интегрирование. Метод Монте-Карло [3]

3 Параллельные методы сортировки массивов [1,8]

4 Параллельные алгоритмы в программах магистерской диссертации

^ 4 МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО САМОСТОЯТЕЛЬНОМУ ИЗУЧЕНИЮ МАТЕРИАЛА

Указанные темы изучаются студентами самостоятельно по указанной литературе и Интернет-источникам. Контроль осуществляется на лабораторных занятиях.

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

^ 5 УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ 5.1 Основная литература
1 Гергель В.П. Высокопроизводительные вычисления для многопроцессорных многоядерных систем: Учебник – М.: Изд-во МГУ, 2010. – 544 с (26 экз)

2 Линев А.В., Боголепов Д.К., Бастраков С.И. Технологии параллельного программирования для процессоров новых архитектур: Учебник – Учебник – М.: Изд-во МГУ, 2010. – 157 с. (26 экз)

3 Старченко А.В., Данилкин Е.А., и др. Практикум по методам параллельных вычислений: Учебник. – М.: Изд-во МГУ, 2010. – 200 с. (26 экз)

4 Воеводин В.В. Вычислительная математика и структура алгоритмов: Учебник. – М.: Изд-во МГУ, 2010. – 168 с. (26 экз)

^ 5.2 Дополнительная литература
Гергель В.П. Теория и практика параллельных вычислений. – [Интернет-ресурс] URL: http://intuit.ru/department/calculate/paralltp/.

Гергель В.П. Введение в методы параллельного программирования – [Электронный ресурс]: [сайт].URL:http://www.intuit.ru/department/calculate/inparallprog/.

Антонов А.С. Параллельное программирование с использованием технологииOpenMP: Учебн. пособие. – М.: Изд-во МГУ, 2007.[Электронный ресурс]:[сайт].URL: http://parallel.ru/info/parallel/openmp.

Антонов А.С. Параллельное программирование с использованием технологии MPI: Учебн. Пособие. – М.: Изд-во МГУ, 2003 [Электронный ресурс]: [сайт]. URL:http://parallel.ru/info/parallel/antonov

Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. – СПб.:БХВ-Петербург, 2002 (20 экз)

Хокни Р., Джессхоуп К. Параллельные ЭВМ. Архитектура, программирование, алгоритмы. – М.: Радио и связь, 1986.

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

Боресков А.В., Харламов А.А. Основы работы с технологией CUDA. – М.: ДМК Пресс, 2011

Сандерс Дж., Кэндрот Э. Технология CUDA в примерах: введение в программирование графических процессоров. – М.: ДМК Пресс, 2011


Большинство учебных материалов по параллельным вычислениям размещены в интернете. Рекомендуется использовать сайты:

1 http://parallel/ru – НИИВЦ МГУ

2 http://hpc-education.ru – Интернет-центр системы образовательных ресурсов в области СКТТ

3 http://intuit.ru – Интернет университет информационных технологий

4 http://hpcc.unn.ru – Центр суперкомпьютерных технологий Нижегородского государственного университета
^ 5.3 Учебно-методические руководства для лабораторных работ
Учебные пособия в электронном виде. Файлы этих и других документов передаются студентам.

Шпаковский Г.И., Серикова Н.В. Программирование для многопроцессорных систем в стандарте MPI. – Минск:БГУ, 2002.

Букатов А.А., Дацюк В.Н., Жегуло А.И. Многопроцессорные системы и параллельное программирование. – Ростов-на-Дону: РГУ, 2000.

Немнюгин С.А. Средства программирования для многопроцессорных вычислительных систем. – СПб: СПбГУ, 2007
5.4 Лицензионное программное обеспечение
Программное обеспечение кластера кафедры АСУ.