Влияние алгоритмов поиска кратчайших путей наэнергопотребление многоядерных процессоров

Современные многоядерные процессоры, операционные системы и прикладное программное обеспечение разрабатываются с учетом требований энергоэффективности, что значительно снижает энергопотребление. Энергоэффективность программного обеспечения зависит от алгоритмов, которые оно реализует, и от того, как оно использует аппаратные ресурсы. В данной работе мы рассматриваем последовательную и параллельную реализации четырех алгоритмов поиска кратчайших путей на плотных взвешенных графах, измеряем и анализируем их время выполнения, энергопотребление, состояния производительности и рабочую частоту процессора. Наша цель – выяснить, как каждый из алгоритмов влияет на энергопотребление процессора, как процессор и операционная система анализируют рабочую нагрузку и предпринимают действия по увеличению или уменьшению рабочей частоты и отключению ядер, а также какие алгоритмы предпочтительнее использовать в последовательном и параллельном режимах. Алгоритм на основе расширения графа (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 МГц соответственно.

1. Andrae 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/challe6010117

2. Khokhriakov 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.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. 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.

5. Chen K.Y. The Smart Energy Management of Multithreaded Java Applications on Multi-Core Processors / K.Y. Chen,

6. F.G. Chen // International Journal of Networked and Distributed Computing. – 2013. – Vol. 1. – No. 1. – Pp. 53-60.

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

8. 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.

9. 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.

10. 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.

11. Prihozhy А., Karasik O. Inference of shortest path algorithms with spatial and temporal locality for Big Data processing // Сборник материалов VIII Международной научно-практической конференции. – Минск: Беспринт, 2022. – Pp. 56-66.

12. Прихожий, А.А. Разнородный блочный алгоритм поиска кратчайших путей между всеми парами вершин графа / А.А. Прихожий, О.Н. Карасик // Системный анализ и прикладная информатика. – 2017. – № 3.– С. 68-75.

13. Venkataraman, G., Sahni, S., Mukhopadhyaya, S. A Blocked All-Pairs Shortest Paths Algorithm // Journal of Experimental Algorithmics (JEA). 2003. – Vol. 8. – Pp. 857-874.

14. 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.

15. 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.

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

17. Карасик О.Н. Настройка блочно-параллельного алгоритма поиска кратких путей на эффективную многоядерную реализацию / О.Н. Карасик, А.А. Прихожий // Системный анализ и прикладная информатика. – 2022. – № 3. – С. 57-65. DOI: 10.21122/2309-4923-2022-3-57-65

18. Прихожий, А.А. Моделирование кэш прямого отображения и ассоциативных кэш на алгоритмах поиска кратчайших путей на графе / А.А. Прихожий // Системный анализ и прикладная информатика. – 2019. – № 4. – С. 10-18.

19. Прихожий, А.А. Оптимизация размещения данных в иерархической памяти для блочных алгоритмов поиска кратчайших путей / А.А. Прихожий // Системный анализ и прикладная информатика. – 2021. – № 3. – С. 40-50. DOI: 10.21122/2309-4923-2021-3-40-50

20. Прихожий, А.А. Кооперативная модель оптимизации выполнения потоков на многоядерной системе / А.А. Прихожий, О.Н. Карасик // Системный анализ и прикладная информатика. – 2014. – № 4. – C. 13-20.

21. Прыхожы, А.А. Кааператыўныя блочна-паралельныя алгарытмы рашэння задач на шмат'ядравых сістэмах / А.А. Прыхожы, А.М. Карасiк // Системный анализ и прикладная информатика. – 2015. – № 2. – С. 10-18.

22. Карасик, О.Н. Потоковый блочно-параллельный алгоритм поиска кратчайших путей на графе / О.Н. Карасик, А.А. Прихожий // Доклады БГУИР. – 2018. – № 2. – С. 77-84.

23. Прихожий, А.А. Усовершенствованный разнородный блочно-параллельный алгоритм поиска кратчайших путей на графе / А.А. Прихожий, О.Н. Карасик // Труды БГТУ. Сер. 3, Физико-математические науки и информатика. – 2023. – № 1 (266). – С. 77-83. DOI: 10.52065/2520-6141-20

24. Прихожий, А.А. Исследование методов реализации многопоточных приложений на многоядерных системах / А.А. Прихожий, О.Н. Карасик // Информатизация образования. – 2014. – № 1. – Pр. 43-62.

25. Прихожий, А.А. Анализ, преобразование и оптимизация для высокопроизводительных параллельных вычислений. – Минск: БНТУ, 2019. – 229 p.