Mapping of dataflow programs by local structure analysis
Thomas A. Anastasio · 1995
This dissertation reports on an experimental investigation of the use of dataflow graph structure information to guide the static mapping of dataflow programs onto a simulated dataflow computer. In general, the mapping problem is computationally intractable, necessitating heuristic approaches. This work seeks to evaluate the usefulness of a variety of rather simple heuristics which are based on discovery of structure in the dataflow graph. The heuristics are tested by simulated execution of a suite of dataflow programs. The quality of a mapping heuristic is measured by comparison of the speedup curves obtained with the mapping and with random mapping. Estimators for maximum and expected speedup are developed based on analysis of application program parallelism profiles. The work of Arvind, Culler, and Maa is placed in a framework which examines the implicit assumptions about inter-epoch scheduling in parallelism profiles. The work is expanded somewhat by consideration of a variety of estimators of communication latency. Speedup estimates based on these methods are in generally good agreement with the experimental results. The dataflow programs which are used in the experiments are chosen to have widely differing characteristics which are thoroughly discussed. Similarly, the dataflow machine architecture is presented in detail. The architecture uses a three-dimensional toroidal communication network. The average inter-node distance of the network is examined as a function of size, leading to the conclusion that the distance grows gracefully with increasing network size. The very simple heuristic of mapping by graph locality has been found to be generally good. This heuristic is based on the assumption that neighboring operators communicate and may not require processor resources at the same time. Mapping neighbors to the same processor may reduce communication latency without loss of parallelism. We find speedup improvements of up to about 25% over random. Another simple heuristic emphasizes the mapping of program cycles. The underlying assumption here is that in a program with cycles, the preponderance of work is done by the operators in the cycles. Various cycle mapping heuristics are examined. Unlike locality mapping, cycle mapping sometimes causes serious deterioration of performance.