Multitasking workload scheduling on flexible-core chip multiprocessors

ABSTRACT

While technology trends have ushered in the age of chip multiprocessors (CMP), a fundamental question is what size to make each core. Most current commercial designs are symmetric CMPs (SCMP) in which each core is identical and range from a simple RISC processor to a complex out-of-order x86 processor. Some researchers have proposed asymmetric CMPs (ACMP) consisting of multiple types of cores. While less of an issue for ACMPs, the fixed nature of both these architectures makes them vulnerable to mismatches between the granularity of the cores and the parallelism in the workload, which can cause inefficient execution. To remedy this weakness, recent research has proposed flexible-core CMPs (FCMP), which have the capability of aggregating multiple small processing cores to form larger logical processors. FCMPs introduce a new resource allocation and scheduling problem which must determine how many logical processors should be configured, how powerful each processor should be, and where/when each task should run. This paper introduces and motivates this problem, describes the challenges associated with it, and evaluates algorithms appropriate for multitasking on FCMPs. We also evaluate static-core CMPs of various configurations and compare them to FCMPs for various multitasking workloads.

REFERENCES

• 1: Murali Annavaram , Ed Grochowski , John Shen, Mitigating Amdahl's Law through EPI Throttling, Proceedings of the 32nd annual international symposium on Computer Architecture, p.298-309, June 04-08, 2005
• 2: Saisanthosh Balakrishnan , Ravi Rajwar , Mike Upton , Konrad Lai, The Impact of Performance Asymmetry in Emerging Multicore Architectures, Proceedings of the 32nd annual international symposium on Computer Architecture, p.506-517, June 04-08, 2005
• 3: Doug Burger , Stephen W. Keckler , Kathryn S. McKinley , Mike Dahlin , Lizy K. John , Calvin Lin , Charles R. Moore , James Burrill , Robert G. McDonald , William Yoder , the TRIPS Team, Scaling to the End of Silicon with EDGE Architectures, Computer, v.37 n.7, p.44-55, July 2004 [doi>10.1109/MC.2004.65]
• 4: Julita Corbalan , Xavier Martorell , Jesus Labarta, Performance-Driven Processor Allocation, IEEE Transactions on Parallel and Distributed Systems, v.16 n.7, p.599-611, July 2005 [doi>10.1109/TPDS.2005.85]
• 5: J. Dorsey, S. Searles, M. Ciraula, E. Fang, S. Johnson, N. Bujanos, R. Kumar, D. Wu, M. Braganza, and S. Meyers. An Integrated Quad-Core Opteron(TM) Processor. In IEEE International Solid-State Circuits Conference, pages 102--103, February 2007.
• 6: D. Feitelson, L. Rudolph, and U. Schwiegelshohn. Parallel Job Scheduling -- A Status Report. In Workshop on Job Scheduling Strategies for Parallel Processing, June 2004.
• 7: D. G. Feitelson. Job Scheduling in Multiprogrammed Parallel Systems. Technical Report RC 19790 (87657), IBM Research, August 1997.
• 8: Dror G. Feitelson , Larry Rudolph, Metrics and Benchmarking for Parallel Job Scheduling, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.1-24, March 30, 1998
• 9: S. Ghiasi and D. Grunwald. Aide de Camp: Asymmetric Dual Core Design for Power and Energy Reduction. Technical Report CU-CS-964-03, The University of Colorado, Department of Computer Science, 2003.
• 10: Ed Grochowski , Ronny Ronen , John Shen , Hong Wang, Best of Both Latency and Throughput, Proceedings of the IEEE International Conference on Computer Design, p.236-243, October 11-13, 2004
• 11: Toshihide Ibaraki , Naoki Katoh, Resource allocation problems: algorithmic approaches, MIT Press, Cambridge, MA, 1988
• 12: Engin Ipek , Meyrem Kirman , Nevin Kirman , Jose F. Martinez, Core fusion: accommodating software diversity in chip multiprocessors, Proceedings of the 34th annual international symposium on Computer architecture, June 09-13, 2007, San Diego, California, USA
• 13: Changkyu Kim , Doug Burger , Stephen W. Keckler, An adaptive, non-uniform cache structure for wire-delay dominated on-chip caches, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 14: Changkyu Kim , Simha Sethumadhavan , M. S. Govindan , Nitya Ranganathan , Divya Gulati , Doug Burger , Stephen W. Keckler, Composable Lightweight Processors, Proceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture, p.381-394, December 01-05, 2007 [doi>10.1109/MICRO.2007.10]
• 15: Rakesh Kumar , Keith I. Farkas , Norman P. Jouppi , Parthasarathy Ranganathan , Dean M. Tullsen, Single-ISA Heterogeneous Multi-Core Architectures: The Potential for Processor Power Reduction, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.81, December 03-05, 2003
• 16: Rakesh Kumar , Dean M. Tullsen , Parthasarathy Ranganathan , Norman P. Jouppi , Keith I. Farkas, Single-ISA Heterogeneous Multi-Core Architectures for Multithreaded Workload Performance, Proceedings of the 31st annual international symposium on Computer architecture, p.64, June 19-23, 2004, München, Germany
• 17: U. Nawathe, M. Hassan, K. Yen, L. Warriner, B. Upputuri, D. Greenhill, A. Kumar, and H. Park. An 8-Core 64-Thread 64b Power-Efficient SPARC SoC. In IEEE International Solid-State Circuits Conference, pages 108--109, February 2007.
• 18: D. Pham, T. Aipperspach, D. Boerstler, M. Bolliger, R. Chaudhry, D. Cox, P. Harvey, P. Harvey, H. Hofstee, C. Johns, J. Kahle, A. Kameyama, J. Keaty, Y. Masubuchi, M. Pham, J. Pille, S. Posluszny, M. Riley, D. Stasiak, M. Suzuoki, O. Takahashi, J. Warnock, S. Weitzel, D. Wendel, and K. Yazawa. Overview of the Architecture, Circuit Design, and Physical Implementation of a First-Generation Cell Processor. IEEE Journal of Solid-State Circuits, 41(1):179--196, January 2006.
• 19: Timothy Sherwood , Erez Perelman , Greg Hamerly , Suleyman Sair , Brad Calder, Discovering and Exploiting Program Phases, IEEE Micro, v.23 n.6, p.84-93, November 2003 [doi>10.1109/MM.2003.1261391]
• 20: D. Tarjan, M. Boyer, and K. Skadron. Federation: Out-of-Order Execution Using Simple In-Order Cores. Technical Report CS-2007-11, University of Virginia, Department of Computer Science, August 2007.
• 21: S. Vangal, J. Howard, G. Ruhl, S. Dighe, H. Wilson, J. Tschanz, D. Finan, P. Iyer, A. Singh, T. Jacob, S. Jain, S. Venkataraman, Y. Hoskote, and N. Borkar. An 80-Tile 1.28 TFLOPS Network-on-Chip in 65nm CMOS. In IEEE International Solid-State Circuits Conference, pages 98--99, February 2007.
• 22: Hongtao Zhong , Steven A. Lieberman , Scott A. Mahlke, Extending Multicore Architectures to Exploit Hybrid Parallelism in Single-thread Applications, Proceedings of the 2007 IEEE 13th International Symposium on High Performance Computer Architecture, p.25-36, February 10-14, 2007 [doi>10.1109/HPCA.2007.346182]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Scheduling

General Terms:
Algorithms, Experimentation, Performance

Keywords:
flexible cores, multicore architectures, multitask scheduling