НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ

КАФЕДРА ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ ТЕХНОЛОГИЙ

“УТВЕРЖДАЮ”

Декан

факультета прикладной математики

и информатики

«___ »______________2006 г.

РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ

ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ

ООП: 010500 – Прикладная математика и информатика; квалификация – магистр прикладной математики и информатики

Факультет Прикладной математики и информатики

Курс 1

Семестр 1

Лекции 18 часа

Лабораторные работы 18 часов

Индивидуальные занятия 36 часов

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

Экзамен 1 семестр

Всего 200 часов

Новосибирск

2006

Рабочая программа составлена на основании государственного образовательного стандарта по направлению 510200 «Прикладная математика и информатика», утвержденный приказом Министерства образования Российской федерации от 01.01.2001г. № 000 ен/маг.

Шифр дисциплины: ДВМ.02

Рабочая программа обсуждена на заседании кафедры Параллельных вычислительных технологий «25» апреля 2006 г. (протокол № 26)

Программу составил:

проф., д. ф.-м. н. _____________

Заведующий кафедрой ПВТ

проф., д. т.н. _____________

Ответственный за основную

образовательную программу

заведующий кафедрой ПМт _____________

1. Внешние требования

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

Таблица 1

Шифр дисциплины

Содержание учебной дисциплины

Часы

ДВМ.02

Параллельные вычислительные методы:

Основные понятия теории параллельных алгоритмов: распараллеливание алгоритмов сортировки, алгоритм сортировки Батчера; общие параллельные алгоритмы:

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

200

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

НЕ нашли? Не то? Что вы ищете?

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

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

7.1. Требования к профессиональной подготовленности магистра прикладной математики

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

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

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

§  умения:

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

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

-  обрабатывать полученные результаты, анализировать и осмысливать их с учетом имеющихся литературных данных;

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

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

2. Особенности (принципы) построения дисциплины

Таблица 2

Особенность (принцип)

Содержание

Основание для введения дисциплины в учебный план направления

Стандарт направления, решение ученого совета ФПМИ от 01.01.2001 № протокола 4.

Адресат дисциплины

Студенты по направлению:

010500 – Прикладная математика и информатика

Главная цель дисциплины

Формирование практических навыков реализации математических методов решения различных задач с помощью параллельных ЭВМ, оценки эффективности параллельного алгоритма.

Ядро дисциплины

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

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

Желательно знакомство с университетскими курсами по

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

Уровень требований по сравнению со Стандартом

Соответствует требованиям Стандарта

Объем дисциплины в часах

18 часов лекций, 18 часов лабораторных работ, 36 часов индивидуальных занятий, 128 часов самостоятельных занятий

Основные понятия дисциплины

Параллельные алгоритмы сортировки, линейной алгебры, ускорение и эффективность параллельного алгоритма

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

Дипломное проектирование

Практическая часть дисциплины

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

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

Обобщение, анализ, синтез, классификация, абстрагирование, моделирование, выделение главного.

Дисциплина и современные информационные технологии

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

3. Цели учебной дисциплины

Таблица 3

Номер цели

Содержание цели

Студент будет знать:

1

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

2

Параллельные алгоритмы сортировки чисел

3

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

4

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

5

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

6

Параллельный метод выполнения быстрого преобразования Фурье

7

Параллельные методы решения систем обыкновенных дифференциальных уравнений

8

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

10

Параллельные явные и неявные методы решения уравнения теплопроводности

Студент будет уметь:

11

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

12

Реализовывать разработанные алгоритмы с помощью языков программирования на параллельных ЭВМ.

13

Контролировать правильность полученных результатов

14

Оценивать точность полученного результата

15

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

4.Содержание и структура учебной дисциплины

Содержание учебной дисциплины

Лекционные занятия (18 часов)

Таблица 4

Ссылки на цели курса

Часы

Темы лекционных занятий

1, 2, 3, 11, 12, 13, 14, 15

2

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

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

1, 2, 3, 11, 12, 13, 14, 15

3

Алгоритм сортировки Батчера.

Определения компаратора, компараторной, сортирующей и объединяющей сетей. Определения битонической последовательности и битонического делителя. Теорема о битоническом делителе. Битонический алгоритм сортировки. Алгоритмы слияния Батчера сортировки Батчера. Время выполнения алгоритма.

1, 2, 3, 11, 12, 13, 14, 15

2

Общие параллельные алгоритмы.

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

4, 5,

11, 12, 13, 14, 15

6

Алгоритмы линейной алгебры.

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

Итерационный метод Якоби. Теорема о сходимости метода Якоби. Скорость сходимости метода. Метод верхней релаксации Якоби и его свойства. Теорема о сходимости метода верхней релаксации. Метод последовательной верхней релаксации.

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

Методы степенных рядов. Теорема о степенях нижней треугольной матрицы. Обратная матрица для треугольной матрицы.

Алгоритм Пана-Райфа вычисления обратной матрицы. Достаточно хорошая оценка для обратной матрицы. Теорема о сходимости степенного ряда к обратной матрице.

Нелинейные задачи. Сжимающее и псевдосжимающее отображения. Решение систем нелинейных уравнений. Метод Ньютона. Метод продолжения.

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

6, 11, 12, 13, 14, 15

5

Дискретное преобразование Фурье.

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

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

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

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

Лабораторные работы (18 часов)

Работа выполняются на параллельной вычислительной системе (кластер – 12 компьютеров Pentium 4, объединенных в общую вычислительную систему).

Таблица 5

Название лабораторной работы

Учебная деятельность

Часы

Ссылки на цели

Параллельные методы решения системы обыкновенных дифференциальных уравнений

·  сформулировать алгоритм параллельной реализации метода решения ОДУ;

·  разработать параллельную программу решения ОДУ;

·  найти ускорение параллельного алгоритма

·  оформить отчет и защитить

4

7, 11-15

Параллельные методы решения уравнения теплопроводности

·  сформулировать алгоритм параллельной реализации метода решения уравнения теплопроводности;

·  разработать параллельную программу решения уравнения теплопроводности;

·  найти ускорение параллельного алгоритма

·  оформить отчет и защитить

8

9, 11-15

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

·  сформулировать алгоритм параллельной реализации метода решения уравнения Пуассона;

·  разработать параллельную программу решения уравнения Пуассона;

·  найти ускорение параллельного алгоритма

·  оформить отчет и защитить

6

8, 11-15

Темы индивидуальных занятий (36 часов)

Таблица 6

Темы

Решая задачи, студент:

Часы

Ссылки на цели

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

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

12

7, 11-15

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

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

12

9, 11-15

Современные параллельные методы решения уравнения Пуассона

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

12

8, 11-15

5. Учебная деятельность

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

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

·  обзор методов решения параболических и гиперболических уравнений (20 часов),

·  обзор методов решения уравнения Пуассона (10 часов),

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

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

·  обзор параллельных методов решения уравнения Пуассона (18 часов),

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

6. Правила аттестации студентов по учебной дисциплине

Итоговый экзамен сдается письменно по билетам. К экзамену допускаются студенты, выполнившие все задания по лабораторным работам и индивидуальные работы. Оценка знаний и умений студентов проводится на основании ответов на поставленные вопросы. Студенту предлагается ответить на 2 вопроса из списка заданий по основным темам курса. Оценку «удовлетворительно» получает студент, усвоивший не менее 30% материала. Оценку «хорошо» получает студент, усвоивший не менее 60% материала. Оценку «отлично» получает студент, усвоивший не менее 80% материала.

7. Литература

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

, Корнеев программирование мультикомпьютеров. Изд-во НГТУ, 2006 г. , Вл. В. Воеводин. Параллельные вычисления. БХВ – Петербург2002. 609с. С. Немнюгин, О. Стесик. Параллельное программирование для многопроцессорных вычислительных систем. БХВ – Петербург, 2002. – 400 с. Гантмахер матриц. Физматлит, 2004 г. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979 г. Стулов по газовой динамике. Изд-во Физматлит, 2004 г. Гельфанд конечных разностей. Изд-во Комкнига, 2006 г. Параллельные ЭВМ. Архитектура, программирование и алгоритмы. - М.: Радио и связь, 1986. Ортега Дж. Введение в параллельные и векторные методы решения линейных систем. – М.: Мир, 1991. Вэйвлеты в обработке сигналов. Изд-во Мир, 2005 г. Корнеев руководство по параллельному программированию на вычислительной системе POWERXPLORER. – Новосибирск, 1997. – (Методическое пособие, Изд-во НГТУ; 1521) – 72 с. Малышкин параллельных вычислений. – Новосибирск, 1998. – (Методическое пособие, Изд-во НГТУ; ) – 55 с.

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

Последовательно-параллельные вычисления. - М.: Мир, 1985. Смит и анализ параллельных алгоритмов. Оксфорд, 1993.

8. Контролирующие материалы для аттестации

студентов по учебной дисциплине

Список заданий

1.  Запишите закон Амдала и назовите переменные

q =

q – f – p – k –

2.  Нарисуйте схему сортирующей сети и продемонстрируйте ее работоспособность на примере набора произвольного набора натуральных чисел, n = 5:

3.  Является ли последовательность битонической:

2 10 8 5 4 3 2 1 ДА НЕТ

8 7 6 5 6 1 2 3 ДА НЕТ

0 0 1 1 0 0 0 1 ДА НЕТ

1 0 0 0 0 0 0 1 ДА НЕТ

4.  Нарисуйте схему битонического делителя и продемонстрируйте ее работоспособность на примере набора произвольного набора из нулей и единиц, n = 6:

5.  Нарисуйте схему битонической сортирующей сети и продемонстрируйте ее работоспособность на примере произвольного набора натуральных чисел, n = 8:

6.  Количество операций:

-  Битонический делитель

-  Битоническая сортировка

-  Слияние Батчера

-  Сортировка Батчера

-  Нечетно-четное слияние

-  Модифицированная каскадная схема суммирования

7.  Проделайте подробно слияние Батчера для двух произвольных последовательностей натуральных чисел:

8.  Проделайте подробно нечетно-четное слияние для двух произвольных последовательностей натуральных чисел:

9.  Какой метод слияния эффективнее и почему?

10.  Найдите частичные суммы произвольной последовательности натуральных чисел:

11.  Для параллельных алгоритмов умножения матрицы на вектор напишите, используется ли конвейерность (да - нет) и количество операций:

да – нет

да – нет

да – нет

да – нет

12.  Шаг метода Якоби для двумерного уравнения Пуассона:

13.  Почему метод Якоби можно распараллелить?

14.  Какой метод декомпозиции применяется для этого?

15.  Запишите в матричной форме систему уравнений Ax=b для дискретного уравнения Пуассона с использованием красно-черного упорядочения:

16.  Запишите в матричной форме для этой системы уравнений метод Гаусса-Зейделя:

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

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

19.  Шаг метода Якоби для решения уравнения в матричном виде:

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

21.  Шаг метода верхней релаксации для решения уравнения в матричном виде:

22.  С какой целью в этом курсе изучаются понятия упорядочения и последовательного упорядочения матрицы?

23.  Определение связаных между собой чисел:

24.  Определение упорядочения:

25.  Определение последовательного упорядочения:

26.  Найти упорядочение (последовательное, если можно) и вектор последовательного упорядочения матриц: