Locality-conscious process scheduling in embedded systems

ABSTRACT

In many embedded systems, existence of a data cache might influence the effectiveness of process scheduling policy significantly. Consequently, a scheduling policy that takes inter-process data reuse into account might result in large performance benefits. In this paper, we focus on array-intensive embedded applications and present a locality-conscious scheduling strategy where we first evaluate the potential data reuse between processes, and then, using the results of this evaluation, select an order for process executions. We also show how process codes can be transformed by an optimizing compiler for increasing inter-process data reuse, thereby making locality-conscious scheduling more effective. Our experimental results obtained using two large, multi-process application codes indicate significant runtime benefits.

REFERENCES

• 1: Francky Catthoor , Eddy de Greef , Sven Suytack, Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design, Kluwer Academic Publishers, Norwell, MA, 1998
• 2: Massimilano Chiodo , Paolo Giusto , Attila Jurecska , Harry C. Hsieh , Alberto Sangiovanni-Vincentelli , Luciano Lavagno, Hardware-Software Codesign of Embedded Systems, IEEE Micro, v.14 n.4, p.26-36, August 1994 [doi>10.1109/40.296155 ]
• 3: G. De Micheli and R. K. Gupta. Hardware-software codesign. Proceedings of the IEEE, 85, No 3. (March 1997):349--365.
• 4: Rolf Ernst, Codesign of Embedded Systems: Status and Trends, IEEE Design & Test, v.15 n.2, p.45-54, April 1998 [doi>10.1109/54.679207 ]
• 5: F. Feautrier. Dataflow analysis of array and scalar references. International Journal of Parallel Programming, 20(1):23--51, 1991.
• 6: M. Kandemir , N. Vijaykrishnan , M. J. Irwin , W. Ye, Influence of compiler optimizations on system power, Proceedings of the 37th conference on Design automation, p.304-307, June 05-09, 2000, Los Angeles, California, United States [doi>10.1145/337292.337425]
• 7: Wayne Kelly , Vadim Maslov , William Pugh , Evan Rosser , Tatiana Shpeisman , David Wonnacott, The Omega Library interface guide, University of Maryland at College Park, College Park, MD, 1995
• 8: Chang-Gun Lee , Joosun Hahn , Yang-Min Seo , Sang Lyul Min , Rhan Ha , Seongsoo Hong , Chang Yun Park , Minsuk Lee , Chong Sang Kim, Analysis of Cache-Related Preemption Delay in Fixed-Priority Preemptive Scheduling, IEEE Transactions on Computers, v.47 n.6, p.700-713, June 1998 [doi>10.1109/12.689649 ]
• 9: Y. Li and W. Wolfe. A task-level hierarchical memory model for system synthesis of multiprocessors. IEEE Transactions on CAD, 18(10), October 1999, pp. 1405--1417.
• 10: WARTS: Wisconsin Architectural Research Tool Set. http://www.cs.wisc.edu/~larus/warts.html
• 11: Michael E. Wolf , Monica S. Lam, A data locality optimizing algorithm, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.30-44, June 24-28, 1991, Toronto, Ontario, Canada
• 12: Wayne Wolf, Computers as components: principles of embedded computing system design, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 13: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 14: A. Wolfe. Software-based cache partitioning for real-time applications. In Proc. the Third International Workshop on Responsive Computer Systems, September 1993.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Performance, Reliability