Dynamic load balancing for parallel interval-Newton using message passing

Chao‐Yang Gau

doi:10.1016/S0098-1354(02)00006-6

2002-06-01

Chao‐Yang Gau

Mark A. Stadtherr *

DOI：10.1016/S0098-1354(02)00006-6

原文链接

查看原文

摘要

En 中文

Branch-and-prune and branch-and-bound techniques are commonly used for intelligent search in finding all solutions, or the optimal solution, within a space of interest. The corresponding binary tree structure provides a natural parallelism allowing concurrent evaluation of subproblems using parallel computing technology. Of special interest here are techniques derived from interval analysis, in particular an interval-Newton/generalized-bisection procedure. In this context, we discuss issues of load balancing and work scheduling that arise in the implementation of parallel interval-Newton on a cluster of workstations using message passing, and describe and analyze techniques for this purpose. Results using an asynchronous diffusive load balancing strategy show that a consistently high efficiency can be achieved in solving nonlinear equations, providing excellent scalability, especially with the use of a two-dimensional torus virtual network. The effectiveness of the approach used, especially in connection with a novel stack management scheme, is also demonstrated in the consistent superlinear speedups observed in performing global optimization. (C) 2002 Elsevier Science Ltd. All rights reserved.

Keyword:

parallel computing

nonlinear equations

optimization

branch-and-prune

branch-and-bound

interval analysis