Slot allocation using logical networks for TDM virtual-circuit configuration for network-on-chip

ABSTRACT

Configuring Time-Division-Multiplexing (TDM) Virtual Circuits (VCs) for network-on-chip must guarantee conflict freedom for overlapping VCs besides allocating sufficient time slots to them. These requirements are fulfilled in the slot allocation phase. In the paper, we define the concept of a logical network (LN). Based on this concept, we develop and prove theorems that constitute sufficient and necessary conditions to establish conflict-free VCs. Using these theorems, slot allocation for VCs becomes a procedure of computing LNs and then assigning VCs to different LNs. TDM VC configuration can thus be predictable and correct-by-construction. We have integrated this slot allocation method into our multi-node VC configuration program and applied the program to an industrial application.

REFERENCES

• 1: Kees Goossens , John Dielissen , Andrei Radulescu, Æthereal Network on Chip: Concepts, Architectures, and Implementations, IEEE Design & Test, v.22 n.5, p.414-421, September 2005 [doi>10.1109/MDT.2005.99]
• 2: Mikael Millberg , Erland Nilsson , Rikard Thid , Axel Jantsch, Guaranteed Bandwidth Using Looped Containers in Temporally Disjoint Networks within the Nostrum Network on Chip, Proceedings of the conference on Design, automation and test in Europe, p.20890, February 16-20, 2004
• 3: Tobias Bjerregaard , Jens Sparso, A Router Architecture for Connection-Oriented Service Guarantees in the MANGO Clockless Network-on-Chip, Proceedings of the conference on Design, Automation and Test in Europe, p.1226-1231, March 07-11, 2005 [doi>10.1109/DATE.2005.36]
• 4: Evgeny Bolotin , Israel Cidon , Ran Ginosar , Avinoam Kolodny, QNoC: QoS architecture and design process for network on chip, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.2-3, p.105-128, February 2004 [doi>10.1016/j.sysarc.2003.07.004]
• 5: O. P. Gangwal, A. Rǎdulescu, K. Goossens, S. González Pestana, and E. Rijpkema, "Building predictable systems on chip: An analysis of guaranteed communication in the Æthereal network on chip," in Dynamic and Robust Streaming In And Between Connected Consumer-Electronics Devices, ser. Philips Research Book Series, P. van der Stok, Ed. Springer, 2005, vol. 3, ch. 1, pp. 1--36.
• 6: Andreas Hansson , Kees Goossens , Andrei Rǎdulescu, A unified approach to constrained mapping and routing on network-on-chip architectures, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084857]
• 7: T. Marescaux, B. Bricke, P. Debacker, V. N. Nollet, and H. Corporaal, "Dynamic time-slot allocation for QoS enabled networks on chip," in Proc. of the IEEE 3rd Workshop on Embedded Systems for Real-Time Multimedia (ESTIMEdia'05), September 2005, pp. 47--52.
• 8: Sander Stuijk , Twan Basten , Marc Geilen , Amir Hossein Ghamarian , Bart Theelen, Resource-Efficient Routing and Scheduling of Time-Constrained Network-on-Chip Communication, Proceedings of the 9th EUROMICRO Conference on Digital System Design, p.45-52, August 30-September 01, 2006 [doi>10.1109/DSD.2006.81]
• 9: Erland Nilsson , Johnny Öberg, Reducing power and latency in 2-D mesh NoCs using globally pseudochronous locally synchronous clocking, Proceedings of the 2nd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 08-10, 2004, Stockholm, Sweden [doi>10.1145/1016720.1016764]
• 10: Jack T. Brassil , Rene L. Cruz, Bounds on Maximum Delay in Networks with Deflection Routing, IEEE Transactions on Parallel and Distributed Systems, v.6 n.7, p.724-732, July 1995 [doi>10.1109/71.395401]