Allocating programs containing branches and loops within a multiple processor system

Abstract

The problem of assigning the modules of distributed program to the processors of a distributed system is addressed. 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 by a directed graph whose edges represent precedence relations between modules. Efficient algorithms based on short-path methods are presented to determine the optimum assignment on a distributed system containing N heterogeneous processors.