論文

査読有り
1999年5月

Minimum cut linear arrangement of p-q dags for VLSI layout of adder trees

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES
  • K Takagi
  • ,
  • N Takagi

E82A
5
開始ページ
767
終了ページ
774
記述言語
英語
掲載種別
研究論文(学術雑誌)
出版者・発行元
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG

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.

リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000080581000008&DestApp=WOS_CPL
ID情報
  • ISSN : 0916-8508
  • eISSN : 1745-1337
  • Web of Science ID : WOS:000080581000008

エクスポート
BibTeX RIS