Graph-Based Approach for Buffer-Aware Timing Analysis of Heterogeneous Wormhole NoCs Under Bursty Traffic
This paper addresses the problem of worst-case timing analysis of heterogeneous wormhole NoCs, i.e., routers with different buffer sizes and transmission speeds, when consecutive-packet queuing (CPQ) occurs. The latter means that there are several consecutive packets of one flow queuing in the netwo...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/8998235/ |
| _version_ | 1818735802211893248 |
|---|---|
| author | Frederic Giroudot Ahlem Mifdaoui |
| author_facet | Frederic Giroudot Ahlem Mifdaoui |
| author_sort | Frederic Giroudot |
| collection | DOAJ |
| description | This paper addresses the problem of worst-case timing analysis of heterogeneous wormhole NoCs, i.e., routers with different buffer sizes and transmission speeds, when consecutive-packet queuing (CPQ) occurs. The latter means that there are several consecutive packets of one flow queuing in the network. This scenario happens in the case of bursty traffic but also for non-schedulable traffic. Conducting such an analysis is known to be a challenging issue due to the sophisticated congestion patterns when enabling backpressure mechanisms. We tackle this problem through extending the applicability domain of our previous work for computing maximum delay bounds using Network Calculus, called Buffer-aware worst-case Timing Analysis (BATA). We propose a new Graph-based approach to improve the analysis of indirect blocking due to backpressure, while capturing the CPQ effect and keeping the information about dependencies between flows. Furthermore, the introduced approach improves the computation of indirect-blocking delay bounds in terms of complexity and ensures the safety of these bounds even for non-schedulable traffic. We provide further insights into the tightness and complexity issues of worst-case delay bounds yielded by the extended BATA with the Graph-based approach, denoted G-BATA. Our assessments show that the complexity has decreased by up to 100 times while offering an average tightness ratio of 71%, with reference to the basic BATA. Finally, we evaluate the yielded improvements with G-BATA for a realistic use case against a recent state-of-the-art approach. This evaluation shows the applicability of G-BATA under more general assumptions and the impact of such a feature on the tightness and computation time. |
| first_indexed | 2024-12-18T00:27:02Z |
| format | Article |
| id | doaj.art-3406b39ce7cc475eb0281c498aefaa34 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-18T00:27:02Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-3406b39ce7cc475eb0281c498aefaa342022-12-21T21:27:13ZengIEEEIEEE Access2169-35362020-01-018324423246310.1109/ACCESS.2020.29738918998235Graph-Based Approach for Buffer-Aware Timing Analysis of Heterogeneous Wormhole NoCs Under Bursty TrafficFrederic Giroudot0https://orcid.org/0000-0002-2889-2018Ahlem Mifdaoui1https://orcid.org/0000-0001-7965-5189Department of Complex Systems Engineering, ISAE Supaéro – University of Toulouse, Toulouse, FranceDepartment of Complex Systems Engineering, ISAE Supaéro – University of Toulouse, Toulouse, FranceThis paper addresses the problem of worst-case timing analysis of heterogeneous wormhole NoCs, i.e., routers with different buffer sizes and transmission speeds, when consecutive-packet queuing (CPQ) occurs. The latter means that there are several consecutive packets of one flow queuing in the network. This scenario happens in the case of bursty traffic but also for non-schedulable traffic. Conducting such an analysis is known to be a challenging issue due to the sophisticated congestion patterns when enabling backpressure mechanisms. We tackle this problem through extending the applicability domain of our previous work for computing maximum delay bounds using Network Calculus, called Buffer-aware worst-case Timing Analysis (BATA). We propose a new Graph-based approach to improve the analysis of indirect blocking due to backpressure, while capturing the CPQ effect and keeping the information about dependencies between flows. Furthermore, the introduced approach improves the computation of indirect-blocking delay bounds in terms of complexity and ensures the safety of these bounds even for non-schedulable traffic. We provide further insights into the tightness and complexity issues of worst-case delay bounds yielded by the extended BATA with the Graph-based approach, denoted G-BATA. Our assessments show that the complexity has decreased by up to 100 times while offering an average tightness ratio of 71%, with reference to the basic BATA. Finally, we evaluate the yielded improvements with G-BATA for a realistic use case against a recent state-of-the-art approach. This evaluation shows the applicability of G-BATA under more general assumptions and the impact of such a feature on the tightness and computation time.https://ieeexplore.ieee.org/document/8998235/Networks-on-chipnetwork calculusreal-timetiming analysiswormhole routingvirtual channel |
| spellingShingle | Frederic Giroudot Ahlem Mifdaoui Graph-Based Approach for Buffer-Aware Timing Analysis of Heterogeneous Wormhole NoCs Under Bursty Traffic IEEE Access Networks-on-chip network calculus real-time timing analysis wormhole routing virtual channel |
| title | Graph-Based Approach for Buffer-Aware Timing Analysis of Heterogeneous Wormhole NoCs Under Bursty Traffic |
| title_full | Graph-Based Approach for Buffer-Aware Timing Analysis of Heterogeneous Wormhole NoCs Under Bursty Traffic |
| title_fullStr | Graph-Based Approach for Buffer-Aware Timing Analysis of Heterogeneous Wormhole NoCs Under Bursty Traffic |
| title_full_unstemmed | Graph-Based Approach for Buffer-Aware Timing Analysis of Heterogeneous Wormhole NoCs Under Bursty Traffic |
| title_short | Graph-Based Approach for Buffer-Aware Timing Analysis of Heterogeneous Wormhole NoCs Under Bursty Traffic |
| title_sort | graph based approach for buffer aware timing analysis of heterogeneous wormhole nocs under bursty traffic |
| topic | Networks-on-chip network calculus real-time timing analysis wormhole routing virtual channel |
| url | https://ieeexplore.ieee.org/document/8998235/ |
| work_keys_str_mv | AT fredericgiroudot graphbasedapproachforbufferawaretiminganalysisofheterogeneouswormholenocsunderburstytraffic AT ahlemmifdaoui graphbasedapproachforbufferawaretiminganalysisofheterogeneouswormholenocsunderburstytraffic |