Micro-preemption synthesis: an enabling mechanism for multi-task VLSI systems

ABSTRACT

Task preemption is a critical enabling mechanism in multi-task VLSI systems. On preemption, data in the register files must be preserved in order for the task to be resumed. This entails extra memory to preserve the context and additional clock cycles to save and restore the context. In this paper, we present techniques and algorithms to incorporate micro-preemption constraints during multi-task VLSI system synthesis. Specifically, we have developed: (i) Algorithms to insert and refine preemption points in scheduled task graphs subject to preemption latency constraints. (ii) Techniques to minimize the context switch overhead by considering the dedicated registers required to save the state of a task on preemption and the shared registers required to save the remaining values in the tasks. (iii) A controller based scheme to preclude preemption related performance degradation. The effectiveness of all approaches, algorithms, and software implementations is demonstrated on real examples.

REFERENCES

• 1: D.W. Anderson, F.J. Sparacio, and F.M. Tomasulo, "The IBM System/360 Model 91: Machine philosophy and instruction-handling," IBM Journal, 11(1), pp. 8-24, 1967.
• 2: W.-M. W. Hwu , Y. N. Patt, Checkpoint repair for high-performance out-of-order execution machines, IEEE Transactions on Computers, v.36 n.12, p.1496-1514, Dec. 1987 [doi>10.1109/TC.1987.5009500]
• 3: G.D. Hillman, "DSP56200: An Algorithm-Specific Digital Signal Processor Peripheral", Proc IEEE, 75(9), pp. iiss-iigi.
• 4: Edward Ashford Lee , David G. Messerschmitt, Static scheduling of synchronous data flow programs for digital signal processing, IEEE Transactions on Computers, v.36 n.1, p.24-35, Jan. 1987 [doi>10.1109/TC.1987.5009446]
• 5: G. Jack Lipovski , Miroslaw Malek, Parallel computing: theory and comparisons, Wiley-Interscience, New York, NY, 1987
• 6: James E. Smith , Andrew R. Pleszkun, Implementing Precise Interrupts in Pipelined Processors, IEEE Transactions on Computers, v.37 n.5, p.562-573, May 1988 [doi>10.1109/12.4607]
• 7: M. Gokhale, et al., "SPLASH: A Reconfigurable Linear Logic Array", ICPP, 1990.
• 8: M. C. McFarland and A. C. Parker and R. Camposano, "The high-level synthesis of digital systems", Proc IEEE, 78(2), pp. 301-318, 1990.
• 9: Gurindar S. Sohi, Instruction Issue Logic for High-Performance, Interruptible, Multiple Functional Unit, Pipelined Computers, IEEE Transactions on Computers, v.39 n.3, p.349-359, March 1990 [doi>10.1109/12.48865]
• 10: J. M. Rabaey , C. Chu , P. Hoang , M. Potkonjak, Fast Prototyping of Datapath-Intensive Architectures, IEEE Design & Test, v.8 n.2, p.40-51, April 1991 [doi>10.1109/54.82037]
• 11: Robert J. Baron , Lee Higbie, Computer Architecture; Case Studies, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992
• 12: A. E1 Gamal, J. Rose, A. Sangiovanni-Vincentelli, "Synthesis Methods for Field Programmable Gate Arrays", Proc. of IEEE, 81(7), pp. 1013-1029, 1993.
• 13: A.K. Yeung, J.M. Rabaey, "A 2.4 GOPS data-driven reconfigurable multiprocessor IC for DSP", ISSCC, pp. 108-109, 1995.
• 14: Kyosun Kim , Ramesh Karri , Miodrag Potkonjak, Heterogeneous built-in resiliency of application specific programmable processors, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.406-411, November 10-14, 1996, San Jose, California, United States
• 15: David Mosberger , Peter Druschel , Larry L. Peterson, Implementing atomic sequences on uniprocessors using rollforward, Software—Practice & Experience, v.26 n.1, p.1-23, Jan. 1996 [doi>10.1002/(SICI)1097-024X(199601)26:1<1::AID-SPE998>3.3.CO;2-S]
• 16: Kyosun Kim , Ramesh Karri , Miodrag Potkonjak, Synthesis of application specific programmable processors, Proceedings of the 34th annual conference on Design automation, p.353-358, June 09-13, 1997, Anaheim, California, United States [doi>10.1145/266021.266164]

INDEX TERMS

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

Additional Classification:
  B. Hardware
  B.4 INPUT/OUTPUT AND DATA COMMUNICATIONS
      B.4.2 Input/Output Devices
          Subjects: Channels and controllers

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
micro-preemption, multi-task VLSI system synthesis, context switch overhead, preemption latency