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

Towsley, Don

IEEE Trans. Software Eng. 12, 1018-1024 (1986).

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.

MSC:

68N25

Theory of operating systems

Keywords:

computer networks; distributed processing; multiprocessor system scheduling; distributed program; distributed system; shortest path methods