Computation of tasks modeled by directed acyclic graphs on distributed computer systems: allocation without subtask replication

The problem of optimally allocating the subtasks of computational tasks modeled by directed acyclic graphs on distributed systems with identical processors is considered. Branch-and-bound and heuristic algorithms are developed for solving the optimization problem of minimizing the system response time. The heuristics attempt to minimize interprocessor communication costs while balancing the processor load. An upper bound is derived for the error in the solution computed by the heuristic algorithms, and the performance of all algorithms is evaluated. Results presented indicate that the heuristic algorithms can provide fast and accurate solution approximations