ON IMPROVING THE PERFORMANCE OF TREE MACHINES

作     者：GUPTA, AK WANG, H 

作者机构：PURDUE UNIVDEPT COMP SCIW LAFAYETTEIN 47907 

出 版 物：《INTERNATIONAL JOURNAL OF HIGH SPEED COMPUTING》 (国际高速计算杂志)

年 卷 期：1995年第7卷第2期

页      面：251-263页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：BINARY TREE MACHINE EMBEDDING HYPERCUBE PARALLEL ALGORITHM PIPELINED COMPUTATION NODE LOAD SIMULATION VLSI LAYOUT (2-DIMENSIONAL AND 3-DIMENSIONAL) 

摘      要：In this paper we introduce a class of trees, called generalized compressed trees. Generalized compressed trees can be derived from complete binary trees by performing certain contraction operations. A generalized 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 have smaller (up to a 74% reduction) 2-dimensional and 3-dimensional VLSI layouts than the complete binary trees. We also show that algorithms initially designed for T can be simulated by CT with at most a constant slow-down. In particular, algorithms having non-pipelined computation structure and originally designed for T can be simulated by CT with no slow-down.