A task-level hierarchical memory model for system synthesis of multiprocessors

ABSTRACT

This paper introduces the first high-level (task-level)model of hierarchical memories and describes a scheduling andallocation algorithm for system-level synthesis of heterogeneousmultiprocessors. Caches are essential for modern RISC embeddedcores to obtain sustained high performance. However, caches havereceived limited use in priority-driven preemptive real-time systemsdue to the unpredictability of caches-average-case improvementsare of no use in systems with hard deadlines. Program-levelcache models do not take into account preemptions between multipletasks running at multiple rates on embedded cores. Our task-levelmodel of performance in the presence of memory hierarchiesprovides an efficient means to bound the guaranteed memory performanceof tasks running in a multi-rate, multi-tasking environment.Our system synthesis algorithm uses software-based cachepartitioning and reservation techniques to guarantee cache hitsfor some tasks and therefore improve task schedulability. Experimentalresults show that our model significantly improves schedulabilityof real-time tasks and can be evaluated efficiently duringsystem-level synthesis.

REFERENCES

• 1: Yau-Tsun Steven Li , Sharad Malik , Andrew Wolfe, Performance estimation of embedded software with instruction cache modeling, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.380-387, November 05-09, 1995, San Jose, California, United States
• 2: Yanbing Li , Wayne Wolf, Hierarchical Scheduling and Allocation of Multirate Systems on Heterogeneous Multiprocessors, Proceedings of the 1997 European conference on Design and Test, p.134, March 17-20, 1997
• 3: D. Kirk and J. Strosnider, "SMART cache design using the MIPS R3000," in Proc., RTSS'90, IEEE, 1990.
• 4: J. Torrellas, "Multiprocessor cache memory performance: characterization and optimization," Stanford Univ., CSL-TR-92-545,1992.
• 5: A. Burchard, Y. Oh, J. Liebeherr, S. H. Son, "A linear-time online task assignment scheme for multiprocessor systems," in Proceedings, 11 th IEEE Workshop Real-Time Operating Systems and Software, pp. 28-31, May 1994.
• 6: D.-T. Peng and K. G. Shin. "Static allocation of periodic tasks with precedence constraints in distributed real-time systems," In Proc., International Conference on Distributed Computing Systems, 1989.
• 7: 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]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

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

General Terms:
Algorithms, Design, Performance, Theory