Please use this identifier to cite or link to this item:
https://elib.bsu.by/handle/123456789/340671| Title: | Heterogeneous blocked all-pairs shortest paths algorithm for clustered weighted graphs |
| Other Titles: | Разнородный блочный алгоритм поиска кратчайших путей между всеми парами вершин кластеризованного взвешенного графа / A. A. Прихожий, О. Н. Карасик |
| Authors: | Prihozhy, A. A. Karasik, O. N. |
| Keywords: | ЭБ БГУ::ОБЩЕСТВЕННЫЕ НАУКИ::Информатика |
| Issue Date: | 2025 |
| Publisher: | Минск : БГУ |
| Citation: | Журнал Белорусского государственного университета. Математика. Информатика = Journal of the Belarusian State University. Mathematics and Informatics. – 2025. – № 3. – С. 62-75 |
| Abstract: | New heterogeneous blocked algorithm of fjnding all-pairs shortest paths in a large directed weighted simple graph consisting of weakly connected dense clusters (subgraphs) of difgerent sizes is proposed. The algorithm considers and actively exploits the input and output bridge-vertices and edges of each cluster to speed up computation and localise memory accesses. It divides all blocks of the cost adjacent matrix into four types (square diagonal, rectangular vertical cross, rectangular horizontal cross and rectangular peripheral) and uses a separate computation procedure for each type, considering the design features of the block itself and the way it is computed through other blocks. A theoretical justifjcation of the advantages of the proposed algorithms, which reduce the execution time when searching for the shortest paths, is given. The validity of the formulated statements is also confjrmed by the results of computational experiments. We have developed single-threaded implementations and multi-threaded OpenMP implementations of the proposed hetero geneous algorithm and two known homogeneous blocked algorithms of fjnding shortest paths. Computational experiments on multi core processors were performed on directed weighted random sparse graphs decomposed into weakly connected dense clusters of difgerent sizes. The results are described for four clustered graphs, two of which have 4800 vertices (20 and 41 clus ters, res pectively) and two of which have 9600 vertices (40 and 80 clusters, respectively). On the MacBook M1 Max computer in the case of single-threaded implementations proposed heterogeneous blocked algorithm for clustered graph with bridgevertices outperformed the known homogeneous blocked algorithm for the same graphs by a factor of 1.62–1.94; in the case of multi-threaded OpenMP implementations the speedup was 1.87–1.97. On a server with Intel Xeon E5-2620v4 processors heterogeneous algorithm outperformed the known homogeneous algorithm by a factor of 1.58 –1.66 for single- threaded implementations and by a factor of 1.29–1.64 for multi-threaded implementations. A comparison of proposed algorithm with the classical blocked Floyd – Warshall algorithm in which all blocks are of the same size showed a speedup of 4.17– 8.18 times in the case of single-threaded implementations and a speedup of 3.91– 6.36 times in the case of multithreaded OpenMP implementations. |
| Abstract (in another language): | Предлагается новый гетерогенный блочный алгоритм поиска кратчайших путей между всеми парами вершин большого ориентированного взвешенного простого графа, состоящего из слабосвязанных плотных кластеров (подграфов) разных размеров. Алгоритм учитывает и активно использует входные и выходные граничные вершины и ребра каждого кластера для ускорения вычислений и локализации обращений к памяти. Он делит все блоки матрицы «стоимость – смежность» на четыре типа (квадратный диагональный, прямоугольный вертикальный на кресте, прямоугольный горизонтальный на кресте и прямоугольный периферийный) и использует отдельную процедуру расчета для них, учитывает конструктивные особенности самого блока и способ его расчета через другие блоки. Приводится теоретическое обоснование преимуществ предлагаемых алгоритмов, сокращающих время выполнения при поиске кратчайших путей. Достоверность сформулированных положений подтверждается результатами проведенных вычислительных экспериментов. Разрабатываются однопоточные реализации и многопоточные OpenMP реализации предлагаемого гетерогенного алгоритма и двух известных гомогенных блочных алгоритмов для поиска кратчайших путей. Вычислительные эксперименты на многоядерных процессорах проводятся на случайных ориентированных взвешенных графах, декомпозированных на слабосвязанные плотные кластеры разных размеров. Описываются результаты для четырех кластеризованных графов, два из которых имеют 4800 вершин (20 и 41 кластер соответственно) и два из которых имеют 9600 вершин (40 и 80 кластеров соответственно). На компьютере MacBook M1 Max в случае с однопоточностью предложенный гетерогенный блочный алгоритм для кластеризованных графов с граничными вершинами превзошел известный гомогенный блочный алгоритм для таких же графов в 1,62–1,94 раза; в случае с OpenMP-многопоточностью ускорение составило 1,87–1,97. На сервере из двух процессоров Intel Xeon E5-2620v4 гетерогенный алгоритм превзошел гомогенный алгоритм в 1,58 –1,66 раза для однопоточности и в 1,29–1,64 раза для многопоточности. Сравнение предложенного алгоритма с классическим блочным алгоритмом Флойда – Уоршелла, в котором блоки имеют одинаковый размер, показало ускорение в 4,17– 8,18 раза в случае с однопоточностью и ускорение в 3,91– 6,36 раза в случае с OpenMP-многопоточностью. |
| URI: | https://elib.bsu.by/handle/123456789/340671 |
| ISSN: | 2520-6508 |
| Licence: | info:eu-repo/semantics/openAccess |
| Appears in Collections: | 2025, №3 |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.