Исследование эффективности параллельного алгоритма Монте-Карло моделирования внутренних свободномолекулярных течений Хохлов И.А. 4-й курс Московский физико-технический институт (государственный университет) Кафедра компьютерного моделирования ФАЛТ Жуковский, 2008

2 Введение Актуальной проблемой математического моделирования является создание эффективных параллельных алгоритмов, реализующих метод Монте-Карло. Во многих случаях параллелизация алгоритма Монте-Карло выполняется путем разделения задачи на статистически независимые реализации с одинаковыми входными параметрами. Результаты таких реализаций суммируются, что дает возможность получить более точный результат за меньшее время. Фундаментальной проблемой программной реализации алгоритма Монте-Карло остается проблема эффективности алгоритма на конкретной аппаратно-программной платформе при различном соотношении затрат на обмен данными и затрат на получение этих данных. При изучении эффективности того или иного параллельного алгоритма этот вопрос часто остается недостаточно проясненным на фоне нечеткой балансировки вычислительной нагрузки на узлы многопроцессорной системы. Чтобы свести к минимуму этот фактор и изучить влияние особенностей платформы и библиотеки, в настоящей работе рассмотрена задача о свободномолекулярном внутреннем течении газа. Соответствующий алгоритм позволяет достигнуть практически идеального распределения нагрузки по параллельным процессам, оставляя возможность регулирования величины этой нагрузки и объема пересылаемых данных. Результат такого исследования актуален в контексте изучения эффективности MPI-алгоритмов на платформах с общей памятью (SMP).

3 Цель работы Исследование эффективности MPI- алгоритмов на платформах с общей памятью (SMP) Выявление влияния вычислительной архитектуры на эффективность параллельного алгоритма

4 План работы Применение метода Монте-Карло в динамике разреженного газа, особенности параллелизации его алгоритма на современных аппаратно-программных платформах Задача о взаимодействии тел в свободномолекулярном режиме, алгоритм метода Монте-Карло Исследование эффективности параллельного алгоритма

5 Метод Монте-Карло Метод Mонте-Карло – это численный метод моделирования широкого круга явлений и решения математических задач, связанный с получением и преобразованием случайных величин Схема методов Монте-Карло основана, во- первых, на получении так называемой стандартной случайной величины, т.е. случайной величины, равномерно распределенной в промежутке [0, 1]; во- вторых, на методах, с помощью которых реализации случайных величин с различными законами распределения выражаются через реализации стандартной случайной величины с равномерным законом распределения; в- третьих, задача метода Монте-Карло после получения ряда реализаций интересующей нас случайной величины заключается в получении некоторых сведений о ее распределении

6 Задача о взаимодействии тел 1. Задание параметров расчета: радиусов и температур тел 2. Задание начальных координат и скоростей частиц 3. Вычисление координат частицы при пролете за время min(tc,t) (tc - время до столкновения с ближайшим телом, t – шаг по времени), в случае столкновения суммирование переданного телу импульса 4. Вычисление скорости частицы после отражения от тела, суммирование реактивного импульса 5. Повторение пп. 3-4 для частицы до истеченияt (tc < t) 6. Повторение пп. 3-5 для всех частиц до истечения времени эволюции T=k t (k~1000) 7. Вычисление средних, запись результатов

7 Подходы к параллелизации Алгоритм параллельных статистически независимых испытаний (ПСНИ) Алгоритм параллелизации по данным (ППД) Алгоритм двухуровневой параллелизации со статической балансировкой (ДУП СБ) Алгоритм двухуровневой параллелизации с динамическим реаллокированием процессоров (ДУП ДБ)

Тестовая система Исследования проводились на вычислительном сервере кафедры компьютерного моделирования ФАЛТ МФТИ. Конфигурация сервера: 4 процессора Intel Itanium GHz (Madison), 8 GB DIMM DDR ECC, HDD 2xSCSI 73GB. Кэш-память L2 – 256 KB, L3 – 6 MB. На сервере установлена операционная система Red Hat Enterprise Linux 4, использовался компилятор GCC версии и библиотека LAM/MPI версии

9 Исследование эффективности На верхней диаграмме представлена зависимость скорости передачи пакета данных от объема передаваемых данных. На нижней диаграмме представлено относительное ускорение в зависимости от количества процессов (включая управляющий). Для и частиц ускорение больше теоретического, что обусловлено влиянием кэш-памяти процессора. Скачок скорости пересылки возможно связан с архитектурой процессора, или из-за реализации библиотеки MPI. Так же время расчета значительно уменьшается при использовании флагов оптимизации.

10 Выводы Алгоритм параллелизации по данным на SMP системе показал высокую эффективность, близкую к 100% (96% – 118%). При малом объеме задачи заметно влияние кэш- памяти процессора L2. Скорость передачи данных существенно зависит от объема передаваемых данных. Малые объемы информации передаются быстро, после определенного объема данных скорость передачи резко падает, после чего медленно растет по практически линейному закону. Оптимизация исполняемого кода программы под архитектуру вычислительной системы (использование флагов оптимизации компилятора) дает значительный прирост производительности (до 70%).