The problem of allocating task interaction graphs (TIGs) to heterogeneous distributed computing systems to minimize job completion time is investigated. The only restriction is that the interprocessor communication cost is the same for any pair of processors. This is suitable for bus-based local area network (LAN) systems such as Ethernet as well as fully interconnected multiprocessor systems. An optimal polynomial solution exists if sufficient homogeneous processors and communication capacity are available. This solution is generalized to form the basis of two faster heuristics, one for the case of homogeneous processors and the other for heterogeneous processors. The heuristics were tested extensively with 55200 systematically generated random TIGs and shown to be stable independent o...[ Read more ]

The problem of allocating task interaction graphs (TIGs) to heterogeneous distributed computing systems to minimize job completion time is investigated. The only restriction is that the interprocessor communication cost is the same for any pair of processors. This is suitable for bus-based local area network (LAN) systems such as Ethernet as well as fully interconnected multiprocessor systems. An optimal polynomial solution exists if sufficient homogeneous processors and communication capacity are available. This solution is generalized to form the basis of two faster heuristics, one for the case of homogeneous processors and the other for heterogeneous processors. The heuristics were tested extensively with 55200 systematically generated random TIGs and shown to be stable independent of the size of the TIG. A performance model is also proposed to predict the performance of the heuristic algorithms. This model is successful in explaining the experimental results qualitatively.