Mapping and physical planning of networks-on-chip architectures with quality-of-service guarantees

ABSTRACT

Networks on Chips (NoCs) have evolved as the communication design paradigm of future Systems on Chips (SoCs). In this work we target the NoC design of complex SoCs with heterogeneous processor/memory cores, providing Quality-of-Service (QoS) for the application. We present an integrated approach to mapping of cores onto NoC topologies and physical planning of NoCs, where the position and size of the cores and network components are computed. Our design methodology automates NoC mapping, physical planning, topology selection, topology optimization and instantiation, bridging an important design gap in building application specific NoCs. We also present a methodology to guarantee QoS for the application during the mapping-physical planning process by satisfying the delay/jitter constraints and real-time constraints of the traffic streams. Experimental studies show large area savings (up to 2x), bandwidth savings (up to 5x) and network component savings (up to 2.2x in buffer count, 3.8x in number of wires, 1.6x in switch ports) compared to traditional design approaches.

REFERENCES

• 1: William J. Dally , Brian Towles, Route packets, net wires: on-chip inteconnectoin networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 2: Luca Benini , Giovanni De Micheli, Networks on Chips: A New SoC Paradigm, Computer, v.35 n.1, p.70-78, January 2002 [doi>10.1109/2.976921]
• 3: Faraydon Karim , Anh Nguyen , Sujit Dey , Ramesh Rao, On-chip communication architecture for OC-768 network processors, Proceedings of the 38th conference on Design automation, p.678-683, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379047]
• 4: S. Kumar et al., "A network on chip architecture and design methodology", ISVLSI 2002, pp. 105--112, 2002.
• 5: 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]
• 6: E. Rijpkema , K. G. W. Goossens , A. Radulescu , J. Dielissen , J. van Meerbergen , P. Wielage , E. Waterlander, Trade Offs in the Design of a Router with Both Guaranteed and Best-Effort Services for Networks on Chip, Proceedings of the conference on Design, Automation and Test in Europe, p.10350, March 03-07, 2003
• 7: Xinping Zhu , Sharad Malik, A hierarchical modeling framework for on-chip communication architectures, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.663-671, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774670]
• 8: Jian Liang , Sriram Swaminathan , Russell Tessier, aSOC: A Scalable, Single-Chip Communications Architecture, Proceedings of the 2000 International Conference on Parallel Architectures and Compilation Techniques, p.37, October 15-19, 2000
• 9: D. Siguenza-Tortosa, J. Nurmi, "Proteo: A New Approach to Network-on-Chip", in CSN 02, Sep. 2002.
• 10: Axel Jantsch , Hannu Tenhunen, Networks on chip, Kluwer Academic Publishers, Hingham, MA, 2003
• 11: S. J. Krolikoski et al., "Methodology and Technology for Virtual Component Driven Hardware/Software Co-Design on the System-Level", ISCAS, June 1999.
• 12: E. B. Van der Tol, E. G. T. Jaspers, "Mapping of MPEG-4 Decoding on a Flexible Architecture Platform", SPIE 2002, pp. 1--13, Jan, 2002.
• 13: Alessandro Pinto , Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Efficient Synthesis of Networks On Chip, Proceedings of the 21st International Conference on Computer Design, p.146, October 13-15, 2003
• 14: Wai Hong Ho , Timothy Mark Pinkston, A Methodology for Designing Efficient On-Chip Interconnects on Well-Behaved Communication Patterns, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.377, February 08-12, 2003
• 15: Jingcao Hu , Radu Marculescu, Energy-aware mapping for tile-based NoC architectures under performance constraints, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan [doi>10.1145/1119772.1119818]
• 16: Jingcao Hu , Radu Marculescu, Exploiting the Routing Flexibility for Energy/Performance Aware Mapping of Regular NoC Architectures, Proceedings of the conference on Design, Automation and Test in Europe, p.10688, March 03-07, 2003
• 17: K. Lahiri, A. Raghunathan, S. Dey, "System-Level Performance Analysis for Designing On-Chip Communication Architectures", IEEE TCAD, vol. 20, no. 6, pp. 768--783, June 2001.
• 18: Antoine Jalabert , Srinivasan Murali , Luca Benini , Giovanni De Micheli, ×pipesCompiler: A Tool for Instantiating Application Specific Networks on Chip, Proceedings of the conference on Design, automation and test in Europe, p.20884, February 16-20, 2004
• 19: A. Radulescu et al., "An Efficient On-Chip Network Interface Offering Guaranteed Services, Shared-Memory Abstraction & Flexible Network Programming", DATE 2004.
• 20: Srinivasan Murali , Giovanni De Micheli, Bandwidth-Constrained Mapping of Cores onto NoC Architectures, Proceedings of the conference on Design, automation and test in Europe, p.20896, February 16-20, 2004
• 21: Srinivasan Murali , Giovanni De Micheli, SUNMAP: a tool for automatic topology selection and generation for NoCs, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996809]
• 22: Girish V. Varatkar , Radu Marculescu, On-chip traffic modeling and synthesis for MPEG-2 video applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.1, p.108-119, January 2004 [doi>10.1109/TVLSI.2003.820523]
• 23: T. T. Ye, G. De Micheli, "Physical Planning for Multiprocessor Networks and Switch Fabrics", ASAP, 2003.
• 24: J. G. Kim, Y. D. Kim, "A linear programming-based algorithm for floorplanning in VLSI design", IEEE TCAD, pp. 584--592, Vol. 22, Issue: 5, May 2003.
• 25: William Dally , Brian Towles, Principles and Practices of Interconnection Networks, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 26: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 27: E. D. Taillard, "Robust tabu search for the quadratic assignment problem", Parallel Computing 17, pp. 443--455, 1991.

INDEX TERMS

Keywords:
QoS, mapping, networks on chips, optimization, physical planning, systems on chips