(57)【要約】    【課題】1ネットを配線するにあたって配線領域に制限を与えて効率的に短時間で配線する。    【解決手段】  配線領域設定部４０がネットを構成する端子の集合を含む最大矩形の配線領域に設定し、この配線領域設定を対象に配線決定部４２で最短距離となるネット間の配線を決定する。配線領域拡大部４４は配線違反又は未結線端子が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に配線決定部４２で配線を決定させる。セルの同一機能をもつ複数の入力端子の１つを使用した場合の未使用の入力端子をクリップ端子として電源端子に配線するクリップネットについても、セル領域を配線領域に設定して配線し、配線違反又は未結線のクリップ端子が存在した場合、現在のセル配線領域を拡大して配線を繰り返す。    【選択図】        図１
2006155118.tif 000002
【特許請求の範囲】
【請求項１】
半導体回路につき１ネット単位に配線を決定する配線方法に於いて、
ネットを構成する端子の集合を含む最大矩形を配線領域に設定する配線領域設定ステップと、
前記配線領域を対象に最短距離となるネット間の配線を決定する配線決定ステップと、
前記配線決定ステップで未結線端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に前記配線決定ステップで配線を決定させる配線領域拡大ステップと、
を備えたことを特徴とする配線方法。
【請求項２】
半導体回路に配置したセルの同一機能をもつ複数の入力端子の１つを使用した場合の未使用の入力端子をクリップ端子として電源端子に配線するクリップネットの配線方法に於いて、
セル領域を配線領域に設定する配線領域設定ステップと、
前記配線領域を対象に最短距離となるクリップ端子と電源端子との間の配線を決定する配線決定ステップと、
前記配線決定ステップで未結線のクリップ端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に前記配線決定ステップで配線を決定させる配線領域拡大ステップと、
を備えたことを特徴とする配線方法。
【請求項３】
コンピュータに、
ネットを構成する端子の集合を含む最大矩形を配線領域に設定する配線領域設定ステップと、
前記配線領域を対象に最短距離となるネット間の配線を決定する配線決定ステップと、
前記配線決定ステップで未結線端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に前記配線決定ステップで配線を決定させる配線領域拡大ステップと、
を実行させることを特徴とするプログラム。
【請求項４】
コンピュータに、
同一機能をもつ複数の入力端子の１つを使用した場合の未使用の入力端子となるクリップ端子と電源端子を備えたセル領域を配線領域に設定する配線領域設定ステップと、
前記配線領域を対象に最短距離となるクリップ端子と電源端子との間の配線を決定する配線決定ステップと、
前記配線決定ステップで未結線のクリップ端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に前記配線決定ステップで配線を決定させる配線領域拡大ステップと、
を備えたことを特徴とする配線プログラム。
【請求項５】
半導体回路につき１ネット単位に配線を決定する配線装置に於いて、
ネットを構成する端子の集合を含む最大矩形を配線領域に設定する配線領域設定部と、
前記配線領域を対象に最短距離となるネット間の配線を決定する配線決定部と、
前記配線決定部で未結線端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に前記配線決定部で配線を決定させる配線領域拡大部と、
を備えたことを特徴とする配線装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＬＳＩのレイアウト設計における配線方法、プログラム及び装置に関し、特に、高密度で高速の配線処理を可能とする配線方法、プログラム及び装置に関する。
【背景技術】
【０００２】
近年、ＬＳＩ設計システムについては、トランジスタサイズの微細化によって高密度設計システム、また開発サイクルの短縮化によって、より短期間で設計終了する高速な設計システムが要求されている。これに伴ってＬＳＩ設計システム内の自動配線システムにおいても、高密度で高速の自動配線が求められている。
【０００３】
自動配線システムは、ネット情報によって配置された素子間の結線を設計ルールや各種の制約条件を満たすように処理するものであり、通常、グローバル配線と詳細配線に分けて処理する。
【０００４】
グローバル配線は、各ネットを特定の配線領域に分けて配線割当てを行うもので、局所的な混雑を避けてどの配線領域を使用するかを決定する。詳細配線は、各ネットの実際の配線を行うもので、２点間又は多点間のネットを一本ずつ順番に最短距離で配線する。配線アルゴリズムとしては、迷路法、線分探索法、チャネル配線法などが使用される。
【０００５】
このような従来の自動配線システムの詳細配線にあっては、1ネットの配線についてはチップ全面を配線領域とする方法を採用している。
【特許文献１】特開平５−１８１９３６号
【特許文献２】特開平６−１２４３２１号
【特許文献３】特開平５−１６０３７５号
【特許文献４】特開平５−２４３３８３号
【特許文献５】特開平９−１４７００９号
【特許文献６】特開平１０−１８９７４６号
【特許文献７】特開２００３−３０３２１７号
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、このような従来の自動配線システムにあっては、1ネットの配線についてチップ全面を配線領域としていたため、迷路法、線分探索法、チャネル配線法等の配線アルゴリズムに従った配線処理をチップ全面の広い領域を対象に実行しており、このため自動配線の処理時間が長時間化してしまい、仮に配線処理が成功せずに例えば論理設計等の上流から再度設計をやり直すような場合も考慮すると、自動配線に時間がかかることに伴いＬＳＩ設計自体のＴＡＴ（Ｔｕｒｎ  Ａｒｏｕｎｄ  Ｔｉｍｅ）も延びてしまうという問題がある。
【０００７】
本発明は、1ネットを配線するに当たって配線領域に制限を与えて効率的に短時間で配線を完了する配線方法、プログラム及び装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
図１は本発明の原理説明図である。
【０００９】
本発明は、一般ネットを対象とした配線方法を提供する。本発明は、半導体回路につき１ネット単位に配線を決定する配線方法に於いて、
ネットを構成する端子の集合を含む最大矩形を配線領域に設定する配線領域設定ステップと、
配線領域を対象に最短距離となるネット間の配線を決定する配線決定ステップと、
配線決定ステップで未結線端子や規則違反（バイオレーション）が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に配線決定ステップで配線を決定させる配線領域拡大ステップと、
を備えたことを特徴とする。
【００１０】
また本発明はクリップネットを対象とした配線方法を提供する。本発明は、半導体回路に配置したセルの同一機能をもつ複数の入力端子の１つを使用した場合の未使用の入力端子をクリップ端子として電源端子に配線するクリップネットの配線方法に於いて、
セル領域を配線領域に設定する配線領域設定ステップと、
配線領域を対象に最短距離となるクリップ端子と電源端子との間の配線を決定する配線決定ステップと、
配線決定ステップで未結線のクリップ端子や規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に配線決定ステップで配線を決定させる配線領域拡大ステップと、
を備えたことを特徴とする。
【００１１】
ここで、配線領域拡大ステップで使用するパラメータは、全てのネットを対象とするデフォルトの拡大関数を含む。また配線領域拡大ステップで使用するパラメータは、ネットの種別に応じて異なる拡大関数を含む。配線領域拡大ステップで使用するパラメータは、特定のネットについて拡大関数をゼロとしても良い。
【００１２】
配線領域拡大ステップで使用するパラメータは、配線層に応じて異なる拡大関数を含む。配線領域拡大ステップで使用するパラメータの拡大関数は、拡大率、グリット数又は増加寸法である。配線領域拡大ステップで使用するパラメータは、矩形配線領域の水平方向と垂直方向の両方又は何れか一方の拡大関数である。
【００１３】
本発明は、コンピュータで実行される、一般ネットを対象としたプログラムを提供する。本発明のプログラムは、コンピュータに、
ネットを構成する端子の集合を含む最大矩形を配線領域に設定する配線領域設定ステップと、
配線領域を対象に最短距離となるネット間の配線を決定する配線決定ステップと、
配線決定ステップで未結線端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に配線決定ステップで配線を決定させる配線領域拡大ステップと、
を実行させることを特徴とする。
【００１４】
本発明は、コンピュータで実行されるクリップネットを対象とした配線プログラムを提供する。本発明の配線プログラムは、コンピュータに、
同一機能をもつ複数の入力端子の１つを使用した場合の未使用の入力端子となるクリップ端子と電源端子を備えたセル領域を配線領域に設定する配線領域設定ステップと、
配線領域を対象に最短距離となるクリップ端子と電源端子との間の配線を決定する配線決定ステップと、
配線決定ステップで未結線のクリップ端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に配線決定ステップで配線を決定させる配線領域拡大ステップと、
を備えたことを特徴とする。
【００１５】
本発明は、一般ネットを対象とした配線装置を提供する。本発明は、半導体回路につき１ネット単位に配線を決定する配線装置に於いて、
ネットを構成する端子の集合を含む最大矩形の配線領域に設定する配線領域設定部と、
配線領域を対象に最短距離となるネット間の配線を決定する配線決定部と、
配線決定部で未結線端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に配線決定部で配線を決定させる配線領域拡大部と、
を備えたことを特徴とする。
【００１６】
本発明は、クリップネットを対象としたネット配線装置を提供する。本発明は、半導体回路に配置したセルの同一機能をもつ複数の入力端子の１つを使用した場合の未使用の入力端子をクリップ端子として電源端子に配線するクリップネットの配線装置に於いて、
セル領域を配線領域に設定する配線領域設定部４０と、
配線領域を対象に最短距離となるクリップ端子と電源端子との間の配線を決定する配線決定部４２と、
配線決定部４２で未結線のクリップ端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に配線決定部で配線を決定させる配線領域拡大部４４と、
を備えたことを特徴とする。
【００１７】
なお、本発明の配線プログラム及び配線装置の詳細は、本発明の配線方法の場合と基本的に同じになる。
【発明の効果】
【００１８】
本発明によれば、1ネットを配線するにあたって、その配線領域に制限を与えて処理することで、必要最小限の配線領域で配線処理を終了でき、配線領域をチップ全面とした場合に比べ配線処理が効率的に実行され、短時間で配線処理を終了することができる。
【００１９】
例えば一般ネットについてはネットを構成する端子の集合の最大矩形を配線領域として配線を決定し、もし未結線の端子や規則違反があった場合には、予め設定したパラメータにより現在の配線領域を拡大しながら未結線の端子や規則違反がなくなるまで配線処理を繰り返すことで、常に配線可能な最小領域を配線領域とした効率的な配線処理ができる。
【００２０】
またセルのクリップ端子を電源端子に落とすクリップネットの配線についても、セル領域を配線領域として配線を決定し、もし未結線のクリップ端子や規則違反があった場合には、予め設定したパラメータにより現在の配線領域を拡大しながら未結線のクリップ端子や規則違反がなくなるまで配線処理を繰り返すことで、常に配線可能な最小領域を配線領域とした効率的な配線処理ができる。通常、ＶＬＳＩにあっては、クリップ端子数は１００万〜２００万と非常に多く、このクリップ端子の配線領域をセル内に抑えることで配線処理の負荷を大幅に低減できる。
【００２１】
また配線領域の拡大に使用するパラメータとして、クロックネットについてはシビアな拡大率を設定し、一方、スキャンネットについては緩やかな拡大率を設定するというようにネットの種別に応じて未結線端子が残った場合の配線領域の拡大率をコントロール可能とする。
【００２２】
更に配線領域の拡大に使用するパラメータとして、例えば厳格な回路設計が要求されるネットについては、拡大のためのパラメータをゼロとして未結線端子又は規則違反が存在した場合にも配線領域の拡大を許さず、配線処理を失敗させて論理設計などの上流の設計からやり直しをさせるといった手法をとることも可能とする。
【発明を実施するための最良の形態】
【００２３】
図２は本発明の配線方法が適用されるＬＳＩ設計システムの全体構成のブロック図である。図２において、ＬＳＩ設計システムは、システム仕様設計部１０、機能設計部１２、論理設計部１４、回路設計部１６、レイアウト設計部１８、設計検証部２０及びＬＳＩ製造部２２から構成されている。このうちレイアウト設計部１８には配置処理部２４と配線処理部２６が設けられ、本発明の配線方法は配線処理部２６について適用される。
【００２４】
システム仕様設計部１０は、目的とするＬＳＩのシステム仕様を実現するため、システム全体を、どのような機能ブロックに分け、どのように動作させるかを決定する。設計結果の妥当性を調べるためには動作シミュレータや方式シミュレータなどが使用される。
【００２５】
機能設計部１２は機能ブロックの内部構造と動作を決定するレジスタトランスファレベル（ＲＴレベル）の設計を行う。設計結果の検証には機能シミュレータが使用される。論理設計部１４はゲートレベルでの論理回路設計を行う。動作確認には論理シミュレータやタイミングシミュレータなどが使用される。回路設計部１６はトランジスタ回路の設計を行う。設計した回路特性を調べるためには回路シミュレータが使用される。
【００２６】
レイアウト設計部１８は回路図を物理的形状と寸法を持つ素子の配置配線に変換する処理であり、自動設計に対応する配置配線プログラムなどが使用される。レイアウト設計部１８における配置処理部２４は、論理回路やトランジスタ回路のようなトポロジカルな情報から、実際の物理的な寸法を持つトランジスタやセルなどの素子の形と、それを配置する場所を決定する。
【００２７】
レイアウト設計部１８に設けた配線処理部２６は、配置処理部２４によって配置された素子間の結線を、設計ルールや各種の制約条件を満足するように決定する。配線手法としてはグローバル配線と詳細配線の２段階に分ける方法が通常使用される。本発明は、このうちの詳細配線について適用される。
【００２８】
詳細配線は各ネットの実際の配線を行うもので、２点間もしくは多点間のネットを１本ずつ順番に最短距離で配線する。配線アルゴリズムとしては、迷路法、線分探索法、チャネル配線法などが使用される。
【００２９】
設計検証部２０は、設計されたレイアウトについて、設計寸法の規則違反を調べるデザインルールチェック（ＤＲＣ）、レイアウトから回路結線情報を作り出す回路抽出、結線誤りを調べる結線チェック、トランジスタの寸法要求特性や電源配線短絡の有無などを調べる電気的ルールチェックなどがある。この設計検証が終了するとマスクデータが作成され、ＬＳＩ製造部２２に引き渡されて、ＬＳＩの製造が行われることになる。
【００３０】
図３は本発明による配線装置の機能構成のブロック図である。図３において、本発明の配線装置３０に対してはネットリスト３２が設けられ、ネットリスト３２には図２に示したように回路設計部１６で設計の済んだネットリスト情報が格納されている。
【００３１】
また配線装置３０に対してはパラメータファイル３４が設けられる。パラメータファイル３４には、後の説明で明らかにする本発明の配線処理における配線領域拡大のために使用する拡張関数としてのパラメータが予め格納されている。
【００３２】
配線装置３０は、一般ネット抽出部３６、クリップネット抽出部３８、配線領域設定部４０、配線決定部４２及び配線領域拡大部４４の機能ブロックで構成されている。配線装置３０で処理の済んだレイアウト設計データは、設計検証が済んだ後にマスクパターンデータ４６として出力される。
【００３３】
配線装置３０に設けた一般ネット抽出部３６は、ネットリスト３２からクリップネットを除く配線ネットを選択して配線領域設定部４０に出力する。クリップネット抽出部３８は、ネットリスト３２からクリップ端子を含むセルを検索して配線領域設定部４０に出力する。
【００３４】
配線領域設定部４０、配線決定部４２及び配線領域拡大部４４は、一般ネットとクリップネットに分けて配線処理を実行する。一般ネットの場合、配線領域設定部４０はネットを構成する端子の集合を含む最大矩形を配線領域として設定する。配線決定部４２は、配線領域設定部４０で設定された配線領域を対象に、最短距離となるネット間の配線を決定する。このネット間の配線決定については、２点間の配線経路の決定には迷路法または線分探索法が使用され、一方、多点間の配線経路の決定についてはチャネル配線法が例えば使用される。
【００３５】
配線領域拡大部４４は、配線決定部４２による配線処理の結果について、バイオレーション（規則違反）や未結線端子が存在した場合、現在の配線領域をパラメータファイル３４に格納したパラメータに従って拡大した後に、配線決定部４２で配線を決定させる処理を行わせる。
【００３６】
配線領域拡大部４４による配線領域の拡大は、パラメータファイル３４に設定しているパラメータの範囲で配線が成功するまで繰り返し行われる。パラメータファイル３４に格納されている配線領域を拡大するために使用するパラメータとしては、拡大率（パーセント）、グリット数、増加寸法（μｍ）などを使用している。
【００３７】
また配線決定部４２で配線結果の判定に使用するバイオレーション（規則違反）としては
（１）スペーシングルール
（２）クロスルール
の２つを基本としている。
【００３８】
次にクリップネットの場合を説明する。クリップネットは、ＬＳＩチップに配置したセルについて、セルが同一の機能を持つ複数の入力端子を持つ場合に、そのうちのいずれか１つを選択して使用した場合、未使用となっている残りの入力端子をクリップ端子とし、このクリップ端子をセル内の電源端子に配線する配線処理を行う。
【００３９】
例えば、あるセルにつき同一の入力機能を備えた３つの入力端子があり、それぞれの入力容量が例えば４０ｐＦ、６０ｐＦ、８０ｐＦと異なっているような場合に、例えば４０ｐＦの入力端子を使用し、残り６０ｐＦと８０ｐＦの入力端子はクリップ端子として電源端子に接続してグランドに落とすような場合である。
【００４０】
このようなクリップネットを対象とした配線処理の場合、配線領域設定部４０はクリップネット抽出部３８で抽出したクリップ端子を含むセルの領域を配線領域に設定し、配線決定部４２は配線領域として設定されたセル領域を対象に、最短距離となるようにクリップ端子と電源端子の間の配線を決定する。
【００４１】
これによってクリップネットについては、セル内に禁止領域が存在しない限り、原則としてセル内部の配線に抑え込むことができる。配線領域拡大部４４は、配線決定部４２による配線結果について、スペーシングとクロッシングのバイオレーションチェック（違反チェック）及び未結線のクリップ端子の有無を判別し、バイオレーション又は未結線のクリップ端子を発見した場合、現在のセル領域について設定した配線領域をパラメータファイル３４に設定したパラメータに従って拡大した後に、配線決定部４２で再度配線を行って、クリップネットの配線を決定させる。
【００４２】
図３における配線装置３０は、例えば図４のようなコンピュータのハードウェア資源により実現される。図４のコンピュータにおいて、ＣＰＵ１１０のバス１１１にはＲＡＭ１１２、ハードディスクコントローラ（ソフト）１１４、フロッピィディスクドライバ（ソフト）１２０、ＣＤ−ＲＯＭドライバ（ソフト）１２４、マウスコントローラ１２８、キーボードコントローラ１３２、ディスプレイコントローラ１３６、通信用ボード１４０が接続される。
【００４３】
ハードディスクコントローラ１１４はハードディスクドライブ１１６を接続し、本発明の配線処理を実行するプログラムをローディングしており、コンピュータの起動時にハードディスクドライブ１１６から必要なプログラムを呼び出して、ＲＡＭ１１２上に展開し、ＣＰＵ１１０により実行する。
【００４４】
フロッピィディスクドライバ１２０にはフロッピィディスクドライブ（ハード）１２２が接続され、フロッピィディスク（Ｒ）１２２に対する読み書きができる。ＣＤ−ＲＯＭドライバ１２４に対しては、ＣＤドライブ（ハード）１２６が接続され、ＣＤに記憶されたデータやプログラムを読み込むことができる。
【００４５】
マウスコントローラ１２８はマウス１３０の入力操作をＣＰＵ１１０に伝える。キーボードコントローラ１３２はキーボード１３４の入力操作をＣＰＵ１１０に伝える。ディスプレイコントローラ１３６は表示部１３８に対して表示を行う。通信用ボード１４０はＬＡＮ１４２を介してネットワーク内の装置や外部のインターネット上の装置との間で通信を行う。
【００４６】
図５は図３のパラメータファイルに格納されるパラメータ情報の説明図である。図５（Ａ）はネット名パラメータファイル４８であり、ネット名に対応して拡大関数として水平拡大と垂直拡大の各パラメータを設定している。ネット名にはディフォルトに続いてｎｅｔ１〜ｎｅｔ４のネット名が登録されている。
【００４７】
ディフォルトの水平拡大１０パーセント、垂直拡大２０パーセントであり、ネット名ｎｅｔ１〜ｎｅｔ４以外の一般ネットに適用される。ネット名ｎｅｔ１、ｎｅｔ２については、水平拡大及び垂直拡大はパーセント表示となっている。またネット名ｎｅｔ３についてはレイアウト設計における格子グリッドを単位として、水平拡大が５ｇｒｉｄ、垂直拡大が２０ｇｒｉｄとして、グリッド数で領域拡大量を定義している。更にネット名ｎｅｔ４については、水平拡大が５μｍ、垂直拡大が１０μｍと、チップ上における領域の増加寸法が定義されている。
【００４８】
ここでネット名パラメータファイル４８にあっては、水平拡大と垂直拡大の度合を異なった値としているが、同じ値としてもよい。また配線領域の拡大を許容できないネットについては、水平拡大及び垂直拡大について、それぞれの拡大関数をゼロとすることもできる。この拡大関数をゼロとする設定は、水平拡大と垂直拡大のいずれか一方の拡大関数をゼロとする場合を含む。
【００４９】
図５（Ｂ）はネット種別パラメータファイル５０であり、ネット種別に応じて配線領域の水平拡大と垂直拡大の拡大関数を設定したことを特徴とする。このネット種別パラメータファイル５０についても、ディフォルトはネット種別Ｋｉｎｄ１〜Ｋｉｎｄ４以外のネットに適用される。また水平拡大及び垂直拡大の拡大関数としては、パーセント、グリッド数及び増加寸法（μｍ）のいずれかとする。またネット種別としては、電気的条件の厳しいクロックネットと電気的条件の緩やかなスキャンネットなどに分類する。
【００５０】
図５（Ｃ）は配線層パラメータファイル５２の説明図であり、配線層に分けて配線領域の水平拡大と垂直拡大の拡大関数となるパラメータを設定している。配線層としてはデフォルト、ＭＥＴ１〜ＭＥＴ４があり、配線層ＭＥＴ１〜ＭＥＴ４以外の配線層についてはデフォルトのパラメータが使用される。水平拡大と垂直拡大の拡大関数のパラメータは、パーセント、グリッド数及び増加寸法（μｍ）のいずれかとする。
【００５１】
図５（Ｄ）は、クリップネット用パラメータファイル５４の説明図である。図５（Ａ）〜（Ｃ）は一般ネットを対象とした配線領域の拡大に使用するパラメータファイルであるが、図５（Ｄ）はクリップ端子を電源端子に接続するクリップネットの配線領域の拡大に使用され、セル名に対応して水平拡大と垂直拡大の増加関数が拡大率（パーセント）で設定されている。
【００５２】
図６は本発明による一般ネットを対象とした配線処理の説明図である。図６（Ａ）は１回目の配線処理であり、ネットリスト３２から選択されたネットに基づいて、チップ５６に配置された複数の端子６０−１〜６０−６を対象に配線処理を行う場合、まず端子６０−１〜６０−６の集合を含む最大矩形として配線領域６２を設定する。
【００５３】
この図６（Ａ）のように設定した配線領域６２を対象に配線処理を実行し、図６（Ｂ）のように配線６４を決定し、端子６０−１〜６０−６を結ぶ配線６４を配線領域６２の内部に収めている。
【００５４】
これに対し従来のチップ５６の全体を配線領域とした配線処理にあっては、例えば端子６０−１、６０−２、６０−３の部分のように、配線領域内がある程度混雑している場合には、チャネルの空きを求めて、自分のネット内端子矩形領域以外のエリアに、図６（Ｂ）の従来配線６１に示すように迂回して配線を行っている。
【００５５】
これに対し本発明にあっては、端子の集合に対し設定した最大矩形となる配線領域６２内に配線６４が収まることで、迂回配線の発生を最小限に抑えることができる。また配線処理はチップ５６全体ではなく、配線領域６２というチップ５６の一部分の領域について処理を実行するだけでよいことから、配線処理に要する処理負担が低減し、処理時間を短縮することができる。
【００５６】
図７はネット内に配線禁止領域がある場合の本発明による配線処理の説明図である。図７（Ａ）は１回目の配線処理であり、チップ５６に展開したネット内に配線禁止領域６６が存在しており、この場合についても、まず端子６０−１〜６０−６の集合を含む最大矩形となる配線領域６２−１を設定し、配線処理を行って配線６４−１を決定する。
【００５７】
しかしながら、配線結果を見ると、配線禁止領域６６の存在により端子６０−１が未結線となっている。そこで本発明にあっては、図７（Ｂ）に示すように、図７（Ａ）の配線領域６２−１を、外部のパラメータファイル３４から得られた拡大関数に従って図７（Ｂ）の配線領域６２−２のように拡大した後、再度、配線処理を実行し、配線禁止領域６６を迂回して端子６０−１と端子６０−２を結ぶ配線６４−２を決定し、配線処理を終了する。
【００５８】
図８は特殊なケースとして直線上に並んだ端子を対象とした本発明による配線処理の説明図である。図８（Ａ）のチップ５６にあっては、既に配線処理の済んだ既配線６８の両側に端子７０−１、７０−２が配置されており、端子７０−１、７０−２は直線上に並んでいる。このような場合についても、端子７０−１、７０−２について最大矩形となる配線領域７２−１を設定すると、この場合には配線領域７２−１は矩形領域とはならず、直線となってしまう。
【００５９】
このように直線となる配線領域７２−１については配線できない可能性があることから、図８（Ｂ）の配線領域７２−２のように矩形の配線領域に拡大した後に配線処理を行うことで、既配線６８を迂回して端子７０−１、７０−２を結ぶ配線７４を決定することができる。
【００６０】
次に本発明による配線処理を、配線アルゴリズムである迷路法に適用した場合について、具体的に説明する。
【００６１】
図９は従来の迷路法による配線処理の説明図である。迷路法は、配線するチップ７６の平面を配線幅と線間間隔の和を中心点間の距離とする正方格子で区切り、格子の中心点間を結ぶ経路を見つけ出す。図９にあっては、出発端子Ａと目標端子Ｂの配線経路を求める場合を例にとっている。
【００６２】
まず出発端子Ａを中心に、上下左右の４箇所のマスに「１」とラベルを付ける。次に「２」の左右上下の空いているマス目にラベル「２」を入れる。以下同様にして、波紋が伝わるように順番に数字の大きなラベルが付されたマス目を形成している。このようにしてラベルの数字が目標端子Ｂに到達したならば、目標端子Ｂよりラベルの数字を降順に辿って、矢印で示すように出発端子Ａに至る最短経路を見つけ出す。
【００６３】
図１０は本発明を適用した迷路法による配線処理の説明図である。図１０（Ａ）にあっては、チップ７６について配置した出発端子Ａと目標端子Ｂに対し、最大矩形となる配線領域８０−１を設定する。この配線領域８０−１について、出発端子Ａを中心に領域内の上下左右にラベル「１」を付し、次にラベル「１」に対し領域内で上下左右となる位置にラベル「２」を付す。以下同様にこれを繰り返す。
【００６４】
しかしながら、この場合には配線領域８０−１内で数字が目標端子Ｂに到達せず、配線が失敗となる。そこで図１０（Ｂ）のように、配線領域８０−１を外部のパラメータファイル３４のパラメータに従って配線領域８０−２のように拡大した後、同様にしてラベルの数字を増加させる処理を繰り返すと、最終的に目標端子Ｂに数字が到達する。そして、目標端子Ｂからラベルの数字を降順に辿って目標端子Ａに至る配線経路を矢印のように見つけ出す。
【００６５】
この図１０における本発明を適用した迷路法による配線処理にあっては、チップ７６に対し設定した配線領域８０−１、８０−２の範囲内で迷路法によるラベル数字付けを行っており、図９の従来例に比べ、数字を設定する領域が制約されており、その分、探索処理に要する処理負担を低減し、高速で配線処理を行うことができる。
【００６６】
図１１は従来の線分探索法による配線処理と、本発明を適用した線分探索法による配線処理の説明図である。図１１（Ａ）は従来の線分探索法による配線処理であり、チップ８０に配置した出発端子８２と目標端子８４について、それぞれより水平及び垂直の４方向に配線禁止領域８５または外枠にぶつかるまで、試行線を延ばす。
【００６７】
即ち、出発端子８２からは水平試行線８２−１と垂直試行線８２−２を延ばし、また目標端子８４からは水平試行線８４−１と垂直試行線８４−２を延ばす。続いて、出発端子８２に対し配線間隔で交点を例えば上方に移動しながら水平試行線を設定し、配線禁止領域８５を回避する交点８６を持つ水平試行線８６−１を設定する。
【００６８】
また目標端子８４については、配線間隔で交点を水平試行線８４−１に沿って水平方向に移動し、配線禁止領域８５を外れる交点９０を持つ垂直試行線９０−２を設定する。そして目標端子８２側から順次設定した水平試行線８６−１と目標端子８４側から出発した垂直試行線９０−２の交点８８が得られることで、出発端子８２と目標端子８４を結ぶ配線経路を決定する。
【００６９】
図１１（Ｂ）は本発明を適用した線分探索法による配線処理の説明図であり、出発端子８２と目標端子８４について、最大矩形となる配線領域９２−１が１回目に設定され、この場合には配線は失敗することから、パラメータファイル３４のパラメータに従って拡大した配線領域９２−２を設定し、この場合にも線分探索法による配線は失敗することから、更に拡大した配線領域９２−３を設定し、この場合には線分探索法による配線経路を設定することができる。
【００７０】
このような線分探索法についても、図１１（Ａ）がチップ８０全体を対象に水平及び垂直の各試行線を設定して交点を求めているのに対し、図１１（Ｂ）の本発明による配線処理にあっては、配線領域９２−１、９２−２、９２−３のように制限された領域内で線分探索法による試行線の設定と交点の探索が行われることで、線分探索法の処理負担を低減し、探索処理を短時間で行うことができる。
【００７１】
なお複数の端子間の配線経路を決定するチャネル配線法についても、従来はセル全体を対象としているが、本発明にあっては、端子の集合に対し最大矩形となる配線領域を設定し、これにつきチャネル配線法による配線が不成功となった場合には、パラメータにより配線領域を拡大して処理を行うことで配線領域を制約して、処理負担を低減し、処理時間を短縮することができる。この点は、それ以外の適宜の配線処理のアルゴリズムにつき同様である。
【００７２】
図１２は一般ネットを対象にした本発明による配線処理のフローチャートである。図１２において、ステップＳ１でネットリスト３２から配線ネットを選択し、ステップＳ２でネットを構成する端子集合を含む最大矩形について配線領域を設定し、ステップＳ３に進んで設定した配線領域を対象に配線処理を実行する。
【００７３】
続いて、ステップＳ４でスペーシングルールまたはクロッシングルールに違反しているか否かのバイオレーションチェックまたは未結線の端子があるか否かチェックし、もしルール違反や未結線の端子があった場合にはステップＳ６に進み、パラメータファイル３４からパラメータとして例えば拡大率（％）を取得し、現在の配線領域を拡大する処理を行った後、ステップＳ３で拡大した配線領域を対象に配線処理を実行する。
【００７４】
このステップＳ６による配線領域の拡大は、ステップＳ４でルール違反または未結線端子がなくなるまで繰り返し行われる。もちろん配線領域の拡大率の上限を設け、上限に達した場合には配線エラーとして処理を終了することになる。ステップＳ４でルール違反及び未結線の端子がなかった場合には、ステップＳ５に進み、全てのネットを配線したか否かチェックし、未処理の場合にはステップＳ１からの処理を繰り返し、全てのネットの配線を確認すると処理を終了する。
【００７５】
図１３は従来のクリップネットの配線処理と本発明を適用したクリップネットの配線処理の説明図である。図１３（Ａ）は従来のクリップネットの配線処理であり、チップ９４上に例えば３つのセル９６−１〜９６−３が配置されており、セル９６−１〜９６−３のそれぞれはクリップ端子９８−１〜９８−３と電源端子１００−１〜１００−３を設けている。
【００７６】
このようなクリップ端子９８−１〜９８−３を対象に、電源端子１００−１〜１００−３側と結線する従来の配線処理は、チップ９４の全体を配線領域として配線処理を実行するため、クリップ端子９８−１〜９８−３を相互に結線した後にセル９６−３の電源端子１００−３に接続するクリップ配線１０２を決定する。
【００７７】
図１３（Ｂ）は本発明によるクリップネットの配線処理であり、本発明にあっては、例えばセル９６−１について示すように、セル領域を配線領域１０４に設定して配線処理を実行する。このためセル９６−１のクリップ端子９８−１は、同じセル内の電源端子１００−１に結線されるクリップ配線１０６−１を決定することになる。この点は他のセル９６−２、９６−３についても同様である。
【００７８】
その結果、本発明のクリップ配線処理にあっては、セル内に配線禁止領域が存在しない限り、セルのクリップ端子は同じセルの電源端子に結線されるクリップネットが構成され、図１３（Ａ）のようにクリップ配線１０２がセルの外部に配線されることで、他の配線経路を決定するための配線領域を制約することがなくなる。また配線領域は原則としてセル内に抑えられることから、配線処理の負担も小さく、処理時間を短縮できる。
【００７９】
図１４は配線禁止領域がある場合の本発明によるクリップネットの配線処理の説明図である。図１４（Ａ）は１回目の配線処理であり、セル９６−１に対し配線禁止領域１０８が設定されている。この場合、セル９６−１について、１回目の配線領域は、セル領域につき配線領域１０４−１のように設定される。なお説明を分かりやすくするため、セル９６−１の外側に配線領域１０４−１を示しているが、実際には両者は重なっている。
【００８０】
この配線領域１０４−１の設定による配線処理を実行すると、クリップ端子９８−１から電源端子１００−１を結ぶクリップ配線１０６−１が結線されるが、これは禁止領域１０８を通ることからバイオレーションチェックにより違反となり、配線は不成功となる。
【００８１】
そこで図１４（Ｂ）のように、配線領域１０４−１を拡大して配線領域１０４−２を設定し、配線領域１０４−２を対象に配線処理を実行する。この場合、配線領域１０４−２には隣接するセル９６−２の電源端子１００−２の一部も含まれることから、セル９６−１のクリップ端子９８−１から隣接するセル９６−２の電源端子１００−２に至る最短経路となるクリップ配線１０６−３が決定される。
【００８２】
図１５はクリップネットを対象とした本発明による配線処理のフローチャートである。図１５において、ステップＳ１でネットリスト３２からクリップ端子を検索し、ステップＳ２でクリップ端子の属するセルを検索し、更にステップＳ３で検索したセルに属する全てのクリップ端子を検索する。続いてステップＳ４でセル枠の領域を配線領域に設定し、ステップＳ５でクリップ配線を実行する。
【００８３】
続いてステップＳ６でクリップ配線をチェックし、ステップＳ７でスペーシングルールまたはクロッシングルールのルール違反または未結線のクリップ端子があるか否かチェックし、もしルール違反または未結線のクリップ端子があった場合には、ステップＳ８でルール違反または未結線のクリップ端子の配線を削除した後、ステップＳ９でパラメータファイル３４に基づいて配線領域を拡大した後、ステップＳ５に戻ってクリップ配線を実行し、ステップＳ７でルール違反または未結線のクリップ端子がなくなるまで、ステップＳ５〜Ｓ９の処理を繰り返す。
【００８４】
ステップＳ７で配線に成功すると、ステップＳ１０で全てのクリップ端子を配線したか否かチェックし、クリップ端子の未配線が残っている場合には、ステップＳ１に戻って同様な処理を繰り返し、ステップＳ１０で全てのクリップ端子の配線終了を判別した場合には処理を終了する。
【００８５】
なお本発明は上記の実施形態に限定されず、その目的と利点を損なうことのない適宜の変形を含み、更に上記の実施形態に示した数値による限定は受けない。
ここで本発明の特徴を列挙すると次の付記のようになる。
【００８６】
（付記）
（付記１）
半導体回路につき１ネット単位に配線を決定する配線方法に於いて、
ネットを構成する端子の集合を含む最大矩形を配線領域に設定する配線領域設定ステップと、
前記配線領域を対象に最短距離となるネット間の配線を決定する配線決定ステップと、
前記配線決定ステップで未結線端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に前記配線決定ステップで配線を決定させる配線領域拡大ステップと、
を備えたことを特徴とする配線方法。（１）
【００８７】
（付記２）
半導体回路に配置したセルの同一機能をもつ複数の入力端子の１つを使用した場合の未使用の入力端子をクリップ端子として電源端子に配線するクリップネットの配線方法に於いて、
前記セル領域を配線領域に設定する配線領域設定ステップと、
前記配線領域を対象に最短距離となるクリップ端子と電源端子との間の配線を決定する配線決定ステップと、
前記配線決定ステップで未結線のクリップ端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に前記配線決定ステップで配線を決定させる配線領域拡大ステップと、
を備えたことを特徴とする配線方法。（２）
【００８８】
（付記３）
付記１又は２記載の配線方法に於いて、前記配線領域拡大ステップで使用する前記パラメータは、全てのネットを対象とするデフォルトの拡大関数を含むことを特徴とする配線方法。
【００８９】
（付記４）
付記１又は２記載の配線方法に於いて、前記配線領域拡大ステップで使用する前記パラメータは、ネットの種別に応じて異なる拡大関数を含むことを特徴とする配線方法。
【００９０】
（付記５）
付記４記載の配線方法に於いて、前記配線領域拡大ステップで使用する前記パラメータは、特定のネットについて拡大関数をゼロとしたことを特徴とする配線方法。
【００９１】
（付記６）
付記１又は２記載の配線方法に於いて、前記配線領域拡大ステップで使用する前記パラメータは、配線層に応じて異なる拡大関数を含むことを特徴とする配線方法。
【００９２】
（付記７）
付記１又は２記載の配線方法に於いて、前記配線領域拡大ステップで使用する前記パラメータの拡大関数は、拡大率、グリット数又は増加寸法であることを特徴とする配線方法。
【００９３】
（付記８）（拡大パラメータの水平垂直）
付記１又は２記載の配線方法に於いて、前記配線領域拡大ステップで使用する前記パラメータは、矩形配線領域の水平方向と垂直方向の両方又は何れか一方の拡大関数であることを特徴とする配線方法。
【００９４】
（付記９）
コンピュータに、
ネットを構成する端子の集合を含む最大矩形を配線領域に設定する配線領域設定ステップと、
前記配線領域を対象に最短距離となるネット間の配線を決定する配線決定ステップと、
前記配線決定ステップで未結線端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に前記配線決定ステップで配線を決定させる配線領域拡大ステップと、
を実行させることを特徴とするプログラム。（３）
【００９５】
（付記１０）
コンピュータに、
同一機能もつ複数の入力端子の１つを使用した場合の未使用の入力端子となるクリップ端子と電源端子を備えたセル領域を配線領域に設定する配線領域設定ステップと、
前記配線領域を対象に最短距離となるクリップ端子と電源端子との間の配線を決定する配線決定ステップと、
前記配線決定ステップで未結線のクリップ端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に前記配線決定ステップで配線を決定させる配線領域拡大ステップと、
を備えたことを特徴とするプログラム。（４）
【００９６】
（付記１１）
付記９又は１０記載のプログラムに於いて、前記配線領域拡大ステップで使用する前記パラメータは、全てのネットを対象とするデフォルトの拡大関数を含むことを特徴とするプログラム。
【００９７】
（付記１２）
付記９又は１０記載のプログラムに於いて、前記配線領域拡大ステップで使用する前記パラメータは、ネットの種別に応じて異なる拡大関数を含むことを特徴とするプログラム。
【００９８】
（付記１３）
付記１２記載のプログラムに於いて、前記配線領域拡大ステップで使用する前記パラメータは、特定のネットについて拡大関数をゼロとしたことを特徴とするプログラム。
【００９９】
（付記１４）
付記９又は１０記載のプログラムに於いて、前記配線領域拡大ステップで使用する前記パラメータは、配線層に応じて異なる拡大関数を含むことを特徴とするプログラム。
【０１００】
（付記１５）
付記９又は１０記載のプログラムに於いて、前記配線領域拡大ステップで使用する前記パラメータの拡大関数は、拡大率、グリット数又は増加寸法であることを特徴とするプログラム。
【０１０１】
（付記１６）
付記９又は１０記載のプログラムに於いて、前記配線領域拡大ステップで使用する前記パラメータは、矩形配線領域の水平方向と垂直方向の両方又は何れか一方の拡大関数であることを特徴とするプログラム。
【０１０２】
（付記１７）
半導体回路につき１ネット単位に配線を決定する配線装置に於いて、
ネットを構成する端子の集合を含む最大矩形を配線領域に設定する配線領域設定部と、
前記配線領域を対象に最短距離となるネット間の配線を決定する配線決定部と、
前記配線決定部で未結線端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に前記配線決定部で配線を決定させる配線領域拡大部と、
を備えたことを特徴とする配線装置。（５）
【０１０３】
（付記１８）
半導体回路に配置したセルの同一機能もつ複数の入力端子の１つを使用した場合の未使用の入力端子をクリップ端子として電源端子に配線するクリップネットの配線装置に於いて、
前記セル領域を配線領域に設定する配線領域設定部と、
前記配線領域を対象に最短距離となるクリップ端子と電源端子との間の配線を決定する配線決定部と、
前記配線決定部で未結線のクリップ端子又は規則違反が存在した場合、現在の配線領域を予め設定したパラメータに従って拡大した後に前記配線決定部で配線を決定させる配線領域拡大部と、
を備えたことを特徴とする配線装置。
【０１０４】
（付記１９）
付記１７又は１８記載の配線装置に於いて、前記配線領域拡大部で使用する前記パラメータは、全てのネットを対象とするデフォルトの拡大関数を含むことを特徴とする配線装置。
【０１０５】
（付記２０）
付記１７又は１８記載の配線装置に於いて、前記配線領域拡大部で使用する前記パラメータは、ネットの種別に応じて異なる拡大関数を含むことを特徴とする配線装置。
【０１０６】
（付記２１）
付記２０記載の配線装置に於いて、前記配線領域拡大部で使用する前記パラメータは、特定のネットについて拡大関数をゼロとしたことを特徴とする配線装置。
【０１０７】
（付記２２））
付記１７又は１８記載の配線装置に於いて、前記配線領域拡大部で使用する前記パラメータは、配線層に応じて異なる拡大関数を含むことを特徴とする配線装置。
【０１０８】
（付記２３）
付記１７又は１８記載の配線装置に於いて、前記配線領域拡大部で使用する前記パラメータの拡大関数は、拡大率、グリット数又は増加寸法であることを特徴とする配線装置。
【０１０９】
（付記２４）
付記１７又は１８記載の配線装置に於いて、前記配線領域拡大部で使用する前記パラメータは、矩形配線領域の水平方向と垂直方向の両方又は何れか一方の拡大関数であることを特徴とする配線装置。
【図面の簡単な説明】
【０１１０】
【図１】本発明の原理説明図
【図２】ＬＳＩ設計システムの全体構成のブロック図
【図３】本発明による配線装置の機能構成のブロック図
【図４】図３の配線装置が適用されるコンピュータのハードウェア環境の説明図
【図５】図３のパラメータファイルの説明図
【図６】本発明による一般ネットを対象とした配線処理の説明図
【図７】配線禁止領域がある場合の本発明による配線処理の説明図
【図８】直線上に並んだ端子を対象とした本発明による配線処理の説明図
【図９】従来の迷路法による配線処理の説明図
【図１０】本発明を適用した迷路法による配線処理の説明図
【図１１】従来の線分探索法による配線処理と本発明を適用した線分探索法による配線処理の説明図
【図１２】一般ネットを対象とした本発明による配線処理のフローチャート
【図１３】従来のクリップネットの配線処理と本発明を適用したクリップネットの配線処理の説明図
【図１４】配線禁止領域がある場合の本発明によるクリップネットの配線処理の説明図
【図１５】クリップネットを対象とした本発明による配線処理のフローチャート
【符号の説明】
【０１１１】
１０：システム仕様設計部
１２：機能設計部
１４：論理設計部
１６：回路設計部
１８：レイアウト設計部
２０：設計検証部
２２：ＬＳＩ製造部
２４：配置処理部
２６：配線処理部
３０：配線装置
３２：ネットリスト
３４：パラメータファイル
３６：一般ネット抽出部
３８：クリップネット抽出部
４０：配線領域設定部
４２：配線決定部
４４：配線領域拡大部
４６：マスクパターンデータ
４８：ネット名パラメータファイル
５０：ネット種別パラメータファイル
５２：配線層パラメータファイル
５４：クリップネット用パラメータファイル
５６、７６、８０、９４：チップ
６０−１〜６０−６、７０−１、７０−２：端子
６２、６２−１、６２−２、７２−１、７４、８０−１、８０−２、９２−１〜９２−３、１０４：配線領域
６４、７４：配線
６６、７８、８５、９０−１〜９０−３、１０８：配線禁止領域
６８：既配線
７６：グリットチップ
８２：出発端子
８２−１、８４−１、８６−１：水平試行線
８２−２、８４−２、９０−２：垂直試行線
８４：目標端子
８６、８８、９０：交点
９６−１〜９６−３：セル
９８−１〜９８−３：クリップ端子
１００−１〜１００−３：電源端子
１０２、１０６−１〜１０６−３：クリップ配線
【図１】
2006155118.tif 000003
【図２】
2006155118.tif 000004
【図３】
2006155118.tif 000005
【図４】
2006155118.tif 000006
【図５】
2006155118.tif 000007
【図６】
2006155118.tif 000008
【図７】
2006155118.tif 000009
【図８】
2006155118.tif 000010
【図９】
2006155118.tif 000011
【図１０】
2006155118.tif 000012
【図１１】
2006155118.tif 000013
【図１２】
2006155118.tif 000014
【図１３】
2006155118.tif 000015
【図１４】
2006155118.tif 000016
【図１５】
2006155118.tif 000017