NDLI: Efficient load balancing for wide-area divide-and-conquer applications

Please wait, while we are loading the content...

Parallel computing in 2010: opportunities and challenges in a networked world

Reference idempotency analysis: a framework for optimizing speculative execution

Pointer and escape analysis for multithreaded programs

Language support for Morton-order matrices

Efficient load balancing for wide-area divide-and-conquer applications

Scalable queue-based spin locks with timeout

Contention elimination by replication of sequential sections in distributed shared memory programs

Accurate data redistribution cost estimation in software distributed shared memory systems

Dynamic adaptation to available resources for parallel computing in an autonomous network of workstations

Parallel programming challenges for Internet-scale computing (entropia)

Source-level global optimizations for fine-grain distributed shared memory systems

High-level adaptive program optimization with ADAPT

Blocking and array contraction across arbitrarily nested loops using affine partitioning

Efficiency vs. portability in cluster-based network servers

Statistical scalability analysis of communication operations in distributed applications

LogGPS: a parallel computational model for synchronization analysis

Peer to peer and distributed computing

Efficient load balancing for wide-area divide-and-conquer applications

Content Provider	ACM Digital Library
Author	Kielmann, Thilo van Nieuwpoort, Rob V. Bal, Henri E.
Abstract	Divide-and-conquer programs are easily parallelized by letting the programmer annotate potential parallelism in the form of spawn and sync constructs. To achieve efficient program execution, the generated work load has to be balanced evenly among the available CPUs. For single cluster systems, Random Stealing (RS) is known to achieve optimal load balancing. However, RS is inefficient when applied to hierarchical wide-area systems where multiple clusters are connected via wide-area networks (WANs) with high latency and low bandwidth.In this paper, we experimentally compare RS with existing load-balancing strategies that are believed to be efficient for multi-cluster systems, Random Pushing and two variants of Hierarchical Stealing. We demonstrate that, in practice, they obtain less than optimal results. We introduce a novel load-balancing algorithm, Cluster-aware Random Stealing (CRS) which is highly efficient and easy to implement. CRS adapts itself to network conditions and job granularities, and does not require manually-tuned parameters. Although CRS sends more data across the WANs, it is faster than its competitors for 11 out of 12 test applications with various WAN configurations. It has at most 4% overhead in run time compared to RS on a single, large cluster, even with high wide-area latencies and low wide-area bandwidths. These strong results suggest that divide-and-conquer parallelism is a useful model for writing distributed supercomputing applications on hierarchical wide-area systems.
Starting Page	34
Ending Page	43
Page Count	10
File Format	PDF
ISBN	1581133464
DOI	10.1145/379539.379563
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2001-06-18
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Java Clustered wide-area systems Distributed supercomputing
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in