A method of computing minimum firing time for self-cleaning SWITCH-less program nets

A program net is a graph representation of data-flow programs consisting of three types of nodes, AND-, OR- and SWITCH-nodes, which represent arithmetic/logical, data merge and context switch operations, respectively. Parallelism residing in data-flow programs has been studied through computing PARAdeg = Sigma((f) over bar(z(i))tau(i))/T for SWITCH-less program nets, where (f) over bar(z(i)) and tau(i) are maximum firing number and single firing time of node z(i), respectively and T is minimum firing time of the program net. The numerator of PARAdeg can be efficiently computed; however, computation of the denominator is usually costly in tel ms of time. In this paper,,ve propose algorithms to compute T by contracting AND-nodes for self-cleaning SWITCH-less program nets. (C) 1998 The Franklin Institute. Published by Elsevier Science Ltd.