National Technical Reports Library

The National Technical Information Service acquires, indexes, abstracts, and archives the largest collection of U.S. government-sponsored technical reports in existence. The NTRL offers online, free and open access to these authenticated government technical reports. Technical reports and documents in its repository may be available online for free either from the issuing federal agency, the U.S. Government Publishing Office’s Federal Digital System website, or through search engines.

Details

Exploiting Flexibly Assignable Work to Imrpove Load Balance.

DE2003807440

Publication Date	2002
Personal Author	Pinari, A.; Hendrickson, B.
Page Count	14
Abstract	In many applications of parallel computing, distribution of the data unambiguously implies distribution of work among processors. But there are exceptions where some tasks can be assigned to one of several processors without altering the total volume of communication. In this paper, we study the problem of exploiting this flexibility in assignment of tasks to improve load balance. We first model the problem in terms of network flow and use combinatorial techniques for its solution. Our parametric search algorithms use maximum flow algorithms for probing on a candidate optimal solution value. We describe two algorithms to solve the assignment problem with log WT and (P) probe calls, where WT and (P), respectively, denote the total workload and number of processors. We also define augmenting paths and cuts for this problem, and show that any algorithm based on augmenting paths can be used to find an optimal solution for the task assignment problem. We then consider a continuous version of the problem, and formulate it as a linearly constrained optimization problem.
Keywords	Parallel computing Algorithms Optimization Least square fit Load balance
Source Agency	Technical Information Center Oak Ridge Tennessee
Corporate Authors	Lawrence Berkeley National Lab., CA.; Department of Energy, Washington, DC.; Sandia National Labs., Albuquerque, NM. Parallel Computing Sciences Dept.
Supplemental Notes	Prepared in cooperation with Sandia National Labs., Albuquerque, NM. Parallel Computing Sciences Dept. Sponsored by Department of Energy, Washington, DC.
Document Type	Technical Report
NTIS Issue Number	200317

Exploiting Flexibly Assignable Work to Imrpove Load Balance.

Exploiting Flexibly Assignable Work to Imrpove Load Balance.
DE2003807440

Publication Date	2002
Personal Author	Pinari, A.; Hendrickson, B.
Page Count	14
Abstract	In many applications of parallel computing, distribution of the data unambiguously implies distribution of work among processors. But there are exceptions where some tasks can be assigned to one of several processors without altering the total volume of communication. In this paper, we study the problem of exploiting this flexibility in assignment of tasks to improve load balance. We first model the problem in terms of network flow and use combinatorial techniques for its solution. Our parametric search algorithms use maximum flow algorithms for probing on a candidate optimal solution value. We describe two algorithms to solve the assignment problem with log WT and (P) probe calls, where WT and (P), respectively, denote the total workload and number of processors. We also define augmenting paths and cuts for this problem, and show that any algorithm based on augmenting paths can be used to find an optimal solution for the task assignment problem. We then consider a continuous version of the problem, and formulate it as a linearly constrained optimization problem.
Keywords	Parallel computing Algorithms Optimization Least square fit Load balance
Source Agency	Technical Information Center Oak Ridge Tennessee
Corporate Authors	Lawrence Berkeley National Lab., CA.; Department of Energy, Washington, DC.; Sandia National Labs., Albuquerque, NM. Parallel Computing Sciences Dept.
Supplemental Notes	Prepared in cooperation with Sandia National Labs., Albuquerque, NM. Parallel Computing Sciences Dept. Sponsored by Department of Energy, Washington, DC.
Document Type	Technical Report
NTIS Issue Number	200317