Efficient operating system scheduling for performance-asymmetric multi-core architectures

ABSTRACT

Recent research advocates asymmetric multi-core architectures, where cores in the same processor can have different performance. These architectures support single-threaded performance and multithreaded throughput at lower costs (e.g., die size and power). However, they also pose unique challenges to operating systems, which traditionally assume homogeneous hardware. This paper presents AMPS, an operating system scheduler that efficiently supports both SMP-and NUMA-style performance-asymmetric architectures. AMPS contains three components: asymmetry-aware load balancing, faster-core-first scheduling, and NUMA-aware migration. We have implemented AMPS in Linux kernel 2.6.16 and used CPU clock modulation to emulate performance asymmetry on an SMP and NUMA system. For various workloads, we show that AMPS achieves a median speedup of 1.16 with a maximum of 1.44 over stock Linux on the SMP, and a median of 1.07 with a maximum of 2.61 on the NUMA system. Our results also show that AMPS improves fairness and repeatability of application performance measurements.

REFERENCES

• 1: 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]
• 2: 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
• 3: 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
• 4: Cyril Banino , Olivier Beaumont , Larry Carter , Jeanne Ferrante , Arnaud Legrand , Yves Robert, Scheduling Strategies for Master-Slave Tasking on Heterogeneous Processor Platforms, IEEE Transactions on Parallel and Distributed Systems, v.15 n.4, p.319-330, April 2004 [doi>10.1109/TPDS.2004.1271181]
• 5: Michael A. Bender , Michael O. Rabin, Scheduling Cilk multithreaded parallel programs on processors of different speeds, Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures, p.13-21, July 09-13, 2000, Bar Harbor, Maine, United States [doi>10.1145/341800.341803]
• 6: S. Y. Borkar, P. Dubey, K. C. Kahn, D. J. Kuck, H. Mulder, S. S. Pawlowski, and J. Rattner. Platform 2015: Intel® processor and platform evolution for the next decade. White Paper, Intel Corporation, 2005.
• 7: Rohit Chandra , Scott Devine , Ben Verghese , Anoop Gupta , Mendel Rosenblum, Scheduling and page migration for multiprocessor compute servers, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.12-24, October 05-07, 1994, San Jose, California, United States
• 8: M. DeVuyst, R. Kumar, and D. M. Tullsen. Exploiting unbalanced thread scheduling for energy and performance on a CMP of SMT processors. In Proceedings of the 20th International Parallel and Distributed Processing Symposium, Apr. 2006.
• 9: Alexandra Fedorova , Margo Seltzer , Christoper Small , Daniel Nussbaum, Performance of multithreaded chip multiprocessors and implications for operating system design, Proceedings of the annual conference on USENIX Annual Technical Conference, p.26-26, April 10-15, 2005, Anaheim, CA
• 10: R. J. O. Figueiredo and J. A. B. Fortes. Impact of heterogeneity on DSM performance. In Proceedings of the Sixth IEEE Symposium on High-Performance Computer Architecture, pages 26--35, Jan. 2000.
• 11: Soraya Ghiasi , Tom Keller , Freeman Rawson, Scheduling for heterogeneous processors in server systems, Proceedings of the 2nd conference on Computing frontiers, May 04-06, 2005, Ischia, Italy [doi>10.1145/1062261.1062295]
• 12: Richard A. Hankins , Gautham N. Chinya , Jamison D. Collins , Perry H. Wang , Ryan Rakvic , Hong Wang , John P. Shen, Multiple Instruction Stream Processor, Proceedings of the 33rd annual international symposium on Computer Architecture, p.114-127, June 17-21, 2006
• 13: 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
• 14: Rakesh Kumar , Dean M. Tullsen , Norman P. Jouppi , Parthasarathy Ranganathan, Heterogeneous Chip Multiprocessors, Computer, v.38 n.11, p.32-38, November 2005 [doi>10.1109/MC.2005.379]
• 15: 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
• 16: Richard P. LaRowe, Jr. , Carla Schlatter Ellis , Laurence S. Kaplan, The robustness of NUMA memory management, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.137-151, October 13-16, 1991, Pacific Grove, California, United States
• 17: Linux Kernel Mailing List. Scalability of signal delivery for POSIX threads. http://lkml.org/lkml/2004/11/22/432, Nov. 2004.
• 18: Daniel Menascé , Virgílio Almeida, Cost-performance analysis of heterogeneity in supercomputer architectures, Proceedings of the 1990 ACM/IEEE conference on Supercomputing, p.169-177, November 12-16, 1990, New York, New York
• 19: D. Pham, S. Asano, M. Bolliger, M. N. Day, H. P. Hofstee, C. Johns, J. Kahle, A. Kameyama, J. Keaty, Y. Masubuchi, M. Riley, D. Shippy, D. Stasiak, M. Suzuoki, M. Wang, J. Warnock, S. Weitzel, D. Wendel, T. Yamazaki, and K. Yazawa. The design and implementation of a first generation CELL* processor. In IEEE International Solid-State Circuits Conference Digest of Technical Papers, pages 184--185, Feb. 2005.
• 20: Mohamed Gomaa , Michael D. Powell , T. N. Vijaykumar, Heat-and-run: leveraging SMT and CMP to manage power density through the operating system, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 21: 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]
• 22: Allan Snavely , Dean M. Tullsen, Symbiotic jobscheduling for a simultaneous multithreaded processor, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.234-244, November 2000, Cambridge, Massachusetts, United States
• 23: Haluk Topcuouglu , Salim Hariri , Min-you Wu, Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing, IEEE Transactions on Parallel and Distributed Systems, v.13 n.3, p.260-274, March 2002 [doi>10.1109/71.993206]
• 24: Volkmar Uhlig , Joshua LeVasseur , Espen Skoglund , Uwe Dannowski, Towards scalable multiprocessor virtual machines, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.4-4, May 06-07, 2004, San Jose, California
• 25: Haoqiang Zheng , Jason Nieh, SWAP: a scheduler with automatic process dependency detection, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.14-14, March 29-31, 2004, San Francisco, California