設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法
【課題】所定の配線領域内における仕様の回路特性を満たす配線長の配線を自動化することにより、作業負担の軽減化および設計期間の短縮化を図ること。
【解決手段】設計支援装置は、所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、所定の配線領域内でかつ該配線経路と非接続な巡回路とを探索し、探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出し、算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定し、判定された判定結果を出力する。これにより、探索困難な端子間の最長配線経路の換わりに、比較的に探索容易な端子間の任意の配線経路と巡回路とを合わせた最長配線経路候補を用いて、所定の配線領域における仕様の回路特性を満たす配線経路長の実現可能性を判定することができる。
【解決手段】設計支援装置は、所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、所定の配線領域内でかつ該配線経路と非接続な巡回路とを探索し、探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出し、算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定し、判定された判定結果を出力する。これにより、探索困難な端子間の最長配線経路の換わりに、比較的に探索容易な端子間の任意の配線経路と巡回路とを合わせた最長配線経路候補を用いて、所定の配線領域における仕様の回路特性を満たす配線経路長の実現可能性を判定することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ＬＳＩやプリント基板などの設計を支援する設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法に関する。
【背景技術】
【０００２】
ＬＳＩ設計におけるアナログ回路やプリント基板の配線の設計では、仕様の回路特性（Ｒ，Ｃ）を満たすため、また、ばらつきによる特性変動の影響を削減するために、ミクロン単位での配線制約が与えられる。例えば、差動回路においては、複数配線に対して等長の配線制約が与えられる。
【０００３】
一般に、このような配線制約を満たす配線を自動化することは難しいため、人手による試行錯誤を繰り返すことで各配線パターンを決定することとなる。このため、配線作業にかかる作業負担および作業時間が増大してしまい、設計期間の長期化を招く要因となっている。
【０００４】
そこで、配線作業を自動化する手法として、下記特許文献１には、複数の既配線回路データの中から最大配線長の配線経路を抽出し、当該配線経路とは異なる他の配線経路の配線長が上記最大配線長となるように、他の配線経路を変更することで、等長配線をおこなう手法が記載されている。
【０００５】
また、下記特許文献２には、スター型指定長配線をおこなう接続点のすべての接続点位置に基づいて所定の領域を作成し、上記領域内に所定の条件で経由点候補を生成する。そして、生成された経由点候補について上記接続点すべてがスター型指定長配線をおこなう際の配線条件を満足する経由点候補の中から経由点を探索し、その経由点からピンまでの指定長配線をおこなう手法が記載されている。
【０００６】
【特許文献１】特開昭６３−２７１６６１号公報
【特許文献２】特開平０８−３６５９６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した特許文献１，２に記載の従来技術では、複雑な配線禁止領域（障害物が存在する領域）を取り扱うことはできないという問題がある。なぜなら、配線領域上の障害物（トランジスタ、配線、ビアなど）が増加し設計ルールが複雑化すると、与えられた配線領域内で配線制約を満たす配線を実現することができるか否かを判断することが難しくなるからである。
【０００８】
このため、複雑な配線禁止領域を取り扱う場合には、結果的に人手による試行錯誤を繰り返すこととなり、依然として配線作業にかかる作業負担および作業時間が増大し、ひいては設計期間の長期化を招くという問題がある。
【０００９】
この発明は、上述した従来技術による問題点を解消するため、所定の配線領域内における仕様の回路特性を満たす配線長の配線を自動化することにより、作業負担の軽減化および設計期間の短縮化を図ることができる設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するため、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法は、所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、前記所定の配線領域内でかつ前記配線経路と非接続な巡回路とを探索し、探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出し、算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定し、判定された判定結果を出力することを要件とする。
【００１１】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、探索困難な端子間の最長配線経路の換わりに、端子間を接続する任意の配線経路と巡回路とを合わせた最長配線経路候補を用いて、所定の配線領域における仕様の回路特性を満たす配線経路長の実現可能性を判定することができる。
【００１２】
また、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法において、仕様の回路特性を満たす配線経路長以上と判定された場合、前記配線経路の一部と前記巡回路の一部とを通過して前記第１の端子から前記第２の端子に辿り着くまでの最長配線経路を探索し、探索された最長配線経路を出力することとしてもよい。
【００１３】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、配線経路長を最大限に維持しながら端子間の配線経路と巡回路とを４つの接続ポイントで繋ぎ換えることで、端子間の最長配線経路を探索することができる。
【００１４】
また、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法において、探索された最長配線経路の配線経路長を算出し、算出された最長配線経路の配線経路長が、前記仕様の回路特性を満たす配線経路長以上か否かを判定することとしてもよい。
【００１５】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、探索された最長配線経路の配線経路長を用いて再判定することで、所定の配線領域における仕様の回路特性を満たす配線経路長の実現可能性をより正確に判定することができる。
【００１６】
また、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法において、前記最長配線経路の配線経路長と、前記仕様の回路特性を満たす配線経路長との差分が予め設定された許容範囲内か否かを判定し、許容範囲外と判定された場合、前記最長配線経路を前記許容範囲内の配線経路長となるように変更し、変更された変更後の最長配線経路を出力することとしてもよい。
【００１７】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、所定の配線領域における仕様の回路特性を満たす配線経路長の配線を実現することができる。
【００１８】
また、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法において、前記所定の配線領域を、障害物を含まない第１の配線領域と、障害物を含む第２の配線領域とに分割し、分割された第１および第２の配線領域ごとに、探索処理、算出処理および判定処理を実行することとしてもよい。
【００１９】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、所定の配線領域を分割して対象となる配線領域を小さくすることで、実際の最長配線経路の配線経路長と、端子間の配線経路の配線経路長および巡回路の配線経路長を合わせた配線経路長との誤差を低減させることができる。
【００２０】
また、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法において、前記第１および第２の配線領域ごとに、探索処理、算出処理および判定処理が実行された結果、前記第１の配線領域内の第１の最長配線経路の一部と前記第２の配線領域内の第２の最長配線経路の一部とを通過して前記第１の端子から前記第２の端子に辿り着くまでの最長配線経路を探索することとしてもよい。
【００２１】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、端子間の最長配線経路を精度よく探索することで、所定の配線領域における仕様の回路特性を満たす配線経路長の実現可能性を正確に判定することができる。
【発明の効果】
【００２２】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、所定の配線領域内における仕様の回路特性を満たす配線長の配線を自動化することにより、作業負担の軽減化および設計期間の短縮化を図ることができるという効果を奏する。
【発明を実施するための最良の形態】
【００２３】
以下に添付図面を参照して、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法の好適な実施の形態を詳細に説明する。
【００２４】
（設計支援装置のハードウェア構成）
まず、本実施の形態にかかる設計支援装置のハードウェア構成について説明する。図１は、本実施の形態にかかる設計支援装置のハードウェア構成を示す説明図である。
【００２５】
図１において、設計支援装置１００は、コンピュータ本体１１０と、入力装置１２０と、出力装置１３０と、から構成されており、不図示のルータやモデムを介してＬＡＮ，ＷＡＮやインターネットなどのネットワーク１４０に接続可能である。
【００２６】
コンピュータ本体１１０は、ＣＰＵ，メモリ，インターフェースを有する。ＣＰＵは、設計支援装置１００の全体の制御を司る。メモリは、ＲＯＭ，ＲＡＭ，ＨＤ，光ディスク１１１，フラッシュメモリから構成される。メモリはＣＰＵのワークエリアとして使用される。
【００２７】
また、メモリには各種プログラムが格納されており、ＣＰＵからの命令に応じてロードされる。ＨＤおよび光ディスク１１１はディスクドライブによりデータのリード／ライトが制御される。また、光ディスク１１１およびフラッシュメモリはコンピュータ本体１１０に対し着脱自在である。インターフェースは、入力装置１２０からの入力、出力装置１３０への出力、ネットワーク１４０に対する送受信の制御をおこなう。
【００２８】
また、入力装置１２０としては、キーボード１２１、マウス１２２、スキャナ１２３などがある。キーボード１２１は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式であってもよい。マウス１２２は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。スキャナ１２３は、画像を光学的に読み取る。読み取られた画像は画像データとして取り込まれ、コンピュータ本体１１０内のメモリに格納される。なお、スキャナ１２３にＯＣＲ機能を持たせてもよい。
【００２９】
また、出力装置１３０としては、ディスプレイ１３１、スピーカ１３２、プリンタ１３３などがある。ディスプレイ１３１は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。また、スピーカ１３２は、効果音や読み上げ音などの音声を出力する。また、プリンタ１３３は、画像データや文書データを印刷する。
【００３０】
（本実施の形態の概要）
つぎに、本実施の形態の概要について説明する。本実施の形態では、ＬＳＩやプリント基板のレイアウト処理において、所定の配線領域内における仕様の回路特性を満たす配線長の配線を自動化することにより、作業負担の軽減化および設計期間の短縮化を図る。
【００３１】
ＬＳＩ設計におけるアナログ回路やプリント基板の配線の設計では、仕様の回路特性を満たすため、ミクロン単位での配線制約（指定長、等長配線など）が与えられる。ところが、ＬＳＩやプリント基板の高集積化により、配線領域上の障害物（トランジスタ、配線、ビアなど）が増加し設計ルールが複雑化している。
【００３２】
このため、端子間の配線形成のために割り付けられた配線領域内における端子間の最長経路探索が困難となり、該配線領域内における仕様の回路特性を満たす配線の実現可能性を判断することが難しくなっている。そこで、所定の配線領域内における仕様の回路特性を満たす配線の実現可能性を効率的かつ効果的に判断する手法を提案する。
【００３３】
まず、探索困難な端子間の最長経路の換わりに、巡回路を含む端子間の配線経路を最長経路候補として探索する。そして、その最長経路候補の配線長が、仕様の回路特性を満たす配線長以上であった場合に、仕様の回路特性を満たす配線が実現可能であると判断する。これは、巡回路を含む端子間の配線経路の配線長が、巡回路を含まない端子間の配線経路の配線長以上となるという特性を利用したものである。
【００３４】
換言すれば、巡回路を含む端子間の配線経路の配線長が、仕様の回路特性を満たす配線長未満であった場合には、配線制約を満たす配線は実現できないことを意味している。仕様の回路特性を満たす配線が実現不可能と判断された場合は、例えば、上流の工程に戻って各端子の配置位置を変更するなどの修正をおこなうこととなる。
【００３５】
一方で、仕様の回路特性を満たす配線が実現可能であると判断された場合には、その仕様の回路特性を満たす配線長に応じて、巡回路を含む配線経路を自動修正し、配線制約を満たす端子間の配線を実現する。これにより、複雑な配線禁止領域（障害物）を含む配線領域を扱うことが可能となり、仕様の回路特性を満たす配線長の配線を自動化することができる。
【００３６】
（配線領域の具体例）
ここで、端子間の配線経路を形成するために割り付けられる配線領域の具体例について説明する。図２は、配線領域の具体例を示す説明図である。図２において、配線領域２００は、ソースＳ（第１の端子）とターゲットＴ（第２の端子）とを接続する配線経路を形成するために割り付けられた配線領域である。
【００３７】
配線領域２００は、格子状に区切って９個のグリッドに分割されている。グリッドには、各グリッドを特定するためのラベルＲ１〜Ｒ９が付与されている。配線領域２００において、ラベルＲ８，Ｒ９が付与されたグリッド（図２中ハッチ部分）は、トランジスタ、配線、ビアなどの障害物が配置された配線禁止領域を示している。なお、配線領域２００を分割する格子サイズ（グリッドの大きさ）は、配線のプロセスによって決まる。
【００３８】
（配線情報のデータ構造）
つぎに、図２に示した配線領域に関する配線情報のデータ構造について説明する。図３は、配線情報のデータ構造を示す説明図である。図３において、配線情報３００は、グリッド数、ソースＳ、ターゲットＴ、配線禁止領域および各グリッドの座標位置に関する情報を有している。
【００３９】
グリッド数は、配線領域２００（図２参照）のＸ方向およびＹ方向のグリッド数を表わしている。ソースＳは、始点端子の配置位置を表わしている。ここでは、ラベルＲ７のグリッドに始点端子が配置されている。ターゲットＴは、終点端子の配置位置を表わしている。ここでは、ラベルＲ３のグリッドに終点端子が配置されている。
【００４０】
配線禁止領域は、トランジスタ、配線、ビアなどの障害物が配置され、新たな配線を形成することができないグリッドを表わしている。ここでは、ラベルＲ８，Ｒ９のグリッドが配線禁止領域となっている。また、配線情報３００には、各グリッドの座標位置を認識するための座標データ（例えば、図４に示す座標テーブル４００）が含まれている。
【００４１】
図４は、座標テーブルの記憶内容を示す説明図である。図４において、座標テーブル４００は、グリッドごとに、ラベル名および座標位置に関する情報を記憶している。この座標テーブル４００を参照することで、各グリッドの座標位置を認識することができる。例えば、ラベルＲ１のグリッドの座標位置は（Ｘ，Ｙ）＝（１，１）である。
【００４２】
（設計支援装置の機能的構成）
つぎに、設計支援装置１００の機能的構成について説明する。図５は、設計支援装置の機能的構成を示すブロック図である。図５において、設計支援装置１００は、探索部５０１と、算出部５０２と、判定部５０３と、出力部５０４と、変更部５０５と、分割部５０６と、を備えている。
【００４３】
これら各機能５０１〜５０６は、設計支援装置１００の記憶部に記憶された当該機能５０１〜５０６に関するプログラムをＣＰＵに実行させることにより、または、入出力Ｉ／Ｆにより、当該機能を実現することができる。また、各機能５０１〜５０６からの出力データは上記記憶部に保持される。また、図５中矢印で示した接続先の機能は、接続元の機能からの出力データを記憶部から読み込んで、当該機能に関するプログラムをＣＰＵに実行させるものとする。
【００４４】
まず、探索部５０１は、所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、所定の配線領域内でかつ配線経路と非接続な巡回路とを探索する機能を有する。所定の配線領域とは、設計対象回路内の２つの端子ごとに割り付けられる配線領域である。例えば、レイアウトツールを実行することで、第１および第２の端子に所定の配線領域を自動的に割り付けることができる。また、巡回路とは、ループ状の配線経路である。この順回路は、所定の配線領域内のうち第１および第２の端子を接続する配線経路が形成された領域を除く残余の領域に形成される。
【００４５】
具体的には、例えば、探索部５０１は、所定の配線領域に関する配線領域情報と、該配線領域内の配線禁止領域を表わす配線禁止情報と、第１および第２の端子に関する接続端子情報とに基づいて、第１および第２の端子を接続する配線経路と巡回路とを探索する。これら配線領域情報、配線禁止情報および接続端子情報として、例えば、図３に示した配線情報３００を用いることができる。なお、配線情報３００は、設計支援装置１００に直接入力することとしてもよく、また、不図示の外部装置からの取得、不図示のデータベースやライブラリからの抽出によって取得することとしてもよい。
【００４６】
ここで、探索部５０１による第１および第２の端子を接続する配線経路と巡回路とを探索する第１の探索処理の具体例について説明する。図６は、第１の探索処理の概要を示す説明図である。ここでは、配線領域６００内のソースＳとターゲットＴとを接続する配線経路と、配線領域６００内でかつ該配線経路と非接続な巡回路とを探索する。
【００４７】
まず、配線領域６００内の各グリッドがノード化され、ノード間をつなぐ各エッジに変数ｘ１〜ｘ１２が割り付けられたグラフ６１０を作成する。グラフ６１０における各ノードの配置位置は、配線領域６００における各グリッドの配置位置に対応している。例えば、ノードｅ１とソースＳが配置されたグリッドとが対応している。
【００４８】
以下、グラフ６１０を用いて、ソースＳからターゲットＴに辿り着くまでの配線経路および巡回路を探索する。なお、前提条件として、グラフ６１０内において、引き返しは不可とし、同じグリッドに２回辿り着いた時点で探索を終了することとする。
【００４９】
具体的には、巡回路を含む最長経路探索問題を線形計画問題にモデル化する。より具体的には、巡回路を含む最長経路探索問題を整数計画問題にモデル化し、その整数計画問題を線形計画問題に緩和する。まず、整数計画問題を定式化すると、目的関数は下記式（１）となり、制約式は下記式（２）〜（５）となる。ただし、ｄｉは区間ｉの距離である。また、ｘｉ＝１は区間ｉを通過、ｘｉ＝０は区間ｉを通過しないことを意味している。
【００５０】
ｍａｘ．Σ｛ｄｉ・ｘｉ｜ｉは区間｝ …（１）
【００５１】
Σ｛ｅｉ｜ｉは終端ノード｝＝２ …（２）
【００５２】
ｂｉ∈｛０，２｝（ただし、ｂｉは任意の分岐ノード） …（３）
【００５３】
ｅｉ∈｛１｝（ただし、ｅｉは２つの始点終点ノード） …（４）
【００５４】
ｘｉ∈｛０，１｝（ただし、ｘｉは任意のエッジ） …（５）
【００５５】
つぎに、この整数計画問題を線形計画問題に緩和する。具体的には、上記の制約式を線形計画制約によって表現する。ここで、グラフ６１０内の代表ノード（始点終点ノード、３分岐ノード、４分岐ノード）を例に挙げて、上記式（３）および（５）を線形計画制約によって表現した制約式について説明する。
【００５６】
まず、グラフ６１０内のノードｅ１（始点ノード）を例に挙げると、制約式は『＋ｘ１＋ｘ７＝１，０≦ｘ１≦１，０≦ｘ７≦１』となる。つぎに、ノードｅ２（終点ノード）を例に挙げると、制約式は『＋ｘ６＋ｘ１２＝１，０≦ｘ６≦１，０≦ｘ１２≦１』となる。
【００５７】
つぎに、ノードｂ３（３分岐）を例に挙げると、『−ｘ３＋ｘ７＋ｘ８≧０，＋ｘ３−ｘ７＋ｘ８≧０，＋ｘ３＋ｘ７−ｘ８≧０，＋ｘ３＋ｘ７＋ｘ８≦２，０≦ｘ３≦１，０≦ｘ７≦１，０≦ｘ８≦１』となる。
【００５８】
つぎに、ノードｂ４（４分岐）を例に挙げると、『−ｘ３＋ｘ４＋ｘ９＋ｘ１０≧０，＋ｘ３−ｘ４＋ｘ９＋ｘ１０≧０，＋ｘ３＋ｘ４−ｘ９＋ｘ１０≧０，＋ｘ３＋ｘ４＋ｘ９−ｘ１０≧０，＋ｘ３＋ｘ４＋ｘ９＋ｘ１０≦２，０≦ｘ３≦１，０≦ｘ４≦１，０≦ｘ９≦１，０≦ｘ１０≦１』となる。
【００５９】
このあと、上記式（１）で示した目的関数と、グラフ６１０内のノードごとに線形計画制約で表現した制約式と、を線形計画ソルバに入力することで、ソースＳからターゲットＴに辿り着くまでの巡回路を含む最長経路を求めることができる。なお、線形計画問題に緩和したため、各変数は必ずしも０または１に収束しない。このため、ここでは０と１の間の中間値をとる変数を、近傍の配線と接続されるように０または１に修正することとする。
【００６０】
ここで、第１の探索処理の探索結果の具体例について説明する。図７は、第１の探索処理の探索結果の具体例を示す説明図である。図７において、配線領域６００には、第１の探索処理の探索結果である、ソースＳとターゲットＴとを接続する配線経路７１０と巡回路７２０とが示されている。
【００６１】
図５の説明に戻り、算出部５０２は、探索部５０１によって探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出する機能を有する。具体的には、例えば、配線経路および巡回路が通過するグリッド数を配線経路長とすることとしてもよく、また、上記式（１）を用いて求めた値を配線経路長とすることとしてもよい。
【００６２】
判定部５０３は、算出部５０２によって算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する機能を有する。仕様の回路特性を満たす配線経路長とは、例えば、設計対象回路の仕様として規定された配線制約であり、特定の配線経路長である。なお、仕様の回路特性を満たす配線経路長は、例えば、ＲＯＭやＲＡＭなどの記憶部に記憶されている。
【００６３】
出力部５０４は、判定部５０３によって判定された判定結果を出力する機能を有する。例えば、仕様の回路特性を満たす配線経路長未満と判定された場合には、割り付けられた配線領域内で仕様の回路特性を満たす配線経路長を満たすことができない旨のエラーメッセージを出力することとしてもよい。なお、出力部５０４による出力形式は、ディスプレイ１３１での画面表示、プリンタ１３３での印刷出力、メモリへのデータ出力（保存）、外部のコンピュータ装置への送信のいずれであってもよい。
【００６４】
設計者は、このエラーメッセージを確認することで、第１および第２の端子に割り付けられた配線領域内において配線制約を満たす配線が実現できないことを認識することができる。これにより、上流の工程に戻って第１および第２の端子の配置位置を変更するなどの対策を適切かつ迅速におこなうことができる。
【００６５】
また、探索部５０１は、判定部５０３によって配線経路長以上と判定された場合、配線経路の一部と巡回路の一部とを通過して第１の端子から第２の端子に辿り着くまでの最長配線経路を探索する機能を有する。具体的には、４つの接続ポイントで配線経路と巡回路とを繋ぎ換えることで、最大限に配線経路長を維持した単一の最長配線経路を探索する。
【００６６】
ここで、探索部５０１による最長配線経路を探索する第２の探索処理の具体例について説明する。ここでは、図７に示した探索結果を例に挙げて説明する。図８は、第２の探索処理の概要を示す説明図である。最長配線経路を探索する場合、図８に示すターンアウトスイッチグラフ（以下、「Ｔｓグラフ」と表記）８００を作成する。
【００６７】
Ｔｓグラフ８００は、配線経路７１０と巡回路７２０とを繋ぎ換える際の接続可能ポイントが表現されたグラフである。具体的には、まず、配線領域６００を区切る境界線の中から、配線経路７１０と巡回路７２０との間の境界線を検出する。例えば、配線経路７１０のソースＳからターゲットＴに辿り着くまでのグリッドごとに、巡回路７２０との間の境界線を検出する。そして、境界線が検出された都度、その境界線にエッジＩＤを割り付ける。
【００６８】
ここで、ソースＳが配置されたグリッドを例に挙げると、巡回路７２０との間の境界線８１０を検出し、その境界線８１０にエッジａを割り付ける。このように、境界線が検出された都度、エッジＩＤ（図８では、エッジａ〜ｄ）を割り付けることで、配線経路７１０と巡回路７２０との間の境界線を認識することができる。
【００６９】
このあと、配線経路７１０、巡回路７２０、エッジａ〜ｄがノード化されたＴｓグラフ８００を作成する。具体的には、配線経路７１０を表わすノードＮ１と、巡回路７２０を表わすノードＮ２とが、エッジａ〜ｄを表わすノードＮａ〜Ｎｄを介して接続されたＴｓグラフ８００を作成する。
【００７０】
つぎに、配線経路７１０および巡回路７２０の原点を設定する。原点の位置は任意に設定可能である。ここでは、配線経路７１０の原点をソースＳ（以下、「原点Ｓ」と表記）に設定し、巡回路７２０の原点を点Ａ（以下、「原点Ａ」と表記）に設定する。
【００７１】
さらに、配線経路７１０の経路上を辿って原点Ｓから各エッジａ〜ｄに辿り着くまでの距離を求めて、ノード間をつなぐ各枝に設定する。例えば、原点Ｓからエッジａまでの距離は「０」のため、ノードＮ１とノードＮａとをつなぐ枝に「０」を設定する。また、原点Ｓからエッジｄまでの距離は「４」のため、ノードＮ１とノードＮｄとをつなぐ枝に「４」を設定する。
【００７２】
同様に、巡回路７２０の経路上を辿って原点Ａから各エッジａ〜ｄに辿り着くまでの距離を求めて、ノード間をつなぐ各枝に設定する。このとき、時計回りに巡回路７２０の経路上を辿ることとする。例えば、原点Ａからエッジａまでの距離は「１」のため、ノードＮ２とノードＮａとをつなぐ枝に「１」を設定する。また、原点Ａからエッジｄまでの距離は「３」のため、ノードＮ２とノードＮｄとをつなぐ枝に「３」を設定する。
【００７３】
ここで、Ｔｓグラフ８００を表わす具体的なグラフ情報のデータ構造について説明する。図９および図１０は、グラフ情報のデータ構造を示す説明図である。図９において、グラフ情報９００は、ノードＮ１，Ｎ２，Ｎａ〜Ｎｄごとに、ノード名、フラグおよびノードタイプに関する情報を有している。例えば、ノードＮ１は、フラグがＯＮに設定された配線経路である。フラグに関する詳細な説明は後述する。
【００７４】
また、図１０において、グラフ情報１０００は、ノードＮ１，Ｎ２ごとに、境界線を表わすノードＮａ〜Ｎｄとの距離に関する情報を有している。このグラフ情報１０００を参照することで、ノード間の距離を特定することができる。上述したＴｓグラフ８００は、図９および図１０に示したグラフ情報９００，１０００によって表現することができる。
【００７５】
つぎに、グラフ情報９００，１０００を用いて、配線経路７１０の一部と巡回路７２０の一部とを通過してソースＳからターゲットＴまで辿り着くまでの最長配線経路を探索する。まず、グラフ情報９００の全ノードのフラグをＯＦＦに設定する。つぎに、ソースＳ，ターゲットＴを含むノードＮ１のフラグをＯＮに設定する。
【００７６】
このあと、グラフ情報１０００が有するノード間の距離を用いて、ノードＮ１→ノードＮ２→ノードＮ１と遷移した場合に、最も迂回の小さい戻り経路を探索する。具体的には、ノードＮａ〜Ｎｄの中から、ノードＮ１からノードＮ２に遷移する際に経由する接続ポイントおよびノードＮ２からノードＮ１に遷移する際に経由する接続ポイントとなる２つのノードＮａ〜Ｎｄを選択し、ノードＮ１→ノードＮ２→ノードＮ１と遷移した場合のコストを計算する。
【００７７】
例えば、ノードＮａ〜Ｎｄの中からノードＮａ，Ｎｂが選択されたとすると、ノードＮ１→ノードＮａ→ノードＮ２→ノードＮｂ→ノードＮ１と遷移する場合のコストを計算する。具体的には、Ｎ１−Ｎａ間の距離（０）とＮ２−Ｎａ間の距離（１）とを加算した値（１）から、Ｎ２−Ｎｂ間の距離（２）とＮ１−Ｎｂ間の距離（１）とを加算した値（３）を減算した値（−２）をコストとする。
【００７８】
具体的には、Ｎ１−Ｎａ間の距離（０）とＮ２−Ｎａ間の距離（１）とを加算した値（１）は、配線経路７１０と巡回路７２０とを繋ぎ換えた際に増加する配線経路長である。また、Ｎ２−Ｎｂ間の距離（２）とＮ１−Ｎｂ間の距離（１）とを加算した値（３）は、配線経路７１０と巡回路７２０とを繋ぎ換えた際に減少する配線経路長である。
【００７９】
このコストを接続ポイントとなる全組み合わせ『Ｎａ−Ｎｂ，Ｎａ−Ｎｃ，Ｎａ−Ｎｄ，Ｎｂ−Ｎｃ，Ｎｂ−Ｎｄ，Ｎｃ−Ｎｄ』について求めて、コストが最大（配線経路長の減少分が最小）の組み合わせを接続ポイントの組み合わせとして決定する。ここでは、『Ｎａ−Ｎｂ』の組み合わせが、最大のコストとなる。この結果、ノードＮ１→ノードＮａ→ノードＮ２→ノードＮｂ→ノードＮ１の遷移に従って、配線領域６００内のグリッドを辿る配線経路を最長配線経路に決定する。
【００８０】
ここで、第２の探索処理の探索結果の具体例について説明する。図１１は、第２の探索処理の探索結果の具体例を示す説明図である。図１１において、符号１１００は、配線経路７１０の一部と巡回路７２０の一部とを通過してソースＳからターゲットＴまで辿り着くまでの最長配線経路（上述したノードＮ１→ノードＮａ→ノードＮ２→ノードＮｂ→ノードＮ１に相当）である。
【００８１】
なお、巡回路７２０と隣接する他の巡回路が存在する場合には、最長配線経路１１００が探索された結果、さらに、最長配線経路１１００の一部と他の巡回路の一部とを通過してソースＳからターゲットＴまで辿り着くまでの最長配線経路を探索することとなる。
【００８２】
図１２は、複数の巡回路の一部を通過する最長配線経路の一例を示す説明図である。図１２において、（１）には、ソースＳとターゲットＴとを接続する配線経路Ｈおよび巡回路Ｊ１〜Ｊｎが示されている。この場合、配線経路Ｈと隣接する巡回路Ｊ１から順に探索部５０１による第２の探索処理を実行して、ソースＳからターゲットＴに辿り着くまでの最長配線経路を探索する。
【００８３】
この結果、（２）に示すように、配線経路Ｈの一部と巡回路Ｊ１〜Ｊｎの一部（Ｊ’１〜Ｊ’ｎ）とを通過してソースＳからターゲットＴに辿り着くまでの最長配線経路Ｉが探索される。このとき、探索が終了した巡回路Ｊ１〜Ｊｎのフラグ（グラフ情報９００のフラグに相当）をＯＮに設定することにより、未探索の巡回路Ｊ１〜Ｊｎを認識することができる。
【００８４】
図５の説明に戻り、出力部５０４は、探索部５０１によって探索された最長配線経路を出力する機能を有する。具体的には、例えば、最長配線経路が通過するグリッドを特定するラベルの接続関係を表わす探索結果を出力することとしてもよい。ここで、出力部５０４によって出力される出力例について説明する。
【００８５】
図１３は、探索結果の出力例を示す説明図である。図１３において、最長配線経路１１００（図１１参照）を表わす探索結果１３００が示されている。探索結果１３００は、接続関係を有するグリッドを特定するラベル情報を有している。
【００８６】
これにより、最長配線経路１１００は、Ｒ７→Ｒ８→Ｒ９→Ｒ６→Ｒ５→Ｒ４→Ｒ１→Ｒ２→Ｒ３を通過する配線経路であると特定することができる。なお、各ラベルＲ１〜Ｒ９の座標位置は、配線領域の配線情報に含まれている座標テーブルを参照することで認識することができる。
【００８７】
また、算出部５０２は、探索部５０１によって探索された最長配線経路の配線経路長を算出する機能を有する。そして、判定部５０３は、算出部５０２によって算出された最長配線経路の配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する機能を有する。
【００８８】
すなわち、配線経路と巡回路とを繋ぎ換えることで単一の最長配線経路が探索された結果、仕様の回路特性を満たす配線経路長を実現できるか否かを判定する。ここで、仕様の回路特性を満たす配線経路長未満と判定された場合には、例えば、上述したエラーメッセージを出力することとしてもよい。
【００８９】
また、判定部５０３は、最長配線経路の配線経路長と、仕様の回路特性を満たす配線経路長との差分が予め設定された許容範囲内か否かを判定することとしてもよい。具体的には、配線制約として、指定配線経路長と完全一致ではなく、回路特性を満たす程度の誤差を許容範囲として設定する。許容範囲は、例えば、図１に示したキーボード１２１やマウス１２２などの入力装置１２０をユーザが操作することで、任意に設定可能である。
【００９０】
また、変更部５０５は、判定部５０３によって許容範囲外と判定された場合、最長配線経路を許容範囲内の配線経路長となるように変更する機能を有する。具体的には、例えば、図１２に示した最長配線経路Ｉの一部であるＪ’１〜Ｊ’ｎを、末端のＪ’ｎから順に切り離すことで最長配線経路Ｉの配線経路長を調整することとしてもよい。
【００９１】
さらに、例えば、末端のＪ’ｎを切り離した結果、最長配線経路Ｉの配線経路長が、仕様の回路特性を満たす配線経路長よりも短くなった場合には、最長配線経路Ｉの一部を所定の配線領域内の空き領域で迂回させて配線経路長を調整することとしてもよい。また、出力部５０４は、変更部５０５によって変更された変更後の最長配線経路を出力する機能を有する。
【００９２】
分割部５０６は、所定の配線領域を、障害物を含まない第１の配線領域と、障害物を含む第２の配線領域とに分割する機能を有する。これは、配線経路の配線経路長および巡回路の配線経路長を合わせた配線経路長と、実際の最長配線経路の配線経路長との誤差を低減させるためにおこなう。特に、大規模な配線領域を扱う場合に有効である。
【００９３】
具体的には、例えば、分割部５０６は、配線情報３００に基づいて、所定の配線領域を区切る境界線に沿ってカットラインを設定することで、障害物を含まない第１の配線領域と、障害物を含む第２の配線領域とに分割する。このとき、例えば、障害物（配線禁止領域）を含まない領域ができる限り広くなるように所定の配線領域を分割することとしてもよい。
【００９４】
また、カットラインの設定位置は、例えば、配線禁止領域から１グリッド以上離した位置に設定することとしてもよい。どうしても配線禁止領域に接する位置にカットラインを設定しなければならない場合には、２つの配線禁止領域の間に配線可能領域が存在する状況が連続するのを回避することとしてもよい。
【００９５】
なお、配線領域上のカットラインの設定位置を表わすカットライン情報は、例えば、グリッドの座標位置によって表現することとしてもよい。このカットライン情報は、分割部５０６によって分割された結果、上記記憶部に記憶される。そして、カットライン情報を記憶部から読み出すことで、第１および第２の配線領域を認識することができる。
【００９６】
また、上記探索部５０１、算出部５０２および判定部５０３は、分割部５０６によって所定の配線領域が第１および第２の配線領域に分割された場合、第１および第２の配線領域ごとに、探索処理、算出処理および判定処理を実行することとなる。ここで、所定の配線領域内を第１および第２の配線領域に分割した場合の一連の処理の流れについて説明する。
【００９７】
図１４は、分割時の一連の処理の流れを示す説明図である。図１４において、配線領域１４００が、カットラインＣにより第１の配線領域１４１０と第２の配線領域１４２０とに分割されている。また、第１の配線領域１４１０内に配線経路１４３０が、第２の配線領域１４２０内に巡回路１４４０が探索済みである。
【００９８】
ここでは、カットラインＣに接する配線禁止領域（ラベルＲ１６，Ｒ１７，Ｒ１９）の間に配線可能領域Ｒ１５，Ｒ１７が存在している。この場合、これら配線可能領域Ｒ１５，Ｒ１７を仮想端子Ｖ１，Ｖ２として扱うことで、配線経路１４３０と巡回路１４４０とを接続する。この結果、配線経路１４５０と巡回路１４６０，１４７０とが探索される。
【００９９】
最後に、配線経路１４５０の一部と巡回路１４６０の一部と、巡回路１４７０の一部とを通過してソースＳからターゲットＴに辿り着くまでの最長配線経路１４８０を探索する。なお、最長配線経路１４８０が探索された結果、変更部５０５により、最長配線経路１４８０を仕様の回路特性を満たす配線経路長となるように変更することとしてもよい。
【０１００】
（設計支援装置の設計支援処理手順）
つぎに、本実施の形態にかかる設計支援装置１００の設計支援処理手順について説明する。図１５は、設計支援装置の設計支援処理手順の一例を示すフローチャートである。図１５のフローチャートにおいて、まず、所定の配線領域に関する配線情報が入力されたか否かを判断する（ステップＳ１５０１）。
【０１０１】
ここで、配線情報が入力されるのを待って（ステップＳ１５０１：Ｎｏ）、入力された場合（ステップＳ１５０１：Ｙｅｓ）、探索部５０１により、所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、所定の配線領域内でかつ該配線経路と非接続な巡回路とを探索する第１の探索処理を実行する（ステップＳ１５０２）。
【０１０２】
このあと、算出部５０２により、ステップＳ１５０２において探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出する（ステップＳ１５０３）。そして、判定部５０３により、ステップＳ１５０３において算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する（ステップＳ１５０４）。
【０１０３】
ここで、仕様の回路特性を満たす配線経路長以上であった場合（ステップＳ１５０４：Ｙｅｓ）、探索部５０１により、配線経路の一部と巡回路の一部とを通過して第１の端子から第２の端子に辿り着くまでの最長配線経路を探索する第２の探索処理を実行する（ステップＳ１５０５）。
【０１０４】
このあと、算出部５０２により、ステップＳ１５０５において探索された最長配線経路の配線経路長を算出する（ステップＳ１５０６）。そして、判定部５０３により、ステップＳ１５０６において算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する（ステップＳ１５０７）。
【０１０５】
ここで、仕様の回路特性を満たす配線経路長以上であった場合（ステップＳ１５０７：Ｙｅｓ）、判定部５０３により、最長配線経路の配線経路長と、仕様の回路特性を満たす配線経路長との差分が予め設定された許容範囲内か否かを判定する（ステップＳ１５０８）。
【０１０６】
ここで、許容範囲外だった場合（ステップＳ１５０８：Ｎｏ）、変更部５０５により、最長配線経路を許容範囲内の配線経路長となるように変更し（ステップＳ１５０９）、ステップＳ１５０８に戻る。一方、許容範囲内だった場合（ステップＳ１５０８：Ｙｅｓ）、出力部５０４により、最長配線経路を出力して（ステップＳ１５１０）、本フローチャートによる一連の処理を終了する。
【０１０７】
また、ステップＳ１５０４において配線経路長未満であった場合（ステップＳ１５０４：Ｎｏ）、または、ステップＳ１５０７において配線経路長未満であった場合（ステップＳ１５０７：Ｎｏ）、出力部５０４により、仕様の回路特性を満たす配線経路長を満たすことができない旨のエラーメッセージを出力して（ステップＳ１５１１）、本フローチャートによる一連の処理を終了する。
【０１０８】
つぎに、図１５に示したステップＳ１５０２における第１の探索処理の具体的処理手順について説明する。図１６は、第１の探索処理の具体的処理手順の一例を示すフローチャートである。これは、巡回路を含む最長経路探索問題を線形計画問題にモデル化した場合の一例である。
【０１０９】
図１６のフローチャートにおいて、まず、所定の配線領域内の各グリッドがノード化され、ノード間をつなぐ各エッジに変数が割り付けられたグラフを作成する（ステップＳ１６０１）。このあと、巡回路を含む最長経路探索問題を線形計画問題にモデル化することで、目的関数および制約式を求める（ステップＳ１６０２）。
【０１１０】
そして、ステップＳ１６０２において求めた目的関数および制約式を線形計画ソルバに入力することで（ステップＳ１６０３）、所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、所定の配線領域内でかつ上記配線経路と非接続な巡回路とを決定し（ステップＳ１６０４）、図１５に示したステップＳ１５０３に移行する。
【０１１１】
つぎに、図１５に示したステップＳ１５０５における第２の探索処理の具体的処理手順について説明する。図１７は、第２の探索処理の具体的処理手順の一例を示すフローチャートである。これは、Ｔｓグラフ（例えば、Ｔｓグラフ８００）を用いて、最長配線経路を探索する場合の一例である。
【０１１２】
図１７のフローチャートにおいて、まず、第１および第２の端子を接続する配線経路と巡回路とを繋ぎ換える際の接続可能ポイントが表現されたＴｓグラフを作成する（ステップＳ１７０１）。このあと、ステップＳ１７０１において作成されたＴｓグラフを用いて、上記配線経路を表わすノードと巡回路を表わすノードとの間を遷移する際に経由する接続ポイントの組み合わせごとのコストを算出する（ステップＳ１７０２）。
【０１１３】
そして、ステップＳ１７０２において算出された組み合わせごとのコストに基づいて、上記配線経路の一部と巡回路の一部とを通過して第１の端子から第２の端子に辿り着くまでの最長配線経路を決定して（ステップＳ１７０３）、図１５に示したステップＳ１５０６に移行する。
【０１１４】
なお、図１５に示したステップＳ１５０２において所定の配線領域内に複数の巡回路が探索された場合には、未探索の巡回路がなくなるまで、第１および第２の端子を接続する配線経路と隣接する巡回路から順にステップＳ１７０１〜ステップＳ１７０３の繰り返し実行することとなる。
【０１１５】
以上説明したように、本実施の形態によれば、探索困難な端子間の最長配線経路の換わりに、比較的に探索容易な端子間の任意の配線経路と巡回路とを合わせた最長配線経路候補を用いて、所定の配線領域における仕様の回路特性を満たす配線経路長の実現可能性を判定することができる。
【０１１６】
そして、仕様の回路特性を満たす配線経路長の実現可能な場合は、端子間の任意の配線経路と巡回路とを用いて、端子間の最長配線経路を探索することができる。さらに、仕様の回路特性を満たす配線経路長に従って最長配線経路を自動修正することで、所定の配線領域における仕様の回路特性を満たす配線経路長の配線を実現することができる。
【０１１７】
また、所定の配線領域を分割して対象となる配線領域を小さくすることで、実際の最長配線経路の配線経路長と、最長配線経路候補の配線経路長との誤差を低減させることができる。この結果、端子間の最長配線経路を精度よく探索でき、所定の配線領域における仕様の回路特性を満たす配線経路長の実現可能性を正確に判定することができる。
【０１１８】
このように、仕様の回路特性を満たす適切な配線をおこなうことで、無駄な配線リソースを削減し、設計対象回路の小型化を実現することができる。さらに、所定の配線領域における仕様の回路特性を満たす配線長の配線を自動化することにより、作業負担の軽減化および設計期間の短縮化を図ることができる。
【０１１９】
なお、本実施の形態で説明した設計支援方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネットなどのネットワークを介して配布することが可能な伝送媒体であってもよい。
【０１２０】
また、本実施の形態で説明した設計支援装置１００は、スタンダードセルやストラクチャードＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ）によっても実現することができる。具体的には、たとえば、上述した設計支援装置１００の機能５０１〜５０６をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、設計支援装置１００を製造することができる。
【図面の簡単な説明】
【０１２１】
【図１】本実施の形態にかかる設計支援装置のハードウェア構成を示す説明図である。
【図２】配線領域の具体例を示す説明図である。
【図３】配線情報のデータ構造を示す説明図である。
【図４】座標テーブルの記憶内容を示す説明図である。
【図５】設計支援装置の機能的構成を示すブロック図である。
【図６】第１の探索処理の概要を示す説明図である。
【図７】第１の探索処理の探索結果の具体例を示す説明図である。
【図８】第２の探索処理の概要を示す説明図である。
【図９】グラフ情報のデータ構造を示す説明図（その１）である。
【図１０】グラフ情報のデータ構造を示す説明図（その２）である。
【図１１】第２の探索処理の探索結果の具体例を示す説明図である。
【図１２】複数の巡回路の一部を通過する最長配線経路の一例を示す説明図である。
【図１３】探索結果の出力例を示す説明図である。
【図１４】分割時の一連の処理の流れを示す説明図である。
【図１５】設計支援装置の設計支援処理手順の一例を示すフローチャートである。
【図１６】第１の探索処理の具体的処理手順の一例を示すフローチャートである。
【図１７】第２の探索処理の具体的処理手順の一例を示すフローチャートである。
【符号の説明】
【０１２２】
１００ 設計支援装置
２００，６００ 配線領域
３００ 配線情報
４００ 座標テーブル
５０１ 探索部
５０２ 算出部
５０３ 判定部
５０４ 出力部
５０５ 変更部
５０６ 分割部
【技術分野】
【０００１】
この発明は、ＬＳＩやプリント基板などの設計を支援する設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法に関する。
【背景技術】
【０００２】
ＬＳＩ設計におけるアナログ回路やプリント基板の配線の設計では、仕様の回路特性（Ｒ，Ｃ）を満たすため、また、ばらつきによる特性変動の影響を削減するために、ミクロン単位での配線制約が与えられる。例えば、差動回路においては、複数配線に対して等長の配線制約が与えられる。
【０００３】
一般に、このような配線制約を満たす配線を自動化することは難しいため、人手による試行錯誤を繰り返すことで各配線パターンを決定することとなる。このため、配線作業にかかる作業負担および作業時間が増大してしまい、設計期間の長期化を招く要因となっている。
【０００４】
そこで、配線作業を自動化する手法として、下記特許文献１には、複数の既配線回路データの中から最大配線長の配線経路を抽出し、当該配線経路とは異なる他の配線経路の配線長が上記最大配線長となるように、他の配線経路を変更することで、等長配線をおこなう手法が記載されている。
【０００５】
また、下記特許文献２には、スター型指定長配線をおこなう接続点のすべての接続点位置に基づいて所定の領域を作成し、上記領域内に所定の条件で経由点候補を生成する。そして、生成された経由点候補について上記接続点すべてがスター型指定長配線をおこなう際の配線条件を満足する経由点候補の中から経由点を探索し、その経由点からピンまでの指定長配線をおこなう手法が記載されている。
【０００６】
【特許文献１】特開昭６３−２７１６６１号公報
【特許文献２】特開平０８−３６５９６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述した特許文献１，２に記載の従来技術では、複雑な配線禁止領域（障害物が存在する領域）を取り扱うことはできないという問題がある。なぜなら、配線領域上の障害物（トランジスタ、配線、ビアなど）が増加し設計ルールが複雑化すると、与えられた配線領域内で配線制約を満たす配線を実現することができるか否かを判断することが難しくなるからである。
【０００８】
このため、複雑な配線禁止領域を取り扱う場合には、結果的に人手による試行錯誤を繰り返すこととなり、依然として配線作業にかかる作業負担および作業時間が増大し、ひいては設計期間の長期化を招くという問題がある。
【０００９】
この発明は、上述した従来技術による問題点を解消するため、所定の配線領域内における仕様の回路特性を満たす配線長の配線を自動化することにより、作業負担の軽減化および設計期間の短縮化を図ることができる設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するため、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法は、所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、前記所定の配線領域内でかつ前記配線経路と非接続な巡回路とを探索し、探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出し、算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定し、判定された判定結果を出力することを要件とする。
【００１１】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、探索困難な端子間の最長配線経路の換わりに、端子間を接続する任意の配線経路と巡回路とを合わせた最長配線経路候補を用いて、所定の配線領域における仕様の回路特性を満たす配線経路長の実現可能性を判定することができる。
【００１２】
また、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法において、仕様の回路特性を満たす配線経路長以上と判定された場合、前記配線経路の一部と前記巡回路の一部とを通過して前記第１の端子から前記第２の端子に辿り着くまでの最長配線経路を探索し、探索された最長配線経路を出力することとしてもよい。
【００１３】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、配線経路長を最大限に維持しながら端子間の配線経路と巡回路とを４つの接続ポイントで繋ぎ換えることで、端子間の最長配線経路を探索することができる。
【００１４】
また、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法において、探索された最長配線経路の配線経路長を算出し、算出された最長配線経路の配線経路長が、前記仕様の回路特性を満たす配線経路長以上か否かを判定することとしてもよい。
【００１５】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、探索された最長配線経路の配線経路長を用いて再判定することで、所定の配線領域における仕様の回路特性を満たす配線経路長の実現可能性をより正確に判定することができる。
【００１６】
また、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法において、前記最長配線経路の配線経路長と、前記仕様の回路特性を満たす配線経路長との差分が予め設定された許容範囲内か否かを判定し、許容範囲外と判定された場合、前記最長配線経路を前記許容範囲内の配線経路長となるように変更し、変更された変更後の最長配線経路を出力することとしてもよい。
【００１７】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、所定の配線領域における仕様の回路特性を満たす配線経路長の配線を実現することができる。
【００１８】
また、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法において、前記所定の配線領域を、障害物を含まない第１の配線領域と、障害物を含む第２の配線領域とに分割し、分割された第１および第２の配線領域ごとに、探索処理、算出処理および判定処理を実行することとしてもよい。
【００１９】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、所定の配線領域を分割して対象となる配線領域を小さくすることで、実際の最長配線経路の配線経路長と、端子間の配線経路の配線経路長および巡回路の配線経路長を合わせた配線経路長との誤差を低減させることができる。
【００２０】
また、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法において、前記第１および第２の配線領域ごとに、探索処理、算出処理および判定処理が実行された結果、前記第１の配線領域内の第１の最長配線経路の一部と前記第２の配線領域内の第２の最長配線経路の一部とを通過して前記第１の端子から前記第２の端子に辿り着くまでの最長配線経路を探索することとしてもよい。
【００２１】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、端子間の最長配線経路を精度よく探索することで、所定の配線領域における仕様の回路特性を満たす配線経路長の実現可能性を正確に判定することができる。
【発明の効果】
【００２２】
この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法によれば、所定の配線領域内における仕様の回路特性を満たす配線長の配線を自動化することにより、作業負担の軽減化および設計期間の短縮化を図ることができるという効果を奏する。
【発明を実施するための最良の形態】
【００２３】
以下に添付図面を参照して、この設計支援プログラム、該プログラムを記録した記録媒体、設計支援装置、および設計支援方法の好適な実施の形態を詳細に説明する。
【００２４】
（設計支援装置のハードウェア構成）
まず、本実施の形態にかかる設計支援装置のハードウェア構成について説明する。図１は、本実施の形態にかかる設計支援装置のハードウェア構成を示す説明図である。
【００２５】
図１において、設計支援装置１００は、コンピュータ本体１１０と、入力装置１２０と、出力装置１３０と、から構成されており、不図示のルータやモデムを介してＬＡＮ，ＷＡＮやインターネットなどのネットワーク１４０に接続可能である。
【００２６】
コンピュータ本体１１０は、ＣＰＵ，メモリ，インターフェースを有する。ＣＰＵは、設計支援装置１００の全体の制御を司る。メモリは、ＲＯＭ，ＲＡＭ，ＨＤ，光ディスク１１１，フラッシュメモリから構成される。メモリはＣＰＵのワークエリアとして使用される。
【００２７】
また、メモリには各種プログラムが格納されており、ＣＰＵからの命令に応じてロードされる。ＨＤおよび光ディスク１１１はディスクドライブによりデータのリード／ライトが制御される。また、光ディスク１１１およびフラッシュメモリはコンピュータ本体１１０に対し着脱自在である。インターフェースは、入力装置１２０からの入力、出力装置１３０への出力、ネットワーク１４０に対する送受信の制御をおこなう。
【００２８】
また、入力装置１２０としては、キーボード１２１、マウス１２２、スキャナ１２３などがある。キーボード１２１は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式であってもよい。マウス１２２は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。スキャナ１２３は、画像を光学的に読み取る。読み取られた画像は画像データとして取り込まれ、コンピュータ本体１１０内のメモリに格納される。なお、スキャナ１２３にＯＣＲ機能を持たせてもよい。
【００２９】
また、出力装置１３０としては、ディスプレイ１３１、スピーカ１３２、プリンタ１３３などがある。ディスプレイ１３１は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。また、スピーカ１３２は、効果音や読み上げ音などの音声を出力する。また、プリンタ１３３は、画像データや文書データを印刷する。
【００３０】
（本実施の形態の概要）
つぎに、本実施の形態の概要について説明する。本実施の形態では、ＬＳＩやプリント基板のレイアウト処理において、所定の配線領域内における仕様の回路特性を満たす配線長の配線を自動化することにより、作業負担の軽減化および設計期間の短縮化を図る。
【００３１】
ＬＳＩ設計におけるアナログ回路やプリント基板の配線の設計では、仕様の回路特性を満たすため、ミクロン単位での配線制約（指定長、等長配線など）が与えられる。ところが、ＬＳＩやプリント基板の高集積化により、配線領域上の障害物（トランジスタ、配線、ビアなど）が増加し設計ルールが複雑化している。
【００３２】
このため、端子間の配線形成のために割り付けられた配線領域内における端子間の最長経路探索が困難となり、該配線領域内における仕様の回路特性を満たす配線の実現可能性を判断することが難しくなっている。そこで、所定の配線領域内における仕様の回路特性を満たす配線の実現可能性を効率的かつ効果的に判断する手法を提案する。
【００３３】
まず、探索困難な端子間の最長経路の換わりに、巡回路を含む端子間の配線経路を最長経路候補として探索する。そして、その最長経路候補の配線長が、仕様の回路特性を満たす配線長以上であった場合に、仕様の回路特性を満たす配線が実現可能であると判断する。これは、巡回路を含む端子間の配線経路の配線長が、巡回路を含まない端子間の配線経路の配線長以上となるという特性を利用したものである。
【００３４】
換言すれば、巡回路を含む端子間の配線経路の配線長が、仕様の回路特性を満たす配線長未満であった場合には、配線制約を満たす配線は実現できないことを意味している。仕様の回路特性を満たす配線が実現不可能と判断された場合は、例えば、上流の工程に戻って各端子の配置位置を変更するなどの修正をおこなうこととなる。
【００３５】
一方で、仕様の回路特性を満たす配線が実現可能であると判断された場合には、その仕様の回路特性を満たす配線長に応じて、巡回路を含む配線経路を自動修正し、配線制約を満たす端子間の配線を実現する。これにより、複雑な配線禁止領域（障害物）を含む配線領域を扱うことが可能となり、仕様の回路特性を満たす配線長の配線を自動化することができる。
【００３６】
（配線領域の具体例）
ここで、端子間の配線経路を形成するために割り付けられる配線領域の具体例について説明する。図２は、配線領域の具体例を示す説明図である。図２において、配線領域２００は、ソースＳ（第１の端子）とターゲットＴ（第２の端子）とを接続する配線経路を形成するために割り付けられた配線領域である。
【００３７】
配線領域２００は、格子状に区切って９個のグリッドに分割されている。グリッドには、各グリッドを特定するためのラベルＲ１〜Ｒ９が付与されている。配線領域２００において、ラベルＲ８，Ｒ９が付与されたグリッド（図２中ハッチ部分）は、トランジスタ、配線、ビアなどの障害物が配置された配線禁止領域を示している。なお、配線領域２００を分割する格子サイズ（グリッドの大きさ）は、配線のプロセスによって決まる。
【００３８】
（配線情報のデータ構造）
つぎに、図２に示した配線領域に関する配線情報のデータ構造について説明する。図３は、配線情報のデータ構造を示す説明図である。図３において、配線情報３００は、グリッド数、ソースＳ、ターゲットＴ、配線禁止領域および各グリッドの座標位置に関する情報を有している。
【００３９】
グリッド数は、配線領域２００（図２参照）のＸ方向およびＹ方向のグリッド数を表わしている。ソースＳは、始点端子の配置位置を表わしている。ここでは、ラベルＲ７のグリッドに始点端子が配置されている。ターゲットＴは、終点端子の配置位置を表わしている。ここでは、ラベルＲ３のグリッドに終点端子が配置されている。
【００４０】
配線禁止領域は、トランジスタ、配線、ビアなどの障害物が配置され、新たな配線を形成することができないグリッドを表わしている。ここでは、ラベルＲ８，Ｒ９のグリッドが配線禁止領域となっている。また、配線情報３００には、各グリッドの座標位置を認識するための座標データ（例えば、図４に示す座標テーブル４００）が含まれている。
【００４１】
図４は、座標テーブルの記憶内容を示す説明図である。図４において、座標テーブル４００は、グリッドごとに、ラベル名および座標位置に関する情報を記憶している。この座標テーブル４００を参照することで、各グリッドの座標位置を認識することができる。例えば、ラベルＲ１のグリッドの座標位置は（Ｘ，Ｙ）＝（１，１）である。
【００４２】
（設計支援装置の機能的構成）
つぎに、設計支援装置１００の機能的構成について説明する。図５は、設計支援装置の機能的構成を示すブロック図である。図５において、設計支援装置１００は、探索部５０１と、算出部５０２と、判定部５０３と、出力部５０４と、変更部５０５と、分割部５０６と、を備えている。
【００４３】
これら各機能５０１〜５０６は、設計支援装置１００の記憶部に記憶された当該機能５０１〜５０６に関するプログラムをＣＰＵに実行させることにより、または、入出力Ｉ／Ｆにより、当該機能を実現することができる。また、各機能５０１〜５０６からの出力データは上記記憶部に保持される。また、図５中矢印で示した接続先の機能は、接続元の機能からの出力データを記憶部から読み込んで、当該機能に関するプログラムをＣＰＵに実行させるものとする。
【００４４】
まず、探索部５０１は、所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、所定の配線領域内でかつ配線経路と非接続な巡回路とを探索する機能を有する。所定の配線領域とは、設計対象回路内の２つの端子ごとに割り付けられる配線領域である。例えば、レイアウトツールを実行することで、第１および第２の端子に所定の配線領域を自動的に割り付けることができる。また、巡回路とは、ループ状の配線経路である。この順回路は、所定の配線領域内のうち第１および第２の端子を接続する配線経路が形成された領域を除く残余の領域に形成される。
【００４５】
具体的には、例えば、探索部５０１は、所定の配線領域に関する配線領域情報と、該配線領域内の配線禁止領域を表わす配線禁止情報と、第１および第２の端子に関する接続端子情報とに基づいて、第１および第２の端子を接続する配線経路と巡回路とを探索する。これら配線領域情報、配線禁止情報および接続端子情報として、例えば、図３に示した配線情報３００を用いることができる。なお、配線情報３００は、設計支援装置１００に直接入力することとしてもよく、また、不図示の外部装置からの取得、不図示のデータベースやライブラリからの抽出によって取得することとしてもよい。
【００４６】
ここで、探索部５０１による第１および第２の端子を接続する配線経路と巡回路とを探索する第１の探索処理の具体例について説明する。図６は、第１の探索処理の概要を示す説明図である。ここでは、配線領域６００内のソースＳとターゲットＴとを接続する配線経路と、配線領域６００内でかつ該配線経路と非接続な巡回路とを探索する。
【００４７】
まず、配線領域６００内の各グリッドがノード化され、ノード間をつなぐ各エッジに変数ｘ１〜ｘ１２が割り付けられたグラフ６１０を作成する。グラフ６１０における各ノードの配置位置は、配線領域６００における各グリッドの配置位置に対応している。例えば、ノードｅ１とソースＳが配置されたグリッドとが対応している。
【００４８】
以下、グラフ６１０を用いて、ソースＳからターゲットＴに辿り着くまでの配線経路および巡回路を探索する。なお、前提条件として、グラフ６１０内において、引き返しは不可とし、同じグリッドに２回辿り着いた時点で探索を終了することとする。
【００４９】
具体的には、巡回路を含む最長経路探索問題を線形計画問題にモデル化する。より具体的には、巡回路を含む最長経路探索問題を整数計画問題にモデル化し、その整数計画問題を線形計画問題に緩和する。まず、整数計画問題を定式化すると、目的関数は下記式（１）となり、制約式は下記式（２）〜（５）となる。ただし、ｄｉは区間ｉの距離である。また、ｘｉ＝１は区間ｉを通過、ｘｉ＝０は区間ｉを通過しないことを意味している。
【００５０】
ｍａｘ．Σ｛ｄｉ・ｘｉ｜ｉは区間｝ …（１）
【００５１】
Σ｛ｅｉ｜ｉは終端ノード｝＝２ …（２）
【００５２】
ｂｉ∈｛０，２｝（ただし、ｂｉは任意の分岐ノード） …（３）
【００５３】
ｅｉ∈｛１｝（ただし、ｅｉは２つの始点終点ノード） …（４）
【００５４】
ｘｉ∈｛０，１｝（ただし、ｘｉは任意のエッジ） …（５）
【００５５】
つぎに、この整数計画問題を線形計画問題に緩和する。具体的には、上記の制約式を線形計画制約によって表現する。ここで、グラフ６１０内の代表ノード（始点終点ノード、３分岐ノード、４分岐ノード）を例に挙げて、上記式（３）および（５）を線形計画制約によって表現した制約式について説明する。
【００５６】
まず、グラフ６１０内のノードｅ１（始点ノード）を例に挙げると、制約式は『＋ｘ１＋ｘ７＝１，０≦ｘ１≦１，０≦ｘ７≦１』となる。つぎに、ノードｅ２（終点ノード）を例に挙げると、制約式は『＋ｘ６＋ｘ１２＝１，０≦ｘ６≦１，０≦ｘ１２≦１』となる。
【００５７】
つぎに、ノードｂ３（３分岐）を例に挙げると、『−ｘ３＋ｘ７＋ｘ８≧０，＋ｘ３−ｘ７＋ｘ８≧０，＋ｘ３＋ｘ７−ｘ８≧０，＋ｘ３＋ｘ７＋ｘ８≦２，０≦ｘ３≦１，０≦ｘ７≦１，０≦ｘ８≦１』となる。
【００５８】
つぎに、ノードｂ４（４分岐）を例に挙げると、『−ｘ３＋ｘ４＋ｘ９＋ｘ１０≧０，＋ｘ３−ｘ４＋ｘ９＋ｘ１０≧０，＋ｘ３＋ｘ４−ｘ９＋ｘ１０≧０，＋ｘ３＋ｘ４＋ｘ９−ｘ１０≧０，＋ｘ３＋ｘ４＋ｘ９＋ｘ１０≦２，０≦ｘ３≦１，０≦ｘ４≦１，０≦ｘ９≦１，０≦ｘ１０≦１』となる。
【００５９】
このあと、上記式（１）で示した目的関数と、グラフ６１０内のノードごとに線形計画制約で表現した制約式と、を線形計画ソルバに入力することで、ソースＳからターゲットＴに辿り着くまでの巡回路を含む最長経路を求めることができる。なお、線形計画問題に緩和したため、各変数は必ずしも０または１に収束しない。このため、ここでは０と１の間の中間値をとる変数を、近傍の配線と接続されるように０または１に修正することとする。
【００６０】
ここで、第１の探索処理の探索結果の具体例について説明する。図７は、第１の探索処理の探索結果の具体例を示す説明図である。図７において、配線領域６００には、第１の探索処理の探索結果である、ソースＳとターゲットＴとを接続する配線経路７１０と巡回路７２０とが示されている。
【００６１】
図５の説明に戻り、算出部５０２は、探索部５０１によって探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出する機能を有する。具体的には、例えば、配線経路および巡回路が通過するグリッド数を配線経路長とすることとしてもよく、また、上記式（１）を用いて求めた値を配線経路長とすることとしてもよい。
【００６２】
判定部５０３は、算出部５０２によって算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する機能を有する。仕様の回路特性を満たす配線経路長とは、例えば、設計対象回路の仕様として規定された配線制約であり、特定の配線経路長である。なお、仕様の回路特性を満たす配線経路長は、例えば、ＲＯＭやＲＡＭなどの記憶部に記憶されている。
【００６３】
出力部５０４は、判定部５０３によって判定された判定結果を出力する機能を有する。例えば、仕様の回路特性を満たす配線経路長未満と判定された場合には、割り付けられた配線領域内で仕様の回路特性を満たす配線経路長を満たすことができない旨のエラーメッセージを出力することとしてもよい。なお、出力部５０４による出力形式は、ディスプレイ１３１での画面表示、プリンタ１３３での印刷出力、メモリへのデータ出力（保存）、外部のコンピュータ装置への送信のいずれであってもよい。
【００６４】
設計者は、このエラーメッセージを確認することで、第１および第２の端子に割り付けられた配線領域内において配線制約を満たす配線が実現できないことを認識することができる。これにより、上流の工程に戻って第１および第２の端子の配置位置を変更するなどの対策を適切かつ迅速におこなうことができる。
【００６５】
また、探索部５０１は、判定部５０３によって配線経路長以上と判定された場合、配線経路の一部と巡回路の一部とを通過して第１の端子から第２の端子に辿り着くまでの最長配線経路を探索する機能を有する。具体的には、４つの接続ポイントで配線経路と巡回路とを繋ぎ換えることで、最大限に配線経路長を維持した単一の最長配線経路を探索する。
【００６６】
ここで、探索部５０１による最長配線経路を探索する第２の探索処理の具体例について説明する。ここでは、図７に示した探索結果を例に挙げて説明する。図８は、第２の探索処理の概要を示す説明図である。最長配線経路を探索する場合、図８に示すターンアウトスイッチグラフ（以下、「Ｔｓグラフ」と表記）８００を作成する。
【００６７】
Ｔｓグラフ８００は、配線経路７１０と巡回路７２０とを繋ぎ換える際の接続可能ポイントが表現されたグラフである。具体的には、まず、配線領域６００を区切る境界線の中から、配線経路７１０と巡回路７２０との間の境界線を検出する。例えば、配線経路７１０のソースＳからターゲットＴに辿り着くまでのグリッドごとに、巡回路７２０との間の境界線を検出する。そして、境界線が検出された都度、その境界線にエッジＩＤを割り付ける。
【００６８】
ここで、ソースＳが配置されたグリッドを例に挙げると、巡回路７２０との間の境界線８１０を検出し、その境界線８１０にエッジａを割り付ける。このように、境界線が検出された都度、エッジＩＤ（図８では、エッジａ〜ｄ）を割り付けることで、配線経路７１０と巡回路７２０との間の境界線を認識することができる。
【００６９】
このあと、配線経路７１０、巡回路７２０、エッジａ〜ｄがノード化されたＴｓグラフ８００を作成する。具体的には、配線経路７１０を表わすノードＮ１と、巡回路７２０を表わすノードＮ２とが、エッジａ〜ｄを表わすノードＮａ〜Ｎｄを介して接続されたＴｓグラフ８００を作成する。
【００７０】
つぎに、配線経路７１０および巡回路７２０の原点を設定する。原点の位置は任意に設定可能である。ここでは、配線経路７１０の原点をソースＳ（以下、「原点Ｓ」と表記）に設定し、巡回路７２０の原点を点Ａ（以下、「原点Ａ」と表記）に設定する。
【００７１】
さらに、配線経路７１０の経路上を辿って原点Ｓから各エッジａ〜ｄに辿り着くまでの距離を求めて、ノード間をつなぐ各枝に設定する。例えば、原点Ｓからエッジａまでの距離は「０」のため、ノードＮ１とノードＮａとをつなぐ枝に「０」を設定する。また、原点Ｓからエッジｄまでの距離は「４」のため、ノードＮ１とノードＮｄとをつなぐ枝に「４」を設定する。
【００７２】
同様に、巡回路７２０の経路上を辿って原点Ａから各エッジａ〜ｄに辿り着くまでの距離を求めて、ノード間をつなぐ各枝に設定する。このとき、時計回りに巡回路７２０の経路上を辿ることとする。例えば、原点Ａからエッジａまでの距離は「１」のため、ノードＮ２とノードＮａとをつなぐ枝に「１」を設定する。また、原点Ａからエッジｄまでの距離は「３」のため、ノードＮ２とノードＮｄとをつなぐ枝に「３」を設定する。
【００７３】
ここで、Ｔｓグラフ８００を表わす具体的なグラフ情報のデータ構造について説明する。図９および図１０は、グラフ情報のデータ構造を示す説明図である。図９において、グラフ情報９００は、ノードＮ１，Ｎ２，Ｎａ〜Ｎｄごとに、ノード名、フラグおよびノードタイプに関する情報を有している。例えば、ノードＮ１は、フラグがＯＮに設定された配線経路である。フラグに関する詳細な説明は後述する。
【００７４】
また、図１０において、グラフ情報１０００は、ノードＮ１，Ｎ２ごとに、境界線を表わすノードＮａ〜Ｎｄとの距離に関する情報を有している。このグラフ情報１０００を参照することで、ノード間の距離を特定することができる。上述したＴｓグラフ８００は、図９および図１０に示したグラフ情報９００，１０００によって表現することができる。
【００７５】
つぎに、グラフ情報９００，１０００を用いて、配線経路７１０の一部と巡回路７２０の一部とを通過してソースＳからターゲットＴまで辿り着くまでの最長配線経路を探索する。まず、グラフ情報９００の全ノードのフラグをＯＦＦに設定する。つぎに、ソースＳ，ターゲットＴを含むノードＮ１のフラグをＯＮに設定する。
【００７６】
このあと、グラフ情報１０００が有するノード間の距離を用いて、ノードＮ１→ノードＮ２→ノードＮ１と遷移した場合に、最も迂回の小さい戻り経路を探索する。具体的には、ノードＮａ〜Ｎｄの中から、ノードＮ１からノードＮ２に遷移する際に経由する接続ポイントおよびノードＮ２からノードＮ１に遷移する際に経由する接続ポイントとなる２つのノードＮａ〜Ｎｄを選択し、ノードＮ１→ノードＮ２→ノードＮ１と遷移した場合のコストを計算する。
【００７７】
例えば、ノードＮａ〜Ｎｄの中からノードＮａ，Ｎｂが選択されたとすると、ノードＮ１→ノードＮａ→ノードＮ２→ノードＮｂ→ノードＮ１と遷移する場合のコストを計算する。具体的には、Ｎ１−Ｎａ間の距離（０）とＮ２−Ｎａ間の距離（１）とを加算した値（１）から、Ｎ２−Ｎｂ間の距離（２）とＮ１−Ｎｂ間の距離（１）とを加算した値（３）を減算した値（−２）をコストとする。
【００７８】
具体的には、Ｎ１−Ｎａ間の距離（０）とＮ２−Ｎａ間の距離（１）とを加算した値（１）は、配線経路７１０と巡回路７２０とを繋ぎ換えた際に増加する配線経路長である。また、Ｎ２−Ｎｂ間の距離（２）とＮ１−Ｎｂ間の距離（１）とを加算した値（３）は、配線経路７１０と巡回路７２０とを繋ぎ換えた際に減少する配線経路長である。
【００７９】
このコストを接続ポイントとなる全組み合わせ『Ｎａ−Ｎｂ，Ｎａ−Ｎｃ，Ｎａ−Ｎｄ，Ｎｂ−Ｎｃ，Ｎｂ−Ｎｄ，Ｎｃ−Ｎｄ』について求めて、コストが最大（配線経路長の減少分が最小）の組み合わせを接続ポイントの組み合わせとして決定する。ここでは、『Ｎａ−Ｎｂ』の組み合わせが、最大のコストとなる。この結果、ノードＮ１→ノードＮａ→ノードＮ２→ノードＮｂ→ノードＮ１の遷移に従って、配線領域６００内のグリッドを辿る配線経路を最長配線経路に決定する。
【００８０】
ここで、第２の探索処理の探索結果の具体例について説明する。図１１は、第２の探索処理の探索結果の具体例を示す説明図である。図１１において、符号１１００は、配線経路７１０の一部と巡回路７２０の一部とを通過してソースＳからターゲットＴまで辿り着くまでの最長配線経路（上述したノードＮ１→ノードＮａ→ノードＮ２→ノードＮｂ→ノードＮ１に相当）である。
【００８１】
なお、巡回路７２０と隣接する他の巡回路が存在する場合には、最長配線経路１１００が探索された結果、さらに、最長配線経路１１００の一部と他の巡回路の一部とを通過してソースＳからターゲットＴまで辿り着くまでの最長配線経路を探索することとなる。
【００８２】
図１２は、複数の巡回路の一部を通過する最長配線経路の一例を示す説明図である。図１２において、（１）には、ソースＳとターゲットＴとを接続する配線経路Ｈおよび巡回路Ｊ１〜Ｊｎが示されている。この場合、配線経路Ｈと隣接する巡回路Ｊ１から順に探索部５０１による第２の探索処理を実行して、ソースＳからターゲットＴに辿り着くまでの最長配線経路を探索する。
【００８３】
この結果、（２）に示すように、配線経路Ｈの一部と巡回路Ｊ１〜Ｊｎの一部（Ｊ’１〜Ｊ’ｎ）とを通過してソースＳからターゲットＴに辿り着くまでの最長配線経路Ｉが探索される。このとき、探索が終了した巡回路Ｊ１〜Ｊｎのフラグ（グラフ情報９００のフラグに相当）をＯＮに設定することにより、未探索の巡回路Ｊ１〜Ｊｎを認識することができる。
【００８４】
図５の説明に戻り、出力部５０４は、探索部５０１によって探索された最長配線経路を出力する機能を有する。具体的には、例えば、最長配線経路が通過するグリッドを特定するラベルの接続関係を表わす探索結果を出力することとしてもよい。ここで、出力部５０４によって出力される出力例について説明する。
【００８５】
図１３は、探索結果の出力例を示す説明図である。図１３において、最長配線経路１１００（図１１参照）を表わす探索結果１３００が示されている。探索結果１３００は、接続関係を有するグリッドを特定するラベル情報を有している。
【００８６】
これにより、最長配線経路１１００は、Ｒ７→Ｒ８→Ｒ９→Ｒ６→Ｒ５→Ｒ４→Ｒ１→Ｒ２→Ｒ３を通過する配線経路であると特定することができる。なお、各ラベルＲ１〜Ｒ９の座標位置は、配線領域の配線情報に含まれている座標テーブルを参照することで認識することができる。
【００８７】
また、算出部５０２は、探索部５０１によって探索された最長配線経路の配線経路長を算出する機能を有する。そして、判定部５０３は、算出部５０２によって算出された最長配線経路の配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する機能を有する。
【００８８】
すなわち、配線経路と巡回路とを繋ぎ換えることで単一の最長配線経路が探索された結果、仕様の回路特性を満たす配線経路長を実現できるか否かを判定する。ここで、仕様の回路特性を満たす配線経路長未満と判定された場合には、例えば、上述したエラーメッセージを出力することとしてもよい。
【００８９】
また、判定部５０３は、最長配線経路の配線経路長と、仕様の回路特性を満たす配線経路長との差分が予め設定された許容範囲内か否かを判定することとしてもよい。具体的には、配線制約として、指定配線経路長と完全一致ではなく、回路特性を満たす程度の誤差を許容範囲として設定する。許容範囲は、例えば、図１に示したキーボード１２１やマウス１２２などの入力装置１２０をユーザが操作することで、任意に設定可能である。
【００９０】
また、変更部５０５は、判定部５０３によって許容範囲外と判定された場合、最長配線経路を許容範囲内の配線経路長となるように変更する機能を有する。具体的には、例えば、図１２に示した最長配線経路Ｉの一部であるＪ’１〜Ｊ’ｎを、末端のＪ’ｎから順に切り離すことで最長配線経路Ｉの配線経路長を調整することとしてもよい。
【００９１】
さらに、例えば、末端のＪ’ｎを切り離した結果、最長配線経路Ｉの配線経路長が、仕様の回路特性を満たす配線経路長よりも短くなった場合には、最長配線経路Ｉの一部を所定の配線領域内の空き領域で迂回させて配線経路長を調整することとしてもよい。また、出力部５０４は、変更部５０５によって変更された変更後の最長配線経路を出力する機能を有する。
【００９２】
分割部５０６は、所定の配線領域を、障害物を含まない第１の配線領域と、障害物を含む第２の配線領域とに分割する機能を有する。これは、配線経路の配線経路長および巡回路の配線経路長を合わせた配線経路長と、実際の最長配線経路の配線経路長との誤差を低減させるためにおこなう。特に、大規模な配線領域を扱う場合に有効である。
【００９３】
具体的には、例えば、分割部５０６は、配線情報３００に基づいて、所定の配線領域を区切る境界線に沿ってカットラインを設定することで、障害物を含まない第１の配線領域と、障害物を含む第２の配線領域とに分割する。このとき、例えば、障害物（配線禁止領域）を含まない領域ができる限り広くなるように所定の配線領域を分割することとしてもよい。
【００９４】
また、カットラインの設定位置は、例えば、配線禁止領域から１グリッド以上離した位置に設定することとしてもよい。どうしても配線禁止領域に接する位置にカットラインを設定しなければならない場合には、２つの配線禁止領域の間に配線可能領域が存在する状況が連続するのを回避することとしてもよい。
【００９５】
なお、配線領域上のカットラインの設定位置を表わすカットライン情報は、例えば、グリッドの座標位置によって表現することとしてもよい。このカットライン情報は、分割部５０６によって分割された結果、上記記憶部に記憶される。そして、カットライン情報を記憶部から読み出すことで、第１および第２の配線領域を認識することができる。
【００９６】
また、上記探索部５０１、算出部５０２および判定部５０３は、分割部５０６によって所定の配線領域が第１および第２の配線領域に分割された場合、第１および第２の配線領域ごとに、探索処理、算出処理および判定処理を実行することとなる。ここで、所定の配線領域内を第１および第２の配線領域に分割した場合の一連の処理の流れについて説明する。
【００９７】
図１４は、分割時の一連の処理の流れを示す説明図である。図１４において、配線領域１４００が、カットラインＣにより第１の配線領域１４１０と第２の配線領域１４２０とに分割されている。また、第１の配線領域１４１０内に配線経路１４３０が、第２の配線領域１４２０内に巡回路１４４０が探索済みである。
【００９８】
ここでは、カットラインＣに接する配線禁止領域（ラベルＲ１６，Ｒ１７，Ｒ１９）の間に配線可能領域Ｒ１５，Ｒ１７が存在している。この場合、これら配線可能領域Ｒ１５，Ｒ１７を仮想端子Ｖ１，Ｖ２として扱うことで、配線経路１４３０と巡回路１４４０とを接続する。この結果、配線経路１４５０と巡回路１４６０，１４７０とが探索される。
【００９９】
最後に、配線経路１４５０の一部と巡回路１４６０の一部と、巡回路１４７０の一部とを通過してソースＳからターゲットＴに辿り着くまでの最長配線経路１４８０を探索する。なお、最長配線経路１４８０が探索された結果、変更部５０５により、最長配線経路１４８０を仕様の回路特性を満たす配線経路長となるように変更することとしてもよい。
【０１００】
（設計支援装置の設計支援処理手順）
つぎに、本実施の形態にかかる設計支援装置１００の設計支援処理手順について説明する。図１５は、設計支援装置の設計支援処理手順の一例を示すフローチャートである。図１５のフローチャートにおいて、まず、所定の配線領域に関する配線情報が入力されたか否かを判断する（ステップＳ１５０１）。
【０１０１】
ここで、配線情報が入力されるのを待って（ステップＳ１５０１：Ｎｏ）、入力された場合（ステップＳ１５０１：Ｙｅｓ）、探索部５０１により、所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、所定の配線領域内でかつ該配線経路と非接続な巡回路とを探索する第１の探索処理を実行する（ステップＳ１５０２）。
【０１０２】
このあと、算出部５０２により、ステップＳ１５０２において探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出する（ステップＳ１５０３）。そして、判定部５０３により、ステップＳ１５０３において算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する（ステップＳ１５０４）。
【０１０３】
ここで、仕様の回路特性を満たす配線経路長以上であった場合（ステップＳ１５０４：Ｙｅｓ）、探索部５０１により、配線経路の一部と巡回路の一部とを通過して第１の端子から第２の端子に辿り着くまでの最長配線経路を探索する第２の探索処理を実行する（ステップＳ１５０５）。
【０１０４】
このあと、算出部５０２により、ステップＳ１５０５において探索された最長配線経路の配線経路長を算出する（ステップＳ１５０６）。そして、判定部５０３により、ステップＳ１５０６において算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する（ステップＳ１５０７）。
【０１０５】
ここで、仕様の回路特性を満たす配線経路長以上であった場合（ステップＳ１５０７：Ｙｅｓ）、判定部５０３により、最長配線経路の配線経路長と、仕様の回路特性を満たす配線経路長との差分が予め設定された許容範囲内か否かを判定する（ステップＳ１５０８）。
【０１０６】
ここで、許容範囲外だった場合（ステップＳ１５０８：Ｎｏ）、変更部５０５により、最長配線経路を許容範囲内の配線経路長となるように変更し（ステップＳ１５０９）、ステップＳ１５０８に戻る。一方、許容範囲内だった場合（ステップＳ１５０８：Ｙｅｓ）、出力部５０４により、最長配線経路を出力して（ステップＳ１５１０）、本フローチャートによる一連の処理を終了する。
【０１０７】
また、ステップＳ１５０４において配線経路長未満であった場合（ステップＳ１５０４：Ｎｏ）、または、ステップＳ１５０７において配線経路長未満であった場合（ステップＳ１５０７：Ｎｏ）、出力部５０４により、仕様の回路特性を満たす配線経路長を満たすことができない旨のエラーメッセージを出力して（ステップＳ１５１１）、本フローチャートによる一連の処理を終了する。
【０１０８】
つぎに、図１５に示したステップＳ１５０２における第１の探索処理の具体的処理手順について説明する。図１６は、第１の探索処理の具体的処理手順の一例を示すフローチャートである。これは、巡回路を含む最長経路探索問題を線形計画問題にモデル化した場合の一例である。
【０１０９】
図１６のフローチャートにおいて、まず、所定の配線領域内の各グリッドがノード化され、ノード間をつなぐ各エッジに変数が割り付けられたグラフを作成する（ステップＳ１６０１）。このあと、巡回路を含む最長経路探索問題を線形計画問題にモデル化することで、目的関数および制約式を求める（ステップＳ１６０２）。
【０１１０】
そして、ステップＳ１６０２において求めた目的関数および制約式を線形計画ソルバに入力することで（ステップＳ１６０３）、所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、所定の配線領域内でかつ上記配線経路と非接続な巡回路とを決定し（ステップＳ１６０４）、図１５に示したステップＳ１５０３に移行する。
【０１１１】
つぎに、図１５に示したステップＳ１５０５における第２の探索処理の具体的処理手順について説明する。図１７は、第２の探索処理の具体的処理手順の一例を示すフローチャートである。これは、Ｔｓグラフ（例えば、Ｔｓグラフ８００）を用いて、最長配線経路を探索する場合の一例である。
【０１１２】
図１７のフローチャートにおいて、まず、第１および第２の端子を接続する配線経路と巡回路とを繋ぎ換える際の接続可能ポイントが表現されたＴｓグラフを作成する（ステップＳ１７０１）。このあと、ステップＳ１７０１において作成されたＴｓグラフを用いて、上記配線経路を表わすノードと巡回路を表わすノードとの間を遷移する際に経由する接続ポイントの組み合わせごとのコストを算出する（ステップＳ１７０２）。
【０１１３】
そして、ステップＳ１７０２において算出された組み合わせごとのコストに基づいて、上記配線経路の一部と巡回路の一部とを通過して第１の端子から第２の端子に辿り着くまでの最長配線経路を決定して（ステップＳ１７０３）、図１５に示したステップＳ１５０６に移行する。
【０１１４】
なお、図１５に示したステップＳ１５０２において所定の配線領域内に複数の巡回路が探索された場合には、未探索の巡回路がなくなるまで、第１および第２の端子を接続する配線経路と隣接する巡回路から順にステップＳ１７０１〜ステップＳ１７０３の繰り返し実行することとなる。
【０１１５】
以上説明したように、本実施の形態によれば、探索困難な端子間の最長配線経路の換わりに、比較的に探索容易な端子間の任意の配線経路と巡回路とを合わせた最長配線経路候補を用いて、所定の配線領域における仕様の回路特性を満たす配線経路長の実現可能性を判定することができる。
【０１１６】
そして、仕様の回路特性を満たす配線経路長の実現可能な場合は、端子間の任意の配線経路と巡回路とを用いて、端子間の最長配線経路を探索することができる。さらに、仕様の回路特性を満たす配線経路長に従って最長配線経路を自動修正することで、所定の配線領域における仕様の回路特性を満たす配線経路長の配線を実現することができる。
【０１１７】
また、所定の配線領域を分割して対象となる配線領域を小さくすることで、実際の最長配線経路の配線経路長と、最長配線経路候補の配線経路長との誤差を低減させることができる。この結果、端子間の最長配線経路を精度よく探索でき、所定の配線領域における仕様の回路特性を満たす配線経路長の実現可能性を正確に判定することができる。
【０１１８】
このように、仕様の回路特性を満たす適切な配線をおこなうことで、無駄な配線リソースを削減し、設計対象回路の小型化を実現することができる。さらに、所定の配線領域における仕様の回路特性を満たす配線長の配線を自動化することにより、作業負担の軽減化および設計期間の短縮化を図ることができる。
【０１１９】
なお、本実施の形態で説明した設計支援方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネットなどのネットワークを介して配布することが可能な伝送媒体であってもよい。
【０１２０】
また、本実施の形態で説明した設計支援装置１００は、スタンダードセルやストラクチャードＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ）によっても実現することができる。具体的には、たとえば、上述した設計支援装置１００の機能５０１〜５０６をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、設計支援装置１００を製造することができる。
【図面の簡単な説明】
【０１２１】
【図１】本実施の形態にかかる設計支援装置のハードウェア構成を示す説明図である。
【図２】配線領域の具体例を示す説明図である。
【図３】配線情報のデータ構造を示す説明図である。
【図４】座標テーブルの記憶内容を示す説明図である。
【図５】設計支援装置の機能的構成を示すブロック図である。
【図６】第１の探索処理の概要を示す説明図である。
【図７】第１の探索処理の探索結果の具体例を示す説明図である。
【図８】第２の探索処理の概要を示す説明図である。
【図９】グラフ情報のデータ構造を示す説明図（その１）である。
【図１０】グラフ情報のデータ構造を示す説明図（その２）である。
【図１１】第２の探索処理の探索結果の具体例を示す説明図である。
【図１２】複数の巡回路の一部を通過する最長配線経路の一例を示す説明図である。
【図１３】探索結果の出力例を示す説明図である。
【図１４】分割時の一連の処理の流れを示す説明図である。
【図１５】設計支援装置の設計支援処理手順の一例を示すフローチャートである。
【図１６】第１の探索処理の具体的処理手順の一例を示すフローチャートである。
【図１７】第２の探索処理の具体的処理手順の一例を示すフローチャートである。
【符号の説明】
【０１２２】
１００ 設計支援装置
２００，６００ 配線領域
３００ 配線情報
４００ 座標テーブル
５０１ 探索部
５０２ 算出部
５０３ 判定部
５０４ 出力部
５０５ 変更部
５０６ 分割部
【特許請求の範囲】
【請求項１】
コンピュータを、
所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、前記所定の配線領域内でかつ前記配線経路と非接続な巡回路とを探索する探索手段、
前記探索手段によって探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出する算出手段、
前記算出手段によって算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する判定手段、
前記判定手段によって判定された判定結果を出力する出力手段、
として機能させることを特徴とする設計支援プログラム。
【請求項２】
前記探索手段は、
前記判定手段によって配線経路長以上と判定された場合、前記配線経路の一部と前記巡回路の一部とを通過して前記第１の端子から前記第２の端子に辿り着くまでの最長配線経路を探索し、
前記出力手段は、
前記探索手段によって探索された最長配線経路を出力することを特徴とする請求項１に記載の設計支援プログラム。
【請求項３】
前記算出手段は、
前記探索手段によって探索された最長配線経路の配線経路長を算出し、
前記判定手段は、
前記算出手段によって算出された最長配線経路の配線経路長が、前記仕様の回路特性を満たす配線経路長以上か否かを判定することを特徴とする請求項２に記載の設計支援プログラム。
【請求項４】
前記コンピュータを、
前記最長配線経路を変更する変更手段として機能させ、
前記判定手段は、
前記最長配線経路の配線経路長と、前記仕様の回路特性を満たす配線経路長との差分が予め設定された許容範囲内か否かを判定し、
前記変更手段は、
前記判定手段によって許容範囲外と判定された場合、前記最長配線経路を前記許容範囲内の配線経路長となるように変更し、
前記出力手段は、
前記変更手段によって変更された変更後の最長配線経路を出力することを特徴とする請求項３に記載の設計支援プログラム。
【請求項５】
前記コンピュータを、
前記所定の配線領域を、障害物を含まない第１の配線領域と、障害物を含む第２の配線領域とに分割する分割手段として機能させ、
前記コンピュータに、
前記分割手段によって分割された第１および第２の配線領域ごとに、前記探索手段、前記算出手段および前記判定手段による処理を実行させることを特徴とする請求項２〜４のいずれか一つに記載の設計支援プログラム。
【請求項６】
前記探索手段は、
前記第１および第２の配線領域ごとに、前記探索手段、前記算出手段および前記判定手段による処理が実行された結果、前記第１の配線領域内の第１の最長配線経路の一部と前記第２の配線領域内の第２の最長配線経路の一部とを通過して前記第１の端子から前記第２の端子に辿り着くまでの最長配線経路を探索することを特徴とする請求項５に記載の設計支援プログラム。
【請求項７】
所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、前記所定の配線領域内でかつ前記配線経路と非接続な巡回路とを探索する探索手段と、
前記探索手段によって探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出する算出手段と、
前記算出手段によって算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する判定手段と、
前記判定手段によって判定された判定結果を出力する出力手段と、
を備えることを特徴とする設計支援装置。
【請求項８】
所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、前記所定の配線領域内でかつ前記配線経路と非接続な巡回路とを探索する探索工程と、
前記探索工程によって探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出する算出工程と、
前記算出工程によって算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する判定工程と、
前記判定工程によって判定された判定結果を出力する出力工程と、
を含んだことを特徴とする設計支援方法。
【請求項１】
コンピュータを、
所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、前記所定の配線領域内でかつ前記配線経路と非接続な巡回路とを探索する探索手段、
前記探索手段によって探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出する算出手段、
前記算出手段によって算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する判定手段、
前記判定手段によって判定された判定結果を出力する出力手段、
として機能させることを特徴とする設計支援プログラム。
【請求項２】
前記探索手段は、
前記判定手段によって配線経路長以上と判定された場合、前記配線経路の一部と前記巡回路の一部とを通過して前記第１の端子から前記第２の端子に辿り着くまでの最長配線経路を探索し、
前記出力手段は、
前記探索手段によって探索された最長配線経路を出力することを特徴とする請求項１に記載の設計支援プログラム。
【請求項３】
前記算出手段は、
前記探索手段によって探索された最長配線経路の配線経路長を算出し、
前記判定手段は、
前記算出手段によって算出された最長配線経路の配線経路長が、前記仕様の回路特性を満たす配線経路長以上か否かを判定することを特徴とする請求項２に記載の設計支援プログラム。
【請求項４】
前記コンピュータを、
前記最長配線経路を変更する変更手段として機能させ、
前記判定手段は、
前記最長配線経路の配線経路長と、前記仕様の回路特性を満たす配線経路長との差分が予め設定された許容範囲内か否かを判定し、
前記変更手段は、
前記判定手段によって許容範囲外と判定された場合、前記最長配線経路を前記許容範囲内の配線経路長となるように変更し、
前記出力手段は、
前記変更手段によって変更された変更後の最長配線経路を出力することを特徴とする請求項３に記載の設計支援プログラム。
【請求項５】
前記コンピュータを、
前記所定の配線領域を、障害物を含まない第１の配線領域と、障害物を含む第２の配線領域とに分割する分割手段として機能させ、
前記コンピュータに、
前記分割手段によって分割された第１および第２の配線領域ごとに、前記探索手段、前記算出手段および前記判定手段による処理を実行させることを特徴とする請求項２〜４のいずれか一つに記載の設計支援プログラム。
【請求項６】
前記探索手段は、
前記第１および第２の配線領域ごとに、前記探索手段、前記算出手段および前記判定手段による処理が実行された結果、前記第１の配線領域内の第１の最長配線経路の一部と前記第２の配線領域内の第２の最長配線経路の一部とを通過して前記第１の端子から前記第２の端子に辿り着くまでの最長配線経路を探索することを特徴とする請求項５に記載の設計支援プログラム。
【請求項７】
所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、前記所定の配線領域内でかつ前記配線経路と非接続な巡回路とを探索する探索手段と、
前記探索手段によって探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出する算出手段と、
前記算出手段によって算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する判定手段と、
前記判定手段によって判定された判定結果を出力する出力手段と、
を備えることを特徴とする設計支援装置。
【請求項８】
所定の配線領域内に配置された第１および第２の端子を接続する配線経路と、前記所定の配線領域内でかつ前記配線経路と非接続な巡回路とを探索する探索工程と、
前記探索工程によって探索された配線経路の配線経路長と巡回路の配線経路長とを合わせた配線経路長を算出する算出工程と、
前記算出工程によって算出された配線経路長が、仕様の回路特性を満たす配線経路長以上か否かを判定する判定工程と、
前記判定工程によって判定された判定結果を出力する出力工程と、
を含んだことを特徴とする設計支援方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２００９−１８７１２１（Ｐ２００９−１８７１２１Ａ）
【公開日】平成２１年８月２０日（２００９．８．２０）
【国際特許分類】
【出願番号】特願２００８−２４２３４（Ｐ２００８−２４２３４）
【出願日】平成２０年２月４日（２００８．２．４）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２１年８月２０日（２００９．８．２０）
【国際特許分類】
【出願日】平成２０年２月４日（２００８．２．４）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]