Учебный курс "Параллельные численные методы"

Создать новую статью

21.07.2011 12:00


Учебный курс "Параллельные численные методы"

Нижегородский Государственный Университет имени Н.И. Лобачевского

Введение

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

Изучение проводится как на модельных, так и на прикладных задачах. Сведения, необходимые для понимания существа задачи и выполнения лабораторных работ, представлены в текстовых описаниях (там где требуется). При выполнении работ активно используются инструменты пакета Intel Parallel Studio XE, поддерживающие процесс создания параллельной программы, начиная с отладки и проверки корректности и заканчивая оценкой эффективности и масштабируемости.

Курс рассчитан на преподавателей и научных сотрудников, а также аспирантов и студентов высших учебных заведений. Курс предполагает наличие у читателя базовых знаний и навыков структурного, модульного и объектно-ориентированного программирования. В качестве базового языка рассматривается С/С++. Многие идеи могут быть с успехом перенесены на другой язык, поддерживающий многопоточное программирование, в частности Fortran. Длительность курса - не менее чем 32 часа. Итоговая аттестация проводится по результатам выполнения практических заданий. При проведении занятий используются компьютерные презентации и материалы для лабораторного практикума.

Курс разрабатывается в лаборатории «Информационные технологии» (ITLab) факультета Вычислительной математики и кибернетики Нижегородского государственного университета им. Н.И. Лобачевского в рамках программы развития ННГУ как Национального исследовательского университета, а также при поддержке компании Интел. По итогам разработки первой версии курса планируется издание учебного пособия.

Авторы курса

  • Баркалов Константин Александрович
  • Мееров Иосиф Борисович
  • Сысоев Александр Владимирович
  • Сиднев Алексей Александрович
  • Кустикова Валентина Дмитриевна
  • Козинов Евгений Александрович
  • Бастраков Сергей Иванович
  • Донченко Роман Владимирович
  • Малова Анна Юрьевна
  • Сафонова Яна Юрьевна

Содержание курса

Введение

(doc)

Раздел 1. Практикум «Введение в технологии параллельного программирования в системах с общей памятью. Инструменты пакета Intel Parallel Studio XE»

Цель раздела: краткий повтор/обзор технологий параллельного программирования в системах с общей памятью (OpenMP, TBB, Cilk Plus, ArBB) на основе выполнения лабораторных работ, обзор базовых возможностей пакета инструментов Intel Parallel Studio XE (Composer, Inspector, Amplifier).

Практикум

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

(doc, ppt, исходные коды программ)

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

(doc, ppt, исходные коды программ)

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

(doc, ppt, исходные коды программ)

Раздел 2. Элементы компьютерной арифметики

Лекционные материалы

2.1. Работа с числами в ЭВМ

(doc, раздел 2.1) (ppt)

2.2. Представление чисел с плавающей запятой в соответствии со стандартом IEEE-754

(doc, раздел 2.2) (ppt)

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

(doc, раздел 2.3) (ppt)

2.4. Элементы аппроксимации математических функций

(doc, раздел 2.4) (ppt)

Практикум

Лабораторная работа 2.1. Элементарные расчетные алгоритмы. Проблемы, ошибки, пути их устранения

(doc, ppt, исходные коды программ)

Лабораторная работа 2.2. Параллельная сортировка вещественных чисел за линейное время

(doc, ppt, исходные коды программ)

Лабораторная работа 2.3. Уменьшение погрешности вычисления сумм чисел с плавающей запятой

(doc, ppt, исходные коды программ)

Раздел 3. Прямые методы решения СЛАУ

3.1. Метод Гаусса для решения систем общего вида

(doc, раздел 3.1) (ppt)

3.2. Метод Холецкого для систем с симметричной положительно определенной матрицей

(doc, раздел 3.2) (ppt)

3.3. Метод прогонки для систем с ленточной матрицей

(doc, раздел 3.3) (ppt)

3.4. Метод редукции для систем с ленточной матрицей

(doc, раздел 3.4) (ppt)

3.5. Методы решения систем с разреженной матрицей

(doc, раздел 3.5) (ppt)

Практикум

Лабораторная работа 3.1. Умножение разреженной матрицы на плотный вектор. Распараллеливание циклов в OpenMP, TBB, ArBB, Cilk Plus

(doc, ppt, исходные коды программ)

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

(doc, ppt, исходные коды программ)

Лабораторная работа 3.3. Решение разреженных СЛАУ прямыми методами в задаче распространения тепла в пластине. Использование MKL PARDISO

(doc, ppt, исходные коды программ)

Лабораторная работа 3.4. Применение методов прогонки и редукции для решения СЛАУ с ленточной матрицей на примере задачи вычисления цены составного опциона

(doc, ppt, исходные коды программ)

Раздел 4. Итерационные методы решения СЛАУ

Лекционные материалы

4.1. Метод простой итерации

(doc, раздел 4.1) (ppt)

4.2. Метод верхней релаксации

(doc, раздел 4.2) (ppt)

4.3. Метод сопряженных градиентов

(doc, раздел 4.3) (ppt)

Практикум

Лабораторная работа 4.1. Решение разреженных СЛАУ итерационными методами в задаче распространения тепла в пластине

(doc, ppt, исходные коды программ)

Раздел 5. Методы решения систем обыкновенных дифференциальных уравнений

Лекционные материалы

(doc) (ppt)

Практикум

 

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

(doc, ppt, исходные коды программ)

Лабораторная работа 5.2. Интегрирование системы дифференциальных уравнений в задаче моделирования процессов в нейронной сети (моделирование мозга)

(doc, ppt, исходные коды программ)

Раздел 6. Методы решения дифференциальных уравнений в частных производных

Лекционные материалы

6.1. Решение волнового уравнения

(doc, раздел 6.1) (ppt)

6.2. Решение задачи теплопроводности

(doc, раздел 6.2) (ppt)

6.3. Решение задачи Дирихле для уравнения Пуассона

(doc, раздел 6.3) (ppt)

6.4. Решение с использованием БПФ

(doc, раздел 6.4) (ppt)

Практикум

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

(doc, ppt, исходные коды программ)

Лабораторная работа 6.2. Разработка, оптимизация и распараллеливание быстрого преобразования Фурье в приложении к задаче фильтрации видео

(doc, ppt, исходные коды программ)

Лабораторная работа 6.3. Использование быстрого преобразования Фурье для решения задачи распространения тепла в пластине

(doc, ppt, исходные коды программ)

Раздел 7. Методы Монте-Карло

Лекционные материалы

7.1 Вычисление определенного интеграла

(doc, раздел 7.1) (ppt)

7.2 Способы уменьшения дисперсии

(doc, раздел 7.2) (ppt)

7.3 Генераторы псевдослучайных чисел

(doc, раздел 7.3) (ppt)

7.4 Подходы к распараллеливанию методов Монте-Карло

(doc, раздел 7.4) (ppt)

Практикум

Лабораторная работа 7.1. Параллельные методы Монте-Карло в задаче вычисления справедливой цены опциона европейского типа

(doc, ppt, исходные коды программ)

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

Программное обеспечение к лабораторному практикуму

Каждая лабораторная работа содержит перечень необходимого для ее выполнения программного обеспечения. Здесь мы приведем полный список ПО, который потребуется для прохождения всех работ практикума.
  • Операционная система: Microsoft Windows XP и выше
  • Среда разработки: Microsoft Visual Studio 2008 и выше
  • Пакет Intel Parallel Studio XE
  • Аппаратные требования: желательна система с не менее чем 4-х ядерным процессором и не менее чем 4-мя GB RAM