(57)【要約】【課題】簡単かつ最適な配線パターン処理をおこなうことにより、後工程での配線パターンの修正を防止し、ＬＳＩの歩留まりの向上を図ること。【解決手段】完全グラフは、配線パターンＷｉに対応するノードＮｉと、配線パターン間の影響度に対応するエッジｅijとから構成されている。異なるグループＧｍどうしの配線パターン間におけるクロストークの影響度Ｆijの総和Σが最小となるように、配線パターンの集合を複数のグループに分ける。完全グラフでは、エッジｅ12、ｅ13、ｅ23、ｅ45の影響度が高く、残余のエッジｅ14、ｅ15、ｅ24、ｅ25、ｅ34、ｅ35の影響度は、エッジｅ12、ｅ13、ｅ23、ｅ45の影響度に比べて低い値とされている。これにより、エッジによって互いに連結されているノードＮ１〜Ｎ３のグループと、ノードＮ４、Ｎ５のグループとに分割される。【選択図】        図５
2006031468.tif 000002
【特許請求の範囲】
【請求項１】
配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出する集合抽出手段と、
前記集合抽出手段によって抽出された配線パターンの集合から、前記各配線パターン間に生じるクロストークの影響度を取得する影響度取得手段と、
前記影響度取得手段によって取得された影響度に基づいて、前記配線パターンの集合を複数のグループに分けるグループ分け手段と、
前記グループ分け手段によって分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付ける割付手段と、
を備えることを特徴とする配線パターン作成装置。
【請求項２】
前記影響度取得手段は、
前記各配線パターン間の距離に基づいて、前記各配線パターン間に生じるクロストークの影響度を取得することを特徴とする請求項１に記載の配線パターン作成装置。
【請求項３】
配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出する集合抽出工程と、
前記集合抽出工程によって抽出された配線パターンの集合から、前記各配線パターン間に生じるクロストークの影響度を取得する影響度取得工程と、
前記影響度取得工程によって取得された影響度に基づいて、前記配線パターンの集合を複数のグループに分けるグループ分け工程と、
前記グループ分け工程によって分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付ける割付工程と、
を含んだことを特徴とする配線パターン作成方法。
【請求項４】
配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出させる集合抽出工程と、
前記集合抽出工程によって抽出された配線パターンの集合から、前記各配線パターン間に生じるクロストークの影響度を取得させる影響度取得工程と、
前記影響度取得工程によって取得された影響度に基づいて、前記配線パターンの集合を複数のグループに分けさせるグループ分け工程と、
前記グループ分け工程によって分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付けさせる割付工程と、
をコンピュータに実行させることを特徴とする配線パターン作成プログラム。
【請求項５】
請求項４に記載の配線パターン作成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、半導体装置の配線パターンを作成する配線パターン作成装置、配線パターン作成方法、配線パターン作成プログラムおよび記録媒体に関する。
【背景技術】
【０００２】
近年、ＬＳＩ設計において、配線処理の重要性が増々高まってきている。これは、回路
の大規模化によって、配線処理での所要時間が増大してきていることが理由に挙げられる。また最近特に注目される理由として、回路の微細化により配線がシグナルインテグリティに大きく影響を与えるようになってきている点がある。ノイズや遅延が回路に与える影響は配線パターンが確定しないと精度よく解析できないため、詳細配線が完了して初めて本格的な対策が可能となる。
【０００３】
このＬＳＩ設計では一般に、初期配線（概略配線）によって配線がどの領域を通過する
かを決定し、その後に、詳細な配線経路を確定する。この際、配線エラーを起こさないことが最も重要である。図１３は、従来の配線エラーを示す説明図である。
【０００４】
図１３において、たとえば、配線パターンａおよび配線パターンｂ、配線パターンｃおよび配線パターンｄのように、異なる配線パターンどうしの接触や、配線パターンｅのように配線禁止領域１３００との接触は、配線エラーとなるため、配線する際の配線エラー制約として処理をおこなう。
【０００５】
しかし、近年はプロセスの微細化が進み、歩留まりの向上、タイミング制約、クロストークノイズの軽減などさまざまな観点から配線を行う必要が生じてきた。クロストークとは、配線間に生じる容量のために、信号の波形、遅延が変動する現象である。配線が長距離を近接すると、配線間容量が大きくなり、クロストークによる影響からノイズ、遅延が大きくなる。
【０００６】
配線が長距離隣接した場合、当該配線間に寄生容量が発生し、配線を伝達する信号の遅延が大きくなる。また一方の配線を伝わる信号が変化した際には、容量を伝わって他方の配線の電圧も変動することにより、誤動作を引き起こす場合もある。
【０００７】
また、信号遷移のタイミングが近い配線どうしが隣接すると、信号波形が変化し、遅延の変動などの悪影響が大きくなる。このような影響は、一般に配線どうしの隣接長が長い場合、配線を駆動するセルの駆動力の差が大きい場合、信号遷移のタイミングが近い場合に大きくなる。
【０００８】
また、従来のトラックアサインメント手法は、チップを小領域に分割し、領域内の線分集合をトラックへ、マッチングによって割り当てる手法であり、詳細配線の前工程としての使用や、一部の配線のみへの適用など、いくつかの手法が提案されている（たとえば、下記非特許文献１を参照。）。
【０００９】
【非特許文献１】シャビア・バテリワラ（Shabbir Batterywala），ナレンドラ・シェノイ（Narendra Shenoy），ウィリアム・ニコルズ（William Nicholls），ハイ・シュー（Hai Zhou）著，“トラック  アサイメント：ア  デザイラブル  インターメディエイト  ステップ  ビットウィーン  グローバル  ルーティング  アンド  ディテイルド  ルーティング（Track Assignment: A Desirable Intermediate Step Between Global Routing and Detailed Routing）”，インターナショナル  カンファレンス  イン  コンピュータ  エイデッド  デザイン（International Conference in Computer Aided Design），2002年，pp.59-66
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述した従来技術では、隣接配線が原因となるクロストークノイズやタイミングエラーなどが生じた際には、配線確定後に人手によって配線の隣接並行配線長を減らし、問題の改善をおこなっていた。このため、エラー修正にかかる所要時間の増大や、修正による回路特性の変化などが生じるという問題があった。
【００１１】
また、配線中に並行配線長を考慮してエラーの削減をおこなう手法も提案されているが、エラーとなる部分の修正のみであり、ＬＳＩの性能向上という観点での対策はなされて
いないという問題があった。さらに、近年、ＬＳＩの集積度向上や大規模化に伴い、ＬＳ
Ｉの製造歩留まりの低下がするという問題があった。
【００１２】
この歩留まり低下の原因の一つとしてプロセス内の小さなごみ（デフェクト）によりチップ上の配線がショート／オープンを起こしてしまうランダム歩留まりがある。図１４は、従来のデフェクトによる配線ショートを示す説明図である。
【００１３】
図１４において、エッチング法によっておこなうアルミ配線では、配線パターン１４０１，１４０２間にデフェクトＤが存在すると、配線のショートが生じる。このように、配線が密集し、配線パターンどうしの隣接配線長が大きくなると、デフェクトが原因となる歩留まりの低下は避けることができないという問題があった。
【００１４】
この発明は、上述した従来技術による問題点を解消するため、簡単かつ最適な配線パターン処理をおこなうことにより、後工程での配線パターンの修正を防止し、ＬＳＩの歩留
まりの向上を図ることができる配線パターン作成装置、配線パターン作成方法、配線パターン作成プログラム、および記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１５】
上述した課題を解決し、目的を達成するため、この発明にかかる配線パターン作成装置、配線パターン作成方法、配線パターン作成プログラム、および記録媒体は、配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出し、抽出された配線パターンの集合から、前記各配線パターン間に生じるクロストークの影響度を取得し、取得された影響度に基づいて、前記配線パターンの集合を複数のグループに分け、分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付けることを特徴とする。
【００１６】
また、上記発明において、各配線パターン間の距離に基づいて、前記各配線パターン間に生じるクロストークの影響度を取得することとしてもよい。
【００１７】
また、上記発明において、配線パターンどうしの並行配線長に基づいて、前記各配線パターン間に生じるクロストークの影響度を取得することとしてもよい。
【００１８】
また、上記発明において、配線パターンに信号を供給するセルの駆動力に基づいて、前記各配線パターン間に生じるクロストークの影響度を取得することとしてもよい。
【００１９】
また、上記発明において、異なるグループどうしの配線パターン間におけるクロストークの影響度の総和が最小となるように、前記配線パターンの集合を複数のグループに分けることとしてもよい。
【００２０】
また、上記発明において、前記配線パターンの集合の中から、配線長が所定長以上となる配線パターンを抽出し、抽出された配線パターンの集合を複数のグループにグループ分けすることとしてもよい。
【００２１】
また、上記発明において、抽出された配線パターンの集合に基づいて、前記配線トラック上に前記各配線パターンを配線する場合に生じる配線エラーの制約に関する情報を取得し、取得された配線エラーの制約に関する情報に基づいて、グループ分けされた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付けることとしてもよい。
【００２２】
これらの発明によれば、クロストークの影響度が大きい配線パターンどうしを隣接配線トラックに割り付けることを防止することができる。特に、クロストークの影響度を配線パターン間の距離、並行配線長、セルの駆動能力に基づいて取得することにより、配線間容量の発生を抑制する回路設計を実現することができる。また、配線長の短い配線パターンをグループ分けの対象外とすることにより、配線自由度の向上を図ることができる。
【発明の効果】
【００２３】
本発明にかかる配線パターン作成装置、配線パターン作成方法、配線パターン作成プログラム、および記録媒体によれば、簡単かつ最適な配線パターン処理をおこなうことにより、後工程での配線パターンの修正を防止し、ＬＳＩの歩留まりの向上を図ることができ
るという効果を奏する。
【発明を実施するための最良の形態】
【００２４】
（実施の形態）
以下に添付図面を参照して、この発明にかかる配線パターン作成装置、配線パターン作成方法、配線パターン作成プログラムおよび記録媒体の好適な実施の形態を詳細に説明する。なお、下記の実施の形態にかかる配線パターン作成装置および配線パターン作成方法は、たとえば、この実施の形態にかかる配線パターン作成プログラムが記録された記録媒体を備えるＣＡＤによって実現することができる。
【００２５】
（配線パターン作成装置のハードウェア構成）
まず、この発明の実施の形態にかかる配線パターン作成装置のハードウェア構成について説明する。図１は、この発明の実施の形態にかかる配線パターン作成装置のハードウェア構成を示すブロック図である。
【００２６】
図１において、配線パターン作成装置は、ＣＰＵ１０１と、ＲＯＭ１０２と、ＲＡＭ１０３と、ＨＤＤ（ハードディスクドライブ）１０４と、ＨＤ（ハードディスク）１０５と、ＦＤＤ（フレキシブルディスクドライブ）１０６と、着脱可能な記録媒体の一例としてのＦＤ（フレキシブルディスク）１０７と、ディスプレイ１０８と、Ｉ／Ｆ（インターフェース）１０９と、キーボード１１０と、マウス１１１と、スキャナ１１２と、プリンタ１１３と、を備えている。また、各構成部はバス１００によってそれぞれ接続されている。
【００２７】
ここで、ＣＰＵ１０１は、配線パターン作成装置の全体の制御を司る。ＲＯＭ１０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ１０３は、ＣＰＵ１０１のワークエリアとして使用される。ＨＤＤ１０４は、ＣＰＵ１０１の制御にしたがってＨＤ１０５に対するデータのリード／ライトを制御する。ＨＤ１０５は、ＨＤＤ１０４の制御で書き込まれたデータを記憶する。
【００２８】
ＦＤＤ１０６は、ＣＰＵ１０１の制御にしたがってＦＤ１０７に対するデータのリード／ライトを制御する。ＦＤ１０７は、ＦＤＤ１０６の制御で書き込まれたデータを記憶したり、ＦＤ１０７に記憶されたデータを配線パターン作成装置に読み取らせたりする。
【００２９】
また、着脱可能な記録媒体として、ＦＤ１０７のほか、ＣＤ−ＲＯＭ（ＣＤ−Ｒ、ＣＤ−ＲＷ）、ＭＯ、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、メモリーカードなどであってもよい。ディスプレイ１０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ１０８は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００３０】
Ｉ／Ｆ１０９は、通信回線を通じてインターネットなどのネットワーク１１４に接続され、このネットワーク１１４を介して他の装置に接続される。そして、Ｉ／Ｆ１０９は、ネットワーク１１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ１０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００３１】
キーボード１１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス１１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００３２】
スキャナ１１２は、画像を光学的に読み取り、配線パターン作成装置内に画像データを取り込む。なお、スキャナ１１２は、ＯＣＲ機能を持たせてもよい。また、プリンタ１１３は、画像データや文書データを印刷する。プリンタ１１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。
【００３３】
（配線パターン作成装置の機能的構成）
つぎに、この発明の実施の形態にかかる配線パターン作成装置の機能的構成について説明する。図２は、この発明の実施の形態にかかる配線パターン作成装置の機能的構成を示すブロック図である。
【００３４】
図２において、配線パターン作成装置２００は、記憶部２０１と、集合抽出部２０２と、影響度取得部２０３と、グループ分け部２０４と、割付部２０５と、配線パターン抽出部２０６と、配線エラー制約情報取得部２０７と、を備える。
【００３５】
記憶部２０１は、配線トラック上に並行に配線された複数の配線パターン（のデータ）を記憶する。この記憶されている配線パターンは、たとえば、グローバル配線処理によって、任意の配線層の配線トラック上に適当に並行配線されたデータである。この記憶部２０１は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、ＨＤ１０５、ＦＤ１０７等の記録媒体によってその機能を実現する。
【００３６】
また、集合抽出部２０２は、記憶部２０１に記憶されている、配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出する。具体的には、配線トラックのうち、任意の配線トラック領域上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出する。ここで、集合抽出部２０２によって抽出された一連の隣接する配線パターンの集合について説明する。図３は、集合抽出部２０２によって抽出された一連の隣接する配線パターンの集合を示す説明図である。
【００３７】
図３において、配線パターンの集合Ｓｋ（ｋ＝１，２，・・・，Ｋ）は、任意の配線トラック領域Ｒｋ内に存在する配線パターンＷｉ（ｉ＝１，２，・・・，Ｐ）の集合である。図３では、配線パターン数は５であるため、Ｐ＝５である。また、配線トラック領域Ｒｋは、５本の配線トラックＴ１〜Ｔ５を有する。
【００３８】
ここで、配線パターンＷｉ，Ｗｊ間の距離ｄijとは、図３中、ｙ方向における配線パターンＷｉ，Ｗｊ間の間隔である。ｊは、配線パターンＷｉの添え字ｉに対応し、ｉ≠ｊである。配線パターンＷ１を例に挙げると、配線パターンＷ２との間隔は距離ｄ12であらわされ、配線パターンＷ３との間隔は距離ｄ13であらわされ、配線パターンＷ４との間隔は距離ｄ14であらわされ、配線パターンＷ５との間隔は距離ｄ15であらわされる。
【００３９】
また、配線パターンＷｉ，Ｗｊどうしの並行配線長ｃijとは、任意の配線パターンと他の配線パターンとをｙ方向（従配線方向）に重ねた場合、ｘ方向（主配線方向）に互いに
並行に配線されている配線長、すなわち、重複している配線長をいう。配線Ｗ３を例に挙げると、配線パターンＷ３と配線パターンＷ１との間では並行配線長ｃ31であり、配線パターンＷ３と配線パターンＷ２との間では並行配線長ｃ32であり、配線パターンＷ３と配線パターンＷ４との間では並行配線長ｃ34であり、配線パターンＷ３と配線パターンＷ５との間では並行配線長ｃ35である。
【００４０】
また、配線パターンの集合Ｓｋ内の配線パターンＷｉは、それぞれ信号が供給されるセルの駆動力が対応付けられている。図４は、セルの駆動力と配線パターンの対応関係を示す図表である。この図表は、たとえば、上述の記憶部２０１に記憶されている。ここで、セルの駆動力ｂｉとは、セル内部の抵抗値の逆数そのもの、または当該逆数に比例する値であらわされており、相対的に駆動力ｂｉが低いと他の配線パターンの影響を受け易く、駆動力ｂｉが高いと他の配線パターンに影響を与え易い。
【００４１】
集合抽出部２０２は、配線パターンの集合Ｓｋを抽出する際、集合Ｓｋ内の各配線パターンＷｉに対応する駆動力も抽出する。この集合抽出部２０２は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、ＨＤ１０５、ＦＤ１０７等に記録されたプログラムを、ＣＰＵ１０１が実行することによって、またはＩ／Ｆ１０９によってその機能を実現する。
【００４２】
影響度取得部２０３は、集合抽出部２０２によって抽出された配線パターンの集合から、各配線パターンＷｉ，Ｗｊ間に生じるクロストークの影響度を取得する。このクロストークの影響度Ｆijは、後述するグループ分け部２０４によるグループ分け処理の際に重み付けされるコスト値として用いられる。
【００４３】
ここで、「クロストーク」とは、配線間に生じる容量のために、信号の波形、遅延が変動する現象であり、他の配線パターンに影響を与える。たとえば、隣接する一対の配線パターンＷｉ，Ｗｊが長距離にわたって近接したり、配線パターンＷｉ，Ｗｊ間の距離が近接したりすると、配線間容量が大きくなり、クロストークが生じることとなる。その影響により他の配線パターンにノイズが発生したり、遅延量が大きくなったりする。また、上述したように、駆動力もクロストークの発生原因となる。
【００４４】
この影響度取得部２０３は、各配線パターンＷｉ，Ｗｊ間の距離ｄijに基づいて、各配線パターンＷｉ，Ｗｊ間に生じるクロストークの影響度Ｆijを取得することができる。具体的には、集合Ｓｋ内の各配線パターンＷｉ，Ｗｊ間の距離ｄijを抽出し、この抽出された距離ｄijをクロストークの影響度とすることができる。この距離ｄijが大きいと配線間容量が小さくなり、距離ｄijが小さいと配線間容量が大きくなる。
【００４５】
また、影響度取得部２０３は、配線パターンＷｉ，Ｗｊどうしの並行配線長ｃijに基づいて、各配線パターンＷｉ，Ｗｊ間に生じるクロストークの影響度Ｆijを取得することができる。具体的には、集合Ｓｋ内の各配線パターンＷｉ，Ｗｊどうしの並行配線長ｃijを抽出し、この抽出された並行配線長ｃijをクロストークの影響度とすることができる。この並行配線長ｃijが大きいと配線間容量が大きくなり、並行配線長ｃijが小さいと配線間容量が小さくなる。
【００４６】
また、影響度取得部２０３は、配線パターンに信号を供給するセルの駆動力ｂｉに基づいて、各配線パターンＷｉ，Ｗｊ間に生じるクロストークの影響度Ｆijを取得することができる。たとえば、配線パターンＷｉごとに抽出されたセルの駆動力ｂｉを抽出し、抽出
元の一の配線パターンＷｉの駆動力ｂｉと他の配線パターンＷｊの駆動力ｂｊとの差の絶対値ｂijを算出する。この算出された絶対値ｂijをクロストークの影響度Ｆijとすることができる。この絶対値ｂijが大きくなればなるほど、いずれか一方の配線パターンＷｉが他方の配線パターンＷｊに影響を与える。
【００４７】
また、影響度取得部２０３は、上述した距離ｄij、並行配線長ｃij、駆動力の差の絶対値ｂijの組み合わせに基づいて、各配線パターンＷｉ，Ｗｊ間に生じるクロストークの影響度Ｆijを取得することができる。たとえば、距離ｄijと並行配線長ｃijを用いる場合、距離ｄijの逆数と並行配線長ｃijとを掛けることにより、クロストークの影響度Ｆijを算出することができる。
【００４８】
また、距離ｄijと駆動力ｂｉを用いる場合、距離ｄの逆数と駆動力の差の絶対値ｂijと
を掛けることにより、クロストークの影響度Ｆijを算出することができる。さらに、並行配線長ｃijと駆動力の差の絶対値ｂijを用いる場合、並行配線長ｃと駆動力の差の絶対値ｂijとを掛けることにより、クロストークの影響度Ｆijを算出することができる。また、距離ｄij、並行配線長ｃij、駆動力ｂiをすべて用いる場合、距離ｄijの逆数と並行配線長ｃijと駆動力の差の絶対値ｂijとを掛けることにより、クロストークの影響度Ｆijを算出することができる。
【００４９】
この影響度取得部２０３は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、ＨＤ１０５、ＦＤ１０７等に記録されたプログラムを、ＣＰＵ１０１が実行することによって、またはＩ／Ｆ１０９によってその機能を実現する。
【００５０】
グループ分け部２０４は、影響度取得部２０３によって取得された影響度Ｆijに基づいて、配線パターンの集合Ｓｋを複数のグループＧｍ（ｍ＝１、２、・・・、Ｍ）に分ける。グループ数ｍは、あらかじめ設定することができる。このグループ分けは、たとえば、異なるグループＧｍどうしの配線パターンＷｉ間におけるクロストークの影響度Ｆijの総和Σが最小となるように、配線パターンの集合を複数のグループに分けることができる。このグループ分けはミンカット法によっておこなうことができる。
【００５１】
この場合、配線トラック領域Ｒｋ内のトラック数をｔとし、グループ分けされるグループ数をｍとすると、各グループ内のノードＮｉの数の最大値、すなわち、配線パターンＷｉの数の最大値ＰがＰ＝Ｔ／ｍとなるように、グループ内のノード数をほぼ均等に分配することができる。なお、Ｐ＝Ｔ／ｍが割り切れない場合は小数点以下を切り上げる。
【００５２】
このグループ分け部２０４によるグループ分けについて具体的に説明する。まず、配線パターンの集合Ｓｋ内の配線パターンＷｉと、影響度取得部２０３によって取得された配線パターン間の影響度Ｆijとを用いて、完全グラフを作成する。図５は、完全グラフの一例を示す説明図である。
【００５３】
図５において、完全グラフ５００は、配線パターンＷｉに対応するノードＮｉと、配線パターン間の影響度に対応するエッジｅijとから構成されている。たとえば、エッジｅ12は、配線パターンＷ１と配線パターンＷ２との間の影響度Ｆ12をあらわしている。
【００５４】
なお、本例では、配線トラック領域Ｒｋ内のトラック数ＴがＴ＝５であり、また、グループ分けされるグループ数ｍをｍ＝２とすると、各グループ内のノードＮｉの数の最大値、すなわち、配線パターンＷｉの数の最大値Ｐは、Ｐ＝３となる。したがって、グループ分け部２０４は、グループ数が２、グループ内のノードの最大値が３という条件が与えられる。
【００５５】
この条件下で、異なるグループＧｍどうしの配線パターン間におけるクロストークの影響度Ｆijの総和Σが最小となるように、配線パターンの集合を複数のグループに分けることができる。グループ内のノードはエッジによって連結される。図５に示した完全グラフでは、エッジｅ12、ｅ13、ｅ23、ｅ45について影響度Ｆ12、Ｆ13、Ｆ23、Ｆ45が高く、残余のエッジｅ14、ｅ15、ｅ24、ｅ25、ｅ34、ｅ35の影響度Ｆ14、Ｆ15、Ｆ24、Ｆ25、Ｆ34、Ｆ35は、エッジｅ12、ｅ13、ｅ23、ｅ45の影響度Ｆ12、Ｆ13、Ｆ23、Ｆ45に比べて低い値とされている。
【００５６】
この影響度Ｆ14、Ｆ15、Ｆ24、Ｆ25、Ｆ34、Ｆ35の総和Σが最小である場合、グループ分けがおこなわれる。図６は、グループ分けされたグループの一例を示す説明図である。図６において、グループＧ１には、ノードＮ１〜Ｎ３が含まれており、グループＧ２には、ノードＮ４、Ｎ５が含まれている。
【００５７】
同一グループ内のノード、たとえば、グループＧ１内のノードＮ１〜Ｎ３によってあらわされる配線パターンＷ１〜Ｗ３は、互いに隣接配線してはいけないことを示しており、同様に、グループＧ２内のノードＮ４、Ｎ５によってあらわされる配線パターンＷ４、Ｗ５も互いに隣接配線してはいけないことを示している。
【００５８】
なお、このグループ分け部２０４によってグループ分けされる条件を、配線トラック制約と呼ぶ。このグループ分け部２０４は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、ＨＤ１０５、ＦＤ１０７等に記録されたプログラムを、ＣＰＵ１０１が実行することによって、またはＩ／Ｆ１０９によってその機能を実現する。
【００５９】
また、配線パターン抽出部２０６は、配線パターンの集合Ｓｋの中から、配線長が所定長以上となる配線パターンを抽出する。具体的には、所定長以上の配線パターンをグループ分け対象の配線パターンとして抽出し、所定長以上でない配線パターンをグループ分けの対象外の配線パターンとして抽出する。そして、グループ分け対象の配線パターンについては、上述のグループ分け部２０４によってグループ分けされ、グループ分けの対象外の配線パターンについては、上述のグループ分け部２０４によってグループ分けされない。
【００６０】
この場合の完全グラフを図７に示す。図７は、完全グラフの他の例を示す説明図である。配線パターンＷ３〜Ｗ５の配線長が、所定長以上でないとすると、図６に示した、配線パターンＷ３〜Ｗ５に対応するノードＮ３〜Ｎ５は、図７において削除される。したがって、図６において、残余のノードＮ１、Ｎ２についてミンカット法により、グループ分けする。図８は、グループ分けされたグループの他の例を示す説明図である。図８において、グループＧ１には、ノードＮ１、Ｎ２が含まれており、グループＧ２は空集合Ｎｕｌｌとなっている。
【００６１】
この配線パターン抽出部２０６は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、ＨＤ１０５、ＦＤ１０７等に記録されたプログラムを、ＣＰＵ１０１が実行することによって、またはＩ／Ｆ１０９によってその機能を実現する。
【００６２】
また、割付部２０５は、グループ分け部２０４によって分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように配線トラック上に割り付ける。換言すれば、他のグループ内の配線パターンどうしが隣接するように、配線トラック上に割り付ける。
【００６３】
具体的には、グループ数がｍの場合、まず、グループＧ１内のノードに対応する配線パターンを配線トラックＴ１に割り付け、グループＧ２内のノードに対応する配線パターンを配線トラックＴ２に割り付ける。そして、同様に、グループＧｍまで順次割り付ける。このあと、グループ内にノードが残っている場合、そのノードの対応する配線パターンを、配線トラックＴm+1から割り付ける。
【００６４】
より具体的に図を用いて説明する。図９は、配線トラック領域Ｒｋに割り付けられた配線パターンの一例を示す説明図である。図９において、配線トラック領域Ｒｋでは、グループ数が２の場合、グループＧ１の配線パターンＷ１〜Ｗ３は、奇数番号の配線トラックＴ１、Ｔ３、Ｔ５に割り付け、グループＧ２の配線パターンＷ４、Ｗ５は、偶数番号の配線トラックＴ２、Ｔ４に割り付ける。なお、図中９００は、配線禁止領域である。これにより、同一グループ内のノードに対応する配線パターンどうしが隣接しないように配線することができる。
【００６５】
この割付部２０５は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、ＨＤ１０５、ＦＤ１０７等に記録されたプログラムを、ＣＰＵ１０１が実行することによって、またはＩ／Ｆ１０９によってその機能を実現する。
【００６６】
また、配線エラー制約情報取得部２０７は、集合抽出部２０２によって抽出された配線パターンの集合に基づいて、配線トラック上に各配線パターンを配線する場合に生じる配線エラーの制約に関する情報（配線エラー制約情報）を取得する。そして、割付部２０５は、配線エラー制約情報取得部２０７によって取得された配線エラー制約情報に基づいて、グループ分け部２０４によってグループ分けされた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように配線トラック上に割り付ける。
【００６７】
ここで、「配線エラー制約」とは、ＬＳＩのレイアウト設計上要求されるデザインルー
ルであり、具体的には、たとえば、スペーシングエラーや接触不良、断線などを防止するための制約である。また、「配線エラー制約情報」とは、たとえば、上述した配線エラー制約を数値化したコスト値である。より具体的には、配線パターンＷｉの配線長や配線禁
止領域のｘ方向の長さや存在する配線トラック番号、配線トラック上の位置などによって
あらかじめ設定される。
【００６８】
ここで、上述した割付部２０５によって割り付けられた配線パターンの他の例を図１０に示す。図１０は、配線トラック領域に割り付けられた配線パターンの他の例を示す説明図である。この図１０に示した例は、配線エラー制約を考慮せずに割り付けられた配線パターンであり、配線パターンＷ５が、配線トラックＴ４の配線禁止領域９００と重なっている。このような場合、配線エラーとなるため、割付部２０５では、配線パターンの入れ替えをおこなう。具体的には、配線トラックＴ２に割り付けられた配線パターンＷ４と、配線トラックＴ４に割り付けられた配線パターンＷ５とを入れ替える。
【００６９】
なお、割付部２０５による配線パターンの入れ替えをおこなっても配線エラーが解消されない場合、再度グループ分け部２０４によるグループ分けを実行する。この場合、今回のグループ分けによるクロストークの影響度Ｆijの総和Σは、前回の総和Σ以上となるが、グループ数を変更したり、グループ内のノード（配線パターン）の組み合わせを変更したりして、異なるグループ分けをおこなう。
【００７０】
この配線エラー制約情報取得部２０７は、具体的には、たとえば、図１に示したＲＯＭ１０２、ＲＡＭ１０３、ＨＤ１０５、ＦＤ１０７等に記録されたプログラムを、ＣＰＵ１０１が実行することによって、またはＩ／Ｆ１０９によってその機能を実現する。
【００７１】
（配線パターン作成処理手順）
つぎに、この発明の実施の形態にかかる配線パターン作成処理手順の一例について説明する。図１１は、この発明の実施の形態にかかる配線パターン作成処理手順の一例を示すフローチャートである。図１１において、まず、配線パターンの集合数をＫとし、初期値をｋ＝１とする（ステップＳ１１０１）。
【００７２】
つぎに、集合抽出部２０２により、配線パターンの集合Ｓｋを抽出する（ステップＳ１１０２）。また、配線エラー制約情報取得部２０７により、抽出された集合Ｓｋについての配線エラー制約情報を取得する（ステップＳ１１０３）。
【００７３】
そして、影響度取得部２０３により、集合Ｓｋ内の配線パターンＷｉ、Ｗｊどうしのクロストークの影響度Ｆijを取得する（ステップＳ１１０４）。このあと、グループ分け部２０４により、集合Ｓｋのグループ分けをおこなう（ステップＳ１１０５）。
【００７４】
そして、割付部２０５により、各グループの配線パターンを、配線トラックに割り付ける（ステップＳ１１０６）。このあと、割り付けられた配線パターンに配線エラーがあるかどうかを判定する（ステップＳ１１０７）。配線エラーがある場合（ステップＳ１１０７：Ｙｅｓ）、再割付回数が所定回数でないときは（ステップＳ１１０８：Ｎｏ）、ステップＳ１１０６に移行して、配線パターンの割り付け（再割付）をおこなう。
【００７５】
一方、再割付回数が所定回数となった場合（ステップＳ１１０８：Ｙｅｓ）、ステップＳ１１０５に移行して、再度グループ分けをおこなう。また、ステップＳ１１０７において、配線エラーがない場合（ステップＳ１１０７：Ｎｏ）、ｋ＝Ｋでない場合（ステップＳ１１０９：Ｎｏ）、ｋをインクリメントして（ステップＳ１１１０）、ステップＳ１１０２に移行し、配線パターンの集合Ｓｋを抽出する。一方、ｋ＝Ｋの場合（ステップＳ１１０９：Ｙｅｓ）、一連の処理を終了する。
【００７６】
この実施の形態によれば、配線パターンを最適な配線トラックに割り付けることができるため、隣接配線パターン間のクロストークの発生を抑制し、ＬＳＩの性能の向上を図ることができる。また、これにより、後工程での配線パターンの修正を防止し、ＬＳＩの歩
留まりの向上を図ることができる。
【００７７】
つぎに、この発明の実施の形態にかかる配線パターン作成処理手順の他の例について説明する。図１２は、この発明の実施の形態にかかる配線パターン作成処理手順の他の例を示すフローチャートである。このフローチャートは、図１１の処理手順に、配線パターン抽出部２０６による配線パターンＷｉの抽出処理手順を追加した例である。なお、図１１に示したフローチャートと同一ステップには同一ステップ番号を付し、その説明を省略する。
【００７８】
図１２において、ステップＳ１１０３のあと、配線パターン数をＰとし、初期値をｉ＝１とする（ステップＳ１２０４）。配線パターンＷｉの配線長が所定長以上かどうかを判定する（ステップＳ１２０５）。所定長以上である場合（ステップＳ１２０５：Ｙｅｓ）、配線パターンＷｉをグループ分け対象の配線パターンとして抽出する（ステップＳ１２０６）。一方、所定長以上でない場合（ステップＳ１２０５：Ｎｏ）、配線パターンＷｉをグループ分け対象外の配線パターンとして抽出する（ステップＳ１２０７）。
【００７９】
そして、ｉ＝Ｐでない場合（ステップＳ１２０８：Ｎｏ）、ｉをインクリメントして（ステップＳ１２０９）、ステップＳ１２０５に移行する。一方、ｉ＝Ｐの場合（ステップＳ１２０８：Ｙｅｓ）、配線パターンＷｉの抽出処理が終了したこととなり、グループ分け対象となった配線パターンＷｉについて、影響度取得部２０３により、クロストークの影響度Ｆijを取得する（ステップＳ１２１０）。
【００８０】
そして、グループ分け部２０４により、グループ分け対象の配線パターンＷｉをグルー
プ分けする（ステップＳ１２１１）。割付部２０５により、各グループＧｉの配線パター
ンＷｉを、配線トラックに割り付ける（ステップＳ１２１２）。このあと、割り付けられ
た配線パターンＷｉに配線エラーがあるかどうかを判定する（ステップＳ１２１３）。配
線エラーがある場合（ステップＳ１２１３：Ｙｅｓ）、再割付回数が所定回数でないときは（ステップＳ１２１４：Ｎｏ）、ステップＳ１２１２に移行して、配線パターンの割り付け（再割付）をおこなう。
【００８１】
一方、再割付回数が所定回数となった場合（ステップＳ１２１４：Ｙｅｓ）、ステップＳ１２１１に移行して、再度グループ分けをおこなう。また、ステップＳ１２１３において、配線エラーがない場合（ステップＳ１２１３：Ｎｏ）、ｋ＝Ｋでない場合（ステップＳ１２１５：Ｎｏ）、ｋをインクリメントして（ステップＳ１２１６）、ステップＳ１１０２に移行し、配線パターンの集合Ｓｋを抽出する。一方、ｋ＝Ｋの場合（ステップＳ１２１５：Ｙｅｓ）、一連の処理を終了する。
【００８２】
この実施の形態によれば、配線長が所定長よりも短い配線パターンについては、配線間容量が小さくなるため、クロストークの影響が小さい配線パターンであるとして、グループ分けの対象外としている。したがって、このような配線パターンについては配線トラック制約を考慮せずに、配線エラー制約のみを考慮して配線トラックに割り付けることができ、配線パターンの割り付けの自由度の向上を図ることができる。これにより、配線パターンの作成を容易におこなうことができる。
【００８３】
また、配線長が所定長以上の配線パターンについては、上述した場合と同様、配線パターンを最適な配線トラックに割り付けることができるため、隣接配線パターン間のクロストークの発生を抑制し、ＬＳＩの性能の向上を図ることができる。したがって、後工程での配線パターンの修正を防止し、ＬＳＩの歩留まりの向上を図ることができる。
【００８４】
以上説明したように、配線パターン作成装置２００、配線パターン作成方法、および配線パターン作成プログラムによれば、簡単かつ最適な配線パターン処理をおこなうことにより、後工程での配線パターンの修正を防止し、ＬＳＩの歩留まりの向上を図ることがで
きるという効果を奏する。
【００８５】
なお、本実施の形態で説明した配線パターン作成方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネット等のネットワークを介して配布することが可能な伝送媒体であってもよい。
【００８６】
（付記１）配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出する集合抽出手段と、
前記集合抽出手段によって抽出された配線パターンの集合から、前記各配線パターン間に生じるクロストークの影響度を取得する影響度取得手段と、
前記影響度取得手段によって取得された影響度に基づいて、前記配線パターンの集合を複数のグループに分けるグループ分け手段と、
前記グループ分け手段によって分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付ける割付手段と、
を備えることを特徴とする配線パターン作成装置。
【００８７】
（付記２）前記影響度取得手段は、
前記各配線パターン間の距離に基づいて、前記各配線パターン間に生じるクロストークの影響度を取得することを特徴とする付記１に記載の配線パターン作成装置。
【００８８】
（付記３）前記影響度取得手段は、
前記配線パターンどうしの並行配線長に基づいて、前記各配線パターン間に生じるクロストークの影響度を取得することを特徴とする付記１または２に記載の配線パターン作成装置。
【００８９】
（付記４）前記影響度取得手段は、
前記配線パターンに信号を供給するセルの駆動力に基づいて、前記各配線パターン間に生じるクロストークの影響度を取得することを特徴とする付記１〜３のいずれか一つに記載の配線パターン作成装置。
【００９０】
（付記５）前記グループ分け手段は、
異なるグループどうしの配線パターン間におけるクロストークの影響度の総和が最小となるように、前記配線パターンの集合を複数のグループに分けることを特徴とする付記１〜４のいずれか一つに記載の配線パターン作成装置。
【００９１】
（付記６）前記配線パターンの集合の中から、配線長が所定長以上となる配線パターンを抽出する配線パターン抽出手段を備え、
前記グループ分け手段は、
前記配線パターン抽出手段によって抽出された配線パターンの集合を複数のグループにグループ分けすることを特徴とする付記５に記載の配線パターン作成装置。
【００９２】
（付記７）前記集合抽出手段によって抽出された配線パターンの集合に基づいて、前記配線トラック上に前記各配線パターンを配線する場合に生じる配線エラーの制約に関する情報を取得する配線エラー制約情報取得手段を備え、
前記割付手段は、
前記配線エラー制約情報取得手段によって取得された配線エラーの制約に関する情報に基づいて、前記グループ分け手段によってグループ分けされた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付けることを特徴とする付記１〜６のいずれか一つに記載の配線パターン作成装置。
【００９３】
（付記８）配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出する集合抽出工程と、
前記集合抽出工程によって抽出された配線パターンの集合から、前記各配線パターン間に生じるクロストークの影響度を取得する影響度取得工程と、
前記影響度取得工程によって取得された影響度に基づいて、前記配線パターンの集合を複数のグループに分けるグループ分け工程と、
前記グループ分け工程によって分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付ける割付工程と、
を含んだことを特徴とする配線パターン作成方法。
【００９４】
（付記９）配線トラック上に並行に配線された複数の配線パターンの中から、一連の隣接する配線パターンの集合を抽出させる集合抽出工程と、
前記集合抽出工程によって抽出された配線パターンの集合から、前記各配線パターン間に生じるクロストークの影響度を取得させる影響度取得工程と、
前記影響度取得工程によって取得された影響度に基づいて、前記配線パターンの集合を複数のグループに分けさせるグループ分け工程と、
前記グループ分け工程によって分けられた各グループ内の配線パターンを、同一グループ内の配線パターンが隣接しないように前記配線トラック上に割り付けさせる割付工程と、
をコンピュータに実行させることを特徴とする配線パターン作成プログラム。
【００９５】
（付記１０）付記９に記載の配線パターン作成プログラムを記録したコンピュータ読み取り可能な記録媒体。
【産業上の利用可能性】
【００９６】
以上のように、本発明にかかる配線パターン作成装置、配線パターン作成方法、配線パターン作成プログラム、および記録媒体は、ＬＳＩなどの半導体装置のレイアウト設計に有用であり、特に、アルミ配線などエッチング法によって配線をおこなう場合の配線設計に適している。
【図面の簡単な説明】
【００９７】
【図１】この発明の実施の形態にかかる配線パターン作成装置のハードウェア構成を示すブロック図である。
【図２】この発明の実施の形態にかかる配線パターン作成装置の機能的構成を示すブロック図である。
【図３】集合抽出部によって抽出された一連の隣接する配線パターンの集合を示す説明図である。
【図４】セルの駆動力と配線パターンの対応関係を示す図表である。
【図５】完全グラフの一例を示す説明図である。
【図６】グループ分けされたグループの一例を示す説明図である。
【図７】完全グラフの他の例を示す説明図である。
【図８】グループ分けされたグループの他の例を示す説明図である。
【図９】配線トラック領域に割り付けられた配線パターンの一例を示す説明図である。
【図１０】配線トラック領域に割り付けられた配線パターンの他の例を示す説明図である。
【図１１】この発明の実施の形態にかかる配線パターン作成処理手順の一例を示すフローチャートである。
【図１２】この発明の実施の形態にかかる配線パターン作成処理手順の他の例を示すフローチャートである。
【図１３】従来の配線エラーを示す説明図である。
【図１４】従来のデフェクトによる配線ショートを示す説明図である。
【符号の説明】
【００９８】
２００  配線パターン作成装置
２０２  集合抽出部
２０３  影響度取得部
２０４  グループ分け部
２０５  割付部
２０６  配線パターン抽出部
２０７  配線エラー制約情報取得部
【図１】
2006031468.tif 000003
【図２】
2006031468.tif 000004
【図３】
2006031468.tif 000005
【図４】
2006031468.tif 000006
【図５】
2006031468.tif 000007
【図６】
2006031468.tif 000008
【図７】
2006031468.tif 000009
【図８】
2006031468.tif 000010
【図９】
2006031468.tif 000011
【図１０】
2006031468.tif 000012
【図１１】
2006031468.tif 000013
【図１２】
2006031468.tif 000014
【図１３】
2006031468.tif 000015
【図１４】
2006031468.tif 000016