Allocation for the SANDAC multiprocessor system
T.M. Ravl, Ercegovac · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1986
This report describes an algorithm for the static allocation of tasks in a general Dataflow Multiprocessor and the SANDAC IV system in particular. Initially a model of execution and the underlying assumptions about the architecture are outlined. The authors then discuss a Graph Reduction algorithm for preprocessing the computation graph. The Graph Reduction algorithm reduces a fine grain graph to an optimal grain graph. The heuristic allocation algorithm is presented and is based on giving precedence to critical paths and minimizing the communication time between tasks. The performance of the algorithm is analyzed and the effect of varying parameters is studied. Subsequently an alternative variation with better characteristics is proposed.