РЕАЛИЗАЦИЯ АЛГОРИТМА БРОНА-КЕРБОША НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ
Аннотация
Поиск максимальных клик графа является одной из фундаментальных проблем тео-рии графов и играет важную роль во многих приложениях. Задача о клике решается при анализе социальных сетей для обнаружения некоторого сообщества, в биоинформатике – для структурного выравнивания белка в трех измерениях, в САПР электрических схем – для размещения элементов и оптимизации. При этом данная задача является NP-полной, а это значит, что из-за ее высокой трудоемкости не всегда можно найти решение за приемле-мое время. Целью работы, описанной в статье, является минимизация времени решения задачи поиска максимальных клик графа с использованием реконфигурируемых вычисли-тельных систем (РВС). Предложен новый способ структурной реализации алгоритма Бро-на-Кербоша на РВС с применением оптимизации, помогающей в балансировке рабочей на-грузки между вычислительными ядрами и основанной на сортировке вершин по порядку вырождения. При реализации был выбран битовый способ представления множеств, когда позиция бита соответствует номеру элемента множества, а его значение является признаком присутствия либо отсутствия элемента во множестве. Выполнен анализ информационного графа одной итерации алгоритма и полного информационного графа всей задачи. Предложена вычислительная структура, реализующая информационный граф задачи на РВС с типом вычислений вложенный конвейер. Оценка скорости решения задачи на РВС выполнена на имитационной модели, которая моделирует выполнениеалгоритма так, как он будет исполняться на РВС. Результат работы модели представ-лен в том числе и в виде функций регрессии, которые отражают зависимость ускорения вычисления алгоритма от количества вычислительных узлов. Показано, что при решении задачи на многопроцессорной вычислительной системе при превышении определенного количества используемых процессорных ядер рост производительности практически не наблюдается, и дальнейшее уменьшение времени решения задачи становится невозможным. Однако при решении задачи на тех же графах на РВС рост производительности близок к линейному и, таким образом, увеличение аппаратных затрат приводит к почти линейному уменьшению времени решения задачи.
Литература
2. Zhang B., Park B.H., Karpinets T.V., and Samatova N.F. From pull-down data to protein inter-action networks and complexes with biological relevance, Bioinformatics, 2008, Vol. 24, No. 7, pp. 979-986.
3. Chen Z., Hendrix W., and Samatova N.F. Community-based anomaly detection in evolutionary networks, J. Intell. Inf. Syst., 2012, Vol. 39, No. 1, pp. 59-85.
4. Berry N., Ko T., Moy T., Smrcka J., Turn-ley J., and Wu B. Emergent Clique Formation in Terrorist Recruitmen, National Conference on Artificial Intelligence, 2004. Available: https://www.aaai.org/Papers/Workshops/2004/WS-04-02/WS04-02-005.pdf (accessed 02 Deсember 2019).
5. Sokolova O.D. Grafovye modeli dlya zadach funktsionirovaniya sovremennykh setey peredachi dannykh [Graph models for the problems of functioning of modern data transfer networks], Tr. 9-y Aziatskoy mezhdunarodnoy shkoly-seminara "Problemy optimizatsii slozhnykh sistem" [Proceedings of the 9th Asian international school-seminar "problems of op-timization of complex systems"]. Alma-Ata (Kazakhstan): 2013, pp. 314-318.
6. Kir'yanov A.G., Lyakhov A.I., Nekrasov P.O., Platov D.A. i dr. Protokol mnogoadresnoy marshrutizatsii Proximity-based Groupcast in MANET [Multicast routing Protocol Proximity-based Groupcast in MANET], Informatsionnye protsessy [Information process], 2012, K. 3, Vol. 12, pp. 213-228.
7. Yablonskiy G.S., Bykov V.I., Gorban' A.N. Kineticheskie modeli kataliticheskikh reaktsiy [Ki-netic models of catalytic reactions]. Novosibirsk: Nauka (Sib. otdelenie), 1983, 255 p.
8. Bron C., Kerbosch J. Algorithm 457: Finding All Cliques of an Undirected Graph, Comm of ACM, 1973, Vol. 16, pp. 575-577.
9. Moon J.W., Moser L. On Cliques in Graphs, Israel J. Math., 1965, Vol. 3, p. 23-28.
10. Tomita E., Tanaka A., Takahashi H. The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments, Theoretical Computer Science, 2006, Vol. 363, No. 1, pp. 28-42.
11. 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 Ap-plications, 2014, pp. 21-30.
12. Rossi R.A., Gleich D.F., Gebremedhin A.H. Parallel Maximumclique Algorithms with Appli-cations to Network Analysis, SIAM J. Sci. Comput., 2015, Vol. 37, No. 5, pp. 589-616.
13. 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.
14. Dasari N.S., Zubair M., Ranjan D.A Novel Parallel Algorithm for Maximal Clique Enumera-tion on Multicore and Distributed Memory Architectures, 10 р. Available at: https://pdfs.semanticscholar.org/9827/9e2cedb14085886fcb4473f1ba483a3df195.pdf (ac-cessed 02 December 2019).
15. 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.
16. Levin I.I. i dr. Sovremennye i perspektivnye vysokoproizvoditel'nye vychislitel'nye sistemy s rekonfiguriruemoy arkhitekturoy [Modern and promising high-performance computing systems with reconfigurable architecture], Vestnik Yuzhno-Ural'skogo gosudarstvennogo universiteta. Ser. Vychislitel'naya matematika i informatika [Bulletin of the South Ural state University. Series "Com-putational mathematics and computer science"], 2015, Vol. 4, No. 3, pp. 24-39.
17. Guzik V.F., Kalyaev I.A., Levin I.I. Rekonfiguriruemye vychislitel'nye sistemy [Reconfigurable computing systems], ed. by I.A. Kalyaeva. Rostov-on-Don: Izd-vo YuFU, 2016, 472 p.
18. Kalyaev I.A. i dr. Rekonfiguriruemye mul'tikonveyernye vychislitel'nye struktury [Multiconference reconfigurable computational structures], ed. by I.A. Kalyaeva. 2nd ed. Ros-tov-on-Don: Izd-vo YuNTS RAN, 2009, 344 p.
19. Nauchno-issledovatel'skiy tsentr super-EVM i neyrokomp'yuterov [Scientific research centre of supercomputers and Neurocomputers]. Available at: http://superevm.ru (accessed 02 De-cember 2019).
20. Levin I.I., Dordopulo A.I., Fedorov A.M., Doronchenko Yu.I. Razvitie tekhnologii po-stroeniya rekonfiguriruemykh vychislitel'nykh sistem s zhidkostnym okhlazhdeniem [Development of technology for the construction of reconfigurable computer systems with liquid cooling] Superkomp'yuternye tekhnologii (SKT-2018): Mater. 5-y Vserossiyskoy nauchno-tekhnicheskoy konferentsii [Supercomputing technologies (SKT-2018): Proceedings of the 5th all-Russian scientific and technical conference]: in 2 vol. Vol. 1. Rostov-on-Don; Taganrog: Izd-vo YuFU, 2018, pp. 184-187, ISBN 978-5-9275-2834-9.
21. Eppstein D., Lffler M., and Strash D. Listing all maximal cliques in sparse graphs in near-optimal time, in Algorithms and Computation, ser. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2010, Vol. 6506, pp. 403-414.
22. Eppstein D. and Strash D. Listing all maximal cliques in large sparse real-world graphs, in Proceedings of the 10th international conference on Experimental algorithms, ser. SEA’11. Berlin, Heidelberg: Springer-Verlag, 2011, pp. 364-375. Available: http://dl.acm.org/citation.cfm?id=2008623.2008656 (accessed 02 December 2019).
23. Batagelj V. and Zaversnik M. An o(m) algorithm for cores decomposition of networks, 2003, cite arxiv:cs/0310049. Available: http://arxiv.org/abs/cs/0310049 (accessed 02 December 2019).
24. Kasarkin A.V., Levin I.I. Strukturnaya realizatsiya zadachi nakhozhdeniya vsekh maksimal'nykh klik grafa na rekonfiguriruemykh vychislitel'nykh sistemakh [Structural im-plementation of the problem of finding all maximum clicks of a graph on reconfigurable com-puter systems], Vestnik komp'yuternykh i informatsionnykh tekhnologiy [Bulletin of computer and information technologies], 2018, No. 10, pp. 3-10.