10.14489/vkit.2018.10.pp.003-010

DOI: 10.14489/vkit.2018.10.pp.003-010

Касаркин А. В., Левин И. И.
СТРУКТУРНАЯ РЕАЛИЗАЦИЯ ЗАДАЧИ НАХОЖДЕНИЯ ВСЕХ МАКСИМАЛЬНЫХ КЛИК ГРАФА НА РЕКОНФИГУРИРУЕМЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ
(с. 3-10)

Аннотация. Представлено преобразование алгоритма Брона–Кербоша для поиска всех максимальных клик графа при реализации на реконфигурируемых вычислительных системах (РВС). Показано, что использование РВС обеспечивает близкий к линейному рост производительности системы при наращивании аппаратного ресурса вычислительного поля программируемых логических интегральных схем (ПЛИС) за счет адаптации архитектуры вычислителя к структуре решаемой прикладной задачи. В то же время для классических многопроцессорных систем при достижении определенного числа процессоров рост производительности систем практически не наблюдается. Разработана структура базовой операции добавления/исключения элементов из множества на РВС, где обработка реализована конвейерно. Показано, что такая организация вычислений позволяет свести вычислительную сложность операции добавления / исключения элементов к линейной. Представлено теоретическое обоснование высокой эффективности структурной реализации алгоритма Брона–Кербоша на РВС. Проведен сравнительный анализ скорости решения задач поиска максимальных клик графа на традиционной многопроцессорной вычислительной системе на базе процессоров Intel Xeon E5504 и теоретической скорости решения задачи, достигаемой РВС на базе ПЛИС фирмы Xilinx семейства UltraScale ХСKU095.

Ключевые слова: теория множеств; NP-полные задачи; задача о клике; максимальные клики графа; алгоритм Брона–Кербоша; реконфигурируемые вычислительные системы; программируемые логические интегральные схемы; информационный граф; структурная реализация; конвейер.

Kasarkin A. V., Levin I. I.
STRUCTURAL IMPLEMENTATION THE FINDING PROBLEM OF ALL MAXIMUM GRAPH CLICKS ON RECONFIGURABLE COMPUTER SYSTEM
(pp. 3-10)

Abstract. The paper covers the transformation of the Bron–Kerbosh algorithm to search all maximum graph clicks for implementation on Reconfigurable Computer Systems (RCS). It is shown that the use of RCS provides a close to linear growth of system performance at increasing the hardware resource of FPGA (Field Programmable Gate Array) computational field by adapting the architecture of computer device to the structure of application problem. At the same time, the growth of system performance is practically not observed for classical multiprocessor systems if a certain number of processors is reached. A structure of base operation of adding/removing elements from the RCS set is developed in which the pipeline processing is implemented. It is shown that the computational complexity of adding/excluding element operation is reduced to a linear due to this organization of calculations. A theoretical foundation of the high performance of structural implementation of the Bron-Kerbosh algorithm on RCS is presented. The comparative analysis of searching problem velocity of all maximum graph clicks on traditionally multiprocessor computer system based on the Intel Xeon E5504 processors and the theoretical velocity of solving problem, achieved by RCS based on Xilinx FPGAs of UltraScale family XCKU095, is performed.

Keywords: Set theory; NP-complete problems; Click problem; Maximum graph clicks; Bron–Kerbosh algorithm; Reconfigurable computer systems; Field Programmable Gate Array; Information graph; Structural implementation; Pipeline.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

А. В. Касаркин, И. И. Левин (Институт компьютерных технологий и информационной безопасности Южного федерального университета, Таганрог, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

A. V. Kasarkin, I. I. Levin (Institute of Computer Technologies and Information Security of the Southern Federal University, Taganrog, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Bron C., Kerbosch J. Algorithm 457: Finding All Cliques of an Undirected Graph // Comm of ACM. 1973. V. 16. P. 575 – 577.
2. Moon J. W., Moser L. On Cliques in Graphs // Israel J. Math. 1965. V. 3. P. 23 – 28.
3. Tomita E., Tanaka A., Takahashi H. The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments // Theoretical Computer Science. 2006. V. 363, No. 1. P. 28 – 42.
4. 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. Р. 21 – 30.
5. Rossi R. A., Gleich D. F., Gebremedhin A. H. Parallel Maximumclique Algorithms with Applications to Network Analysis // SIAM J. Sci. Comput. 2015. V. 37, No. 5. Р. 589 – 616.
6. Kovács L., Szabó G. Conceptualization with Incremental Bron-Kerbosch Algorithm in Big Data Architecture // Acta Polytechnica Hungarica. 2016. V. 13, No. 2. Р. 139 – 158.
7. Dasari N. S., Zubair M., Ranjan D. A Novel Parallel Algorithm for Maximal Clique Enumeration on Multicore and Distributed Memory Architectures. [Электронный ресурс]. 10 р. URL: https://pdfs.semanticscholar.org/9827/9e2cedb14085886fcb4473f1ba 483a3df195.pdf (дата обращения: 04.07.2018).
8. Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection / B. Pattabiraman et al. // Internet Mathematics. 2015. V. 11, No. 4-5. P. 421 – 448.
9. Современные и перспективные высокопроизводительные вычислительные системы с реконфигурируемой архитектурой / И. И. Левин и др. // Вестник Южно-Уральского государственного университета. Сер. Вычислительная математика и информатика. 2015. Т. 4, № 3. С. 24 – 39.
10. Гузик В. Ф., Каляев И. А., Левин И. И. Реконфигурируемые вычислительные системы / под общ. ред. И. А. Каляева. Ростов н/Д: Изд-во ЮФУ, 2016. 472 с.
11. Реконфигурируемые мультиконвейерные вычислительные структуры / И. А. Каляев и др.; под общ. ред. И. А. Каляева. 2-е изд., перераб. и доп. Ростов н/Д: Изд-во ЮНЦ РАН, 2009. 344 с.
12. Касаркин А. В. Реализация операций добавления и исключения элементов множества на реконфигурируемых вычислительных системах // Материалы 10-й Всерос. мультиконф. МКПУ-2017. Ростов н/Д, 2017. Т. 3. С. 134 – 136.
13. UltraScale Architecture and Product Data Sheet: Overview [Электронный ресурс] // DS890 (v3.1) November 15, 2017. URL: https://datasheet.octopart.com/ XCKU035-2FBVA900E-Xilinx-datasheet-101617039.pdf (дата обращения: 04.07.2018).

Eng

1. Bron C., Kerbosch J. (1973). Algorithm 457: Finding All Cliques of an Undirected Graph. Communications of the ACM, 16, pp. 575-577.
2. Moon J. W., Moser L. (1965). On Cliques in Graphs. Israel Journal of Mathematics, 3, pp. 23-28.
3. Tomita E., Tanaka A., Takahashi H. (2006). The Worst-Case Time Complexity for Generating All Maximal Cliques and Computational Experiments. Theoretical Computer Science, 363(1), pp. 28-42.
4. Dasari N. S., Ranjan D., Mohammad Z. (2014). Maximal Clique Enumeration for Large Graphs on Hadoop Framework. Proceedings of the first work-shop on Parallel programming for analytics applications, pp. 21-30.
5. Rossi R. A., Gleich D. F., Gebremedhin A. H. (2015). Parallel Maximumclique Algorithms with Appli-cations to Network Analysis. SIAM Journal on Scientific Computing, 37(5), pp. 589-616.
6. Kovács L., Szabó G. (2016). Conceptualization with Incremental Bron-Kerbosch Algorithm in Big Data Architecture. Acta Polytechnica Hungarica, 13 (2), pp. 139-158.
7. Dasari N. S., Zubair M., Ranjan D. A Novel Parallel Algorithm for Maximal Clique Enumeration on Multicore and Distributed Memory Architectures. Available at: https://pdfs.semantic-scholar.org/9827/9e2cedb 14085886fcb4473f1ba483a3df195.pdf, (Accessed: 04.07.2018).
8. Pattabiraman B. et al. (2015). Fast Algorithms for the Maximum Clique Problem on Massive Graphs with Applications to Overlapping Community Detection. Internet Mathematics, 11(4-5), pp. 421-448.
9. Levin I. I. et al. (2015). Modern and future high-performance computing systems with reconfigurable architecture. Vestnik Yuzhno-Ural'skogo gosudarstvennogo universiteta. Seriya Vychislitel'naya matematika i informatika, 4(3), pp. 24-39. [in Russian langiage]
10. Kalyaev I. A. (Ed.), Guzik V. F., Levin I. I. (2016). Reconfigurable computing systems. Rostov-on-Don: Izdatel'stvo YuFU. [in Russian langiage]
11. Kalyaev I. A. (Ed.) et al. (2009). Reconfigurable multi-pipeline computing structures. 2nd ed. Rostov-on-Don: Izdatel'stvo YuNTs RAN. [in Russian langiage]
12. Kasarkin A. V. (2017). Implementation of opera-tions of adding and excluding elements of a set on reconfigurable computing systems. Materials of the 10th All-Russia multiconference MCPU-2017. Rostov-on-Don, Vol. 3, pp. 134-136. [in Russian langiage]
13. UltraScale Architecture and Product Data Sheet: Overview. DS890 (v3.1) November 15, 2017. Available at: https://datasheet.octopart.com/ XCKU035-2FBVA900E-Xilinx-datasheet-101617039.pdf (Accessed: 04.07.2018).

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2018.10.pp.003-010

и заполните форму

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2018.10.pp.003-010

and fill out the form