Profiling of energy consumption by algorithms of shortest paths search in large dense graphs

Abstract

Reducing power consumption when solving computationally intensive problems is an important applied problem in science and industry. The paper presents the results of profiling four algorithms of finding the shortest paths between all pairs of graph vertices, which allowed us to estimate the power consumption and execution time of the algorithms on a multicore system. Profiling was performed on single-threaded implementations of the classical Floyd-Warshall algorithm, the algorithm based on vertex expansion of the graph, the homogeneous Floyd-Warshall block algorithm, and the heterogeneous block algorithm. The experiments used simple complete, oriented weighted graphs ranging in size from 1200 to 4800 vertices. Profiling performed via Intel VTune and Intel SoC Watch showed that the algorithm itself has the largest impact on power consumption. On graphs up to 1200 vertices, the power consumption is not proportionally dependent on the algorithm's execution time. For example, the slow classical Floyd-Warshall algorithm has consumed up to 20 % less energy compared to the faster block algorithms. As the graph size increases, the algorithm based on vertex expansion of the graph becomes strictly dominant; it consumed up to 25 % less energy than the blocked algorithms. With increasing the graph size, a proportional relationship between the algorithm execution time and the amount of energy consumed has been clearly established.