В работе обобщается опыт коллектива авторов, полученный в ходе разработки учебных материалов и чтения курса лекций «Параллельные численные методы» в магистратуре ННГУ им. Н.И. Лобачевского. Показана актуальность разработки курса по данной тематике. Дается общая характеристика учебного плана магистратуры и места данного курса в плане обучения, сформулированы основные требования к обучаемым. Подробно описывается структура курса, демонстрируются методы организации практических и лабораторных занятий, способы оценивания результатов работ студентов. Полный комплект материалов курса выложен в открытый доступ на сайте НОЦ СКТ-Приволжье.
Об опыте разработки и чтения курса «Параллельные численные методы»* 2.2 Основные требования к обучаемым
Лекционная часть курса ориентирована на студентов магистратуры, обладающих знанием основ линейной алгебры и численных методов в объеме курсов, читаемых в бакалавриате факультетов естественнонаучного профиля.
Выполнение практических работ предполагает наличие у слушателей базовых навыков разработки программ на C/C++. Владение параллельным программированием на OpenMP, навыки работы с TBB и MKL, а также с другими компонентами пакета Intel Parallel Studio XE будут полезны при изучении курса, но не являются обязательным условием. Вся необходимая информация включена в материалы сопутствующего курса «Технологии параллельного программирования». 3. Структура курса лекций
Лекционная часть рассматривает области применения и основные возможности различных технологий параллельного программирования, а также вопросы построения и анализа эффективных параллельных алгоритмов из разных разделов численных методов. Лабораторный практикум начинается с изучения базовых возможностей технологий и современного инструментария при решении модельных задач и постепенно усложняется, охватывая широкий спектр параллельных алгоритмов, предназначенных для решения прикладных задач из разных предметных областей (физика, биология, финансы). Материалы курса содержат подробные описания и коды программ, позволяющие работать самостоятельно. Изложение сопровождается результатами вычислительных экспериментов и их кратким анализом.
Как уже было сказано, курс «Параллельные численные методы» читается одновременно с курсом «Технологии параллельного программирования». В рамках последнего студенты изучают современные технологии параллельного программирования в системах с общей (OpenMP, TBB, Cilk Plus) и распределенной (MPI) памятью, а также технологии программирования графических процессоров (NVidia CUDA). При выполнении практических заданий студенты работают с пакетом инструментов Intel Parallel Studio XE (Composer, Inspector, Amplifier). Данная комбинация курсов позволяет отделить алгоритмы от конкретной технологии их реализации и сделать основной акцент на алгоритмической части. Количество часов в курсе лекций может варьироваться в зависимости от целевой аудитории (от сокращенного варианта для чтения на молодежных школах до развернутого семестрового курса лекций для студентов магистратуры).
Ниже приведен список основных разделов курса «Параллельные численные методы» и дано их краткое содержание.
Элементы компьютерной арифметики. Раздел является опциональным. Темой раздела являются числа с плавающей запятой и проблема их представления в памяти компьютера. Студенты изучают представление чисел с плавающей запятой в соответствии со стандартом IEEE754. Обсуждаются проблемы накопления вычислительной погрешности и методы ее уменьшения/контроля. Приводятся типовые примеры, в которых накопление погрешности может привести к некорректным результатам вычислений.
Прямые методы решения СЛАУ. Данная часть курса посвящена рассмотрению прямых методов решения систем линейных алгебраических уравнений с матрицами как общего, так и специального вида: метод исключения Гаусса, разложение Холецкого, методы прогонки и редукции. Изложены классические варианты и даны оценки трудоемкости алгоритмов, показана их недостаточная эффективность при использовании современных вычислительных архитектур. Последовательно проводится идея блочной обработки данных.
Здесь же рассматриваются задачи разреженной алгебры. Дан краткий обзор структур хранения разреженных матриц, рассмотрены типовые проблемы, возникающие при реализации основных операций над разреженными матрицами. Проводится сравнение алгоритмов матрично-векторного и матричного умножения для случая плотных и разреженных матриц. В качестве примера более сложного вычислительного алгоритма для разреженных матриц рассмотрено разложение Холецкого. Показана проблема роста коэффициента заполнения матрицы при разложении, изложены алгоритмы переупорядочивания матрицы, снижающие заполнение результирующей матрицы (методы минимальной степени и вложенных сечений). Итерационные методы решения СЛАУ. В данной части рассмотрены итерационные методы решения систем линейных уравнений: от базовых методов (простой итерации, Якоби, Зейделя, верхней релаксации) до методов крыловского типа (обобщенный метод минимальных невязок, методы бисопряженных и сопряженных градиентов). Рассмотрены способы их распараллеливания, приведены теоретические и экспериментальные оценки ускорения, достигаемого за счет введения параллелизма. Одновременно рассматриваются и методы предобуславливания: базовые методы (Якоби, Гаусса-Зейделя) и методы, основанные на неполном LU-разложении (ILU(0) и ILU(p) факторизация).
Методы решения обыкновенных дифференциальных уравнений. Здесь студенты работают с основными методами решения ОДУ: семейство методов Рунге-Кутта и семейство методов Адамса. Рассматриваются параллельные варианты методов для решения систем ОДУ. Для методов Рунге-Кутта приведена схема конвейерного решения систем ОДУ с разреженной правой частью. В качестве иллюстративного примера рассматривается решение системы ОДУ, возникающей при моделировании системы нейронов.
Методы решения дифференциальных уравнений в частных производных. Затрагиваются вопросы параллельного решения дифференциальных уравнений в частных производных. Рассмотрены типовые уравнения в частных производных (гиперболического, параболического и эллиптического типов). В качестве метода сведения дифференциального уравнения к системе линейных алгебраических уравнений студентам рассказывается метод конечных разностей. Рассмотрены явные и неявные схемы решения уравнений параболического и гиперболического типов (последовательный и параллельный алгоритмы). Обсуждаются достоинства и недостатки каждого их подходов (условие Куранта). Отдельно обсуждается решение системы уравнений, возникающей в процессе решения задачи Дирихле для уравнения Пуассона. Изложена волновая схема обработки данных при параллельном решении данной СЛАУ итерационными методами.
Параллельные методы Монте-Карло. Заключительная часть посвящена численным методам Монте-Карло. Здесь слушатели знакомятся с проблемами, возникающими при использовании случайных чисел при решении задач методами Монте-Карло. Рассмотрены различные способы генерации псевдослучайных чисел, как последовательные, так и параллельные; обсуждаются вопросы безызбыточного распараллеливания метода. Типовым примером применения метода является задача многомерного интегрирования. 4. Проведение лабораторных занятий
Основной формой обучения является лекционная. Выполнение лабораторных работ проводится студентами самостоятельно. С целью организации контроля процесса выполнения лабораторных работ разработана система дистанционной проверки программ.
В системе выполняется автоматизированная проверка корректности сданных программ на наборе тестовых задач. Способ проверки корректности зависит от типа задачи. Например, для прямых методов решения СЛАУ выполняется проверка решения подстановкой, для методов решения дифференциальных уравнений проверяется соответствие поведения погрешности при увеличении размерности сетки теоретическим свойствам метода. Студенты выполняют последовательную реализацию метода на языке С++ и параллельные реализации с использованием технологий OpenMP, Intel Cilk Plus, Intel TBB. Эффективность параллельных реализаций проверяется путем сравнения ускорения относительно последовательной версии с пороговым значением, зависящим от задачи. Студенты загружают программы в систему через веб-интерфейс в виде набора файлов исходного кода и файла сборки для make. Система дистанционной проверки программ основана на свободно-распространяемой системы для проведения соревнований по спортивному программированию Ejudge (https://ejudge.ru/).
При выполнении лабораторных работ, самостоятельной работе и подготовке к зачету студенты имеют доступ к материалам курса, размещенным на сайте НОЦ СКТ-Приволжье [7] , режим доступа свободный. 4. Заключение
В данной публикации представлено описание курса лекций «Параллельные численные методы», читаемого в магистратуре института информационных технологий, математики и механики ННГУ им. Н.И. Лобачевского. Данный курс лекций был разработан в 2010 – 2012 годах при активной поддержке корпорации Intel. По итогам чтения курсов «Параллельные численные методы» и «Технологии параллельного программирования» (также при поддержке корпорации Intel) было издано учебное пособие в 4 томах [8]. Литература 1. Самарский А.А., Гулин А.В. Численные методы математической физики. М.: Научный мир, 2000. 2. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Бином. Лаборатория знаний, 2003. 7. http://hpc-education.unn.ru/обучение/курсы/магистратура On the experience of development and teaching the lecture course “Parallel numerical methods” in University of Nizhny Novgorod Konstantin Barkalov, Iosif Meyerov and Sergey Bastrakov Keywords: numerical methods, parallel algorithms, educational materials, lecture course This work summarizes experience of the authors obtained during development of educational materials and teaching the lecture course “Parallel numerical methods” in Master’s degree programme in Lobachevsky State University of Nizhny Novgorod. We demonstrate the relevance of developing the course on parallel numerical methods. General description of the Master’s curriculum and the position of this course in the curriculum as well as main requirements to students are given. We present methods of organizing practice and laboratory works and evaluation of student performance. References to the website of the Volga Research and Education Center for Supercomputing Technologies that contains all presented materials in free access are given.