Параллельные вычисления - polpoz.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Конкурс «тризформашка-2014: Параллельные вычисления» 1 86.8kb.
Брайан Грин Скрытая реальность. Параллельные миры и глубинные законы... 50 5592.57kb.
«Приближенные методы вычисления корней уравнений» 1 55.56kb.
Занятие 8 Числа Фибоначчи 1 272.54kb.
Вопросы опроса №3 по теме «Углы. Параллельные прямые. Подобие и равенство... 1 52.78kb.
Практическая работа №25. Тема: LibreOffice Calc. Создание и форматирование... 1 16kb.
Параллельные вычислительные технологии цикл: 20 февраля – 2 марта... 1 29.59kb.
Пример вычисления норм теста 1 109.86kb.
Центр обучения и повышения квалификации переводчиков и преподавателей... 1 94.15kb.
Мпс для высокопроизводительной обработки информации 1 231.81kb.
Исследовательская работа по математике Тема: «Счет и вычисления основа... 1 193.51kb.
Общие сведения об учебном курсе 1 416.55kb.
1. На доске выписаны n последовательных натуральных чисел 1 46.11kb.

Параллельные вычисления - страница №1/1



РОССИЙСКАЯ ФЕДЕРАЦИЯ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ


Государственное образовательное учреждение

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

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

ИНСТИТУТ МАТЕМАТИКИ, ЕСТЕСТВЕННЫХ

НАУК, ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

КАФЕДРА АЛГЕБРЫ И МАТЕМАТИЧЕСКОЙ ЛОГИКИ

БАРАННИКОВА Д.Д.

ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ


Учебно-методический комплекс.

Рабочая программа для студентов очной формы обучения,

направление 010100.62 "Математика",

профиль подготовки "Алгебра, теория чисел, математическая логика"

Тюменский государственный университет

2011


Баранникова Д.Д. Параллельные вычисления. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения, направления 010100.62 "Математика", профиль подготовки "Алгебра, теория чисел, математическая логика". Тюмень, 2011, 19 стр.

Рабочая программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению и профилю подготовки.

Рабочая программа дисциплины опубликована на сайте ТюмГУ: «Параллельные вычисления» [электронный ресурс] / Режим доступа: http://www.umk3.utmn.ru., свободный.

Рекомендовано к изданию кафедрой алгебры и математической логики. Утверждено проректором по учебной работе Тюменского государственного университета.



ОТВЕТСТВЕННЫЙ РЕДАКТОР: В.Н. Кутрунов, д. ф.-м. н., профессор.

© Тюменский государственный университет, 2011.

© Баранникова Д.Д., 2011.


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




    1. Цель и задача дисциплины.

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

Цель дисциплины:

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

Задача дисциплины:

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


    1. Место дисциплины в структуре ООП бакалавриата.

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

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

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

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

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

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

способностью применять знания на практике (ОК-6);

способностью приобретать новые знания, используя современные образовательные и информационные технологии (ОК-8);

навыками работы с компьютером (ОК-12);

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

способностью к анализу и синтезу (ОК-14);

умением понять поставленную задачу (ПК-2);

умением формулировать результат (ПК-3);

умением строго доказать утверждение (ПК-4);

умением на основе анализа увидеть и корректно сформулировать результат (ПК-5);

умением самостоятельно увидеть следствия сформулированного результата (ПК-6);

умением грамотно пользоваться языком предметной области (ПК-7);

умением ориентироваться в постановках задач (ПК-8);

знанием корректных постановок классических задач (ПК-9);

пониманием корректности постановок задач (ПК-10);

пониманием того, что фундаментальное знание является основой компьютерных наук (ПК-12);

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

выделением главных смысловых аспектов в доказательствах (ПК-16);

владением методом алгоритмического моделирования при анализе постановок математических задач (ПК-19);

владением методами математического и алгоритмического моделирования при решении прикладных задач (ПК-20);

владением методами математического и алгоритмического моделирования при анализе теоретических проблем и задач (ПК-21);

владением проблемно-задачной формой представления математических знаний (ПК-22);

владением методами математического и алгоритмического моделирования при анализе управленческих задач в научно-технической сфере (ПК-24);

умением точно представить математические знания в устной форме (ПК-27);

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


В результате освоения дисциплины обучающийся должен:


  • Знать: основные методы разработки программ для параллельных ЭВМ с общей и с распределенной памятью, виды разделяемых ресурсов и способы взаимного исключения при доступе к разделяемым ресурсам, иметь представление о потоках исполнения и интерфейсе MPI.

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

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




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


2. Структура и трудоемкость дисциплины.
Семестр 8. Форма промежуточной аттестации: экзамен. Общая трудоемкость дисциплины составляет 3 зачетные единицы, 108 часов.
3. Тематический план.

Таблица 1.

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



Тема

недели семестра

Виды учебной работы и самостоятельная работа, в час.

Итого часов по теме

Из них в интерактивной форме

Итого количество баллов

Лекции*

Семинарские (практические) занятия*

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




1

2

3

4

5

7

8

9

10




Модуль 1






















1.1

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

1

2

2

4

8

2

0 – 10

1.2

Модели вычислений и методы анализа эффективности

2-3

4

4

6

14

4

0 – 10

1.3

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

4-5

4

4

6

14

4

0 – 10




Всего




10

10

16

36

10

0-30




Модуль 2






















2.1

Технология разработки параллельных программ для многопроцессорных систем с распределенной памятью (стандарт передачи сообщений MPI)

6-7

4

4

6

14

4

0 – 14

2.2

Технология разработки параллельных программ для многопроцессорных систем с общей памятью (стандарт OpenMP)

8-9

4

4

6

14

4

0-14

2.3

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

10

2

2

4

8

2

0-7




Всего




10

10

16

36

10

0-35




Модуль 3






















3.1

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

11-13

6

6

10

22

4

0-20

3.2

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

14-15

4

4

6

14

4

0-15




Всего




10

10

16

36

8

0-35




Итого (часов, баллов):




30

30

48

108

28

0-100




Из них в интерактивной форме







14

14




28






Таблица 2.

Виды и формы оценочных средств в период текущего контроля.

№ темы

Устный опрос

Письменные работы

Информационные системы и технологии

Итого

количество

баллов


собеседование

ответ на

семинаре


Контрольная работа

Электронный

практикум






Модуль 1

1.1

-

0-2

0-5

0-3

0 – 10

1.2

-

0-2

0-5

0-3

0 – 10

1.3

-

0-2

0-5

0-3

0 – 10

Всего

-

0-6

0-15

0-9

0-30




Модуль 2

2.1

0-2

0-2

0-8

0-2

0 – 14

2.2

0-1

0-2

0-8

0-3

0-14

2.3

0-2

0-2

-

0-3

0-7

Всего

0-5

0-6

0-16

0-8

0-35




Модуль 3

3.1

0-1

0-3

0-10

0-6

0-20

3.2

0-2

0-2

0-8

0-3

0-15

Всего

0-3

0-5

0-18

0-9

0-35

Итого

0-8

0-17

0-49

0-26

0-100



Таблица 3.

Планирование самостоятельной работы студентов.



Модули и темы

Виды СРС

Неделя семестра

Объем часов

Кол-во баллов

Обязательные

Дополнительные

1

Модуль 1
















1.1

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

Проработка лекций, работа с литературой, решение

типовых задач



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

1

4

0-3

1.2

Модели вычислений и методы анализа эффективности

2-3

6

0-3

1.3

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

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

4-5

6

0-3




Всего по модулю 1

16

0-9

2

Модуль 2
















2.1

Технология разработки параллельных программ для многопроцессорных систем с распределенной памятью (стандарт передачи сообщений MPI)

Проработка лекций, работа с литературой, решение

типовых задач



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

6-7

6

0-2

2.2

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

8-9

6

0-3

2.3

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

10

4

0-3




Всего по модулю 2

16

0-8

3

Модуль 3
















3.1

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

Проработка лекций, работа с литературой, решение

типовых задач



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

11-13

10

0-6

3.2

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

14-15

6

0-3




Всего по модулю 3

16

0-9




Итого (часов, баллов)

48

0-26



  1. Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами.

№ п/п

Наименование обеспечиваемых (последующих) дисциплин

Темы дисциплины необходимые для изучения обеспечиваемых (последующих) дисциплин

1.1

1.2

1.3

2.1

2.2

2.3

3.1

3.2

1.

Выполнение дипломной работы

+

+

+

+

+

+

+

+

2.

Производственная практика

+

+

+

+

+

+

+

+



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


Модуль 1

Тема №1.1. Принципы построения параллельных вычислительных систем.

Цели и задачи введения параллельной обработки данных. Важность проблематики параллельных вычислений. Обзор современных параллельных вычислительных систем. Мультипроцессоры и мультикомпьютеры. Типовые топологии сети передачи данных. Классификация и оценка производительности. Понятие кластерных систем.

Тема № 1.2. Модели вычислений и методы анализа эффективности.

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

Тема № 1.3. Анализ коммуникационной трудоемкости параллельных алгоритмов. Критерии оценки топологии сети. Алгоритмы маршрутизации и методы передачи данных. Типовые операции взаимодействия. Методы логического представления топологии сети. Оценка времени передачи данных для кластерных систем.



Модуль 2

Тема № 2.1. Технология разработки параллельных программ для многопроцессорных систем с распределенной памятью (стандарт передачи сообщений MPI) . Общая характеристика стандарта MPI. Режимы передачи данных. Коллективные операции. Конструирование производных типов данных. Управление процессами. Создание логических топологий. Примеры: матричные вычисления, решение уравнений в частных производных.

Тема № 2.2. Технология разработки параллельных программ для многопроцессорных систем с общей памятью (стандарт OpenMP). Общая характеристика стандарта OpenMP. Создание параллельных областей. Разделение вычислительной нагрузки между потоками. Работа с данными. Синхронизация. Функции и переменные окружения. Сравнительная характеристика подходов параллельного программирования для систем с распределенной и общей памятью.

Тема № 2.3 Принципы разработки параллельных методов. Моделирование параллельных программ. Этапы разработки: разделение вычислений, выделение информационных зависимостей, масштабирование и распределение вычислений между процессорами. Демонстрация на примере решения гравитационной задачи N-тел.



Модуль 3.

Тема № 3.1 Параллельные численные алгоритмы для решения типовых задач вычислительной математики. Матричные вычисления: матрично-векторное умножение, умножение матриц, решение систем линейных уравнений. Сортировка. Обработка графов. Решение уравнений в частных производных. Оптимизация.

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


  1. Планы семинарских занятий.


Модуль 1

Тема №1.1. Принципы построения параллельных вычислительных систем.

Цели и задачи введения параллельной обработки данных. Важность проблематики параллельных вычислений. Обзор современных параллельных вычислительных систем. Мультипроцессоры и мультикомпьютеры. Типовые топологии сети передачи данных. Классификация и оценка производительности. Понятие кластерных систем.

Тема № 1.2. Модели вычислений и методы анализа эффективности.

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

Тема № 1.3. Анализ коммуникационной трудоемкости параллельных алгоритмов. Критерии оценки топологии сети. Алгоритмы маршрутизации и методы передачи данных. Типовые операции взаимодействия. Методы логического представления топологии сети. Оценка времени передачи данных для кластерных систем.



Модуль 2

Тема № 2.1. Технология разработки параллельных программ для многопроцессорных систем с распределенной памятью (стандарт передачи сообщений MPI) . Общая характеристика стандарта MPI. Режимы передачи данных. Коллективные операции. Конструирование производных типов данных. Управление процессами. Создание логических топологий. Примеры: матричные вычисления, решение уравнений в частных производных.

Тема № 2.2. Технология разработки параллельных программ для многопроцессорных систем с общей памятью (стандарт OpenMP). Общая характеристика стандарта OpenMP. Создание параллельных областей. Разделение вычислительной нагрузки между потоками. Работа с данными. Синхронизация. Функции и переменные окружения. Сравнительная характеристика подходов параллельного программирования для систем с распределенной и общей памятью.

Тема № 2.3 Принципы разработки параллельных методов. Моделирование параллельных программ. Этапы разработки: разделение вычислений, выделение информационных зависимостей, масштабирование и распределение вычислений между процессорами. Демонстрация на примере решения гравитационной задачи N-тел.



Модуль 3.

Тема № 3.1 Параллельные численные алгоритмы для решения типовых задач вычислительной математики. Матричные вычисления: матрично-векторное умножение, умножение матриц, решение систем линейных уравнений. Сортировка. Обработка графов. Решение уравнений в частных производных. Оптимизация.

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


  1. Темы лабораторных работ (Лабораторный практикум).

Не планируются.


  1. Примерная тематика курсовых.

Не планируются.


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

a) Текущая аттестация:

  • контрольные работы; В каждом семестре проводятся контрольные работы (на семинарах).

  • тестирование (письменное или компьютерное) по разделам дисциплины;

b) Промежуточная аттестация:

  • тестирование по дисциплине;

  • экзамен (письменно-устная форма). Экзамен выставляется после ответа на вопросы экзаменационного билета.

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

Варианты контрольных работ:
Контрольная работа №1

1. Разработайте программу для нахождения минимального (максимального) значения среди элементов вектора.

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

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

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

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

6. Выполните задание 3 с использованием операции одновременного выполнения передачи и приема данных. Сравните результаты вычислительных экспериментов.

7. Разработайте программу-пример для каждой имеющейся в MPI коллективной операции.

8. Разработайте реализации коллективных операций при помощи парных обменов между процессами. Выполните вычислительные эксперименты и сравните времена выполнения разработанных программ и функций MPI для коллективных операций.

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

10. Разработайте программу-пример для каждого имеющегося в MPI способа конструирования производных типов данных.

11. Разработайте программу-пример с использованием функций упаковки и распаковки данных. Выполните эксперименты и сравните с результатами при использовании производных типов данных.

12. Разработайте производные типы данных для строк, столбцов, диагоналей матриц.

13. Разработайте программу-пример для каждой из рассмотренных функций для управления процессами и коммуникаторами.

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

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

16. Разработайте программу-пример для декартовой топологии.

17. Разработайте программу-пример для топологии графа.

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

Контрольная работа № 2

1. Выполните реализацию двух ленточных алгоритмов умножения матриц. Сравните времена выполнения этих алгоритмов.

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

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

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

Контрольные вопросы к экзамену
Принципы построения параллельных вычислительных систем:

1. В чем заключаются основные способы достижения параллелизма?

2. В чем могут состоять различия параллельных вычислительных систем?

3. Что положено в основу классификация Флинна?

4. В чем состоит принцип разделения многопроцессорных систем на мультипроцессоры и мультикомпьютеры?

5. Какие классы систем известны для мультипроцессоров?

6. В чем состоят положительные и отрицательные стороны симметричных мультипроцессоров?

7. Какие классы систем известны для мультикомпьютеров?

8. В чем состоят положительные и отрицательные стороны кластерных систем?

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

10. В чем состоят особенности сетей передачи данных для кластеров?

11. Каковы основные характеристики сетей передачи данных?

12. Какие системные платформы могут быть использованы для построения кластеров?
Модели вычислений и методы анализа эффективности:

1. Как определяется модель "операция - операнды"?

2. Как определяется расписание для распределения вычислений между процессорами?

3. Как определяется время выполнения параллельного алгоритма?

4. Какое расписание является оптимальным?

5. Как определить минимально возможное время решения задачи?

6. Что понимается под паракомпьютером и для чего может оказаться полезным данное понятие?

7. Какие оценки следует использовать в качестве характеристики времени последовательного решения задачи?

8. Как определить минимально возможное время параллельного решения задачи по графу "операнды – операции"?

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

10. При каком числе процессоров могут быть получены времена выполнения параллельного алгоритма, сопоставимые по порядку с оценками минимально возможного времени решения задачи?

11. Как определяются понятия ускорения и эффективности?

12. Возможно ли достижение сверхлинейного ускорения?

13. В чем состоит противоречивость показателей ускорения и эффективности?

14. Как определяется понятие стоимости вычислений?

15. В чем состоит понятие стоимостно-оптимального алгоритма?

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

17. В чем состоит каскадная схема суммирования? С какой целью рассматривается модифицированный вариант данной схемы?

18. В чем различие показателей ускорения и эффективности для рассматриваемых вариантов каскадной схемы суммирования?

19. В чем состоит параллельный алгоритм вычисления всех частных сумм последовательности числовых значений?

20. Как формулируется закон Амдаля? Какой аспект параллельных вычислений позволяет учесть данный закон?

21. Какие предположения используются для обоснования закона Густавсона-Барсиса?

22. Как определяется функция изоэффективности?

23. Какой алгоритм является масштабируемым? Приведите примеры методов с разным уровнем масштабируемости.


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

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

2. Какие основные методы применяются при маршрутизации передаваемых данных по сети?

3. В чем состоят основные методы передачи данных? Приведите для этих методов аналитические оценки времени выполнения?

4. Какие операции передачи данных могут быть выделены в качестве основных?

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

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

7. В чем состоят возможные алгоритмы выполнения операции редукции? Какой из алгоритмов является наилучшим по времени выполнения?

8. В чем состоят алгоритм выполнения операции циклического сдвига?

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

10. В чем различие моделей для оценки времени выполнения операций передачи данных в кластерных вычислительных системах? Какая модель является более точной? Какая модель может быть использована для предварительного анализа временной трудоемкости коммуникационных операций?
Технология разработки параллельных программ для многопроцессорных систем с распределенной памятью (стандарт передачи сообщений MPI):

1. Какой минимальный набор средств является достаточным для организации параллельных вычислений в системах с распределенной памятью?

2. В чем состоит важность стандартизации средств передачи сообщений?

3. Что следует понимать под параллельной программой?

4. В чем различие понятий процесса и процессора?

5. Какой минимальный набор функций MPI позволяет начать разработку параллельных программ?

6. Как описываются передаваемые сообщения?

7. Как можно организовать прием сообщений от конкретных процессов?

8. Как определить время выполнения MPI программы?

9. В чем различие парных и коллективных операций передачи данных?

10. Какая функция MPI обеспечивает передачу данных от одного процесса всем процессам?

11. Что понимается под операцией редукции?

12. В каких ситуациях следует применять барьерную синхронизацию?

13. Какие режимы передачи данных поддерживаются в MPI?

14. Как организуется неблокирующий обмен данными в MPI?

15. В чем состоит понятие тупика? В каких ситуациях функция одновременного выполнения передачи и приема гарантирует отсутствие тупиковых ситуаций?

16. Какие коллективные операции передачи данных предусмотрены в MPI?

17. Что понимается под производным типом данных в MPI?

18. Какие способы конструирования типов имеются в MPI?

19. В каких ситуациях может быть полезна упаковка и распаковка данных?

20. Что понимается в MPI под коммуникатором?

21. Для чего может потребоваться создание новых коммуникаторов?

22. Что понимается в MPI под виртуальной топологией?

23. Какие виды топологий предусмотрены в MPI?

24. Для чего может оказаться полезным использование виртуальных топологий?

25. В чем состоят особенности разработки параллельных программ с использованием MPI на алгоритмическом языке Fortran?

26. Какие основные дополнительные возможности предусмотрены в стандарте MPI-2?
Принципы разработки параллельных методов:

1. В чем состоят исходные предположения для возможности применения рассмотренной в разделе методики разработки параллельных алгоритмов?

2. Каковы основные этапы проектирования и разработки методов параллельных вычислений?

3. Как определяется модель "подзадачи-сообщения"?

4. Как определяется модель "процессы-каналы"?

5. Какие основные требования должны быть обеспечены при разработке параллельных алгоритмов?

6. В чем состоят основные действия на этапе выделения подзадач?

7. Каковы основные действия на этапе определения информационных зависимостей?

8. В чем состоят основные действия на этапе масштабирования имеющегося набора подзадач?

9. В чем состоят основные действия на этапе распределения подзадач по процессорам вычислительной системы?

10. Как происходит динамическое управление распределением вычислительной нагрузки при помощи схемы "менеджер - исполнитель"?

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

12. Какой способ выполнения операции обобщенного сбора данных является более эффективным?
Параллельные численные алгоритмы для решения типовых задач вычислительной математики (матрично-векторное умножение):

1. Назовите основные способы распределения элементов матрицы между процессорами вычислительной системы.

2. В чем состоит постановка задачи умножения матрицы на вектор?

3. Какова вычислительная сложность последовательного алгоритма умножения матрицы на вектор?

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

5. Какие подходы могут быть предложены для разработки параллельных алгоритмов умножения матрицы на вектор?

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

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

8. Какой из представленных алгоритмов умножения матрицы на вектор обладает лучшими показателями ускорения и эффективности?

9. Может ли использование циклической схемы разделения данных повлиять на время работы каждого из представленных алгоритмов?

10. Какие информационные взаимодействия выполняются для алгоритмов при ленточной схеме разделения данных? В чем различие необходимых операций передачи данным при разделении матрицы по строкам и столбцам?

11. Какие информационные взаимодействия выполняются для блочного алгоритма умножения матрицы на вектор?

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

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

14. Какие функции библиотеки MPI оказались необходимыми при программной реализации алгоритмов?
Параллельные численные алгоритмы для решения типовых задач вычислительной математики (матричное умножение):

1. В чем состоит постановка задачи умножения матриц?

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

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

4. Какие способы разделения данных используются при разработке параллельных алгоритмов матричного умножения?

5. Представьте общие схемы рассмотренных параллельных алгоритмов умножения матриц.

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

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

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

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

10. Какой из рассмотренных алгоритмов характеризуется наименьшими и наибольшими требованиями к объему необходимой памяти?

11. Какой из рассмотренных алгоритмов обладает наилучшими показателями ускорения и эффективности?

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

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

14. Какие функции библиотеки MPI оказались необходимыми при программной реализации алгоритмов?
Параллельные численные алгоритмы для решения типовых задач вычислительной математики (решение систем линейных уравнений):
1. Что представляет собой система линейных уравнений? Какие типы систем вам известны? Какие методы могут быть использованы для решения систем разных типов?

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

3. В чем идея параллельной реализации метода Гаусса?

4. Какие информационные взаимодействия имеются между базовыми подзадачами для параллельного варианта метода Гаусса?

5. Какие показатели эффективности для параллельного варианта метода Гаусса?

6. В чем состоит схема программной реализации параллельного варианта метода Гаусса?

7. В чем состоит идея параллельной реализации метода сопряженных градиентов?

8. Какой из алгоритмов обладает большей коммуникационной сложностью?


Параллельные численные алгоритмы для решения типовых задач вычислительной математики (сортировка данных):
1. В чем состоит постановка задачи сортировки данных?

2. Приведите несколько примеров алгоритмов сортировки? Какова вычислительная сложность приведенных алгоритмов?

3. Какая операция является базовой для задачи сортировки данных?

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

5. Что представляет собой алгоритм чет-нечетной перестановки?

6. В чем состоит параллельный вариант алгоритма Шелла? Какие основные отличия этого варианта параллельного алгоритма сортировки от метода чет-нечетной перестановки?

7. Что представляет собой параллельный вариант алгоритма быстрой сортировки?

8. Что зависит от правильного выбора ведущего элемента для параллельного алгоритма быстрой сортировки?

9. Какие способы выбора ведущего элемента могут быть предложены?

10. Для каких топологий могут применяться рассмотренные алгоритмы сортировки?

11. В чем состоит алгоритм сортировки с использованием регулярного набора образцов?
Параллельные численные алгоритмы для решения типовых задач вычислительной математики (обработка графов):
1. Приведите определение графа. Какие основные способы используются для задания графов?

2. В чем состоит задача поиска всех кратчайших путей?

3. Приведите общую схему алгоритма Флойда. Какова трудоемкость алгоритма?

4. В чем состоит способ распараллеливания алгоритма Флойда?

5. В чем заключается задача нахождения минимального охватывающего дерева? Приведите пример использования задачи на практике.

6. Приведите общую схему алгоритма Прима. Какова трудоемкость алгоритма?

7. В чем состоит способ распараллеливания алгоритма Прима?

8. В чем отличие геометрических и комбинаторных методов разделения графа? Какие методы являются более предпочтительными? Почему?

9. Приведите описание метода покоординатного разбиения и алгоритма разделения с учетом связности. Какой из этих методов является более простым для реализации?
Параллельные численные алгоритмы для решения типовых задач вычислительной математики (уравнения в частных производных):
1. Как определяется задача Дирихле для уравнения Пуассона?

2. Как метод конечных разностей применяется для решения задачи Дирихле?

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

4. В чем состоит проблема синхронизации параллельных вычислений?

5. Как характеризуется поведение параллельных участков программы, которое именуется состязанием потоков (race condition)?

6. В чем состоит проблема взаимоблокировки?

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

8. Как изменяется объем вычислений при применении методов волновой обработки данных?

9. Что такое фрагментирование (chunking)?

10. Как повысить эффективность методов волновой обработки данных?

11. Как очередь заданий позволяет балансировать нагрузку процессорам?

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

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

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


Параллельные численные алгоритмы для решения типовых задач вычислительной математики (оптимизация):
1. В чем состоит задача поиска оптимального решения?

2. Что может являться целью в задаче поиска оптимального решения?

3. В чем состоит сложность определения оптимума в многоэкстремальных задачах оптимизации?

4. Какой подход к оценке оптимального решения использован в разделе? Какие еще подходы Вам известны?

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

6. Чем вызвана необходимость реализации асинхронной схемы расчетов в параллельной модификации индексного метода?



7. В чем состоит общая схема реализации программной системы параллельной глобальной оптимизации?



  1. Образовательные технологии.

    1. аудиторные занятия:

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

  • активные и интерактивные формы (семинары в диалоговом режиме по темам 1.1-3.2, компьютерное моделирование и практический анализ результатов, работа студенческих исследовательских групп)

    1. внеаудиторные занятия:

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

  • индивидуальные консультации.


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


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

      1. К.Ю.Богачев. Основы параллельного программирования. М.: Изд-во Бином, 2003.

      2. К.Ю.Богачев. Практикум на ЭВМ. Методы решения линейных систем и нахождения собственных значений. - 2-е изд., перераб. и дополн., Изд-во мех-мат. ф-та МГУ им. М.В.Ломоносова, 1999.

      3. Высокопроизводительные вычисления на кластерах: учебн. пособие/Под ред. А.В. Старченко.–Томск: изд-во Ттом. ун-та, 2008.

      4. В.П. Гергель, Р.Г. Стронгин. Основы параллельных вычислений для многопроцессорных вычислительных систем. Учебное пособие. Издательство Нижегородского госуниверситета. Нижний Новгород, 2003.

      5. Гергель, В.П., Стронгин, Р.Г. (2003, 2 изд.). Основы параллельных вычислений для многопроцессорных вычислительных систем. - Н.Новгород, ННГУ.


11.2 дополнительная литература:

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

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

      3. Таненбаум Э. (2002) . Архитектура компьютера. – СПб.: Питер.

      4. Quinn, M. J. (2004). Parallel Programming in C with MPI and OpenMP. – New York, NY: McGraw-Hill.

      5. Grama, A., Gupta, A., Kumar V. (2003, 2nd edn.). Introduction to Parallel Computing. – Harlow, England: Addison-Wesley.

      6. Pacheco, P. (1996). Parallel Programming with MPI. - Morgan Kaufmann.

      7. Chandra, R., Dagum, L., Kohr, D., Maydan, D., McDonald, J., and Melon, R. (2000). Parallel Programming in OpenMP. Morgan Kaufmann Publishers.

      8. Culler, D., Singh, J.P., Gupta, A. (1998) Parallel Computer Architecture: A Hardware/Software Approach. - Morgan Kaufmann.

      9. Tanenbaum, A. (2001). Modern Operating System. 2nd edn. – Prentice Hall (русский перевод Таненбаум Э. Современные операционные системы. – СПб.: Питер, 2002)


11.3 программное обеспечение и Интернет-ресурсы

      1. http://parallel.ru/

      2. http://computer.org/parascope/

      3. http://www.software.unn.ac.ru/ccam/mskurs/RUS/HTML/cs338_ppr_course.htm

      4. http://www.software.unn.ac.ru/ccam/files/HTML_Version/index.html




  1. Технические средства и материально-техническое обеспечение дисциплины

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