МЕТОД РЕШЕНИЯ ГРАФОВЫХ NP-ПОЛНЫХ ЗАДАЧ НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ НА ОСНОВЕ ПРИНЦИПА РАСПАРАЛЛЕЛИВАНИЯ ПО ИТЕРАЦИЯМ

  • А. В. Касаркин
Ключевые слова: Теория множеств, графовые NP-полные задачи, задача о клике, максимальные клики графа, реконфигурируемые вычислительные системы, программируемые логические интегральные схемы (ПЛИС), информационный граф, структурная реализация, конвейер, суперкомпьютеры

Аннотация

При решении графовых NP-полных задач на многопроцессорных системах рост обо-
рудования не приводит к пропорциональному росту производительности системы, поэто-
му не всегда удается решить задачу за приемлемое время. Целью работы, описанной в
статье, является минимизация времени решения задачи поиска максимальных клик графа с
использованием реконфигурируемых вычислительных систем (РВС). При решении задачи
на РВС методом распараллеливания по слоям рост производительности также замедля-
ется, несмотря на лучшую степень масштабируемости по сравнению с многопроцессор-
ными реализациями. В статье предложен метод создания параллельно-конвейерных про-
грамм для реконфигурируемых вычислительных систем на основе распараллеливания по
итерациям для решения графовых NP-полных задач. Рассмотрено, что использовать би-
товый способ представления множеств (как в методе распараллеливания по слоям) для
метода распараллеливания по итерациям не является эффективным. Новый метод отли-
чается организацией вычислений, а именно – обработкой неупорядоченных множеств,
доступ к элементам которых осуществляется не по адресам (как в массивах), а по значе-
ниям (именам вершин и именам дуг графа). Показано, что новый метод на основе распа-
раллеливания по итерациям, несмотря на более низкую удельную производительность, свя-
занную с тем, что вычислительным подструктурам из-за символьного представления
множеств необходимо обработать большее число промежуточных данных, обеспечивает
практически линейный рост реальной производительности РВС при значительно большем
количестве вычислительного ресурса по сравнению с методом распараллеливания по слоям.

Литература

1. Kir'yanov A.G., Lyahov A.I., Nekrasov P.O., Platov D.A. i dr. Protokol mnogoadresnoj
marshrutizacii Proximity-based Groupcast in MANET (GiM) [A multiaddress routing protocol
Proximity-based Groupcast in MANET (GiM)], Informacionnye process [Informatsionnyie
protsessy], 2012, No. 3, Vol. 12, pp. 213-228.
2. Kurejchik V.M., Glushan' V.M., Shcherbakov L.I. Kombinatornye apparatnye modeli i
algoritmy v SAPR [Combinatory hardware models and algorithms for CAD]. Moscow: Radio i
svyaz', 1990, 216 p.
3. Jens Clausen. Branch and bound algorithms principles and examples. Department of comp sc.,
university of Copenhagen, Universitetsparken 1, DK-2100 Corpenhagen, Denmark.(March 12,
1999).
4. Kiryushin N.K., Mikhalev I.V. Ispol'zovanie mnogoyadernykh uskoriteley dlya resheniya
zadachi propozitsional'noy vypolnimosti [Use of multicore accelerators for tasks of propositional
satisfiability], Problemy nauki [Problemy Nauki], 2017, No. 22 (104).
5. Dasari N.S., Ranjan D., Mohammad Z. Maximal Clique Enumeration for Large Graphs on
Hadoop Framework, Proc. of the First Workshop on Parallel Programming for Analytics Applications,
2014, pp. 21-30. Doi: 10.1145/2567634.2567640.
6. Rossi R.A., Gleich D.F., Gebremedhin A.H. Parallel Maximum clique Algorithms with Applications
to Network Analysis, SIAM J. Sci. Comput., 2015, Vol. 37, No. 5, pp. 589-616. Doi:
10.1137/14100018X.
7. Kovács L., Szabó G. Conceptualization with Incremental Bron-Kerbosch Algorithm in Big
Data Architecture, Acta Polytechnica Hungarica, 2016, Vol. 13, No. 2, pp. 139-158. Doi:
10.12700/aph.13.2.2016.2.8.
8. Pattabiraman B. et al. Fast Algorithms for the Maximum Clique Problem on Massive Graphs
with Applications to Overlapping Community Detection, Internet Mathematics, 2015, Vol. 11,
No. 4-5, pp. 421-448. Doi: 10.1080/15427951.2014.986778.
9. Dasari N.S., Zubair M., Ranjan D. A Novel Parallel Algorithm for Maximal Clique Enumeration
on Multicore and Distributed Memory Architectures. 10 р. Available at:
https://pdfs.semanticscholar.org/9827/9e2cedb14085886fcb4473f1ba483a3df195.pdf (accessed
23 September 2020).
10. Dasari N.S., Desh Z.M. pbitMCE: A bit-based approach for maximal clique enumeration on
multicore processors, in: Proc. 20th IEEE International Conference on Parallel and Distributed
Systems (ICPADS 2014), 2014, pp. 478-485. Doi: 10.1109/PADSW.2014.7097844.
11. Bron C., Kerbosch J. Algorithm 457: Finding All Cliques of an Undirected Graph, Comm of
ACM, 1973, Vol. 16, pp. 575-577.
12. Johnson D.J. and Trick M.A. Eds., Cliques, Coloring, and Satisfiability: Second DIMACS
Implementation Challenge, Workshop, October 11-13, 1993. Boston, MA, USA: American
Mathematical Society, 1996.
13. Moon J. and Moser L. On cliques in graphs, Israel Journal of Mathematics, 1965, Vol. 3,
No. 1, pp. 23-28. Available: Doi: 10.1007/BF02760024.
14. Kalyaev I.A. i dr. Rekonfiguriruemye mul'tikonveyernye vychislitel'nye struktury [Reconfigurable
multipipeline computing structures], under general ed. of I.A. Kalyaev. 2nd ed., revised
and enlarged. Rostov-on-Don: Izd-vo YUNTS RAN, 2009, 344 p.
15. Nauchno-issledovatel'skiy tsentr super-EVM i neyrokomp'yuterov [Scientific research center
of supercomputers and neurocomputers]. Available at: http://superevm.ru (accessed 23 September
2020).
16. Kalyaev A.V., Levin I.I. Modul'no-narashchivaemye mnogoprotsessornye sistemy so
strukturno-protsedurnoy organizatsiey vychisleniy [Modular-scalable multiprocessor systems
with structural and procedural organization of calculations]. Moscow: Yanus-K, 2003, 380 p.
17. Kasarkin A.V., Levin I.I. Strukturnaya realizatsiya zadachi nakhozhdeniya vsekh
maksimal'nykh klik grafa na rekonfiguriruemykh vychislitel'nykh sistemakh [Structural implementation
of the task of maximal clique enumeration on reconfigurable computer systems],
Vestnik komp'yuternykh i informatsionnykh tekhnologiy [Herald of computer and information
technologies], 2018, No. 10, pp. 3-10. Doi: 10.14489/vkit.2018.10.pp.003-010.
18. Kasarkin A.V., Levin I.I. Realizatsiya algoritma Brona-Kerbosha na rekonfiguriruemykh
vychislitel'nykh sistemakh [Implementation of the Bron-Kerbosch algorithm on reconfigurable
computer systems], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering sciences],
2019, No. 7 (209), pp. 142-152. Doi: 10.23683/2311-3103-2019-7-142-152.
19. Levin I., Dordopulo A., Fedorov A., Doronchenko Y. Design Technology for Reconfigurable
Computer Systems with Immersion Cooling. In: Voevodin V., Sobolev S. (eds.) Supercomputing.
RuSCDays 2018. Communications in Computer and Information Science, Vol 965.
Springer, Cham. Doi: 10.1007/978-3-030-05807-4_47.
20. Levin I.I., Pelipets A.V. Effektivnaya realizatsiya rasparallelivaniya na rekonfiguriruemykh
sistemakh [Efficient Parallel Execution on Reconfigurable Systems], Vestnik komp'yuternykh i
informatsionnykh tekhnologiy [Herald of computer and information technologies], 2018, No. 8,
pp. 11-16.
21. Kasarkin A.V., Levin I.I., Sorokin D.A. New iteration parallel-based method for solving graph NPcomplete
problems with reconfigurable computer systems, IOP Conf. Series: Materials Science and
Engineering, 2020, Vol. 919 (1), pp. 052007(1-7). Doi: 10.1088/1757-899X/919/5/052007.
Опубликован
2021-02-25
Выпуск
Раздел
РАЗДЕЛ III. РЕКОНФИГУРИРУЕМЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ