Localization of data references in blocked heterogeneous shortest paths algorithm for clustered graphs

Abstract

The increasing size of real systems, for which the problem of shortest paths search is solved, necessitates the use of graph models that break the system into autonomous weakly interacting subsystems. Such models include clustered graphs consisting of weakly connected dense subgraphs (clusters) of different sizes. Block algorithms are an efficient solution to the problem of the all-pairs shortest paths. Heterogeneous block algorithms distinguish four types of unequally sized blocks, operate on models that are adequate to real objects, enable the use of architectural features of computing systems to be considered, and reduce the time it takes to calculate the shortest paths in large graphs. In this paper, two new algorithms for computing blocks of two types are developed. They are part of the heterogeneous block algorithm, consider the properties of clustered graphs, and are built on the specifics of the organization of computing architectures (in particular, multicore processors). An important property of these algorithms is their ability to spatially and temporally localize data references, to reduce data transfer traffic in multilevel memory, and to reduce the number of iterations of loops executed. To develop the algorithms formal methods were used to transform, optimize and prove correctness