Ring-Split: Deadlock-Free Routing Algorithm for Circulant Networks-on-Chip
This article considers the usage of circulant topologies as a promising deadlock-free topology for networks-on-chip (NoCs). A new high-level model, Newxim, for the exploration of NoCs with any topology is presented. Two methods for solving the problem of cyclic dependencies in circulant topologies,...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-01-01
|
| Series: | Micromachines |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2072-666X/14/1/141 |
| _version_ | 1797438600882683904 |
|---|---|
| author | Aleksandr Y. Romanov Nikolay M. Myachin Evgenii V. Lezhnev Alexander D. Ivannikov Ahmed El-Mesady |
| author_facet | Aleksandr Y. Romanov Nikolay M. Myachin Evgenii V. Lezhnev Alexander D. Ivannikov Ahmed El-Mesady |
| author_sort | Aleksandr Y. Romanov |
| collection | DOAJ |
| description | This article considers the usage of circulant topologies as a promising deadlock-free topology for networks-on-chip (NoCs). A new high-level model, Newxim, for the exploration of NoCs with any topology is presented. Two methods for solving the problem of cyclic dependencies in circulant topologies, which limit their applications for NoCs due to the increased possibility of deadlocks, are proposed. The first method of dealing with deadlocks is universal and applicable to any topology; it is based on the idea of bypassing blocked sections of the network on an acyclic subnetwork. The second method—Ring-Split—takes into account the features of circulant topologies. The results of high-level modeling and comparison of the peak throughput of NoCs for circulant and mesh topologies using deadlock-free routing algorithms are presented. It was shown that a new approach for routing in circulants (compared to mesh topology) shows up to 59% better network throughput with a uniform distribution of network load. |
| first_indexed | 2024-03-09T11:40:24Z |
| format | Article |
| id | doaj.art-8f37a6475ff646ccb2fd27b9e10095db |
| institution | Directory Open Access Journal |
| issn | 2072-666X |
| language | English |
| last_indexed | 2024-03-09T11:40:24Z |
| publishDate | 2023-01-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Micromachines |
| spelling | doaj.art-8f37a6475ff646ccb2fd27b9e10095db2023-11-30T23:33:46ZengMDPI AGMicromachines2072-666X2023-01-0114114110.3390/mi14010141Ring-Split: Deadlock-Free Routing Algorithm for Circulant Networks-on-ChipAleksandr Y. Romanov0Nikolay M. Myachin1Evgenii V. Lezhnev2Alexander D. Ivannikov3Ahmed El-Mesady4HSE University, Moscow 101000, RussiaOOO “OZON TEKHNOLOGII”, Moscow 123112, RussiaHSE University, Moscow 101000, RussiaInstitute for Design Problems in Microelectronics of Russian Academy of Sciences, Moscow 124365, RussiaDepartment of Physics and Engineering Mathematics, Faculty of Electronic Engineering, Menoufia University, Menouf 32952, EgyptThis article considers the usage of circulant topologies as a promising deadlock-free topology for networks-on-chip (NoCs). A new high-level model, Newxim, for the exploration of NoCs with any topology is presented. Two methods for solving the problem of cyclic dependencies in circulant topologies, which limit their applications for NoCs due to the increased possibility of deadlocks, are proposed. The first method of dealing with deadlocks is universal and applicable to any topology; it is based on the idea of bypassing blocked sections of the network on an acyclic subnetwork. The second method—Ring-Split—takes into account the features of circulant topologies. The results of high-level modeling and comparison of the peak throughput of NoCs for circulant and mesh topologies using deadlock-free routing algorithms are presented. It was shown that a new approach for routing in circulants (compared to mesh topology) shows up to 59% better network throughput with a uniform distribution of network load.https://www.mdpi.com/2072-666X/14/1/141network-on-chiprouting algorithmdeadlockcirculant topologyNoC modeling |
| spellingShingle | Aleksandr Y. Romanov Nikolay M. Myachin Evgenii V. Lezhnev Alexander D. Ivannikov Ahmed El-Mesady Ring-Split: Deadlock-Free Routing Algorithm for Circulant Networks-on-Chip Micromachines network-on-chip routing algorithm deadlock circulant topology NoC modeling |
| title | Ring-Split: Deadlock-Free Routing Algorithm for Circulant Networks-on-Chip |
| title_full | Ring-Split: Deadlock-Free Routing Algorithm for Circulant Networks-on-Chip |
| title_fullStr | Ring-Split: Deadlock-Free Routing Algorithm for Circulant Networks-on-Chip |
| title_full_unstemmed | Ring-Split: Deadlock-Free Routing Algorithm for Circulant Networks-on-Chip |
| title_short | Ring-Split: Deadlock-Free Routing Algorithm for Circulant Networks-on-Chip |
| title_sort | ring split deadlock free routing algorithm for circulant networks on chip |
| topic | network-on-chip routing algorithm deadlock circulant topology NoC modeling |
| url | https://www.mdpi.com/2072-666X/14/1/141 |
| work_keys_str_mv | AT aleksandryromanov ringsplitdeadlockfreeroutingalgorithmforcirculantnetworksonchip AT nikolaymmyachin ringsplitdeadlockfreeroutingalgorithmforcirculantnetworksonchip AT evgeniivlezhnev ringsplitdeadlockfreeroutingalgorithmforcirculantnetworksonchip AT alexanderdivannikov ringsplitdeadlockfreeroutingalgorithmforcirculantnetworksonchip AT ahmedelmesady ringsplitdeadlockfreeroutingalgorithmforcirculantnetworksonchip |