Parallel blocked all-pair shortest path algorithm: block size effect on cache operation in multi-core system

Abstract

The problem of finding all-pairs of shortest path in a graph is a classical computer-science problem which has numerous practical applications in multiple domains. This paper analyzes a parallel version of the blocked all-pair shortest path algorithm at the aim of evaluating the influence of the hierarchical cache memory on the parameters of algorithm implementations on multi-processor/multi-core systems. Computational experiments carried out by means of a profiling tool on various graph sizes have convincingly shown that the behavior and parameters of the cache memory operation don’t depend on the graph size and are determined only by the distance matrix block size. Obtained results show, that for every target machine the optimal block size can be found once in the case the graph size isn’t high, it is divisible by the block size, and it is larger than the size of processor’s last level shared cache. After that the optimal block size can be reused for efficient solving of the shortest paths problem on all graphs of larger size.