Efficient link capacity and QoS design for network-on-chip

ABSTRACT

This paper addresses the allocation of link capacities in the automated design process of a network-on-chip based system. Communication resource costs are minimized under Quality-of-Service timing constraints.First, we introduce a novel analytical delay model for virtual channeled wormhole networks with non-uniform link capacities that eliminates costly simulations at the inner-loop of the optimization process. Second, we present an efficient capacity allocation algorithm that assigns link capacities such that packet delays requirements for each flow are satisfied. We demonstrate the benefit of capacity allocation for a typical system on chip, where the traffic is heterogeneous and delay requirements may largely vary, in comparison with the standard approach which assumes uniform-capacity links.

REFERENCES

• 1: Pierre Guerrier , Alain Greiner, A generic architecture for on-chip packet-switched interconnections, Proceedings of the conference on Design, automation and test in Europe, p.250-256, March 27-30, 2000, Paris, France [doi>10.1145/343647.343776]
• 2: William J. Dally , Brian Towles, Route packets, not wires: on-chip inteconnection networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 3: 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]
• 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: Kees Goossens , John Dielissen , Om Prakash Gangwal , Santiago Gonzalez Pestana , Andrei Radulescu , Edwin Rijpkema, A Design Flow for Application-Specific Networks on Chip with Guaranteed Performance to Accelerate SOC Design and Verification, Proceedings of the conference on Design, Automation and Test in Europe, p.1182-1187, March 07-11, 2005 [doi>10.1109/DATE.2005.11]
• 6: Jingcao Hu , R. Marculescu, Application-specific buffer space allocation for networks-on-chip router design, Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design, p.354-361, November 07-11, 2004 [doi>10.1109/ICCAD.2004.1382601]
• 7: W.J. Dally and C. Seitz. The Torus Routing Chip. Distributed Computing, vol. 1, no. 3, 1986, pp. 187--196
• 8: H. Sarbazi-Azad, A. Khonsari and M. Ould-khaoua. Performance Analysis of Deterministic Routing in Wormhole k-ary n-cubes with Virtual Channels. Journal of Interconnection Networks, 2002, vol. 3
• 9: S. Loucif , M. Ould-khaoua, Modeling Latency in Deterministic Wormhole-Routed Hypercubes under Hot-Spot Traffic, The Journal of Supercomputing, v.27 n.3, p.265-278, March 2004 [doi>10.1023/B:SUPE.0000011387.24259.d1]
• 10: Christian Roche , Prasasth Palnati , Mario Gerla , Fabio Neri , Emilio Leonardi, Performance of Congestion Control Mechanisms in Wormhole Routing Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1365, April 09-11, 1997
• 11: Jong Kim , C. R. Das, Hypercube Communication Delay with Wormhole Routing, IEEE Transactions on Computers, v.43 n.7, p.806-814, July 1994 [doi>10.1109/12.293259]
• 12: R. I. Greenberg and L. Guan. Modeling and Comparison of Wormhole Routed Mesh and Torus Networks. IASTED, 1997
• 13: B. Ciciani , M. Colajanni , C. Paolucci, Performance evaluation of deterministic wormhole routing in k-ary n-cubes, Parallel Computing, v.24 n.14, p.2053-2075, Dec. 1998 [doi>10.1016/S0167-8191(98)00094-5]
• 14: Jeffrey T. Draper , Joydeep Ghosh, A comprehensive analytical model for wormhole routing in multicomputer systems, Journal of Parallel and Distributed Computing, v.23 n.2, p.202-214, Nov. 1994 [doi>10.1006/jpdc.1994.1132]
• 15: William J. Dally, Performance Analysis of k-ary n-cube Interconnection Networks, IEEE Transactions on Computers, v.39 n.6, p.775-785, June 1990 [doi>10.1109/12.53599]
• 16: William J. Dally, Virtual-channel flow control, Proceedings of the 17th annual international symposium on Computer Architecture, p.60-68, May 28-31, 1990, Seattle, Washington, United States
• 17: L. Kleinrock. Queuing Systems, volume 1: Theory, John Wiley & Sons Inc, New York, 1975
• 18: OPNET modeler (www.opnet.com)