Age based scheduling for asymmetric multiprocessors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback
Take a look at the new version of this page: [ beta version ]. Tell us what you think.

Age based scheduling for asymmetric multiprocessors

Full text

Pdf (319 KB)

Source

Conference on High Performance Networking and Computing archive
Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis table of contents

Portland, Oregon

SESSION: Technical papers table of contents

Article No.: 25

Year of Publication: 2009

ISBN:978-1-60558-744-8

Authors

Nagesh B. Lakshminarayana	Georgia Institute of Technology
Jaekyu Lee	Georgia Institute of Technology
Hyesoon Kim	Georgia Institute of Technology

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
: IEEE CS

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 82, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1654059.1654085 What is a DOI?

ABSTRACT

Asymmetric (or Heterogeneous) Multiprocessors are becoming popular in the current era of multi-cores due to their power efficiency and potential performance and energy efficiency. However, scheduling of multithreaded applications in Asymmetric Multiprocessors is still a challenging problem. Scheduling algorithms for Asymmetric Multiprocessors must not only be aware of asymmetry in processor performance, but have to consider the characteristics of application threads also.

In this paper, we propose a new scheduling policy, Age based scheduling, that assigns a thread with a larger remaining execution time to a fast core. Age based scheduling predicts the remaining execution time of threads based on their age, i.e., when the threads were created. These predictions are based on the insight that most threads that are created together tend to have similar execution durations. Using Age based scheduling, we improve the overall performance of several important multithreaded applications including Parsec and asymmetric benchmarks from Splash-II and Omp-SCR. Our evaluations show that Age based scheduling improves performance up to 37% compared to the state-of-the-art Asymmetric Multiprocessor scheduling policy and on average by 10.4% for the Parsec benchmarks. Our results also show that the Age based scheduling policy with profiling improves the average performance by 13.2% for the Parsec benchmarks.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Intel xeon processor. http://www.intel.com/support/processors/xeon/.
	2	Linux kernel CPUfreq subsystem. http://www.kernel.org/pub/linux/utils/kernel/cpufreq/cpufreq.html.
	3	O(1) Scheduler. http://joshaas.net/linux/.
	4	Enhanced Intel SpeedStep Technology for the Intel Pentium M Processor--White Paper, March 2004.
	5	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 [doi>10.1109/ISCA.2005.36]
	6	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 [doi>10.1109/ISCA.2005.51]
	7	Michela Becchi , Patrick Crowley, Dynamic thread assignment on heterogeneous multiprocessor architectures, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128029]
	8	C. Bienia, S. Kumar, J. P. Singh, and K. Li. The PARSEC Benchmark Suite: Characterization and Architectural Implications. Technical Report TR-811-08, Princeton University, 2008.
	9	Daniel Bovet , Marco Cesati, Understanding The Linux Kernel, Oreilly & Associates Inc, 2005
	10	Qiong Cai , José González , Ryan Rakvic , Grigorios Magklis , Pedro Chaparro , Antonio González, Meeting points: using thread criticality to adapt multicore hardware to parallel regions, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada [doi>10.1145/1454115.1454149]
	11	James W. Demmel , John R. Gilbert , Xiaoye S. Li, An Asynchronous Parallel Supernodal Algorithm for Sparse Gaussian Elimination, SIAM Journal on Matrix Analysis and Applications, v.20 n.4, p.915-952, Oct. 1999 [doi>10.1137/S0895479897317685]
	12	A. J. Dorta, C. Rodriguez, F. D. Sande, and A. Gonzalez-Ecsribano. The OpenMP Source Code Repository: an Infrastructure to Contribute to the Development of OpenMP.
	13	A. Fedorova, D. Vengerov, and D. Doucette. Operating System Scheduling On Heterogeneous Core Systems. Technical report, Sun Microsystem, 2007.
	14	R. Grant and A. Afsahi. Power-Performance Efficiency of Asymmetric Multiprocessors for Multi-threaded Scientific Applications. In IPDPS, 2006.
	15	Intel Corporation. Intel VTune Performance Analyzers. http://www.intel.com/vtune/.
	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	Tong Li , Dan Baumberger , David A. Koufaty , Scott Hahn, Efficient operating system scheduling for performance-asymmetric multi-core architectures, Proceedings of the 2007 ACM/IEEE conference on Supercomputing, November 10-16, 2007, Reno, Nevada [doi>10.1145/1362622.1362694]
	18	Robert Love, Linux Kernel Development (2nd Edition) (Novell Press), Novell Press, 2005
	19	Marshall Kirk McKusick , George V. Neville-Neil, Thread Scheduling in FreeBSD 5.2, Queue, v.2 n.7, October 2004 [doi>10.1145/1035594.1035622]
	20	Tomer Y. Morad , Uri C. Weiser , Avinoam Kolodny , Mateo Valero , Eduard Ayguade, Performance, Power Efficiency and Scalability of Asymmetric Cluster Chip Multiprocessors, IEEE Computer Architecture Letters, v.5 n.1, p.4, January 2006 [doi>10.1109/L-CA.2006.6]
	21	D. Shelepov and A. Fedorova. Scheduling on Heterogeneous Multicore Processors Using Architectural Signatures. In WIOSCA, 2008.
	22	Andrew S Tanenbaum , Albert S Woodhull, Operating Systems Design and Implementation (3rd Edition), Prentice-Hall, Inc., Upper Saddle River, NJ, 2005
	23	Steven Cameron Woo , Moriyoshi Ohara , Evan Torrie , Jaswinder Pal Singh , Anoop Gupta, The SPLASH-2 programs: characterization and methodological considerations, Proceedings of the 22nd annual international symposium on Computer architecture, p.24-36, June 22-24, 1995, S. Margherita Ligure, Italy [doi>10.1145/223982.223990]