<?xml version="1.0" encoding="UTF-8"?>
<article article-type="research-article" dtd-version="1.3" xml:lang="ru" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:noNamespaceSchemaLocation="https://metafora.rcsi.science/xsd_files/journal3.xsd">
  <front>
    <journal-meta>
      <journal-id journal-id-type="publisher-id">moitvivt</journal-id>
      <journal-title-group>
        <journal-title xml:lang="ru">Моделирование, оптимизация и информационные технологии</journal-title>
        <trans-title-group xml:lang="en">
          <trans-title>Modeling, Optimization and Information Technology</trans-title>
        </trans-title-group>
      </journal-title-group>
      <issn pub-type="epub">2310-6018</issn>
      <publisher>
        <publisher-name>Издательство</publisher-name>
      </publisher>
    </journal-meta>
    <article-meta>
      <article-id pub-id-type="doi"/>
      <article-id pub-id-type="custom" custom-type="elpub">427</article-id>
      <title-group>
        <article-title xml:lang="ru">ИССЛЕДОВАНИЕ ВОЗМОЖНОСТЕЙ УСКОРЕНИЯ АЛГОРИТМОВ ПАРАЛЛЕЛЬНОЙ СОРТИРОВКИ RADIX НА GPGPU</article-title>
        <trans-title-group xml:lang="en">
          <trans-title>THE RESEARCH OF POSSIBILITIES OF ACCELERATION OF PARALLEL ALGORITHMS FOR RADIX SORTING ON GPGPU</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>Vorontsov</surname>
              <given-names>Gleb Vladimirovich</given-names>
            </name>
          </name-alternatives>
          <email>lomovivanvivt@yandex.ru</email>
          <xref ref-type="aff">aff-1</xref>
        </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>Preobrazhensky</surname>
              <given-names>Andrei Petrovich</given-names>
            </name>
          </name-alternatives>
          <email>app@vivt.ru</email>
          <xref ref-type="aff">aff-2</xref>
        </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>Choporov</surname>
              <given-names>Oleg Nikolaevich</given-names>
            </name>
          </name-alternatives>
          <email>choporov_oleg@mail.ru</email>
          <xref ref-type="aff">aff-3</xref>
        </contrib>
      </contrib-group>
      <aff-alternatives id="aff-1">
        <aff xml:lang="ru">Воронежский институт высоких технологий</aff>
        <aff xml:lang="en">Voronezh Institute of High Technologies</aff>
      </aff-alternatives>
      <aff-alternatives id="aff-2">
        <aff xml:lang="ru">Воронежский институт высоких технологий</aff>
        <aff xml:lang="en">Voronezh Institute of High Technologies</aff>
      </aff-alternatives>
      <aff-alternatives id="aff-3">
        <aff xml:lang="ru">Воронежский институт высоких технологий Воронежский государственный технический университет</aff>
        <aff xml:lang="en">Voronezh Institute of High Technologies Voronezh State Technical University</aff>
      </aff-alternatives>
      <pub-date pub-type="epub">
        <day>01</day>
        <month>01</month>
        <year>2026</year>
      </pub-date>
      <volume>1</volume>
      <issue>1</issue>
      <elocation-id>e427</elocation-id>
      <permissions>
        <copyright-statement>Copyright © Авторы, 2026</copyright-statement>
        <copyright-year>2026</copyright-year>
        <license license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/">
          <license-p>This work is licensed under a Creative Commons Attribution 4.0 International License</license-p>
        </license>
      </permissions>
      <self-uri xlink:href="https://moitvivt.ru/ru/journal/article?id=427"/>
      <abstract xml:lang="ru">
        <p>В данной работе проводится анализ алгоритма параллельной сортировки RADIX на графических процессорах (GPGPU). Вначале рассматривается наивный алгоритм поразрядной сортировки. При этом используются два вида поразрядной сортировки — по младшим и старшим разрядам. Приведен пример их использования. С тем, чтобы увеличить производительность алгоритма поразрядной сортировки предлагается использовать параллельное решение, хотя при этом возникают дополнительные проблемы, требующие своего решения. Анализируются возможные подходы по распараллеливанию, предложенные различными авторами. В рассматриваемом алгоритме данные хранятся в памяти графического процессора, и сортировка выполняется непосредственно на GPU. Этот алгоритм параллельной Radix сортировки состоит из 3-х подсистем: подсчет двоичных комбинаций в текущем разряде, префикс суммирование, окончательное соответствие ключей с вычисленными позициями. Первым шагом алгоритма является процесс подсчета частоты каждого элемента в последовательности. Для осуществления этого параллельным образом происходит разделение входного массива на блоки. Далее вычисляется локальная частота всех возможных элементов для каждого блока. Затем для каждой маски проводится префиксное суммирование. На следующем шаге получаются из локальных списков частот глобальные. Приведены результаты моделирования, продемонстрировавшие увеличение в несколько раз быстродействие предлагаемого алгоритма по сравнению с известными.</p>
      </abstract>
      <trans-abstract xml:lang="en">
        <p>This paper analyzes parallel RADIX sorting on GPGPU. First, they consider the naive&#13;
algorithm of radix sorting. It is indicated that using two types of radix sorting - at Junior and&#13;
senior level. Given an example of their use. In order to increase the performance of the radix&#13;
sorting algorithm is proposed to use a parallel solution, although this raises additional issues&#13;
that require resolution. Analyzes possible approaches for the parallelization proposed by&#13;
various authors. In the proposed algorithm the data is stored in GPU memory, and sorting is&#13;
performed directly on the GPU. This algorithm is a parallel Radix sort consists of 3&#13;
subsystems: counting binary combinations in the current category, prefix summing, the final&#13;
key according to the computed positions. The first step of the algorithm is the process of&#13;
counting the frequency of each element in the sequence. To have it done in a parallel way&#13;
there is a separation of the input array into blocks. It then computes the local frequency of all&#13;
possible elements for each block. Next, for each mask is the prefix summation. The next step is&#13;
to obtain from the local lists of the frequency of the global. Simulation results demonstrated&#13;
the increase of several times the performance of the proposed algorithm in comparison with&#13;
the known.</p>
      </trans-abstract>
      <kwd-group xml:lang="ru">
        <kwd>параллельная сортировка</kwd>
        <kwd>алгоритм</kwd>
        <kwd>данные</kwd>
        <kwd>процессор</kwd>
      </kwd-group>
      <kwd-group xml:lang="en">
        <kwd>parallel sorting</kwd>
        <kwd>algorithm</kwd>
        <kwd>data</kwd>
        <kwd>processor</kwd>
      </kwd-group>
      <funding-group>
        <funding-statement xml:lang="ru">Исследование выполнено без спонсорской поддержки.</funding-statement>
        <funding-statement xml:lang="en">The study was performed without external funding.</funding-statement>
      </funding-group>
    </article-meta>
  </front>
  <back>
    <ref-list>
      <title>References</title>
      <ref id="cit1">
        <label>1</label>
        <mixed-citation xml:lang="ru">Linh Ha Fast 4-way parallel radix sorting on GPUs / Ha Linh, Jens Kruger,&#13;
Claudio T.Silva [электронный ресурс]:&#13;
http://www.sci.utah.edu/~csilva/papers/cgf.pdf</mixed-citation>
      </ref>
      <ref id="cit2">
        <label>2</label>
        <mixed-citation xml:lang="ru">Wikipedia, Radix Sort [электронный ресурс]:&#13;
https://en.wikipedia.org/wiki/Radix_sort.</mixed-citation>
      </ref>
      <ref id="cit3">
        <label>3</label>
        <mixed-citation xml:lang="ru">Batcher K.Sorting Networks and Their Applications / K. Batcher&#13;
// Proceedings of the AFIPS Spring Joint Computing Conference, vol. 32,&#13;
1968, pp.307-314.</mixed-citation>
      </ref>
      <ref id="cit4">
        <label>4</label>
        <mixed-citation xml:lang="ru">Ajtai M. An 0(n log n) sorting network / M.Ajtai, J.Komlós, E.Szemerédi&#13;
//In: STOC ’83: Proceedings of the fifteenth annual ACM symposium on&#13;
Theory of computing, 1983, pp. 1– 9.&#13;
</mixed-citation>
      </ref>
      <ref id="cit5">
        <label>5</label>
        <mixed-citation xml:lang="ru">Leighton T. Tight bounds on the complexity of parallel sorting / T.Leighton&#13;
// In: STOC ’84: Proceedings of the sixteenth annual ACM symposium on&#13;
Theory of computing (New York, NY, USA, 1984), ACM, pp. 71–80.&#13;
</mixed-citation>
      </ref>
      <ref id="cit6">
        <label>6</label>
        <mixed-citation xml:lang="ru">Zagha M. Radix sort for vector multiprocessors / M.Zagha, G. E.Blelloch //&#13;
In: Supercomputing ’91: Proceedings of the 1991 ACM/IEEE conference on&#13;
Supercomputing (New York, NY, USA, 1991), pp. 712–721.&#13;
</mixed-citation>
      </ref>
      <ref id="cit7">
        <label>7</label>
        <mixed-citation xml:lang="ru">Kipfer P. UberFlow: a GPU-based particle engine / P.Kipfer, M.Segal,&#13;
R.Westermann // In: HWWS ’04: Proceedings of the ACM&#13;
SIGGRAPH/EUROGRAPHICS conference on Graphics hardware (New&#13;
York, NY, USA, 2004), ACM Press, pp. 115– 122.&#13;
</mixed-citation>
      </ref>
      <ref id="cit8">
        <label>8</label>
        <mixed-citation xml:lang="ru">Sintorn E. Fast parallel GPU-sorting using a hybrid algorithm / E.Sintorn,&#13;
U.Assarsson //In: Workshop on General Purpose Processing on Graphics Processing Units (GPGPU) (2007). [электронный ресурс]:&#13;
http://www.cse.chalmers.se/~uffe/hybridsort.pdf</mixed-citation>
      </ref>
      <ref id="cit9">
        <label>9</label>
        <mixed-citation xml:lang="ru">Sengupta S. Scan primitives for GPU computing / S.Sengupta, M.Harris,&#13;
Y.Zhang, J. D.Owens // In: Graphics Hardware 2007 (Aug. 2007), ACM, pp.&#13;
97–106.</mixed-citation>
      </ref>
      <ref id="cit10">
        <label>10</label>
        <mixed-citation xml:lang="ru">Harris M., Sengupta S., Owens J. D. Parallel prefix sum (scan) with cuda /&#13;
Harris M., Sengupta S., Owens J. D. // GPU Gems 3. Boston: Addison&#13;
Wesley, 2007. 851–876.</mixed-citation>
      </ref>
      <ref id="cit11">
        <label>11</label>
        <mixed-citation xml:lang="ru">Guy E. Blelloch Prefix Sums and Their Applications / Guy E. Blelloch //&#13;
[электронный ресурс]: https://www.cs.cmu.edu/~guyb/papers/Ble93.pdf.</mixed-citation>
      </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>