zbMATH — the first resource for mathematics

Schedulability analysis and task mapping for real-time on-chip communication. (English) Zbl 1213.68153
Summary: Priority-based wormhole switching with a priority share policy has been proposed as a possible solution for real-time on-chip communication. However, the blocking introduced by priority share complicates the analysis process. In this paper, we propose a new “per-priority” basis analysis scheme which computes the total time window at each priority level instead of each traffic-flow. By checking the release instance of each flow at the corresponding priority window, we can determine schedulability efficiently. Building on this static analysis, for a given set of tasks and network topology, we further propose a task mapping and priority assignment algorithm, in such a way that the hard time bounds are met with a reduced hardware overhead. Experiment results show that significant resource saving can be achieved with no performance degradation in terms of missed deadlines. By using this approach, a broad class of real-time communications with different QoS requirements can be explored and developed in a SoC/NoC communication platform.

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68M99 Computer system organization
Full Text: DOI
[1] Audsley NC, Burns A, Richardson M, Tindell KW, Wellings AJ (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8:284–292 · doi:10.1049/sej.1993.0034
[2] Balakrishnan S, Ozguner F (1998) A priority-driven flow control mechanism for real-time traffic in multiprocessor networks. IEEE Trans Parallel Distrib Syst 9(7):664–678 · doi:10.1109/71.707545
[3] Benini L, Micheli GD (2002) Networks on chips: a new SoC paradigm. Computer 35(1):70–78 · Zbl 05087025 · doi:10.1109/2.976921
[4] Bjerregaard T, Mahadevan S (2006) A survey of research and practices of network-on-chip. ACM Comput Surv 38(1):1 · doi:10.1145/1132952.1132953
[5] Bjerregaard T, Sparsø J (2005) A scheduling discipline for latency and bandwidth guarantees in asynchronous network-on-chip. In: ASYNC ’05: Proceedings of the 11th IEEE international symposium on asynchronous circuits and systems, pp 34–43
[6] Bolotin E, Cidon I, Ginosar R, Kolodny A (2004) QNoC: QoS architecture and design process for network on chip. J Syst Archit 50:105–128 · Zbl 05431999 · doi:10.1016/j.sysarc.2003.07.004
[7] Dally WJ (1992) Virtual-channel flow control. IEEE Trans Parallel Distrib Syst 3(2):194–205 · Zbl 05106668 · doi:10.1109/71.127260
[8] Dally WJ (2001) Route packets, not wires: on-chip interconnection networks. In: Proceedings of the 38th design automation conference (DAC), pp 684–689
[9] Dick RP, Rhodes DL, Wolf W (1998) TGFF: task graph for free. In: Proceedings of the international workshop hardware-software codesign
[10] Furber S, Bainbridge J (2005) Future trends in SoC interconnect. In: IEEE international symposium on VLSI design, automation and test, pp 183–186
[11] Goossens K, Dielissen J, Radulescu A (2005) Æthereal network on chip: concepts, architectures, and implementations. IEEE Des Test 22(5):414–421 · Zbl 05094065 · doi:10.1109/MDT.2005.99
[12] Hary SL, Ozguner F (1997) Feasibility test for real-time communication using wormhole routing. IEE Proc Comput Digital Tech 144(5):273–278 · doi:10.1049/ip-cdt:19971369
[13] Kavaldjiev N, Smith GJM, Jansen PG, Wolkotte PT (2006) A virtual channel network-on-chip for GT and BE traffic. In: ISVLSI ’06: Proceedings of the IEEE computer society annual symposium on emerging VLSI technologies and architectures. IEEE Computer Society, Washington, p 211
[14] Kim B, Kim J, Hong SJ, Lee S (1998) A real-time communication method for wormhole switching networks. In: ICPP ’98: Proceedings of the international conference on parallel processing, pp 527–534
[15] Lehoczky JP (1990) Fixed priority scheduling of periodic task sets with arbitrary deadlines. In: 11th IEEE real-time systems symposium, pp 201–209
[16] Lu Z, Jantsch A, Sander I (2005) Feasibility analysis of messages for on-chip networks using wormhole routing. In: ASP-DAC ’05: Proceedings of the 2005 conference on Asia South Pacific design automation, pp 960–964
[17] Millberg M, Nilsson E, Thid R, Jantsch A (2004) Guaranteed bandwidth using looped containers in temporally disjoint networks within the Nostrum network on chip. In: Proceedings of the design automation and test Europe conference (DATE), p 20890
[18] Ni LM, McKinley PK (1993) A survey of wormhole routing techniques in direct networks. Computer 26(2):62–76 · Zbl 05087633 · doi:10.1109/2.191995
[19] Shi Z, Burns A (2008a) Priority assignment for real-time wormhole communication in on-chip networks. In: Proceeding of the 29th IEEE real time system symposium (RTSS), pp 421–430
[20] Shi Z, Burns A (2008b) Real-time communication analysis for on-chip networks with wormhole switching. In: Proceeding of the 2nd ACM/IEEE international symposium on networks-on-chip (NoCS), pp 161–170
[21] Shi Z, Burns A (2009a) Real-time communication analysis with a priority share policy in on-chip networks. In: 21st Euromicro conference on real-time systems (ECRTS), pp 3–12
[22] Shi Z, Burns A (2009b) Improvement of schedulability analysis with a priority share policy in on-chip networks. In: 17th international conference on real-time and network systems (RTNS), pp 75–84
[23] Tindell KW, Burns A, Wellings AJ (1994) An extendible approach for analyzing fixed priority hard real-time tasks. Real-Time Syst J 6(2):133–151 · doi:10.1007/BF01088593
[24] Wiklund D, Liu D (2003) Socbus: switched network on chip for hard real time embedded systems. In: IPDPS ’03: Proceedings of the 17th international symposium on parallel and distributed processing. IEEE Computer Society, Washington, p 781
[25] Wolkotte PT, Smit GJM, Rauwerda GK, Smit LT (2005) An energy-efficient reconfigurable circuit-switched network-on-chip. In: IPDPS ’05: Proceedings of the 19th IEEE international parallel and distributed processing symposium (IPDPS’05)–Workshop 3. IEEE Computer Society, Washington, p 1551
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.