Optimal assignments in broadcast networks

A program whose execution is distributed among several processors in a broadcast system has a total execution cost equal to the sum of processor costs and communication costs, which are functions of the amount of data transmitted and the average transmission delays. A critical delay x is a value of average transmission delay such that no assignment is minimum-cost for average delays both smaller and larger than x. An algorithm is presented for finding the set of all q critical delays of a program that requires computing O( q) optimal assignments at fixed values of average delay. For p=2 processors, H.S. Stone´s (1977) assignment graph approach can be used to find an optimal assignment, while for p>2, S.H. Bokhari´s (1981) dynamic programming approach for programs with tree-structured calls graphs, or an A* algorithm for the more general case, can be used. When more than one optimal assignment exists, an efficient algorithm is described for finding optimal assignments with minimum channel utilization for p=2 that involves the creation of a compact graphical representation of all optimal assignments of the program. Bokhari´s algorithm and the A* algorithm can be easily extended to find optimal assignments with minimum transmission costs when p>2