Exploiting Flexibly Assignable Work to Imrpove Load Balance.

Pinari, A. ; Hendrickson, B.

Technical Information Center Oak Ridge Tennessee

关键词: Parallel computing;    Algorithms;    Optimization;    Least square fit;    Load balance;   

RP-ID  :  DE2003807440

学科分类：工程和技术（综合）

美国|英语

来源: National Technical Reports Library

【 摘 要 】

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.