Параллельное программирование для ресурсоёмких задач численного моделирования в физике

Альтернативный курс для студентов 2 курса 
физического факультета МГУ им.

“Параллельное программирование для ресурсоёмких задач численного моделирования в физике”

Аннотация

Учебный курс для студентов физического факультета посвящен основным принципам, методам и технологиям параллельного программирования, ориентированных на решение ресурсоёмких физических задач. Студенты получат знания о современных высокопроизводительных вычислительных системах и практические навыки работы на них. Будут подробно разобраны такие популярные технологии параллельного программирования как OpenMP и MPI. Практические занятия будут проводиться на базе выделенного учебного кластера, содержащего 14 процессоров Intel Xeon. Завершающим этапом курса является работа над индивидуальным заданием, охватывающим весь материал курса. Курс открывает широкие возможности дальнейшего развития на переднем крае науки.

Введение

Современные научные и прикладные исследования в физике часто требуют проведения масштабных ресурсоемких вычислений. Стремительный рост производительности современных вычислительных систем достигается за счет использование параллельно работающих процессоров или многоядерных систем. Традиционные суперкомпьютеры с оригинальной архитектурой значительно повышают производительность вычислений, однако имеют существенный недостаток – большую цену, чем серьёзно уступают кластерным системам. При существенном снижении стоимости производительность кластерной системы в большом классе задач остается весьма высокой. Так, согласно последнему списку наиболее мощных компьютеров мира (www. top500.org, ноябрь 2009), восемьдесят три процента самых производительных вычислительных систем в мире выполнены по кластерной технологии с использованием стандартных вычислительных узлов.

В тоже время стандартный вычислительный узел уже давно не является однопроцессорной машиной, и эффективность использования многопроцессорной/многоядерной архитектуры для решения одной ресурсоемкой задачи зависит от применяемых средств разработки и методов распараллеливания. Технологией ставшей де-факто стандартной в научных ресурсоёмких приложениях является OpenMP, поддерживаемая всеми современными разработчиками компиляторов.

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

В перспективе использование кластера не ограничивается решением только локальных задач. В настоящее время активно создаются проблемно-ориентированные системные коллаборации с применением распределенных высоко­производительных вычислительных ресурсов ‑ ГРИДов.

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

Программа курса

1.  Обзор технологий параллельного программирования.

Два направления параллельного программирования: данные и алгоритм. Базовые принципы создания параллельных программ. Модели вычислений и методы анализа эффективности. Закон Амдала. Проблема использования алгоритмов параллельного программирования. Параллелизм, масштабируемость, локальность, модульность.

2.  Введение в архитектуру высокопроизводительных систем.

Принцип фон Неймана. Классификация параллельных компьютеров и систем. Архитектура компьютеров. Общая и распределенная память. Векторно-конвейерные суперкомпьютеры. Симметричные мультипроцессорные системы SMP. Системы с массовым параллелизмом (МРР). Кластерные системы. Технологии интерконнекта. Эволюция высокопроизводительных систем. Современное состояние, тенденции, прогнозы.

3.  Операционная система Linux.

Основы ОС Linux. Различия между Linux и другими операционными системами. Базовые концепции UNIX. Учетные записи. Shell и команды. Файловая система. Компиляция и выполнение программ. SSH. FTP. Использование редактора vi. Система X Window. Источники информации по Linux.

4.  Введение в технологии параллельного программирования.

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

5.  Технология OpenMP

Основные принципы, общая организация OpenMP. Структура параллельных программ. Основные конструкции и директивы OpenMP (parallel, do/for, sections, single). Директивные предложения. Переменные окружения и функции OpenMP. Синхронизация и дополнительные возможности. Рекомендации но настройке и отладке. Примеры программ: вычисление числа pi, вычисление определённого интеграла, варианты перемножения матриц. Обзор Intel Cluster OpenMP.

6.  Интерфейс передачи сообщений MPI.

Общая организация MPI. Терминология и обозначения. Привязка к языку. Типы данных. Базовые функции MPI. Коммуникационные операции типа точка-точка. Коллективные операции. Производные типы данных и передача упакованных данных. Операции с ком­муни­каторами и группами. Топология процессов. Реализации интерфейса передачи сооб­щений MPI. Примеры программ: вычисление числа pi, вычисление определённого интеграла, варианты перемножения матриц. Дополнительные инструменты в MPI-2.0: создание и управление процессами, односторонние взаимодействия, параллельный ввод/вывод.

7.  Параллельное программирование с использованием MPI для моделирования физических задач.

Параллельные численные алгоритмы для решения типовых задач физического моделиро­вания. Методы Монте-Карло. Точечные вычисления для моделирования систем взаимодействующих тел. Сеточные вычисления для приближенных решений дифференциальных уравнений в частных производных: задача Дирихле (явная разностная схема для уравнения Пуассона), решение краевой задачи методом Якоби. Матричные вычисления для решения систем линейных уравнений: параллельные алгоритмы решения систем линейных алгебраических уравнений методом Гаусса. Параллельная реализация преобразования Фурье.. Методы разработки параллельных программ для многопроцессорных систем с распреде­ленной памятью. Использован6ие библиотек подпрограмм для многопроцессорных вычислительных систем.

Темы практических и лабораторных занятий

1.  Введение в операционную систему Linux.

Вход в систему, сеанс работы, изменение пароля, тестовый редактор vi, структура файловой системы, имена файлов. Интерпретаторы команд (sh), встроенные команды, переменные окружения и выполнение командных файлов. Получение информации о выполняющихся процессах.

2.  Простые последовательные программы.

Написать и выполнить программу, выводящую на экран "Hello, world!". Написать и отладить одну из программ: перемножение матриц, вычисление числа Пи, численное интегрирование заданной функции, решение системы линейных уравнений методом Гаусса. Исследовать эффективность выполнения программы и возможности компилятора по ее оптимизации. Предложить различные методы распараллеливания программы, выбрать и обосновать наилучший метод для кластера.

3.  Общая структура параллельной программы. Базовые конструкции OpenMP.

Ознакомиться с примерами простейших программ, использующих OpenMP. Компиляция и запуск тестовых программ, последующий анализ их выполнения. Реализовать программу, в которой каждый поток выводит свой номер.

4.  Примеры использование средств OpenMP.

Написать программу расчета определённого интеграл с помощью средств OpenMP. Реализовать параллельный алгоритм решение краевой задачи методом Якоби.

5.  Общая структура параллельной программы. Базовые функции MPI.

Ознакомиться с примерами простейших программ, использующих MPI. Компиляция и запуск тестовых программ, последующий анализ их выполнения. Реализовать программу, в которой каждый процессор выводит свой номер в группе. Выдать разрешение таймера и определить время выполнения функции запроса времени. Определить, синхронизованы ли таймеры различных процессов системы.

6.  Коммуникационные операции типа точка-точка.

a.  Прием/передача сообщений с блокировкой.

Пинг-понг. Смоделировать обмен сообщениями между двумя процессами. Определить базовые характеристики коммуникационной сети кластера: латент­ность (время на передачу сообщения нулевой длины) и максимально достижимую пропускную способность (количество мегабайт в секунду; на сообщениях какой длины она достигается).

* Скалярное произведение распределенных между процессорами векторов. Сравнение эффективности реализации различных видов пересылок данных с блокировкой между двумя выделенными процессорами.

b.  Прием/передача сообщений без блокировки.

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

*Осуществить при помощи посылки сообщений типа точка-точка передачу данных: по кольцу ("эстафетная палочка" и "сдвиг" ), master-slave, от каждого каждому.

*Реализовать транспонирование матрицы с использованием неблокирующих операций.

7.  Коллективные взаимодействия процессов.

a.  Барьерная синхронизация.

Реализовать барьерную синхронизацию, проверить синхронизацию таймеров различных процессов системы.

*Моделирование синхронизации при помощи пересылок точка-точка и сравнение эффективности.

b.  Широковещательная рассылка, распределение и сбор данных.

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

c.  *Операции приведения и сканирования.

Смоделировать глобальное суммирование методом сдваивания и сравнить эффективность такой реализации с функцией MPI_Reduce.

8.  *Операции с группами процессов и коммуникаторами. Виртуальные топологии.

Создать две непересекающихся группы процессов и организовать обмен сообщениями через коммуникатор MPI_COMM_WORLD процессов с одинаковым рангом в этих группах.

Использовать двумерную декартову топологию процессов при реализации параллельного перемножения матриц.

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

a.  Пример реализации метода Монте-Карло.

b.  Параллельный алгоритм решение краевой задачи методом Якоби

c.  Задача Дирихле (Явная разностная схема для уравнения Пуассона).

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

методом Гаусса.

10.  Дополнительные инструменты в MPI-2.0: односторонние взаимодействия.

Заменить в написанных программах для прием/передача сообщений (пункт 6) двух точечные обмены односторонними коммуникациями.

11.  Дополнительные инструменты в MPI-2.0: создание и управление процессами.

Написать программу, которая принимает на вход число процессов, запускает на этом числе процессоров одну из написанных программ, получает от нее результат и выводит.

12.  Дополнительные инструменты в MPI-2.0: параллельный ввод/вывод

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

13.  Библиотеки подпрограмм для многопроцессорных вычислительных систем.

Примеры использования библиотек BLAS, LAPACK, ScaLAPACK

14.  Самостоятельная работа над индивидуальным заданием.

Примеры индивидуальных заданий

1.  Метод переменных направлений для решения краевой задачи для уравнения теплопроводности

2.  Метод Гаусса решения СЛАУ

3.  СЛАУ по формулам Крамера

4.  Решения обратной задачи для уравнения теплопроводности

5.  Система нелинейновзамодействующих осцилляторов

6.  Дифракция (Фурье преобразование)

7.  Деформируемое зеркало (уравнение Пуассон, СЛАУ)

8.  Рассеяние (Опыт Резерфорда, рассеяние в сильнодисперсной среде).

9.  Пористый кремний (Задача Перколяции)

10.  Факторизация целых чисел (Алгоритм Шермана-Лемана). Для задачи нахождения секретного ключа некоторых шифрсистем (например RSA).

11.  Гармонический осциллятор (Уравнении Шредингера, поиск собственных значений).

Список литературы:

1)  , Стесик программирование для многопроцессорных вычислительных систем. - СПб.: Петербург, 2002.

2)  , Воеводин Вл. В. Параллельные вычисления. - СПб: BHV, 2002.

3)  "Параллельное программирование с использованием технологии MPI", издательстве Московского университета 2004

4)  , , . Программирование многопроцессорных вычислительных систем. Ростов-на-Дону. Издательство , 2003, 208 с

5)  Калиткин методы. - М.: Наука, 1978. - 512 с

6)  “Параллельное программирование в MPI”, издательство "Регулярная и хаотическая динамика" 2003 г., - 303 стр.

7)  Эндрюс “Основы многопоточного, параллельного и распределенного программирования”, издательство "Вильямс" 2003 г.- 512 стр.

8)  “Основы параллельного программирования” издательство "Бином. Лаборатория знаний" 2003 г. - 342 стр.

9)  Воеводин  структуры алгоритмов и программ. - М.: ОВМ АН СССР, 1987. - 148с.

10)  http://parallel. ru