Sensitivity-driven co-synthesis of distributed embedded systems

ABSTRACT

Abstract: Describes a new, sensitivity-driven algorithm for the co-synthesis of real-time distributed embedded systems. Many embedded computing systems are distributed systems: communicating periodic processes executing on several CPUs/ASICs connected by communication links. We use performance estimates to compute a local sensitivity of the design to process allocation. We propose a priority prediction method to schedule processes. Based on these techniques, we develop a gradient-search algorithm which co-synthesizes heterogeneous distributed systems of arbitrary topology and the associated application software architecture. Experimental results show that our algorithm can find good implementation architectures in small amounts of CPU time.

REFERENCES

• 1: 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]
• 2: Joseph G. D'Ambrosio , Xiaobo (Sharon) Hu, Configuration-level hardware/software partitioning for real-time embedded systems, Proceedings of the 3rd international workshop on Hardware/software co-design, September 22-24, 1994, Grenoble, France
• 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: 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]
• 5: 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]
• 6: C. J. Hou and K. G. Shin. Allocation of periodic task modules with precedence and deadline constraints in distributed real-time systems. In Proceedings, Real- Time Systems Symposium, 1982.
• 7: J. Y.-T. Leung and J. Whitehead. On the complexity of fixed-priority scheduling of periodic, real-time tasks. Performance Evaluation, 2, 1982.
• 8: 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]
• 9: M. C. McFarland, A. C. Parker, and R. Camposano. The high-level synthesis of digital systems. Proceedings of the IEEE, 78(2), February 1990.
• 10: D.-T. Peng and K. G. Shin. Static allocation of periodic tasks with precedence constraints. In Proceedings, International Conference on Distributed Computing Systems, 1989.
• 11: S. Prakash and A. C. Parker. SOS: synthesis of application-specific heterogeneous multiprocessor systems. Journal of Parallel and Distributed Computing, 16, 1992.
• 12: K. Ramamritham. Allocation and scheduling of complex periodic tasks. In Proceedings, International Conference on Distributed Computing Systems, 1990.
• 13: K. Ramamritham and J. A. Stankovic. Scheduling algorithms and operating systems support for realtime systems. Proceedings of the IEEE, 82(1), January 1994.
• 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: Christopher Rosebrugh , Eng-Kee Kwang, Multiple microcontrollers in an embedded system, Dr. Dobb's Journal, v.17 n.1, p.48-57, Jan. 1992
• 16: L. Sha, R. Rajkumar, and S. S. Sathaye. Generalized rate-monotonic scheduling theory: A framework for developing real-time systems. Proceedings o} the IEEE, 82(1), January 1994.
• 17: K. G. Shin and P. Ramanathan. Real-time computing: A new discipline of computer science and engineering. Proceedings o} the IEEE, 82(1), January 1994.
• 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: 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]
• 20: Ti-Yen Yen , Wayne Wolf, Performance estimation for real-time distributed embedded systems, Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors, p.64-71, October 02-04, 1995

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles

          Nouns: ASIC

  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Gradient methods
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
ASICs, CPU time, application software architecture, arbitrary topology, communicating periodic processes, communication links, distributed processing, gradient-search algorithm, heterogeneous distributed systems, local sensitivity, logic design, performance estimates, priority prediction method, process allocation, process scheduling, processor scheduling, real-time distributed embedded systems, real-time systems, sensitivity-driven co-synthesis, software engineering