CMAPS: a cosynthesis methodology for application-oriented parallel systems

ABSTRACT

Currently, a lot of research is devoted to system design, and little work is done on requirements analysis. Besides going from specification to design, one of our main objectives is to show how an application problem can be transformed into specifications. Working from the hardware-software codesign perspective, a system is designed starting from an application problem itself, rather than the detailed behavioral specifications. Given an application problem specified as a directed acyclic graph of elementary problems, a hardware-software solution is derived such that the synthesized software, a parallel pseudoprogram, can be scheduled and executed on the synthesized software, a parallel pseudoprogram, can be scheduled and executed on the synthesized hardware, a set of system-level parallel computer specifications, with heuristically optimal performance. This is known as system-level cosynthesis of application-oriented general-purpose parallel systems for which a novel methodology called Cosynthesis Methodology for Applicaton-Oriented Parallel Systems (CMAPS), is presented. Since parallel programs and multiprocessor architectures are largely interdependent, CMAPS explores the relationship between hardware designs and software algorithms by interleaving the modeling phases and the synthesis phases of both hardware and software. High scalability in terms of problem complexity and easy upgradability to new technologies are achieved through modularization of the input problem specification, of the software algorithms, and of the hardware subsystem models. The work presented in this paper will be beneficial to designers of general-purpose parallel computer systems which must be oriented toward solving some user-specified problem such as the global controller of an industry automation process or a multiprocessor video server. Some application examples are given to illustrate various codesign phases of CMAPS and its feasibility.

REFERENCES

• 1: Selim G. Akl, The design and analysis of parallel algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1989
• 2: Jean-Michel Berge, Hardware - Software Codesign and Co-Verification, Kluwer Academic Publishers, Norwell, MA, 1997
• 3: W. P. Birmingham , A. P. Gupta , D. P. Siewiorek, The MICON system for computer design, Proceedings of the 26th ACM/IEEE conference on Design automation, p.135-140, June 25-28, 1989, Las Vegas, Nevada, United States [doi>10.1145/74382.74406]
• 4: W. W. Chu , M.-T. Lan, Task allocation and precedence relations for distributed real-time systems, IEEE Transactions on Computers, v.36 n.6, p.667-679, June 1987 [doi>10.1109/TC.1987.1676960]
• 5: Rolf Ernst , Jorg Henkel , Thomas Benner, Hardware-Software Cosynthesis for Microcontrollers, IEEE Design & Test, v.10 n.4, p.64-75, October 1993 [doi>10.1109/54.245964]
• 6: FLYNN, M. J. 1972. Some computer organizations and their effectiveness. IEEE Trans. Comput. C-21, 9 (Sept. 1972), 948-960.
• 7: Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
• 8: GADIENT,A.J.AND THOMAS, D. E. 1993. A dynamic approach to controlling high-level synthesis CAD tools. IEEE Trans. Very Large Scale Integr. Syst. 1, 3 (Sept.), 328-341.
• 9: GRAHAM, R. L. 1969. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math. 17 (1969), 416-429.
• 10: GUPTA,A.P.,BIRMINGHAM,W.P.,AND SIEWIOREK, D. P. 1993. Automating the design of computer systems. IEEE Trans. Comput.-Aided Des. Integr. Circuits 12, 4 (Apr.), 473-487.
• 11: Rajesh K. Gupta , Giovanni De Micheli, Hardware-Software Cosynthesis for Digital Systems, IEEE Design & Test, v.10 n.3, p.29-41, July 1993 [doi>10.1109/54.232470]
• 12: Tim J. Harris, A survey of PRAM simulation techniques, ACM Computing Surveys (CSUR), v.26 n.2, p.187-206, June 1994 [doi>10.1145/176979.176984]
• 13: Pao-Ann Hsiung , Chung-Hwang Chen , Trong-Yen Lee , Sao-Jie Chen, ICOS: an intelligent concurrent object-oriented synthesis methodology for multiprocessor systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.2, p.109-135, April 1998 [doi>10.1145/290833.290834]
• 14: Pao-Ann Hsiung , Sao-Jie Chen , Tsung-Chien Hu , Shih-Chiang Wang, PSM: an object-oriented synthesis approach to multiprocessor system design, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.4 n.1, p.83-97, March 1996 [doi>10.1109/92.486083]
• 15: HSIUNG, P.-A., LEE, T.-Y., AND CHEN, S.-J. 1997. MOBnet: An extended Petri net model for the concurrent object-oriented system-level synthesis of multiprocessor systems. IEICE Trans. Inf. Syst. E80-D, 2 (Feb.), 232-242.
• 16: Pao-Ann Hsiung , Trong-Yen Lee , Sao-Jie Chen, Object-Oriented Technology Transfer to Multiprocessor System-Level Synthesis, Proceedings of the Technology of Object-Oriented Languages and Systems-Tools - 24, p.284, September 01-01, 1997
• 17: Kai Hwang, Advanced Computer Architecture: Parallelism,Scalability,Programmability, McGraw-Hill Higher Education, 1992
• 18: Asawaree Kalavade , Edward A. Lee, A Hardware-Software Codesign Methodology for DSP Applications, IEEE Design & Test, v.10 n.3, p.16-28, July 1993 [doi>10.1109/54.232469]
• 19: Sanjaya Kuman , James H. Aylor , Barry W. Johnson , Wm. A. Wulf, A Framework for Hardware/Software Codesign, Computer, v.26 n.12, p.39-45, December 1993 [doi>10.1109/2.247650]
• 20: Jiann-Fu Linn , Sao-Jie Chen, Analysis of multiprocessor task scheduling, Computer Systems Science and Engineering, v.11 n.2, p.117-120, March 1996
• 21: LIN, J. -F., SEE, W. -B., AND CHEN, S. -J. 1995. Performance bounds on scheduling parallel tasks with communication cost. IEICE Trans. Inf. Syst. (Mar. 1995), 263-268.
• 22: PRAKASH,S.AND PARKER, A. C. 1992. SOS: synthesis of application-specific heterogeneous multiprocessor systems. J. Parallel Distrib. Comput. 16, 4 (Dec.), 338-351.
• 23: Jerry Rozenblit , Jerzy Rozenblit , Buchenrieder Klaus, Computer Aided Software/Hardware Engineering, IEEE Press, Piscataway, NJ, 1994
• 24: Donald E. Thomas , Jay K. Adams , Herman Schmit, A Model and Methodology for Hardware-Software Codesign, IEEE Design & Test, v.10 n.3, p.6-15, July 1993 [doi>10.1109/54.232468]
• 25: ULLMAN, J. 1975. NP-complete scheduling problems. J. Comput. Syst. Sci. 10, 384-393.
• 26: Frank Vahid , Daniel D. Gajski , Jie Gong, A binary-constraint search algorithm for minimizing hardware during hardware/software partitioning, Proceedings of the conference on European design automation, p.214-219, September 19-23, 1994, Grenoble, France
• 27: WOLF, W. 1994. Hardware-software co-design of embedded systems. Proc. IEEE 82, 7 (July 1994), 967-989.
• 28: Wayne Wolf, Object-oriented cosynthesis of distributed embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.3, p.301-314, July 1996 [doi>10.1145/234860.234861]
• 29: Wayne H. Wolf, An architectural co-synthesis algorithm for distributed, embedded computing systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.5 n.2, p.218-229, June 1997 [doi>10.1109/92.585225]
• 30: Xun Xiong , Edna Barros , Wolfgang Rosenstiel, A method for partitioning UNITY language in hardware and software, Proceedings of the conference on European design automation, p.220-225, September 19-23, 1994, Grenoble, France
• 31: Ti-Yen Yen , Wayne Wolf, Communication synthesis for distributed embedded systems, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.288-294, November 05-09, 1995, San Jose, California, United States
• 32: Ti-Yen Yen , Wayne Wolf, Sensitivity-driven co-synthesis of distributed embedded systems, Proceedings of the 8th international symposium on System synthesis, p.4-9, September 13-15, 1995, Cannes, France [doi>10.1145/224486.224488]
• 33: Ti-Yen Yen , Wayne Wolf, Hardware-Software Co-Synthesis of Distributed Embedded Systems, Kluwer Academic Publishers, Norwell, MA, 1996

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Systems specification methodology; System architectures
  C.1 PROCESSOR ARCHITECTURES
  C.5 COMPUTER SYSTEM IMPLEMENTATION

General Terms:
Design

Keywords:
application-oriented general-purpose multiprocessors, hardware-software modeling and cosynthesis, requirements analysis