JPH0429356A - チャネル配線方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 産業上の利用分野 本発明はＶＬＳＩのレイアウト設計において、配線領域
（チャネル）内配線を行なう方法に関するものであも 従来技術 従来の配線方法としては（１）配線トラック数を最小化
することを目的とした方法　（２）チャネル高を最小化
することを目的とした方法があっ九 （１）の方法の代表的なものとして、　「レフトエラ　
ジ法」　　（７°ロシーリンク′　第　８　回　デ゛す
゛イン　オートメーシミンワークシ菖）７′″　Ｐｒｏ
ｃ、　　８ｔｈ　　Ｄｅｓｉｇｎ　　Ａｕｔｏｍａｔｉ
ｏｎ　　Ｗｏｒｋｓｈｏｐ、　ｐｐ、１５５−１６９．
　１９７１．）、　「ドッグレッグ法」　（７°ロシー
リンク’ｉ１３　　回　デ゛す′イン　オートメーショ
ン　コンファレンス　Ｐｒｏｃ、　　１３ｔｈ　　Ｄｅ
ｓｉｇｎ　　Ａｕｔｏｍａｔｉｏｎ　　Ｃｏｎｆ、、　
　ｐｐ、４２５−４３３、１９７６）、　「吉相・クラ
の方法」　（アイ・什・什・什　トランサゝクシ１ン　
コンピュータ　エイテゝ７ビ　テ″′軒イン　ＩＥＥＥ
　　Ｔｒａｎｓ、　Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ　　
Ｄｅｓｉｇｎ、　　ｖｏｌ、ＣＡＤ−１，ｐｐ、２５−
３５、　１９８２．）、　　　「グリ　−ディ　法」　
　（７°ロシーリンク゛　第　１９　回　テゝす′イン
　オートメーション　コンファレンス　Ｐｒｏｃ、　１
’９ｔｈ　　Ｄｅｓｉｇｎ　Ａｕｔｏｍａｔｉｏｎ　Ｃ
ｏｎｆ、、　ｐｐ、４１８−４２４．１９８２）、　「
階層的配線方法」　　（７°ロシーリンク゛　第２０回
　テ゛す゛イン　オートメーション　コンファレンス　
Ｐｒｏｃ、　２０ｔｈ　　Ｄｅｓｉｇｎ　　Ａｕｔｏｍ
ａｔｘｏｎＣｏｎｆ、、　　ｐｐ、５９１−５９７．　
１９８３）、　　　ｒ　ＹＡＣＲ２Ｊ　　　（７°ロシ
ーリンク′　オフゝ　ザ　アイ　・　イー・　イー・　
イー　インターナシヨナル　コン７アレンスオン　コン
ピュータ　エイテ９フド　デゝす′イン　Ｐｒｏｃ、　
　ｏｆ　　ｔｈｅ　　ＩＥＥＥＩｎｔｅｒｎａｔｉｏｎ
ａｌ　　Ｃｏｎｆｅｒｅｎｃｅ　　ｏｎ　　Ｃｏｍｐｕ
ｔｅｒ−Ａｉｄｅｄ　　Ｄｅｓｉｇｎ、　ＩＣＣＡＤ−
８４，ｐｐ、？２−７５．　１９８４）などがある。

これらいずれの方法Ｌ　配線幅は全て同じであるものと
して配線を行っており、配線幅の考慮はなされていな（
−まｆ、　　ＹＡＣＲ２を除いて設計規準の考慮もなさ
れていないた数　配線間隔はコンタクトが横に並んでい
ても設計規準が満たされるだけ空けられも　従って、チ
ャネル高を最小にすることは配線トラック数の最小化と
なる。

（２）の方法の代表的なものとして、　「非格子型配線
幅可変配線手法」　（プロシーリンク゛　オフ゛　イン
ターナハナル　コンファレンス　オン　コンピュータ　
エイデゝフド　テ９す゛イン　Ｐｒｏｃ、　。

ｆ　　Ｉｎｔｅｒｎａｔｉｏｎａｌ　　Ｃｏｎｆｅｒｅ
ｎｃｅ　　ｏｎ　　Ｃｏｍｐｕｔｅｒ−ＡｉｄｅｄＤｅ
ｓｉｇｎ、　ｐｐ、３０４−３０６．　１９８５）があ
る。この方法は配線幅を考慮していも　また　設計規準
も考慮しているたべ　配線間隔は設計規準の最小間隔で
あ也　従って一般的に（上　（１）の方法よりチャネル
高の点では優れた解を得ることができも発明が解決しよ
うとする課題 従来方法（１）で（友　配線幅一定といった制約のもと
て配線を行っているためへ　配線幅の種類が複数存在す
るときチャネル高の点で最適化が行えな（＼　また上記
で述べたようへ　配線間隔の考慮を行っていないた敢　
余分な空間を作るといった問題点を有していも 従来方法（２）でｉ；Ｌ（１）がもつ問題点は存在しな
し兎　しかし　この配線方法はｘＹテクニ・ツクを用い
て行っている。ここで２層配線におけるＸＹテクニック
とは　配線の水平方向線分を第１層（または第２層）、
垂直方向線分を第２層（または第１層）を用いて配線を
行なうテクニックである。

従って、配線の水平線分が垂直線分と同じ配線層を用い
て配線を行うことができな匹　まＬ　その逆も同様であ
ム　このことは　２層を有効に用いた配線を行なうより
高密度な配線結果を得るという機会を失うといった問題
点を有している。

本発明（よ　以上のような問題点に鑑べ　配線幅や配線
間隔の考慮ができ、さらにＸＹテクニックを無視した配
線を行なうことにより、チャネル高の低い高密度な配線
結果を得ることのできるチャネル配線方法を提供するこ
とを目的とする。

課題を解決するための手段 本発明は　２行の端子列に挟まれた帯状の配線領域にお
いて、前記各端子に与えられた結線要求を満足するよう
に前記配線領域内で配線を行なう方法であって、配線が
完了するために必要な水平線分を発生させる水平線分発
生手段と、前記配線領域内に前記端子列に平行な仮想線
分を前記配線領域内に含まれる配線層ごとに１本あるい
は複数本発生させ、前記仮想線分上に前記配線の水平線
分を割り当てる水平線分割当手段と、前記配線の水平線
分に対して前記配線領域における前記配線層ごとの設計
規準を満たして前記配線領域の高さができるだけ低くな
るような前記水平線分の折り曲げを行なう水平線分析り
曲げ手段と、配線の垂直線分を発生させる垂直線分発生
手段とを備えたチャネル配線方法であａ また　本発明は上記水平線分割当手段として、前記端子
の位置関係により生じる前記水平線分の割当順番を調べ
る水平線分割当順番決定手段と、ある一つの前記仮想線
分上に割り当てることのできる前記水平線分の候補を選
択する水平線分候補選択手段と、前記端子の位置関係に
より生じる前記水平線分の上下関係において前記上下関
係をもつ前記水平線分の集合を求め、　前記集合内に含
まれる前記水平線分の線分幅と設計規準により前記集合
内に含まれる前記水平線分を評価する最長路長計算手段
と、配線を完了するために必要な前記配線領域の高さを
あらかじめ見積るチャネル高見積り手段と、前記チャネ
ル高見積り手段によって得られたチャネル高のある一定
以上の高さの位置に垂直線分を設けこの垂直線分を列挙
する配線密度位置列挙手段と、前記水平線分候補が前記
垂直線分を被覆する個数を計算する配線密度個数計算手
段と、前記水平線分をチャネルの上側に割り当てる度合
を評価する上辺引力計算手段と、前記各水平線分の長さ
を計算する水平線分長計算手段と、前記最長路長計算手
段と前記配線密度個数計算手段と前記上辺引力計算手段
及び前記水平線分長計算手段のうち少なくとも１つの手
段を用いて得られた結果を基にして前記仮想線分上に前
記水平線分候補から水平線分を選択する水平線分選択手
段とを備え　前記水平線分がすべて割り当てられるまで
前記各手段を繰り返し行なうことを特徴とすム 作用 本発明によれば　配線幅や配線間隔を考慮ＬｘＹテクニ
ックを無視した配線を行なうた数　チャネル高の低い高
密度な配線結果を得ることができる。

実施例 以下、本発明の一実施例を添付図面に基づいて説明す４
　本発明の処理の流れを、第１図のフロー＠　第２図の
配線処理の分解図及び第３図の水平線分割当手段の分解
図を用いて説明する。

第１図に示すように本発明のフローは大きく分けて、水
平線分発生手段１３、水平線分割当手段１、水平線分析
り曲げ手段１１及び垂直線分発生手段１２から構成され
ていも　また水平線分割当手段１（上　水平線分割当順
番決定手段２、水平線分候補選択手段３、最長路長計算
手段４、チャネル高見積り手段５、配線密度位置列挙手
段６、配線密度個数計算手段７、上辺引力計算手段８、
水平線分長計算手段９、水平線分選択手段ｌＯ（１０ａ
、１０ｂ）から構成されている。

初めに　本発明の処理方法の概略を第１図を用いて説明
する。まず水平線分発生手段１３では配線が完了するた
めに必要な水平線分をすべて列挙するものである。発生
される水平線分は公知例「ドッグレッグ法」で示される
ものと同様な２端子ネツトによって構成される水平線分
であム　ここで、列挙された水平線分の集合を水平線分
集合Ｈとする。次に　水平線分割当手段ｌでは端子列に
平行な仮想線分をチャネル内に配線層ごとに発生させ、
その仮想線分上に配線の水平線分を割り当てる。もし水
平線分が仮想線分上に割り当てることができたな叡　水
平線分集合Ｈから除かれもこの操作はすべての端子が結
線要求どおりに配線できるまですなわ板　水平線分集合
Ｈが空になるまで行なう。例えば　第２図（ａ）がその
−例である。第２図において、　２０１は幅４のネット
ｌの端子、　２０２は幅２のネット２の端子、　２０３
は幅３のネット３の端子、２０４はチャネルの上辺２０
５はチャネルの下辺　２０６は幅４の第１層にあるネッ
トｌの水平線分、　２０７は幅２の第２層にあるネット
２の水平線分、　２０８は１幅３の第１層にあるネット
３の水平線分、　２０９は第１トラツクの第１層仮想線
分、　２１０は第２トラツクの第２層仮想線分、　２１
１は第３トラツクの第１層仮想線分であも 次の水平線分析り曲げ手段１１によって、設計規準を満
たし　か２　できるだけ最終的なチャネル高を最小にす
るために　割り当てられた水平線分を同層による折り曲
げを行なう。例え１Ｌ１２図（ａ）は第２図（ｂ）とな
４　ここで第２図（ｂ）において、　２１２は水平線分
２０７を折り曲げしたときの線分を示す。

最後の垂直線分発生手段１２によって、すべての端子に
対して結線要求どおりに同電位に接続するため＆ミ　層
ごとに　端子と端子、端子と水平線分、水平線分と水平
線分との間に配線の垂直線分を発生させも　例えば　第
２図（Ｃ）が第２図（ｂ）に対する最終結果であム　こ
こで第２図（Ｃ）において、　２１３はコンタクト２１
９と端子２０１をつなぐ第２層の垂直線分、　２１４は
コンタクト２２０と端子２０１をつなぐ第２層の垂直線
分、　２１５は線分２１２の左端と端子２０２をつなぐ
第２層の垂直線分、　２１６は線分２１２の右端と端子
２０２をつなぐ第２層の垂直線分、　２１７はコンタク
ト２２１と端子２０３をつなぐ第２層の垂直線分、　２
１８はコンタクト２２２と端子２０３をつなぐ第２層の
垂直線分、　２１９は線分２０６と垂直線分２１３をつ
なぐコンタクト、　２２０は線分２０６と垂直線分２１
４をつなぐコンタクト、２２１は線分２０８と垂直線分
２１７をつなぐコンタクト、　２２２は線分２０８と垂
直線分２１８をつなぐコンタクトである。端子２０１〜
２０３はすべて第２層に割り当てることにす４次に　水
平線分割当手段１について説明する。

この手段１はチャネルの上辺から下辺へ順に仮想線分を
発生させ、その仮想線分上に配線の水平線分を割り当て
ていくのものである。ここで、仮想線分の発生させる順
番はチャネルの上辺からに限らず、任意に発生させるこ
ともできる。例えばチャネルの下辺から上辺へ　または
チャネルの上辺と下辺を交互に発生させてもよい。以下
では仮想線分をチャネルの上辺から下辺の順に発生させ
るときを考えも　手段ｌに含まれる手段２から手段ＩＯ
の１回のループによって発生する仮想線分の種類ζ１　
１）ラックＸ層数通りである。ここで、　トラックとは
垂直方向位置で区別した仮想線分のことであａ　また　
本実施例では層数を２とすａ　第１図において水平線分
選択手段１０が２つ（１０ａと１０ｂ）あるの（友　層
数が２のときのフロー例であるからであａ　従って、配
線問題が扱う層数だけ水平線分選択手段１０が必要とな
ム第３図によって、第１図における水平線分割当手段ｌ
のループについて説明する。第３図において、　３０１
は仮想線分３０２上に割り当てられた水平線分、３０２
は第１層の仮想線分、　３０３は第２層の仮想線分、　
３０４は仮想線分３０６上に割り当てられた水平線分、
　３０５は第１層の仮想線分、　３０６は第２層の仮想
線分、　３０７は仮想線分３０８上に割り当てられた水
平線分、　３０８は第１層の仮想線分、　３０９は第２
層の仮想線分であａ　水平線分発生手段１３で発生する
水平線分集合Ｈの要素（よ　水平線分３０１．３０４と
３０７であ４＋１回目ループ（手段２から手段１０まで
）によって第３図（ａ）に示すように仮想線分３０２を
発生し　仮想線分３０２上に水平線分３０１を割り当て
たとする。従って水車線分３０１は水平線分集合Ｈから
削除される。ここで水平線分３０１は仮想線分３０３上
に割り当てることができないことに注意されたｌ、％　
　なぜなら、もし線分３０１を仮想線分３０３上に割り
当てたとすると、下層線分３０２上に他のいかなる配線
の水平線分を割り当てたとしても端子２０１〜２０３の
全てが第２層に割り当てられるた敦　水平線分３０１と
電気的ショートを起こすからである。

まだ水平線分集合Ｈが空になっていないので、　２回目
のループが実行される。このループによって第３図（ｂ
）に示すように仮想線分３０６を発生し仮想線分３０６
上に水平線分３０４を割り当てたとすム　従って水平線
分３０４は水平線分集合Ｈから削除される。ここで線分
３０４は仮想線分３０５または３０６上いずれでも割り
当てることができることに注意された１、％　　ただし
　本発明は２層オーバーラツプ配線を行うので、できる
限り第２層の仮想水平線分に割り当てることが望ましく
−まだ水平線分集合Ｈが空になっていないので、　３回
目のループが実行されも　このループによって第３図（
Ｃ）に示すように仮想線分３０８を発生し仮想線分３０
８上に水平線分３０７を割り当てたとすム　従って水平
線分３０７は水平線分集合Ｈから削除されも　このとき
、水平線分集合Ｈが空になったので、水平線分割当手段
１は終了す４次に　さらに詳細に水平線分割当手段１を
説明するために　手段２から手段１０を処理の順番に説
明すも 水平線分割当順番決定手段２を、第４図を用いて説明す
ム　４０１はネットｌの幅４の水平線分、４０２はネッ
ト２の幅２の水平線分、　４０３はネット３の幅３の水
平線分、　４０４は拡張上下制約グラフ、４０５はグラ
フ４０４におけるソー人４０６はグラフ４０４における
シン久　４０７は水平線分４０１を表すグラフ上の項九
　４０８は水平線分４０２を表すグラフ上の項八　４０
９は水平線分４０３を表すグラフ上の頂点であも　配線
の水平線分４０１〜４０３の垂直配置位置は端子２０１
．２０２と２０３の位置関係によって限定される場合が
ある。このことを表すものとして上下制約グラフがあａ
　これはチャネル配線問題では一般によく用いられるも
のであり、また公知例「再帰的配線方法」（７°ロシ一
リンク゛第２５回テ゛す１イン　オートメーシ箇ン　コ
ンファレンス　Ｐｒｏｃ、　　２５ｔｈ　　Ｄｅｓｉｇ
ｎ　　Ａｕｔｏｍａｔｉｏｎ　Ｃｏｎｆ、、　ｐｐ、１
７８−１８２．１９８８）ではその上下制約グラフに対
して一部情報を追加した拡張上下制約グラフについて示
されていも　本発明ではこの拡張上下制約グラフを用い
も　拡張上下制約グラフ４０４において、各頂点４０７
から４０９は各水平線分を表し　有向枝は枝の両端にあ
る頂点の上下関係を表す。例えば　頂点４０７→頂点４
゜８の場合、頂点４０７がもつ水平線分は頂点４０８が
もつ水平線分より先（上）に割り当、てなければならな
いことを表す。さらに拡張上下制約グラフ４０４におい
て、頂点４０５はそのグラフにおけるソー人　頂点４０
６はシンクを表す。水平線分割当順番決定手段２によっ
てこのグラフ４０４を作成する。

次の水平線分候補選択手段３で（よ　拡張上下制約グラ
フ４０４を用いてチャネルの上辺に最も近いトラックに
割り当てることのできる水平線分の候補を求める。その
方法として、グラフ４０４において頂点４０５につなが
る頂点がもつ水平線分を水平線分集合Ｈの中からすべて
列挙すａ　ここで、列挙された水平線分の集合を水平線
分集合Ｈ′とすも　同時へ　集合Ｈ゛の各要素には４つ
の属性（Ｗｌ、Ｗ２．Ｗ３．Ｗ４）がある。この属性１
友　水平線分選択手段１０のところで線分の選択基準と
して用いるものであり、それらは以下の手段４から手段
９によって求められも 最長路長計算手段４でＧム　　拡張上下制約グラフ４０
４を用いて、集合Ｈ′に含まれる各水平線分りに対して
割当優先度を計算する。計算方法は式（１）とし　それ
を属性Ｗ１とする。

Ｗｌ−Σ（水平線分りの頂点を含むソースがらシンクま
での最長路上にある頂点がもつ水平線分幅）＋スペーシ
ングデザインルール×（水平線分りの頂点を含むソース
からシンクまでの最長路上にある頂点数＋１）　・・・
　（１） 例えば　第４図において線分４０１の属性Ｗ　１　＋１
Ｗ１＝　（４＋２＋３）＋（２ｘ　４）＝　１７となも
　ここで、　スペーシングデザインルール（以下、単に
スペーシングと呼ぶ）とは線分間の設計規準間隔であり
、ここでは２としム チャネル高見積り手段５を、第５図を用いて説明す、％
　　５０１は水平線分４０１の左端に接する垂直線分、
　５０２は水平線分４０３の左端に接する垂直線分、　
５０３は水平線分４０２の左端に接する垂直線分、５０
４は水平線分４０１の右端に接する垂直線分、　５０５
は水平線分４０２の右端に接する垂直線分、　５０６は
水平線分４０３の右端に接する垂直線分である。まず、
配線密度と呼ぶ概念を導入する。配線密度とは　チャネ
ルのある位置に対して垂直線分を引き、その垂直線分を
通過する配線の水平線分の配線幅とその間のスぺ−シン
クの和とす４　ただし　チャネルの上辺と水平線分の阻
　及びチャネルの下辺と水平線分の間も考慮することに
すム　例えば　スペーシングを２として、第５図の各チ
ャネル密度を計算すると、垂直線分５０１におけるチャ
ネル密度Ｄ１は２＋４＋２４．　垂直線分５０２におけ
るチャネル密度Ｄ２は２＋４＋２＋３＋２−１３．　　
垂直線分５０３におけるチャ調ル密度Ｄ３は２＋４＋２
＋２＋２＋３＋２−１７、以下垂直線分５（４における
チャネル密度Ｄ　４−１７、垂直線分５０５におけるチ
ャネル密度Ｄ５−１１、垂直線分５０６におけるチャネ
ル密度Ｄ６−７とな４　もし配線方法力ＸＹテクニック
を用いているならば　各位置におけるチャネル密度は配
線を完了するための必要な最低チャネル高を示すことに
なるか叙　チャネル密度の最大値はすべての配線が完了
するために必要なチャネル高を表すことになム　手段５
では各端子２０１、２０２と２０３の位置に垂直線分を
発生させ、その位置の配線密度を計算し　位置とその位
置における配線密度を対とした集合である配線密度集合
Ｃを求めも さら番ミ　配線密度位置列挙手段６で１よ　配線密度集
合Ｃの中からある一定以上の配線密度をもつものだけ列
挙した限定配線密度集合Ｃ′を求める。

この手段６は後の手段７の計算で用いるものであム　後
述の手段７で明らかになる力交　一定量上の配線密度を
もつものを採用するのは　もし配線密度のある値だけを
採用すると、手段７の最適化が損なわれる可能性がある
からである。

次に　配線密度個数計算手段７を説明する。この手段（
よ　各水平線分が限定配線密度集合Ｃ°に含まれる要素
をどのくらい被覆している力＼　を評価するものである
。被覆された個数が多いほど、また配線密度の高いとこ
ろを被覆している水平線分は優先的にトラックに割当を
しなければならなｔ、Ｘ。

本発明で（戴　それを評価するためＣ，：、被覆された
個数が多いほど、さらに配線密度の大きいものを被覆す
ればするほど評価が高くなる評価式を式（２）を用いる
。ここで、評価された各位は水平線分集合Ｈ°の各線分
りの属性Ｗ２とすへＷ２＝Σ（ｋ　ｉｘ水平線分区間に
ある配線密度Ｄｉを被覆する個数）　・・・　（２） ここで、ｋｉは任意の定数でに１≧に２≧・・・≧ｋｉ
の関係をも板　またＤｉは限定配線密度集合Ｃ′に含ま
れる配線密度でＤ１≧Ｄ２≧・・・≧Ｄｉの関係をもつ
例として、第５図において水平線分４０１の属性Ｗ２を
計算すム　まず限定配線密度集合Ｃ°に含まれる配線密
度が１７と１３であったすム　線分４０１は配線密度＝
１３を１−１．配線密度＝１７を２つ被覆しティるノテ
、Ｗ２＝　（１０ｘ　２）＋（５ｘ　１）＝　２５とな
ム　ここでｋｌ＝ＩＱ、に２＝５としに上辺引力計算手
段８を説明すも　この手段８はその水平線分が上辺と下
辺に向がってどのくらい強さで引っ張られているかを評
価するものである。

例えば　ある水平線分Ｎが上辺に４つと、下辺に２つと
接続する必要があるとする。その線分Ｎはできるだけチ
ャネルの上辺に割当てることができたならば　総配線長
は短くなることは容易にゎがる。本実施例はチャネルの
上辺から下辺に向がって水平線分を割当てることにして
いるので、手段８は上辺への引力を計算すム　従って、
もしチャネルの上辺から下辺に向かって水平線分を割当
てを行なうなら（歌　手段８は下辺への引力を計算しな
ければならな１．Ｘｏ　　水平線分集合Ｈ″に含まれる
各水平線分りに対して、式（３）により上辺への引力を
計算する。また　この値を線分りの属性Ｗ３とすム Ｗ３＝線分りがもつ端子のうちチャネル上辺にある端子
数／線分りがもつ端子数　・・・　（３）次に　水平線
分長計算手段９を説明する。水平線分の長いものや幅の
広いものを優先的に割り当てると後述の水平線分選択手
段１０で２層オーバーラツプ配線が容易となる。そこで
、長いもの、幅の広いものを優先的に割り当てる評価と
して式（４）を計算する。それを水平線分集合Ｈ゛に含
まれるすべての水平線分りの属性Ｗ４とす４Ｗ４＝ｋｉ
ｘ（水平線分の左端から右端の長さ）×（水平線分の輻
）　・・・　（４） ここで、　ｋｉは任意定改 水平線分選択手段１０を、第６図を用いて説明する。　
６０１はネット１の端−Ｆ、６０２はネット２の端子、
　６０３はネット３の端子、　６０４はネット４の端子
、６０５は幅４の配線の水平線分、６０６は幅２の配線
の水平線分、　６０７は幅４の配線の水平線分、　６０
８は幅３の配線の水平線分、６０９は水平線分６０５を
区間表現した線分、　６１Ｏは水平線分６０６を区間表
現した線分、　６１１は水平線分６０７を区間表現した
線分、　６１２は水平線分６０８を区間表現した線分、
　６１３は第１層の仮想線分、　６１４は第２層の仮想
線分であも　手段１０は手段１０ａと手段１０ｂとに分
かれる力（異なるところは水平線分を仮想線分に割り付
ける基準だけである。これは後で述べる。

まず、水平線分集合Ｈ°に含まれるすべての水平線分り
を区間表現する。例えば　水平線分６０５は区間線分６
０９に　水平線分６０６は区間線分６１０に　水平線分
６０７は区間線分６１１、水平線分６０８は区間線分６
１２になる。次へ　各水平線分りに対する各区間線分Ｓ
に重みＷを与える。Ｗは式（５）によって計算される。

Ｗ　＝　ｋｌ　Ｘ　Ｗｌ十に２Ｘ　Ｗ２＋に３ｘ　Ｗ３
＋に４ｘ　Ｗ４　　　・　・　　　　（５）ここで、ｋ
ｌ、に２．ｋｌ　　ｋ４はそれぞれ任意の定説　Ｗは値
が大きいほどその線分の選択優先度が高くなム　ＷはＷ
ｌからＷ４の和であるので、ＷｌからＷ４の優先の度合
をに１からに４によって自由に制御できも　一般に（よ
　チャネルの高さを最小化するためにに１とに２かに３
とに４より高い値が設定されも　次へ　選択すべき（割
当すべき）水平線分の組を求めるために　グラフ理論に
おける「最大独立集合」の概念を用いも　最大独立集合
と（ｉ　　お互いの区間線分に重なりがなく、かつそれ
ら区間線分がもつ重みの和が最大である区間線分の集合
のことをいう。線分の選択方法として、先に求めた重み
Ｗ付き区間線分Ｓに対して最大独立集合を求数　その集
合に含まれる線分すべてを今割当すべき線分とすａ　−
例を第６図によって説明すも前提として、区間線分６０
９の重みＷを１２、区間線分６１０の重みＷを６、区間
線分６１１の重みＷを８、区間線分６１２の重みＷを６
とすａま咀　線分６０９と６１０、及び線分６１０と６
１１はある区間で重なりが生じているので、それぞれは
１つの集合にできなしも　線分６０９と６１１、及び線
分６１０と６１１も同様であａ　しかし線分６０９と６
１２は重なりがないので、それらは１つの集合（６０９
，６１２）にできる。さらにその集合の重みを１２＋６
＝１８となム　同様にして、線分６１１と６１２は重な
′りがないので、それらは１つの集合（６１１，６１２
）にできる。またその集合の重みは８＋６＝１４となる
。線分６１０はどの線分とも重なりをもつので、線分６
１０それ自身が集合（６１０）となり、その集合の重み
は８であム　ここで今、集合（６１０）、　（６０９，
６１２）と（６１１，６１２）が存在する力丈　重みは
それぞれ８、１８、１４なのでその重みの最大値１８を
もつ集合、すなわち集合（６０９，６１２）が最大独立
集合となａ　よって選択される線分は線分６０９と線分
６１２となる。最大独立集合を解く　算法（よ　　公知
例　（シ′ヤーナル　オフ゛　サ′　アソシェーシ■ン
　フォア　コンビスープインク′　マシーナリ　Ｊｏｕ
ｒｎａｌ　　ｏｆ　　ｔｈｅ　　Ａｓ５ｏｃｉａｔ１ｏ
ｎ　　ｆｏｒ　　Ｃｏｍｐｕｔｉｎｇ　　Ｍａｃｈｉｎ
ｅｒｙ、　　ｖｏｌ、３３．　　ｎｏ、２．　　ｐｐ、
２９０−３１２．１９８６）に示されている。本発明は
その算法を用いも 次に、　　仮想線分６１３，６１４を発生させ、求めた
区間線分６０９の水平線分６０５と区間線分６１２の水
平線分６０８を仮想線分６１３叉は６１４上に割り当て
る。それを第６図を用いて説明すも　水平線分６０９の
区間内に対して、チャネルの上辺にある同電位でない端
子を列挙すも　もしその端子がなければ　水平線分６０
９を６０９がもつ端子と層と同じ層の仮想線分上に割り
当てる。

第６図の場合、端子６０２，６０３が存在する。従って
上の場合に当たらな（′１ｏ　　このとき、端子が存在
する層と違う層の仮想線分上に割り当てる。今の場合、
端子６０２，６０３があるが仮　線分６゜９を端子と違
う層（端子は第２層に存在）、すなわち第１層目の仮想
線分６１３上に割り当てることになる。以上の操作を線
分６０８についても同様に行なう。そして水平線分集合
Ｈ°の中から水平線分６０５と６０８を削除すａ　手段
１ｏのへこれまでの操作は水平線分選択手段１０ａであ
る。

改番ミ　　水平線分選択手段１０ｂを説明すム　この手
段１０ｂは手段１０ａとほとんど同じである。

しかし　仮想線分に水平線分を割り当てるところだけが
異なム　まず手段１０ａと同様にして、水平線分集合Ｈ
′に含まれる線分りに対して選択すべき（割当すべき）
線分を最大独立集合の概念を用いて求めも　第６図で１
よ　すでに線分６０９と６１２が割り当られているので
、集合（６１０）と（６１１）Ｌか存在しなし℃　従っ
て最大独立集合は集合（６１１）であム　次へ　区間線
分６１１の水平線分６０７を仮想線分に割り当ても　こ
のときすでに仮想線分６１３に水平線分６０５と６０８
が割り当てられているので、水平線分６０７を第１層目
の仮想線分６１３に割り当てることはできな（〜　従っ
て、ここでは第２層目の仮想線分６１４に水平線分が割
り当てることができるかを調べるだけでよし〜　第６図
でＣ！　　水平線分６０７の区間内に対してチャネルの
上辺に端子が存在しないので、仮想線分６１２上に水平
線分６０７を割り当ても　そして水平線分集合Ｈ°の中
から水平線分６０７を削除すム 以上の手段ｌＯにより、２層のオーバーラツプ配線が可
能となることがわかる。水平線分選択手段１０ａ、１０
ｂによって、水平線分集合Ｈ′から除外された水平線分
を水平線分集合Ｈから取り除いてできた水平線分集合Ｈ
”　について水平線分割当手段１を適用すも 水平線分析り曲げ手段１１を、第７図を用いて説明すも
　７０１は幅２の１層のみの配ｍ、７０２は配線７０１
を折り曲げした後の配線であ４手段１１は水平線分割当
手段ｌによってできた配線結果に対して垂直方向のチャ
ネルの圧縮を行うものであａ　このとき、圧縮されてで
きたチャネル内の配線は設計規準が満たされてなければ
ならなｌ、％　　例えば第７図（ａ）が水平線分割当手
段１によって得られた配線結果であったとすると、垂直
方向のチャネルの圧縮により、第７図（ｂ）の結果が得
られる。この手段１１は一般にチャネルコンパクション
と呼ばれる。ここで用いる算法は　例えば公知例「ナツ
トクラッカー法」（７°ロシーりンク゛第２　４回　　
テゝす′イン　オートメーシ這ン　コンファレンス　Ｐ
ｒｏｃ、　　２４．ｔｈＤｅｓｉｇｎ　Ａｕｔｏｍａｔ
ｉｏｎ　Ｃｏｎｆ、、　ｐｐ、２９８−３０４．１９８
７）、「チャネルスペーサ」　（信学論（Ａ）、　Ｊ７
２−Ａ、　Ｎｏ、２ｐｐ、３４９−３５８．１９８９）
などいずれの方法を用いてもよ（を 最後に　垂直線分発生手段１２によって、すべての端子
に対して結線要求どおりに同電位に接続するため凶　層
ごとに　端子と端子、端子と水平線分、水平線分と水平
線分との間に配線の垂直線分を発生させも 第８図（よ　ある配線問題を本発明に適用した配線結果
を示すものであム　第８図において、　１０１は端子、
　１０２はコンタクト、　１０３は第１層配ＩＩＬ　１
０４は第２層配電　１０５はチャネルの上ａ　１０６は
チャネルの下辺であム　第９図（よ第８図と同じ配線問
題を「非格子型配線幅可変配線手法」に適用した配線結
果を示すものであム本発明を用いれ１′Ｌ　第８図に示
すようＥ、　　ＸＹテクニックを無視したより低いチャ
ネル高の高密度な配線結果を得ることができも　この結
果を第９図に示すような従来例「非格子型配線幅可変配
線手法」　（７”ロシーリンク′　オフゝ　インターナ
ショナル　コンファレンス　オン　コンピュータ　エイ
テ′フビ　デゝす１イン　Ｐｒｏｃ、　　ｏｆ　　Ｉｎ
ｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ　　ｏｎ
　　Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ　　Ｄｅｓｉｇｎ、
　　ｐｐ、３０４−３０６、１９８５）によって得られ
た配線結果と比較すると、明らかに配線層の使用に差が
見られ　結果的にチャネル高に影響が現れている。

発明の詳細 な説明したように　本発明によれば　配線幅や配線間隔
を考慮ＬＸＹテクニックを無視した配線を行なうたへ　
チャネル高の低い高密度な配線結果を得ることが可能で
あり、その効果は顕著であも

【図面の簡単な説明】

第１図は本発明の処理のフロー諷　第２図の配線処理の
分解医　第３図は水平線分割当手段の分解医　第４図は
水平線分割当順番決定手段の説明医第５図はチャネル高
見積り手段の説明図　第６図は水平線分選択手段の説明
＠　第７図は水平線分析り曲げ手段の説明図　第８図は
本発明によるー配線結果＠　第９図は従来例「非格子型
配線幅可変配線手法」による配線結果図であも １・・・水平線分割当手段、　２・・・水平線分割当順
番決定半没　３・・・水平線分候補選択平反　４・・・
最長路長計算半没　５・・・チャネル高見積り手段、　
６・・・配線密度位置列挙半没　７・・・配線密度個数
計算手段、　８・・・上辺引力計算平反　９・・・水平
線分長計算半没　１０・・・水平線分選折半ＪＲ，１１
・・・水平線分析り曲げ半没　１２・・・垂直線分発生
半没　１３・・・水平線分発生手［１１０１・・・端子
、　１０２・・・コンタクト、　１０３・・・第１層配
＆ｌ　　１０４・・・第２層配線　１０５・・・チャネ
ルの上ａ　１０６・・・チャネルの下近 代理人の氏名　弁理士　粟野重孝　はか１名第 図 （ａ〕 （Ｃ） 路 図 Ｅ練＠ＩｔＤＬ　８ ！！ 第 図 Ｃ（Ｌ） （ｂ）

Claims (2)

【特許請求の範囲】
1. （１）２行の端子列に挟まれた帯状の配線領域において
   、前記各端子に与えられた結線要求を満足するように前
   記配線領域内で配線を行なう方法であって、配線が完了
   するために必要な水平線分を発生させる水平線分発生手
   段と、前記配線領域内に前記端子列に平行な仮想線分を
   前記配線領域内に含まれる配線層ごとに１本あるいは複
   数本発生させ、前記仮想線分上に前記配線の水平線分を
   割り当てる水平線分割当手段と、前記配線の水平線分に
   対して前記配線領域における前記配線層ごとの設計規準
   を満たして前記配線領域の高さができるだけ低くなるよ
   うな前記水平線分の折り曲げを行なう水平線分析り曲げ
   手段と、配線の垂直線分を発生させる垂直線分発生手段
   とを備えたチャネル配線方法。
2. （２）請求項１記載の水平線分割当手段として、前記端
   子の位置関係により生じる前記水平線分の割当順番を調
   べる水平線分割当順番決定手段と、ある一つの前記仮想
   線分上に割り当てることのできる前記水平線分の候補を
   選択する水平線分候補選択手段と、前記端子の位置関係
   により生じる前記水平線分の上下関係において前記上下
   関係をもつ前記水平線分の集合を求め、前記集合内に含
   まれる前記水平線分の線分幅と設計規準により前記集合
   内に含まれる前記水平線分を評価する最長路長計算手段
   と、配線を完了するために必要な前記配線領域の高さを
   あらかじめ見積るチャネル高見積り手段と、前記チャネ
   ル高見積り手段によって得られたチャネル高のある一定
   以上の高さの位置に垂直線分を設けこの垂直線分を列挙
   する配線密度位置列挙手段と、前記水平線分候補が前記
   垂直線分を被覆する個数を計算する配線密度個数計算手
   段と、前記水平線分をチャネルの上側に割り当てる度合
   を評価する上辺引力計算手段と、前記各水平線分の長さ
   を計算する水平線分長計算手段と、前記最長路長計算手
   段と前記配線密度個数計算手段と前記上辺引力計算手段
   及び前記水平線分長計算手段のうち少なくとも１つの手
   段を用いて得られた結果を基にして前記仮想線分上に前
   記水平線分候補から水平線分を選択する水平線分選択手
   段とを備え、前記水平線分がすべて割り当てられるまで
   前記各手段を繰り返し行なうことを特徴とするチャネル
   配線方法。