В курсе излагаются некоторые известные численные алгоритмы и рассматривается
круг вопросов, связанных с их распараллеливанием. Рассматриваются прямые методы
решения систем линейных алгебраических уравнений с матрицами как общего, так и
специального вида (метод исключения Гаусса, разложение Холецкого, метод
прогонки), итерационные методы решения систем линейных уравнений (методы простой
итерации и верхней релаксации, метод сопряженных градиентов), задачи разреженной
алгебры, методы параллельного решения систем обыкновенных дифференциальных
уравнений и дифференциальных уравнений в частных производных, методы
Монте-Карло.
Изучение проводится как на модельных, так и на прикладных задачах. Сведения,
необходимые для понимания существа задачи и выполнения лабораторных работ,
представлены в текстовых описаниях (там где требуется). При выполнении работ
активно используются инструменты пакета Intel Parallel Studio XE, поддерживающие
процесс создания параллельной программы, начиная с отладки и проверки
корректности и заканчивая оценкой эффективности и масштабируемости.
Курс рассчитан на преподавателей и научных сотрудников, а также аспирантов и
студентов высших учебных заведений. Курс предполагает наличие у читателя базовых
знаний и навыков структурного, модульного и объектно-ориентированного
программирования. В качестве базового языка рассматривается С/С++. Многие идеи
могут быть с успехом перенесены на другой язык, поддерживающий многопоточное
программирование, в частности Fortran. Длительность курса - не менее чем 32
часа. Итоговая аттестация проводится по результатам выполнения практических
заданий. При проведении занятий используются компьютерные презентации и
материалы для лабораторного практикума.
Курс разрабатывается в лаборатории «Информационные технологии» (ITLab)
факультета Вычислительной математики и кибернетики Нижегородского
государственного университета им. Н.И. Лобачевского в рамках программы развития
ННГУ как Национального исследовательского университета, а также при поддержке
компании Интел. По итогам разработки первой версии курса планируется издание
учебного пособия.
Элементы технологии Cilk Plus - (doc, ppt).
Содержание курса
Введение
(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. Числа с плавающей запятой и проблема их представления в памяти
компьютера
(в разработке...)
2.2. Представление чисел с плавающей запятой в соответствии со стандартом
IEEE-754
(в разработке...)
2.3. Погрешность вычислений, погрешность аппроксимации и методы их
уменьшения/контроля
(в разработке...)
2.4. Элементы аппроксимации математических функций
(в разработке...)
Практикум
Лабораторная работа 2.1. Элементарные расчетные алгоритмы. Проблемы,
ошибки, пути их устранения
(в разработке...)
Лабораторная работа 2.2. Параллельная сортировка вещественных чисел за
линейное время
(doc, ppt, исходные коды программ)
Лабораторная работа 2.3. Уменьшение погрешности вычисления скалярного
произведения векторов
(в разработке...)
Раздел 3. Прямые методы решения СЛАУ
3.1. Метод Гаусса для решения систем общего вида
(doc, раздел 3.1) (ppt)
3.2. Метод Холецкого для систем с симметричной положительно определенной
матрицей
(doc, раздел 3.2) (ppt)
3.3. Метод прогонки для систем с ленточной матрицей
(doc, раздел 3.3) (ppt)
3.4. Метод редукции для систем с ленточной матрицей
(в разработке...)
3.5. Методы решения систем с разреженной матрицей
(в разработке...)
Практикум
Лабораторная работа 3.1. Умножение разреженной матрицы на плотный
вектор. Распараллеливание циклов в OpenMP, TBB, ArBB, Cilk Plus
(doc, ppt, исходные коды программ)
Лабораторная работа 3.2. Алгоритмическая оптимизация в задачах алгебры
разреженных матриц на примере матричного умножения
(doc, ppt, исходные коды программ)
Лабораторная работа 3.3. Решение разреженных СЛАУ прямыми методами в
задаче распространения тепла в пластине. Использование MKL PARDISO
(в разработке...)
Лабораторная работа 3.4. Применение методов прогонки и редукции для
решения СЛАУ с ленточной матрицей на примере задачи вычисления цены составного
опциона
(в разработке...)
Раздел 4. Итерационные методы решения СЛАУ
Лекционные материалы
4.1. Метод простой итерации
(doc, раздел 4.1) (ppt)
4.2. Метод верхней релаксации
(doc, раздел 4.2) (ppt)
4.3. Метод сопряженных градиентов
(doc, раздел 4.3) (ppt)
Практикум
Лабораторная работа 4.1. Решение разреженных СЛАУ итерационными
методами в задаче распространения тепла в пластине
(в разработке...)
Раздел 5. Методы решения систем обыкновенных дифференциальных уравнений
Лекционные материалы
(в разработке...)
Практикум
Лабораторная работа 5.1. Интегрирование стохастического
дифференциального уравнения в задаче вычисления справедливой цены опциона
европейского типа
(в разработке...)
Лабораторная работа 5.2. Интегрирование системы дифференциальных
уравнений в задаче моделирования процессов в нейронной сети (моделирование
мозга)
(в разработке...)
Раздел 6. Методы решения дифференциальных уравнений в частных производных
Лекционные материалы
6.1. Решение волнового уравнения
(doc, раздел 6.1) (ppt)
6.2. Решение задачи теплопроводности
(doc, раздел 6.2) (ppt)
6.3. Решение задачи Дирихле для уравнения Пуассона
(doc, раздел 6.3) (ppt)
6.4. Решение с использованием БПФ
(в разработке...)
Практикум
Лабораторная работа 6.1. Решение дифференциальных уравнений в частных
производных на примере задачи вычисления справедливой цены составного опциона
(doc, ppt, исходные коды программ)
Лабораторная работа 6.2. Разработка, оптимизация и распараллеливание
быстрого преобразования Фурье в приложении к задаче фильтрации видео
(doc, ppt, исходные коды программ)
Лабораторная работа 6.3. Использование быстрого преобразования Фурье
для решения задачи распространения тепла в пластине
(в разработке...)
Раздел 7. Методы Монте-Карло
Лекционные материалы
7.1 Вычисление определенного интеграла
(doc, раздел 7.1) (ppt)
7.2 Способы уменьшения дисперсии
(ppt)
7.3 Генераторы псевдослучайных чисел
(ppt)
7.4 Подходы к распараллеливанию методов Монте-Карло
(ppt)
Практикум
Лабораторная работа 7.1. Параллельные методы Монте-Карло в задаче
вычисления справедливой цены опциона европейского типа
(doc, ppt, исходные коды программ)
Образовательные комплексы
