A COMPILING TECHNIQUE FOR DATA-FLOW MACHINES - NEW ALGORITHM FOR OPTIMUM TRANSLATION FROM CONTROL FLOW GRAPH INTO DATA-FLOW GRAPH

In this paper an optimum algorithm to translate control flow graphs to dataflow graphs is proposed for dataflow execution of sequential prog rams. Some of the existing analysis methods restrict the specification of a program to be processed while others require a very high analysi s cost. The algorithm proposed in this paper (CD translation algorithm ), (1) with a very low cost, and (2) for any control structure that ca n be described by a control flow graph, (3) can generate dataflow prog rams that give an optimum dataflow execution, Furthermore, this propos ed analysis algorithm is designed to handle task level control flow gr aphs as well as instruction level control flow graphs, which are accep ted by the existing methods, so that optimum control is-possible for t ask level dataflow execution.