ПРЕОБРАЗОВАНИЕ ПРОСТЕЙШИХ СОРТИРУЮЩИХ СЕТЕЙ К НЕЧЕТНО-ЧЕТНОЙ СЕТИ БАТЧЕРА
Аннотация
Все алгоритмы сортировки являются информационно-эквивалентными, поэтому выбор наи-
более эффективного алгоритма обычно зависит от скорости его работы и от количества ис-
пользуемой памяти. При параллельной, аппаратной реализации на эффективность алгоритмов
сортировки также влияют: степень утилизации аппаратных ресурсов; латентность результи-
рующей вычислительной структуры; количество и разрядность сортируемых элементов. Задача
сортировки или упорядочивания данных не формализована в виде математических преобразова-
ний, поэтому каждый из известных алгоритмов ее решения принято рассматривать как атомар-
ную, независимую единицу. Переход от одного алгоритма решения задачи к другому возможен при
описании задачи в виде информационного графа, вершины которого отражают элементарные
выполняемые операции, а дуги – информационные зависимости между ними. Имея набор элемен-
тарных преобразований, можно влиять на функциональную регулярность связей информационного
графа, латентность вычислительной структуры, коэффициент параллелизма и т.д. К преимуще-
ствам работы с информационным графом задачи также можно отнести сравнительную про-
стоту используемого понятийного аппарата. Информационный граф задачи сортировки «пузырь-
ком» представляет собой простейшую сортирующую сеть, построенную по принципу объедине-
ния ступеней «голова-хвост». В данной работе показана и обоснована функциональная избыточ-
ность подобных сортирующих сетей; приведены способы оптимизации числа операций и измене-
ния порядка их следования. Основным результатом работы является методика преобразования
сортирующих сетей в нечетно-четную сеть слияния Батчера. Разработана программа, автома-
тически выполняющая преобразование сортирующих сетей и позволяющая подстраивать тополо-
гию информационного графа под наиболее эффективный вид в зависимости от результирующей
степени параллелизма вычислительной структуры. Обобщая полученные результаты, можно
отметить, что автоматизированное приведение известных алгоритмов к «быстрым» может
обеспечить получение оптимальной параллельно-конвейерной программы при заданных ограниче-
ниях, что позволит значительно ускорить процесс их разработки.
Литература
Vol. 3. Sorting and Search]. 2nd ed.: transl. from engl. Moscow: Izd. dom «Vil'yams», 2001.
2. Skiena S.S. Algoritmy. Rukovodstvo po razrabotke [Algorithms. Development Guide]. 3rd ed.: transl.
from engl. Saint Petersburg: BKhV-Peterburg, 2022, 848 p.
3. Sorting algorithm. Available at: https://en.wikipedia.org/wiki/Sorting_algorithm (accessed 31 July 2024).
4. Timsort. Available at: https://en.wikipedia.org/wiki/Timsort (accessed 31 July 2024).
5. Quicksort. Available at: https://en.wikipedia.org/wiki/Quicksort (accessed 31 July 2024).
6. Alekseev K.N. Metody i sredstva sozdaniya parallel'no-konveyernykh programm dlya resheniya zadach
real'nogo vremeni na rekonfiguriruemykh vychislitel'nykh sistemakh: diss. ... kand. tekhn. nauk, po
spetsial'nosti 05.13.11 “Matematicheskoe i programmnoe obespechenie vychislitel'nykh mashin,
kompleksov i komp'yuternykh setey” [Methods and tools for creating parallel-pipeline programs for
solving real-time problems on reconfigurable computing systems: cand. of eng. sc. diss., in specialty
05.13.11 “Mathematical and software support for computing machines, complexes and computer networks”],
scientific supervisor: dr. of eng. sc., professor Levin I.I. Taganrog, 2020, 213 p.
7. Alekseev K.N., Levin I.I., Sorokin D.A. Strukturno-protsedurnaya realizatsiya na rekonfiguriruemykh
vychislitel'nykh sistemakh kodirovaniya Khaffmana v real'nom masshtabe vremeni [Structuralprocedural
implementation on reconfigurable computing systems of Huffman coding in real time],
Vestnik komp'yuternykh i informatsionnykh tekhnologiy [Bulletin of computer and information technologies],
2018, No. 9, pp. 3-10. ISSN 1810-7206. DOI: 10.14489/vkit.2018.09.pp.003-010. Available
at: http://www.vkit.ru/index.php//current-issue-rus/751-003-010.
8. Alekseev K.N., Sorokin D.A., Semernikova E.E. Strukturno-protsedurnaya realizatsiya kodirovaniya
algoritmom KHaffmana v zadachakh upravleniya [Structural and procedural implementation of coding
by the Huffman algorithm in control problems], Mater. 10-y Vserossiyskoy mul'tikonferentsii po
problemam upravleniya (MKPU-2017), 11-16 sentyabrya 2017 g. [Proceedings of the 10th All-
Russian Multiconference on Control Problems (MCCP-2017), September 11-16, 2017]. Rostov-on-
Don: Izd-vo YuFU, 2017, Vol. 3, pp. 126-127.
9. Dudnikov E.A., Alekseev K.N., Sorokin D.A. High-Speed Huffman encoding of dense data flows on
FPGA, German International Journal of Modern Science / Deutsche internationale Zeitschrift für
zeitgenössische Wissenschaft, 2021, No. 9, Vol. 1, pp. 36-40. Available at: https://dizzw.com/wpcontent/
uploads/2021/05/Deutsche-internationale-Zeitschrift-für-zeitgenössische-Wissenschaft-№9-
part-1-2021-37-41.pdf.
10. Kalyaev A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so strukturnoprotsedurnoy
organizatsiey vychisleniy [Modularly scalable multiprocessor systems with structuralprocedural
organization of computations]. Moscow: Yanus-K, 2003, 380 p.
11. Kalyaev I.A., Levin I.I., Semernikov E.A., Shmoylov V.I. Rekonfiguriruemye mul'tikonveyernye
vychislitel'nye struktury [Reconfigurable multipipeline computing structures]. 2nd ed., under the general
ed. of I.A. Kalyaeva. Rostov-on-Don: Izd-vo YuNTS RAN, 2009, 344 p. ISBN 978-5-902982-61-6.
12. Levin I.I., Alekseev K.N. Preobrazovanie sortiruyushchikh setey dlya raznoy stepeni parallelizma
[Transformation of sorting networks for different degrees of parallelism], Izvestiya YuFU.
Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2023, No.№ 5 (235), pp. 104-118.
DOI: 10.18522/2311-3103-2023-5-104-118.
13. Pisarenko I.V., Alekseev K.N., Mel'nikov A.K. Resursonezavisimoe predstavlenie sortiruyushchikh setey na
yazyke programmirovaniya Set@l [Resource-independent representation of sorting networks in the Set@l
programming language], Vestnik komp'yuternykh i informatsionnykh tekhnologiy [Bulletin of Computer and
Information Technologies], 2019, No. 11 (185), pp. 53-60. DOI: 10.14489/vkit.2019.11. pp.053-060. Available
at: http://vkit.ru/index. php/ current-issue-rus/857-053-060.
14. Pisarenko I.V., Kasarkin A.V., Alekseev K.N. Rekursivnoe opisanie grafov s assotsiativnymi
operatsiyami na yazyke programmirovaniya Set@l [Recursive Description of Graphs with Associative
Operations in the Set@l Programming Language], Vserossiyskaya nauchnaya konferentsiya
"Superkomp'yuternye tekhnologii (SKT) 2020", 05-10 oktyabrya 2020 g. Krym, Alushta, Rossiya [All-
Russian Scientific Conference "Supercomputer Technologies (SCT) 2020", October 5-10, 2020. Crimea,
Alushta, Russia]. Rostov-on-Don; Taganrog: Izd-vo YuFU, 2020, pp. 79-83.
15. Mikhaylov D.V. Metody sozdaniya parallel'no-konveyernykh programm dlya zadach s
posledovatel'nym informatsionnym grafom: diss. ... kand. tekhn. nauk po spetsial'nosti 05.13.11
“Matematicheskoe i programmnoe obespechenie vychislitel'nykh mashin, kompleksov i
komp'yuternykh setey” [Methods for creating parallel-pipeline programs for problems with a sequential
information graph:... cand. of eng. sc. diss. in specialty 05.13.11 “Mathematical and software support
for computing machines, complexes and computer networks”], scientific supervisor: dr. of eng.
sc., professor Levin I.I. Taganrog, 2022, 213 p.
16. Mikhaylov D.V. Metody sozdaniya parallel'no-konveyernykh programm dlya zadach s
posledovatel'nym informatsionnym grafom: diss. ... kand. tekhn. nauk po spetsial'nosti 05.13.11
“Matematicheskoe i programmnoe obespechenie vychislitel'nykh mashin, kompleksov i
komp'yuternykh setey” [Methods for creating parallel-pipeline programs for problems with a sequential
information graph:... cand. of eng. sc. diss. in specialty 05.13.11 “Mathematical and software support
for computing machines, complexes and computer networks”], scientific supervisor: dr. of eng.
sc., professor Levin I.I. Taganrog, 2022, 213 p.
17. Mikhaylov D.V. Preobrazovanie nekotorykh vidov posledovatel'nykh informatsionnykh grafov v
parallel'no-konveyernuyu formu [Transformation of Some Types of Sequential Information Graphs into
a Parallel-Pipeline Form], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences],
2020, No. 7 (217), pp. 78-93. DOI: 10.18522/2311-3103-2020-7-78-93.
18. Mikhaylov D.V. Preobrazovanie posledovatel'nogo informatsionnogo grafa metoda progonki v
parallel'nuyu formu [Transformation of the sequential information graph of the sweep method into a
parallel form] Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2021,
No. 7 (224), pp. 177-188. DOI: 10.18522/2311-3103-2021-7-177-188.
21. Batcher odd–even mergesort. Available at: https://en.wikipedia.org/wiki/Batcher_odd%E2%80%
93even_mergesort (accessed 31 July 2024).
19. Richard E. Blahut Fast Algorithms for Digital Signal Processing. Cambridge University Press,
05.2011. DOI: https://doi.org/10.1017/CBO9780511760921.
