2層チャネル配線について
（昭和59年11月30日 原稿受付）
情報工学科永松正博
On the 2−Layer Channel Routing
by Masahiro NAGAMATSU
Abstract
In this paper we propose a new 2−layer channel routing algorithm． Terminals are interconnected with horizontal segments on one layer and vertical segments on the other． This algorithm is a vertical type and the routing progresses column by column left to right． With this algorithm every channel can be routed even if its vertical constraint graph has loops． Experimental results indicate that this algorithm is successful． For example，96％of the 90％−terminaFdensity channels and 92％of 100％．terminaLdenslty channels can be routed within one track of channel dencity．
の配置の際にチャネルと呼ばれる配線領域を形成してお 1・まえがき @ き，このチ。ネル内に酉己線を行うものである．チ。ネ，レ
半導体のプロセス技術の進歩により，LSIの集積度 割当法は2段階に別れており，まず始めに，各ネットの は毎年1．5から2倍の割合いで増大し続けており，1 配線がどのチャネルを通るかを大まかに決定し（グロー チップあたりのゲート数が数万を越えた理論LSIも出 バル配線），次に，個々のチャネル内の配線を行う 現した現在は，VLSIの時代に入ったといわれる。この （チャネル配線）ものである。配線時間が短く，しかも
ような大規模なシステムを人手だけで設計することユよ不 高い配線率が得られることがチャネル割当法の特徴であ 可能であり，VLSIの設計の各フェーズにおける，設計 る。この手法は従来，ビルディングブロック方式，マス および検証の自動化を総合的に，かつ，高度に確立する タースライス方式のLSIの設計に用いられて来たが，
ことが要求されている。 VLSIの配線においても主流になると思われる。
VLSIのレイアウト設計とは，回路が決定した後，各 本論文では，新しい2層チャネル配線アルゴリズムを セルの配置，および，各セル間の配線を決定し，最終的 提案し，それが非常に厳しい条件のチャネルに対しても，
なマスクパターン情報を作成することである。その際， 最適に近い配線を行うことを実験により示す。
電気的な条件を満足し，かつ，チップ面積の最小化を計
2．定義と準備 ることが目標となる。集積度の増加にともない，チップ
面積の大部分を配線がしめ，また，遅延時間の原因の大 チャネルは図一1に示すような長方形をした配線領域で 部分が配線に由来するようになることを考えると，配置 ある。チャネルの上端と下端には端子が並んでおり，そ 配線は，VLSIの設計において非常に重要な問題である。 れらの間を結線することが要求されている。互いに結線 ところが，配置配線を決定することは，一般に組合わせ されるべき端子の集合をネットと呼ぶ。図において端子 問題であり，その困難さは集積度（セルの個数）の増加 に付けられた数字は，その端子が属するネットの番号を に対して，指数関数的に増加する。5） 表わす。一般にチップ上に配線を行う場合，問題を簡単 過去，多くの配線手法が提案されている。3畑BP） に，また，扱い易くするために，チップ上に格子（その その中で，チャネル割当法3）と呼ばれる手法は，セル 間隔は最小パターン間隔と呼ばれ，製造技術の進歩によ
コラム1コラム2コラム3コラム4コラム5コラム6コラム7コラム8
トラック3
トラック2 トラック1
図一1 チャネルとチャネル配線
1
図一2 チャネルとチャネル配線を表わすグラフ 図一3 制約グラフ
り，現在ではサブミクロンのオーダーになりつつある） E1＝‖〈c・Z・2＞・〈c＋1・Z・2＞）11≦c≦L−1・
を考え，その格子上に配線を行う。チャネル配線におい 1≦τ≦WU
ても，この格子上に配線することが要求される。格子の ｛（〈c・ち1＞・〈cパ＋1・1＞）11≦c≦L・
水平方向（図に書いた場合の左右の方向）の直線を下か 1≦τ≦W−1｝∪
ら順にトラック1，2，．．．と呼び，垂直方向（図に書い ｛（〈c・ち1＞・〈c・ち2＞）i1≦c≦L，1≦τ≦W た場合の上下の方向）の直線を左から順にコラム1，2， E2＝｛（〈c，W＋1，1＞，〈c，W，1＞）ll≦c≦L｝
と呼ぶ。 ここで， ，Z，ヵは整数値を取る。頂点〈C，Z，ヵ〉は，
チャネル配線の配線領域は2層構造になっていて，こ 3次元空間上の，エ座標がc，y座標が ，9座標がρ の2層を使用して配線を行う。例えば，図一1に示す例 の位置に置かれているとする。Lをチャネルの長さ，
の場合，太い破線で示す配線は第1層に，太い実線で示 Wをチャネルの幅，もしくは，トラック数と呼ぶ。図 す配線は第2層に行っている。配線間の容量を小さくす 一1のチャネルとチャネル配線を，この定義に従って正確 るためと，問題を簡単にするために，第1層には垂直方 に書くと図一2のようになる。
向の配線のみを，第2層には水平方向の配線のみを行う γ0に属する頂点を下側端子，γ2に属する頂点を ように制限する。 上側端子と呼ぶ。コラム6の上側端子をtOP（6），下側端 以上の考察より，チャネルを次に示す無向グラフG 子をbot（c）で表わす。 N個のネットが存在するとし，
＝（UE）で定義する。 各ネットに1，2，＿，Nと番号を付け，各端子がどの V＝γ0∪γ1UV2 ネットに属するかを関数net：γ0∪γ2−｛0，1…，Mで VO＝｛〈c，0，1＞11≦c≦L｝ 表わす。 net（u）＝0のときは，端子ηはどのネットに V1＝｛〈c，ε，p＞11≦c≦L，1≦Z≦W，1≦ρ≦2｝ も属さない。このような端子を空端子と呼ぶ。1≦e V2＝｛〈c， W＋1，1＞11≦c≦L｝ ≦Nなる各εに対して，1｛∋net＠）＝ε｝1＞2で E＝EOUE1UE2 あると仮定する。
EO＝｛（〈c，0，1＞，〈c，1，1＞）l l≦c≦L｝ colr（θ）で，ネットεに属する端子のエ座標の最大値
を，coll（ε）で最小値を表わす。 coll（θ）＝colr（ε）である ｛0「0∈γ， netb）＝e｝， G．＝（γ。， E∩（V。×γ．））と定義
ネットeは配線にあたり考慮する必要がないので，各e する（G．をネットεの配線と呼ぶ）。次の①および②
に対して，coll（ε）＜colr（ε）であると仮定する。｛colr（θ） が成立する。
11＜ε〈N｝の最大値をL1とする。チャネル配線の ①各εに対して， G，は連結である。
場合，一般には，配線のための領域がL1よりもさら ②各姻eキ∫）に対して，γ．∩肪＝φである。■
に右側に出る。この出る長さは最大で［W／2］である。 チャネル配線が可能であるためには，明らかに，佐 ここでは，とりあえず，L1＋［W／2］〈Lであると 本以上のトラックが必要である。
仮定しておく。 図一1において，ネット1の配線は，トラック3に水 実数値コCに対して，4（勾二1｛61coll（θ）≦エ≦ 平方向の配線があり，それから各端子に配線が垂直に出 colr（ε）川と定義する。コラムcに対して，4τ）をコラ ているという形をしている。この様な水平方向の配線を ムτの密度，4（c＋0．5）をコラムcとコラム ＋1の 幹線といい，それから出る垂直方向の配線を支線という。
間の密度と呼ぶ。 各ネットの幹線を1本のトラックに割当てることにより max｛4（c）lc＝1，2，＿，L｝をCチャネル密度と呼び， 配線を行う手法を，幹線支線方式という。図一1に示す例 46と書く。max｛4（6＋0．5）1τ＝1，2，＿， L−1｝ の場合，コラム1においてネット1の端子がネット2の
を5チャネル密度と呼び，ゐと書く。単にチャネル密 端子の上にあることより，ネット1の幹線はネット2の 度という場合はCチャネル密度を意味する。直はまた， 幹線より上のトラックに割当てられなければならない。
max l｛εlcoll（θ）〈エ〈colr（θ）｝1と定義することも 同様に，コラム2における考察より，ネット2の幹線は できる。一般に，45≦4c≦45＋1である。 ネット3の幹線より上のトラックに割当てられなければ ならない。このような，端子の位置の上下関係により
3・チャネル配線 ネ。ト間に生じる制約条件を浦向グラフで表わしたも
チャネル配線とは，次の条件1を満足するように，関 のを制約グラフと呼ぶ。図一1に示すチャネルの制約グ 数netの定義域をyoUV2からγに拡張することであ ラフを図一3に示す。
ると定義することができる。 left・edge 3）法は最初に提案されたチャネル配線手法
［条件1］1≦e≦1Vなる各θに対して， V．＝ であり，幹線支線方式である。この手法は，ネット間に 1 2 3 4 5
3
1 2 3 4 5
1 2 3 4 5 1 2 3 4 5
（a） （b） （c）
図一4 幹線分割により使用するトラック数を減少させる 1 2 3
1 2 3
3 1 2
1・く2
3 1 2
（a） （b） （c）
図一5 幹線分割により制約ループを解消する
o o o 9 9
・ ● ● ● ● コ コ ロ コ ロ コ コ ロ ロ ロ
F−」 L−Lr −」r
ロ コ ロ コ ロ ロ
： ； 8 ゴ ロ ロ の
↓↓ ↓ ▲ 旦
（εし） （b） （c）
図一6 幹線分割の例
前述の制約条件が存在しない場合には，最適な配線を行 4章で提案する（Rivest 11）も同様のアルゴリズムを提 う。しかしながら，制約条件が存在する場合には，使用 案している）。このアルゴリズムは任意のチャネルを短 するトラック数が増加したり，配線不能になることがあ い時間で100％配線する。しかも，5章で示すように，大 る。この様な例を図一4，図一5に示す。図一4の場合， 部分のチャネルをチャネル密度に近い本数のトラックで 制約グラフは（b）のようになり，幹線支線方式では（a） 配線することができる。
のように5本のトラックを必要とする。しかし、（c）に
＿ 、 4．垂直型チャネル配線アルゴリズム 不すように，各不ットの幹線を分割して（これを幹線分
割という）配線を行えば2本のトラックで配線できる。 垂直型チャネル配線アルゴリズムは，左側のコラムよ 一方，図一5の場合，制約グラフは（b）のように有向閉 り順に，コラム1，コラム2，＿と配線を行う。以下，
路（これを制約ループという）を持ち，（a）に示すよう 垂直型チャネル配線アルゴリズムCHROUTERをc言 に幹線支線方式では配線できない。この場合も，（c）に 語風に記述する。net（〈c， z，ρ〉）は3次元の配列net［ε，
示すように幹線分割を行い，制約ループを解消すれば， ，ρ］で表現されており（以後，netは配列を意味する），
配線可能となる。 CHROUTERの実行前には， net［ら0，1］， net［6， W 幹線分割の例を図一6に示す。（c）のように，その ＋1，1］（1≦c≦L）は各端子が属するネットを示し
ネットの端子のある範囲の外で幹線分割をすることを ており，net［らちρ］（1≦ε≦L，1≦Z≦W，1
「折返し」という。浅野川は，幹線分割による制約 ≦〃≦2）はすべて0である。
ループの解消の方法について議論している。Deutch 2）@ ［アルゴリズムCHROUTER］
Yoshimura 12）らの方法，および，それらを改良，変形 CHROUTER（）
した数多くの方法は幹線分割により使用するトラック数 lint ，窮
を減少させている。これらの方法はいずれも，各ネット for（ ＝1； ＜＝1レル7；十十τ）∫［z］＝0；
を2端子サブネットに分解し，それらに対して幹線支線 c＝1；
方式を適用したものと考えることができ，従って図一6 while（（c〈＝L1）ll（∫［z］！＝Oforsomez（
（a）のタイプの幹線分割しか行えない。しかも，幹線分 1〈＝z〈＝ル））
割できるコラムは，そのネットの端子があるコラムに限 ｛∫［0］＝net［ら0，1］；
られる。従って，これらの方法では，図一4（c），図一5 f［W＋1］＝net［ρW＋1，1］；
（c）に示す配線は行うことはできない。 COLROUTER（c）；
梶谷6），河本7），永松10）らは，2層チャネル配線に ＋＋c；
対して，チャネル密度に近い本数のトラックで配線でき ｝ るためのチャネルの条件について議論している。これら ｝ の議論に使用されたチャネル配線アルゴリズムは，コラ ■
ムごとに配線を進めていくものであり（垂直型チャネル COLROUTER（τ）はコラムεの配線を行うものであ 配線アルゴリズムと呼ばれる），多彩な幹線分割を簡単 り，後に具体的な記述を与えるが，COLROUTER（6）
に行うことがてきる。これらのアルゴリズムを一般的な の実行の直前の時点におけるチャネルの配線の状態は以 チャネルに対しても適用できるように拡張したものを， 下のようになっている。
コラムc．1までの配線が完了している。さらに，コ COLROUTER（c）の配線は・このようにコラムc−1よ ラム仁1からコラムcにどのように配線が渡されるか 、り渡された配線，および・コラムcの端子から出た配線 が，配列∫により次のように表わされている。 をコラムCにおいて上下に移動させ，適当なトラックよ
∫［。］一。。・［。・，1］ りコラム・＋・に渡すことである・以下・COLR°U−
1〈t＜Wなる各tに対して， TERの記述を与える。
一｛∴難三璽よ璽V三㌦配一る＊／
り渡される配線がない場合 for（z＝＝1；z＜＝W；十十z）net［ρち2］＝∫［彦］；
f［W十1］一…［ρW＋1，1］ ｝
1≦ε≦Nになる各εに対して，net（ε）＝1｛ 11≦ UP（t）／＊トラックtの配線が上に移動できるか否かを
，＜剛田一。川と麟する． @ 判定し・移動できるならば移動できる先のトラ・クのう
コラムcの配線とは，コラム仁1から渡された配線 ち一番下のものを返す＊／
および，コラム6の端子に対して，コラムc上の配線を int z；
行い，コラムεよりさらに右方に延びてゆく配線をコラ ｛int Z 1；
ム。＋1に渡すことである．コラム・の配線の例を図一 （・＜ ・＜一助齢・・［・・1・2］＝°か∫田）
7に示す．このコラム。の配線の直前の時点において， 齢・・［…］・…［・・＋1・1］・……t［・
f［。］一。4，∫［1］一∫［1］一・，∫［2］一・3，f ・1・1］がすべて゜カ ∫［・］であるような 1が存
［3］一。，f［、］一。1，∫［5］一・2，∫［6］一・1， 在すれば・e・…（そのような 1の中で最小のも
∫［7］一。1であり，配線後は，∫［・］一・4，∫［2］ の）・存在しなけれ｛ボ・etu「n（°）・
−0，∫［3］一・3，∫［4］−OJ［5］一・2ゴ［6］ ｝
一。である．ネ。ト．・の配線はトラ。ク4とトラ・ク DOWN（ ）／＊トラ・クtの配綱ぎ下に移動できるか 6を通りコラム6−1よ 闢nされ，コラムcの上側端子 否かを判定し，移動できるならば移動できる先のト と結ばれ，コラム・で配線が終了する．ネ・ト・2の配 ラ・クのうち一番上のものを返す＊／
線は，トラック5を通りコラムc−1より渡され，その intτ；｛UP（z）と同様｝
ままトラ。ク5を通りコラム・＋1に渡される．ネ・ト MOVEUP（・）／＊トラ・ク・の配線をトラ・クUP（z）へ θ3の配線は，トラック2を通りコラム6−1より渡され， 移動する＊／
トラック2からトラック3に移され，トラック3を通り int Z；
コラムc＋1に渡される。ネットθ4の配線は，コラムc ｛intτ1；
の下側端子から出て，トラック1を通りコラム6＋1に t1＝UP（ε）；
渡される。 if（ε1！＝o）
｛n・t［ 1］＝n・t［Ω＋1・1］＝…＝n・t ；三↑コ；ム＝ ［・・1・1］一…［・…2］一∫［ 1］一∫［・］・
。1 ∫巨］＝0；
el e2 e1
e3
｝
｝
MOVEDOWN（z）／＊トラック の配線をトラック DOWN（z）へ移動する＊／
int Z；｛MOVEUP（t）と同様｝
float str（t）／＊トラックzの配線の移動（幹線分割）の 必要度を返す（正ならば上，負ならば下）＊／
図一7 コラムCにおける配線 int Z；
lint，1， c 1；float s ①strωにおいて，コラムcのすぐ右側で始まるネット ／＊α1・a2・α3は配線のためのパラメータ＊／ の端子がある側（上側，下側）のトラックを空けること 5＝0； も評価する。
if（∫［ ］＝∫レ1］for some 1（× 1＜＝W）） ②COLROUTER（ε）においてMOVEUP（0）および 5＋＝α1； MOVEDOWN（0）が実行できない場合， Wを1増加
if（〆［z］＝∫［ 1］for some z 1（1＜＝君1＜z））8一 して配線を続行する。
5−＝α1； ③0（WLIog W）の時間で配線を行う。
for（c 1 ＝ c； ε1〈＝ 1二 1 ； 十十 6 1 ）
5．計算機による実験
｛if（（net［c1 ， W十1 ，1］＝∫［τ］）＆＆（net［（・1 ，
0・1］＝∫［ 1］！＝Ofor someτ1（× 1＜ 垂直型チャネル配線アルゴリズムCHROUTERを使 ＝助） い，ランダムに作ったチャネルの配線を行い，端子密度 5＋＝α2＊（W− ）／（W＊（α3＋ε1−c））； を変化させて，配線に使用したトラックの本数を調べた。
if（（net［61，0，1］＝∫［τ］倣（net［c1，W 結果を表1に示す。端子密度は100×（空端子でない端 ＋1，1］＝∫［ 1］！＝Oforsomez1（1＜ 子の個数）／L1である。各端子密度に対し， L 1＝
＝，1＜z）） 150のチャネルを1000個ランダムに発生した。ネットは r＝α2＊ （W＊（α3＋c1−c））； すべて3端子からなる。表1の4εと書かれた欄は，
｝ 1000個のチャネルのチャネル密度の平均を示す。使用水 return（∫）； 平トラック数4c＋ゴC＝0，1，2，3，4）と書かれた ｝ 欄は，1000個のチャネルのうちで，チャネル密度にゴ本
PASSO／＊コラムτ＋1に配線を渡す＊／ 足した本数のトラックで配線できたものの個数を示す。
｛int Z， 1； チャネル配線の場合，配線に使用した領域がL1より for（τ＝1； ＜：＝W；十十 ） もさらに右側に出ることがある。この出たコラム数を if（（nt（∫レ］ニ＝1）＆＆（colr（ア［z］）＜ニc）） 1000個のチャネルに対して平均を取ったものが，
∫［z］＝0； addcolと書かれた欄に示された数字である。この値が ｝ 非常に小さいことより，L1より右側にほとんど出な COLROUTER（c）／＊コラムcの配線＊／ いことが分かる。「折返し」により配線が長くなった長 int c； さの，1000個のチャネルに対する平均をpostと書かれ
｛int ， z 1； た欄に示す。一番下の0で囲んだ行は初期トラック数 receiveO； （W）を46＋2にして実験を行った結果であり，そ ifσ［0］！＝0） MOvEUP（0）； の他の行は初期トラック数を4、にした結果である。
if（∫［W＋1］！＝o）MOvEDOWN（W＋1）； 端子密度80％以下では，すべてのチャネルに対して while（σ［z］！＝0）倣（（（str（ ）＞0）倣（UP（の））‖ addcol＝0である。また端子密度90％の場合，2個の （（str（ ）＜0）＆＆（DOWN（z））））であるtが存在する） チャネルに対してのみaddcol＝1である。端子密度 ｛ 1＝そのようなtの中でlstr（z）が最大のもの； 100％の場合， addcol＞0であるチャネルの個数はかな if（stre 1）＞0）MOVEUPぴ1） り多いが，初期トラックを4、＋2にすればかなり減少 else MOVEDO s N（ 1）； する。 postも同じ傾向にある。
｝ 一般に，パラメータを変更して複数通りの配線を行い，
pass（）； そのなかで最良の配線を選ぶことにすれば，表1の結果 ｝ ■ はさらに改善される。例えば，端子密度100％の場合，
アルゴリズムを分り易くするため，簡単に記述したが， 3通りの配線を行った結果，997個のチャネルがaddcol 5章の実験で使用するプログラムは，さらに以下のこと ＝0，トラック数4c＋2以下で配線可能であった。図一
を行う・ 8に端子密度1・・％，トラ。ク数娠一78），。dd。。1一
表一1 端子密度と使用トラック数の関係 使用 トラック数 端子密度 dc addcol post
dc十〇 dc十1 dc十2 dc十3 dc十4 50 40．2 0 0．19 882 997 1000 1000 1000 60 47．8 0 0．36 844 996 1000 1000 1000 70 55．4 0 0．77 787 995 1000 1000 1000
80 62．9 0 1．32 780 991 999 1000 1000
90 70．5 0，002 4．00 663 962 997 1000 1000
100 77．6 0，314 35．19 550 927 993 1000 1000
（100） （77．6） （0．056） （8．18） （0） （0） （990） （999） （1000）
0，post＝82の例を示す。図中，印の付いたネットは 密度が90％ならば96％のチャネルが4c＋1本のトラッ
「折返し」をされたネットである。この例の場合，配線 クで，99％のチャネルが4c＋2本のトラックで配線可 に要する時間は9．1secであった。使用した計算機は東 能であった。
芝のUX−300，言語はCである。 本手法は， strの計算，初期トラックの本数，トラッ クの追加の方法等に多くのパラメータが含まれ，これら
6・あとがき の変更が結果にかなり景多響を与える．コラム数、5。，端
縦横の配線に異なる層を用いる2層チャネル配線問題 子密度100％の1000個のチャネルに対して，パラメータ に対して，新しい垂直型チャネル配線アルゴリズムを提 を変更して3通りの配線を行った結果，997個のチャネ 案した。このアルゴリズムは各コラムにおいて，必要に ルが4ε＋2本のトラックで配線可能であった。一般に 応じて幹線分割およびトラックの追加を行う。 本手法においては，パラメータを変更して複数通りの配 本手法を使用することにより，制約条件が厳しく，端 線を行えば，単一の場合と比較してかなり良い結果にな 子密度の非常に大きいチャネルに対しても，チャネル密 る。最適なパラメータおよびパラメータの組合わせは対 度に近い本数のトラックで配線できることを示した。例 象とするチャネルに大きく依存する。パラメータの決定
えば，コラム数150のチャネルの場合，端子密度が80％ 等今後の課題である。
ならば99％のチャネルが4c＋1本のトラックで，端子
図一8 チャネル配線の例
7）河本達也： 区間の概念による諸配線方式の統二的考察 ，
参考文、献 信学技法CAS 80−127（1981）。
1）浅野，北橋，田中，堀野，天野： ビルディングブロック 8）Lee， C Y．： An algorithm for path connections and ap 方式LSIの配線の実現可能性について〉信学技法・CAS plications ・IRE Trans・， vol・・EC−10，no．3，PP．346−365
78−33 （1978）o （1961）．
2）Deutch， D． N．： Aedogleg channel router ，Proc．13 9）Mikami， K． and Tabuchi， K．： Acomputer program for th Design Automation Conference， pp．425−433（1976）． optimal routing of printed circuit conductors ，Pproc． IFIP 3）H・・him・t・・A・・nd St…n・・J・・ AWi・e・・uti・g by・pti− C・・g・ess， PP．1475−1478（1968）．
mizing channe｝assignment within large apertures ，Proc． 10）永松正博：．ミ垂直型チャネル配線アルゴリズムとチャネル 8th Design Autolhation Workshop， pp．155−169（1971）． 配線に要するトラック数について．，電子通信学会論文誌投 4）Hlghtower， D． W．： Asolution to line・roUting problems 稿中。
on the continuous plane ，proc．6 th Design Automation 11）Rivest， R． L． and Fiduccia， C． M．： A曾greedy channel W・・k・h・p・PP・1−24（1969）・ …t・・ ，P…．19 th D・・輌9・A・t・m・ti・・C・nf・・ence， PP．
5） Johnson， D．S．： The NP−completeness column：An 418−424（1982）．
ongoing guide ，J． Algorithms， Vo1． 3，No．4，pp． 12） Yoshimura， T． and Kuh， E．： Efficient algorithms for 381−395（1982）・ ・h・nn・1・・uti・g ，IEEE t・an・． C・mp・t・・ Aid・d D。、ig。。f 6）梶谷，石井，下山，金田： 2セル列2層最小間隔配線ア Integrated Circuits and Systems， Vo1． CAD．1，No．1，pp．
ルゴリズム ，信学技法CAS 79−142（1980）。 ． 25−35（1982）．
