A technique to derive time costs of data flow programs

The authors present a technique for analyzing the time cost behavior of data-flow programs that are loop free or contain non tested loops that meet certain constraints. It is assumed that the underlying computer system is a dynamic data-flow computer which has sufficient processors to support the execution of data-flow programs. The token model is modified to describe both the execution and time cost behavior. The technique is similar to some flow-analysis and graph-reduction techniques. In analyzing the time cost of a data-flow program, the technique first determines the number of tokens that pass through each edge in the program. All nodes that are neither input nor output nodes are then deleted. Every time a node or an edge is deleted, the time cost associated with it is properly distributed within the program. Since the resultant program only contains edges that connect input and output nodes, the time cost of the program can be easily obtained. Two examples are given to show the use of the technique