Analysis of communication delay bounds for network on chips

ABSTRACT

In network-on-chip, computing worst-case delay bound for packet delivery is crucial for designing predictable systems but yet an intractable problem due to complicated resource contention scenarios. In this paper, we present an analysis technique to derive the communication delay bound for individual flows. Based on a network contention model, this technique, which is topology independent, employs the network calculus theory to first compute the equivalent service curve for individual flows and then calculate their packet delay bound. To exemplify our method, we also present the derivation of a closed-form formula to calculate the delay bound for all-to-one gather communication. Our experimental results demonstrate the theoretical bounds are correct and tight.

REFERENCES

• 1: Cheng-Shang Chang, Performance Guarantees in Communication Networks, Springer-Verlag, London, 2000
• 2: Tobias Bjerregaard , Shankar Mahadevan, A survey of research and practices of Network-on-chip, ACM Computing Surveys (CSUR), v.38 n.1, p.1-es, 2006 [doi>http://doi.acm.org/10.1145/1132952.1132953]
• 3: 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]
• 4: Jean-Yves Le Boudec , Patrick Thiran, Network calculus: a theory of deterministic queuing systems for the internet, Springer-Verlag New York, Inc., New York, NY, 2001
• 5: 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]
• 6: Luciano Lenzini , Linda Martorini , Enzo Mingozzi , Giovanni Stea, Tight end-to-end per-flow delay bounds in FIFO multiplexing sink-tree networks, Performance Evaluation, v.63 n.9, p.956-987, October 2006 [doi>10.1016/j.peva.2005.10.003]
• 7: Shobana Balakrishnan , Füsun Özgüner, A Priority-Driven Flow Control Mechanism for Real-Time Traffic in Multiprocessor Networks, IEEE Transactions on Parallel and Distributed Systems, v.9 n.7, p.664-678, July 1998 [doi>10.1109/71.707545]
• 8: Zhonghai Lu , Axel Jantsch , Ingo Sander, Feasibility analysis of messages for on-chip networks using wormhole routing, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China [doi>10.1145/1120725.1120767]
• 9: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 10: Zhonghai Lu , Axel Jantsch, Slot allocation using logical networks for TDM virtual-circuit configuration for network-on-chip, Proceedings of the 2007 IEEE/ACM international conference on Computer-aided design, November 05-08, 2007, San Jose, California
• 11: J. Ostermann et. al, "Video Coding with H.264/AVC: Tools, Performance and Complexity," IEEE Circuits and Systems Magazine, vol. 4(1), pp. 7--28, 2004.
• 12: Anna Charny , Jean-Yves Le Boudec, Delay Bounds in a Network with Aggregate Scheduling, Proceedings of the First COST 263 International Workshop on Quality of Future Internet Services, p.1-13, September 25-26, 2000
• 13: Markus Fidler , Volker Sander, A parameter based admission control for differentiated services networks, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.44 n.4, p.463-479, 15 March 2004 [doi>10.1016/j.comnet.2003.12.004]
• 14: Jens B. Schmitt , Frank A. Zdarsky, The DISCO network calculator: a toolbox for worst case analysis, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, October 11-13, 2006, Pisa, Italy [doi>10.1145/1190095.1190105]