| 1. |
|
|
| 2. |
- Liu, Meng, et al.
(författare)
-
A dependency-graph based priority assignment algorithm for real-time traffic over NoCs with shared virtual-channels
- 2016
-
Ingår i: IEEE International Workshop on Factory Communication Systems - Proceedings, WFCS. - 9781509023394
-
Konferensbidrag (refereegranskat)abstract
- The Network-on-Chip (NoC) is the on-chip interconnection medium of choice for modern massively parallel processors and System-on-Chip (SoC) in general. Fixed-priority based preemptive scheduling using virtual-channels is a solution to support real-time communications in on-chip networks. Targeting the priority assignment problem in the context of NoCs, heuristic based priority assignment algorithms are more practical, due to the exponentially increased search space as the number of flows goes up. In our previous work, we have proposed a graph-based heuristic priority assignment algorithm (called GHSA) for NoC communications, where we show that taking the dependencies between flows into account can significantly reduce the search space. However, GHSA only works for NoCs with distinct priorities. Routers in such type of platforms may have a large amount of buffer cost when the number of flows is high. The applicability can thus be limited in reality. One solution to reduce the buffer cost is to allow priority sharing of different flows. In this paper, we propose a dependency-graph based priority assignment algorithm (called eGHSA) targeting NoCs with shared virtual-channels. A number of experiments as well as a case study based on an automotive application are generated, which clearly show that eGHSA improves the efficiency compared to the existing solution in the literature.
|
|
| 3. |
- Liu, Meng, et al.
(författare)
-
A Tighter Recursive Calculus to Compute the Worst-Case Traversal Time of Real-Time Traffic over NoCs
- 2017
-
Ingår i: 2017 22ND ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE (ASP-DAC). - 9781509015580 ; , s. 275-282
-
Konferensbidrag (refereegranskat)abstract
- Network-on-Chip (NoC) is a communication subsystem which has been widely utilized in many-core processors and system-on-chips in general. In this paper, we focus on a Round-Robin Arbitration (RRA) based wormhole-switched NoC which is a common architecture used in most of the existing implementations. In order to execute real-time applications on such a NoC based platform, a number of given real-time requirements need to be fulfilled. One of the most typical requirements is schedulability which refers to if real-time packets can be delivered within the given time durations. Timing analysis is a common tool to verify the schedulability of a real-time system. Unfortunately, the existing timing analyses of RRA-based NoCs either provide too pessimistic estimates which results in overly allocated resources, or require a large amount of processing which limits the applicability in reality. Therefore, in this paper, we present an improved timing analysis, aiming to provide more accurate estimates along with acceptable computation time. From the evaluation results, we can clearly observe the improvement achieved by the proposed timing analysis.
|
|
| 4. |
- Liu, Meng, et al.
(författare)
-
Buffer-Aware Analysis for Worst-Case Traversal Time of Real-Time Traffic over RRA-based NoCs
- 2017
-
Ingår i: Proceedings - 2017 25th Euromicro International Conference on Parallel, Distributed and Network-Based Processing, PDP 2017. - 9781509060580 ; , s. 567-575
-
Konferensbidrag (refereegranskat)abstract
- Network-on-Chip (NoC) is a communication sub-system which has been widely utilized in many-core processors and system-on-chips in general. In order to execute time-critical applications on a NoC-based platform, the timing behavior of the network needs to be predicted during system design. One of the most important timing requirements is regarding schedulability, which refers to determining if a real-time packet can be delivered within a specific time duration. To verify the fulfillment of such timing requirement, a proper timing analysis is mandatory. Our work focuses on a Round-Robin Arbitration (RRA) based wormhole-switched NoC, which is a common architecture used in many of the existing implementations. Recursive Calculus (RC) is one of the existing analysis approaches for RRA-based NoCs which has been utilized in many research works. However, RC does not take buffer-effects into account. As a result, while performing RC on most of the existing RRA-based NoC designs, it can produce unsafe estimates which is not acceptable for time-critical systems. In this paper, we identify the optimistic problem of RC, and we propose a Revised Recursive Calculus (RRC) which extends RC by considering buffer-effects as well as supporting packetization.
|
|
| 5. |
- Liu, Meng, et al.
(författare)
-
Improved Priority Assignment for Real-Time Communications in On-Chip Networks
- 2015
-
Ingår i: ACM International Conference Proceeding SeriesVolume 04-06. - New York, NY, USA : ACM. - 9781450335911 ; , s. 171-180
-
Konferensbidrag (refereegranskat)abstract
- The Network-on-Chip is the on-chip interconnection medium of choice for modern massively parallel processors and System-on-Chip in general. Fixed-priority based preemptive scheduling using virtual-channels is a solution to support real-time communications in on-chip networks. However, the different characteristics of the Network-on-Chip compared to the single processor scheduling problem prevents the usage of known optimal algorithms (e.g. the Audsley's algorithm) to assign priorities to messages. A heuristic search algorithm based approach (called the HSA) focusing on the priority assignment for on-chip communications has been presented in the literature. The HSA is much faster than an exhaustive search based solution, with a price of missing certain schedulable cases (i.e. non-optimal). In this paper, we present two undirected-graph based priority assignment algorithms, the GESA and the GHSA. In contrast to the previous work, we can decrease the search space significantly by taking the interference dependencies of different messages on the network into account. A number of experiments are generated, in order to evaluate the proposed algorithms. The results show that the GESA can always achieve higher schedulability ratios than the HSA, but may require longer processing time. On the other hand, the GHSA has the same performance as the HSA regarding the schedulability, but can significantly improve the efficiency.
|
|
| 6. |
- Liu, Meng, et al.
(författare)
-
Scheduling Real-Time Packets with Non-preemptive Regions on Priority-Based NoCs
- 2016
-
Ingår i: Proceedings - 2016 IEEE 22nd International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2016.
-
Konferensbidrag (refereegranskat)abstract
- Network-on-Chip (NoC) is a preferred communi- cation medium for massively parallel platforms. Fixed-priority based scheduling using virtual-channels is one of the promising solutions to support real-time traffic in on-chip networks. Most of the existing NoC implementations which can support fixed- priority based scheduling use a flit-level preemptive scheduling. Under such a mechanism, preemptions can happen between the transmissions of successive flits. In this paper, we present a modified framework where the non-preemptive region of each NoC packet increases from a single flit. Using the proposed approach, the response times of certain packet flows can be reduced, which can thus improve the schedulability of the whole network. As a result, the utilization of NoCs can be improved by admitting more real-time traffic. Schedulability tests regarding the proposed framework are presented along with the proof of the correctness. Moreover, a number of experiments as well as a case study based on an automotive application have been generated, where we can clearly observe the improvement of our solution compared to the original flit-level preemptive NoC.
|
|
| 7. |
- Liu, Meng, et al.
(författare)
-
Tighter Time Analysis for Real-Time Traffic in On-Chip Networks with Shared Priorities
- 2016
-
Ingår i: 2016 10th IEEE/ACM International Symposium on Networks-on-Chip, NOCS 2016.
-
Konferensbidrag (refereegranskat)abstract
- The Network-on-Chip (NoC) is the preferred inter- connection medium for massively parallel platforms. Targeting real-time applications, fixed-priority based NoCs with virtual- channels have been proposed as a promising solution. In order to verify if specific time requirements can be satisfied, scheduability tests are typically used. Several analysis approaches have been proposed targeting priority-based NoCs. However, due to the approximation considered in the analyses, the results may involve a large amount of pessimism. The applicability of the analyses is thus limited in practice. In this paper, we identify a number of properties of NoCs with shared priorities. An improved time analysis is proposed where pessimism can be significantly reduced for many cases. In order to evaluate the proposed analysis, a number of experiments have been generated along with a case study based on an automotive application. The improvement can be clearly observed from the evaluation results.
|
|
| 8. |
- Liu, Meng, et al.
(författare)
-
Using Non-Preemptive Regions and Path Modification to Improve Schedulability of Real-Time Traffic over Priority-Based NoCs
- 2017
-
Ingår i: Real-time systems. - : Springer Science and Business Media LLC. - 0922-6443 .- 1573-1383. ; :6, s. 886-915
-
Tidskriftsartikel (refereegranskat)abstract
- Network-on-Chip (NoC) is a preferred communication medium for massively parallel platforms. Fixed-priority based scheduling using virtual-channels is one of the promising solutions to support real-time traffic in on-chip networks. Most of the existing works regarding priority-based NoCs use a flit-level preemptive scheduling. Under such a mechanism, preemptions can only happen between the transmissions of successive flits but not during the transmission of a single flit. In this paper, we present a modified framework where the non-preemptive region of each NoC packet increases from a single flit. Using the proposed approach, the response times of certain traffic flows can be reduced, which can thus improve the schedulability of the whole network. As a result, the utilization of NoCs can be improved by admitting more real-time traffic. Schedulability tests regarding the proposed framework are presented along with the proof of the correctness. Additionally, we also propose a path modification approach on top of the non-preemptive region based method to further improve schedulability. A number of experiments have been performed to evaluate the proposed solutions, where we can observe significant improvement on schedulability compared to the original flit-level preemptive NoCs.
|
|
| 9. |
- Liu, Meng, et al.
(författare)
-
Using Segmentation to Improve Schedulability of Real-Time Traffic over RRA-based NoCs
- 2016
-
Ingår i: ACM SIGBED Review. Special Issue on 14th International Workshop on Real-Time Networks (RTN 2016) SIGBED Review. - France : ACM. - 1551-3688. ; 13:4, s. 20-24
-
Tidskriftsartikel (refereegranskat)abstract
- Network-on-Chip (NoC) is the interconnect of choice for many- core processors and system-on-chips in general. Most of the existing NoC designs focus on the performance with respect to average throughput, which makes them less applicable for real-time applications especially when applications have hard timing requirements on the worst-case scenarios. In this paper, we focus on a Round- Robin Arbitration (RRA) based wormhole-switched NoC which is a common architecture used in most of the existing implementations. We propose a novel segmentation algorithm targeting RRA-based NoCs in order to improve the schedulability of real-time traffic without modifying the hardware architecture. According to the evaluation results, the proposed segmentation solution can signifi- cantly improve the schedulability of the whole network.
|
|
| 10. |
- Liu, Meng, et al.
(författare)
-
Using Segmentation to Improve Schedulability of RRA-based NoCs with Mixed Traffic
- 2017
-
Ingår i: 2017 22ND ASIA AND SOUTH PACIFIC DESIGN AUTOMATION CONFERENCE (ASP-DAC). - 9781509015580 ; , s. 744-750
-
Konferensbidrag (refereegranskat)abstract
- Network-on-Chip (NoC) is the interconnect of choice for many- core processors and system-on-chips in general. Most of the exist- ing NoC designs focus on the performance with respect to average throughput, which makes them less applicable for real-time appli- cations especially when applications have hard timing requirements on the worst-case scenarios. In this paper, we focus on a Round- Robin Arbitration (RRA) based wormhole-switched NoC which is a common architecture used in most of the existing implementa- tions. We propose a novel segmentation algorithm targeting RRA- based NoCs in order to improve the schedulability of real-time traf- fic without modifying the hardware architecture. Additionally, we also address the problem of transmitting both real-time traffic and best-effort traffic in the same NoC. The proposed solutions aim to provide timing guarantees to real-time traffic and achieve low la- tency for best-effort traffic. According to the evaluation results, the proposed segmentation solution can significantly improve the schedulability of the whole network.
|
|
