<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">intechngu</journal-id><journal-title-group><journal-title xml:lang="ru">Вестник НГУ. Серия: Информационные технологии</journal-title><trans-title-group xml:lang="en"><trans-title>Vestnik NSU. Series: Information Technologies</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">1818-7900</issn><issn pub-type="epub">2410-0420</issn><publisher><publisher-name>НГУ</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.25205/1818-7900-2019-17-1-82-89</article-id><article-id custom-type="elpub" pub-id-type="custom">intechngu-80</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>Статьи</subject></subj-group></article-categories><title-group><article-title>Оптимизация переупорядочивания модельных частиц при реализации метода частиц в ячейках на GPU</article-title><trans-title-group xml:lang="en"><trans-title>Reordering Optimization for GPU Implementation of Particle-in-Cell Method</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Романенко</surname><given-names>А. А.</given-names></name><name name-style="western" xml:lang="en"><surname>Romanenko</surname><given-names>A. A.</given-names></name></name-alternatives><email xlink:type="simple">arom@ccfit.nsu.ru</email><xref ref-type="aff" rid="aff-1"/></contrib><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Снытников</surname><given-names>А. В.</given-names></name><name name-style="western" xml:lang="en"><surname>Snytnikov</surname><given-names>A. V.</given-names></name></name-alternatives><email xlink:type="simple">snytav@ssd.sscc.ru</email><xref ref-type="aff" rid="aff-2"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>Новосибирский государственный университет</institution><country>Россия</country></aff><aff xml:lang="en"><institution>Novosibirsk State University</institution><country>Russian Federation</country></aff></aff-alternatives><aff-alternatives id="aff-2"><aff xml:lang="ru"><institution>Новосибирский государственный университет; Институт вычислительной математики и математической геофизики СО РАН</institution><country>Россия</country></aff><aff xml:lang="en"><institution>Novosibirsk State University; Institute of Computational Mathematics and Mathematical Geophysics SB RAS</institution><country>Russian Federation</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2019</year></pub-date><pub-date pub-type="epub"><day>30</day><month>10</month><year>2020</year></pub-date><volume>17</volume><issue>1</issue><fpage>82</fpage><lpage>89</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Романенко А.А., Снытников А.В., 2020</copyright-statement><copyright-year>2020</copyright-year><copyright-holder xml:lang="ru">Романенко А.А., Снытников А.В.</copyright-holder><copyright-holder xml:lang="en">Romanenko A.A., Snytnikov A.V.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://intechngu.elpub.ru/jour/article/view/80">https://intechngu.elpub.ru/jour/article/view/80</self-uri><abstract><p>Представлено описание реализации метода частиц в ячейках на GPU. Основным недостатком метода, с точки зрения затрат по времени, является функция переупорядочивания частиц между ячейками. Изложена оригинальная методика оптимизации данного этапа расчета, позволяющая избавиться от атомарных операций. Приведены результаты тестирования производительности на ряде современных графических процессоров.</p></abstract><trans-abstract xml:lang="en"><p>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 to speedup 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 buffer arrays, the number of arrays being equal to number of neighbour cells (26 for 3D case). Second, each neighbour cell copies the particles from the necessary array to her own particle array. Since the second operation is done in 26 threads independently with no synchronization, waiting and involves no critical sections, semaphores, mutexes, atomic operations etc. It results in the more than 10 times reduce of the reordering time compared to the straightforward reordering algorithm. Futhermore, we eliminate the 26 buffer arrays in the following way: the particles are just labeled instead of moving to buffer array. It enables to keep all the advantages with no memory wasted for buffer arrays.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>трехмерная модель</kwd><kwd>плазма</kwd><kwd>оптимизация</kwd></kwd-group><kwd-group xml:lang="en"><kwd>GPU</kwd><kwd>3D model</kwd><kwd>plasma</kwd><kwd>GPU</kwd><kwd>optimization</kwd></kwd-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Бэдсел Ч., Лэнгдон А. Физика плазмы и численное моделирование. М.: Энергоатомиздат, 1989.</mixed-citation><mixed-citation xml:lang="en">Бэдсел Ч., Лэнгдон А. Физика плазмы и численное моделирование. М.: Энергоатомиздат, 1989.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Birdsall C. K., Langdon A. Plasma Physics via Computer Simulation. CRC Press, 2004.</mixed-citation><mixed-citation xml:lang="en">Birdsall C. K., Langdon A. Plasma Physics via Computer Simulation. CRC Press, 2004.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Григорьев Ю. Н., Вшивков В. А., Федорук М. П. Численное моделирование методами частиц в ячейках. Новосибирск: Изд-во СО РАН, 2004.</mixed-citation><mixed-citation xml:lang="en">Григорьев Ю. Н., Вшивков В. А., Федорук М. П. Численное моделирование методами частиц в ячейках. Новосибирск: Изд-во СО РАН, 2004.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">Grigoryev Yu. N., Vshivkov V. A., Fedoruk M. P. Numerical Particle-in-Cell Methods. Theory and applications. Utrech, Boston, 2002.</mixed-citation><mixed-citation xml:lang="en">Grigoryev Yu. N., Vshivkov V. A., Fedoruk M. P. Numerical Particle-in-Cell Methods. Theory and applications. Utrech, Boston, 2002.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">Astrelin V. T., Burdakov A. V., Postupaev V. V. Generation of ion-acoustic waves and suppresion of heat transport during plasma heating by an electron beam. Plasma Physics Reports, 1998, vol. 24 (5), p. 414-425.</mixed-citation><mixed-citation xml:lang="en">Astrelin V. T., Burdakov A. V., Postupaev V. V. Generation of ion-acoustic waves and suppresion of heat transport during plasma heating by an electron beam. Plasma Physics Reports, 1998, vol. 24 (5), p. 414-425.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Боресков А. В., Харламов А. А. Основы работы с технологией CUDA. ДМК Пресс, 2010.</mixed-citation><mixed-citation xml:lang="en">Боресков А. В., Харламов А. А. Основы работы с технологией CUDA. ДМК Пресс, 2010.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">Burau H., Widera R., Hoenig W., Juckeland G., Debus A., Kluge T., Schramm U., Cowan T., Sauerbrey R., Bussmann M. PIConGPU: A Fully Relativistic Particle-in-Cell Code for a GPU Cluster. IEEE Transactions on Plasma Science, 2010, vol. 38, p. 2831-2839. DOI 10.1109/TPS.2010.2064310</mixed-citation><mixed-citation xml:lang="en">Burau H., Widera R., Hoenig W., Juckeland G., Debus A., Kluge T., Schramm U., Cowan T., Sauerbrey R., Bussmann M. PIConGPU: A Fully Relativistic Particle-in-Cell Code for a GPU Cluster. IEEE Transactions on Plasma Science, 2010, vol. 38, p. 2831-2839. DOI 10.1109/TPS.2010.2064310</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">Rossi F., Londrillo P., Sgattoni A., Sinigardi S., Turchetti G. Towards robust algorithms for current deposition and dynamic load-balancing in a GPU particle in cell code. In: AIP Conference Proceedings, 2012, vol. 1507, iss. 1, p. 184-192. DOI 10.1063/1.4773692</mixed-citation><mixed-citation xml:lang="en">Rossi F., Londrillo P., Sgattoni A., Sinigardi S., Turchetti G. Towards robust algorithms for current deposition and dynamic load-balancing in a GPU particle in cell code. In: AIP Conference Proceedings, 2012, vol. 1507, iss. 1, p. 184-192. DOI 10.1063/1.4773692</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">Kong X., Huang M., Ren Ch., Decyk V. Particle-in-cell simulations with charge-conserving current deposition on graphic processing units. Journal of Computational Physics, 2011, vol. 230, iss. 4, p. 1676-1685. DOI 10.1016/j.jcp.2010.11.032</mixed-citation><mixed-citation xml:lang="en">Kong X., Huang M., Ren Ch., Decyk V. Particle-in-cell simulations with charge-conserving current deposition on graphic processing units. Journal of Computational Physics, 2011, vol. 230, iss. 4, p. 1676-1685. DOI 10.1016/j.jcp.2010.11.032</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Rieke M., Trost T., Grauer R. Coupled Vlasov and two-fluid codes on GPUs. Journal of Computational Physics, 2015, vol. 283, p. 436-452. DOI 10.1016/j.jcp.2014.12.016</mixed-citation><mixed-citation xml:lang="en">Rieke M., Trost T., Grauer R. Coupled Vlasov and two-fluid codes on GPUs. Journal of Computational Physics, 2015, vol. 283, p. 436-452. DOI 10.1016/j.jcp.2014.12.016</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">Месяц Е. А., Снытников А. В., Лотов К. В. О выборе числа частиц в методе частиц-в-ячейках для моделирования задач физики плазмы // Вычислительные технологии, 2013. Т. 18, № 6. С. 83-96.</mixed-citation><mixed-citation xml:lang="en">Месяц Е. А., Снытников А. В., Лотов К. В. О выборе числа частиц в методе частиц-в-ячейках для моделирования задач физики плазмы // Вычислительные технологии, 2013. Т. 18, № 6. С. 83-96.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Lotov K. V., Timofeev I. V., Mesyats E. A., Snytnikov A. V., Vshivkov V. A. Note on quantitatively correct simulations of the kinetic beam-plasma instability. Physics of Plasmas, 2015, vol. 22, no. 2, p. 024502. DOI 10.1063/1.4907223.</mixed-citation><mixed-citation xml:lang="en">Lotov K. V., Timofeev I. V., Mesyats E. A., Snytnikov A. V., Vshivkov V. A. Note on quantitatively correct simulations of the kinetic beam-plasma instability. Physics of Plasmas, 2015, vol. 22, no. 2, p. 024502. DOI 10.1063/1.4907223.</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">Tskhakaya D., Schneider R. Optimization of PIC codes by improved memory management. Journal of Computational Physics, 2007, vol. 225, iss. 1, p. 829-839. DOI 10.1016/j.jcp. 2007.01.002.</mixed-citation><mixed-citation xml:lang="en">Tskhakaya D., Schneider R. Optimization of PIC codes by improved memory management. Journal of Computational Physics, 2007, vol. 225, iss. 1, p. 829-839. DOI 10.1016/j.jcp. 2007.01.002.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
