DocumentCode :
2738069
Title :
Adaptive quality equalizing: high-performance load balancing for parallel branch-and bound across applications and computing systems
Author :
Mahapatra, Nihar R. ; Dutt, Shantanu
Author_Institution :
Dept. of Electr. & Comput. Eng., State Univ. of New York, Buffalo, NY, USA
fYear :
1998
fDate :
30 Mar-3 Apr 1998
Firstpage :
796
Lastpage :
800
Abstract :
In this paper we present an adaptive version of our previously proposed quality equalizing (QE) load balancing strategy that attempts to maximize the performance of parallel branch-and-bound (B&B) by adapting to application and target computing system characteristics. Adaptive QE (AQE) incorporates the following salient adaptive features: (1) Anticipatory quantitative and qualitative load balancing mechanisms. (2) Regulation of load information exchange overhead. (3) Deterministic load balancing in extended neighborhoods instead of just immediate neighborhoods as in non-adaptive QE. (4) Randomized global load balancing to fetch work from outside the extended neighborhood. AQE fields speedup improvements of up to 80%, and 15% on the average, compared to that provided by QE for several real-world mixed-integer programming (MIP) problems, and near-ideal speedups for two of the largest problems in the MIPLIB benchmark suite on an IBM SP2 system
Keywords :
computational complexity; integer programming; parallel algorithms; resource allocation; IBM SP2 system; adaptive features; adaptive quality equalizing; computing system characteristics; deterministic load balancing; high-performance load balancing; load balancing mechanisms; load information exchange overhead; parallel branch-and bound; quality equalizing load balancing strategy; randomized global load balancing; real-world mixed-integer programming problems; Adaptive equalizers; Application software; Computer applications; Concurrent computing; Cost function; Load management; Optimization methods; Parallel processing; Search problems; Space exploration;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel Processing Symposium, 1998. IPPS/SPDP 1998. Proceedings of the First Merged International ... and Symposium on Parallel and Distributed Processing 1998
Conference_Location :
Orlando, FL
ISSN :
1063-7133
Print_ISBN :
0-8186-8404-6
Type :
conf
DOI :
10.1109/IPPS.1998.670019
Filename :
670019
Link To Document :
بازگشت