Minimum cut linear arrangement of <i>p-q</i> dags for VLSI layout of adder trees

作     者：Takagi, K Takagi, N 

作者机构：Nara Inst Sci & Technol Grad Sch Informat Sci Ikoma 6300101 Japan Nagoya Univ Dept Informat Engn Nagoya Aichi 4648603 Japan 

出 版 物：《IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES》 (电子信息通信学会汇刊：电子学、通信及计算机科学基础)

年 卷 期：1999年第E82A卷第5期

页      面：767-774页

核心收录：

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

主　　题：graph algorithm minimum cut linear arrangement VLSI layout adder tree multiplier 

摘      要：Two algorithms for minimum cut linear arrangement of a class of graphs called p-q dags are proposed. A p-q dag represents the connection scheme of an adder tree, such as Wallace tree, and the VLSI layout problem of a bit slice of an adder tree is treated as the minimum cut linear arrangement problem of its corresponding p-q dag. One of the two algorithms is based on dynamic programming. It calculates an exact minimum solution within n(O(1)) time and space, where n is the size of a given graph. The other algorithm is an approximation algorithm which calculates a solution with O(log n) cutwidth. It requires O(n log n) time.