sapiСистемный анализ и прикладная информатика«System analysis and applied information science»2309-49232414-0481Belarusian National Technical University10.21122/2309-4923-2023-2-4-12sapi-613Research ArticleСистемный анализSystem analysisВлияние алгоритмов поиска кратчайших путей наэнергопотребление многоядерных процессоровInfluence of shortest path algorithms on energy consumption of multi-core processorsПрихожийА. А.PrihozhyA. A.

Минск

КарасикО. Н.KarasikO. N.

Минск

Белорусский национальный технический университетБеларусьBelarusian National Technical UniversityBelarus20230310202302412Copyright © Прихожий А.А., Карасик О.Н., 20232023Прихожий А.А., Карасик О.Н.Prihozhy A.A., Karasik O.N.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://sapi.bntu.by/jour/article/view/613

Современные многоядерные процессоры, операционные системы и прикладное программное обеспечение разрабатываются с учетом требований энергоэффективности, что значительно снижает энергопотребление. Энергоэффективность программного обеспечения зависит от алгоритмов, которые оно реализует, и от того, как оно использует аппаратные ресурсы. В данной работе мы рассматриваем последовательную и параллельную реализации четырех алгоритмов поиска кратчайших путей на плотных взвешенных графах, измеряем и анализируем их время выполнения, энергопотребление, состояния производительности и рабочую частоту процессора. Наша цель – выяснить, как каждый из алгоритмов влияет на энергопотребление процессора, как процессор и операционная система анализируют рабочую нагрузку и предпринимают действия по увеличению или уменьшению рабочей частоты и отключению ядер, а также какие алгоритмы предпочтительнее использовать в последовательном и параллельном режимах. Алгоритм на основе расширения графа (GEA) оказался наиболее энергоэффективным среди алгоритмов, реализуемых последовательно. Классический алгоритм Флойда-Уоршалла (FW) потребил в два раза больше энергии, а блочные однородный (BFW) и неоднородный (HBFW) алгоритмы потребили на 52,2 % и 21,2 % больше энергии, чем GEA. Все эксперименты проводились на 8-ядерном процессоре Intel Core i7-10700. Параллельные реализации алгоритмов BFW и HBFW быстрее и энергоэффективнее параллельной реал изации FW. Они потребили меньше энергии, чем их последовательные аналоги. Последовательный алгоритм GEA потребил меньше энергии, чем параллельный FW, хотя проиграл последнему по времени выполнения. Многоядерный процессор выполнял FW со средней частотой 4235 МГц, и выполнял BFW и HBFW с меньшей частотой 4059 МГц и 4035 МГц соответственно.

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.

многоядерный процессоралгоритм кратчайших путейоднопоточное приложениемногопоточное приложениевремя выполненияэнергопотреблениеOpenMPmulti-core processorshortest paths algorithmsingle-thread applicationmulti-threaded applicationruntimeenergy consumptionOpenMPReferencesAndrae A. On global electricity usage of communication technology: trends to 2030 / A. Andrae, T. Edler // Challenges 2015. – No. 6(1):117-157. DOI: 10.3390/challe6010117Andrae A., Edler T. On global electricity usage of communication technology: trends to 2030. Challenges 2015; 6(1):117-157. DOI: 10.3390/challe6010117Khokhriakov S. Multicore processor computing is not energy proportional: An opportunity for bi-objective optimization for energy and performance / S. Khokhriakov, R.R. Manumachu, A. Lastovetsky // Applied Energy. – Vol. 268. – 2020. – Pp. 114957. ISSN 0306-2619. DOI: 10.1016/j.apenergy.2020.114957Khokhriakov 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.114957Basmadjian 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.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.Attia K.M. Dynamic power management techniques in multi-core architectures: A survey study / K.M. Attia, M.A. ElHosseini, H.A. Ali // Ain Shams Engineering Journal. – 2017. – Vol. 8. – No. 3. – Pp. 445-456.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.Chen K.Y. The Smart Energy Management of Multithreaded Java Applications on Multi-Core Processors / K.Y. Chen,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.F.G. Chen // International Journal of Networked and Distributed Computing. – 2013. – Vol. 1. – No. 1. – Pp. 53-60.Floyd R.W. Algorithm 97: Shortest path. Communications of the ACM, 1962, 5(6), p. 345.Floyd, R.W. Algorithm 97: Shortest path. Communications of the ACM, 1962, 5(6), p. 345.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.Singh, A. Performance Analysis of Floyd Warshall Algorithm vs Rectangular Algorithm / A. Singh, P.K. Mishra // International Journal of Computer Applications. – 2014. –Vol. 107, No. 16. – Pp. 23-27.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.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.Pettie S. A new approach to all-pairs shortest paths on real-weighted graphs. Theoretical Computer Science, 312 (1), 2004: 47-74.Pettie, S. A new approach to all-pairs shortest paths on real-weighted graphs / S. Pettie // Theoretical Computer Science. 312 (1). – 2004. – Pp. 47-74.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.Prihozhy А., Karasik O. Inference of shortest path algorithms with spatial and temporal locality for Big Data processing // Сборник материалов VIII Международной научно-практической конференции. – Минск: Беспринт, 2022. – Pp. 56-66.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Прихожий, А.А. Разнородный блочный алгоритм поиска кратчайших путей между всеми парами вершин графа / А.А. Прихожий, О.Н. Карасик // Системный анализ и прикладная информатика. – 2017. – № 3.– С. 68-75.Venkataraman, G., Sahni, S., Mukhopadhyaya, S. A Blocked All-Pairs Shortest Paths Algorithm. Journal of Experimental Algorithmics (JEA), 2003, vol. 8, pp. 857-874.Venkataraman, G., Sahni, S., Mukhopadhyaya, S. A Blocked All-Pairs Shortest Paths Algorithm // Journal of Experimental Algorithmics (JEA). 2003. – Vol. 8. – Pp. 857-874.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.Park, J.S. Optimizing graph algorithms for improved cache performance / J.S. Park, M. Penner, V.K. Prasanna // IEEE Trans. on Parallel and Distributed Systems. – 2004. – No. 15(9). – Pp. 769-782.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.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.Tang, P. Rapid Development of Parallel Blocked All-Pairs Shortest Paths Code for Multi-Core Computers. IEEE SOUTHEASTCON, 2014, pp. 1-7.Tang, P. Rapid Development of Parallel Blocked All-Pairs Shortest Paths Code for Multi-Core Computers // IEEE SOUTHEASTCON. – 2014. – Pp. 1-7.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Карасик О.Н. Настройка блочно-параллельного алгоритма поиска кратких путей на эффективную многоядерную реализацию / О.Н. Карасик, А.А. Прихожий // Системный анализ и прикладная информатика. – 2022. – № 3. – С. 57-65. DOI: 10.21122/2309-4923-2022-3-57-65Prihozhy 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.Прихожий, А.А. Моделирование кэш прямого отображения и ассоциативных кэш на алгоритмах поиска кратчайших путей на графе / А.А. Прихожий // Системный анализ и прикладная информатика. – 2019. – № 4. – С. 10-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.Прихожий, А.А. Оптимизация размещения данных в иерархической памяти для блочных алгоритмов поиска кратчайших путей / А.А. Прихожий // Системный анализ и прикладная информатика. – 2021. – № 3. – С. 40-50. DOI: 10.21122/2309-4923-2021-3-40-50Prihozhy 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.Прихожий, А.А. Кооперативная модель оптимизации выполнения потоков на многоядерной системе / А.А. Прихожий, О.Н. Карасик // Системный анализ и прикладная информатика. – 2014. – № 4. – C. 13-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.Прыхожы, А.А. Кааператыўныя блочна-паралельныя алгарытмы рашэння задач на шмат'ядравых сістэмах / А.А. Прыхожы, А.М. Карасiк // Системный анализ и прикладная информатика. – 2015. – № 2. – С. 10-18.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.Карасик, О.Н. Потоковый блочно-параллельный алгоритм поиска кратчайших путей на графе / О.Н. Карасик, А.А. Прихожий // Доклады БГУИР. – 2018. – № 2. – С. 77-84.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Прихожий, А.А. Усовершенствованный разнородный блочно-параллельный алгоритм поиска кратчайших путей на графе / А.А. Прихожий, О.Н. Карасик // Труды БГТУ. Сер. 3, Физико-математические науки и информатика. – 2023. – № 1 (266). – С. 77-83. DOI: 10.52065/2520-6141-20Prihozhy A.A., Karasik O.N. Investigation of methods for implementing multithreaded applications on multicore systems. Informatization of education, 2014, no. 1, pp. 43-62.Прихожий, А.А. Исследование методов реализации многопоточных приложений на многоядерных системах / А.А. Прихожий, О.Н. Карасик // Информатизация образования. – 2014. – № 1. – Pр. 43-62.Prihozhy, A.A. Analysis, transformation and optimization for high performance parallel computing. Minsk: BNTU, 2019, 229 p.Прихожий, А.А. Анализ, преобразование и оптимизация для высокопроизводительных параллельных вычислений. – Минск: БНТУ, 2019. – 229 p.Прихожий, А.А. Анализ, преобразование и оптимизация для высокопроизводительных параллельных вычислений. – Минск: БНТУ, 2019. – 229 p.

The authors declare that there are no conflicts of interest present.