Computation of minimum firing time for general self-cleaning SWITCH-less program nets
A data-flow program net is a graph representation of data-Row programs consisting of three types of nodes, AND-node, OR-node and SWITCH-node, which represent arithmetic/logical, data merge and context switch operations respectively. Minimum firing (completion) time (T) under bar of a program net is an important element in computing parallel degree PARAdeg residing in a data-flow program and is defined as the minimum time when the program net is executed by enough many processors. In this paper, we propose algorithms to efficiently compute (T) under bar by contracting AND-nodes generally for self cleaning SWITCH-less program nets with arbitrary node firing time and give the experimental results of the algorithms to show the efficiency.
minimum firing time program net data-flow program node contraction