Текущий выпуск Выпуск 3, 2018 Том 28

Особенности параллельной реализации метода частиц в ячейках

 pdf (182K)

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

Ключевые слова: оптимизация, GPU, графические процессоры, моделирование, PIC
Цитата: Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2018, т. 28, вып. 3, с. 419-426
DOI: 10.20537/vm180311

The peculiarities of the parallel implementation of Particle-In-Cell method

Particle-In-Cell (PIC) method is widely used for plasma simulation and the GPUs appear to be the most efficient way to run this method. In this work we propose a technique that enables one to speed up one of the most time-consuming operations in the GPU implementation of the PIC method. The operation is particle reordering, or redistribution of particles between cells, which is performed after pushing. The reordering operation provides data locality which is the key performance issue of the PIC method. We propose to divide the reordering into two stages. First, gather the particles that are going to leave a particular cell into arrays, the number of arrays being equal to the number of neighbor cells (26 for 3D case). Second, each neighbor cell copies the particles from the necessary array to its own particle array. The second operation is done in 26 threads independently with no synchronization or waiting and involves no critical sections, semaphores, mutexes, atomic operations etc. It results in the more than 10 times reduction of the reordering time compared to the straightforward reordering algorithm.

Keywords: optimization, GPU, simulation, PIC
Citation in English: Bulletin of Udmurt University. Mathematics, Mechanics, Computer Science, 2018, vol. 28, issue 3, pp. 419-426

Журнал индексируется в Scopus

Журнал входит в базы данных zbMATH, MathSciNet

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Журнал включен в перечень ВАК.

Электронная версия журнала на Общероссийском математическом портале Math-Net.Ru.

Журнал включен в Crossref