版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构: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.