Allocating programs containing branches and loops within a multiple processor system. (English) Zbl 0599.68030

This paper addresses the problem of assigning the modules of a distributed program to the processors of a distributed system. The goal of such an assignment is to minimize the total execution and communication costs. A computational model of a distributed program, containing probabilistic branches and loops, is described using a directed graph whose edges represent precedence relations between modules. Efficient algorithms based on shortest path methods are presented to determine the optimum assignment on a distributed system containing N heterogeneous processors.


68N25 Theory of operating systems
Full Text: DOI