咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Minimum cut linear arrangement... 收藏

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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分