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

Full description

Saved in:
Bibliographic Details
Main Authors: A. A. Prihozhy, O. N. Karasik
Format: Article
Language:English
Published: Belarusian National Technical University 2023-10-01
Series:Системный анализ и прикладная информатика
Subjects:
Online Access:https://sapi.bntu.by/jour/article/view/613
Tags: Add Tag
No Tags, Be the first to tag this record!
_version_ 1832543614500077568
author A. A. Prihozhy
O. N. Karasik
author_facet A. A. Prihozhy
O. N. Karasik
author_sort A. A. Prihozhy
collection DOAJ
description 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.
format Article
id doaj-art-084062fd552a4a5282c41e3822df54bf
institution Kabale University
issn 2309-4923
2414-0481
language English
publishDate 2023-10-01
publisher Belarusian National Technical University
record_format Article
series Системный анализ и прикладная информатика
spelling doaj-art-084062fd552a4a5282c41e3822df54bf2025-02-03T11:37:40ZengBelarusian National Technical UniversityСистемный анализ и прикладная информатика2309-49232414-04812023-10-010241210.21122/2309-4923-2023-2-4-12454Influence of shortest path algorithms on energy consumption of multi-core processorsA. A. Prihozhy0O. N. Karasik1Belarusian National Technical UniversityBelarusian National Technical UniversityModern 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.https://sapi.bntu.by/jour/article/view/613multi-core processorshortest paths algorithmsingle-thread applicationmulti-threaded applicationruntimeenergy consumptionopenmp
spellingShingle A. A. Prihozhy
O. N. Karasik
Influence of shortest path algorithms on energy consumption of multi-core processors
Системный анализ и прикладная информатика
multi-core processor
shortest paths algorithm
single-thread application
multi-threaded application
runtime
energy consumption
openmp
title Influence of shortest path algorithms on energy consumption of multi-core processors
title_full Influence of shortest path algorithms on energy consumption of multi-core processors
title_fullStr Influence of shortest path algorithms on energy consumption of multi-core processors
title_full_unstemmed Influence of shortest path algorithms on energy consumption of multi-core processors
title_short Influence of shortest path algorithms on energy consumption of multi-core processors
title_sort influence of shortest path algorithms on energy consumption of multi core processors
topic multi-core processor
shortest paths algorithm
single-thread application
multi-threaded application
runtime
energy consumption
openmp
url https://sapi.bntu.by/jour/article/view/613
work_keys_str_mv AT aaprihozhy influenceofshortestpathalgorithmsonenergyconsumptionofmulticoreprocessors
AT onkarasik influenceofshortestpathalgorithmsonenergyconsumptionofmulticoreprocessors