Параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики

В статье предложен параллельный алгоритм метода пробных частиц (МПЧ), который является разновидностью статистического метода Монте-Карло для решения задач динамики разреженного газа и молекулярной газовой динамики....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автор:	Печерица, Л.Л.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут технічної механіки НАН України і НКА України 2013
Назва видання:	Техническая механика
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/88374
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики / Л.Л. Печерица // Техническая механика. — 2013. — № 1. — С. 32-44. — Бібліогр.: 15 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-88374
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-883742025-02-23T19:46:37Z Параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики Печерица, Л.Л. В статье предложен параллельный алгоритм метода пробных частиц (МПЧ), который является разновидностью статистического метода Монте-Карло для решения задач динамики разреженного газа и молекулярной газовой динамики. У статті запропоновано паралельний алгоритм методу пробних часток (МПЧ), що є різновидом статистичного методу Монте-Карло для рішення задач динаміки розрідженого газу й молекулярної газової динаміки. The paper deals with the test particles method (TPM) as a version of the Monte-Carlo statistical method for different problems of the rarefied gas dynamics and molecular gas dynamics. 2013 Article Параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики / Л.Л. Печерица // Техническая механика. — 2013. — № 1. — С. 32-44. — Бібліогр.: 15 назв. — рос. 1561-9184 https://nasplib.isofts.kiev.ua/handle/123456789/88374 681.3:06/519.245+533.7 ru Техническая механика application/pdf Інститут технічної механіки НАН України і НКА України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	В статье предложен параллельный алгоритм метода пробных частиц (МПЧ), который является разновидностью статистического метода Монте-Карло для решения задач динамики разреженного газа и молекулярной газовой динамики.
format	Article
author	Печерица, Л.Л.
spellingShingle	Печерица, Л.Л. Параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики Техническая механика
author_facet	Печерица, Л.Л.
author_sort	Печерица, Л.Л.
title	Параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики
title_short	Параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики
title_full	Параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики
title_fullStr	Параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики
title_full_unstemmed	Параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики
title_sort	параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики
publisher	Інститут технічної механіки НАН України і НКА України
publishDate	2013
url	https://nasplib.isofts.kiev.ua/handle/123456789/88374
citation_txt	Параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики / Л.Л. Печерица // Техническая механика. — 2013. — № 1. — С. 32-44. — Бібліогр.: 15 назв. — рос.
series	Техническая механика
work_keys_str_mv	AT pečericall parallelʹnyjalgoritmmetodaprobnyhčasticdlârešeniâzadačmolekulârnojgazovojdinamiki
first_indexed	2025-11-24T20:03:33Z
last_indexed	2025-11-24T20:03:33Z
_version_	1849703387395784704
fulltext	УДК 681.3:06/519.245+533.7 Л.Л. ПЕЧЕРИЦА ПАРАЛЛЕЛЬНЫЙ АЛГОРИТМ МЕТОДА ПРОБНЫХ ЧАСТИЦ ДЛЯ РЕШЕНИЯ ЗАДАЧ МОЛЕКУЛЯРНОЙ ГАЗОВОЙ ДИНАМИКИ В статье предложен параллельный алгоритм метода пробных частиц (МПЧ), который является разно- видностью статистического метода Монте-Карло для решения задач динамики разреженного газа и моле- кулярной газовой динамики. Структура алгоритмов методов Монте-Карло представляет собой серию ста- тистических испытаний, что позволяет с высокой эффективностью осуществить параллелизацию процесса моделирования и значительно сократить время счета. Возможности параллелизации процесса вычислений наиболее исследованы для метода прямого моделирования Монте-Карло (ПММК). В результате анализа отличительных особенностей последовательных алгоритмов указанных методов, по аналогии с алгорит- мом параллельных статистических испытаний, ПММК выбран оптимальный путь параллелизации МПЧ. Показано, что специально организованный вычислительный процесс позволяет осуществить распаралле- ливание алгоритма МПЧ по крупным независимым подзадачам. Проведены предварительные тестовые расчеты для разработанного параллельного алгоритма МПЧ с использованием многоядерной ПЭВМ. Ре- зультаты расчетов газодинамических параметров, полученные для задачи внутреннего течения в сопле Лаваля с последующим расширением струи в окружающее пространство, сравнивались с результатами последовательного алгоритма МПЧ и параллельного алгоритма нестационарного метода ПММК для уста- новившегося течения. В результате анализа временных затрат для разных условий численного моделиро- вания установлено, что параллелизация алгоритма МПЧ дает возможность сокращения машинного време- ни соответственно количеству ядер (или процессоров), участвующих в расчетах. Для тестовой задачи при- ведена зависимость реального ускорения и эффективности параллельного алгоритма МПЧ от числа ис- пользуемых ядер многоядерного компьютера. Выполнено сравнение расчетных значений ускорения и эффективности с данными, соответствующими закону Амдала, и результатами численного эксперимента на суперкомпьютере массивно-параллельной архитектуры SPP-1600. Показано, что предложенный парал- лельный алгоритм МПЧ характеризуется высокой степенью эффективности и ускорения, поскольку вре- менные затраты на обменные процессы сведены к минимуму и все используемые ядра ПЭВМ задействова- ны равномерно. У статті запропоновано паралельний алгоритм методу пробних часток (МПЧ), що є різновидом ста- тистичного методу Монте-Карло для рішення задач динаміки розрідженого газу й молекулярної газової динаміки. Структура алгоритмів методів Монте-Карло представляє собою серію повторних розрахунків (статистичних випробувань), що дозволяє з досить високою ефективністю здійснити паралелізацію проце- су моделювання й значно скоротити час розрахунку. Можливості паралелізації процесу обчислень най- більш досліджені для методу прямого моделювання Монте-Карло (ПММК). У результаті аналізу відмінних рис послідовних алгоритмів зазначених методів, за аналогією з алгоритмом паралельних статистичних випробувань, ПММК обрано оптимальний шлях паралелізації МПЧ. Показано, що спеціально організова- ний обчислювальний процес дозволяє здійснити розпаралелювання алгоритму МПЧ по великим незалеж- ним підзадачам. Проведено попередні тестові розрахунки для розробленого паралельного алгоритму МПЧ із використанням багатоядерної ПЕОМ. Результати розрахунків газодинамічних параметрів, які отримані для задачі внутрішнього плину в соплі Лаваля з наступним розширенням струменя в навколишній простір, порівнювалися з результатами послідовного алгоритму МПЧ і паралельного алгоритму нестаціонарного методу ПММК для сталого плину. Внаслідок аналізу часових витрат для різних умов чисельного моделю- вання встановлено, що паралелізація алгоритму МПЧ дає можливість скорочення машинного часу відповідно до кількості ядер (або процесорів), що беруть участь у розрахунках. Для тестової задачі наведена залежність реального прискорення й ефективності паралельного алгоритму МПЧ від числа вико- ристовуваних ядер багатоядерного комп'ютера. Виконано порівняння розрахункових значень прискорення та ефективності з даними, що відповідають закону Амдала, та результатами чисельного експерименту на суперкомп'ютері массивно-паралельної архітектури SPP-1600. Показано, що запропонований паралельний алгоритм МПЧ характеризується високим ступенем ефективності й прискорення, оскільки часові витрати на обмінні процеси зведені до мінімуму й всі використовувані ядра ПЕОМ задіяні рівномірно. The paper deals with the test particles method (TPM) as a version of the Monte-Carlo statistical method for different problems of the rarefied gas dynamics and molecular gas dynamics. The structure algorithms of the Monte-Carlo methods presenting a series of repeat calculations (statistical tests) allow parallelization of simulation with a high efficiency and a significant reduction of machine time. It is found that the possibilities of parallelization of calculations are best studied using the Monte-Carlo direct simulation method (MCSSM). The research objective is to develop a parallel calculated algorithm of the TPM. An optimal method of the TPM parallelization is chosen analyzing special features of sequential algorithms of the above methods and studying the MCSSM parallel algorithms. It is shown that special calculations allow off-paralleling the TPM algorithm on large independent problems. The results of calculations of gas dynamical parameters for a problem of the Laval nozzle internal flow followed by the jet expansion in the environment are compared with the results of the TPM sequential algorithm and a parallel algorithm of the MCSSM non-steady method for a steady flow. The time expended for different conditions of a numerical simulation is analyzed. It is found that parallelization of the TPM  Л.Л. Печерица, 2013 Техн. механика. – 2013. – № 1. 32 algorithm allows reduction of machine time correspondingly the number of cores (or processors) participating in calculations. The dependency of a real acceleration and the efficiency of the TPM parallel algorithm on the used cores of a multi-core computer is presented for a test problem. Calculated values of the acceleration and the efficiency are compared with data conforming to the Amdal law and the results of a numerical experiment with the SPP-1600 massive parallel architecture computer. It is shown that the TPM parallel proposed algorithm is characterized by a high degree of the efficiency and the acceleration because the time expended for exchanged processes is held to a minimum and all used cores of a personal computer are evenly operational. Промежуточная область течений разреженного газа является до настоя- щего времени наименее исследованной. Строгое описание течений в таких областях может быть выполнено с привлечением уравнений Больцмана и На- вье–Стокса, решение которых связано с определенными математическими трудностями. Развиваемый в данной работе метод Монте-Карло является од- ним из наиболее распространенных численных статистических методов в ки- нетической теории разреженных газов. Его применение в области малых зна- чений чисел Кнудсена ( < 0,01) наталкивается на значительные трудно- сти, связанные с непомерно быстрым ростом необходимой памяти и расчет- ного времени ЭВМ. Эта проблема является общей для всех разработанных численных методов решения кинетических уравнений. Выходом из сложив- шейся ситуации может быть только уменьшение счетного времени и исполь- зуемых машинных ресурсов. Основным направлением повышения произво- дительности численного моделирования течений разреженного газа является параллелизация алгоритмов и их адаптация к архитектуре современных мас- сивно-параллельных компьютеров. Kn Рассматриваемый в данной работе метод пробных частиц (МПЧ) являет- ся развитием одной из разновидностей метода Монте-Карло в стационарной постановке – подхода В. И. Власова [1, 2]. При реализации МПЧ моделируе- мое физическое пространство разбивается на малые объемы с заданными границами, линейные размеры которых меньше местной длины свободного пробега молекул. Расчетные алгоритмы по реализации МПЧ сводятся к ос- реднению молекулярных признаков в соответствующих ячейках расчетного поля при большом времени слежения за их случайными блужданиями среди полевых молекул. Рассматриваемый метод был развит для свободномолеку- лярного течения и распространен на переходную область вплоть до сплош- носредной, где ячейки расчетной сетки должны быть достаточно малы и для обеспечения необходимой точности результатов требуется большое расчет- ное время. Поэтому возможность параллелизации процесса вычислений в МПЧ открывает дальнейшую перспективу его развития. Другой известной разновидностью метода Монте-Карло является разрабо- танный О. М. Белоцерковским и В. Е. Яницким [3, 4] подход реализации идей Г. Берда [5]. На его основе получены наиболее важные результаты решения сложных задач современной аэрогазодинамики. В методе прямого моделирова- ния Монте-Карло (ПММК) реальное течение газа моделируется достаточно большим числом разыгрываемых молекул. Метод ПММК использует принцип расщепления непрерывного процесса движения и столкновений молекул в раз- реженном газе на два последовательных независимых этапа на каждом малом временном шаге, величина которого во всей области должна быть меньше среднего времени между столкновениями молекул. Моделирование воспроиз- водит некоторый нестационарный процесс. Стационарное решение, если оно существует, достигается в результате процесса установления. Достижение не- обходимой точности моделирования требует осреднения по большому числу 33 временных шагов, количество которых зависит от числа моделирующих моле- кул и параметров задачи. Сравнительный анализ МПЧ и ПММК показывает определенную общ- ность в их реализации. Алгоритмы этих методов можно разбить на три ос- новных блока [6]: – обработка начальных данных, вычисление необходимых констант, об- нуление массивов, генерация расчетной сетки; – проведение необходимого количества статистических испытаний, про- граммно реализованных как тело цикла; – осреднение накапливаемой информации и ее обработка. Осреднение информации осуществляется по времени пребывания моле- кул в ячейках для МПЧ и по проведенной серии испытаний для ПММК. Ос- новные же отличия указанных алгоритмов заключаются во внутреннем со- держании второго блока: – в МПЧ каждое испытание включает генерацию частиц на границах об- ласти и слежение за их передвижением в пределах расчетной области. При моделировании движения молекул оцениваются времена пролета текущей ячейки, возможного столкновения молекул и отражения от преграды. В каче- стве реализованного выбирается то из перечисленных событий, время кото- рого минимально; – в методе ПММК процесс моделирования осуществляется по временным шагам и разделен на два этапа: первый – моделирование движения частиц независимо друг от друга и их индексацию по расчетным ячейкам, второй – моделирование процессов, происходящих в ячейке (межмолекулярные столк- новения и взаимодействие с границами физического пространства). Каждое испытание включает генерацию частиц на границах области, их передвиже- ние, переиндексацию и розыгрыш столкновений. Результаты последующих итераций (серий испытаний) обоих методов не коррелируют с результатами предыдущих. Независимость результатов расче- тов обеспечивается за счет автоматического сдвига генератора случайных чисел для каждого из проводимых испытаний. При моделировании методами Монте-Карло время вычислений пропор- ционально числу испытаний , в то время как их сходимость обратно пропор- циональна N N . Это свойство последовательных алгоритмов методов стати- стического моделирования приводит к существенному увеличению объемов вычислений. В то же время структура таких алгоритмов, представляющая со- бой серию повторных расчетов, позволяет с весьма высокой эффективностью осуществить параллелизацию процесса моделирования с использованием мно- гопроцессорных вычислительных систем. Возможности параллелизации процесса вычислений наиболее всего ис- следованы на методе ПММК. Группой ученых Санкт-Петербургского Инсти- тута высокопроизводительных вычислений и баз данных во главе с Г. А. Лукьяновым разработана общая методология высокопроизводительных вычислений с помощью ПММК на суперкомпьютерах различной архитекту- ры. На основе этой методологии решается задача выбора оптимального алго- ритма и соответствующей ему архитектуры вычислительной системы [6 – 10]. Коллективом российских ученых Отдела моделирования сложных стати- стических систем Центра перспективных исследований Санкт-Петербург- ского государственного политехнического университета разработан комплекс параллельных алгоритмов и программ, обеспечивающих высокую эффектив- 34 ность ПММК на суперкомпьютерах различной архитектуры. В комплекс ал- горитмов [11] входят: алгоритм параллельных статистически независимых испытаний (ПСНИ), алгоритм параллелизации по данным, алгоритм двух- уровневой параллелизации со статической балансировкой и алгоритм двух- уровневой параллелизации с динамической реаллокацией процессоров. Алгоритм ПСНИ [8] характеризуется предельно высокой степенью па- раллелизма, ускорения и эффективности по сравнению с любым другим па- раллельным алгоритмом ПММК нестационарных течений и относится к типу параллелизации по независимым подзадачам. Независимость отдельных не- стационарных реализаций ПММК позволяет выполнить их параллельно на разных процессорах. Применение ПСНИ на многопроцессорной системе при- водит к сокращению числа итераций внешнего цикла последовательного ал- горитма ПММК [6] для каждого отдельного процессора. Идея параллелиза- ции ПСНИ заключается в разделении серии независимых испытаний на групп (процессов), которые реализуются параллельно на N n p процессорах. При p = достигается максимальное значение ускорения и эффективности данно- го алгоритма. После инициализации программы порождаются параллель- ных процессов, каждый из которых получает свой уникальный в пределах задачи номер. Номер процесса определяет константу, на которую сдвигается генератор случайных чисел, а также номера частиц и ячеек, с которыми рабо- тает данный процесс. Для каждого процесса после выполнения блока подго- товки данных выполняется блок моделирования движения и столкновений молекул. Общее число итераций для системы из n n p процессоров – . Число итераций для каждого процесса N  nN . Обмен данными происходит только после завершения расчетов на всех процессорах. Обработка результатов ве- дется последовательно на одном процессоре. Параллельное программирование с помощью МПЧ – совершенно новое направление в развитии идей В. И. Власова. Схема последовательного алго- ритма МПЧ показана на рисунке 1. Анализ общности и отличий алгоритмов МПЧ и ПММК дают возможность попытки паралелизации МПЧ аналогично ПСНИ ПММК, но с учетом особенностей процесса блуждания пробных частиц на фоне полевых. Так как по сравнению с другими параллельными алгорит- мами ПММК алгоритм ПСНИ обладает хорошими характеристиками произ- водительности, то можно сделать положительный прогноз и в поведении со- ответствующих характеристик аналогичной параллелизации по независимым подзадачам для МПЧ. По аналогии с алгоритмом ПСНИ ПММК, паралелизация МПЧ по незави- симым подзадачам заключается в разделении серии испытаний на группы, каждая из которых реализуется параллельно на одном из N p процессоров. При этом ключевым моментом МПЧ является процесс хаотического блуждания пробных частиц на фоне полевых. Основная трудность при моделировании хаотического движения молекул заключается в правильном расчете свободного пробега пробной молекулы и выборе ее скорости после столкновения с полевой молекулой. В отличие от ПММК, где отдельные реализации являются незави- симыми друг от друга, в МПЧ траектории движения молекул косвенно зависят от движения молекул на предшествующих испытаниях. 35 Ввод начальных данных, задание геометрии преграды, считывание начального поля параметров 36 Нет Проверка условия вылета частицы за пределы расчетной области Расчет времени пролета t расчетной ячейки пр Расчет оставшегося времени пролета t =T -ст ст t до столкновения Расчет времени пролета перt до пересечения с поверхностью преграды Вычисление минимального времени t = min ( t , , t ) пр стt пер Блок свободного пролета Блок пересече- ния Блок столкновения Осреднение молекулярных признаков по времени; расчет распределенных и суммарных нагрузок Вывод результатов t = tпер t = tстt = t пр ispJ = +1 ispJ Количество испытаний ispJ > N Да Розыгрыш грани старта пробной частицы Розыгрыш координат старта zyx ,, пробной частицы Розыгрыш скорости старта пробной частицы   Определение номера текущей ячейки kjiN ,, Розыгрыш времени T до столкновения ст Рис. 1 При моделировании процесса блуждания в момент столкновения меняется не только скорость пробной молекулы в соответствующей пространственной ячейке, но и скорость полевой молекулы (скорость полевой молекулы после столкновения симметрична новой скорости пробной молекулы относительно плоскости, построенной на векторах скоростей пробной и полевой молекул до столкновения) [12]. Таким образом, в каждой группе испытаний, проводи- мых на одном из p процессоров, поле скоростей, на котором разыгрываются траектории движения пробных молекул, постоянно корректируется при каж- дом из столкновений. При таком моделировании движения молекул обеспе- чивается консервативность метода [13], частота столкновений пробной моле- кулы увеличивается вдвое, а суммарный импульс и энергия системы не ме- няются. При паралелизации по независимым подзадачам на каждом из реальных процессоров выполняется блок моделирования процесса движения, столкно- вений молекул, их отражения от обтекаемой поверхности и взаимодействие с границами физического пространства. При использовании для параллелиза- ции программного стандарта MPI с момента начала работы программы поро- ждаются параллельных процессов. При этом каждый процесс получает свой уникальный в пределах задачи номер, меняющийся от до 1 n 0 n 1 . Вы- полнение блока подготовки данных (ввод начальных данных, задание геомет- рии преграды, считывание начального поля параметров и их обработка) вы- полняется в рамках нулевого процесса на -м процессоре. Сформированные рабочие массивы и константы передаются на остальные процессоры, на кото- рых моделирование хаотического движения молекул осуществляется парал- лельно. После окончания моделирования все данные передаются на -й про- цессор, где и ведется обработка полученных результатов. Укрупненная схема алгоритма параллелизации по независимым подзадачам программы расчета МПЧ показана на рисунке 2. 1 Применение такого параллельного алгоритма приводит для каждого от- дельного процессора к сокращению числа итераций внешнего цикла последо- вательного алгоритма МПЧ (рисунок 1). Число испытаний в блоке моделиро- вания хаотического движения молекул для каждого процесса сокращается приблизительно в / n раз. Инициированные процессов перераспределя- ются по N n p процессорам. Область эффективного применения данного алго- ритма достигается при >>1 и >>N N p . Когда число инициированных про- цессов превышает количество реальных процессоров ( n > p ), определяется число необходимых виртуальных процессоров. Если <n p , то в вычисли- тельном процессе задействованы не все реальные процессоры. В случае n = p реализуемые процессы оптимальным образом используют все имеющиеся в наличии процессоры, равномерность загрузки которых зависит только от ко- личества проводимых на них испытаний и траекторий молекул, разыгрывае- мых на каждом из испытаний. 37 Порождение процессов n 38 . . . . . . . . . . . . . . . Ввод начальных данных, задание геометрии преграды, считывание начального поля пара- метров 1-м процессором Пересылка данных всем процессорам Блок моделирования хаотиче- ского движения молекул на 1-м процессоре Блок моделирования хаоти- ческого движения молекул на n -м процессоре Постановка 0 -го процесса на 1-й процессор . . . Пересылка данных 1-му процессору Осреднение по выборкам 1-м процессором Вывод результатов Завершение n процессов Постановка 1n -го процесса на n -й процессор Рис. 2 Независимость расчетов в рассмотренном ранее алгоритме ПСНИ ПММК обеспечивается за счет того, что генератор случайных чисел на каждом испы- тании стартует с разных точек (сдвигается на константу, определяемую но- мером инициированного процесса). В отличие от ПСНИ, при паралелизации по независимым подзадачам МПЧ независимость результатов расчетов обес- печивается следующим образом. Для всех порожденных процессов началь- ные номера граней, координаты старта и исходные скорости пробных моле- кул одинаковы (генератор случайных чисел стартует с одной точки). В про- цессе движения молекул в моменты столкновений и отражений от преграды разыгрываются по два равновероятных направления скорости, выбор которых обеспечивает независимость расчетов на разных процессорах. Остановимся на этом более детально. Вычисление скорости пробной молекулы после столкновения   произ- водится по формуле для столкновения упругих сфер [13], при этом два рав- новероятных направления   симметричны относительно плоскости, в кото- рой лежат скорости взаимодействующих пробной и полевой молекул: )( 2 1 egпол   , (1) где   – скорость пробной молекулы; пол  – скорость полевой молекулы; g – модуль относительной скорости молекул перед столкновением; e  – случай- ный вектор, равномерно распределенный на единичной сфере. Компоненты вектора выражаются через углы , e    сферической системы координат и случайные числа ( i =0,1...): iR  (2) .sinsin ;2;cossin ;21cos 1      z y x e Re Re Скорость пробной молекулы при ее отражении от поверхности обтекае- мого тела (преграды) соответствует диффузной схеме взаимодействия: 32ln2   RRRTw , (3) где – температура поверхности тела; wT R – газовая постоянная. Равновероятные направления скорости отражения симметричны отно- сительно внешней нормали к поверхности тела [13]: .sinsin ;sin;cossin ;2;cos 5 4            z y x R R (4) Независимость расчетных результатов при параллелизации по незави- симым подзадачам МПЧ обеспечивается выбором разных сочетаний симмет- ричных направлений указанных скоростей при 1-м, 2-м и т. д. столкновениях и отражениях. Выбор разных направлений скоростей обеспечивает различия в траекториях движения молекул для инициированных процессов. В зависимо- сти от номера процесса после очередного столкновения (или отражения) мо- 39 лекул в формулах (1) и (4) выбираются знаки + или –. Начальные траектории первого испытания для всех процессов одинаковы. При первом столкновении (или отражении) траектории молекул четных и нечетных процессов уже от- личаются друг от друга (1-й уровень разветвления по траекториям). При сле- дующем событии траектории совпадают только на каждом 4-м процессе (2-й уровень). На -том уровне траектории совпадают на процессах, номера ко- торых кратны k k2 . Алгоритм выбора направления скоростей в зависимости от номера про- цесса может быть различным. Один из возможных вариантов – введение мно- гоуровневых признаков процессов: – на 1-м уровне процессам присваиваются признаки 1 или 2 в соответст- вии с четностью их номеров. Процессам с четными признаками в формулах (1) и (4) ставится в соответствие знак +, нечетным признакам знак –; – на 2-м уровне процессам с признаком 1 поочередно дописываются цифры 1 или 2, т. е. присваиваются новые признаки 11 или 12. Процессам с признаком 2 поочередно присваиваются новые признаки 21 или 22. В зависи- мости от четности новых признаков выбираются знаки + или –; – на каждом последующем уровне ко всем предшествующим одинако- вым признакам процессов, как и ранее, поочередно дописываются цифры 1 или 2. Четность вновь полученных признаков является определяющей в вы- боре знаков в формулах скоростей. После того, как обеспечено отличие траекторий для всех инициирован- ных процессов, дальнейший выбор знаков в формулах (1) и (4) осуществляет- ся с вероятностью 0,5. Обычно расщепление по траекториям завершается уже на первых испытаниях. В связи с тем, что суммарное количество отражений и столкновений даже для небольшого числа испытаний достаточно велико, то ограничений на количество инициированных процессов практически нет, од- нако целесообразно, чтобы их количество не превышало количество реаль- ных процессоров ( n  p ). Для проведения тестирования параллельного алгоритма метода пробных молекул на многоядерном компьютере выбрана задача внутреннего течения в сопле Лаваля с последующим расширением струи в окружающее пространст- во. Результаты численного моделирования данного течения с помощью по- следовательного алгоритма МПЧ приведены в [14], а результаты параллели- зации ПММК по данным – в [7]. Условия течения соответствовали экспери- менту, изложенному ранее в работе [15]. Расчет с помощью МПЧ проводился в рамках осесимметричной задачи на равномерной прямоугольной сетке. Геометрия расчетной области, включающей сопло истечения и прилегающую к его выходному сечению область расширения, условия и алгоритм расчета подробно описаны в работе [14]. Данная задача является идеальной для тести- рования алгоритма МПЧ, поскольку размеры расчетной области позволяют при сравнительно небольшом количестве ячеек обеспечить в них хорошую статистику за счет переотражения молекул от стенок сопла. Линейный размер ячеек при этом не превосходит местную длину свободного пробега молекул для рассматриваемого режима истечения (число Кнудсена на срезе сопла ). aKn  3109  На рисунках 3 и 4 приведено сравнение изолиний чисел Маха M и отно- сительной плотности 0 параллельного алгоритма МПЧ (нижняя полу- плоскость) с соответствующими результатами ПММК [7] (верхняя полуплос- 40 кость). Изолинии строились в области с максимальными размерами 150 мм (60 ) и 100 мм (40 ). ar ar Моделирование ПММК проводилось с помощью алгоритма параллелиза- ции по данным на суперкомпьютере 8РР-1600. Эта вычислительная система содержит 8 процессоров, общий объем оперативной памяти 2 Гб, а пиковая производительность равна 1,6 GFLOPS (GFLOPS – 109 операций с плаваю- щей запятой в секунду). Схема используемого в расчетах параллельного ал- горитма ПММК подробно описана в [8], а детализация временных и сеточных параметров расчета ПММК – в [7]. При моделировании МПЧ [14] было проведено 4-е итерации. Шаг расчетной сетки по соответствующим осям составлял 0,15 мм и 0,2 мм. Число ячеек при таком разбиении расчетной области  8·104. Время счета 4-й ите- рации параллельного алгоритма МПЧ на 4-х ядерном однопроцессорном Рис. 4 Рис. 3 компьютере Intel Core 2 (Quad Q8400 2,66 GHz с памятью DDR2 4 GBytes PC2-6400 (400 MHz) 2x2048 Mbytes ASUS P5KPL-AM) составило 628, 315, 210 и 158 секунд расчетного времени на 1-м, 2-х, 3-х и 4-х ядрах соответст- венно (для распределенных поровну между ядрами 106 испытаний). Про- граммная поддержка стандарта MPI обеспечивалась с помощью компилятора Compaq Visual Fortran. При параллельных расчетах все процессы выполня- лись параллельно, каждый – на своем реальном процессоре. Осреднение ре- зультатов, полученных всеми задействованными процессами, осуществлялось по их количеству. Машинное время при использовании параллельного алго- ритма сокращается приблизительно во столько раз, сколько процессоров уча- ствуют в расчетах. Изолинии чисел Маха M и относительной плотности 0 на рисунках 3 и 4 с точностью до статистических погрешностей совпадают с данными по- следовательного моделирования [14]. Время счета последовательного алго- 41 ритма на Intel Core 2 составило 2772 с ≈ 46 минут. Поскольку в процессе счета последовательного алгоритма задействовано только одно ядро, на расчетное время влияют только быстродействие процессора и характери- стики оперативного запоминающего устройства, а реальное количество ядер компьютера не имеет значения. На рисунке 5 показана диаграмма, позволяющая сравнить времена счета параллельного алгоритма МПЧ с использованием стандарта MPI при реше- нии задачи о стационарном истечении газа в вакуум на одноядерной персо- нальной ПЭВМ Pentium-IV и 4-х ядерной ПЭВМ Intel Core 2. Приведенные на диаграмме времена счета соответствуют следующим расчетным вариан- там: 1. параллельный алгоритм на ПЭВМ Pentium-IV; 2. имитация параллельного алгоритма для 4-х процессов на Pentium-IV; 3. параллельный алгоритм на 1-м ядре ПЭВМ Intel Core 2; 4. параллельные расчеты на 2-х ядрах ПЭВМ Intel Core 2; 5. параллельные расчеты на 3-х ядрах ПЭВМ Intel Core 2; 6. параллельные расчеты на 4-х ядрах ПЭВМ Intel Core 2. время расчета Как показывает диаграмма, время счета зависит от характеристик ПЭВМ: переход от расчетов на Pentium-IV (Intel Pentium-IV 2400 MHz (BUS 533 MHz) 1024 MB (SDRAM PC–2100) к расчетам на Intel Core 2 сокращает вре- менные затраты примерно в 2,7 – 2,9 раза (сравнение вариантов 1 и 3). Из диаграммы видно, что время решения рассматриваемой задачи в слу- чае использования параллельного алгоритма с разделением на процессов, распределенных по реальным процессорам (варианты 4 – 6), примерно в раз меньше, чем в случае реализации алгоритма на одном ядре (вариант 3). Получить идеальное ускорение, равное , невозможно из-за затрат времени на обмен данными и т. д. Например, переход от расчетов на одном ядре (ва- риант 3) к расчетам на 4-х ядрах Intel Core 2 (вариант 6) сокращает время сче- та приблизительно в 4 раза. При имитации параллельного алгоритма для 4-х процессов на Pentium-IV (один процессор реальный, три – виртуальные, смотри вариант 2) время счета практически не меняется по сравнению со временем счета параллельного алгоритма на одном процессоре (вариант 1). n n n n Таким образом, при решении указанной задачи в результате перехода от одноядерной ПЭВМ Pentium-IV (вариант 1) к 4-х ядерной ПЭВМ Intel Core 2 (вариант 6) удалось добиться сокращения расчетного времени приблизитель- но в 10 раз. Было проведено сравнение временных затрат, требующихся для реализа- ции различных частей двух параллельных алгоритмов: МПЧ при расчете вариант расчета 1 2 3 4 5 6 1684 с 1636 c 628 с 315 с 210 с 158 с Рис. 5 42 внутреннего течения в сопле Лаваля на 4-х ядрах ПЭВМ Intel Core 2 ( =158 с) и ПММК при расчете свободного истечения газа в вакуум на 8-ми процессорном кластере Parsytec CC/16 ( = 652 с) [6]. Выявлено, что в обоих случаях доля параллельных вычислений от общего объема составила pT pT a ≈ 0,99, а временные составляющие параллельного счета, обмена данными и со- хранения информации малы и близки друг другу. Рис. 6 Рис. 7 Для параллельного алгоритма МПЧ зависимость ускорения ( = pS pS pTT1 , где – время работы параллельного алгоритма на одном про- цессоре; – время работы параллельного алгоритма на 1T pT p -процессорной вычислительной системе) от числа p используемых ядер ПЭВМ Intel Core 2 приведено на рисунке 6 (белые точки). Расчетные значения ускорения хорошо согласуются с приведенными на этом же рисунке теоретическими кривыми, соответствующими закону Амдала, и данными параллельного алго- ритма ПММК (черные точки), полученными на суперкомпьютере массивно- параллельной архитектуры SPP-1600 (8 процессоров) [10]. pS Эффективность параллельных вычислений =pE ))1((1 aa p  и оп- ределяет среднюю долю времени реализации алгоритма, в течение которого ядра (или процессоры) реально используются для решения задачи. Так как ≈ 0,99, то эффективность рассматриваемого параллельного алгоритма также близка к единице (при расчетах на 1, 2, 3, 4 - х ядрах 0,97, рисунок 7). a pE  Рассмотренная тестовая задача позволяет сравнить времена счета при пе- реходе от последовательного алгоритма МПЧ к параллельному. Анализ расчет- ных времен показал, что параллелизация дает возможность сокращения ма- шинного времени приблизительно во столько раз, сколько ядер (процессоров или компьютеров) участвуют в расчетах. Получить идеальное ускорение не- возможно из-за затрат времени на обмен данными и т. п. Предложенный парал- лельный алгоритм МПЧ построен таким образом, что временные затраты на обменные процессы сведены к минимуму, а все используемые ядра задейство- ваны равномерно. Поэтому разработанный алгоритм характеризуется высо- кой степенью эффективности и ускорения, что подтверждают рисунки 6 и 7. 1.Власов В. И. Улучшение метода статистических испытаний (Монте-Карло) для расчета течений разре- женных газов / В. И. Власов // Докл. АН СССР. – 1966. – Т. 167, № 5. – С. 1016 – 1018. 43 44 2. Власов В. И. Консервативный вариант метода пробных молекул (Монте-Карло) / В. И. Власов // Труды VIII Всесоюзной конф. по динамике разр. газов (Численные и аналитические методы в динамике разре- женных газов). – М., 1986. – С. 81 – 85. 3. Белоцерковский О. М. Статистический метод частиц в ячейках для решения задач динамики разреженно- го газа / О. М. Белоцерковский, В. Е. Яницкий // ЖВМиМФ. – 1975. – Т. 15. – С. 1195 – 1208. 4. Белоцерковский О. М. Прямое статистическое моделирование задач аэрогидродинамики / О. М. Белоцер- ковский, А. И. Ерофеев, В. Е. Яницкий. – Вычислительный центр АН СССР. – 1983. – 55 с. 5. Берд Г. Молекулярная газовая динамика / Г. Берд. – М. : Мир, 1981. – 319 с. 6. Быков Н. Ю. Параллельное прямое моделирование Монте-Карло нестационарных течений разреженного газа на суперкомпьютерах массивно-параллельной архитектуры в молекулярной газовой динамике / Н. Ю. Быков, Г. А. Лукьянов. – С.-Петербург, 1997.– 33 с. (Препринт / Ин-т Высокопроизводительных Вычислений и Баз Данных ; № 5-97). 7. Гришин И. А. Параллелизация по данным прямого моделирования Монте-Карло в молекулярной газовой динамике / И. А. Гришин, В. В. Захаров, Г. А. Лукьянов. – С.-Петербург, 1998.– 32 с. (Препринт / Ин-т Высокопроизводительных Вычислений и Баз Данных ; № 03-98). 8. Захаров В. В. Параллельные алгоритмы прямого моделирования Монте-Карло в молекулярной газовой динамике : методическое пособие для пользователей / В. В. Захаров, Г. А. Лукьянов, Г. О. Ханларов. – С.- Петербург : Ин-т Высокопроизводительных Вычислений и Баз Данных, 1999. – 46 с. 9. Алгоритмы двухуровневой параллелизации ПММК для решения нестационарных задач молекулярной газовой динамики / А. В. Богданов, Н. Ю. Быков, И. А. Гришин, В. В. Захаров, Г. А. Лукьянов, Гр. О. Ханларов // Математическое моделирование. – 2000. – Т. 12, № 6. – С. 97 – 101. 10. Захаров В. В. Параллельное прямое моделирование Монте-Карло течений разреженного газа на много- процессорных вычислительных системах различной архитектуры / В. В. Захаров, Г. А. Лукьянов // Тези- сы докладов 3-й Всероссийской молодежной школы "Суперкомпьютерные вычислительно- информационные технологии в физических и химических исследованиях", Черноголовка, 2001. – C. 42 – 46. 11. Суперкомпьютерные технологии прямого моделирования Монте-Карло в молекулярной газовой дина- мике. – Режим доступа к документу : http://www.spbcas.ru/mccc/parallel/parallel.htm. 12. Перепухов В. А. Применение метода Монте-Карло в динамике сильно разреженного газа / В. А. Перепухов // Динамика разреженного газа и молекулярная газовая динамика. – М. : ЦАГИ, 1972. – Вып. 1411. – С. 54 – 72. 13. Власов В. И. Расчет обтекания пластины под углом атаки потоком разреженного газа / В. И. Власов // Ученые записки ЦАГИ. – 1973. – Т. IV, № 1. – С. 17 – 24. 14. Басс В. П. Численное моделирование стационарного истечения струи двигателя малой тяги в вакуум / В. П. Басс, Л. Л. Печерица // Техническая механика. – 2011. – № 4. – С. 82 – 87. 15. Boyd I. D. Particle simulations of helium microthruster flows / I. D Boyd, Y. R. Jafry., J. V. Dtukel // J. of Spacecraft and Rockets. – 1994. – Vol. 31, N 2. – P. 271 – 277. Институт технической механики Получено 20.12.12, НАН Украины и ГКА Украины, в окончательном варианте 26.02.13 г. Днепропетровск

Параллельный алгоритм метода пробных частиц для решения задач молекулярной газовой динамики

Репозитарії

Схожі ресурси