=Paper=
{{Paper
|id=Vol-1482/772
|storemode=property
|title=Об опыте разработки и чтения курса лекций «Параллельные численные методы»
(On the experience of development and teaching the lecture course "Parallel numerical methods" in University of Nizhny Novgorod)
|pdfUrl=https://ceur-ws.org/Vol-1482/772.pdf
|volume=Vol-1482
}}
==Об опыте разработки и чтения курса лекций «Параллельные численные методы»
(On the experience of development and teaching the lecture course "Parallel numerical methods" in University of Nizhny Novgorod)==
https://ceur-ws.org/Vol-1482/772.pdf
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Об опыте разработки и чтения курса «Параллельные чис-
ленные методы»*
К.А. Баркалов, И.Б. Мееров, С.И. Бастраков
Нижегородский государственный университет им. Н.И. Лобачевского
В работе обобщается опыт коллектива авторов, полученный в ходе разработки учеб-
ных материалов и чтения курса лекций «Параллельные численные методы» в магист-
ратуре ННГУ им. Н.И. Лобачевского. Показана актуальность разработки курса по
данной тематике. Дается общая характеристика учебного плана магистратуры и мес-
та данного курса в плане обучения, сформулированы основные требования к обучае-
мым. Подробно описывается структура курса, демонстрируются методы организации
практических и лабораторных занятий, способы оценивания результатов работ сту-
дентов. Полный комплект материалов курса выложен в открытый доступ на сайте
НОЦ СКТ-Приволжье.
1. Введение
К настоящему времени накоплено значительное количество учебной и учебно-
методической литературы по численным методам (см., например, последние издания классиче-
ских учебников [13]). Обычно в таких книгах рассматриваются вопросы построения, приме-
нения и теоретического обоснования алгоритмов приближенного решения различных классов
математических задач, и при этом недостаточно полно отражен вопрос отображения алгоритма
на архитектуру вычислительной системы. Указанный пробел в определенной степени воспол-
няется наличием переводной литературы (см., например, известные пособия [4–6]), в которых
данный вопрос рассмотрен достаточно подробно. Однако в этих книгах круг рассматриваемых
задач, в основном, ограничен задачами алгебры.
Одновременно с этим существует огромный объем материалов по современным технологи-
ям параллельного программирования (количество ссылок опубликованные пособия и интернет-
ресурсы здесь исчисляется сотнями). Обычно использование технологий в них рассматривается
на примерах относительно простых методов, которые не требуют предварительного изучения.
В силу сказанного актуальной является проблема разработки учебно-методических мате-
риалов, в которых совмещалось бы рассмотрение сложных параллельных алгоритмов и их реа-
лизация с использованием современных вычислительных технологий. Для решения указанной
задачи в ННГУ им. Н.И. Лобачевского были разработаны дополняющие друг друга курсы лек-
ций – «Параллельные численные методы» и «Технологии параллельного программирования».
В данной работе приведено описание первого из них.
2. Общая характеристика курса
2.1 Место курса в плане обучения магистрантов
Дисциплина «Параллельные численные методы» предназначена для студентов 1-го курса
магистратуры (10 семестр), обучающихся в институте информационных технологий, математи-
ки и механики ННГУ им. Н.И. Лобачевского по направлениям «Прикладная математика и ин-
форматика» и «Фундаментальная информатика и информационные технологии».
Целями освоения дисциплины «Параллельные численные методы» являются овладение
известными численными алгоритмами, а также рассмотрение круга вопросов, связанных с их
распараллеливанием.
*
Работа поддержана грантом МОН РФ (соглашение от 27 августа 2013 г. № 02.В.49.21.0003 между МОН
РФ и ННГУ ни. Н.И. Лобачевского).
772
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
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). Данная
комбинация курсов позволяет отделить алгоритмы от конкретной технологии их реализации и
сделать основной акцент на алгоритмической части. Количество часов в курсе лекций может
варьироваться в зависимости от целевой аудитории (от сокращенного варианта для чтения на
молодежных школах до развернутого семестрового курса лекций для студентов магистратуры).
Ниже приведен список основных разделов курса «Параллельные численные методы» и да-
но их краткое содержание.
Элементы компьютерной арифметики. Раздел является опциональным. Темой раздела яв-
ляются числа с плавающей запятой и проблема их представления в памяти компьютера. Сту-
денты изучают представление чисел с плавающей запятой в соответствии со стандартом IEEE-
754. Обсуждаются проблемы накопления вычислительной погрешности и методы ее уменьше-
ния/контроля. Приводятся типовые примеры, в которых накопление погрешности может при-
вести к некорректным результатам вычислений.
Прямые методы решения СЛАУ. Данная часть курса посвящена рассмотрению прямых ме-
тодов решения систем линейных алгебраических уравнений с матрицами как общего, так и
специального вида: метод исключения Гаусса, разложение Холецкого, методы прогонки и ре-
дукции. Изложены классические варианты и даны оценки трудоемкости алгоритмов, показана
их недостаточная эффективность при использовании современных вычислительных архитек-
тур. Последовательно проводится идея блочной обработки данных.
Здесь же рассматриваются задачи разреженной алгебры. Дан краткий обзор структур хра-
нения разреженных матриц, рассмотрены типовые проблемы, возникающие при реализации
основных операций над разреженными матрицами. Проводится сравнение алгоритмов матрич-
но-векторного и матричного умножения для случая плотных и разреженных матриц. В качестве
примера более сложного вычислительного алгоритма для разреженных матриц рассмотрено
разложение Холецкого. Показана проблема роста коэффициента заполнения матрицы при раз-
ложении, изложены алгоритмы переупорядочивания матрицы, снижающие заполнение резуль-
тирующей матрицы (методы минимальной степени и вложенных сечений).
773
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
Итерационные методы решения СЛАУ. В данной части рассмотрены итерационные мето-
ды решения систем линейных уравнений: от базовых методов (простой итерации, Якоби, Зей-
деля, верхней релаксации) до методов крыловского типа (обобщенный метод минимальных не-
вязок, методы бисопряженных и сопряженных градиентов). Рассмотрены способы их распарал-
леливания, приведены теоретические и экспериментальные оценки ускорения, достигаемого за
счет введения параллелизма. Одновременно рассматриваются и методы предобуславливания:
базовые методы (Якоби, Гаусса-Зейделя) и методы, основанные на неполном LU-разложении
(ILU(0) и ILU(p) факторизация).
Методы решения обыкновенных дифференциальных уравнений. Здесь студенты работают с
основными методами решения ОДУ: семейство методов Рунге-Кутта и семейство методов
Адамса. Рассматриваются параллельные варианты методов для решения систем ОДУ. Для ме-
тодов Рунге-Кутта приведена схема конвейерного решения систем ОДУ с разреженной правой
частью. В качестве иллюстративного примера рассматривается решение системы ОДУ, возни-
кающей при моделировании системы нейронов.
Методы решения дифференциальных уравнений в частных производных. Затрагиваются
вопросы параллельного решения дифференциальных уравнений в частных производных. Рас-
смотрены типовые уравнения в частных производных (гиперболического, параболического и
эллиптического типов). В качестве метода сведения дифференциального уравнения к системе
линейных алгебраических уравнений студентам рассказывается метод конечных разностей.
Рассмотрены явные и неявные схемы решения уравнений параболического и гиперболического
типов (последовательный и параллельный алгоритмы). Обсуждаются достоинства и недостатки
каждого их подходов (условие Куранта). Отдельно обсуждается решение системы уравнений,
возникающей в процессе решения задачи Дирихле для уравнения Пуассона. Изложена волновая
схема обработки данных при параллельном решении данной СЛАУ итерационными методами.
Параллельные методы Монте-Карло. Заключительная часть посвящена численным мето-
дам Монте-Карло. Здесь слушатели знакомятся с проблемами, возникающими при использова-
нии случайных чисел при решении задач методами Монте-Карло. Рассмотрены различные спо-
собы генерации псевдослучайных чисел, как последовательные, так и параллельные; обсужда-
ются вопросы безызбыточного распараллеливания метода. Типовым примером применения ме-
тода является задача многомерного интегрирования.
4. Проведение лабораторных занятий
Основной формой обучения является лекционная. Выполнение лабораторных работ прово-
дится студентами самостоятельно. С целью организации контроля процесса выполнения лабо-
раторных работ разработана система дистанционной проверки программ.
В системе выполняется автоматизированная проверка корректности сданных программ на
наборе тестовых задач. Способ проверки корректности зависит от типа задачи. Например, для
прямых методов решения СЛАУ выполняется проверка решения подстановкой, для методов
решения дифференциальных уравнений проверяется соответствие поведения погрешности при
увеличении размерности сетки теоретическим свойствам метода. Студенты выполняют после-
довательную реализацию метода на языке С++ и параллельные реализации с использованием
технологий OpenMP, Intel Cilk Plus, Intel TBB. Эффективность параллельных реализаций про-
веряется путем сравнения ускорения относительно последовательной версии с пороговым зна-
чением, зависящим от задачи. Студенты загружают программы в систему через веб-интерфейс
в виде набора файлов исходного кода и файла сборки для make. Система дистанционной про-
верки программ основана на свободно-распространяемой системы для проведения соревнова-
ний по спортивному программированию Ejudge (https://ejudge.ru/).
При выполнении лабораторных работ, самостоятельной работе и подготовке к зачету сту-
денты имеют доступ к материалам курса, размещенным на сайте НОЦ СКТ-Приволжье [7] ,
режим доступа свободный.
774
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
4. Заключение
В данной публикации представлено описание курса лекций «Параллельные численные ме-
тоды», читаемого в магистратуре института информационных технологий, математики и меха-
ники ННГУ им. Н.И. Лобачевского. Данный курс лекций был разработан в 2010 – 2012 годах
при активной поддержке корпорации Intel. По итогам чтения курсов «Параллельные численные
методы» и «Технологии параллельного программирования» (также при поддержке корпорации
Intel) было издано учебное пособие в 4 томах [8].
Литература
1. Самарский А.А., Гулин А.В. Численные методы математической физики. М.: Научный мир,
2000.
2. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Бином. Лаборатория
знаний, 2003.
3. Самарский А.А. Введение численные методы. СПб.: Лань, 2005.
4. Деммель Дж. Вычислительная линейная алгебра. Теория и приложения. М.: Мир, 2001.
5. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М.: Мир, 1999.
6. Саад Ю.. Итерационные методы для разреженных линейных систем. В 2-х томах. Том 1. М.:
Издательство Московского университета, 2013.
7. http://hpc-education.unn.ru/обучение/курсы/магистратура
8. Гергель В.П., Баркалов К.А., Мееров И.Б., Сысоев А.В., и др. Параллельные вычисления.
Технологии и численные методы: Учебное пособие в 4 томах. Н. Новгород: Изд-во
Нижегородского госуниверситета, 2013.
775
Суперкомпьютерные дни в России 2015 // Russian Supercomputing Days 2015 // RussianSCDays.org
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 labora-
tory 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.