Automatic synthesis of system on chip multiprocessor architectures for process networks

ABSTRACT

In this paper, we present an approach for automatic synthesis of System on Chip (SoC) multiprocessor architectures for applications expressed as process networks. Our approach is targeted towards design space exploration (DSE) and thus the speed of synthesis is of critical interest. The focus here is on the problem of resource allocation and binding with a view to optimize cost under performance constraints. Our approach exploits adjacency relation of processes and uses a dynamic programming based algorithm to synthesize the architecture including interconnection network. We have done a number of experiments on real as well as randomly generated process networks. The results have been compared with an optimal MILP formulation. They conclusively show that this approach is fast as well as effective and can be employed for DSE.

REFERENCES

• 1: Gills Kahn. The Semantics of a Simple Language for Parallel Programming. In Proc. IFIP Congress 74. North Holland Publishing Co, 1974.
• 2: E. A. de Kock , W. J. M. Smits , P. van der Wolf , J.-Y. Brunel , W. M. Kruijtzer , P. Lieverse , K. A. Vissers , G. Essink, YAPI: application modeling for signal processing systems, Proceedings of the 37th conference on Design automation, p.402-405, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337511]
• 3: Todor Stefanov , Ed Deprettere, Deriving process networks from weakly dynamic applications in system-level design, Proceedings of the 1st IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, October 01-03, 2003, Newport Beach, CA, USA [doi>10.1145/944645.944673]
• 4: Bharat P. Dave , Ganesh Lakshminarayana , Niraj K. Jha, COSYN: hardware-software co-synthesis of heterogeneous distributed embedded systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.7 n.1, p.92-104, March 1999 [doi>10.1109/92.748204]
• 5: Jui-Ming Chang and Massoud Pedram. Codex-dp: Co-design of Communicating Systems Using Dynamic Programming. IEEE Trans. on CAD, 19(7):732--744, July 2000.
• 6: Jiong Luo , Niraj K. Jha, Low Power Distributed Embedded Systems: Dynamic Voltage Scaling and Synthesis, Proceedings of the 9th International Conference on High Performance Computing, p.679-692, December 18-21, 2002
• 7: Dongkun Shin , Jihong Kim, Power-aware scheduling of conditional task graphs in real-time multiprocessor systems, Proceedings of the 2003 international symposium on Low power electronics and design, August 25-27, 2003, Seoul, Korea [doi>10.1145/871506.871607]
• 8: Yu-Kwong Kwok , Ishfaq Ahmad, Static scheduling algorithms for allocating directed task graphs to multiprocessors, ACM Computing Surveys (CSUR), v.31 n.4, p.406-471, Dec. 1999 [doi>10.1145/344588.344618]
• 9: Andy D. Pimentel , Louis O. Hertzberger , Paul Lieverse , Pieter van der Wolf , Ed F. Deprettere, Exploring Embedded-Systems Architectures with Artemis, Computer, v.34 n.11, p.57-63, November 2001 [doi>10.1109/2.963445]
• 10: E. A. de Kock, Multiprocessor mapping of process networks: a JPEG decoding case study, Proceedings of the 15th international symposium on System Synthesis, October 02-04, 2002, Kyoto, Japan [doi>10.1145/581199.581216]
• 11: Thomas Martyn Parks, Bounded scheduling of process networks, University of California at Berkeley, Berkeley, CA, 1996
• 12: Twan Basten and Jan Hoogerbrugge. Efficient Execution of Process Networks. In Communicating Process Architectures, 2001.
• 13: PROPHID: a heterogeneous multi-processor architecture for multimedia, Proceedings of the 1997 International Conference on Computer Design (ICCD '97), p.164, October 12-15, 1997
• 14: J. A. J. Leijten , J. L. van Meerbergen , A. H. Timmer , J. A. G. Jess, Stream communication between real-time tasks in a high-performance multiprocessor, Proceedings of the conference on Design, automation and test in Europe, p.125-131, February 23-26, 1998, Le Palais des Congrés de Paris, France
• 15: Information technology -- Generic coding of moving pictures and associated audio information: Video. ISO/IEC 13818-2, 1996.
• 16: Basant K. Dwivedi, Anshul Kumar, and M. Balakrishnan. Synthesis of Application Specific Multiprocessor Architectures for Process Networks . Technical report, Dept. of Computer Science & Engg., Indian Institute of Technology Delhi, 2003.
• 17: Manoj Kumar Jain , M. Balakrishnan , Anshul Kumar, An efficient technique for exploring register file size in ASIP synthesis, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France [doi>10.1145/581630.581671]
• 18: http://www.arm.com.
• 19: http://www.gaisler.com/leon.html.
• 20: Basant Kumar Dwivedi, Harsh Dhand, M. Balakrishnan, and Anshul Kumar. RPNG: A Tool for Random Process Network Generation. Technical report, Dept. of Computer Science & Engg., Indian Institute of Technology Delhi, 2004.
• 21: http://www.intel.com/products/server/processors.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

General Terms:
Design, Performance

Keywords:
Kahn process networks, application specific multiprocessors, partitioning