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...
Saved in:
| Main Authors: | , |
|---|---|
| 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 |