Name
Abstract | ||
|---|---|---|
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 minimizes 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. |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1007/3-540-40922-X_6 | FMCAD |
Keywords | Field | DocType |
conjunction scheduling,conjunction schedule,new algorithm,image computation,dependence matrix,active lifetime,transition relation part,border-block triangular form,cluster conjunction schedule,transition relation,clustering algorithm,procedure guide | Cluster (physics),Heuristic,Matrix (mathematics),Scheduling (computing),Computer science,Permutation,Algorithm,Cluster analysis,Triangular matrix,Computation | Conference |
Volume | ISSN | ISBN |
1954 | 0302-9743 | 3-540-41219-0 |
Citations | PageRank | References |
39 | 1.94 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| In-Ho Moon | 1 | 161 | 11.98 |
| Gary D. Hachtel | 2 | 1069 | 140.38 |
| Fabio Somenzi | 3 | 3394 | 302.47 |