(57)【特許請求の範囲】
【請求項１】
設計対象回路内の接続関係を有する一対の部品ごとに、当該部品間をつなぐネットのうち同一配線層に配線すべきネットをグループ化したネットグループ固有の始点／終点座標および配線幅を記憶する記憶手段にアクセス可能なコンピュータを、
前記記憶手段にアクセスして、前記設計対象回路の配線領域内の前記始点座標から前記終点座標に辿り着くまでの前記配線幅の配線経路を前記ネットグループごとに探索する探索手段、
前記探索手段によって探索された配線経路間で相互に交差関係を有するネットグループの組み合わせを検出する検出手段、
前記設計対象回路内の接続関係を有する一対の部品ごとのネットグループがノード化され、前記検出手段によって検出された交差関係を有するネットグループの組み合わせのノード間をつなぐ無向グラフを作成する作成手段、
前記作成手段によって作成された無向グラフの彩色問題を解くことにより、当該無向グラフ内の直接接続されたノード間で配線層が異なるように、前記設計対象回路が有する複数の配線層の中から前記各ネットグループに割り当てる配線層を決定する決定手段、
前記決定手段によって決定された決定結果を出力する出力手段、
として機能させることを特徴とする設計支援プログラム。
【請求項２】
前記探索手段は、
前記配線領域内の配線禁止領域を除く残余の配線領域を配線可能領域として、前記始点座標から前記終点座標に辿り着くまでの配線経路を探索することを特徴とする請求項１に記載の設計支援プログラム。
【請求項３】
前記探索手段は、
前記検出手段によって第１および第２のネットグループの組み合わせが検出された場合、前記第２のネットグループの配線経路を配線禁止領域として、前記第１のネットグループの配線経路を再探索することを特徴とする請求項２に記載の設計支援プログラム。
【請求項４】
前記探索手段は、
前記検出手段によって第１および第２のネットグループの組み合わせが検出された場合、前記第１のネットグループから分割された第３および第４のネットグループ固有の配線幅に基づいて、前記第１のネットグループ固有の始点座標と終点座標とをつなぐ前記第３および第４のネットグループの配線経路を探索することを特徴とする請求項２または３に記載の設計支援プログラム。
【請求項５】
設計対象回路内の接続関係を有する一対の部品ごとに、当該部品間をつなぐネットのうち同一配線層に配線すべきネットをグループ化したネットグループ固有の始点／終点座標および配線幅を記憶する記憶手段と、
前記記憶手段にアクセスして、前記設計対象回路の配線領域内の前記始点座標から前記終点座標に辿り着くまでの前記配線幅の配線経路を前記ネットグループごとに探索する探索手段と、
前記探索手段によって探索された配線経路間で相互に交差関係を有するネットグループの組み合わせを検出する検出手段と、
前記設計対象回路内の接続関係を有する一対の部品ごとのネットグループがノード化され、前記検出手段によって検出された交差関係を有するネットグループの組み合わせのノード間をつなぐ無向グラフを作成する作成手段と、
前記作成手段によって作成された無向グラフの彩色問題を解くことにより、当該無向グラフ内の直接接続されたノード間で配線層が異なるように、前記設計対象回路が有する複数の配線層の中から前記各ネットグループに割り当てる配線層を決定する決定手段と、
前記決定手段によって決定された決定結果を出力する出力手段と、
を備えることを特徴とする設計支援装置。
【請求項６】
制御手段および記憶手段を備え、設計対象回路内の接続関係を有する一対の部品ごとに、当該部品間をつなぐネットのうち同一配線層に配線すべきネットをグループ化したネットグループ固有の始点／終点座標および配線幅を記憶するテーブルにアクセス可能なコンピュータが、
前記制御手段により、前記テーブルにアクセスして、前記設計対象回路の配線領域内の前記始点座標から前記終点座標に辿り着くまでの前記配線幅の配線経路を前記ネットグループごとに探索する探索工程と、
前記制御手段により、前記探索工程によって探索された配線経路間で相互に交差関係を有するネットグループの組み合わせを検出する検出工程と、
前記制御手段により、前記設計対象回路内の接続関係を有する一対の部品ごとのネットグループがノード化され、前記検出工程によって検出された交差関係を有するネットグループの組み合わせのノード間をつなぐ無向グラフを作成する作成工程と、
前記制御手段により、前記作成工程によって作成された無向グラフの彩色問題を解くことにより、当該無向グラフ内の直接接続されたノード間で配線層が異なるように、前記設計対象回路が有する複数の配線層の中から前記各ネットグループに割り当てる配線層を決定する決定工程と、
前記制御手段により、前記決定工程によって決定された決定結果を出力する出力工程と、
を実行することを特徴とする設計支援方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、プリント基板やＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ）の配線設計を支援する技術に関する。
【背景技術】
【０００２】
プリント基板やＬＳＩの配線設計では、仕様の回路特性を満たすための配線制約に従って配線をおこなう必要がある。従来において、配線設計にかかる設計者の作業負荷を低減するために、配線制約に従った配線の自動化を図る技術が開示されている（たとえば、下記特許文献１〜３参照。）。
【０００３】
また、近年では、プリント基板やＬＳＩの大規模化、高集積化にともなって、配線設計に必要となる配線層数が増加しており、製造コストが増大している。このため、より少ない配線層で仕様の回路特性を実現することは、製造コストの削減のために重要となっている。
【０００４】
【特許文献１】特開２０００−３３１０３８号公報
【特許文献２】特開平５−１４３６９２号公報
【特許文献３】特開平８−２６３５３９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した従来技術では、複雑化する配線制約に従って配線層の割り当てを自動化することは難しいため、人手による配線層の割り当てがおこなわれている。この結果、設計作業にかかる設計者の作業負担が増大し、ひいては設計期間の長期化を招くという問題があった。
【０００６】
さらに、膨大な数の配線を人手により配線層に割り当てることは、非常に煩雑な作業となるだけでなく、設計者の知識や経験も必要となるため、膨大な作業時間を費やしているにもかかわらず最適な結果を得ることができない場合があるという問題があった。
【０００７】
この発明は、上述した従来技術による問題点を解消するため、設計対象回路内の一対の部品間をつなぐネットのうち、同一配線層に配線すべきネットをグループ化したネットグループごとに自動でかつ最適な配線層割当をおこなうことにより、回路動作の信頼性向上および設計期間の短縮化を図ることを目的とする。
【課題を解決するための手段】
【０００８】
この開示技術は、設計対象回路内の接続関係を有する一対の部品ごとに、当該部品間をつなぐネットのうち同一配線層に配線すべきネットをグループ化したネットグループ固有の始点／終点座標および配線幅を記憶するテーブルにアクセスして、前記設計対象回路の配線領域内の前記始点座標から前記終点座標に辿り着くまでの前記配線幅の配線経路を前記ネットグループごとに探索し、探索された配線経路間で相互に交差関係を有するネットグループの組み合わせを検出し、検出された組み合わせのネットグループがそれぞれ異なる配線層に割り当てられるように、前記設計対象回路が有する複数の配線層の中から前記各ネットグループに割り当てる配線層を決定し、決定された決定結果を出力する。
【発明の効果】
【０００９】
この開示技術によれば、設計対象回路内の一対の部品間をつなぐネットのうち、同一配線層に配線すべきネットをグループ化したネットグループごとに自動でかつ最適な配線層割当をおこなうことにより、回路動作の信頼性向上および設計期間の短縮化を図ることができるという効果を奏する。
【発明を実施するための最良の形態】
【００１０】
以下に添付図面を参照して、この設計支援プログラム、設計支援装置、および設計支援方法の好適な実施の形態を詳細に説明する。この設計支援プログラム、設計支援装置、および設計支援方法では、設計対象回路内の一対の部品間をつなぐネットのうち、同一配線層に配線すべきネットをグループ化し、ネットグループごとに配線経路探索および配線層割当を自動化しておこなうことにより、設計期間の短縮化を図る。
【００１１】
（実施の形態の概要）
まず、本実施の形態の概要について説明する。ここでは最初に、設計対象回路内の部品間を接続する複数のネットをグループ化したネットグループについて説明する。図１は、ネットグループの一例を示す説明図である。図１において、接続関係を有する一対の部品１１０，１２０が示されている。部品１１０と部品１２０は、４本のネット１３０〜１６０によって接続されている。
【００１２】
ネット１３０〜１６０は、部品１１０の端子Ｔ１〜Ｔ４と、部品１２０の端子Ｔ５〜Ｔ８と、をそれぞれ接続する経路（パス）である。ここでは、ネット１３０〜１６０は、特性上の問題から、すべてを同一配線層で配線すべきパスであるとする。本実施の形態では、このような同一配線層に配線すべき複数のネット１３０〜１６０をグループ化してネットグループ１７０として扱う。
【００１３】
ネットグループ１７０の配線幅は、たとえば、各ネット１３０〜１６０の配線幅をＷとすると、これらネット１３０〜１６０の配線幅を足し合わせた４Ｗとなる。また、詳細は後述するが、ネットグループ１７０の始点座標Ａおよび終点座標Ｂは、各部品Ｐ１，Ｐ２が占める領域内の任意の座標位置に設定する。
【００１４】
従来において、設計対象回路内の部品間をつなぐ配線経路を、どの配線層に形成すべきかを決める場合、まず、部品間をつなぐ１本１本の配線経路を探索し、そのあと、人手により各配線経路に割り当てる配線層を決定していた。これでは、設計者の作業負担が膨大なものとなり、作業時間の増大化を招いてしまう。
【００１５】
そこで、本実施の形態では、同一配線層に配線すべきネット（たとえば、ネット１３０〜１６０）をグループ化し、そのネットグループ（たとえば、ネットグループ１７０）ごとに、配線経路の探索および配線層の割り当てを自動化する手法を提案する。これにより、配線設計にかかる作業負担の軽減化および作業時間の短縮化を図る。
【００１６】
（設計対象回路の一例）
つぎに、本実施の形態にかかる設計対象回路の配線領域について説明する。図２は、設計対象回路の配線領域の一例を示す説明図である。図２において、設計対象回路の配線領域２００が示されている。ここで、配線領域２００の配線格子サイズは、Ｘ軸方向に「０≦Ｘ≦Ｘmax」であり、Ｙ軸方向に「０≦Ｙ≦Ｙmax」である。
【００１７】
この配線領域２００上には、部品Ｐ１〜Ｐ６が配置されている。また、配線領域２１０において、符号Ｆ１〜Ｆ４は障害物が配置された配線禁止領域である。本実施の形態では、配線領域２００に配置された一対の部品（たとえば、部品Ｐ１と部品Ｐ５）をつなぐネットのうち同一配線層に配線すべきネットをグループ化してネットグループとして扱う。
【００１８】
なお、設計対象回路が有する複数の配線層のうち、各障害物が形成される配線層はそれぞれ決まっているが、ここではある配線層の配線領域内にすべての障害物が形成されている状況を設計対象回路の配線領域２００として説明する。
【００１９】
（設計支援装置のハードウェア構成）
つぎに、実施の形態にかかる設計支援装置のハードウェア構成について説明する。図３は、設計支援装置のハードウェア構成を示すブロック図である。図３において、設計支援装置３００は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）３０１と、ＲＯＭ（Ｒｅａｄ‐Ｏｎｌｙ  Ｍｅｍｏｒｙ）３０２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）３０３と、磁気ディスクドライブ３０４と、磁気ディスク３０５と、光ディスクドライブ３０６と、光ディスク３０７と、ディスプレイ３０８と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）３０９と、キーボード３１０と、マウス３１１と、スキャナ３１２と、プリンタ３１３と、を備えている。また、各構成部はバス３２０によってそれぞれ接続されている。
【００２０】
ここで、ＣＰＵ３０１は、設計支援装置３００の全体の制御を司る。ＲＯＭ３０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ３０３は、ＣＰＵ３０１のワークエリアとして使用される。磁気ディスクドライブ３０４は、ＣＰＵ３０１の制御にしたがって磁気ディスク３０５に対するデータのリード／ライトを制御する。磁気ディスク３０５は、磁気ディスクドライブ３０４の制御で書き込まれたデータを記憶する。
【００２１】
光ディスクドライブ３０６は、ＣＰＵ３０１の制御にしたがって光ディスク３０７に対するデータのリード／ライトを制御する。光ディスク３０７は、光ディスクドライブ３０６の制御で書き込まれたデータを記憶したり、光ディスク３０７に記憶されたデータをコンピュータに読み取らせたりする。
【００２２】
ディスプレイ３０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ３０８は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００２３】
インターフェース（以下、「Ｉ／Ｆ」と略する。）３０９は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク３１４に接続され、このネットワーク３１４を介して他の装置に接続される。そして、Ｉ／Ｆ３０９は、ネットワーク３１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ３０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００２４】
キーボード３１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス３１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００２５】
スキャナ３１２は、画像を光学的に読み取り、設計支援装置３００内に画像データを取り込む。なお、スキャナ３１２は、ＯＣＲ（Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅａｄｅｒ）機能を持たせてもよい。また、プリンタ３１３は、画像データや文書データを印刷する。プリンタ３１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。
【００２６】
（設計支援装置の機能的構成）
つぎに、設計支援装置３００の機能的構成について説明する。図４は、設計支援装置の機能的構成を示すブロック図である。図４において、設計支援装置３００は、取得部４０１と、探索部４０２と、検出部４０３と、作成部４０４と、決定部４０５と、出力部４０６と、判断部４０７と、を含む構成である。
【００２７】
この制御部となる機能（取得部４０１〜判断部４０７）は、具体的には、たとえば、図３に示したＲＯＭ３０２、ＲＡＭ３０３、磁気ディスク３０５、光ディスク３０７などの記憶領域に記憶されたプログラムをＣＰＵ３０１に実行させることにより、または、Ｉ／Ｆ３０９により、その機能を実現する。
【００２８】
また、各機能（取得部４０１〜判断部４０７）からの出力データは上記記憶領域に保持される。また、図４中矢印で示した接続先の機能は、接続元の機能からの出力データを記憶領域から読み込んで、当該機能に関するプログラムをＣＰＵ３０１に実行させるものとする。
【００２９】
まず、取得部４０１は、設計対象回路に関する回路情報を取得する機能を有する。回路情報とは、設計対象回路に関する配線領域情報と、設計対象回路内の接続関係を有する一対の部品ごとのネットグループに関するネットグループ情報とを含む電子データである。なお、取得された回路情報は、図３に示したＲＡＭ３０３、磁気ディスク３０５、光ディスク３０７などの記憶領域に記憶される。
【００３０】
この回路情報は、たとえば、図３に示したキーボード３１０やマウス３１１をユーザが操作することで設計支援装置３００に直接入力することとしてもよく、また、不図示の外部装置から取得することとしてもよい。さらに、設計支援装置３００が備える不図示のデータベースやライブラリからの抽出によって回路情報を取得することとしてもよい。
【００３１】
ここで、回路情報に含まれる配線領域情報およびネットグループ情報について説明する。まず、配線領域情報の具体例について説明する。図５および図６は、配線領域情報の具体例を示す説明図である。図５において、配線領域情報５００には、設計対象回路の配線領域２００の配線格子サイズを特定する情報が示されている。
【００３２】
この配線領域情報５００によれば、配線領域２００のＸ軸方向の配線格子サイズ「０−Ｘmax」およびＹ軸方向の配線格子サイズ「０−Ｙmax」と、設計対象回路が有する配線層の層数「３０」を特定することができる。各配線層には、最下層の配線層から順に「１〜３０」の番号が割り付けられている。これにより、各配線層を認識することができる。
【００３３】
図６において、配線領域情報６００には、配線領域２００上の配線禁止領域をあらわす配線禁止情報６００−１〜６００−４が示されている。ここで、配線禁止領域とは、トランジスタ、配線、ビアなどの障害物が配置され、新たな配線を形成することができない領域である。
【００３４】
具体的には、配線禁止情報６００−１〜６００−４は、配線禁止ＩＤ、開始座標、終了座標、開始層および終了層に関する情報を有している。配線禁止ＩＤは、配線禁止領域を識別する識別子である。開始座標は、配線禁止領域の開始位置を特定する座標位置である。終了座標は、配線禁止領域の終了位置を特定する座標位置である。開始層／終了層は、複数層にわたって形成される配線禁止領域の開始層および終了層を特定する番号である。
【００３５】
ここで、配線禁止領域Ｆ１を例に挙げると、開始座標（ＸF１，ＹF１）および終了座標（ＸF２，ＹF２）によって特定される矩形の領域であり（図２参照）、設計対象回路の第１層から第３０層にわたって形成される障害物（異なる配線層間を接続するビア）である。
【００３６】
つぎに、ネットグループ情報の具体例について説明する。図７は、ネットグループ情報の具体例を示す説明図である。図７において、ネットグループテーブル７００には、設計対象回路内の接続関係を有する一対の部品ごとのネットグループ情報７００−１〜７００−４が記憶されている。ここで、部品とは、たとえば、抵抗器、コンデンサ、トランジスタ、ＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）などの電子部品である。
【００３７】
具体的には、ネットグループ情報７００−１〜７００−４は、ネットグループＩＤ、始点座標、終点座標、ビット幅および使用層に関する情報を有している。ネットグループＩＤは、ネットグループを識別する識別子である。始点座標／終点座標は、ネットグループの配線経路の始点および終点を特定する座標位置である。
【００３８】
ビット幅は、ネットグループ固有の配線幅を特定する情報である。使用層は、ビアのタイプによって制限される使用可能な配線層を特定する情報である。ここで、ネットグループＮＧ１を例に挙げると、始点座標（ＸN１，ＹN１）、終点座標（ＸN２，ＹN２）であり、ビット幅「３２ビット」、使用層「第１層〜第５層」である。
【００３９】
なお、ビット幅が「３２ビット」の場合、たとえば、１ビットの情報を送信するために１本の配線を用いるとすると、ネットグループＮＧ１に含まれるネットの総数は３２本となる。このため、たとえば、設計対象回路の配線幅が６０［ｎｍ］の場合、ネットグループＮＧ１固有の配線幅は１９２０［ｎｍ］（＝３２×６０）となる。
【００４０】
図４の説明に戻り、探索部４０２は、設計対象回路の配線領域内のネットグループ固有の始点座標から終点座標に辿り着くまでのネットグループ固有の配線幅の配線経路をネットグループごとに探索する機能を有する。具体的には、たとえば、探索部４０２は、記憶領域に記憶された配線領域情報５００，６００およびネットグループ情報７００−１〜７００−４に基づいて、ネットグループＮＧ１〜ＮＧ４ごとの配線経路を探索する。
【００４１】
より詳細に説明すると、たとえば、探索部４０２は、配線領域２００全体を配線可能領域として、ネットグループＮＧ１〜ＮＧ４固有の始点座標から終点座標に辿り着くまでの最短の配線経路（仮想配線経路）を探索することとしてもよい。つまり、配線領域２００上の配線禁止領域Ｆ１〜Ｆ４を考慮することなく、各ネットグループＮＧ１〜ＮＧ４の配線経路を探索する。
【００４２】
ここで、探索部４０２による探索結果について説明する。図８は、探索結果の具体例を示す説明図（その１）である。図８において、配線領域２００には、ネットグループＮＧ１〜ＮＧ４固有の始点座標から終点座標に辿り着くまでの配線経路８１０〜８４０が示されている。ここで、各配線経路８１０〜８４０は、各ネットグループＮＧ１〜ＮＧ４固有の始点座標と終点座標とを結ぶ直線である。
【００４３】
検出部４０３は、探索部４０２によって探索された配線経路間で相互に交差関係を有するネットグループの組み合わせを検出する機能を有する。具体的には、たとえば、検出部４０３は、配線領域情報５００，６００と、配線経路８１０〜８４０をあらわす配線経路情報とに基づいて、配線経路間で相互に交差関係を有するネットグループの組み合わせを検出する。
【００４４】
図８に示した例では、配線領域情報５００から配線領域２００の配線格子サイズを特定し、配線領域２００内で各ネットグループＮＧ１〜ＮＧ４固有の始点座標と終点座標とを結ぶ直線間の交点を検出することで、交差関係を有するネットグループの組み合わせを検出することができる。
【００４５】
より具体的には、たとえば、ネットグループＮＧ１〜ＮＧ４から選ばれた任意のネットグループと他のネットグループとの交点を検出し、後述する交差情報テーブルに登録する。これを、ネットグループＮＧ１〜ＮＧ４から選ばれていない未選択のネットグループがなくなるまで繰り返す。ただし、既に登録済みの交点については重複登録しない。
【００４６】
ここで、検出部４０３による検出結果（交差情報）について説明する。図９は、交差情報の具体例を示す説明図（その１）である。図９において、交差情報テーブル９００には、相互に交差関係を有するネットグループの組み合わせをあらわす交差情報９００−１〜９００−４が示されている。
【００４７】
具体的には、交差情報９００−１〜９００−４は、エッジＩＤ、始点および終点に関する情報を有している。エッジＩＤは、後述する無向グラフにおいて、交差関係を有するネットグループのノード間をつなぐエッジを識別する識別子である。始点／終点は、交差関係を有するネットグループの組み合わせを特定する情報である。
【００４８】
たとえば、交差情報９００−１によれば、ネットグループＮＧ１の配線経路８１０とネットグループＮＧ３の配線経路８３０との間で交差関係を認識することができる。なお、交差情報テーブル９００は、たとえば、図３に示したＲＡＭ３０３、磁気ディスク３０５、光ディスク３０７などの記憶領域によって実現される。
【００４９】
決定部４０５は、検出部４０３によって検出された組み合わせのネットグループがそれぞれ異なる配線層に割り当てられるように、設計対象回路が有する複数の配線層の中から各ネットグループに割り当てる配線層を決定する機能を有する。この決定処理には、たとえば、与えられた無向グラフのノードに対して、直接接続されたノード間で色が異なるように彩色する彩色問題を適用することができる。
【００５０】
無向グラフの彩色問題を解くことにより、その無向グラフ内のノードを最小の数の色で彩色することができる。つまり、この彩色問題を配線層割当の最適化に適用することにより（彩色問題における色を配線層の番号に適用）、配線設計に必要となる最小の配線層数を求める。以下、決定部４０５による決定処理の具体的な処理内容について説明する。
【００５１】
まず、作成部４０４は、設計対象回路内の接続関係を有する一対の部品ごとのネットグループがノード化され、検出部４０３によって検出された交差関係を有するネットグループの組み合わせのノード間をつなぐ無向グラフを作成する機能を有する。具体的には、たとえば、まず、ネットグループ情報７００−１〜７００−４を参照して、ネットグループＮＧ１〜ＮＧ４をノード化する。
【００５２】
このあと、交差情報９００−１〜９００−４を参照して、相互に交差関係を有するネットグループをあらわすノード間をエッジＥ１〜Ｅ４によってつなぐ無向グラフを作成する。図１０は、無向グラフの具体例を示す説明図（その１）である。図１０において、無向グラフ１０００は、ネットグループＮＧ１〜ＮＧ４をあらわすノードＮＧ１〜ＮＧ４から構成され、交差関係を有するノード間がエッジＥ１〜Ｅ４によって接続されている。
【００５３】
決定部４０５は、作成部４０４によって作成された無向グラフ１０００の彩色問題を解くことにより、無向グラフ１０００内の直接接続されたノード間で配線層が異なるように、各ネットグループＮＧ１〜ＮＧ４に割り当てる配線層を決定する。具体的には、たとえば、ＳＥＱ（ＳＥＱｕｅｎｔｉａｌ  ｈｅｕｒｉｓｔｉｃ）を用いて、無向グラフ１０００内の各ノードＮＧ１〜ＮＧ４に、隣接ノードに割り当てられていない色を順次割り当てていく。
【００５４】
ここで、各ノードＮＧ１〜ＮＧ４につながれたエッジ数の最大値を「Δ」とする。配線層割当に彩色問題を適用することにより、最大でも「Δ＋１」の層数の配線層を用いて、各ネットグループＮＧ１〜ＮＧ４に割り当てる配線層を決定することができる。無向グラフ１０００の例では、必要となる配線層は最大でも３層である。
【００５５】
ここで、決定部４０５による決定結果の具体例について説明する。図１１は、決定結果の具体例を示す説明図（その１）である。図１１において、決定結果１１００には、各ネットグループＮＧ１〜ＮＧ４の割当先の配線層が示されている。具体的には、ネットグループＮＧ１，ＮＧ２は第１層に割り当てられており、ネットグループＮＧ３，ＮＧ４は第２層に割り当てられている。
【００５６】
この決定結果１１００によれば、相互に交差関係にあるネットグループＮＧ１とネットグループＮＧ３，ＮＧ４とがそれぞれ異なる配線層に割り当てられており、また、相互に交差関係にあるネットグループＮＧ２とネットグループＮＧ３，ＮＧ４とがそれぞれ異なる配線層に割り当てられている。
【００５７】
さらに、交差関係にないネットグループＮＧ１とネットグループＮＧ２、およびネットグループＮＧ３とネットグループＮＧ４が同一の配線層に割り当てられている。すなわち、ネットグループＮＧ１〜ＮＧ４の配線設計に必要となる配線層の層数は「２」となる。このように、配線層割当に無向グラフの彩色問題を適用することにより、配線設計に必要となる配線層の層数を最小化することができる。
【００５８】
出力部４０６は、決定部４０５によって決定された決定結果（たとえば、決定結果１１００）を出力する機能を有する。なお、出力部４０６による出力形式としては、たとえば、ディスプレイ３０８への表示、プリンタ３１３への印刷出力、Ｉ／Ｆ３０９による外部装置への送信がある。また、ＲＡＭ３０３、磁気ディスク３０５、光ディスク３０７などの記憶領域に記憶することとしてもよい。
【００５９】
また、上述した例では、配線領域内の配線禁止領域を考慮しない仮想的な配線経路（８１０〜８４０）を探索することとしたが、配線領域内の配線禁止領域を考慮して、物理的に配線可能な配線経路（概略配線経路）を探索することとしてもよい。
【００６０】
具体的には、たとえば、探索部４０２は、配線領域２００内の配線禁止領域Ｆ１〜Ｆ４を除く残余の配線領域２００を配線可能領域として、ネットグループＮＧ１〜ＮＧ４固有の始点座標から終点座標に辿り着くまでの配線経路を探索することとしてもよい。ここで、探索部４０２による探索処理の具体的な処理内容について説明する。
【００６１】
まず、配線可能領域において、各ネットグループＮＧ１〜ＮＧ４固有の始点座標から終点座標に辿り着くまでに１回の曲がりを許して配線経路を探索する。ここで、配線経路が探索されなかった場合、同様に２回の曲がりを許して配線経路を探索する。これでも配線経路が探索されなかった場合には、配線不能として探索処理を終了する、あるいは、配線領域２００の配線領域サイズを拡張して再探索する。
【００６２】
ここで、探索部４０２による探索結果について説明する。図１２は、探索結果の具体例を示す説明図（その２）である。図１２において、配線領域２００には、各ネットグループＮＧ１〜ＮＧ４固有の始点座標から終点座標に辿り着くまでの配線経路１２１０〜１２４０が示されている。これら配線経路１２１０〜１２４０は、配線領域２００内の配線禁止領域Ｆ１〜Ｆ４を迂回して、各ネットグループＮＧ１〜ＮＧ４固有の始点座標と終点座標とを結ぶ概略配線経路である。
【００６３】
つぎに、探索部４０２による探索結果（配線経路情報）をあらわすデータ構造について説明する。図１３および図１４は、配線経路情報の具体例を示す説明図である。図１３において、探索結果テーブル１３００には、ネットグループＮＧ１〜ＮＧ４ごとの配線経路１２１０〜１２４０（図１２参照）に関する配線経路情報１３００−１〜１３００−４が記憶されている。
【００６４】
具体的には、配線経路情報１３００−１〜１３００−４は、各ネットグループＮＧ１〜ＮＧの開始インデックスおよびパターン数を有している。インデックスは、配線経路１２１０〜１２４０を構成する各パターンの配線経路情報（図１４に示す配線経路情報１４００−１〜１４００−１２）の格納場所を特定する索引番号である。
【００６５】
開始インデックスは、各配線経路１２１０〜１２４０の開始パターン（各ネットグループＮＧ１〜ＮＧ４固有の始点座標を含むパターン）の配線経路情報の格納場所を特定する索引番号である。パターン数は、各配線経路１２１０〜１２４０を構成するパターンの総数である。
【００６６】
図１４において、探索結果テーブル１４００には、インデックス０〜１１ごとに、パターンＩＤおよび開始／終了座標に関する配線経路情報１４００−１〜１４００−１２が記憶されている。パターンＩＤは、配線経路１２１０〜１２４０を構成するパターンＰＴ１〜ＰＴ１２を識別する識別子である。
【００６７】
これら探索結果テーブル１３００，１４００を参照することにより、配線領域２００内における各配線経路１２１０〜１２４０を特定することができる。ここで、ネットグループＮＧ３の配線経路１２３０を例に挙げると、配線経路情報１３００−３から開始インデックス「３」およびパターン数「３」を特定する。そして、インデックス３を含む３つ分の配線経路情報１４００−４〜１４００−６からパターンＰＴ４，ＰＴ５，ＰＴ６の開始／終了座標を特定する。
【００６８】
これにより、配線領域２００内におけるパターンＰＴ４，ＰＴ５，ＰＴ６からなる配線経路１２３０を特定することができる。なお、探索結果テーブル１３００，１４００は、たとえば、図３に示したＲＡＭ３０３、磁気ディスク３０５、光ディスク３０７などの記憶領域によって実現される。
【００６９】
この場合、検出部４０３は、探索結果テーブル１３００，１４００を参照して、配線経路１２１０〜１２４０間で相互に交差関係を有するネットグループの組み合わせを検出する。具体的には、探索結果テーブル１３００，１４００を参照して、配線領域２００内における各配線経路１２１０〜１２４０を特定し、配線経路１２１０〜１２４０間の交差関係を検出する。
【００７０】
ここで、検出部４０３による検出結果について説明する。図１５は、交差情報の具体例を示す説明図（その２）である。図１５において、交差情報テーブル１５００には、相互に交差関係を有するネットグループの組み合わせをあらわす交差情報１５００−１〜１５００−５が記憶されている。
【００７１】
これによれば、配線領域２００全体を配線可能領域として配線経路８１０〜８４０を探索した場合（図９に示した交差情報テーブル９００）に比べて、配線経路１２３０と配線経路１２４０との間で交差関係をあらわすネットグループＮＧ３とネットグループＮＧ４との組み合わせ（交差情報１５００−５）が増えている。
【００７２】
つぎに、交差情報１５００−１〜１５００−５に基づく無向グラフについて説明する。図１６は、無向グラフの具体例を示す説明図（その２）である。図１６において、無向グラフ１６００は、ネットグループＮＧ１〜ＮＧ４をあらわすノードＮＧ１〜ＮＧ４から構成され、交差関係を有するノード間がエッジＥ１〜Ｅ５によって接続されている。
【００７３】
この無向グラフ１６００は、図１０に示した無向グラフ１０００に比べて、ノードＮＧ３とノードＮＧ４とをつなぐエッジＥ５が増えている。この場合、決定部４０５は、無向グラフ１６００の彩色問題を解くことにより、無向グラフ１６００内の直接接続されたノード間で割当先の配線層が異なるように、各ネットグループＮＧ１〜ＮＧ４に割り当てる配線層を決定する。
【００７４】
ここで、決定部４０５による決定結果の具体例について説明する。図１７は、決定結果の具体例を示す説明図（その２）である。図１７において、決定結果１７００には、各ネットグループＮＧ１〜ＮＧ４の割当先の配線層が示されている。具体的には、ネットグループＮＧ１，ＮＧ２は第１層に割り当てられている。また、ネットグループＮＧ３は第２層に割り当てられており、ネットグループＮＧ４は第３層に割り当てられている。
【００７５】
この決定結果１７００によれば、物理的に配線可能な配線経路１２１０〜１２４０が探索された結果、仮想的な配線経路を探索した場合に比べて、ネットグループＮＧ３とネットグループＮＧ４との交差関係が新たに発生している。このため、ネットグループＮＧ３とネットグループＮＧ４とがそれぞれ異なる配線層に割り当てられている。
【００７６】
また、取得部４０１は、同一配線層に割り当てるべき複数のネットグループの組み合わせを規定する制約条件を取得することとしてもよい。ここで、制約条件の具体例について説明する。図１８は、制約条件の具体例を示す説明図（その１）である。図１８において、制約条件１８００には、制約条件ＩＤ、および同一配線層に割り当てるべきネットグループＮＧ１〜ＮＧ４の組み合わせが規定されている。
【００７７】
制約条件ＩＤは、制約条件を識別する識別子である。ここでは、制約条件Ｃ１として、同一配線層に割り当てるべきネットグループＮＧ１およびＮＧ２の組み合わせが規定されている。この制約条件１７００は、たとえば、図３に示したキーボード３１０やマウス３１１をユーザが操作することで設計支援装置に直接入力することとしてもよく、また、不図示の外部装置から取得することとしてもよい。
【００７８】
この場合、決定部４０５は、取得部４０１によって取得された制約条件に基づいて、設計対象回路が有する複数の配線層の中から各ネットグループに割り当てる配線層を決定することとしてもよい。具体的には、彩色問題において、同一配線層に割り当てるべきネットグループをあらわすノードを同じ色で彩色する制約をつけることにより実現する。図１７に示した例では、まず、ネットグループＮＧ１，ＮＧ２を同一配線層（同じ色）に割り当てたあと、ネットグループＮＧ３，ＮＧ４の割当先を決定することとなる。
【００７９】
また、探索部４０２は、物理的に配線可能な各ネットグループの配線経路が探索された結果、検出部４０３によって第１および第２のネットグループの組み合わせが検出された場合、第２のネットグループの配線経路を配線禁止領域として、第１のネットグループの配線経路を再探索することとしてもよい。
【００８０】
具体的には、設計対象回路の配線領域情報（たとえば、配線領域情報５００，６００）と、探索済みの配線経路に関する配線経路情報（たとえば、探索結果テーブル１３００，１４００）とに基づいて、配線領域内の障害物（たとえば、配線禁止領域Ｆ１〜Ｆ４）と第２のネットグループの配線経路とを配線禁止領域として、第１のネットグループの配線経路を再探索する（後述する実施例１を参照）。
【００８１】
さらに、探索部４０２は、検出部４０３によって第１および第２のネットグループの組み合わせが検出された場合、第１のネットグループから分割された第３および第４のネットグループ固有の配線幅に基づいて、第１のネットグループ固有の始点座標と終点座標とをつなぐ第３および第４のネットグループの配線経路を探索することとしてもよい（後述する実施例２を参照）。
【００８２】
第３および第４のネットグループ固有の配線幅は、たとえば、後述する第１のネットグループを分割する割合から算出することとしてもよい。また、第１のネットグループから分割される第３および第４のネットグループに関するネットグループ情報から特定することとしてもよい。なお、第３および第４のネットグループに関するネットグループ情報は、たとえば、設計対象回路の回路情報に含まれている。
【００８３】
ここで、Ｎ本のネットをグループ化した第１のネットグループを、第３および第４のネットグループに分割するネット数の割合は、任意に設定可能である。たとえば、ネット数の割合が「１：１」に設定されている場合、第１のネットグループを、Ｎ／２本のネットをグループ化した第３のネットグループと、Ｎ／２本のネットをグループ化した第４のネットグループとに分割することとなる。
【００８４】
たとえば、図１に示したネットグループ１７０を第１のネットグループとすると、それぞれ２本（＝４／２）のネットをグループ化した第３および第４のネットグループに分割することとなる。なお、ネット数が割り切れない場合には、一方の端数を切り上げ、もう一方の端数を切り捨てることとしてもよい。
【００８５】
なお、第１のネットグループを分割する割合は、たとえば、図３に示したキーボード３１０やマウス３１１をユーザが操作することで任意に設定され、ＲＡＭ３０３、磁気ディスク３０５、光ディスク３０７などの記憶領域に記憶される。
【００８６】
また、第１のネットグループを分割する割合に従って、第１のネットグループ固有の配線幅を分割することで、第３および第４のネットグループ固有の配線幅を算出することができる。たとえば、上記割合が「１：１」、第１のネットグループ固有の配線幅が２４０［ｎｍ］であった場合、第３および第４のネットグループ固有の配線幅はともに１２０［ｎｍ］となる。
【００８７】
判断部４０７は、決定部４０５によって割当先が決定された結果、相互に交差関係を有する第１および第２のネットグループの割当先が制約条件に違反しているか否かを判断する機能を有する。具体的には、たとえば、検出部４０３によって検出された検出結果と、取得部４０１によって取得された制約条件とを比較することにより、制約条件に違反しているか否かを判断する。
【００８８】
そして、探索部４０２は、判断部４０７によって制約条件に違反していると判断された場合、配線領域内の配線禁止領域および第２のネットグループの配線経路を除く残余の配線領域を配線可能領域として、第１のネットグループの配線経路を再探索することとしてもよい（後述する実施例３を参照）。
【００８９】
（設計支援装置の設計支援処理手順）
つぎに、本実施の形態にかかる設計支援装置３００の設計支援処理手順について説明する。図１９は、設計支援装置の設計支援処理手順の一例を示すフローチャートである。
【００９０】
なお、以下に説明する設計支援処理では、たとえば、図３に示したキーボード３１０やマウス３１１をユーザが操作することで設計対象回路に関する配線領域情報およびネットグループ情報が設計支援装置３００に入力されると、ステップＳ１９０１〜１９０６における一連の処理がコンピュータにより自動実行される。
【００９１】
図１９のフローチャートにおいて、まず、取得部４０１により、設計対象回路に関する配線領域情報およびネットグループ情報を取得したか否かを判断する（ステップＳ１９０１）。ここで、配線領域情報およびネットグループ情報を取得するのを待って（ステップＳ１９０１：Ｎｏ）、取得した場合（ステップＳ１９０１：Ｙｅｓ）、探索部４０２により、取得された配線領域情報およびネットグループ情報に基づいて、設計対象回路の配線領域内のネットグループ固有の始点座標から終点座標に辿り着くまでのネットグループ固有の配線幅の配線経路をネットグループごとに探索する（ステップＳ１９０２）。
【００９２】
このあと、検出部４０３により、探索された配線経路間で相互に交差関係を有するネットグループの組み合わせを検出し（ステップＳ１９０３）、作成部４０４により、ネットグループがノード化され、検出部４０３によって検出された交差関係を有するネットグループの組み合わせのノード間をつなぐ無向グラフを作成する（ステップＳ１９０４）。
【００９３】
そして、決定部４０５により、作成された無向グラフの彩色問題を解くことにより、当該無向グラフ内の直接接続されたノード間で配線層が異なるように、設計対象回路が有する複数の配線層の中から各ネットグループに割り当てる配線層を決定し（ステップＳ１９０５）、最後に、出力部４０６により、決定部４０５によって決定された決定結果を出力して（ステップＳ１９０６）、本フローチャートによる一連の処理を終了する。
【００９４】
なお、ステップＳ１９０２において、仮想配線経路または概略配線経路のいずれを探索対象とするかは、ユーザによって予め設定されていることとする。
【００９５】
以上説明したように、本実施の形態によれば、設計対象回路内の一対の部品間をつなぐネットのうち同一配線層に配線すべきネットをグループ化し、ネットグループごとの配線経路探索および配線層割当を自動化することができる。これにより、配線設計にかかる作業負荷および作業時間を削減し、設計期間の短縮化を図ることができる。
【００９６】
また、相互に交差関係を有するネットグループをそれぞれ異なる配線層に割り当て、相互に交差関係にないネットグループを同一配線層に割り当てることができる。これにより、回路動作の信頼性を低下させることなく配線設計に必要となる配線層の層数を最適化することができ、製造コストを削減することができる。
【実施例１】
【００９７】
つぎに、本実施の形態の実施例１について説明する。実施例１では、物理的に配線可能な配線経路を探索した結果、相互に交差関係を有する第１および第２のネットグループの組み合わせが検出された場合、第２のネットグループの配線経路を配線禁止領域として、第１のネットグループの配線経路を再探索する。
【００９８】
この結果、第２のネットグループの配線経路を迂回して、第１のネットグループ固有の始点座標から終点座標に辿り着くまでの配線経路が探索されると、第１および第２のネットグループの交差関係が解消される。なお、実施の形態において説明した箇所と同一箇所については、図示および説明を省略する。
【００９９】
具体的には、検出部４０３により、相互に交差関係を有するネットグループの組み合わせが検出された結果、ネットグループＮＧ１〜ＮＧ４の中から、交差関係にある他のネットグループ数が最大となるネットグループを検出する。具体的には、たとえば、作成部４０４によって作成された無向グラフ１６００（または、交差情報テーブル１５００）を参照して、各ノードＮＧ１〜ＮＧ４のエッジ数を計数する。
【０１００】
より具体的には、たとえば、交差情報テーブル１５００に出現する各ネットグループＩＤを計数することにより、各ノードＮＧ１〜ＮＧ４のエッジ数を計数することができる。なお、エッジ数が最大のノードがあらわすネットグループは、交差関係にある他のネットグループ数が最大のネットグループに相当する。
【０１０１】
図２０は、計数結果の具体例を示す説明図である。図２０において、計数結果２０００には、ネットグループＮＧ１〜ＮＧ４ごとのエッジ数が示されている。この計数結果２０００を参照することで、エッジ数が最大（３本）となるノードＮＧ３，ＮＧ４を検出することができる。
【０１０２】
このあと、探索部４０２により、エッジ数が最大のネットグループＮＧ３，ＮＧ４のうち、ネットグループＮＧ３（または、ネットグループＮＧ４）の配線経路を配線禁止領域として、ネットグループＮＧ４（または、ネットグループＮＧ３）の配線経路を再探索する。
【０１０３】
ここで、実施例１における探索部４０２による探索結果について説明する。ここでは、探索部４０２によって配線経路１２１０〜１２４０が探索された結果、ネットグループＮＧ３の配線経路１２３０を配線禁止領域として、ネットグループＮＧ４の配線経路を再探索した探索結果について説明する。
【０１０４】
図２１は、探索結果の具体例を示す説明図（その３）である。図２１において、配線領域２００には、各ネットグループＮＧ１〜ＮＧ４固有の始点座標から終点座標に辿り着くまでの配線経路１２１０〜１２３０，２１１０が示されている。
【０１０５】
配線経路２１１０は、配線領域２００内の配線禁止領域Ｆ１〜Ｆ４、およびネットグループＮＧ３の配線経路１２３０を配線禁止領域として、ネットグループＮＧ４固有の始点座標から終点座標に辿り着くまでの配線経路を再探索した探索結果である。ここでは、配線経路２１１０が探索された結果、ネットグループＮＧ３とネットグループＮＧ４との交差関係が解消されている。
【０１０６】
図２２は、決定結果の具体例を示す説明図（その３）である。図２２において、決定結果２２００には、各ネットグループＮＧ１〜ＮＧ４の割当先の配線層が示されている。具体的には、ネットグループＮＧ１，ＮＧ２は第１層に割り当てられており、ネットグループＮＧ３，ＮＧ４は第２層に割り当てられている。
【０１０７】
これによれば、ネットグループＮＧ３とネットグループＮＧ４との交差関係が解消され、ネットグループＮＧ３，ＮＧ４が同一配線層に割り当てられている。このため、図１７に示した決定結果１７００に比べて、設計対象回路の配線設計に必要となる配線層の層数が「１」少なくなっている。
【０１０８】
なお、探索部４０２による配線経路の再探索は、配線設計に必要となる配線層の層数が予め設定された閾値以下となるまで繰り返しおこなわれることとしてもよい。たとえば、閾値として「５」が設定されている場合、配線設計に必要となる配線層の層数が５以下となるまで、配線経路の再探索を繰り返す。なお、上記閾値は、たとえば、図３に示したキーボード３１０やマウス３１１をユーザが操作することで任意に設定可能である。
【０１０９】
（実施例１の設計支援処理手順）
つぎに、実施例１における設計支援処理手順について説明する。図２３は、実施例１における設計支援処理手順の一例を示すフローチャートである。まず、取得部４０１により、配線領域情報５００，６００およびネットグループ情報７００−１〜７００−４を取得したか否かを判断する（ステップＳ２３０１）。
【０１１０】
ここで、配線領域情報５００，６００およびネットグループ情報７００−１〜７００−４を取得するのを待って（ステップＳ２３０１：Ｎｏ）、取得した場合（ステップＳ２３０１：Ｙｅｓ）、探索部４０２により、配線領域情報５００，６００およびネットグループ情報７００−１〜７００−４に基づいて、配線領域２００内の各ネットグループＮＧ１〜ＮＧ４固有の始点座標から終点座標に辿り着くまでの各ネットグループＮＧ１〜ＮＧ４の配線幅の配線経路を探索する（ステップＳ２３０２）。
【０１１１】
このあと、検出部４０３により、探索された配線経路１２１０〜１２４０間で相互に交差関係を有するネットグループの組み合わせを検出し（ステップＳ２３０３）、作成部４０４により、ネットグループＮＧ１〜ＮＧ４がノード化され、交差関係を有するネットグループの組み合わせのノード間をつなぐ無向グラフ１６００を作成する（ステップＳ２３０４）。
【０１１２】
そして、決定部４０５により、無向グラフ１６００の彩色問題を解くことにより、無向グラフ１６００内の直接接続されたノード間で配線層が異なるように、設計対象回路が有する複数の配線層の中から各ネットグループＮＧ１〜ＮＧ４に割り当てる配線層を決定する（ステップＳ２３０５）。
【０１１３】
つぎに、決定部４０５によって決定された決定結果に基づいて、設計対象回路の配線設計に必要となる配線層の層数が予め設定された閾値以下か否かを判断する（ステップＳ２３０６）。ここで、閾値以下ではなかった場合（ステップＳ２３０６：Ｎｏ）、検出部４０３により、ネットグループＮＧ１〜ＮＧ４の中から、エッジ数が最大のノードをあらわすネットグループＮＧ３，ＮＧ４を検出する（ステップＳ２３０７）。
【０１１４】
そして、検出されたネットグループＮＧ３，ＮＧ４のうちネットグループＮＧ３の配線経路１２３０を配線禁止領域に設定して（ステップＳ２３０８）、ステップＳ２３０２に戻り、探索部４０２により、ネットグループＮＧ４の配線経路を再探索する。
【０１１５】
また、ステップＳ２３０６において、閾値以下であった場合（ステップＳ２３０６：Ｙｅｓ）、最後に、出力部４０６により、ステップＳ２３０５において決定された決定結果を出力して（ステップＳ２３０９）、本フローチャートによる一連の処理を終了する。
【０１１６】
なお、交差関係を解消する配線経路が探索されない場合を考慮して、ステップＳ２３０７において再探索回数が予め設定された所定回数以上となった場合には、配線設計に必要となる配線層の層数が閾値以下ではない場合であってもステップＳ２３０９に移行することとしてもよい。
【０１１７】
実施例１によれば、配線経路１２３０を配線禁止領域として、ネットグループＮＧ４固有の始点座標から終点座標までの配線経路２１１０を新たに探索することにより、ネットグループＮＧ３，ＮＧ４の同一配線層への割り当てが可能となり、配線設計に必要となる配線層の層数を削減することができる。
【実施例２】
【０１１８】
つぎに、本実施の形態の実施例２について説明する。実施例２では、物理的に配線可能な配線経路を探索した結果、相互に交差関係を有する第１および第２のネットグループの組み合わせが検出された場合、第１のネットグループから分割された第３および第４のネットグループ固有の配線幅に基づいて、第１のネットグループ固有の始点座標と終点座標とをつなぐ第３および第４のネットグループの配線経路を探索する。
【０１１９】
この結果、第２のネットグループの配線経路を迂回して、第１のネットグループ固有の始点座標から終点座標に辿り着くまでの第３および第４のネットグループの配線経路が探索されると、第１および第２のネットグループの交差関係が解消される。
【０１２０】
具体的には、検出部４０３により、図２０に示した計数結果２０００を参照して、エッジ数が最大のノードＮＧ３，ＮＧ４を検出する。ここでは、ネットグループ３を分割対象として説明する。このあと、ネットグループＮＧ３から分割されるネットグループＮＧ５，ＮＧ６固有の配線幅を特定する。
【０１２１】
そして、探索部４０２により、ネットグループＮＧ５，ＮＧ６固有の配線幅に基づいて、ネットグループＮＧ３固有の始点座標と終点座標とをつなぐネットグループＮＧ５，ＮＧ６の配線経路を探索する。
【０１２２】
ここで、実施例２における探索部４０２による探索結果について説明する。ここでは、配線経路１２１０〜１２４０が探索された結果、ネットグループＮＧ４の配線経路１２４０を配線禁止領域として、ネットグループＮＧ３から分割されたネットグループＮＧ５，ＮＧ６の配線経路を探索した探索結果について説明する。
【０１２３】
図２４は、探索結果の具体例を示す説明図（その４）である。なお、ここでは説明のため、ネットグループＮＧ５，ＮＧ６固有の始点／終点座標は、ネットグループＮＧ３固有の始点／終点座標からずれた座標位置となっている。図２４において、配線領域２００には、各ネットグループＮＧ１，ＮＧ２，ＮＧ４，ＮＧ５，ＮＧ６固有の始点座標から終点座標に辿り着くまでの配線経路１２１０，１２２０，１２４０，２３１０，２３２０が示されている。
【０１２４】
配線経路２３１０，２３２０は、配線領域２００内の配線禁止領域Ｆ１〜Ｆ４、およびネットグループＮＧ４の配線経路１２４０を配線禁止領域として、ネットグループＮＧ５，ＮＧ６の配線経路を探索した探索結果である。ここでは、これら配線経路２３１０，２３２０が探索された結果、ネットグループＮＧ３（ネットグループＮＧ５，ＮＧ６）と、ネットグループＮＧ４との交差関係が解消されている。
【０１２５】
なお、ネットグループＮＧ５，ＮＧ６の配線経路が探索されなかった場合には、第３のネットグループを分割するネット数の割合を自動変更（たとえば、「５：５」→「６：４）して、ネットグループＮＧ５，ＮＧ６の配線経路を再探索することとしてもよい。
【０１２６】
実施例２によれば、配線経路１２４０を配線禁止領域として、ネットグループＮＧ３固有の始点座標から終点座標までの配線経路２３１０，２３２０を新たに探索することにより、ネットグループＮＧ４〜ＮＧ６の同一配線層への割り当てが可能となり、設計対象回路の配線設計に必要となる配線層の層数を削減することができる。
【実施例３】
【０１２７】
つぎに、本実施の形態の実施例３について説明する。実施例３では、各ネットグループに配線層が割り当てられた結果、相互に交差関係を有する第１および第２のネットグループの割当結果が制約条件に違反している場合、第２のネットグループの配線経路を配線禁止領域として、第１のネットグループの配線経路を再探索する。
【０１２８】
この結果、第２のネットグループの配線経路を迂回して、第１のネットグループ固有の始点座標から終点座標に辿り着くまでの配線経路が探索されると、第１および第２のネットグループの交差関係が解消される。ここで、実施例３の制約条件について説明する。図２５は、制約条件の具体例を示す説明図（その２）である。
【０１２９】
図２５において、制約条件２５００には、制約条件Ｃ２として、同一配線層に割り当てるべきネットグループＮＧ１およびＮＧ３の組み合わせが規定されている。ここでは、判断部４０７は、相互に交差関係を有する第１および第２のネットグループの割当結果が制約条件２５００に違反しているか否かを判断することとなる。
【０１３０】
具体的には、判断部４０７により、決定部４０５によって割当先が決定された結果（図１７に示した決定結果１７００）、検出部４０３によって検出された相互に交差関係を有するネットグループの組み合わせと、制約条件２５００に規定されているネットグループＮＧ１とネットグループＮＧ３との組み合わせを比較することにより、制約条件２５００に違反しているか否かを判断する。
【０１３１】
ここでは、相互に交差関係を有するネットグループの組み合わせの中に、ネットグループＮＧ１とネットグループＮＧ３との組み合わせが存在するため（交差情報テーブル１５００、無向グラフ１６００を参照）、制約条件２５００に違反していると判断する。
【０１３２】
この場合、探索部４０２は、配線領域２００内の配線禁止領域Ｆ１〜Ｆ４およびネットグループＮＧ１（または、ネットグループＮＧ３）の配線経路１２３０（または、配線経路１２１０）を除く残余の配線領域２００を配線可能領域として、ネットグループＮＧ３（または、ネットグループＮＧ１）の配線経路１２１０（または、配線経路１２３０）を再探索する。
【０１３３】
ここで、実施例３における探索部４０２による探索結果について説明する。ここでは、判断部４０７によってネットグループＮＧ１，ＮＧ３を同一配線層に形成する制約条件２５００に違反していると判断された結果、ネットグループＮＧ１の配線経路１２１０を配線禁止領域として、ネットグループＮＧ３の配線経路を再探索した探索結果について説明する。
【０１３４】
図２６は、探索結果の具体例を示す説明図（その５）である。図２６において、配線領域２００には、各ネットグループＮＧ１〜ＮＧ４固有の始点座標から終点座標に辿り着くまでの配線経路１２１０〜１２３０，２６１０が示されている。
【０１３５】
配線経路２６１０は、配線領域２００内の配線禁止領域Ｆ１〜Ｆ４、およびネットグループＮＧ１の配線経路１２１０を配線禁止領域として、ネットグループＮＧ３固有の始点座標から終点座標に辿り着くまでの配線経路を再探索した探索結果である。ここでは、配線経路２５１０が探索された結果、ネットグループＮＧ１とネットグループＮＧ３との交差関係が解消されている。
【０１３６】
（実施例３の設計支援処理手順）
つぎに、実施例３における設計支援処理手順について説明する。図２７は、実施例３における設計支援処理手順の一例を示すフローチャートである。図２７のフローチャートにおいて、まず、取得部４０１により、配線領域情報５００，６００、ネットグループ情報７００−１〜７００−４および制約条件２５００を取得したか否かを判断する（ステップＳ２７０１）。
【０１３７】
ここで、配線領域情報５００，６００、ネットグループ情報７００−１〜７００−４および制約条件２５００を取得するのを待って（ステップＳ２７０１：Ｎｏ）、取得した場合（ステップＳ２７０１：Ｙｅｓ）、探索部４０２により、配線領域情報５００，６００およびネットグループ情報７００−１〜７００−４に基づいて、配線領域２００内の各ネットグループＮＧ１〜ＮＧ４固有の始点座標から終点座標に辿り着くまでの各ネットグループＮＧ１〜ＮＧ４の配線幅の配線経路を探索する（ステップＳ２７０２）。
【０１３８】
このあと、検出部４０３により、探索された配線経路１２１０〜１２４０間で相互に交差関係を有するネットグループの組み合わせを検出し（ステップＳ２７０３）、作成部４０４により、ネットグループＮＧ１〜ＮＧ４がノード化され、交差関係を有するネットグループの組み合わせのノード間をつなぐ無向グラフ１６００を作成する（ステップＳ２７０４）。
【０１３９】
そして、決定部４０５により、無向グラフ１６００の彩色問題を解くことにより、無向グラフ１６００内の直接接続されたノード間で配線層が異なるように、設計対象回路が有する複数の配線層の中から各ネットグループＮＧ１〜ＮＧ４に割り当てる配線層を決定する（ステップＳ２７０５）。
【０１４０】
つぎに、判断部４０７により、検出部４０３によって検出された相互に交差関係を有するネットグループの組み合わせが、ステップＳ２７０１において取得された制約条件２５００に違反しているか否かを判断する（ステップＳ２７０６）。
【０１４１】
ここで、制約条件２５００に違反している場合（ステップＳ２７０６：Ｙｅｓ）、ネットグループＮＧ１の配線経路１２１０を配線禁止領域に設定して（ステップＳ２７０７）、ステップＳ２７０２に戻り、ネットグループＮＧ３固有の始点座標から終点座標に辿り着くまでの配線経路を再探索する。
【０１４２】
一方、制約条件２５００に違反していない場合（ステップＳ２７０６：Ｎｏ）、最後に、出力部４０６により、ステップＳ２７０５において決定された決定結果を出力して（ステップＳ２７０８）、本フローチャートによる一連の処理を終了する。
【０１４３】
実施例３によれば、制約条件２５００違反となっているネットグループＮＧ１の配線経路１２１０を配線禁止領域として、ネットグループＮＧ３固有の始点座標から終点座標までの配線経路２６１０を新たに探索することにより、ネットグループＮＧ１，ＮＧ３の同一配線層への割り当てが可能となり、制約条件２５００違反を解消することができる。
【０１４４】
なお、本実施の形態で説明した設計支援方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また、このプログラムは、インターネットなどのネットワークを介して配布することが可能な媒体であってもよい。
【０１４５】
また、本実施の形態で説明した設計支援装置３００は、スタンダードセルやストラクチャードＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ  Ｌｏｇｉｃ  Ｄｅｖｉｃｅ）によっても実現することができる。具体的には、たとえば、上述した設計支援装置３００の機能（取得部４０１〜判断部４０７）をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、設計支援装置３００を製造することができる。
【０１４６】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１４７】
（付記１）設計対象回路内の接続関係を有する一対の部品ごとに、当該部品間をつなぐネットのうち同一配線層に配線すべきネットをグループ化したネットグループ固有の始点／終点座標および配線幅を記憶する記憶手段にアクセス可能なコンピュータを、
前記記憶手段にアクセスして、前記設計対象回路の配線領域内の前記始点座標から前記終点座標に辿り着くまでの前記配線幅の配線経路を前記ネットグループごとに探索する探索手段、
前記探索手段によって探索された配線経路間で相互に交差関係を有するネットグループの組み合わせを検出する検出手段、
前記検出手段によって検出された組み合わせのネットグループがそれぞれ異なる配線層に割り当てられるように、前記設計対象回路が有する複数の配線層の中から前記各ネットグループに割り当てる配線層を決定する決定手段、
前記決定手段によって決定された決定結果を出力する出力手段、
として機能させることを特徴とする設計支援プログラム。
【０１４８】
（付記２）前記コンピュータを、
前記設計対象回路内の接続関係を有する一対の部品ごとのネットグループがノード化され、前記検出手段によって検出された交差関係を有するネットグループの組み合わせのノード間をつなぐ無向グラフを作成する作成手段として機能させ、
前記決定手段は、
前記作成手段によって作成された無向グラフの彩色問題を解くことにより、当該無向グラフ内の直接接続されたノード間で配線層が異なるように、前記複数の配線層の中から前記各ネットグループに割り当てる配線層を決定することを特徴とする付記１に記載の設計支援プログラム。
【０１４９】
（付記３）前記探索手段は、
前記配線領域を配線可能領域として、前記始点座標から前記終点座標に辿り着くまでの最短の配線経路を探索することを特徴とする付記１または２に記載の設計支援プログラム。
【０１５０】
（付記４）前記探索手段は、
前記配線領域内の配線禁止領域を除く残余の配線領域を配線可能領域として、前記始点座標から前記終点座標に辿り着くまでの配線経路を探索することを特徴とする付記１または２に記載の設計支援プログラム。
【０１５１】
（付記５）前記探索手段は、
前記検出手段によって第１および第２のネットグループの組み合わせが検出された場合、前記第２のネットグループの配線経路を配線禁止領域として、前記第１のネットグループの配線経路を再探索することを特徴とする付記４に記載の設計支援プログラム。
【０１５２】
（付記６）前記探索手段は、
前記検出手段によって第１および第２のネットグループの組み合わせが検出された場合、前記第１のネットグループから分割された第３および第４のネットグループ固有の配線幅に基づいて、前記第１のネットグループ固有の始点座標と終点座標とをつなぐ前記第３および第４のネットグループの配線経路を探索することを特徴とする付記４または５に記載の設計支援プログラム。
【０１５３】
（付記７）前記探索手段は、
前記第１のネットグループから分割された第３および第４のネットグループ固有の配線幅を算出することにより、前記第３および第４のネットグループの配線経路を探索することを特徴とする付記６に記載の設計支援プログラム。
【０１５４】
（付記８）前記記憶手段は、
同一配線層に割り当てるべき複数のネットグループの組み合わせを規定する制約条件を記憶しており、
前記コンピュータを、
前記記憶手段にアクセスして、前記決定手段によって前記割当先が決定された結果、前記第１および第２のネットグループの割当先が前記制約条件に違反しているか否かを判断する判断手段として機能させ、
前記探索手段は、
前記判断手段によって前記制約条件に違反していると判断された場合、前記配線領域内の配線禁止領域および前記第２のネットグループの配線経路を除く残余の配線領域を配線可能領域として、前記第１のネットグループの配線経路を再探索することを特徴とする付記５〜７のいずれか一つに記載の設計支援プログラム。
【０１５５】
（付記９）前記探索手段は、
前記判断手段によって前記制約条件に違反していると判断された場合、前記第１のネットグループから分割された第３および第４のネットグループ固有の配線幅に基づいて、前記第１のネットグループ固有の始点座標と終点座標とをつなぐ前記第３および第４のネットグループの配線経路を探索することを特徴とする付記８に記載の設計支援プログラム。
【０１５６】
（付記１０）前記記憶手段は、
同一配線層に割り当てるべき複数のネットグループの組み合わせを規定する制約条件を記憶しており、
前記決定手段は、
前記記憶手段によって記憶された制約条件に基づいて、前記複数の配線層の中から前記各ネットグループに割り当てる配線層を決定することを特徴とする付記１〜９のいずれか一つに記載の設計支援プログラム。
【０１５７】
（付記１１）付記１〜１０のいずれか一つに記載の設計支援プログラムを記録したコンピュータに読み取り可能な記録媒体。
【０１５８】
（付記１２）設計対象回路内の接続関係を有する一対の部品ごとに、当該部品間をつなぐネットのうち同一配線層に配線すべきネットをグループ化したネットグループ固有の始点／終点座標および配線幅を記憶する記憶手段と、
前記記憶手段にアクセスして、前記設計対象回路の配線領域内の前記始点座標から前記終点座標に辿り着くまでの前記配線幅の配線経路を前記ネットグループごとに探索する探索手段と、
前記探索手段によって探索された配線経路間で相互に交差関係を有するネットグループの組み合わせを検出する検出手段と、
前記検出手段によって検出された組み合わせのネットグループがそれぞれ異なる配線層に割り当てられるように、前記設計対象回路が有する複数の配線層の中から前記各ネットグループに割り当てる配線層を決定する決定手段と、
前記決定手段によって決定された決定結果を出力する出力手段と、
を備えることを特徴とする設計支援装置。
【０１５９】
（付記１３）制御手段および記憶手段を備え、設計対象回路内の接続関係を有する一対の部品ごとに、当該部品間をつなぐネットのうち同一配線層に配線すべきネットをグループ化したネットグループ固有の始点／終点座標および配線幅を記憶するテーブルにアクセス可能なコンピュータが、
前記制御手段により、前記テーブルにアクセスして、前記設計対象回路の配線領域内の前記始点座標から前記終点座標に辿り着くまでの前記配線幅の配線経路を前記ネットグループごとに探索する探索工程と、
前記制御手段により、前記探索工程によって探索された配線経路間で相互に交差関係を有するネットグループの組み合わせを検出する検出工程と、
前記制御手段により、前記検出工程によって検出された組み合わせのネットグループがそれぞれ異なる配線層に割り当てられるように、前記設計対象回路が有する複数の配線層の中から前記各ネットグループに割り当てる配線層を決定する決定工程と、
前記制御手段により、前記決定工程によって決定された決定結果を出力する出力工程と、
を実行することを特徴とする設計支援方法。
【図面の簡単な説明】
【０１６０】
【図１】ネットグループの一例を示す説明図である。
【図２】設計対象回路の配線領域の一例を示す説明図である。
【図３】設計支援装置のハードウェア構成を示すブロック図である。
【図４】設計支援装置の機能的構成を示すブロック図である。
【図５】配線領域情報の具体例を示す説明図（その１）である。
【図６】配線領域情報の具体例を示す説明図（その２）である。
【図７】ネットグループ情報の具体例を示す説明図である。
【図８】探索結果の具体例を示す説明図（その１）である。
【図９】交差情報の具体例を示す説明図（その１）である。
【図１０】無向グラフの具体例を示す説明図（その１）である。
【図１１】決定結果の具体例を示す説明図（その１）である。
【図１２】探索結果の具体例を示す説明図（その２）である。
【図１３】配線経路情報の具体例を示す説明図（その１）である。
【図１４】配線経路情報の具体例を示す説明図（その２）である。
【図１５】交差情報の具体例を示す説明図（その２）である。
【図１６】無向グラフの具体例を示す説明図（その２）である。
【図１７】決定結果の具体例を示す説明図（その２）である。
【図１８】制約条件の具体例を示す説明図（その１）である。
【図１９】設計支援装置の設計支援処理手順の一例を示すフローチャートである。
【図２０】計数結果の具体例を示す説明図である。
【図２１】探索結果の具体例を示す説明図（その３）である。
【図２２】決定結果の具体例を示す説明図（その３）である。
【図２３】実施例１における設計支援処理手順の一例を示すフローチャートである。
【図２４】探索結果の具体例を示す説明図（その４）である。
【図２５】制約条件の具体例を示す説明図（その２）である。
【図２６】探索結果の具体例を示す説明図（その５）である。
【図２７】実施例３における設計支援処理手順の一例を示すフローチャートである。
【符号の説明】
【０１６１】
２００  配線領域
３００  設計支援装置
４０１  取得部
４０２  探索部
４０３  検出部
４０４  作成部
４０５  決定部
４０６  出力部
４０７  判断部
【図１】
0005125791.tif 000002
【図２】
0005125791.tif 000003
【図３】
0005125791.tif 000004
【図４】
0005125791.tif 000005
【図５】
0005125791.tif 000006
【図６】
0005125791.tif 000007
【図７】
0005125791.tif 000008
【図８】
0005125791.tif 000009
【図９】
0005125791.tif 000010
【図１０】
0005125791.tif 000011
【図１１】
0005125791.tif 000012
【図１２】
0005125791.tif 000013
【図１３】
0005125791.tif 000014
【図１４】
0005125791.tif 000015
【図１５】
0005125791.tif 000016
【図１６】
0005125791.tif 000017
【図１７】
0005125791.tif 000018
【図１８】
0005125791.tif 000019
【図１９】
0005125791.tif 000020
【図２０】
0005125791.tif 000021
【図２１】
0005125791.tif 000022
【図２２】
0005125791.tif 000023
【図２３】
0005125791.tif 000024
【図２４】
0005125791.tif 000025
【図２５】
0005125791.tif 000026
【図２６】
0005125791.tif 000027
【図２７】
0005125791.tif 000028