МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ
ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
УТВЕРЖДАЮ Декан факультета _______________ «_____» ___________________ 2015 г. |
РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ
Б3.2.11 Параллельные вычисления и параллельное
программирование
Направление подготовки 01.03.04 — «Прикладная математика»
Профиль подготовки «Математическое моделирование в экономике и технике»
Квалификация (степень) выпускника – бакалавр
Форма обучения очная
Пенза, 2015
1. Цели освоения дисциплины
Целями освоения дисциплины «Параллельные вычисления и параллельное программирование» являются
§ изучение основных вопросов, связанных с построением кластерных систем;
§ изучение основных методов параллелизации вычислительного процесса;
§ изучение основных математических методов, допускающих параллелизацию вычислений.
2. Место дисциплины в структуре ОПОП бакалавриата
Дисциплина «Параллельные вычисления и параллельное программирование» в учебном плане находится в вариативной части профессионального цикла Б.3 и является одной из дисциплин, формирующих профессиональные знания и навыки, характерные для бакалавра по направлению подготовки 01.03.04 «Прикладная математика».
Изучение дисциплины базируется на знаниях студентами курсов “Программирование для ЭВМ”, «Численные методы» (Б3.1, профессиональный цикл, базовая часть), «Архитектура ЭВМ» (Б2.2, математический и естественнонаучный цикл, вариативная часть).
Основные положения дисциплины должны быть использованы в дальнейшем при выполнении дипломных и выпускных аттестационных работ.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины «Параллельные вычисления и параллельное программирование»
Процесс изучения дисциплины направлен на формирование элементов следующих компетенций в соответствии с ФГОС ВПО по данному направлению:
Коды компетенции | Наименование компетенции | Структурные элементы компетенции (в результате освоения дисциплины обучающийся должен знать, уметь, владеть) |
1 | 2 | 3 |
ОПК-1 | готовность к самостоятельной работе | Знать: 1) принципы построения параллельных вычислительных систем. 2) принципы разработки параллельных алгоритмов и программ |
Уметь: работать с параллельными библиотеками MPI и OpenMP; | ||
Владеть: представлением об архитектуре многопроцессорных вычислительных систем. | ||
ОПК-2: | способен использовать современные математические методы и современные прикладные программные средства и осваивать современные технологии программирования. | Знать: параллельные численные алгоритмы для решения типовых задач вычислительной математики |
Уметь: строить параллельные алгоритмы для решения поставленных задач | ||
Владеть: представлением о перспективных направлениях развития средств современной вычислительной техники, связанных с созданием и применением параллельных маши | ||
ПК-11 | готов применять знания и навыки управления информацией | Знать: Моделирование и анализ параллельных вычислений. |
Уметь: реализовывать параллельные процессы в рамках локальной сети.; | ||
Владеть: представлением о возможной степени параллелизации конкретных алгоритмов. |
4. Структура и содержание дисциплины «Параллельные вычисления и параллельное программирование»
4.1. Структура дисциплины «Параллельные вычисления и параллельное программирование»
Общая трудоемкость дисциплины составляет 4 зачетные единицы, 144 часа.
№ п/п | Наименование разделов и тем дисциплины (модуля) | Семестр | Недели семестра | Виды учебной работы, включая самостоятельную работу студентов и трудоемкость (в часах) | Формы текущего контроля успеваемости (по неделям семестра) |
| ||||||||||||||
Аудиторная работа | Самостоятельная работа |
| ||||||||||||||||||
Всего | Лекция | Практические занятия | Лабораторные занятия | Всего | Подготовка к аудиторным занятиям | Реферат, эссе и др. | Курсовая работа (проект) | Подготовка к зачету | Собеседование | Коллоквиум | Проверка тестов | Проверка контрольн. работ | Проверка реферата | Проверка эссе и иных творческих работ | курсовая работа (проект) | др. | ||||
1. | Раздел 1. Основные принципы построения параллельных вычислительных систем. | 8 | 1-5 | 10 | 5 | 5 | 15 | 12 | 3 | 5 | 15 | |||||||||
1.1. | Тема 1.1. Основные понятия. | 8 | 1-2 | 4 | 2 | 2 | 10 | 8 | 2 | 5 | ||||||||||
1.2. | Тема 1.2. МРI интерфейс передачи сообщений. | 8 | 3-4 | 4 | 2 | 2 | 5 | 4 | 1 | 5 | ||||||||||
1.3. | Тема 1.3. Примеры простейших параллельных программ. | 8 | 5 | 2 | 1 | 1 | 5 | 4 | 1 | |||||||||||
2. | Раздел 2. Параллелизация матричных вычислений. | 8 | 6-8 | 14 | 5 | 5 | 4 | 20 | 17 | 3 | 5 | 15 | ||||||||
2.1. | Тема 2.1. Умножение матрицы на вектор | 8 | 6 | 2 | 1 | 1 | 10 | 8 | 2 | 5 | ||||||||||
Тема 2.2. Умножение матриц. | 8 | 7 | 6 | 2 | 2 | 2 | 16 | 9 | 6 | |||||||||||
2.2. | Тема 2.3. Решение СЛАУ. | 8 | 8 | 6 | 2 | 2 | 2 | 10 | 9 | 1 | 10 | |||||||||
3. | Раздел 3. Параллелизация решений дифференциальных уравнений и алгоритмов дискретной математики. | 8 | 9-13 | 15 | 5 | 5 | 5 | 15 | 12 | 3 | 10 | 15 | ||||||||
3.1. | Тема 3.1. Параллельные алгоритмы теории графов и комбинаторики | 8 | 9 | 4 | 1 | 1 | 2 | 10 | 8 | 2 | 10 | |||||||||
3.2. | Тема 3.2. Параллельные методы решения дифференциальных уравнений в частных производных. | 8 | 10-11 | 6 | 2 | 2 | 2 | |||||||||||||
3.3. | Тема 3.3. Параллельные методы решения систем ОДУ. | 8 | 12-13 | 5 | 2 | 2 | 1 | 5 | 4 | 1 | 10 | |||||||||
Курсовая работа (проект) | ||||||||||||||||||||
Подготовка к зачету | 5 | |||||||||||||||||||
Общая трудоемкость, в часах | 39 | 13 | 13 | 13 | 105 | 57 | 48 | 5 | Промежуточная аттестация | |||||||||||
Форма | Семестр | |||||||||||||||||||
Зачет | 8 | |||||||||||||||||||
Экзамен | - | |||||||||||||||||||
4.2. Содержание дисциплины
№ п/п | Наименование раздела дисциплины | Содержание раздела |
1. | Основные принципы построения параллельных вычислительных систем. | Введение. Краткие сведения о структуре параллельных вычислений. Различные виды параллельных архитектур. Принципы разработки параллельных методов. Кластер: понятие, особенности, свойства. Организация кластерной сети. Варианты построения кластера. Издержки и выигрыш при реализации параллельных и векторных вычислений. Классы задач, допускающие эффективную параллелизацию. Общая структура параллельных программ Понятие оптимального параллельного алгоритма. Принцип декомпозиции в параллельных задачах. Интерфейс передачи сообщений (MPI): установка, общая организация, базовые функции, коммуникационные операции, особенности, принципы работы. Передача данных по «конвейеру» и «кольцу». Примеры простейших параллельных программ. |
2. | Параллелизация матричных вычислений. | Умножение матрицы на вектор: при разделении данных по строкам, столбцам и блочном разделении: Определение подзадач. Выделение информационных зависимостей. Масштабирование и распределение подзадач по процессорам. Анализ эффективности. Параллельные методы матричного умножения. Умножение матриц при ленточной схеме разделения данных. Алгоритм Фокса умножения матриц при блочном разделении данных. Алгоритм Кэннона умножения матриц при блочном разделении данных. Анализ эффективности. Решение систем линейных уравнений. Метод Гаусса. Метод сопряженных градиентов. Определение подзадач. Выделение информационных зависимостей. Масштабирование и распределение подзадач по процессорам. Анализ эффективности. |
3. | Параллелизация решений дифференциальных уравнений и алгоритмов дискретной математики. | Параллельные методы сортировки. Быстрая сортировка. Сортировка Шелла.. Сортировка с использованием регулярного набора образцов. Параллельные методы на графах. Задача поиска всех кратчайших путей. Алгоритм Флойда. Задача нахождения минимального охватывающего дерева. Алгоритм Прима. Задача оптимального разделения графов. Параллельные методы решения дифференциальных уравнений в частных производных. Организация параллельных вычислений для систем с общей и разделенной памятью. OpenMP. Решение систем обыкновенных дифференциальных уравнений. Примеры на языке Фортран. |
5. Образовательные технологии
В процессе изучения дисциплины «Параллельные вычисления и параллельное программирование» предполагается использовать структурно-логические и интеграционные образовательные технологии, реализуемые посредством:
- лекций в виде вводных, текущих, обзорных и заключительно-обобщающих занятий;
- практических занятий с использованием методов «многократного повторения» (темы 2.1, 2.2, 2.3, 3.2); по логике мышления – индуктивные, дедуктивные и репродуктивные.
- лабораторных занятий, заключающихся в написании и отладке программ на языке высокого уровня Си++ (темы 2.2, 2.3, 3.1, 3.2, 3.3);.
- организации самостоятельной работы на основе личностно-дифференцированного подхода планирования задания в виде воспроизводящей и частично-поисковой работ.
- организации текущего контроля знаний студентов методами: выполнения домашних заданий, оценки активности на практических занятиях и рейтинговой системы общей оценки знаний студентов.
Занятия, проводимые в интерактивных формах, с использованием интерактивных технологий составляют 30% занятий.
6. Учебно-методическое обеспечение самостоятельной работы студентов.
Оценочные средства для текущего контроля успеваемости,
промежуточной аттестации по итогам освоения дисциплины.
6.1. План самостоятельной работы студентов
№ нед. | Тема | Вид самостоятельной работы | Задание | Рекомен-дуемая литера-тура | Количест-во часов | |
1-5 | Основные принципы построения параллельных вычислительных систем. | Подготовка к аудиторным занятиям | Типовое задание №1 |
| 12 | |
6-9 | Параллелизация матричных вычислений. | Подготовка к аудиторным занятиям | Типовое задание №2 |
| 10 |
10-13 | Параллелизация решений дифференциальных уравнений и алгоритмов дискретной математики. | Подготовка к аудиторным занятиям | Типовое задание №3 | П.7 а) 3, стр. 83-108 | 9 |
5-13 | Все темы | Подготовка к зачету | Изучение теорети-ческого материала | П.7 все источники а) | 5 |
5-13 | Темы 2.2, 2.3, 3.1, 3.2, 3.3 | Написание программ, их отладка и демонстрация | Темы лабораторных работ | П.7 все источники а) | 36 |
Образец типового задания №1
1) MPI-процесс с номером 0 вводит с клавиатуры массив из 8 целых чисел. Затем с помощью функции MPI_SCATTER рассылает по 4 процессам фрагменты этого массива. Каждый процесс печатает полученные данные. Произвести сложение всех элементов массива, распределенных по процессам, с помощью функций MPI_REDUCE с получением результата на процессе с номером 2. Вычисленное значение распечатать.
2) На нулевом процессе с помощью датчика случайных чисел сформировать массив из 10 вещественных чисел: x = cos(k rand()) ,k =1,2,...,10 k . С помощью процедуры MPI_BCAST разослать эти значения остальным процессам, умножить на каждом процессе элементы на его номер и определить глобальный максимальный элемент среди всех элементов, содержащихся на каждом процессе.
3) На каждом процессе определить значение переменной temp. Затем с использованием функций Send и Recv организовать передачу значения temp от каждого процесса остальным и замену значения temp наибольшим. Результат распечатать.
4) Сравнить эффективность коллективной операции Bcast с реализацией процедуры рассылки значения на остальные процессы с помощью функций MPI Send и Recv.
Образец типового задания №2
1) Написать MPI-программу, которая считывает из файла или вычисляет по заданной формуле вещественную матрицу А={аij} i=1,2,.. .,n; j=1,2,…,n, рассылает ее по процессорным элементам и определяет номер строки, максимально удаленной от первой строки заданной матрицы. Расстояние между k-й и i-й строками матрицы A определяется как 
. Обеспечить равномерную загрузку всех процессорных элементов, участвующих в работе программы.
2) Написать MPI-программу умножения матрицы A на вектор b. Параллельная программа должна считывать из файла или вычислять по заданной формуле вещественную матрицу A размерности n х n и вектор b размерности n. Обеспечить равномерную загрузку всех процессорных элементов, участвующих в работе программы.
3) Написать MPI-программу, которая считывает из файла или вычисляет по заданной формуле матрицу А={аij} i=1,2,...,n; j=1,2,…,n вещественных чисел и заменяет матрицу А на матрицу (А+АТ)/2, где АТ – транспонированная матрица А. Обеспечить равномерную загрузку всех процессорных элементов, участвующих в работе программы.
Образец типового задания №3
1) Используя представленную на лекции программу, решить систему линейных неоднородных ОДУ, в которой симметричная матрица имеет вид
В качестве начальных условий принять yi(0)=1, i=1,n . Сумму вычислять с точностью 
. Исследовать ускорение и эффективность параллельной программы в зависимости от размерности задачи и числа используемых процессов.
2) Используя представленную на лекции программу, решить обыкновенное дифференциальное уравнение n - го порядка: y(n) = cos(t) .В качестве начальных условий принять y(i)(0)=1, i=0,n-1. Исследовать ускорение и эффективность параллельной программы в зависимости от размерности задачи и числа используемых процессов.
3) Составить параллельную программу для решения системы линейных однородных ОДУ методом Рунге–Кутты четвертого порядка, описанным в лекции. Рассмотреть случай диагональной матрицы (aii = -1/i). В качестве начальных условий принять yi(0)=1, i=1,n. Исследовать ускорение и эффективность параллельной программы в зависимости от размерности задачи и числа используемых процессов.
6.2. Методические указания по организации самостоятельной работы студентов
- Подготовка к аудиторным занятиям проводится посредством изучения курса лекций, дополнительной литературы, а также решения предложенных задач.
- Подготовка лабораторных работ осуществляется в виде написания программ на языке высокого уровня Си++ с использованием дополнительной литературы.
-Подготовка к зачету – изучение курса лекций, изучение дополнительной литературы.
6.3. Материалы для проведения текущего и промежуточного контроля знаний студентов
Контроль освоения компетенций
№ п\п | Вид контроля | Контролируемые темы (разделы) | Компетенции, компоненты которых контролируются |
1 | Проведение теоретического опроса | Разделы 1, 2, 3. | ПК-5, ПК-11, ПК-12 |
2 | Проверка выполнения лабораторный работ | Разделы 2,3. | ПК-5, ПК-11, ПК-12 |
Вопросы к теоретическому опросу №1
1. Что такое параллельное программирование и суперкомпьютеры. Области в которых может возникать потребность в параллельных вычислениях. Особенности параллельных вычислений.
2. Увеличение производительности при параллельных вычислениях. К каким областям задач может быть применено распараллеливание и к каким нет. Закон Амдала.
3. Различные архитектуры параллельных компьютеров. Классификация Флинна.
4. Конвейерная обработка данных. Суперскалярные процессоры.
5. Векторная обработка данных.
6. Особенности построения параллельных алгоритмов. Системы автоматического распараллеливания и обычные схемы.
7. Разделение на подзадачи. Установление связей между отдельными подзадачами. Объединение мелких подзадач в большие, законченные счетные единицы (агломерация). Алгоритмы с использованием менеджера и без использования.
8. Балансировка загрузки узлов. Зависимость выбора алгоритма от структуры вычислительной сети.
Вопросы к теоретическому опросу №2
1. Умножение матрицы на вектор: при разделении данных по строкам, столбцам и блочном разделении. Сравнительный анализ.
2. Умножение матрицы на матрицу: при разделении данных по строкам, столбцам и блочном разделении. Сравнительный анализ.
3. Метод Жордана-Гаусса решения СЛАУ. Особенности реализации. Недостатки.
4. Метод Якоби решения СЛАУ. Особенности реализации. Недостатки.
5. Метод сопряженных градиентов решения СЛАУ. Особенности реализации. Недостатки.
Вопросы к теоретическому опросу №3
Алгоритмы Краскала, Прима, Флойда. Особенности реализации. Недостатки.2. Параллельные алгоритмы сортировки. Особенности реализации. Недостатки.
Метод Гаусса-Зейделя решения задачи Коши для уравнения Пуссона. Различные варианты исключения неоднозначности вычислений. Особенности реализации. Недостатки. Метод Рунге-Кутты решения систем ОДУ с постоянными коэффициентами. Особенности реализации. Недостатки. Схема «предиктор-корректор» решения систем ОДУ с постоянными коэффициентами. Особенности реализации. Недостатки.
Темы лабораторных работ:
Умножение мариц.. Метод Жордана-Гаусса решения СЛАУ. Реализация алгоритма Краскала. Решение задачи Коши для уравнения Пуассона. Решение систем ОДУ с постоянными коэффициентами.
Вопросы к зачету
Виды параллельных архитектур. Принципы разработки параллельных методов. Кластер: понятие, особенности, свойства. Организация кластерной сети. Варианты построения кластера. Издержки и выигрыш при реализации параллельных и векторных вычислений. Классы задач, допускающие эффективную параллелизацию. Общая структура параллельных программ Понятие оптимального параллельного алгоритма. Принцип декомпозиции в параллельных задачах. Интерфейс передачи сообщений (MPI): установка, общая организация, базовые функции, коммуникационные операции, особенности, принципы работы. Передача данных по «конвейеру» и «кольцу». Умножение матрицы на вектор: при разделении данных по строкам, столбцам и блочном разделении. Параллельные методы матричного умножения. Умножение матриц при ленточной схеме разделения данных. Алгоритм Фокса умножения матриц при блочном разделении данных. Алгоритм Кэннона умножения матриц при блочном разделении данных. Метод Гаусса. Метод сопряженных градиентов. Параллельные методы сортировки. Быстрая сортировка. Сортировка Шелла.. Сортировка с использованием регулярного набора образцов. Параллельные методы на графах. Задача поиска всех кратчайших путей. Алгоритм Флойда. Задача нахождения минимального охватывающего дерева. Алгоритм Прима. Задача оптимального разделения графов. Параллельные методы решения дифференциальных уравнений в частных производных. Организация параллельных вычислений для систем с общей и разделенной памятью. Решение систем обыкновенных дифференциальных уравнений.7. Учебно-методическое и информационное обеспечение
дисциплины «Параллельные вычисления и параллельное программирование»
а) Основная литература
1. Антонов программирование с использованием MPI. – М.: Изд-во МГУ, 2004. – 71 с.
2. , , Жегуло многопроцессорных вычислительных систем. – Ростов н/Д: Изд-во , 2003. – 208 с.
3. , Воеводин Вл. В. Параллельные вычисления. – СПб.: БХВ-Петербург, 2002. – 609 с.
4. , Стронгин параллельных вычислений для многопроцессорных вычислительных машин. – Нижний Новгород: Изд-во ННГУ им. , 2000. – 176 с.
5. Корнеев вычислительные системы. – М.: Нолидж, 1999. – 320 с.
6. , Есаулов вычисления на многопроцессорных вычислительных системах. – Томск: Изд-во Том. ун-та, 2002. – 56 с.
б) дополнительная литература:
1. http://intel. ru
2. http://www. parallel. ru/cluster/intel_compilers. html
3. http://temag. ru/?ID=604337
4. , Николаев решения сеточных уравнений. – М.: Наука, 1978. – 592 с.
5. Самарский в численные методы. – М.: Наука, 1987. – 288 с.
6. Самарский разностных схем. – М.: Наука, 1989. – 614 с.
8. Материально-техническое обеспечение дисциплины (модуля)
Занятия по дисциплине «Параллельные вычисления и параллельное программирование» проводятся в лекционных аудиториях университета.
Рабочая программа дисциплины «Параллельные вычисления и параллельное программирование» составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций ПрООП по направлению подготовки 01.03.04 — «Прикладная математика»
Программу составили:
1. _______________________________ доцент кафедры ВиПМ
Настоящая программа не может быть воспроизведена ни в какой форме без предварительного письменного разрешения кафедры-разработчика программы.
Программа одобрена на заседании кафедры «Высшая и прикладная математика»
Протокол № ___ от «____» _____________ 201_ года
Зав. Кафедрой ВиПМ ________________ проф. ______________
Программа согласована с заведующим выпускающей кафедрой «Высшая и прикладная математика»
Зав. Кафедрой ВиПМ _______________ проф. ______________
Программа одобрена методической комиссией ФВТ
Протокол № ___ от «____» ______________ 201__ года
Председатель методической комиссии ФВТ
К. т.н., профессор
Сведения о переутверждении программы на очередной учебный год и регистрации изменений
Учебный год | Решение кафедры (№ протокола, дата, подпись зав. кафедрой) | Внесенные изменения | Номера листов (страниц) | ||
заменен- ных | новых | аннулиро-ванных | |||
