Направление подготовки: 02.06.01 Компьютерные и информационные науки Направленность (профиль) подготовки: 01.01.07 – Вычислительная математика Квалификация владеть: теоретическими знаниями в построении и программировании параллельных систем


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное автономное учреждение

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

"Казанский (Приволжский) федеральный университет"


УТВЕРЖДАЮ

Проректор по научной деятельности КФУ

проф.
Д.

К.

Нургалиев

_________________

"_____"__________________20__ г.






Программа дисциплины



Б1.В.ОД.5 Введение в высокопроизводительные вычисления




Направление подготовки: 02.06.01 Компьютерные и информационные науки

Направленность (профиль)
подготовки: 01.01.07


Вычислительная математика

Квалификация выпускника «Исследователь. Преподаватель
-
исследователь»

Форма обучения: очная

Язык обучения: русский


















Казань 201
4



Положение о рабочей программе дисциплины
федерального
государственного автономного образовательного
учреждения высшего образования «Казанский (Приволжский) федеральный университет»



2


1. КРАТКАЯ АННОТАЦИЯ

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


2.
М
ЕСТО ДИСЦИПЛИНЫ

(МОДУЛЯ)

В СТРУКТУРЕ О
ПОП

Данная дисциплина относится к общепрофессиональным дисциплинам
.

Осваивается на
1

курсе в
1

семестре аспирантами, обучающимися по направлению
«Исследователь
.
Преподаватель
-
исследователь»
.


Для успешного освоения данной
дисциплины нужно освоение
в качестве предшествующих
следующих дисциплин:



Архитектура компьютера;



Численные методы;



Программирование на языках
C
/
C
++.


3. ПЕРЕЧЕНЬ ПЛАНИРУЕМЫХ РЕЗУЛЬТАТОВ ОБУЧЕНИЯ ПО ДИСЦИПЛИНЕ
(МОДУЛЮ)


Обучающ
ийся, завершивший изучение дисциплины, должен

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

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

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

д
емонстрир
овать способность и готовность

применять полученные знания на
практике


В результате освоения дисциплины формируются следующие компетенции:



Шифр компетенции

Расшифровка

приобретаемой компетенции

ОПК
-
1

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



4.
СТРУКТУРА И СОДЕРЖАНИЕ ДИСЦИПЛИНЫ (МОДУЛЯ)


4.1. Распределение трудоёмкости дисциплины (в часах) по видам нагрузки обучающегося
и по разделам дисциплины


Положение о рабочей программе дисциплины
федерального
государственного автономного образовательного
учреждения высшего образования «Казанский (Приволжский) федеральный университет»



3

Общая трудоемкость дисциплины составляет
2
зачетных единицы
, 72
часа. Из них:
лекции
12
ч
.,
практика
6

ч
.,
самостоятельная работа
54
ч
.


Итоговая форма контроля: зачет.



Раздел дисциплины

Семестр

Лекции

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

занятия

Лаборат
орные

работы

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

1
.

Классификация параллельных архитектур

1

1



4

2
.

Параллелизм и его использование

1

1



4

3
.

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

1

2

2


6

4
.

Технология программирования MPI

1

2

2


6

5
.

Гибридная модель параллельного
программирования

1

2



10

6
.

Параллельная реализация некоторых
частных методов

1

2

2


10

7
.

Явная схема Эйлера. Метод
декомпозиции
области.

1

2



14



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


Тема
1.

Классификация параллельных архитектур
.

Классификация Флинна
,
однопроцессорные системы
,
системы с векторными

процессорами
,
мультипроцессорные системы с памятью общего использования
, UMA SMP,
когерентность
кешей
, UMA
с коомутируемой сетью межсоединений
, NUMA, COMA.

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

Многомашинные

системы с передачей сообщений
,
массивно
-
параллельные системы
,
кластеры
и сети рабочих станций
,
ПО для управления многомашинными системами
. PVM, MPI, Linda,
Orca.

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

Тема 2. Параллелизм и его использование.

Графы информационных зависимостей
.
К
онцепция неограниченного параллелизма
.
Крупноблочное распараллеливание
.
Низкоуровневое распараллеливание
.
Оценка
эффективности параллельных вычислений
.

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


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

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

Решение задач по созданию параллельных программ с помощью технологии
OpenMP
.
Разбор
особенностей этой технологии
.


Тема 4. Технология программирования MPI.

Общие функции
,
функции приема
/
передачи сообщений между процессами
.
Функции
коллективного взаимодействия процессов
,
создания пользовательских операций
,
работа с
группами процес
сов
.
Пересылка разнотипных данных
,
производные типы данных
,
упаковка
Положение о рабочей программе дисциплины
федерального
государственного автономного образовательного
учреждения высшего образования «Казанский (Приволжский) федеральный университет»



4

данных
.
Решение задач по созданию параллельных программ с помощью технологии
MPI.
Разбор особенностей этой технологии
.


Тема 5. Гибридная модель параллельного программирования.

Совместное

использование технологий программирования
MPI, OpenMP.

Решение задач с привлечением обеих технологий
-

MPI
и
OpenMP.
Разбор особенностей
совместного использования
.


Тема 6. Примеры параллельных численных методов.

Умножение матрицы на вектор
.
Произведение матриц
(
алгортм Штрассена
).
Параллельная
реализация волнового алгоритма
.
Быстрое преобразование Фурье
.
Решение системы линейных
уравнений с трехдиагональной матрицей
-

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

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

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

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


Тема 7. Метод декомпозиции области Шварца с налегающими подобластями.

Формулировка

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

Метод декомпозиции области Шварца с налегающими подобластями для стационарного
уравнения теплопроводности как пример крупнозернистого распараллеливания на уровне
алгоритма
.



5. ОБРАЗОВАТЕЛЬНЫЕ ТЕХНОЛОГИИ

На лекциях:



п
р
едметно
-

и личностно
-
ориентированные технологии обучения
;



презентации с использованием мультимеди
йного

оборудования
;


На семинарах:



проблемно
-
ориентированные дискуссии
;



обсуждение материалов рефератов;



обсуждение дополнительной литературы;



презентации с
использованием мультимеди
йного

оборудования
;



п
редметно
-

и личностно
-
ориентированные технологии обучения
;

.


6.
УЧЕБНО
-
МЕТОДИЧЕСКОЕ
ОБЕСПЕЧЕНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ
РАБОТЫ ОБУЧАЮЩИХСЯ ПО ДИСЦИПЛИНЕ (МОДУЛЮ)


САМОСТОЯТЕЛЬНАЯ РАБОТА АСПИРАНТОВ
(
СРА
)
включает с
ледующие виды работ
:

Темы 1
-
2.

Реферат
.
Варианты тем
:

Положение о рабочей программе дисциплины
федерального
государственного автономного образовательного
учреждения высшего образования «Казанский (Приволжский) федеральный университет»



5

1)

Описание какой
-
либо существующей параллельной архитектуры

2)

Языки программирования
,
позволяющие создавать параллельные программы на уровне
ядра языка или его стандартной библиотеки

3)

Вычисления на графических процессорах и специализированных со
-
процессорах
.


Тема 3.

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

Параллельная реализация волнового алгоритма поиска к
ратчайшего пути в графе
.


Темы 4
-
5.

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

с совместным использованием технологий
MPI
и
OpenMP.


Тема 6.

Реализация
reduce
-
алгоритма для скалярного произведения
векторов
.

Конвейерная реализация алгоритма
,
вычисляющего выражение
(A[i]*B[i]+C[i])/D[i]

Исследование устойчивости алгоритма Штрассена
.


Тема 7.

Программная реализация явной схемы Эйлера для решения двумерной нестационарной задачи
Пуассона
.

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


7. ФОНД ОЦЕНОЧНЫХ СРЕДСТВ

7.1.
Регламент дисциплины

Форма контроля:
зачет


Промежуточная форма контроля



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


7.2. Оценочные средства текущего контроля


Самостоятельная работа аспирантов

включает следующие виды работ:




анализ учебной литературы по темам лекционного материала;



подготовка рефератов по общим темам
;



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



7.3.
Вопросы к зачету

1.

Классификация многопроцессорных ЭВМ с общей памятью.

2.

Балансировка нагрузки map/reduce
-
алгоритмов.

3.

Алгоритм MESI.

4.

Слабая согласованность кеш
-
памяти. Барьеры памяти.

5.

Примитивы синхронизации параллельных программ. Системная реализация Мьютекса.

6.

Примитивы синхронизации параллельных программ. CAS
-
реализация Мьютекса.

7.

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

Положение о рабочей программе дисциплины
федерального
государственного автономного образовательного
учреждения высшего образования «Казанский (Приволжский) федеральный университет»



6

8.

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

9.

Способы реализации потокобезопасной очереди

10.

Способы реализации потокобезопасного стека

11.

Высокоуровнемые паттерны проектирования: Pipeline (конвейер), Master and Slave
(хозяин и подчи
нённый), Replicable (воспроизводимый).

12.

Высокоуровнемые паттерны проектирования: Divide and Conquer (разделяй и властвуй),
Geometric Decomposition (геометрическая декомпозиция).

13.

Реализация подхода префиксного суммирования: паттерн scan.

14.

Алгоритм Штрассена.


7.4.
Таблица соответствия компетенций, критериев оценки их освоения и оценочных
средств



Индекс
компете
нции

Расшифровка
компетенции

Показатель
формирования
компетенции для
данной дисциплины

Оценочное средство

О
ПК
-
1

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

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

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


8. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ДЛЯ ОБУЧАЮЩИХСЯ ПРИ ОСВОЕНИИ
ДИСЦИПЛИНЫ

(МОДУЛЯ)

В процессе обучения
аспирантов

по дисциплине

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

Практическое занятие состоит
из следующих этапов:



проверка исходных знаний;



формулировка самостоятельных заданий и обсуждение путей их решения;



обсуждение возникающих в процессе решения трудностей.

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

практи
ческие вопросы
, ошибки, допущенные
аспирантами

при обсуждении, а также на
самостоятельность и активность работы
аспирантов

с литературой и лекционным материалом.

Для успешного освоения дисциплины каждый
аспирант

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

Положение о рабочей программе дисциплины
федерального
государственного автономного образовательного
учреждения высшего образования «Казанский (Приволжский) федеральный университет»



7

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

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

Самостоятельная работа является обязательной составляющей деятельности
аспиранта

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

так же указана
трудоемкость са
мостоятельной работы по каждой из тем. Это


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

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

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

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

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

длительность устойчивости внимания


45 минут. При появлении рассеянности
есть необходимость прервать

работу на 3


5 минут, но не
следует покидать

рабочее ме
сто.
Каждые 1.5


2 часа необходимо делать перерыв на 10
-
15 минут. Желательно сопровождать
перерыв интенсивной физической активностью.


9.
УЧЕБНО
-
МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ
ДИСЦИПЛИНЫ (МОДУЛЯ)


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

1.

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

В
.

Линев
,
Д
.
К
.
Боголепов
,
С
.
И
.
Бастраков
;
под ред
.
В
.
П
.
Гергеля
;
Нижегор
.
гос
.
ун
-
т
им
.
Н.

И
.
Лобачевского.
-

Москва
:
Изд
-
во Московского университета, 2010.
-

148
с
.

2.

Инструменты параллельного программирования в системах с общей памятью
:
учебник
для студентов высших учебных заведений
/
К
.
В
.
Корняков
,
В
.
Д
.
Кустикова
,
И
.
Б
.
Мееров
[
и др
.];
под ред
.
проф
.
В
.
П
.
Гергеля
;
Нижегор
.
гос
.
ун
-
т им
.
Н
.
И
.
Лобачевского
,
Координац
.
совет Системы науч
.
-
образоват
.
центров суперкомпьютер
.
технологий.
-

2
-
е
изд
.,
испр
.
и доп.
-

Москва
:
Изд
-
во Московского университета, 2010.
-

262
с
.

3.

Богачёв К
.

Ю
.
Основы параллельного программирования
:
учебное
пособие
.
-

2
-
е
(
эл
.).
-

М
.:
Бином
.
Лаборатория знаний
, 2013.
-

342
с.

http://e.lanbook.com/books/element.php?pl1_id=42626


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

1.

Столов Е
.
Л
.
Введение в цифровую обработку изображений и параллельные вычисления
:
[
учеб
.
пособие
] /
Е
.

Л
.
Столов
;
Казан
.
гос
.
ун
-
т.
-

Казань
: [
КГУ
], 2
006.
-

67
с
.

Положение о рабочей программе дисциплины
федерального
государственного автономного образовательного
учреждения высшего образования «Казанский (Приволжский) федеральный университет»



8

2.

Кандаурова
,
Н
.
В
.
Вычислительные системы
,
сети и телекоммуникации
. (
Курс лекций и
лабораторный практикум
) [
Электронный ресурс
]:
учеб
.
пособие
/
Н
.
В
.
Кандаурова
,
С.

В.

Яковлев
,
В
.
П
.
Яковлев и др
.
-

2
-
е изд
.,
стер
.
-

М
.:
ФЛИНТА
, 2013.
-

344
с
.
http://znanium.com/bookread.php?book=466100

3.

Сырецкий
,
Г
.
А
.
Информатика
.
Фундаментальный курс
.
Том
II.
Информационные
технологии и системы
/
Г
.
А
.
C
ырецкий.
-

СПб
.:
БХВ
-
Петербург, 2007.
-

846
с
.
http://znanium.com/bookread.php?book=350042



9
.3. Интернет
-
ресурсы:

1.

Информационно
-
аналитический центр по параллельным вычислениям

-

http://parallel.ru

2.

Основы работы с технологией
CUDA
-

http://www.znanium.com

3.

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

спец
иалистов
по

численному анализу
-

http://z3950.ksu.ru/bcover/0000730145_con.pdf

4.

Справочник по компьютерной математике
-

http://www.users.kaluga.ru/math/


10. МАТЕРИАЛЬНО
-
ТЕХНИЧЕСКОЕ И ПРОГРАММНОЕ

ОБЕСПЕЧЕНИЕ
ДИСЦИПЛИНЫ (МОДУЛЯ)

Компьютерный класс
,
представляющий собой рабочее место преподавателя и не менее
15
рабочих мест студентов
,
включающих компьютерный стол
,
стул
,
персональный

компьютер с
многоядерным процессором
,
лицензионное программное обе
спечение
, включающее в себя
среду разработки на языках C/C++ с компилятором, удовлетворяющим стандарту C++11 или
C++14 и содержащим поддержку расширения OpenMP.

Каждый компьютер имеет

широкополосный доступ в

сеть Интернет
.
Все компьютеры
подключены к корпо
ративной компьютерной сети КФУ и

находятся в едином домене
.


Программа составлена в соответствии с требованиями ФГОС ВО и с учетом

рекомендаций по направлению подготовки
.


Автор(ы):

Даутов Р.З.

Рецензент(ы):
Павлова М. Ф.


Программа одобрена на заседании Учебно
-
методической комиссии Института ВМ и ИТ КФУ
от 11 сентября 2014 г. протокол № 1.



Приложенные файлы

  • pdf 4397133
    Размер файла: 370 kB Загрузок: 0

Добавить комментарий