Computation and communication refinement for multiprocessor SoC design: A system-level perspective

ABSTRACT

Continuous advancements in semiconductor technology enable the design of complex systems-on-chips (SoCs) composed of tens or hundreds of IP cores. At the same time, the applications that need to run on such platforms have become increasingly complex and have tight power and performance requirements. Achieving a satisfactory design quality under these circumstances is only possible when both computation and communication refinement are performed efficiently, in an automated and synergistic manner. Consequently, formal and disciplined system-level design methodologies are in great demand for future multiprocessor design. This article provides a broad overview of some fundamental research issues and state-of-the-art solutions concerning both computation and communication aspects of system-level design. The methodology we advocate consists of developing abstract application and platform models, followed by application mapping onto the target platform, and then optimizing the overall system via performance analysis. In addition, a communication refinement step is critical for optimizing the communication infrastructure in this multiprocessor setup. Finally, simulation and prototyping can be used for accurate performance evaluation purposes.

REFERENCES

• 1: Adrijean Andriahantenaina , Alain Greiner, Micro-Network for SoC: Implementation of a 32-Port SPIN network, Proceedings of the conference on Design, Automation and Test in Europe, p.11128, March 03-07, 2003
• 2: Giuseppe Ascia , Vincenzo Catania , Maurizio Palesi, Multi-objective mapping for mesh-based NoC architectures, 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.1016765]
• 3: Bailey, N. 1975. The Mathematical Theory of Infectious Diseases, 2nd ed. Charles Griffin, London.
• 4: Felice Balarin , Yosinori Watanabe , Harry Hsieh , Luciano Lavagno , Claudio Passerone , Alberto Sangiovanni-Vincentelli, Metropolis: An Integrated Electronic System Design Environment, Computer, v.36 n.4, p.45-52, April 2003 [doi>10.1109/MC.2003.1193228 ]
• 5: Bartic, T. A., Mignolet, J.-Y., Nollet, V., Marescaux, T., Verkest, D., Vernalde, S., and Lauwereins, R. 2003. Highly scalable network on chip for reconfigurable systems. In Proceedings of the International Symposium on System-on-Chip.
• 6: 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 ]
• 7: Beran, J. 1994. Statistics for Long-Memory Processes. Chapman & Hall, London.
• 8: Bergstra, J. A. and Klop, J. W. 1985. Algebra of communicating processes with abstraction. Theoretical Comput. Sci. 37, 1.
• 9: D. Bertozzi , L. Benini , G. de Micheli, Low Power Error Resilient Encoding for On-Chip Data Buses, Proceedings of the conference on Design, automation and test in Europe, p.102, March 04-08, 2002
• 10: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 11: Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Coping with Latency in SOC Design, IEEE Micro, v.22 n.5, p.24-35, September 2002 [doi>10.1109/MM.2002.1044297 ]
• 12: Vikas Chandra , Anthony Xu , Herman Schmit , Larry Pileggi, An Interconnect Channel Design Methodology for High Performance Integrated Circuits, Proceedings of the conference on Design, automation and test in Europe, p.21138, February 16-20, 2004
• 13: Ge-Ming Chiu, The Odd-Even Turn Model for Adaptive Routing, IEEE Transactions on Parallel and Distributed Systems, v.11 n.7, p.729-738, July 2000 [doi>10.1109/71.877831 ]
• 14: Cristian Constantinescu, Dependability Analysis of a Fault-Tolerant Processor, Proceedings of the 2001 Pacific Rim International Symposium on Dependable Computing, p.63, December 17-19, 2001
• 15: Cristian Constantinescu, Impact of Deep Submicron Technology on Dependability of VLSI Circuits, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.205-209, June 23-26, 2002
• 16: 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]
• 17: Jose Duato , Sudhakar Yalamanchili , Ni Lionel, Interconnection Networks: An Engineering Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2002
• 18: Tudor Dumitras , Radu Marculescu, On-Chip Stochastic Communication, Proceedings of the conference on Design, Automation and Test in Europe, p.10790, March 03-07, 2003
• 19: System Design: Traditional Concepts and New Paradigms, Proceedings of the 1999 IEEE International Conference on Computer Design, p.2, October 10-13, 1999
• 20: David Flynn, AMBA: Enabling Reusable On-Chip Designs, IEEE Micro, v.17 n.4, p.20-27, July 1997 [doi>10.1109/40.612211 ]
• 21: Marc Geilen , Twan Basten , Sander Stuijk, Minimising buffer requirements of synchronous dataflow graphs with model checking, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065796]
• 22: Christopher J. Glass , Lionel M. Ni, The turn model for adaptive routing, Journal of the ACM (JACM), v.41 n.5, p.874-902, Sept. 1994 [doi>10.1145/185675.185682]
• 23: Norbert Götz , Ulrich Herzog , Michael Rettelbach, Multiprocessor and Distributed System Design: The Integration of Functional Specification and Performance Analysis Using Stochastic Process Algebras, Performance Evaluation of Computer and Communication Systems, Joint Tutorial Papers of Performance '93 and Sigmetrics '93, p.121-146, May 10-14, 1993
• 24: Hedetniemi, S. M., Hedetniemi, S. T., and Liestman, A. L. 1988. A survey of gossiping and broadcasting in communication networks. Networks 18, 4, 319--359.
• 25: Hemani, A., Jantsch, A., Kumar, S., Postula, A., Oberg, J., Millberg, M., and Lindqvist, D. 2000. Network on a chip: An architecture for billion transistor era. In Proceedings of the IEEE NorChip Conference.
• 26: Jane Hillston, A compositional approach to performance modelling, Cambridge University Press, New York, NY, 1996
• 27: Horst, R., Jewett, D., and Lenowski, D. 1993. The risk of data corruption in microprocessor based systems. In Proceedings of the 23rd International Symposium on Fault-Tolerant Computing.
• 28: Jingcao Hu , Radu Marculescu, DyAD: smart routing for networks-on-chip, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA [doi>10.1145/996566.996638]
• 29: 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]
• 30: Hu, J. and Marculescu, R. 2005a. Communication and task scheduling of application-specific Networks-on-chip. IEE Proceedings Comput. Digital Techniques. 152, 5, 643--651.
• 31: Hu, J. and Marculescu, R. 2005b. Energy- and performance-aware mapping for regular NoC architectures. IEEE Trans. Comput. Aided Des. Integrated Circuits Syst. 24, 4.
• 32: Hu, J., Ogras, U. Y., and Marculescu, R. System-level buffer allocation for application-specific Networks-on-Chip router design. IEEE Trans Comput. Aided Des. Integrated Circuits Syst. To appear.
• 33: W. Hung , C. Addo-Quaye , T. Theocharides , Y. Xie , N. Vijaykrishnan , M. J. Irwin, Thermal-Aware IP Virtualization and Placement for Networks-on-Chip Architecture, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.430-437, October 11-13, 2004
• 34: IBM CoreConnect. 2006. http://www.chips.ibm.com/products/powerpc/cores.
• 35: 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
• 36: Axel Jantsch , Hannu Tenhunen, Networks on chip, Kluwer Academic Publishers, Hingham, MA, 2003
• 37: Kahn, G.1974. The semantics of a simple language for parallel programming. In Information Processing, J. L. Rosenfeld, ed. Stockholm, Sweden.
• 38: Jong Kim , Kang G. Shin, Execution Time Analysis of Communicating Tasks in Distributed Systems, IEEE Transactions on Computers, v.45 n.5, p.572-579, May 1996 [doi>10.1109/12.509908 ]
• 39: Lee, E. and Messerschmitt, D. 1987. Synchronous dataflow. In Proc. IEEE 75, 9, 1235--1245.
• 40: Lee, E. and Parks, T. M. 1995. Dataflow process networks. Proc. IEEE 83, 5.
• 41: Hyung Gyu Lee , Umit Y. Ogras , Radu Marculescu , Naehyuck Chang, Design space exploration and prototyping for on-chip multimedia applications, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA [doi>10.1145/1146909.1146949]
• 42: Paul Lieverse , Pieter Van Der Wolf , Kees Vissers , Ed Deprettere, A Methodology for Architecture Exploration of Heterogeneous Signal Processing Systems, Journal of VLSI Signal Processing Systems, v.29 n.3, p.197-207, November 2001 [doi>10.1023/A:1012231429554 ]
• 43: Tao Lin , Lawrence T. Pileggi, Throughput-driven IC communication fabric synthesis, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.274-279, November 10-14, 2002, San Jose, California [doi>10.1145/774572.774613]
• 44: Wojciech Maly, IC design in high-cost nanometer-technologies era, Proceedings of the 38th conference on Design automation, p.9-14, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378249]
• 45: Sorin Manolache , Petru Eles , Zebo Peng, Fault and energy-aware communication mapping with guaranteed latency for applications implemented on NoC, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA [doi>10.1145/1065579.1065648]
• 46: Radu Marculescu , Amit Nandi , Luciano Lavagno , Alberto Sangiovanni-Vincentelli, System-level power/performance analysis of portable multimedia systems communicating over wireless channels, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 47: Alexander Maxiaguine , Simon Künzli , Samarjit Chakraborty , Lothar Thiele, Rate analysis for streaming applications with on-chip buffer constraints, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.131-136, January 27-30, 2004, Yokohama, Japan
• 48: R. Milner, Communication and Concurrency, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 49: Prabhat Mishra , Aviral Shrivastava , Nikil Dutt, Architecture description language (ADL)-driven software toolkit generation for architectural exploration of programmable SOCs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.3, p.626-658, July 2006
• 50: Morgenstein, A. 2004. Comparative analysis of serial vs. parallel links in networks on chip. In Proceedings of the International Symposium on Systems on Chip.
• 51: 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
• 52: 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]
• 53: Amit Nandi , Radu Marculescu, System-level power/performance analysis for embedded systems design, Proceedings of the 38th conference on Design automation, p.599-604, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379032]
• 54: Lionel M. Ni , Philip K. McKinley, A Survey of Wormhole Routing Techniques in Direct Networks, Computer, v.26 n.2, p.62-76, February 1993 [doi>10.1109/2.191995 ]
• 55: Norros, I. 1994. A storage model with self-similar input. Queueing Syst. 16, 3--4, 387--396.
• 56: Umit Y. Ogras , Jingcao Hu , Radu Marculescu, Key research problems in NoC design: a holistic perspective, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, p.69-74, September 19-21, 2005, Jersey City, NJ, USA [doi>10.1145/1084834.1084856]
• 57: U. Y. Ogras , R. Marculescu, Application-specific network-on-chip architecture customization via long-range link insertion, Proceedings of the 2005 IEEE/ACM International conference on Computer-aided design, p.246-253, November 06-10, 2005, San Jose, CA
• 58: Umit Y. Ogras , Radu Marculescu, Energy- and Performance-Driven NoC Communication Architecture Synthesis Using a Decomposition Approach, Proceedings of the conference on Design, Automation and Test in Europe, p.352-357, March 07-11, 2005 [doi>10.1109/DATE.2005.137]
• 59: Umit Y. Ogras , Radu Marculescu , Hyung Gyu Lee , Naehyuck Chang, Communication architecture optimization: making the shortest path shorter in regular networks-on-chip, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
• 60: Ogras, U. Y. and Marculescu, R. 2006a. It's a small world after all; NoC performance optimization via long link insertion. IEEE Trans. Very Large Scale Integrat. Syst. (Special Section Hardware/ Software Codesign and System Synthesis.)
• 61: Open Core Protocol International Partnership (OCP-IP).2006. OCP datasheet. http://www. ocpip.org.
• 62: James Lyle Peterson, Petri Net Theory and the Modeling of Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1981
• 63: 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
• 64: Alessandro Pinto , Alvise Bonivento , Allberto L. Sangiovanni-Vincentelli , Roberto Passerone , Marco Sgroi, System level design paradigms: Platform-based design and communication synthesis, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.3, p.537-563, July 2006
• 65: Pirretti, M. 2004. Fault tolerant algorithms for network-on-chip interconnect. In Proceedings of the IEEE Computer Society Annual Symposium on VLSI.
• 66: Brigitte Plateau , Karim Atif, Stochastic Automata Network of Modeling Parallel Systems, IEEE Transactions on Software Engineering, v.17 n.10, p.1093-1108, October 1991 [doi>10.1109/32.99196 ]
• 67: Brigitte Plateau , Jean-Michel Fourneau, A methodology for solving Markov models of parallel systems, Journal of Parallel and Distributed Computing, v.12 n.4, p.370-387, Aug. 1991 [doi>10.1016/0743-7315(91)90007-V]
• 68: Paul Pop , Petru Eles , Zebo Peng , Traian Pop, Analysis and optimization of distributed real-time embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.3, p.593-625, July 2006
• 69: Saastamoinen, I., Alho, M., and Nurmi, J. 2003. Buffer implementation for proteo network-on-chip. In Proceedings of the International Symposium on Circuits and Systems.
• 70: Semiconductor Association. 2003. The International Technology Roadmap for Semiconductors (ITRS).
• 71: Shang, L., Peh, L. S., and Jha, N. K. 2006. POWERHERD: A distributed scheme for dynamic satisfying peak power constraints in interconnection networks. IEEE Trans. Comput.-Aided Des. Integrated Circuits Syst. 25, 1, 92--110.
• 72: Krishnan Srinivasan , Karam S. Chatha , Goran Konjevod, Linear Programming based Techniques for Synthesis of Network-on-Chip Architectures, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.422-429, October 11-13, 2004
• 73: Sundararajan Sriram , Shuvra S. Bhattacharyya, Embedded Multiprocessors: Scheduling and Synchronization, Marcel Dekker, Inc., New York, NY, 2000
• 74: Stewart, W. 1994. An Introduction to the Numerical Solution of Markov Chains. Princeton University Press, N.J.
• 75: Stewart, W., Atif, K., and Plateau, B. 1995. The numerical solution of stochastic automata networks. In European J. Operational Research 86, 503--525.
• 76: Kishar Shridharbhai Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1982
• 77: 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]
• 78: Guang Yang , Alberto Sangiovanni-Vincentelli , Yosinori Watanabe , Felice Balarin, Separation of concerns: overhead in modeling and efficient simulation techniques, Proceedings of the 4th ACM international conference on Embedded software, September 27-29, 2004, Pisa, Italy [doi>10.1145/1017753.1017765]
• 79: Terry Tao Ye , Giovanni De Micheli , Luca Benini, Analysis of power consumption on switch fabrics in network routers, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA [doi>10.1145/513918.514051]
• 80: Ye, T. T. and De Micheli, G. 2003. Physical planning for multiprocessor networks and switch fabrics. In Proceedings of the IEEE International Conference on Application-Specific Systems, Architectures, and Processors.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: VLSI (very large scale integration)

  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.4 VLSI Systems

General Terms:
Design, Performance

Keywords:
Embedded systems, Markov chains, communication, energy optimization, networks-on-chip, performance analysis, prototype, systems-on-chip, traffic