A METHOD FOR SOLVING GRAPH NP-COMPLETE TASKS ON RECONFIGURABLE COMPUTER SYSTEMS BASED ON THE ITERATION PARALLELIZING PRINCIPLE
Abstract
When we solve graph NP-complete tasks on multiprocessor systems, the growth of hardware
resource does not lead to the proportional increase of the system performance, and hence, the task
solution time is not always reasonable. The aim of our research, given in the paper, is minimization
of the solution time of the task of maximal clique enumeration on reconfigurable computer
systems (RCS). When we solve tasks on RCSs with the help of the method of parallelizing by layers,
the growth of performance also slows down in spite of better scalability in comparison with
multiprocessor implementations. In the paper, we suggest a method of parallel-pipeline application
development for reconfigurable computer systems. The method is based on parallelizing bylayers for graph NP-complete tasks. We show that the bit representation of sets, which is used for
the method of parallelizing by layers, is not efficient for the method of parallelizing by iterations.
The new method has another organization of calculations; it processes unordered sets, whose
elements are accessed not by addresses (as in arrays), but by values (names of vertices and names
of edges of the graph). We show that the new method, based on parallelizing by iterations, provides
ramping of the RCS real performance at much larger computational resource in comparison
with the method of parallelizing by layers. Its specific performance is lower, because computing
substructures are to process more intermediate data due to symbolic representation of sets.
References
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.
