Разнородный блочный алгоритм поиска кратчайших путей между всеми парами вершин кластеризованного взвешенного графа - Прихожий, Анатолий Алексеевич; Карасик, Олег Николаевич (Журнал Белорусского государственного университета. Математика. Информатика, 2026)
Предлагается новый гетерогенный блочный алгоритм поиска кратчайших путей между всеми парами вершин большого ориентированного взвешенного простого графа, состоящего из слабосвязанных плотных кластеров (подграфов) разных размеров. Алгоритм учитывает и активно использует входные и выходные граничные вершины и ребра каждого кластера для ускорения вычислений и локализации обращений к памяти. Он делит все блоки матрицы «стоимость – смежность» на четыре типа (квадратный диагональный, прямоугольный вертикальный на кресте, прямоугольный горизонтальный на кресте и прямоугольный периферийный) и использует отдельную процедуру расчета для них, учитывает конструктивные особенности самого блока и способ его расчета через другие блоки. Приводится теоретическое обоснование преимуществ предлагаемых алгоритмов, сокращающих время выполнения при поиске кратчайших путей. Достоверность сформулированных положений подтверждается результатами проведенных вычислительных экспериментов. Разрабатываются однопоточные реализации и многопоточные 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-многопоточностью.
Keywords: кластеризованный взвешенный большой граф; кратчайшие пути между всеми парами вершин; блочный алгоритм; гетерогенные вычисления; ускорение