Program graph allocation in distributed multicomputers

Data-flow multiprocessors have been shown to be a very efficient solution to the problem of multiprocessor schedulability. Recent research has demonstrated the critical importance of the proper allocation of program partitions to Processing Elements. We first describe in this paper several heuristic algorithms which have been used for program allocation. We then describe the layered approach to the problem of allocation (syntax directed and graph partitioning). A parallel approach to simulated annealing is used to perform allocation at the data-flow graph level. It is also shown how the results apply to the allocation problem in the Hughes Data-Flow Machine. Finally, simulation results indicate the validity of the solutions.