Data flow program reduction

Text includes handwritten formulasIn data flow programs, instructions execute when their operands become available. The arrival of data thus acts as the control as well and leads to models with a single graph representing the data and the control flow. In this thesis, we transform a data flow model to one with a separate data and control flow. This is motivated by 'reductions' that can be carried out on the transformed model and by the ease of implementing such models by conventional techinques. Data flow models are networks consisting of operators and control nodes connected by data paths. The operator nodes carry out a functional operation on the input data while the control nodes route the data correctly. In directly implementing a data flow program, 'copy' operations are required for the control nodes. We specify conditions which allow the removal of these copy operations in the transformed model. The problem is significant since the control nodes often make up more than half of the data flow program The control flow is then simplified and it is demonstrated that this simplification can lead to an increase in parallelism. Finally, the implications of the analysis to extant architectures is considered and it is shown how the results motivate a separation of the data and the control flow in implementing a data flow processor