Influence of shortest path algorithms on energy consumption of multi-core processors

Modern multi-core processors, operating systems and applied software are being designed towards energy efficiency, which significantly reduces energy consumption. Energy efficiency of software depends on algorithms it implements, and, on the way, it exploits hardware resources. In the paper, we consider sequential and parallel implementations of four algorithms of shortest paths search in dense weighted graphs, measure and analyze their runtime, energy consumption, performance states and operating frequency of the Intel Core i7-10700 8-core processor. Our goal is to find out how each of the algorithms influences the processor energy consumption, how the processor and operating system analyze the workload and take actions to increase or reduce operating frequency and to disable cores, and which algorithms are preferable for exploiting in sequential and parallel modes. The graph extension-based algorithm (GEA) appeared to be the most energy efficient among algorithms implemented sequentially. The classical Floyd-Warshall algorithm (FW) consumed up to twice as much energy, and the blocked homogeneous (BFW) and heterogeneous (HBFW) algorithms consumed up to 52.2 % and 21.2 % more energy than GEA. Parallel implementations of BFW and HBFW are faster by up to 4.41 times and more energy efficient by up to 3.23 times than the parallel implementation of FW and consume less energy by up to 2.22 times than their sequential counterparts. The sequential GEA algorithm consumes less energy than the parallel FW, although it loses FW in runtime. The multi-core processor runs FW with an average frequency of 4235 MHz and runs BFW and HBFW with lower frequency of 4059 MHz and 4035 MHz respectively.

1. Andrae A., Edler T. On global electricity usage of communication technology: trends to 2030. Challenges 2015; 6(1):117-157. DOI: 10.3390/challe6010117

2. Khokhriakov S., Manumachu R.R., Lastovetsky A. Multicore processor computing is not energy proportional: An opportunity for bi-objective optimization for energy and performance. Applied Energy, vol. 268, 2020, 114957, ISSN 0306-2619, DOI: 10.1016/j.apenergy.2020.114957

3. Basmadjian R. and De Meer H. Evaluating and modeling power consumption of multi-core processors. In Proc. of the 3rd Int’l Conf. on Future Energy Systems (e-Energy 2012). ACM, May 2012, pp. 1-10.

4. Attia K.M., El-Hosseini M.A., Ali H.A. Dynamic power management techniques in multi-core architectures: A survey study. Ain Shams Engineering Journal, 2017, vol. 8, no. 3, pp. 445-456.

5. Chen K.Y., Chen F.G. The Smart Energy Management of Multithreaded Java Applications on Multi-Core Processors. International Journal of Networked and Distributed Computing, 2013, vol. 1, no. 1, pp. 53-60.

6. Floyd R.W. Algorithm 97: Shortest path. Communications of the ACM, 1962, 5(6), p. 345.

7. Madkour A., Aref W.G., Rehman F.U., Rahman M.A., Basalamah S. A Survey of Shortest-Path Algorithms. ArXiv:1705.02044v1 [cs.DS] 4 May 2017, 26 p.

8. Singh A., Mishra P.K. Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm. International Journal of Computer Applications, vol. 107, no. 16, 2014, pp. 23-27.

9. Pettie S. A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science, 312 (1), 2004: 47-74.

10. Prihozhy А., Karasik O. Inference of shortest path algorithms with spatial and temporal locality for Big Data processing // Proceedings VIII International conference “Big data and advanced analytics”, Minsk: Bestprint, 2022. pp. 56-66.

11. Prihozhy A.A., Karasik O.N. Heterogeneous blocked all-pairs shortest paths algorithm. System analysis and Applied Information Science, 2017, no. 3, pp. 68-75. DOI: 10.21122/2309-4923-20173-68-75

12. Venkataraman, G., Sahni, S., Mukhopadhyaya, S. A Blocked All-Pairs Shortest Paths Algorithm. Journal of Experimental Algorithmics (JEA), 2003, vol. 8, pp. 857-874.

13. Park, J.S., Penner, M., and Prasanna, V.K. Optimizing graph algorithms for improved cache performance. IEEE Trans. on Parallel and Distributed Systems, 2004, 15(9), pp. 769-782.

14. Albalawi, E., Thulasiraman, P., Thulasiram, R. Task Level Parallelization of All Pair Shortest Path Algorithm in OpenMP 3.0. 2nd International Conference on Advances in Computer Science and Engineering (CSE 2013), 2013, Los Angeles, CA, July 1-2, 2013, pp. 109-112.

15. Tang, P. Rapid Development of Parallel Blocked All-Pairs Shortest Paths Code for Multi-Core Computers. IEEE SOUTHEASTCON, 2014, pp. 1-7.

16. Karasik O.N., Prihozhy A.A. Tuning block-parallel all-pairs shortest path algorithm for effi multi-core implementation. System analysis and applied information science, 2022, no. 3, pp. 57–65. DOI: 10.21122/2309-4923-2022-3-57-65

17. Prihozhy A.A. Simulation of direct mapped, k-way and fully associative cache on all pairs shortest paths algorithms. System analysis and applied information science, 2019, no. 4, pp. 10-18.

18. Prihozhy A.A. Optimization of data allocation in hierarchical memory for blocked shortest paths algorithms. System analysis and applied information science, 2021, no. 3, pp. 40-50.

19. Prihozhy A.A., Karasik O.N. Cooperative model for optimization of execution of threads on multi-core system. System analysis and applied information science, 2014, no. 4, pp. 13-20.

20. Prihozhy A.A., Karasik O.N. Cooperative block-parallel algorithms for task execution on multi-core system. System analysis and applied information science, 2015, no. 2, pp. 10-18.

21. Karasik O.N., Prihozhy A.A. Threaded block-parallel algorithm for finding the shortest paths on graph. Doklady BGUIR, 2018, no. 2, pp. 77-84.

22. Prihozhy А.А., Karasik O.N. Advanced heterogeneous block-parallel all-pairs shortest path algorithm. Proceedings of BSTU, issue 3, Physics and Mathematics. Informatics, 2023, no. 1 (266), pp. 77–83. DOI: 10.52065/2520-6141-2023-266-1-13

23. Prihozhy A.A., Karasik O.N. Investigation of methods for implementing multithreaded applications on multicore systems. Informatization of education, 2014, no. 1, pp. 43-62.

24. Prihozhy, A.A. Analysis, transformation and optimization for high performance parallel computing. Minsk: BNTU, 2019, 229 p.