Border-Block Triangular Form and Conjunction Schedule in Image Computation

In-Ho Moon and Fabio Somenzi

To appear at Formal Methods in Computer Aided Design (FMCAD00), Austin, Texas, November 1-3, 2000


Conjunction scheduling in image computation consists of clustering the parts of a transition relation and ordering the clusters, so that the size of the BDDs for the intermediate results of image computation stay small. We present an approach based on the analysis and permutation of the dependence matrix of the transition relation. Our algorithm computes a bordered-block lower triangular form of the matrix that heuristically minimized the active lifetime of variables, that is, the number of conjunctions in which the variables participate. The ordering procedure guides a clustering algorithm based on the affinity of the transition relation parts. The ordering procedure is then applied again to define the cluster conjunction schedule. Our experimental results show the effectiveness of the new algorithm.

Server START Conference Manager
Update Time 26 Jun 2000 at 16:35:37
Start Conference Manager
Conference Systems