Optimal Replication of Series-Parallel Graphs for Computation-Intensive Applications
抄録
We consider the replication problem of series-parallel (SP) task
graphs where each task may run on more than one processor. The objective
of the problem is to minimize the total cost of task execution and
interprocessor communication. We call it, the minimum cost replication
problem for SP graphs (MCRP-SP). In this paper, we adopt a new
communication model where the purpose of replication is to reduce the
total cost. The class of applications we consider is
computation-intensive applications in which the execution cost of a task
is greater than its communication cost. The complexity of MCRP-SP for
such applications is proved to be NP-complete. We present a
branch-and-bound method to find an optimal solution as well as an
approximation approach for suboptimal solution. The numerical results
show that such replication may lead to a lower cost than the optimal
assignment problem (in which each task is assigned to only one processor)
does. The proposed optimal solution has the complexity of O(n22nM), while
the approximation solution has O(n4M2), where n is the number of
processors in the system and M is the number of tasks in the graph.
(Also cross-referenced as UMIACS-TR-93-4.1)