整数計画法を用いた3層ボトルネックチャネルトラック割当て法

情報処理学会

書誌事項

タイトル別名
  • Three-layer Bottleneck Channel Track Assignment by ILP

抄録

性能仕様を満たすアナログ集積回路を低面積で実現する自動設計技術が求められている．ボトルネック配線方式における，各ネットの端子がボトルネック領域の左右の接続領域の上辺に 1 端子ずつ配置された 2 端子ネット問題「U 字型 3 層物理配線問題」に対し，整数線形計画法を用いて各ネットのトラック割当てと配線層割当てを決定するアルゴリズムを提案する．すべての許容解を表現できる定式化を用いると，ネット数 30 の問題に数時間以上の計算時間を要するが，提案手法は，各ネットの配線パターンを，配線可能性を考慮して 3 種類に限定することで，ネット数が 300 程度の問題に対して数秒で解を出力する．

Design automation that realizes analog integrated circuits to meet performance specifications in a small area is desired. In this paper, An algorithm for a bottleneck channel routing problem that uses Integer Linear Programming is proposed. The proposed algorithm determines the track and layer assignment of nets for three-layer bottleneck channel routing problem with layout constraints in which pins of each net are placed on the upper boundary of the adjacent regions on both sides of the bottleneck channel. The proposed algorithm restricts the routing pattern of each net to one of three patterns by taking feasibility into account, and outputs a solution in a few seconds when the number of nets is 300.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ