ON IMPROVING THE PERFORMANCE OF TREE MACHINES

In this paper we introduce a class of trees, called generalized compre ssed trees. Generalized compressed trees can be derived from complete binary trees by performing certain 'contraction' operations. A general ized compressed tree CT of height h has approximately 25% fewer nodes than a complete binary tree T of height h. We show that these trees ha ve smaller (up to a 74% reduction) 2-dimensional and 3-dimensional VLS I layouts than the complete binary trees. We also show that algorithms initially designed for T can be simulated by CT with at most a consta nt slow-down. In particular, algorithms having non-pipelined computati on structure and originally designed for T can be simulated by CT with no slow-down.