Efficient program scheduling for heterogeneous multi-core processors

ABSTRACT

Heterogeneous multicore processors promise high execution efficiency under diverse workloads, and program scheduling is critical in exploiting this efficiency. This paper presents a novel method to leverage the inherent characteristics of a program for scheduling decisions in heterogeneous multicore processors. The proposed method projects the core's configuration and the program's resource demand to a unified multi-dimensional space, and uses weighted Euclidean distance between these two to guide the program scheduling. The experimental results show that on average, this distance based scheduling heuristic achieves 24.5% reduction in energy delay product, 6.1% reduction in energy, and 9.1% improvement in throughput when compared with traditional hardware oblivious scheduling algorithm.

REFERENCES

• 1: F. A. Bower, et al. "The Impact of Dynamically Heterogeneous Multicore Processors on Thread Scheduling", IEEE Micro, pp 17--25, May 2008.
• 2: The ARM Cortex-A9 Processor, the ARM white paper. http://www.arm.com/pdfs/ARMCortexA-9Processors.pdf
• 3: R. Kumar, et al, "Single-ISA heterogeneous multi-core architectures: the potential for processor power reduction", Micro-36, pp 81--92, Dec. 2003.
• 4: Yoav Benjamini. "Opening the Box of a Boxplot". The American Statistician. Vol 42 (4), pp257--262, Nov. 1988.
• 5: A. Phansalkar, et al, "Measuring Program Similarity: Experiments with SPEC CPU Benchmark Suites," ISPASS'05, pp 10--20, Mar. 2005
• 6: J. Chen and L. K. John, "Energy aware program scheduling in a heterogeneous multicore system", IISWC'08, pp. 1--9, Sept. 2008.
• 7: Changkyu Kim, et. al., "Composable Lightweight Processors," Micro-40, pp. 381--394, Dec. 2007
• 8: D. P. Gulati et al., "Multitasking Workload Scheduling on Flexible Core Chip Multiprocessors", PACT'08, pp187--196, Oct. 2008.
• 9: E. Ipek, et al., "Core Fusion: Accommodating software diversity in chip multiprocessors". ISCA-34, pp 186--197, June 2007.
• 10: D. Burger and T. M. Austin, "The simplescalar tool set version 3.02", http://www.simplescalar.com/
• 11: David Brooks, et al. "Wattch: A Framework for Architectural-Level Power Analysis and Optimizations", ISCA-27, pp 83--94, June, 2000
• 12: H. P Hofstee, "Power efficient processor architecture and the CELL processor", HPCA-11. pp. 258--262, Feb. 2005
• 13: M. Maheswaran and H. J. Siegel, "A Dynamic Matching and Scheduling Algorithm for Heterogeneous Computing Systems", Proc. Heterogeneous Computing Workshop, pp. 57--69, 1998
• 14: M. Haungs, et. al, "Branch transition rate: a new metric for improved branch classification analysis", HPCA-6, pp. 241--250, Feb. 2000
• 15: C. S. Ballapuram, A. Sharif and H. S. Lee, "Exploiting Access Semantics and Program Behavior to Reduce Snoop Power in Chip Multiprocessors", ASPLOS XIII, pp 60--69, Mar 2008
• 16: R. L. M. et al. "Evaluation Techniques for Storage Hierarchies". IBM Systems Journal, pp 78--117. 1970
• 17: M. Becchi, Patrick Crowley, "Dynamic thread Assignment on Heterogeneous Multi-processor Architectures", Computing Frontiers 2006, pp 29--40, May 2006
• 18: J. Liu, et al., "Power-aware scheduling under timing constraints for mission-critical embedded systems", DAC-38, pp840--845, July, 2001.
• 19: M. Ruggiero, et al. "Communication aware system-on-chip allocation and scheduling framework for stream-oriented multi-processor", DATE, pp3--8, Apr. 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles
          Subjects: Heterogeneous (hybrid) systems

General Terms:
Design, Performance

Keywords:
energy-delay product, heterogeneous multi-core, program scheduling