Dynamic thread assignment on heterogeneous multiprocessor architectures

ABSTRACT

In a multi-programmed computing environment, threads of execution exhibit different runtime characteristics and hardware resource requirements. Not only do the behaviors of distinct threads differ, but each thread may also present diversity in its performance and resource usage over time. A heterogeneous chip multiprocessor (CMP) architecture consists of processor cores and caches of varying size and complexity. Prior work has shown that heterogeneous CMPs can meet the needs of a multi-programmed computing environment better than a homogeneous CMP system. In fact, the use of a combination of cores with different caches and instruction issue widths better accommodates threads with different computational requirements.A central issue in the design and use of heterogeneous systems is to determine an assignment of tasks to processors which better exploits the hardware resources in order to improve performance. In this paper we argue that the benefits of heterogeneous CMPs are bolstered by the usage of a dynamic assignment policy, i.e., a runtime mechanism which observes the behavior of the running threads and exploits thread migration between the cores. We validate our analysis by means of simulation. Specifically, our model assumes a combination of Alpha EV5 and Alpha EV6 processors and of integer and floating point programs from the SPEC2000 benchmark suite. We show that a dynamic assignment can outperform a static one by 20% to 40% on average and by as much as 80% in extreme cases, depending on the degree of multithreading simulated.

REFERENCES

• 1: 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
• 2: 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
• 3: Rakesh Kumar , Norman P. Jouppi , Dean M. Tullsen, Conjoined-Core Chip Multiprocessing, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.195-206, December 04-08, 2004, Portland, Oregon [doi>10.1109/MICRO.2004.12]
• 4: John L. Hennessy , David A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 5: R. E. Kessler, The Alpha 21264 Microprocessor, IEEE Micro, v.19 n.2, p.24-36, March 1999 [doi>10.1109/40.755465]
• 6: N. L. Binkert, E. G. Hallnor, and S. K. Reinhardt. Network-Oriented Full-System Simulation using M5. In Sixth Workshop on Computer Architecture Evaluation using Commercial Workloads (CAECW), February 2003
• 7: T. Sherwood, E. Perelman, G. Hamerly, S. Sair, and B. Calder. Discovering and exploiting program phases. In IEEE Micro: Micro's Top Picks from Computer Architecture Conferences, Dec. 2003
• 8: Timothy Sherwood , Suleyman Sair , Brad Calder, Phase tracking and prediction, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 9: Fei Sun , Srivaths Ravi , Anand Raghunathan , Niraj K. Jha, Synthesis of Application-Specific Heterogeneous Multiprocessor Architectures Using Extensible Processors, Proceedings of the 18th International Conference on VLSI Design held jointly with 4th International Conference on Embedded Systems Design (VLSID'05), p.551-556, January 03-07, 2005 [doi>10.1109/ICVD.2005.155]
• 10: G. C. Sih , E. A. Lee, A Compile-Time Scheduling Heuristic for Interconnection-Constrained Heterogeneous Processor Architectures, IEEE Transactions on Parallel and Distributed Systems, v.4 n.2, p.175-187, February 1993 [doi>10.1109/71.207593]
• 11: Hyunok Oh , Soonhoi Ha, A Static Scheduling Heuristic for Heterogeneous Processors, Proceedings of the Second International Euro-Par Conference on Parallel Processing-Volume II, p.573-577, August 26-29, 1996
• 12: R. J. O. Figuiredo and J. A. B. Fortes. Impact of Heterogeneity on DSM Performances. In Sixth International Symposium on High Performance Computer Architecture, January, 2000
• 13: J. M. Tendler et al. POWER4 System Microarchitecture. In IBM Journal of Research and Development. Vol 46, No. 1, January 2002.
• 14: S. Richardson. MPOC: A Chip Multiprocessor for Embedded Systems. HP Technical Report HPL-2002-186, 2002.
• 15: Digital Equipment Corp. Alpha 21164 Microprocessor Hardware Reference Manual. October, 1996.
• 16: Kunle Olukotun , Basem A. Nayfeh , Lance Hammond , Ken Wilson , Kunyung Chang, The case for a single-chip multiprocessor, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.2-11, October 01-04, 1996, Cambridge, Massachusetts, United States
• 17: John B. Andrews , Constantine D. Polychronopoulos, An analytical approach to performance/cost modeling of parallel computers, Journal of Parallel and Distributed Computing, v.12 n.4, p.343-356, Aug. 1991 [doi>10.1016/0743-7315(91)90005-T]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

General Terms:
Design, Performance

Keywords:
chip multiprocessor, heterogeneous architectures, simulation