Operating system multilevel load balancing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Operating system multilevel load balancing

Full text

Pdf (111 KB)

Source

Symposium on Applied Computing archive
Proceedings of the 2006 ACM symposium on Applied computing table of contents

Dijon, France

SESSION: Operating systems and adaptive applications (OSAA) table of contents

Pages: 1467 - 1471

Year of Publication: 2006

ISBN:1-59593-108-2

Authors

M. Corrêa	Faculty of Informatics - PUCRS, Porto Alegre, Brazil
A. Zorzo	Faculty of Informatics - PUCRS, Porto Alegre, Brazil
R. Scheer	HP Brazil R&D, Porto Alegre, Brazil

Sponsor

SIGAPP: ACM Special Interest Group on Applied Computing

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 74, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	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/1141277.1141619 What is a DOI?

ABSTRACT

This paper describes an algorithm that allows Linux to perform multilevel load balancing in NUMA computers. The Linux scheduler implements a load balancing algorithm that uses structures called sched domains to build a hierarchy that represents the machine's topology. Although sched domains implementation allows Linux to build a multilevel hierarchy to represent multilevel machines, the generic code of the current kernel version builds no more than two levels in the sched domains hierarchy. Thus, for NUMA systems with three or more memory access levels, the constructed hierarchy does not represent correctly the machine's topology. When Linux load balancing algorithm uses an incorrect sched domains hierarchy, process execution time can increase, because processes can be moved to nodes that are distant from their memory areas. In order to solve this problem, we have implemented an algorithm to build multilevel sched domains hierarchies for NUMA computers. Our proposed algorithm uses ACPI SLIT table data to recognize how many memory access levels a machine contains. Then, it builds an n-level sched domains hierarchy, where n is the number of memory access levels. Through benchmarking and simulation results we demonstrate that the Linux load balancing performance when the sched domains hierarchy is built using our proposed algorithm is better than using the current Linux algorithm.

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	J. Aas. Understanding the Linux 2.6.8.1 CPU Scheduler. http://josh.trancesoftware.com/linux.
	2	G. Attiya and Y. Hamam. Two Phase Algorithm for Load Balancing in Heterogeneous Distributed Systems. In 12th Euromicro Conference on Parallel, Distributed and Network-Based Processing, pages 434--439, 2004.
	3	M. J. Bligh, M. Dobson, D. Hart, and G. Huizenga. Linux on NUMA Systems. In Proceedings of the Linux Symposium, pages 89--102, Ottawa, Canada, 2004.
	4	C. Bohn and G. Lamont. Load Balancing for Heterogeneous Clusters of PCs. Future Generation Computer Systems, 18:389--400, 2002.
	5	Rajkumar Buyya, High Performance Cluster Computing: Architectures and Systems, Prentice Hall PTR, Upper Saddle River, NJ, 1999
	6	Moon-Seok Chang , Haen-Yun Kim, Performance Analysys of a CC-NUMAOperating System, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.44, April 23-27, 2001
	7	Eric Focht. NUMA aware scheduler. http://home.arcor.de/efocht/sched, 2002.
	8	D. Grosu and A. Chronopoulos. Algorithmic Mechanism Design for Load Balancing in Distributed Systems. IEEE Transactions on Systems, Man and Cybernetics, 34(1), 2004.
	9	Hewlett-Packard. Meet the HP Integrity Superdome. http://h21007.www2.hp.com/dspp/files/unprotected/superdomejan05.pdf, 2005.
	10	Hewlett-Packard, Intel, Microsoft, Phoenix and Toshiba. Advanced Configuration and Power Interface Specification. URL http://www.acpi.info/DOWN-LOADS/ACPIspec30.pdf, 2004.
	11	Kai Hwang , Zhiwei Xu, Scalable Parallel Computing: Technology,Architecture,Programming, McGraw-Hill, Inc., New York, NY, 1998
	12	JavaSim Web Site. http://javasim.ncl.ac.uk.
	13	C. Kolivas. Kernbench benckmark. http://ck.kolivas.org/kernbench, 2004.
	14	R. Love. Linux Kernel Development. SAMS, Developer Library Series, 2003.
	15	M. Woodacre and D. Robb and D. Roe and K. Feind. The SGI AltixTM 3000 Global Shared-Memory Architecture. http://www.sgi.com/products/servers/altix/whitepapers, 2005.
	16	PeSO Project Web Site. http://www.inf.pucrs.br/peso.
	17	Marc Snir , Steve W. Otto , David W. Walker , Jack Dongarra , Steven Huss-Lederman, MPI: The Complete Reference, MIT Press, Cambridge, MA, 1995
	18	Yuanshi Wang , Jiming Liu, Macroscopic model of agent-based load balancing on grids, Proceedings of the second international joint conference on Autonomous agents and multiagent systems, July 14-18, 2003, Melbourne, Australia [doi>10.1145/860575.860704]
	19	W. Zhu, Cluster Queue Structure for Shared-Memory Multiprocessor Systems, The Journal of Supercomputing, v.25 n.3, p.215-236, July 2003 [doi>10.1023/A:1024247027039]
	20	Yi-Chang Zhuang , Tyng Yue Liang , Ce-kuen Shieh , Jun-qi Lee , Laurence Tianruo Yang, A Group-Based Load Balance Scheme for Software Distributed Shared Memory Systems, The Journal of Supercomputing, v.28 n.3, p.295-309, June 2004 [doi>10.1023/B:SUPE.0000022101.41799.cc]