Object-oriented cosynthesis of distributed embedded systems

ABSTRACT

This article describes a new hardware-software cosynthesis algorithm that takes advantage of the structure inherent in an object-oriented specification. The algorithm creates a distributed system implementation with arbitrary topology, using the object-oriented structure to partition functionality in addition to scheduling and allocating processes. Process partitioning is an especially important optimization for such systems because the specification will not, in general, take into account the process structure required for efficient execution on the distributed engine. The object-oriented specification naturally provides both coarse-grained and fine-grained partitions of the system. Our algorithm uses that multilevel structure to guide synthesis. Experimental results show that our algorithm takes advantage of the object-oriented specification to quickly converge on high-quality implementations.

REFERENCES

• 1: Grady Booch, Object oriented design with applications, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1990
• 2: Jean Paul Calvez , Alan Wyche , Charles Edmundson, Embedded real-time systems, John Wiley & Sons, Inc., New York, NY, 1993
• 3: 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
• 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: DASARATHY, B. AND FERIDUN, M. 1984. Task allocation problems in the synthesis of distributed real-time systems. In Proceedings, IEEE 1984 Real-Time Systems Symposium, IEEE, Piscataway, NJ, 135-144.
• 6: 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]
• 7: 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]
• 8: James P. Huang, Modeling of software partition for distributed real-time applications, IEEE Transactions on Software Engineering, v.11 n.10, p.1113-1126, Oct. 1985 [doi>10.1109/TSE.1985.231859]
• 9: ISMAIL, T. B., O'BRIEN, K., AND JERRAYA, A. 1994. Interactive system-level partitioning with PARTIF. In Proceedings, EDAC '94, IEEE Computer Society Press, Los Alamitos, CA.
• 10: LAGNESE, E. D. AND THOMAS, D.E. 1991. Architectural partitioning of system level synthesis of integrated circuits. IEEE Trans. CAD/ICAS 10, 7 (July), 847-860.
• 11: C. L. Liu , James W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment, Journal of the ACM (JACM), v.20 n.1, p.46-61, Jan. 1973 [doi>10.1145/321738.321743]
• 12: PRAKASH, S. AND PARKER, A.C. 1992. SOS: Synthesis of application-specific heterogeneous multiprocessor systems. J. Parallel Distrib. Comput. 16, 338-351.
• 13: Roger S. Pressman, Software engineering (3rd ed.): a practitioner's approach, McGraw-Hill, Inc., New York, NY, 1992
• 14: K. Ramamritham , J. A. Stankovic , P. F. Shiah, Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, v.1 n.2, p.184-194, April 1990 [doi>10.1109/71.80146]
• 15: James Rumbaugh , Michael Blaha , William Premerlani , Frederick Eddy , William Lorensen, Object-oriented modeling and design, Prentice-Hall, Inc., Upper Saddle River, NJ, 1991
• 16: Bran Selic , Garth Gullekson , Paul T. Ward, Real-time object-oriented modeling, John Wiley & Sons, Inc., New York, NY, 1994
• 17: Sally Shlaer , Stephen J. Mellor, Object lifecycles: modeling the world in states, Yourdon Press, Upper Saddle River, NJ, 1992
• 18: 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
• 19: WOLF, W. 1994. Hardware-software co-design of embedded systems. Proc. IEEE 82, 7 (July) 967-989.
• 20: 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]
• 21: 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]
• 22: 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
• 23: Pamela Zave, A Compositional Approach to Multiparadigm Programming, IEEE Software, v.6 n.5, p.15-25, September 1989 [doi>10.1109/52.35586]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Microprocessor/microcomputer applications

General Terms:
Design

Keywords:
distributed embedded systems, hardware-software co-design, object-oriented co-synthesis