Разнородный блочный алгоритм поиска кратчайших путей между всеми парами вершин графа
Another Title
Heterogenious blocked all-pairs shortest paths algorithm
Bibliographic entry
Прихожий, А. А., Карасик О. Н. Разнородный блочный алгоритм поиска кратчайших путей между всеми парами вершин графа = Heterogenious blocked all-pairs shortest paths algorithm / А. А. Прихожий, О. Н. Карасик // Системный анализ и прикладная информатика. - 2017. – №3. - С. 68-75.
Abstract
Рассматривается проблема поиска кратчайших путей между всеми парами вершин взвешенного ориентированного графа. Известны алгоритмы Дейкстры и Флойда-Уоршелла, однородные блочные и параллельные алгоритмы и другие алгоритмы решения этой проблемы. Предлагается новый разнородный блочный алгоритм, рассматривающий различные типы блоков и учитывающий разделяемую иерархическую организации памяти и многоядерность процессоров при вычислении блока каждого типа. На теоретическом и экспериментальном уровнях проводится сравнение предлагаемых разнородных алгоритмов вычисления блоков с общепринятым однородным универсальным алгоритмом пересчета блока. Основной акцент делается на использовании вариантов неоднородности, взаимодействия блоков во время вычислений и вариаций в размере блока, размере матрицы блоков и общего количества блоков с целью выявления возможности сокращения объема вычислений, производимых при расчете блока, сокращения активности работы с кэш памятью процессора и выявления влияния времени расчета каждого типа блока на общее время выполнения разнородного блочного алгоритма. Предложен рекуррентный ресинхронизированный алгоритм расчета диагонального блока (D0), улучшающий использование кэш памяти процессора и сокращающий количество итераций и размер данных, необходимых для расчёта диагонального блока до 3 раз, что дает ускорение в расчете диагонального блока до 60%. Для более эффективной работы с кэш памятью предложены варианты перестановки основных циклов k-i-j алгоритмов расчета блоков креста (C1, C2) и обновляемых блоков (U3), использование которых в комбинации с алгоритмом расчета диагонального блока сокращает общее время работы разнородного блочного алгоритма на 13% в среднем по сравнению с однородным блочным алгоритмом.
Abstract in another language
The problem of finding the shortest paths between all pairs of vertices in a weighted directed graph is considered. The algorithms of Dijkstra and Floyd-Warshall, homogeneous block and parallel algorithms and other algorithms of solving this problem are known. A new heterogeneous block algorithm is proposed which considers various types of blocks and takes into account the shared hierarchical memory organization and multi-core processors for calculating each type of block. The proposed heterogeneous block computing algorithms are compared with the generally accepted homogeneous universal block calculation algorithm at theoretical and experimental levels. The main emphasis is on using the nature of the heterogeneity, the interaction of blocks during computation and the variation in block size, the size of the block matrix and the total number of blocks in order to identify the possibility of reducing the amount of computation performed during the calculation of the block, reducing the activity of the processor’s cache memory and determining the influence of the calculation time of each block type on the total execution time of the heterogeneous block algorithm. A recurrent resynchronized algorithm for calculating the diagonal block (D0) is proposed, which improves the use of the processor’s cache and reduces the number of iterations up to 3 times that are necessary to calculate the diagonal block, which implies the acceleration in calculating the diagonal block up to 60%. For more efficient work with the cache memory, variants of permutation of the basic loops k-i-j in the algorithms of calculating the blocks of the cross (C1 and C2) and the updated blocks (U3) are proposed. These permutations in combination with the proposed algorithm for calculating the diagonal block reduce the total runtime of the heterogeneous block algorithm to 13% on average against the homogeneous block algorithm.
View/
Collections
- №3[10]