(57)【要約】【課題】線長を調整する領域の最適な大きさおよび位置を直感的に表現することで設計者に対する利便性の向上を図ること。【解決手段】表示例１は、配線パスの線長調整領域をその配線パスで構成される配線グループの近傍に表示させる例である。（Ａ）は、線長制約条件からの調整領域の導出例を示している。配線パスごとに、目標線長と線長との差分をとり、それぞれの配線パスの調整線長とする。このあと、調整線長を合計し、合計された調整線長を、線長調整領域換算関数に与えることで、線長調整領域の面積を得る。（Ｂ）は、（Ａ）で導出された面積分の線長調整領域を配線グループの近傍に描画した状態を示している。このように、配線グループに必要な線長調整領域を配線グループの近傍に表示することにより、配線グループを構成する配線パスの線長を長くして等長とするのに必要な面積を把握することができる。【選択図】図２
2011086267.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータを、
送信元から送信先までの配線グループを構成する複数の配線パスの中から、線長が最長となる特定の配線パスを選択する選択手段、
前記選択手段によって選択された特定の配線パスの線長に対する残余の配線パスの不足線長を検出する不足線長検出手段、
前記不足線長検出手段によって検出された前記残余の配線パスの不足線長の総和に応じた不足面積を算出する不足面積算出手段、
前記不足面積算出手段によって算出された不足面積の総和に応じた線長調整領域を、前記配線グループの近傍に割り当てる割当手段、
表示画面を制御して、前記配線グループと前記割当手段によって割当てられた線長調整領域とを前記表示画面に表示する表示制御手段、
として機能させることを特徴とする設計支援プログラム。
【請求項２】
前記コンピュータを、
前記各配線パスの並び順を検出する配列位置検出手段、
前記配列位置検出手段によって検出された前記各配線パスの配列順に従って、前記不足線長の列に比例関係があるか否かを判断する比例関係判断手段、
前記比例関係判断手段によって判断された判断結果に基づいて、前記特定の配線パスを含む境界線により前記配線グループを分割する分割手段として機能させ、
前記不足面積算出手段は、
前記分割手段による分割で得られた分割配線グループごとに、当該分割配線グループ内の残余の配線パスの不足線長の総和に応じた不足面積を算出し、
前記割当手段は、
前記分割配線グループごとに、前記不足面積に応じた線長調整を前記分割配線グループの近傍に割り当てることを特徴とする請求項１に記載の設計支援プログラム。
【請求項３】
前記コンピュータを、
前記比例関係判断手段によって比例関係がないと判断された場合、前記複数の配線パスのうち配列順が中央となる配線パスを前記特定の配線パスに再選択する再選択手段として機能させ、
前記分割手段は、
前記再選択手段によって再選択された特定の配線パスを含む境界線により前記配線グループを分割することを特徴とする請求項２に記載の設計支援プログラム。
【請求項４】
前記コンピュータを、
前記分割配線グループごとに、前記分割配線グループを迂回して前記境界線の一端から他端までの最短経路を探索する探索手段、
前記分割配線グループごとに、前記境界線と前記探索手段によって探索された最短経路とで囲まれた図形の中から、前記分割配線グループを迂回しかつ配線可能な迂回領域を取得する取得手段、
前記分割配線グループごとに、前記取得手段によって取得された迂回領域の面積が前記不足面積以下となるように調整することにより、線長調整領域を設定する設定手段として機能させ、
前記割当手段は、
前記設定手段によって設定された線長調整領域、前記配線グループの近傍に割り当てることを特徴とする請求項２または３に記載の設計支援プログラム。
【請求項５】
前記コンピュータを、
前記分割配線グループごとに、前記迂回領域の面積が前記不足面積以下であるか否かを判定する判定手段として機能させ、
前記探索手段は、
前記判定手段によって前記不足面積以下であると判定された場合、前記分割配線グループを最大限迂回して前記境界線の一端から他端までの最短経路をあらたに探索し、
前記取得手段は、
前記境界線と前記探索手段によってあらたに探索された最短経路とで囲まれた図形の中から、前記分割配線グループを迂回する迂回領域を取得することを特徴とする請求項４に記載の設計支援プログラム。
【請求項６】
前記コンピュータを、
前記判定手段によって前記不足面積以下であると判定された場合、前記境界線と前記探索手段によってあらたに探索された最短経路とで囲まれた図形を所定量拡大させた図形を作成する作成手段として機能させ、
前記取得手段は、
前記作成手段によって作成された図形の中から、前記分割配線グループを迂回する迂回領域を取得することを特徴とする請求項５に記載の設計支援プログラム。
【請求項７】
送信元から送信先までの配線グループを構成する複数の配線パスの中から、線長が最長となる特定の配線パスを選択する選択手段と、
前記選択手段によって選択された特定の配線パスの線長に対する残余の配線パスの不足線長を検出する不足線長検出手段と、
前記不足線長検出手段によって検出された前記残余の配線パスの不足線長の総和に応じた不足面積を算出する不足面積算出手段と、
前記不足面積算出手段によって算出された不足面積の総和に応じた線長調整領域を、前記配線グループの近傍に割り当てる割当手段と、
表示画面を制御して、前記配線グループと前記割当手段によって割当てられた線長調整領域とを前記表示画面に表示する表示制御手段と、
を備えることを特徴とする設計支援装置。
【請求項８】
選択手段、不足線長検出手段、不足面積算出手段、割当手段および表示制御手段を備えるコンピュータが、
前記選択手段により、送信元から送信先までの配線グループを構成する複数の配線パスの中から、線長が最長となる特定の配線パスを選択する選択工程と、
前記不足線長検出手段により、前記選択工程によって選択された特定の配線パスの線長に対する残余の配線パスの不足線長を検出する不足線長検出工程と、
前記不足面積算出手段により、前記不足線長検出工程によって検出された前記残余の配線パスの不足線長の総和に応じた不足面積を算出する不足面積算出工程と、
前記割当手段により、前記不足面積算出工程によって算出された不足面積の総和に応じた線長調整領域を、前記配線グループの近傍に割り当てる割当工程と、
前記表示制御手段により表示画面を制御して、前記配線グループと前記割当工程によって割当てられた線長調整領域とを前記表示画面に表示する表示工程、
を実行することを特徴とする設計支援方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プリント板やＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Iｎｔｅｇｒａｔｉｏｎ）での配線処理を実行する設計支援プログラム、設計支援装置、および設計支援方法に関する。
【背景技術】
【０００２】
近年、プリント板の配線設計においては、ＬＳＩの低電圧化、信号速度の高速化などにより、設計制約条件が指示されることが一般的になってきている。設計制約条件の中には、部品間を接続する配線パターンを流れる信号のタイミングを合わせるために、配線パスに対してその配線パスを流れる信号のディレイ（伝搬遅延）を元に換算した線長が指示されている。また、バスなどのような複数の配線パスからなる配線グループにおいてはその各配線パスのレシーバに対し入力タイミングが等しくなるようにディレイを合わせる指示がされている。
【０００３】
一般的に、配線設計は部品間の配線区間をエラーなく結線できることが確認できた後に、信号のディレイに関する制約を満足するように、既配線の線長調整をおこなう。しかし、線長調整できるような配線領域が残っていないような場合、配線グループの配線パターンをずらす、または、配線経路の検討からやり直すこととなり、配線設計に時間を要している。線長制約条件を遵守した配線設計においては、配線長の違反線長を示す表示が配線パターンを表示している画面とは別のウィンドウで表示される設計ツールがある（たとえば、下記特許文献１を参照。）。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平１１−１１０４３４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、上述した従来の設計ツールでは、配線パターンと違反線長の対応が取りづらいという問題があった。また、違反線長に対応する実際の配線パターン長がイメージしづらいという問題があった。したがって、線長調整に必要な配線領域が足りているのか不足なのかを判断するのは困難であるという問題があった。
【０００６】
本発明は、上述した従来技術による問題点を解消するため、線長を調整する領域の最適な大きさおよび位置を直感的に表現することで設計者に対する利便性の向上を図ることができる設計支援プログラム、設計支援装置、および設計支援方法を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上述した課題を解決し、目的を達成するため、本設計支援プログラム、設計支援装置、および設計支援方法は、送信元から送信先までの配線グループを構成する複数の配線パスの中から、線長が最長となる特定の配線パスを選択し、選択された特定の配線パスの線長に対する残余の配線パスの不足線長を検出し、検出された前記残余の配線パスの不足線長の総和に応じた不足面積を算出し、算出された不足面積の総和に応じた線長調整領域を、前記配線グループの近傍に割り当てて表示画面を制御して、前記配線グループと割当てられた線長調整領域とを前記表示画面に表示することを要件とする。
【発明の効果】
【０００８】
本設計支援プログラム、設計支援装置、および設計支援方法によれば、線長を調整する領域の最適な大きさおよび位置を直感的に表現することで設計者に対する利便性の向上を図ることができるという効果を奏する。
【図面の簡単な説明】
【０００９】
【図１】表示例１における線長調整領域の表示前の状態を示す説明図である。
【図２】表示例１における線長調整領域の表示後の状態を示す説明図である。
【図３】表示例２における線長調整領域の表示前後の状態を示す説明図である。
【図４】表示例３における線長調整領域の表示前後の状態を示す説明図である。
【図５】表示例４における線長調整領域の表示前の状態を示す説明図である。
【図６】表示例４における線長調整領域の表示後の状態を示す説明図である。
【図７】表示例５における線長調整領域の表示前の状態を示す説明図である。
【図８】表示例５における線長調整領域の表示後の状態を示す説明図である。
【図９】表示例６における線長調整領域の表示後の状態を示す説明図である。
【図１０】表示例７における線長調整領域の表示後の状態を示す説明図である。
【図１１】表示例８における線長調整領域の表示後の状態を示す説明図である。
【図１２】実施の形態にかかる設計支援装置のハードウェア構成を示すブロック図である。
【図１３】設計基準テーブルの記憶内容の一例を示す説明図である。
【図１４】基板テーブルの記憶内容の一例を示す説明図である。
【図１５】ネットテーブルの記憶内容の一例を示す説明図である。
【図１６】ランド形状テーブルの記憶内容の一例を示す説明図である。
【図１７】部品ピンテーブルの記憶内容の一例を示す説明図である。
【図１８】ビアテーブルの記憶内容の一例を示す説明図である。
【図１９】ラインテーブルの記憶内容の一例を示す説明図である。
【図２０】線長制約条件テーブルの記憶内容の一例を示す説明図である。
【図２１】配線パステーブルの記憶内容の一例を示す説明図である。
【図２２】配線ルートテーブルの記憶内容の一例を示す説明図である。
【図２３】線長調整テーブルの記憶内容の一例を示す説明図である。
【図２４】概略領域テーブルの記憶内容の一例を示す説明図である。
【図２５】線長領域テーブルの記憶内容の一例を示す説明図である。
【図２６】指示領域テーブルの記憶内容の一例を示す説明図である。
【図２７】仮配線テーブルの記憶内容の一例を示す説明図である。
【図２８】格子の構造体の記憶内容を示す説明図である。
【図２９】格子管理テーブルの構造体の記憶内容を示す説明図である。
【図３０】設計支援装置の機能的構成を示すブロック図である。
【図３１】本実施の形態にかかる設計支援装置による設計支援処理手順を示すフローチャート（その１）である。
【図３２】本実施の形態にかかる設計支援装置による設計支援処理手順を示すフローチャート（その２）である。
【図３３】本実施の形態にかかる設計支援装置による設計支援処理手順を示すフローチャート（その３）である。
【図３４】格子管理テーブルの一例を示す説明図である。
【図３５】格子管理テーブル作成処理の詳細な処理手順を示すフローチャート（その１）である。
【図３６】格子管理テーブル作成処理の詳細な処理手順を示すフローチャート（その２）である。
【図３７】障害物マッピング後の格子管理テーブルの一例を示す説明図である。
【図３８】障害物のマッピング処理の詳細な処理手順を示すフローチャート（その１）である。
【図３９】障害物のマッピング処理の詳細な処理手順を示すフローチャート（その２）である。
【図４０】障害物のマッピング処理の詳細な処理手順を示すフローチャート（その３）である。
【図４１】パターン占有率計算処理の具体例を示す説明図である。
【図４２】パターン占有率計算処理の詳細な処理手順を示すフローチャート（その１）である。
【図４３】パターン占有率計算処理の詳細な処理手順を示すフローチャート（その２）である。
【図４４】パターン占有率計算処理の詳細な処理手順を示すフローチャート（その３）である。
【図４５】配線ルートの概略配線処理の具体例を示す説明図である。
【図４６】配線ルートの概略配線処理（ステップＳ３１０８）の詳細な処理手順を示すフローチャートである。
【図４７】配線グループのマッピング処理の具体例を示す説明図である。
【図４８】配線グループのマッピング処理の詳細な処理手順を示すフローチャートである。
【図４９】未配線区間の概略配線処理（ステップＳ３２０９）の詳細な処理手順を示すフローチャート（その１）である。
【図５０】未配線区間の概略配線処理（ステップＳ３２０９）の詳細な処理手順を示すフローチャート（その２）である。
【図５１】未配線区間の概略配線処理（ステップＳ３２０９）の具体例を示す説明図である。
【図５２】格子の領域変換処理の詳細な処理手順を示すフローチャートである。
【図５３】格子の領域変換処理の具体例を示す説明図である。
【図５４】線長調整領域の概略決定処理（ステップＳ３３０４）の詳細な処理手順を示すフローチャート（その１）である。
【図５５】線長調整領域の概略決定処理（ステップＳ３３０４）の詳細な処理手順を示すフローチャート（その２）である。
【図５６】線長調整領域の概略決定処理（ステップＳ３３０４）の詳細な処理手順を示すフローチャート（その３）である。
【図５７】図形形状Ｒａとユーザの指示領域Ｒｚとの図形形状の積集合結果を示す説明図である。
【図５８】不足線長の比例関係に基づく線長調整領域の概略位置決定を示す説明図である。
【図５９】相関関係を示すグラフである。
【図６０】図５８で示したバスＢ１，Ｂ２での不足線長および相関係数を示す説明図である。
【図６１】ステップＳ５５０５で得られた座標配列Ｃｏ［］を示す説明図である。
【図６２】ステップＳ５５０６〜Ｓ５５０９における分割例を示す説明図である。
【図６３】概略領域割当後の格子管理テーブルＧａを示す説明図である。
【図６４】線長調整換算処理（ステップＳ５６０２，Ｓ５６０５）の詳細な処理手順を示すフローチャートである。
【図６５】概略領域割当処理（ステップＳ５６０３，Ｓ５６０６）の詳細な処理手順を示すフローチャート（その１）である。
【図６６】概略領域割当処理（ステップＳ５６０３，Ｓ５６０６）の詳細な処理手順を示すフローチャート（その２）である。
【図６７】概略領域割当処理（ステップＳ５６０３，Ｓ５６０６）の詳細な処理手順を示すフローチャート（その３）である。
【図６８】概略領域割当処理（ステップＳ５６０３，Ｓ５６０６）の詳細な処理手順を示すフローチャート（その４）である。
【図６９】概略領域割当処理（ステップＳ５６０３，Ｓ５６０６）の詳細な処理手順を示すフローチャート（その５）である。
【図７０】概略領域割当処理（ステップＳ５６０３，Ｓ５６０６）の詳細な処理手順を示すフローチャート（その６）である。
【図７１】概略領域割当処理の具体例１を示す説明図である。
【図７２】概略領域割当処理の具体例２を示す説明図である。
【図７３】概略領域割当処理の具体例３を示す説明図である。
【図７４】格子管理テーブルＧｂを示す説明図である。
【図７５】格子の領域変換処理（ステップＳ７０１４）の処理結果例を示す説明図である。
【図７６】格子配列の迂回領域取得処理の具体例を示す説明図である。
【図７７】格子配列の迂回領域取得処理の詳細な処理手順を示すフローチャート（その１）である。
【図７８】格子配列の迂回領域取得処理の詳細な処理手順を示すフローチャート（その２）である。
【図７９】格子配列の面積計算処理の具体例を示す説明図である。
【図８０】格子配列の面積計算処理の詳細な処理手順を示すフローチャートである。
【図８１】線長調整領域の詳細決定処理（ステップＳ３３０５）の詳細な処理手順を示すフローチャート（その１）である。
【図８２】線長調整領域の詳細決定処理（ステップＳ３３０５）の詳細な処理手順を示すフローチャート（その２）である。
【図８３】線長調整領域の詳細決定処理（ステップＳ３３０５）の詳細な処理手順を示すフローチャート（その３）である。
【図８４】線長調整領域の詳細決定処理（ステップＳ３３０５）の詳細な処理手順を示すフローチャート（その４）である。
【図８５】線長調整領域の詳細決定処理（ステップＳ３３０５）の具体例１を示す説明図である。
【図８６】線長調整領域の詳細決定処理（ステップＳ３３０５）の具体例２を示す説明図である。
【図８７】線長調整領域の詳細決定処理（ステップＳ３３０５）の具体例３を示す説明図である。
【図８８】詳細領域割当処理の具体例１を示す説明図である。
【図８９】詳細領域割当処理（ステップＳ８２０７／Ｓ８４０７）の詳細な処理手順を示すフローチャート（その１）である。
【図９０】詳細領域割当処理（ステップＳ８２０７／Ｓ８４０７）の詳細な処理手順を示すフローチャート（その２）である。
【図９１】詳細領域割当処理の具体例２を示す説明図である。
【図９２】図３３に示した線長調整領域のマッピング処理（ステップＳ３３０６）の詳細な処理手順を示すフローチャートである。
【図９３】図３３に示した線長調整領域の代替層割当処理（ステップＳ３３１１）の詳細な処理手順を示すフローチャートである。
【図９４】図３３に示した線長調整領域表示処理（ステップＳ３３１３）の詳細な処理手順を示すフローチャートである。
【発明を実施するための形態】
【００１０】
以下に添付図面を参照して、本発明にかかる設計支援プログラム、設計支援装置、および設計支援方法の好適な実施の形態を詳細に説明する。本実施の形態では、設計データにおいて、線長制約条件に違反する配線パスを自動的に検出し、線長の違反線長を元に、その配線パスの線長調整に必要な配線領域をその配線パスが属する配線グループの近くに表示させる。これにより、違反する配線グループの有無および線長調整に必要な配線領域（線長調整領域）を設計者に対して一つにまとめて示すことができる。
【００１１】
したがって、設計者は、配線結線前の段階で、配線接続関係を元にして各配線グループが使用する線長調整領域を視認しながら配線経路の検討に使用することができる。また、配線の結線作業において先に配線した配線グループの線長調整領域を残しながら配線することが可能となる。このようにして、後の線長調整を考慮しながら配線作業がおこなうことができるようになり、設計の手戻りなく効率的におこなうことができる。
【００１２】
なお、本明細書において、「配線パス」とは、部品ピンや配線の中継点を指示するためのビアなどを用いて配線対象の接続関係を示す情報である。また、「配線パターン」とは、配線パスにしたがって部品を電気的に接続するための導体となるラインを示すレイアウトデータである。
【００１３】
また、制約条件での線長は、物理的に接続している配線パターンを配線パスの接続関係と照らし合わせながら抽出し、抽出されたすべての配線パターンを線長制約条件で指定されている換算方法にしたがって配線パスの線長へと換算することで得られる。「違反線長」とは、線長制約条件の基準値の範囲より短い場合は不足している線長（負の値）を、長い場合は超過している線長（正の値）をいう。また、部品間を流れる信号のタイミングを調整するために、信号のディレイを線長に数値換算し、線長に関する制約として制約条件に定義し、線長を合わせることでディレイを合わせることを行っているが、線長に換算せずにディレイに関する制約として制約条件に定義していたとしても、内部で計算する値の単位が異なるだけであるため、ディレイを直接扱うことも可能である。
【００１４】
（表示例）
本実施の形態では、８種の表示例により設計者に違反する配線パスの有無および違反線長の長さを設計者に対して一つにまとめて表示する。以下、本実施の形態における表示例１〜１３について順次説明する。
【００１５】
＜表示例１＞
表示例１は、配線パスの線長調整領域をその配線パスで構成される配線グループの近傍に表示させる例である。線長調整領域とは、配線パスの線長を調整するための空き領域である。たとえば、ある配線パスが不足（違反線長が負の値）である場合、不足している違反線長分のラインを延ばして線長調整領域に引き回すことができる。以下、表示例１について図１および図２を用いて説明する。
【００１６】
図１は、表示例１における線長調整領域の表示前の状態を示す説明図である。表示例１において、（Ａ）は、設計対象となるトポロジの一例を示している。（Ｂ）は、トポロジでの線長制約条件を示している。（Ｃ）は、（Ａ）に示したトポロジを（Ｂ）の線長制約条件にしたがって配線したレイアウトである。バス１０３を構成する配線パスが配線させると、配線パターンとなる。
【００１７】
（Ａ）のトポロジ１００では、ドライバ１０１とレシーバ１０２とが、線長制約条件：ＢＵＳ０１で指定されたバス１０３により接続されている。
【００１８】
（Ｂ）の線長制約条件では、条件名、パス名、線長、基準値、および違反線長が規定されている。条件名とは、線長制約条件の条件名である。ここでは、ＢＵＳ０１が条件名である。なお、ＢＵＳ０１の線長条件として“±０．５ｍｍ”が規定されており、『各配線パスの線長は基準値（平均線長）から±０．５ｍｍ以内の等長配線』であることを意味している。なお、「等長」とは、線長条件を遵守する範囲の線長は線長制約条件を満たすことを意味している。
【００１９】
また、線長制約条件において、パス名は、線長制約条件で規定された配線パスの名称である。ここでは、バス１０３を構成する８本の配線パスの名称（ｐａｔｈ１〜ｐａｔｈ８）となる。なお、バス１０３を構成する配線パス群を配線グループと称す。
【００２０】
基準値とは、線長制約条件に規定されている配線パス（ここでは、ｐａｔｈ１〜ｐａｔｈ８）の基準となる情報である。基準値には、たとえば、線長制約条件に規定されている配線パスから選ばれた特定の配線パスの線長や線長制約条件に規定されている配線パスの平均線長が用いられる。ここでは、平均線長を基準値としている。
【００２１】
違反値とは、線長制約条件の基準値の範囲より短い場合は不足している線長を、長い場合は超過している線長をいう。具体的には、任意の配線パスについて、線長が基準値よりも大きい場合は、配線パスの線長から等長となる上限線長を引いた正の値が違反線長となる。一方、線長が基準値より小さい場合は、配線パスの線長から等長となる下限線長を引いた負の値が違反線長となる。なお、配線パスの線長が等長（上限線長と下限線長との間の長さ）である場合は、線長制約条件を遵守していることとなる。
【００２２】
たとえば、ｐａｔｈ１の線長は、１３０．０００［ｍｍ］、基準値は１２０．５００［ｍｍ］である。したがって、ｐａｔｈ１の線長１３０．０００［ｍｍ］から、上限線長である１２１．０００［ｍｍ］（＝１２０．５００［ｍｍ］＋０．５［ｍｍ］）を減算すると、＋９．０００［ｍｍ］（＞０）となる。したがって、ｐａｔｈ１の線長は、９．０００［ｍｍ］の長さ分超過していることとなる。
【００２３】
また、ｐａｔｈ４の線長は、１２０．０００［ｍｍ］、基準値は１２０．５００［ｍｍ］である。したがって、ｐａｔｈ４の線長１２０．０００［ｍｍ］から、下限線長である１２０．０００［ｍｍ］（＝１２０．５００［ｍｍ］−０．５［ｍｍ］）を減算すると、０［ｍｍ］となる。したがって、ｐａｔｈ４の線長は、線長制約条件を遵守していることとなる。
【００２４】
また、ｐａｔｈ８の線長は、１１２．０００［ｍｍ］、基準値は１２０．５００［ｍｍ］である。したがって、ｐａｔｈ８の線長１１２．０００［ｍｍ］から、下限線長である１２０．０００［ｍｍ］（＝１２０．５００［ｍｍ］−０．５［ｍｍ］）を減算すると、−８．０００［ｍｍ］（＜０）となる。したがって、ｐａｔｈ８の線長は、８．０００［ｍｍ］の長さ分不足していることとなる。
【００２５】
図２は、表示例１における線長調整領域の表示後の状態を示す説明図である。表示例１において、（Ａ）は、線長制約条件からの調整領域の導出例を示している。たとえば、配線パス（ｐａｔｈ１〜ｐａｔｈ８）のうち線長が最長となる配線パス（ｐａｔｈ１）をｐａｔｈ１の目標線長に決定する。残余のパス（ｐａｔｈ２〜ｐａｔｈ８）の目標線長は、最長の配線パス（ｐａｔｈ１）の線長の下限線長１２９．５００［ｍｍ］（１３０．００［ｍｍ］−０．５［ｍｍ］）に決定する。
【００２６】
そして、配線パスごとに、目標線長と線長との差分をとり、それぞれの配線パスの調整線長とする。このあと、調整線長を合計し（本例では、７２．５００［ｍｍ］）、合計された調整線長を、線長調整領域換算関数に与えることで、線長調整領域の面積（本例では、８７．５００［ｍｍ２］）を得る。（Ｂ）は、（Ａ）で導出された面積分の線長調整領域１０４をｐａｔｈ１〜ｐａｔｈ８の配線パスからなる配線グループの近傍に描画した状態を示している。
【００２７】
このように、配線グループに必要な線長調整領域を配線グループの近傍に表示することにより、配線グループを構成する配線パス（ｐａｔｈ１〜ｐａｔｈ８）の線長を長くして等長とするのに必要な面積を把握することができる。
【００２８】
＜表示例２＞
つぎに、表示例２について説明する。表示例２は、障害物を考慮した線長調整領域を配線グループの近傍に表示させる例である。
【００２９】
図３は、表示例２における線長調整領域の表示前後の状態を示す説明図である。（Ａ）は、表示例２における線長調整領域の表示前の状態を示す説明図である。（Ａ）では、ドライバ１０１、レシーバ１０２、配線グループを構成する配線パス（の配線パターン）が表示されている。さらに、ビアなどの障害物１０５も表示されている。（Ｂ）では、図２の（Ａ）に示したように得られた面積分の線長調整領域１０４を、障害物１０５に重ならないように、配線グループの近傍に表示する。
【００３０】
このように、障害物１０５を回避して線長調整領域１０４を表示することで、設計者に精度の高い見積もりを提示することができ、設計の効率化を図ることができる。
【００３１】
＜表示例３＞
つぎに、表示例３について説明する。表示例３は、設計者が指定した指示領域内で線長調整領域１０４を配線グループの近傍に表示させる例である。
【００３２】
図４は、表示例３における線長調整領域１０４の表示前後の状態を示す説明図である。（Ａ）は、表示例３における線長調整領域１０４の表示前の状態を示す説明図である。（Ａ）では、ドライバ１０１、レシーバ１０２、配線グループを構成する配線パス（の配線パターン）が表示されている。さらに、ビアなどの障害物１０５も表示されている。（Ｂ）では、図２の（Ａ）に示したように得られた面積分の線長調整領域１０４を、障害物１０５に重ならないように、かつ、設計者が指定した指示領域１０６内で、配線グループの近傍に表示する。
【００３３】
このように、指示領域１０６内に線長調整領域１０４を表示することで、設計者の意図を設計対象の見積もりへ反映させることができる。
【００３４】
＜表示例４＞
つぎに、表示例４について説明する。表示例４は、配線パターンの結線が未完成であっても、線長調整領域を表示する例である。具体的には、未配線区間の線長を論理計算で求め、論理計算結果の線長を元にして配線パスの線長制約条件の遵守／違反をチェックし、線長調整領域を表示する。以下、表示例４について、図５および図６を用いて説明する。
【００３５】
図５は、表示例４における線長調整領域１０４の表示前の状態を示す説明図である。表示例４において、（Ａ）は、設計対象となるトポロジの一例を示している。（Ｂ）は、トポロジでの線長制約条件を示している。（Ｃ）は、（Ａ）に示したトポロジを（Ｂ）の線長制約条件にしたがって配線したレイアウトである。バス１０３を構成する配線パスが配線させると、配線パターンとなる。
【００３６】
（Ａ）のトポロジ１００では、ドライバ１０１とレシーバ１０２とが、線長制約条件：ＢＵＳ０１で指定されたバス１０３により接続されている。
【００３７】
（Ｂ）の線長制約条件においては、ｐａｔｈ１〜ｐａｔｈ４が結線済みであるが、ｐａｔｈ５〜ｐａｔｈ８は未配線である。したがって、ｐａｔｈ１〜ｐａｔｈ８の平均値である基準値も求められず、これにともない、ｐａｔｈ１〜ｐａｔｈ８の違反線長も求められてない。したがって、（Ｃ）では、ｐａｔｈ１〜ｐａｔｈ８のうち、ｐａｔｈ１〜ｐａｔｈ４の配線パターンが表示される。
【００３８】
図６は、表示例４における線長調整領域１０４の表示後の状態を示す説明図である。表示例４において、（Ａ）は、線長制約条件からの線長調整領域１０４の導出例を示している。その前に、未配線の配線パス（ｐａｔｈ５〜ｐａｔｈ８）の仮線長を求める。具体的には、たとえば、マンハッタン長を仮線長とする。既結線の配線パス（ｐａｔｈ１〜ｐａｔｈ４）については、便宜上、線長を仮線長とする。
【００３９】
そして、配線パス（ｐａｔｈ１〜ｐａｔｈ８）のうち仮線長が最長となる配線パス（ｐａｔｈ１）をｐａｔｈ１の目標線長に決定する。残余のパス（ｐａｔｈ２〜ｐａｔｈ８）の目標線長は、最長の配線パス（ｐａｔｈ１）の仮線長の下限線長１２９．５００［ｍｍ］（１３０．００［ｍｍ］−０．５［ｍｍ］）に決定する。
【００４０】
そして、配線パスごとに、目標線長と仮線長との差分をとり、それぞれの配線パスの調整線長とする。このあと、調整線長を合計し（本例では、７２．５００［ｍｍ］）、合計された調整線長を、線長調整領域換算関数に与えることで、線長調整領域の面積（本例では、８７．５００［ｍｍ２］）を得る。（Ｂ）は、（Ａ）で導出された面積分の線長調整領域を既結線のｐａｔｈ１〜ｐａｔｈ４の配線パスからなる配線グループの近傍に描画した状態を示している。
【００４１】
このように、配線グループに必要な線長調整領域を既結線の配線パスとなる配線パターン近傍に表示することにより、未配線の配線パス（ｐａｔｈ５〜ｐａｔｈ８）があっても、配線グループを構成する配線パス（ｐａｔｈ１〜ｐａｔｈ８）の線長を長くして等長とするのに必要な面積を把握することができる。
【００４２】
＜表示例５＞
つぎに、表示例５について説明する。表示例５は、表示例４と同様、配線パターンの結線が未完成であっても、線長調整領域を表示する例である。具体的には、個々の配線パスではなく、配線グループの概略経路情報を元に配線パスの論理線長を求める。そして、論理計算の線長を元にして配線パスの線長制約条件の遵守／違反をチェックし、線長調整領域を表示する。
【００４３】
図７は、表示例５における線長調整領域の表示前の状態を示す説明図である。表示例５において、（Ａ）は、設計対象となるトポロジの一例を示している。（Ｂ）は、トポロジでの線長制約条件を示している。（Ｃ）は、（Ａ）に示したトポロジを（Ｂ）の線長制約条件にしたがって配線したレイアウトである。バス１０３を構成する配線パスが配線させると、配線パターンとなる。
【００４４】
（Ａ）のトポロジ１００では、ドライバ１０１とレシーバ１０２とが、線長制約条件：ＢＵＳ０１で指定されたバス１０３により接続されている。
【００４５】
（Ｂ）の線長制約条件においては、すべての配線パスｐａｔｈ１〜ｐａｔｈ８が未配線である。したがって、ｐａｔｈ１〜ｐａｔｈ８の平均値である基準値も求められず、これにともない、ｐａｔｈ１〜ｐａｔｈ８の違反線長も求められてない。したがって、（Ｃ）では、個々の配線パスではなく、ｐａｔｈ１〜ｐａｔｈ８を構成する配線グループをあらわすバス１０３（バス名：ＢＵＳ０１）が概略経路として表示される。
【００４６】
図８は、表示例５における線長調整領域の表示後の状態を示す説明図である。表示例５において、（Ａ）は、線長制約条件からの調整領域の導出例を示している。その前に、未配線の配線パス（ｐａｔｈ１〜ｐａｔｈ８）の仮線長を求める。具体的には、たとえば、マンハッタン長を仮線長とする。
【００４７】
そして、配線パス（ｐａｔｈ１〜ｐａｔｈ８）のうち仮線長が最長となる配線パス（ｐａｔｈ１）をｐａｔｈ１の目標線長に決定する。残余のパス（ｐａｔｈ２〜ｐａｔｈ８）の目標線長は、最長の配線パス（ｐａｔｈ１）の仮線長の下限線長１３０．０００［ｍｍ］（１３０．５０［ｍｍ］−０．５［ｍｍ］）に決定する。
【００４８】
そして、配線パスごとに、目標線長と仮線長との差分をとり、それぞれの配線パスの調整線長とする。このあと、調整線長を合計し（本例では、７６．０００［ｍｍ］）、合計された調整線長を、線長調整領域換算関数に与えることで、線長調整領域の面積（本例では、８８．５００［ｍｍ２］）を得る。（Ｂ）は、（Ａ）で導出された面積分の線長調整領域１０４を、ｐａｔｈ１〜ｐａｔｈ８を構成する配線グループをあらわすバス１０３（バス名：ＢＵＳ０１）の近傍に描画した状態を示している。
【００４９】
このように、未配線区間を論理計算により補完することにより、概略経路を基にして未配線状態でも配線パスの線長調整領域を表示することができる。したがって、未配線の配線グループに対しても概略経路により線長調整領域を確認することができる。
【００５０】
＜表示例６＞
つぎに、表示例６について説明する。表示例６は、表示例５において、配線グループが複数存在する場合の線長調整領域の表示例を示している。
【００５１】
図９は、表示例６における線長調整領域の表示後の状態を示す説明図である。図９において、具体的には、一方の配線グループの概略経路となるバス１０３と、ドライバ９０１とレシーバ１０２間の配線グループの概略経路となるバス９０２とが、表示されている。
【００５２】
そして、バス１０３の周囲には、バス１０３の線長調整領域１０４が表示され、バス９０２の周囲には、バス９０２の線長調整領域９０３が表示されている。表示例６では、線長調整領域１０４と線長調整領域９０３とが重ならないように調整して表示する。
【００５３】
これにより、複数の配線グループにおいて、線長調整領域が不足しているかどうかを同時に確認することができる。
【００５４】
＜表示例７＞
つぎに、表示例７について説明する。表示例７は、表示例２，３，６において、不足分の線長調整領域を表示する例である。ここでは代表例として表示例６において、不足分の線長調整領域を表示する例を説明する。
【００５５】
図１０は、表示例７における線長調整領域の表示後の状態を示す説明図である。図１０では、バス１０３を概略経路とする配線グループの線長調整領域１０４とバス９０２を概略経路とする配線グループの線長調整領域９０３とが表示されている。また、線長調整領域９０３は、領域不足とする。したがって、レイアウトがされていない空き領域に、不足分の面積に相当する不足領域１００１，１００２を表示する。
【００５６】
これにより、事前に線長調整領域が不足していることや不足している面積、不足している面積に相当する領域の配置先がわかるため、配線設計の手戻りの減少を図ることができる。なお、表示例７では、不足領域１００１，１００２を表示することとしたが、文字列や数値（たとえば、２０［ｍｍ２］など）により不足面積を表示してもよい。
【００５７】
＜表示例８＞
つぎに、表示例８について説明する。表示例８は、表示例２，３，６において、不足分の線長調整領域を表示する例である。ここでは代表例として表示例６において、不足分の線長調整領域を表示する例を、図１１を用いて説明する。
【００５８】
図１１は、表示例８における線長調整領域の表示後の状態を示す説明図である。図１１では、複数のレイヤＬ１，Ｌ２，Ｌ３，…について、それぞれレイアウトデータがある。たとえば、レイヤＬ２には、バス１０３を概略経路とする配線グループの線長調整領域１０４とバス９０２を概略経路とする配線グループの線長調整領域９０３とが表示されている。
【００５９】
ここで、たとえば、線長調整領域９０３が２０［ｍｍ２］分の領域不足であるとした場合、表示例７のように、同じレイヤＬ２において不足領域１００１，１００２を表示するのではなく、他のレイヤ（ここでは、レイヤＬ３）に不足領域１１００を表示させる。レイヤＬ２の線長調整領域９０３とレイヤＬ３の不足領域１１００とは、ビアを介して接続させる。
【００６０】
ここで、レイヤ３を不足領域専用のレイヤとすることで、レイヤ３を確認することで、設計者は不足分を直感的に理解することができる。また、不足領域１１００は線長調整領域９０３とビアで接続されているため、不足領域１１００をそのまま線長調整領域として利用することもできる。
【００６１】
（設計支援装置のハードウェア構成）
図１２は、実施の形態にかかる設計支援装置のハードウェア構成を示すブロック図である。図１２において、設計支援装置は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１２０１と、ＲＯＭ（Ｒｅａｄ‐Ｏｎｌｙ  Ｍｅｍｏｒｙ）１２０２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１２０３と、磁気ディスクドライブ１２０４と、磁気ディスク１２０５と、光ディスクドライブ１２０６と、光ディスク１２０７と、ディスプレイ１２０８と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）１２０９と、キーボード１２１０と、マウス１２１１と、スキャナ１２１２と、プリンタ１２１３と、を備えている。また、各構成部はバス１２００によってそれぞれ接続されている。
【００６２】
ここで、ＣＰＵ１２０１は、設計支援装置の全体の制御を司る。ＲＯＭ１２０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ１２０３は、ＣＰＵ１２０１のワークエリアとして使用される。磁気ディスクドライブ１２０４は、ＣＰＵ１２０１の制御にしたがって磁気ディスク１２０５に対するデータのリード／ライトを制御する。磁気ディスク１２０５は、磁気ディスクドライブ１２０４の制御で書き込まれたデータを記憶する。
【００６３】
光ディスクドライブ１２０６は、ＣＰＵ１２０１の制御にしたがって光ディスク１２０７に対するデータのリード／ライトを制御する。光ディスク１２０７は、光ディスクドライブ１２０６の制御で書き込まれたデータを記憶したり、光ディスク１２０７に記憶されたデータをコンピュータに読み取らせたりする。
【００６４】
ディスプレイ１２０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ１２０８は、たとえば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００６５】
インターフェース（以下、「Ｉ／Ｆ」と略する。）１２０９は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク１２１４に接続され、このネットワーク１２１４を介して他の装置に接続される。そして、Ｉ／Ｆ１２０９は、ネットワーク１２１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ１２０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００６６】
キーボード１２１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス１２１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００６７】
スキャナ１２１２は、画像を光学的に読み取り、設計支援装置内に画像データを取り込む。なお、スキャナ１２１２は、ＯＣＲ（Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅａｄｅｒ）機能を持たせてもよい。また、プリンタ１２１３は、画像データや文書データを印刷する。プリンタ１２１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。
【００６８】
（各種テーブル）
つぎに、本実施の形態で利用する各種テーブルの記憶内容について説明する。
【００６９】
図１３は、設計基準テーブル１３００の記憶内容の一例を示す説明図である。設計基準テーブル１３００とは、レイアウトを行う場合の設計基準が規定されたテーブルである。具体的には、たとえば、概略格子用の１格子当たりのサイズや詳細格子用の１格子当たりのサイズ、線長調整領域の塗りつぶしパターン番号（足りている）、線長調整領域の塗りつぶしパターン番号（不足している）、ライン−ライン間隙値、ライン−ビア間隙値などの線長制約条件の値が定義されている。配線パスは、設計基準に従ってレイアウトされる。
【００７０】
図１４は、基板テーブル１４００の記憶内容の一例を示す説明図である。基板テーブル１４００とは、基板の層数と基板の図形形状など基板に関する情報が規定されたテーブルである。たとえば、層数が８である場合、図１１に示したようなレイヤはＬ１〜Ｌ８となる。また、基板の図形形状は、図形形状の頂点座標で規定される。
【００７１】
図１５は、ネットテーブル１５００の記憶内容の一例を示す説明図である。ネットテーブル１５００とは、ネットごとに、ネットを特定するネット番号とネット名とを対応付けたテーブルである。
【００７２】
図１６は、ランド形状テーブル１６００の記憶内容の一例を示す説明図である。ランド形状テーブル１６００とは、ランドごとに、ランドを特定するランド形状番号とランドの形状情報とを対応付けたテーブルである。形状情報とは、形状を特定する情報であり、たとえば、ランドの形状が矩形である場合、矩形（を示す識別子）と対角となる２つの頂点座標となる。また、ランドの形状が円である場合、円（を示す識別子）と中心座標と半径となる。
【００７３】
図１７は、部品ピンテーブル１７００の記憶内容の一例を示す説明図である。部品ピンテーブル１７００とは、部品ピンごとに、部品ピンを特定する部品ピン番号、部品ピンが属するネットのネット番号、部品ピンの座標位置、部品ピンが配置される階層番号、該当するランド形状番号を対応付けたテーブルである。
【００７４】
図１８は、ビアテーブル１８００の記憶内容の一例を示す説明図である。ビアテーブル１８００とは、ビアごとに、ビアを特定するビア番号、ビアが属するネットのネット番号、ビアの座標位置、ビアが配置される階層番号、該当するランド形状番号を対応付けたテーブルである。
【００７５】
図１９は、ラインテーブル１９００の記憶内容の一例を示す説明図である。ラインテーブル１９００とは、ラインごとに、ラインを特定するライン番号、ラインが属するネットのネット番号、ラインのＦｒｏｍ−Ｔｏ座標位置、ラインの線幅、ラインが配線される階層番号を対応付けたテーブルである。ラインの線幅に従って描画すると配線パターンとなる。
【００７６】
図２０は、線長制約条件テーブル２０００の記憶内容の一例を示す説明図である。線長制約条件テーブル２０００とは、線長制約条件ごとに、線長制約条件を特定する制約条件番号、線長条件、線長基準、配線パス番号リスト、配線ルート番号リストを対応付けたテーブルである。線長条件とは、線長制約条件が許容する範囲を示しており、線長条件情報を遵守する配線パスは基準パス、違反する配線パスは違反パスとなる。
【００７７】
制約条件番号は、図１または図１０に示した条件名に対応する。線長基準とは、制約対象となる配線パスの基準を示す情報である。たとえば、特定の配線パスを基準とする場合、当該配線パスの配線パス番号（たとえば、配線パス番号２）が設定される。この場合、配線パス番号で特定される配線パスが基準パスとなる。また、制約対象となる配線パスの平均線長を線長基準としてもよい。線長基準で得られた値が、線長制約条件の基準値に相当する。
【００７８】
また、配線パス番号リストとは、その線長制約条件が課される配線パスを特定する配線パス番号を列挙したリストである。線長基準は、配線パス番号リストに基づいて設定される。たとえば、特定の配線パス番号を線長基準とする場合、配線パス番号リストの中から選ばれる。同様に、配線パスの平均線長の場合、配線パス番号リストにより特定される配線パス群の平均線長となる。
【００７９】
また、配線ルート番号リストとは、その配線パス番号リストで特定される配線グループ配線経路を規定する配線ルート番号を列挙したリストである。
【００８０】
図２１は、配線パステーブル２１００の記憶内容の一例を示す説明図である。配線パステーブル２１００とは、配線パスごとに、配線パスを特定する配線パス番号、配線接続順要素リスト、線長判定情報とを対応付けたテーブルである。
【００８１】
配線パス番号は、線長制約条件内のパス名に対応する。配線接続順要素リストとは、部品ピンやビアなどの配線要素を接続順に羅列したリストである。線長とは、配線パスの線長であり、線長制約条件内の線長に相当する。線長判定情報は、配線パスが線長制約条件を遵守したか違反したかの判定結果を示す情報である。「ＯＫ」である場合は、線長制約条件を遵守しており、数値である場合は、違反していることを示す。数値である場合、正の値であるときは、超過をあらわし、負の値であるときは、不足をあらわす。
【００８２】
図２２は、配線ルートテーブル２２００の記憶内容の一例を示す説明図である。配線ルートテーブル２２００とは、配線ルートごとに、配線ルートを特定する配線ルート番号、配線経路、配線される層（レイヤ）番号、代替層番号を対応付けたテーブルである。配線経路は、一連の座標値により定義される。
【００８３】
図２３は、線長調整テーブル２３００の記憶内容の一例を示す説明図である。線長調整テーブル２３００とは、線長制約条件ごとに、概略領域、指示領域、仮配線を対応付けたテーブルである。具体的には、線長制約条件番号ごとに、概略領域番号リスト、指示領域番号リスト、仮配線番号リストを対応付けている。たとえば、１行目のレコードでは、線長制約条件番号：１のレコードで特定される配線パスについて、概略領域番号：１の概略領域および指示領域番号：１の指示領域が概略領域として定義される。
【００８４】
図２４は、概略領域テーブル２４００の記憶内容の一例を示す説明図である。概略領域テーブル２４００とは、概略領域番号ごとに概略領域を特定するテーブルである。具体的には、概略領域番号ごとに、概略形状情報、階層番号、線長領域番号リスト、分割線を対応付けている。概略形状情報とは、概略領域の形状を特定する情報である。階層番号は、その概略領域が設定される階層を特定する番号である。線長領域番号リストとは、その概略領域において線長領域を特定する線長領域番号の一覧である。分割線とは、その概略領域を分割する分割線を通る頂点の座標群である。
【００８５】
図２５は、線長領域テーブル２５００の記憶内容の一例を示す説明図である。線長領域テーブル２５００とは、線長領域番号ごとに、配線パス番号リスト、不足面積、概略形状情報、詳細形状情報、詳細面積を対応付けたテーブルである。
【００８６】
図２６は、指示領域テーブル２６００の記憶内容の一例を示す説明図である。指示領域テーブル２６００とは、指示領域番号ごとに、指示形状情報、階層番号、概略形状情報を対応付けたテーブルである。
【００８７】
図２７は、仮配線テーブル２７００の記憶内容の一例を示す説明図である。仮配線テーブル２７００とは、仮配線番号ごとに、配線パス番号、未配線区間、階層番号、概略経路を対応付けたテーブルである。
【００８８】
図２８は、格子の構造体の記憶内容を示す説明図である。格子は、範囲｛Ａｘ１，Ａｙ１，Ａｘ２，Ａｙ２｝と、パターン占有率Ａｒ、障害物占有フラグＡｆ１、配線パス占有フラグＡｆ２、優先度Ａｐにより構造体を構成する。範囲｛Ａｘ１，Ａｙ１，Ａｘ２，Ａｙ２｝とは格子の形状を特定する情報であり、｛Ａｘ１，Ａｙ１｝を左上頂点、｛Ａｘ２，Ａｙ２｝を右下頂点とする矩形により格子を特定する。
【００８９】
図２９は、格子管理テーブルの構造体の記憶内容を示す説明図である。格子管理テーブルは、図形形状Ｇｒ、単位サイズＧｕ、個数Ｇｘ、個数Ｇｙ、格子配列Ｇａ［］により構造体を構成する。図形形状Ｇｒとは、与えられた図形形状Ｓを包含する矩形の図形形状である。単位サイズＧｕは、格子管理テーブルを構成する格子の単位サイズを特定する。個数Ｇｘとは、格子管理テーブルのｘ方向の格子の個数であり、個数Ｇｙとは、格子管理テーブルのｙ方向の格子の個数である。格子配列Ｇａ［］とは、格子管理テーブルに含まれている格子群である。
【００９０】
（設計支援装置の機能的構成）
図３０は、設計支援装置の機能的構成を示すブロック図である。設計支援装置３０００は、選択部３００１と、不足線長検出部３００２と、不足面積算出部３００３と、割当部３００４と、表示制御部３００５と、分割部３００８と、配列位置検出部３００６と、比例関係判断部３００７と、再選択部３００９と、探索部３０１０と、取得部３０１１と、設定部３０１２と、判定部３０１３と、作成部３０１４と、仮線長算出部３０１５と、を含む構成である。これら各機能は、具体的には、たとえば、図１２に示したＲＯＭ１２０２、ＲＡＭ１２０３、磁気ディスク１２０５、光ディスク１２０７などの記憶装置に記憶されたプログラムをＣＰＵ１２０１に実行させることにより、または、Ｉ／Ｆ１２０９により、その機能を実現する。
【００９１】
選択部３００１は、送信元から送信先までの配線グループを構成する複数の配線パスの中から、線長が最長となる特定の配線パスを選択する。送信元とは、たとえば、ドライバ１０１であり、送信先とは、たとえば、レシーバ１０２である。配線グループとは、たとえば、バス１０３のように複数の配線パスが一まとまりとなった配線パターンである。選択部３００１では、配線グループを構成する複数の配線パスの中から最大線長の配線パスを特定の配線パスとして選択する。これにより、それ以外の残余の配線パスは、特定の配線パスよりも線長が短いこととなる。選択部３００１は、後述の図５４に示したフローチャートのステップＳ５４０６の処理を実行する。
【００９２】
不足線長検出部３００２は、選択部３００１によって選択された特定の配線パスの線長に対する残余の配線パスの不足線長を検出する。具体的には、たとえば、特定の配線パスの線長から残余の配線パスの線長を減算することで、不足線長を検出する。
【００９３】
不足面積算出部３００３は、不足線長検出部３００２によって検出された残余の配線パスの不足線長の総和に応じた不足面積を算出する。具体的には、たとえば、不足線長検出部３００２で得られた不足面積の総和と、図１３の設計基準テーブル１３００から読み出された線長調整幅と、を乗算することで、配線グループにおける不足面積を算出する。
【００９４】
割当部３００４は、不足面積算出部３００３によって算出された不足面積の総和に応じた線長調整領域を、配線グループの近傍に割り当てる。近傍については、以下のように定義する。本実施の形態では、マトリクス状に配列された格子群となる格子管理テーブルを採用する。したがって、特定の配線パスから最も遠い残余の配線パスが含まれる格子や当該格子に隣接する格子が、まず、近傍として選ばれる。特定の配線パスから最も遠い残余の配線パスが含まれる格子については、当該格子の配線パターン占有率が所定以下である場合、十分配線可能となるため、近傍の対象とする。
【００９５】
また、領域は、不足面積を超えるまで配線グループの外側に段階的に拡大していく。さらに、概略的に線長調整領域が決まったら、格子管理テーブルを細分化して詳細な線長調整領域を決める。これらの詳細な処理については、フローチャートにおいて後述する。
【００９６】
表示制御部３００５は、表示画面を制御して、配線グループと割当部３００４によって割当てられた線長調整領域とを表示画面に表示する。また、表示例２で示したように、割当部３００４は、線長調整領域を、障害物がない配線グループの近傍に割り当てることとしてもよい。また、表示例３で示したように、割当部３００４は、線長調整領域を、配線グループの近傍のうち範囲指定された領域内に割り当てることとしてもよい。
【００９７】
配列位置検出部３００６は、各配線パスの並び順を検出する。比例関係判断部３００７は、配列位置検出部３００６によって検出された各配線パスの配列順に従って、不足線長の列に比例関係があるか否かを判断する。なお、比例関係の有無は、配線パスの配列順に従った不足線長の相関関係を求めることで判断される。
【００９８】
分割部３００８は、比例関係判断部３００７によって判断された判断結果に基づいて、特定の配線パスを含む境界線により配線グループを分割する機能を有する。分割部３００８では、比例関係があると判断された場合、特定の配列パスが配列方向の一端側に寄っているため、分割すると、一方がほとんど特定の配線パスしかなく、他方には残余の配線パスが多く含まれることとなる。
【００９９】
この場合、不足面積算出部３００３では、分割部３００８による分割で得られた分割配線グループごとに、当該分割配線グループ内の残余の配線パスの不足線長の総和に応じた不足面積を算出する。そして、割当部３００４では、分割配線グループごとに、不足面積に応じた線長調整を分割配線グループの近傍に割り当てる。
【０１００】
再選択部３００９は、比例関係判断部３００７によって比例関係がないと判断された場合、複数の配線パスのうち配列順が中央となる配線パスを特定の配線パスに再選択する機能を有する。具体的には、比例関係がない場合、不足線長はほぼ同一線長となる。したがって、このような場合は、特定の配線パスを基準に分割するのではなく、中央の配列位置の配線パスを基準にして分割することで、割当部３００４による割当の効率化を図る。
【０１０１】
探索部３０１０は、分割配線グループごとに、分割配線グループを迂回して境界線の一端から他端までの最短経路を探索する機能を有する。具体的には、たとえば、分割配線グループの図形形状を通らない（境界はよい）最短経路を探索する。
【０１０２】
取得部３０１１は、分割配線グループごとに、境界線と探索部３０１０によって探索された最短経路とで囲まれた図形の中から、分割配線グループを迂回しかつ配線可能な迂回領域を取得する。設定部３０１２は、分割配線グループごとに、取得部３０１１によって取得された迂回領域の面積が不足面積以下となるように調整することにより、線長調整領域を設定する。
【０１０３】
判定部３０１３は、分割配線グループごとに、迂回領域の面積が不足面積以下であるか否かを判定する。探索部３０１０は、判定部３０１３によって不足面積以下であると判定された場合、分割配線グループを最大限迂回して境界線の一端から他端までの最短経路をあらたに探索する。すなわち、最短経路が複数ある場合、最も迂回する経路を選択する。これにより、線長調整領域を大きくとることができる。そして、取得部３０１１は、境界線と探索部３０１０によってあらたに探索された最短経路とで囲まれた図形の中から、分割配線グループを迂回する迂回領域を取得する。
【０１０４】
作成部は、判定部３０１３によって不足面積以下であると判定された場合、境界線と探索部３０１０によってあらたに探索された最短経路とで囲まれた図形を所定量拡大させた図形を作成する。これにより、不足面積に到達するように図形を段階的に拡大させることができる。この場合、取得部３０１１は、作成部によって作成された図形の中から、分割配線グループを迂回する迂回領域を取得することとなる。
【０１０５】
仮線長算出部３０１５は、配線グループのうち未結線の配線パスの仮線長を算出する。具体的には、表示例４および表示例５のように、配線グループ内の配線パスの一部または全部が未結線であっても仮線長を用いることで、線長調整領域を割当てて表示するためである。この場合、選択部３００１は、仮線長算出部３０１５によって算出された仮線長を用いて、配線グループを構成する複数の配線パスの中から、特定の配線パスを選択する。
【０１０６】
また、不足線長検出部３００２は、仮線長算出部３０１５によって算出された仮線長を用いて、特定の配線パスの線長に対する残余の配線パスの不足線長を検出する。そして、不足面積算出部３００３は、仮線長算出部３０１５によって算出された仮線長を用いて、残余の配線パスの不足線長の総和に応じた不足面積を算出する。
【０１０７】
また、表示例６で示したように、割当部３００４は、他の線長調整領域と重複しないように割り当てることとしてもよい。また、表示例８に示したように、判定部３０１３は、不足面積に基づいて、線長調整領域の面積が充足しているか否かを判定する。この場合、割当部３００４は、判定部３０１３によって不足していると判定された場合、不足分の面積に相当する領域を他の階層に割り当てる。これにより、不足分を代替層に割当てることができる。
【０１０８】
また、判定部３０１３は、不足面積に基づいて、線長調整領域の面積が充足しているか否かを判定し、表示制御部３００５は、判定部３０１３によって不足していると判定された場合、線長調整領域が充足している場合と異なるように表示画面に表示する。すなわち、線長調整領域が不足する場合には、塗りつぶしパターンや文字表示などを用いることで、面積が不足していることがわかるように表示する。これにより、事前に線長調整領域が不足していることがわかるため、配線設計の手戻りの低減化を図ることができる。
【０１０９】
（設計支援処理手順）
つぎに、本実施の形態の設計支援処理手順について説明する。
【０１１０】
図３１〜図３３は、本実施の形態にかかる設計支援装置による設計支援処理手順を示すフローチャートである。まず、図３１において、ステップＳ３１０１〜Ｓ３１０３により、基板形状を大きめの格子サイズでメッシュに分割する。
【０１１１】
具体的には、図１４に示した基板テーブル１４００を参照して、設計対象となる基板の階層番号と図形形状を読み出して図形形状Ｂｄに設定する（ステップＳ３１０１）。つぎに、図１３に示した設計基準テーブル１３００を参照して（たとえば、番号１のレコードを参照）、概略格子用の１格子当たりのサイズを単位サイズＵａに設定する（ステップＳ３１０２）。そして、図形形状Ｂｄおよび単位サイズＵａを引数とし、格子管理テーブルＧａを返り値とする関数により、格子管理テーブル作成処理を実行する（ステップＳ３１０３）。
【０１１２】
格子管理テーブル作成処理（ステップＳ３１０３）の詳細については後述するが、格子管理テーブル作成処理（ステップＳ３１０３）により、格子管理テーブルＧａが返り値として得られる。格子管理テーブルＧａは、基板の図形形状Ｂｄを概略格子の単位サイズＵａでメッシュに分割したテーブルである。
【０１１３】
また、ステップＳ３１０４以降および図３２のステップＳ３２０１〜Ｓ３２１０により、格子管理テーブルＧａのメッシュとなる格子に配線パターン要素の情報を反映する。具体的には、まず、表示例２を実現するため、障害物のマッピング処理を実行する（ステップＳ３１０４）。障害物のマッピング処理（ステップＳ３１０４）の詳細については後述するが、障害物のマッピング処理（ステップＳ３１０４）では、格子管理テーブルＧａに障害物をマッピングする。
【０１１４】
つぎに、表示例５を実現するため、ステップＳ３１０５〜Ｓ３１０９を実行する。具体的には、ループ変数Ｉ１をＩ１＝１とし（ステップＳ３１０５）、Ｉ１が配線グループ数を超えたか否かを判断する（ステップＳ３１０６）。配線グループ数とは、線長制約条件の数であり、図２０のレコード数と一致する。
【０１１５】
Ｉ１が配線グループ数以下である場合（ステップＳ３１０６：Ｎｏ）、Ｉ１番目の線長制約条件での配線グループを、配線グループＲｇに設定する（ステップＳ３１０７）。具体的には、線長制約条件テーブル２０００において、Ｉ１番目の配線グループのレコードにある配線パス番号リストに列挙されている配線パス番号で特定される配線パス群を、配線グループＲｇとする。
【０１１６】
そして、配線ルートの概略配線処理を実行する（ステップＳ３１０８）。配線ルートの概略配線処理（ステップＳ３１０８）の詳細については後述するが、配線ルートの概略配線処理（ステップＳ３１０８）では、格子管理テーブルＧａおよび配線グループＲｇを引数とする。
【０１１７】
配線ルートの概略配線処理（ステップＳ３１０８）のあと、ループ変数Ｉ１をインクリメントして（ステップＳ３１０９）、ステップＳ３１０６に戻る。これにより、すべての線長制約条件について配線ルートの概略配線処理を実行することができる。そして、Ｉ１が配線グループ数を超えた場合（ステップＳ３１０６：Ｙｅｓ）、図３２のステップＳ３２０１に移行する。
【０１１８】
図３２においては、ステップＳ３１０６：Ｙｅｓのあと、ループ変数Ｉ１をＩ１＝１にリセットし（ステップＳ３２０１）、Ｉ１が配線グループ数を超えたか否かを判断する（ステップＳ３２０２）。
【０１１９】
Ｉ１が配線グループ数以下である場合（ステップＳ３２０２：Ｎｏ）、Ｉ１番目の線長制約条件での配線グループを、配線グループＲｇに設定する（ステップＳ３２０３）。具体的には、線長制約条件テーブル２０００において、Ｉ１番目の配線グループのレコードにある配線パス番号リストに列挙されている配線パス番号で特定される配線パス群を、配線グループＲｇとする。
【０１２０】
そして、配線グループのマッピング処理を実行する（ステップＳ３２０４）。配線グループのマッピング処理（ステップＳ３２０４）の詳細については後述するが、配線グループのマッピング処理（ステップＳ３２０４）では、格子管理テーブルＧａおよび配線グループＲｇを引数とする。
【０１２１】
配線グループのマッピング処理（ステップＳ３２０４）のあと、ループ変数Ｉ１をインクリメントして（ステップＳ３２０５）、ステップＳ３２０２に戻る。これにより、すべての線長制約条件について配線グループのマッピング処理を実行することができる。そして、Ｉ１が配線グループ数を超えた場合（ステップＳ３２０２：Ｙｅｓ）、ステップＳ３２０６に移行する。
【０１２２】
このあと、表示例４を実現するため、ループ変数Ｉ１をＩ１＝１にリセットし（ステップＳ３２０６）、Ｉ１が配線グループ数を超えたか否かを判断する（ステップＳ３２０７）。
【０１２３】
Ｉ１が配線グループ数以下である場合（ステップＳ３２０７：Ｎｏ）、Ｉ１番目の線長制約条件での配線グループを、配線グループＲｇに設定する（ステップＳ３２０８）。具体的には、線長制約条件テーブル２０００において、Ｉ１番目の配線グループのレコードにある配線パス番号リストに列挙されている配線パス番号で特定される配線パス群を、配線グループＲｇとする。
【０１２４】
そして、未配線区間の概略配線処理を実行する（ステップＳ３２０９）。未配線区間の概略配線処理（ステップＳ３２０９）の詳細については後述するが、未配線区間の概略配線処理（ステップＳ３２０９）では、格子管理テーブルＧａおよび配線グループＲｇを引数とする。
【０１２５】
未配線区間の概略配線処理（ステップＳ３２０９）のあと、ループ変数Ｉ１をインクリメントして（ステップＳ３２１０）、ステップＳ３２０７に戻る。これにより、すべての線長制約条件について未配線区間の概略配線処理を実行することができる。そして、Ｉ１が配線グループ数を超えた場合（ステップＳ３２０７：Ｙｅｓ）、図３３のステップＳ３３０１に移行する。
【０１２６】
つぎに、表示例６を実現するため、ステップＳ３３０１〜Ｓ３３０７により、線長調整領域の概略形状を決定し、さらに、詳細な領域を決定する。
【０１２７】
図３３において、ループ変数Ｉ２をＩ２＝１にリセットし（ステップＳ３３０１）、Ｉ２が配線グループ数を超えたか否かを判断する（ステップＳ３３０２）。Ｉ２が配線グループ数以下である場合（ステップＳ３３０２：Ｎｏ）、Ｉ２番目の線長制約条件での配線グループを、配線グループＲｇに設定する（ステップＳ３３０３）。具体的には、線長制約条件テーブル２０００において、Ｉ２番目の配線グループのレコードにある配線パス番号リストに列挙されている配線パス番号で特定される配線パス群を、配線グループＲｇとする。
【０１２８】
そして、線長調整領域の概略配線処理（ステップＳ３３０４）、線長調整領域の詳細配線処理（ステップＳ３３０５）および線長調整領域のマッピング処理（ステップＳ３３０６）を実行する。線長調整領域の概略配線処理（ステップＳ３３０４）、線長調整領域の詳細配線処理（ステップＳ３３０５）および線長調整領域のマッピング処理（ステップＳ３３０６）の詳細については後述するが、それぞれ、格子管理テーブルＧａおよび配線グループＲｇを引数とする。
【０１２９】
線長調整領域のマッピング処理（ステップＳ３３０６）のあと、ループ変数Ｉ２をインクリメントして（ステップＳ３３０７）、ステップＳ３３０２に戻る。これにより、すべての線長制約条件について線長調整領域の概略配線処理、詳細配線処理、マッピング処理を実行することができる。そして、Ｉ２が配線グループ数を超えた場合（ステップＳ３３０２：Ｙｅｓ）、ステップＳ３３０８に移行する。
【０１３０】
つぎに、表示例８を実現するため、ステップＳ３３０８〜Ｓ３３１２により、線長調整領域の不足分を代替層に割当てる。具体的には、まず、ループ変数Ｉ２をＩ２＝１にリセットし（ステップＳ３３０８）、Ｉ２が配線グループ数を超えたか否かを判断する（ステップＳ３３０９）。
【０１３１】
Ｉ２が配線グループ数以下である場合（ステップＳ３３０９：Ｎｏ）、Ｉ２番目の線長制約条件での配線グループを、配線グループＲｇに設定する（ステップＳ３３１０）。具体的には、線長制約条件テーブル２０００において、Ｉ２番目の配線グループのレコードにある配線パス番号リストに列挙されている配線パス番号で特定される配線パス群を、配線グループＲｇとする。
【０１３２】
そして、線長調整領域の代替層割当処理を実行する（ステップＳ３３１１）。線長調整領域の代替層割当処理（ステップＳ３３１１）の詳細については後述するが、線長調整領域の代替層割当処理（ステップＳ３３１１）では、配線グループＲｇを引数とする。
【０１３３】
線長調整領域の代替層割当処理（ステップＳ３３１１）のあと、ループ変数Ｉ２をインクリメントして（ステップＳ３３１２）、ステップＳ３３０９に戻る。これにより、すべての線長制約条件について線長調整領域の代替層割当処理を実行することができる。そして、Ｉ２が配線グループ数を超えた場合（ステップＳ３３０９：Ｙｅｓ）、線長調整領域表示処理を実行する（ステップＳ３３１３）。線長調整領域表示処理（ステップＳ３３１３）の詳細は後述するが、線長調整領域表示処理（ステップＳ３３１３）では、線長調整領域が表示されることとなる。
【０１３４】
＜格子管理テーブル作成処理＞
格子管理テーブル作成処理では、図形形状Ｓおよび単位サイズＵを引数とし、格子管理テーブルＧを返り値とする。
【０１３５】
図３４は、格子管理テーブルの一例を示す説明図である。ステップＳ３１０３において用いられる場合は、図形形状Ｓ＝Ｂｄ、単位サイズＵ＝Ｕａ、格子管理テーブルＧ＝Ｇａとする。
【０１３６】
図３５および図３６は、格子管理テーブル作成処理の詳細な処理手順を示すフローチャートである。まず、図３５において、格子管理テーブルＧの領域を確保し（ステップＳ３５０１）、図形形状Ｓを包含する矩形の図形形状を、図形形状Ｇ．Ｇｒに設定する（ステップＳ３５０２）。また、単位サイズＵを単位サイズＧ．Ｇｕに設定し（ステップＳ３５０３）、ｘ方向の格子個数Ｇ．Ｇｘを算出する（ステップＳ３５０４）。具体的には、図形形状Ｇ．Ｇｒのｘ方向の長さを単位サイズＧ．Ｇｕで割った値がｘ方向の格子個数Ｇ．Ｇｘとなる。
【０１３７】
同様にして、ｘ方向に直交するｙ方向の格子個数Ｇ．Ｇｙを算出する（ステップＳ３５０５）。具体的には、図形形状Ｇ．Ｇｒのｙ方向の長さを単位サイズＧ．Ｇｕで割った値がｙ方向の格子個数Ｇ．Ｇｙとなる。このあと、格子総数Ｇｚ（＝Ｇ．Ｇｘ×Ｇ．Ｇｙ）を算出し（ステップＳ３５０６）、Ｇｚ個の格子の記憶領域を格子配列Ｇ．Ｇａ［］に設定する（ステップＳ３５０７）。そして、図３６のステップＳ３６０１に移行する。
【０１３８】
つぎに、図３６において、ループ変数Ｉ１＝１（ステップＳ３６０１）、ループ変数Ｉ２＝１とし（ステップＳ３６０２）、Ｉ２＞Ｇ．Ｇｙであるか否かを判断する（ステップＳ３６０３）。Ｉ２＞Ｇ．Ｇｙでない場合（ステップＳ３６０３：Ｎｏ）、格子配列要素Ｇ．Ｇａ［Ｉ１，Ｉ２］の範囲Ａｘ１，Ａｙ１，Ａｘ２，Ａｙ２を設定する（ステップＳ３６０４）。格子配列要素Ｇ．Ｇａ［Ｉ１，Ｉ２］は、対角の位置にある頂点（Ａｘ１，Ａｙ１），（Ａｘ２，Ａｙ２）により表現された格子である。
【０１３９】
このあと、Ｉ２をインクリメントし（ステップＳ３６０５）、ステップＳ３６０３に戻る。ステップＳ３６０３において、Ｉ２＞Ｇ．Ｇｙである場合（ステップＳ３６０３：Ｙｅｓ）、Ｉ１＞Ｇ．Ｇｘであるか否かを判断する（ステップＳ３６０６）。Ｉ１＞Ｇ．Ｇｘでない場合（ステップＳ３６０６：Ｎｏ）、Ｉ１をインクリメントして（ステップＳ３６０７）、ステップＳ３６０２に戻ってＩ２をＩ２＝１にする。
【０１４０】
一方、Ｉ１＞Ｇ．Ｇｘである場合（ステップＳ３６０６：Ｙｅｓ）、格子配列要素Ｇ．Ｇａ［Ｉ１，Ｉ２］がすべて特定され、格子管理テーブルＧが返り値として得られる。これにより、格子管理テーブルＧの構造体が構築されることとなる。
【０１４１】
＜障害物のマッピング処理＞
障害物のマッピング処理では、格子管理テーブルＧに対して障害物のマッピングをおこなう。
【０１４２】
図３７は、障害物マッピング後の格子管理テーブルの一例を示す説明図である。ステップＳ３１０４において用いられる場合は、格子管理テーブルＧ＝Ｇａとする。格子管理テーブルＧには、線長調整領域の計算対象外の配線パターン要素（ライン要素やビア要素）がマッピングされる。図３７において、Ｓ３７０１は線長調整領域の計算対象の配線パターン要素であり、Ｓ３７０２は計算対象外の配線パターン要素である。この場合、Ｓ３７０２の配線パターン要素が格子管理テーブルＧに障害物マッピングされる。
【０１４３】
図３８〜図４０は、障害物のマッピング処理の詳細な処理手順を示すフローチャートである。図３８では、障害物となるラインのマッピング処理を、図３９では、障害物となるビアのマッピング処理を、図４０では、障害物となる部品ピンのマッピング処理について説明する。
【０１４４】
まず、図３８において、ループ変数Ｉ１をＩ１＝１とし（ステップＳ３８０１）、Ｉ１がライン数を超えているか否かを判断する（ステップＳ３８０２）。ライン数とは、図１９に示したラインテーブル１９００にエントリされているラインの総数である。
【０１４５】
Ｉ１がライン数を超えていない場合（ステップＳ３８０２：Ｎｏ）、Ｉ１番目のラインを配線要素Ｅ１に設定する（ステップＳ３８０３）。そして、配線要素Ｅ１は配線グループの配線パスの一部か否かを判断する（ステップＳ３８０４）。具体的には、配線要素Ｅ１のライン（Ｆｒｏｍ−Ｔｏ座標値で結ぶ線分）が、線長制約条件テーブル２０００の配線パス番号リストにより特定される配線パスに含まれているか否かを判断する。
【０１４６】
より具体的には、配線パスは、図２１の配線パステーブル２１００を参照することにより配線接続順要素リストで特定されるため、配線接続順要素リスト内の部品ピンやビアなどの座標値を図１７の部品ピンテーブル１７００や図１８のビアテーブル１８００を参照して取得し、取得された座標値を結ぶことで、配線パスとなる線分を特定する。この配線パスの線分に、配線要素Ｅ１のラインが位置するか否かを判断することとなる。
【０１４７】
そして、配線要素Ｅ１が配線グループの配線パスの一部である場合（ステップＳ３８０４：Ｙｅｓ）、障害物ではないため、ステップＳ３８０７に移行する。一方、一部でない場合（ステップＳ３８０４：Ｎｏ）、障害物となるため、配線要素Ｅ１の配線パターンの形状を図形形状Ｓ１に設定する（ステップＳ３８０５）。具体的には、図１９のラインテーブル１９００を参照して、配線要素Ｅ１のラインの線幅を取得してラインに線幅を反映することで、配線要素Ｅ１の配線パターンの形状を得る。この得られた形状を図形形状Ｓ１とする。
【０１４８】
つぎに、パターン占有率計算処理を実行する（ステップＳ３８０６）。パターン占有率計算処理（ステップＳ３８０６）については後述するが、格子管理テーブルＧ＝Ｇａ、図形形状Ｓ＝Ｓ１、図形種別フラグＦｋ＝１、加算フラグＦａ＝１とする。図形種別フラグＦｋ、加算フラグＦａについては後述する。これにより、格子配列Ｇｐ［］が得られる。
【０１４９】
図形形状Ｓ１についてパターン占有率が算出されたあと、ループ変数Ｉ１をインクリメントし（ステップＳ３８０７）、ステップＳ３８０２に戻る。ステップＳ３８０２において、Ｉ１がライン数を超えた場合（ステップＳ３８０２：Ｙｅｓ）、図３９のステップＳ３９０１に移行する。
【０１５０】
図３９において、ループ変数Ｉ２をＩ２＝１とし（ステップＳ３９０１）、Ｉ２がビア数を超えたか否かを判断する（ステップＳ３９０２）。ビア数とは、図１８に示したビアテーブル１８００にエントリされているビアの総数である。
【０１５１】
Ｉ２がビア数を超えていない場合（ステップＳ３９０２：Ｎｏ）、Ｉ２番目のビアを配線要素Ｅ２に設定する（ステップＳ３９０３）。そして、配線要素Ｅ２は配線グループの配線パスの一部か否かを判断する（ステップＳ３９０４）。具体的には、配線要素Ｅ２のビアの座標値が、線長制約条件テーブル２０００の配線パス番号リストにより特定される配線パスに含まれているか否かを判断する。
【０１５２】
より具体的には、配線パスは、図２１の配線パステーブル２１００を参照することにより配線接続順要素リストで特定されるため、配線接続順要素リスト内の部品ピンやビアなどの座標値を図１７の部品ピンテーブル１７００や図１８のビアテーブル１８００を参照して取得し、取得された座標値を結ぶことで、配線パスとなる線分を特定する。この配線パスの線分に、配線要素Ｅ２のビアが位置するか否かを判断することとなる。
【０１５３】
そして、配線要素Ｅ２が配線グループの配線パスの一部である場合（ステップＳ３９０４：Ｙｅｓ）、障害物ではないため、ステップＳ３９０７に移行する。一方、一部でない場合（ステップＳ３９０４：Ｎｏ）、障害物となるため、配線要素Ｅ２の配線パターンの形状を図形形状Ｓ２に設定する（ステップＳ３９０５）。
【０１５４】
具体的には、図１８のビアテーブル１８００を参照して、配線要素Ｅ２のビアのランド形状番号から図１６のランド形状テーブル１６００のレコードを特定する。この特定されたランド形状を、配線要素Ｅ２のビアの座標位置で反映することで、配線要素Ｅ２の配線パターンの形状を得る。この得られた形状を図形形状Ｓ２とする。
【０１５５】
つぎに、パターン占有率計算処理を実行する（ステップＳ３９０６）。パターン占有率計算処理（ステップＳ３９０６）については後述するが、格子管理テーブルＧ＝Ｇａ、図形形状Ｓ＝Ｓ２、図形種別フラグＦｋ＝１、加算フラグＦａ＝１とする。これにより、格子配列Ｇｐ［］が得られる。
【０１５６】
図形形状Ｓ２についてパターン占有率が算出されたあと、ループ変数Ｉ２をインクリメントし（ステップＳ３９０７）、ステップＳ３９０２に戻る。ステップＳ３９０２において、Ｉ２がビア数を超えた場合（ステップＳ３９０２：Ｙｅｓ）、図４０のステップＳ４００１に移行する。
【０１５７】
図４０において、ループ変数Ｉ３をＩ３＝１とし（ステップＳ４００１）、Ｉ３が部品ピン数を超えたか否かを判断する（ステップＳ４００２）。部品ピン数とは、部品ピンテーブル１７００にエントリされている部品ピンの総数である。
【０１５８】
Ｉ３が部品ピン数を超えていない場合（ステップＳ４００２：Ｎｏ）、Ｉ３番目の部品ピンを配線要素Ｅ３に設定する（ステップＳ４００３）。そして、配線要素Ｅ３は配線グループの配線パスの一部か否かを判断する（ステップＳ４００４）。具体的には、配線要素Ｅ３の部品ピンの座標値が、線長制約条件テーブル２０００の配線パス番号リストにより特定される配線パスに含まれているか否かを判断する。
【０１５９】
より具体的には、配線パスは、図２１の配線パステーブル２１００を参照することにより配線接続順要素リストで特定されるため、配線接続順要素リスト内の部品ピンや部品ピンなどの座標値を図１７の部品ピンテーブル１７００や図１８のビアテーブル１８００を参照して取得し、取得された座標値を結ぶことで、配線パスとなる線分を特定する。この配線パスの線分に、配線要素Ｅ３の部品ピンが位置するか否かを判断することとなる。
【０１６０】
そして、配線要素Ｅ３が配線グループの配線パスの一部である場合（ステップＳ４００４：Ｙｅｓ）、障害物ではないため、ステップＳ４００７に移行する。一方、一部でない場合（ステップＳ４００４：Ｎｏ）、障害物となるため、配線要素Ｅ３の配線パターンの形状を図形形状Ｓ３に設定する（ステップＳ４００５）。
【０１６１】
具体的には、図１７の部品ピンテーブル１７００を参照して、配線要素Ｅ３の部品ピンのランド形状番号から図１６のランド形状テーブル１６００のレコードを特定する。この特定されたランド形状を、配線要素Ｅ３の部品ピンの座標位置で反映することで、配線要素Ｅ３の配線パターンの形状を得る。この得られた形状を図形形状Ｓ３とする。
【０１６２】
つぎに、パターン占有率計算処理を実行する（ステップＳ４００６）。パターン占有率計算処理（ステップＳ４００６）については後述するが、格子管理テーブルＧ、図形形状Ｓ３、図形種別フラグＦｋ＝１、加算フラグＦａ＝１とする。これにより、格子配列Ｇｐ［］が得られる。
【０１６３】
図形形状Ｓ３についてパターン占有率が算出されたあと、ループ変数Ｉ３をインクリメントし（ステップＳ４００７）、ステップＳ４００２に戻る。ステップＳ４００２において、Ｉ３が部品ピン数を超えた場合（ステップＳ４００２：Ｙｅｓ）、障害物のマッピング処理を終了する。
【０１６４】
＜パターン占有率計算処理＞
図４１は、パターン占有率計算処理の具体例を示す説明図である。図４１では、説明を簡略化するため、３×３の格子配列要素Ｇ．Ｇａ［ｘ，ｙ］を用いて説明する。各格子配列要素Ｇ．Ｇａ［ｘ，ｙ］は、末尾の［ｘ，ｙ］で簡略化する。
【０１６５】
たとえば、図形４１０１〜４１０３で構成される図形４１００のうち、格子配列要素Ｇ．Ｇａ［１，２］内の図形４１０１の面積をＳａ、１格子あたりの面積をＳｒとすると、格子配列要素Ｇ．Ｇａ［１，２］のパターン占有率Ａｒは、
Ａｒ＝（Ｓａ÷Ｓｒ）×１００［％］
となる。格子配列要素Ｇ．Ｇａ［２，２］、Ｇ．Ｇａ［３，２］についても同様にパターン占有率Ａｒを求める。なお、他の格子配列要素Ｇ．Ｇａ［１，１］〜Ｇ．Ｇａ［３，１］、Ｇ．Ｇａ［１，３］〜Ｇ．Ｇａ［３，３］には図形がないため、Ａｒ＝０となる。そして、Ａｒ≠０の格子配列要素Ｇ．Ｇａ［１，２］〜Ｇ．Ｇａ［３，２］の組み合わせを示す格子配列Ｇｐ［］＝｛［１，２］,［２，２］,［３，２］｝を返り値として返す。
【０１６６】
図４２〜図４４は、パターン占有率計算処理の詳細な処理手順を示すフローチャートである。パターン占有率計算処理では、格子管理テーブルＧ、図形形状Ｓ、図形種別フラグＦｋ、加算フラグＦａを引数とし、最終的に格子配列Ｇｐ［］を返り値として得る。
【０１６７】
なお、パターン占有率計算処理（ステップＳ３８０６）では、図形形状Ｓ＝Ｓ１となり、パターン占有率計算処理（ステップＳ３９０６）では、図形形状Ｓ＝Ｓ２となり、パターン占有率計算処理（ステップＳ４００６）では、図形形状Ｓ＝Ｓ３となる。また、パターン占有率計算処理（ステップＳ３８０６，Ｓ３９０６，Ｓ４００６）では、格子管理テーブルＧは、格子管理テーブル作成処理（ステップＳ３１０３）で作成された格子管理テーブルＧａである。
【０１６８】
また、図形種別フラグＦｋとは、渡された図形形状の要素が障害物であるか配線パスであるかを識別するフラグである。Ｆｋ＝１の場合は障害物であり、Ｆｋ＝２の場合は配線パスである。なお、Ｆｋ＝０の場合、何もしないこととなる。
【０１６９】
また、加算フラグＦａとは、渡された図形形状が含まれている割合を加算するか否かを制御するフラグである。Ｆａ＝０の場合、加算せず、Ｆａ＝１の場合、加算することとする。パターン占有率計算処理（ステップＳ３８０６，Ｓ３９０６，Ｓ４００６）では、いずれもＦｋ＝１、Ｆａ＝１に設定される。
【０１７０】
なお、図形種別フラグＦｋと加算フラグＦａの組み合わせには、｛Ｆｋ＝０，Ｆａ＝０｝となる場合がある。この場合、引数として渡された図形形状Ｓと重なる格子だけを求めて格子配列Ｇｐ［］として返すことになる。
【０１７１】
まず、図４２において、格子配列Ｇｐ［］＝Φ（空集合）とし（ステップＳ４２０１）、図形形状Ｓを包含する矩形形状を図形形状Ｓｒとする（ステップＳ４２０２）。たとえば、パターン占有率計算処理（ステップＳ３８０６）では、配線要素Ｅ１の配線パターンの形状となる図形形状Ｓ１を包含する矩形形状が図形形状Ｓｒとなる。
【０１７２】
つぎに、図形形状Ｓｒと図形形状Ｇ．Ｇｒとの図形形状の積集合を、図形形状Ｓｒに設定する（ステップＳ４２０３）。図形形状Ｇ．Ｇｒは、格子管理テーブル作成処理（ステップＳ３１０３）のステップＳ３５０２における、図形形状Ｓを包含する矩形の図形形状である。ステップＳ３５０２での図形形状ＳはＳ＝Ｂｄ（基板の図形形状）であるため、ステップＳ４２０３の図形形状Ｇ．Ｇｒは、基板の図形形状Ｂｄを包含する矩形形状である。
【０１７３】
そして、積集合をとった図形形状Ｓｒの面積が０であるか否かを判断する（ステップＳ４２０４）。０でない場合（ステップＳ４２０４：Ｎｏ）、格子管理テーブルＧ（ステップＳ３８０６，Ｓ３９０６，Ｓ４００６では、基板の図形形状Ｂｄにおける格子管理テーブルＧａ）の格子座標系における図形形状Ｓｒが覆う矩形を格子矩形Ｇｒに設定する（ステップＳ４２０５）。そして、ステップＳ４３０１に移行する。
【０１７４】
また、図４３において、ループ変数Ｉ１をステップＳ４２０５で設定された格子矩形ＧｒのＸ座標の最小値（Ｘ座標ｍｉｎ）に設定するとともに（ステップＳ４３０１）、ループ変数Ｉ２をステップＳ４２０５で設定された格子矩形ＧｒのＹ座標の最小値（Ｙ座標ｍｉｎ）に設定する（ステップＳ４３０２）。
【０１７５】
そして、Ｉ２が格子矩形ＧｒのＹ座標の最大値（Ｙ座標ｍａｘ）を超えたか否かを判断する（ステップＳ４３０３）。超えた場合（ステップＳ４３０３：Ｙｅｓ）、Ｉ１をインクリメントして（ステップＳ４３０４）、Ｉ１が格子矩形ＧｒのＸ座標の最大値（Ｘ座標ｍａｘ）を超えたか否かを判断する（ステップＳ４３０５）。越えていない場合（ステップＳ４３０５：Ｎｏ）、ステップＳ４３０２に戻り、Ｉ２を再度格子矩形ＧｒのＹ座標の最小値に設定する。
【０１７６】
また、ステップＳ４３０３において、Ｉ２が格子矩形ＧｒのＹ座標の最大値を超えていない場合（ステップＳ４３０３：Ｎｏ）、格子配列要素Ｇ．Ｇａ［Ｉ１，Ｉ２］の範囲Ａｘ１，Ａｙ１，Ａｘ２，Ａｙ２でできる矩形形状（格子そのもの）を図形形状Ｓｒとする（ステップＳ４３０６）。
【０１７７】
そして、図形形状ＳとステップＳ４３０６で得られた図形形状Ｓｒとの図形形状の積集合を図形形状Ｓａとする（ステップＳ４３０７）。図４１を例に挙げると、格子配列要素Ｇ．Ｇａ［２，２］の格子の矩形形状がＳｒとなり、図形４１００がＳとなる。したがって、ＳとＳｒの図形形状の積集合Ｓａは図形形状４１０２となる。このあと、比率Ａｒを算出して（ステップＳ４３０８）、図４４のステップＳ４４０１に移行する。
【０１７８】
図４４において、比率ＡｒがＡｒ＝０であるか否かを判断する（ステップＳ４４０１）。Ａｒ＝０である場合（ステップＳ４４０１：Ｙｅｓ）、ステップＳ４４０８に移行する。一方、Ａｒ＝０でない場合（ステップＳ４４０１：Ｎｏ）、図形種別フラグＦｋの値を判断する（ステップＳ４４０２）。Ｆｋ＝０の場合（ステップＳ４４０２：０）、ステップＳ４４０５に移行する。
【０１７９】
Ｆｋ＝１の場合（ステップＳ４４０２：１）、格子配列要素Ｇ．Ｇａ［Ｉ１，Ｉ２］の障害物占有フラグＧ．Ｇａ［Ｉ１，Ｉ２］．Ａｆ１をＧ．Ｇａ［Ｉ１，Ｉ２］．Ａｆ１＝１に設定して（ステップＳ４４０３）、ステップＳ４４０５に移行する。また、Ｆｋ＝２の場合（ステップＳ４４０２：２）、格子配列要素Ｇ．Ｇａ［Ｉ１，Ｉ２］の配線パス占有フラグＧ．Ｇａ［Ｉ１，Ｉ２］．Ａｆ２をＧ．Ｇａ［Ｉ１，Ｉ２］．Ａｆ２＝１に設定して（ステップＳ４４０４）、ステップＳ４４０５に移行する。
【０１８０】
このあと、加算フラグＦａがＦａ＝１であるか否かを判断する（ステップＳ４４０５）。Ｆａ＝１でない場合（ステップＳ４４０５：Ｎｏ）、ステップＳ４４０７に移行する。一方、Ｆａ＝１である場合（ステップＳ４４０５：Ｙｅｓ）、格子配列要素Ｇ．Ｇａ［Ｉ１，Ｉ２］のパターン占有率Ｇ．Ｇａ［Ｉ１，Ｉ２］．Ａｒ（初期値は０）に比率Ａｒを加算して（ステップＳ４４０６）、パターン占有率Ｇ．Ｇａ［Ｉ１，Ｉ２］．Ａｒを更新する。
【０１８１】
そして、格子配列Ｇｐ［］と格子配列要素Ｇ．Ｇａ［Ｉ１，Ｉ２］との和集合をあらたな格子配列Ｇｐ［］にして（ステップＳ４４０７）、ループ変数Ｉ２をインクリメントする（ステップＳ４４０８）。このあと、図４３のステップＳ４３０３に戻る。
【０１８２】
なお、図４２のステップＳ４２０４において、積集合をとった図形形状Ｓｒの面積が０である場合（ステップＳ４２０４：Ｙｅｓ）、格子配列Ｇｐ［］を返してパターン占有率計算処理を終了する。同様に、図４３のステップＳ４３０５において、ループ変数Ｉ１が格子矩形ＧｒのＸ座標の最大値を超えた場合（ステップＳ４３０５：Ｙｅｓ）、格子配列Ｇｐ［］を返してパターン占有率計算処理を終了する。
【０１８３】
＜配線ルートの概略配線処理＞
つぎに、配線ルートの概略配線処理について説明する。配線ルートの概略配線処理では、図２０の線長制約条件テーブル２０００での線長制約条件ごとに特定される配線グループ（配線パス番号リストで特定される配線パス群）の配線ルート番号リストから、図２２の配線ルートテーブル２２００内の配線ルートを特定して、基板の図形形状Ｂｄの格子管理テーブルＧａに概略配線する処理である。
【０１８４】
図４５は、配線ルートの概略配線処理の具体例を示す説明図である。格子管理テーブルＧａには、配線ルートＲｒがマッピングされている。格子配列Ｇｐ［］は、配線ルートＲｒを含む格子の集合である。
【０１８５】
図４６は、配線ルートの概略配線処理（ステップＳ３１０８）の詳細な処理手順を示すフローチャートである。配線ルートの概略配線処理（ステップＳ３１０８）は、基板の図形形状Ｂｄの格子管理テーブルＧａと配線グループＲｇを引数とし、配線グループＲｇの概略配線となる図形形状Ｒａを返り値として返す関数である。
【０１８６】
まず、図３１のステップＳ３１０７で選ばれた配線グループＲｇの配線ルートを、配線ルートＲｒに設定する（ステップＳ４６０１）。具体的には、図２０に示した線長制約条件テーブル２０００から配線グループＲｇに相当するレコードの配線ルート番号を読み出し、図２２の配線ルートテーブル２２００の配線ルート番号をポイントすることで、配線ルートテーブル２２００から配線ルートを読み出して、配線ルートＲｒとする。
【０１８７】
そして、配線ルートＲｒがＲｒ＝Φ（空集合）であるか否かを判断する（ステップＳ４６０２）。空集合である場合（ステップＳ４６０２：Ｙｅｓ）、配線ルートＲｒがないため、概略配線することができず、配線ルートの概略配線処理（ステップＳ３１０８）を終了する。
【０１８８】
一方、Ｆｒ＝Φでない場合（ステップＳ４６０２：Ｎｏ）、配線ルートＲｒの図形形状をパターン占有率計算処理（ステップＳ４６０４）での引数となる図形形状Ｓに設定する（ステップＳ４６０３）。そして、パターン占有率計算処理を実行する（ステップＳ４６０４）。
【０１８９】
パターン占有率計算処理（ステップＳ４６０４）では、格子管理テーブルＧ＝Ｇａ、図形形状Ｓ＝Ｒｒ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ４６０４）では、引数として渡された配線ルートＲｒと重なる格子群となる格子配列Ｇｐ［］を返す。
【０１９０】
そして、格子配列Ｇｐ［］内のすべての格子のパターン占有率に所定値（＞０）を加算する（ステップＳ４６０５）。パターン占有率計算処理（ステップＳ４６０４）では、加算フラグＦａ＝０に設定しているため、格子配列Ｇｐ［］に入れられる格子配列要素Ｇ．Ｇａ［Ｉ１，Ｉ２］のパターン占有率Ｇ．Ｇａ［Ｉ１，Ｉ２］．Ａｒは、０のままである。したがって、格子配列Ｇｐ［］内のすべての格子に概略配線があるようにするため、格子配列要素Ｇ．Ｇａ［Ｉ１，Ｉ２］のパターン占有率Ｇ．Ｇａ［Ｉ１，Ｉ２］．Ａｒに所定値を加算しておく。
【０１９１】
このあと、格子の領域変換処理を実行する（ステップＳ４６０６）。格子の領域変換処理（ステップＳ４６０６）については後述するが、格子配列Ｇｐ［］を引数とし、配線グループＲｇの概略配線となる図形形状Ｒａを返り値とする関数である。
【０１９２】
そして、格子の領域変換処理（ステップＳ４６０６）で得られた図形形状Ｒａを配線グループＲｇと関連付けて記憶装置に記憶する（ステップＳ４６０７）。具体的には、配線グループＲｇに対応する線長調整テーブル２３００の概略領域番号リストに概略領域テーブル２４００の概略領域番号が設定されていない場合、（１）概略領域テーブル２４００に新規レコードを追加し、新規レコードの概略領域の概略形状情報に図形形状Ｒａを設定する。また、（２）配線グループＲｇに対応する線長調整テーブル２３００の概略領域番号リストに（１）で追加した新規レコードに設定した概略領域番号を追加する。
【０１９３】
一方、配線グループＲｇに対応する線長調整テーブル２３００の概略領域番号リストに概略領域テーブル２４００の概略領域番号が設定されている場合、（３）配線グループＲｇに対応する線長調整テーブル２３００の概略領域番号リストにある概略領域番号が指す概略領域テーブル２４００のレコードの概略形状情報を図形形状Ｒａで更新する。これにより、配線ルートの概略配線処理を終了する。
【０１９４】
＜配線グループのマッピング処理＞
つぎに、配線グループのマッピング処理について説明する。配線グループのマッピング処理では、配線グループ内の配線パスを格子管理テーブルＧ（＝Ｇａ）上に順次マッピングする関数である。
【０１９５】
図４７は、配線グループのマッピング処理の具体例を示す説明図である。図４７において、（Ａ）では、格子管理テーブルＧａ上に配線グループＲｇを構成する配線パスＲｐが順次マッピングされている。その後、（Ｂ）では、マッピングされたすべての配線パスＲｐを包含する図形形状Ｒａを取得する。
【０１９６】
図４８は、配線グループのマッピング処理の詳細な処理手順を示すフローチャートである。配線グループのマッピング処理では、格子管理テーブルＧおよび配線グループＲｇを引数とし、図形形状Ｒａを返り値として返す。なお、図３２に示した配線グループのマッピング処理（ステップＳ３２０４）では、格子管理テーブルＧ＝Ｇａに設定される。
【０１９７】
まず、格子配列Ｇｐ［］＝Φ（空集合）とし（ステップＳ４８０１）、ループ変数Ｉ１をＩ１＝１とする（ステップＳ４８０２）。そして、Ｉ１が配線グループＲｇの配線パス数を超えたか否かを判断する（ステップＳ４８０３）。超えていない場合（ステップＳ４８０３：Ｎｏ）、配線グループＲｇに定義されている配線パスのＩ１番目の配線パス番号をＪ１とし（ステップＳ４８０４）、Ｊ１番目の配線パスを配線パスＲｐとする（ステップＳ４８０５）。具体的には、線長制約条件テーブル２０００の対象となる線長制約条件のレコードにおける配線パス番号リストの先頭（左端）からの位置がＪ１となる。
【０１９８】
つぎに、ループ変数Ｉ２をＩ２＝１とし（ステップＳ４８０６）、Ｉ２が配線パスＲｐの配線パターン要素数を超えたか否かを判断する（ステップＳ４８０７）。配線パターン要素とは、配線パステーブル２１００の配線接続順要素リストに挙げられている部品ピンやビアである。配線パターン要素数とは、配線パスＲｐにおける配線接続順要素リスト内の部品ピンやビアの総数である。
【０１９９】
Ｉ２が配線パスＲｐの配線パターン要素数を超えていない場合（ステップＳ４８０７：Ｎｏ）、配線パスＲｐの配線パターン要素のＩ２番目の番号をＪ２とし（ステップＳ４８０８）、配線パスＲｐのＪ２番目の配線パターン要素を、配線パターン要素Ｅ１にする（ステップＳ４８０９）。具体的には、配線パステーブル２１００の対象となる配線パスＲｐのレコードにおける配線接続順要素リストの先頭（左端）からの位置がＪ２となる。
【０２００】
そして、配線パターン要素Ｅ１の配線パターンの形状を図形形状Ｓ１に設定する（ステップＳ４８１０）。たとえば、Ｊ２が配線パスＲｐのレコードにおける配線接続順要素リストの先頭位置である場合、その配線パターン要素Ｅ１（部品ピンまたはビア）の図形形状が図形形状Ｓ１となる。また、Ｊ２が先頭から２番目以降である場合、（Ｊ２−１）番目の配線パターン要素からのラインの図形形状とＪ２番目の配線パターン要素Ｅ１（部品ピンまたはビア）の図形形状との組み合わせが図形形状Ｓ１となる。このあと、パターン占有率計算処理を実行する（ステップＳ４８１１）。
【０２０１】
パターン占有率計算処理（ステップＳ４８１１）では、格子管理テーブルＧ＝Ｇａ、図形形状Ｓ＝Ｓ１、図形種別フラグＦｋ＝２、加算フラグＦａ＝１に設定して、図４２に示した処理手順にしたがって実行する。パターン占有率計算処理（ステップＳ４８１１）では、配線パターン要素Ｅ１の配線パターンの形状である図形形状Ｓ１を構成する格子群を格子配列Ｇｐ１［］として返す。
【０２０２】
そして、格子配列Ｇｐ［］（初期値はΦ）と格子配列Ｇｐ１［］との和集合をとり、あらたな格子配列Ｇｐ［］とする（ステップＳ４８１２）。そして、Ｉ２をインクリメントして（ステップＳ４８１３）、ステップＳ４８０７に戻る。
【０２０３】
一方、ステップＳ４８０７において、ループ変数Ｉ２が配線パスＲｐの配線パターン要素数を超えた場合（ステップＳ４８０７：Ｙｅｓ）、ループ変数Ｉ１をインクリメントして（ステップＳ４８１４）、ステップＳ４８０３に戻る。
【０２０４】
一方、ステップＳ４８０３において、ループ変数Ｉ１が配線グループＲｇの配線パス数を超えた場合（ステップＳ４８０３：Ｙｅｓ）、格子の領域変換処理を実行する（ステップＳ４８１５）。格子の領域変換処理（ステップＳ４８１５）では、格子配列Ｇｐ［］を引数とし、図形形状Ｒａを返り値として返す。
【０２０５】
そして、マッピングされたすべての配線パスＲｐを包含する図形形状Ｒａ（図４７（Ｂ）を参照）を配線グループＲｇに関連付けて記憶装置に記憶する（ステップＳ４８１６）。具体的には、配線グループＲｇに対応する線長調整テーブル２３００の概略領域番号リストに概略領域テーブル２４００の概略領域番号が設定されていない場合、（１）概略領域テーブル２４００に新規レコードを追加し、新規レコードの概略領域の概略形状情報に図形形状Ｒａを設定する。また、（２）配線グループＲｇに対応する線長調整テーブル２３００の概略領域番号リストに（１）で追加した新規レコードに設定した概略領域番号を追加する。
【０２０６】
一方、配線グループＲｇに対応する線長調整テーブル２３００の概略領域番号リストに概略領域テーブル２４００の概略領域番号が設定されている場合、（３）配線グループＲｇに対応する線長調整テーブル２３００の概略領域番号リストにある概略領域番号が指す概略領域テーブル２４００のレコードの概略形状情報を図形形状Ｒａで更新する。これにより、配線グループのマッピング処理を終了する。
【０２０７】
＜未配線区間の概略配線処理＞
つぎに、表示例４を実現するための未配線区間の概略配線処理（ステップＳ３２０９）について説明する。未配線区間の概略配線処理（ステップＳ３２０９）では、表示例４で示したように、未配線区間を概略配線した場合の図形形状を求める処理である。未配線区間の概略配線処理（ステップＳ３２０９）は、格子管理テーブルＧａと配線グループＲｇを引数とし、図形形状Ｒａを返り値として返す関数である。
【０２０８】
図４９および図５０は、未配線区間の概略配線処理（ステップＳ３２０９）の詳細な処理手順を示すフローチャートである。まず、図４９において、配線グループＲｇに関連付けられた図形形状を図形形状Ｒａに設定する（ステップＳ４９０１）。そして、図形形状Ｒａを単位サイズＧ．Ｇｕだけ拡大する（ステップＳ４９０２）。このあと、図４２に示したパターン占有率計算処理を実行する（ステップＳ４９０３）。
【０２０９】
パターン占有率計算処理（ステップＳ４９０３）では、格子管理テーブルＧ＝Ｇａ、図形形状Ｓ＝Ｒａ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ４９０３）では、引数として渡された図形形状Ｒａと重なる格子群となる格子配列Ｇｐ［］を返す。
【０２１０】
また、格子配列Ｇｐ２［］＝Φ（空集合）とし（ステップＳ４９０４）、ループ変数Ｉ１＝１にする（ステップＳ４９０５）。そして、Ｉ１が配線グループＲｇ内の配線パス数を超えたか否かを判断する（ステップＳ４９０６）。
【０２１１】
超えていない場合（ステップＳ４９０６：Ｎｏ）、配線グループＲｇに定義されている配線パスのＩ１番目の番号をＪ１とし（ステップＳ４９０７）、配線パス番号Ｊ１の配線パスを配線パスＲｐとする（ステップＳ４９０８）。そして、図５０のステップＳ５００１に移行する。
【０２１２】
一方、ステップＳ４９０６において、ループ変数Ｉ１が配線グループ内の配線パス数を超えた場合（ステップＳ４９０６：Ｙｅｓ）、格子配列Ｇｐ２［］＝Φであるか否かを判断する（ステップＳ４９０９）。Ｇｐ２［］＝Φである場合（ステップＳ４９０９：Ｙｅｓ）、図形形状Ｒａが得られず、未配線区間の概略配線処理（ステップＳ３２０９）を終了する。
【０２１３】
一方、Ｇｐ２［］＝Φでない場合（ステップＳ４９０９：Ｎｏ）、配線グループＲｇに関連付けられた図形形状を図形形状Ｒａに設定する（ステップＳ４９１０）。そして、図４２に示したパターン占有率計算処理を実行する（ステップＳ４９１１）。
【０２１４】
パターン占有率計算処理（ステップＳ４９１１）では、格子管理テーブルＧ＝Ｇａ、図形形状Ｓ＝Ｒａ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ４９１０）では、引数として渡された図形形状Ｒａと重なる格子群となる格子配列Ｇｐ［］を返す。
【０２１５】
そして、得られた格子配列Ｇｐ［］と格子配列Ｇｐ１［］との和集合をとり（ステップＳ４９１２）、格子の領域変換処理を実行する（ステップＳ４９１３）。格子の領域変換処理（ステップＳ４９１３）では、格子配列Ｇｐ［］を引数とし、図形形状Ｒａを返り値として返す。
【０２１６】
このあと、得られた図形形状Ｒａを配線グループＲｇに関連付けて記憶装置に記憶する（ステップＳ４９１４）。具体的には、配線グループＲｇに対応する線長調整テーブル２３００の概略領域番号リストに概略領域テーブル２４００の概略領域番号が設定されていない場合、（１）概略領域テーブル２４００に新規レコードを追加し、新規レコードの概略領域の概略形状情報に図形形状Ｒａを設定する。また、（２）配線グループＲｇに対応する線長調整テーブル２３００の概略領域番号リストに（１）で追加した新規レコードに設定した概略領域番号を追加する。
【０２１７】
一方、配線グループＲｇに対応する線長調整テーブル２３００の概略領域番号リストに概略領域テーブル２４００の概略領域番号が設定されている場合、（３）配線グループＲｇに対応する線長調整テーブル２３００の概略領域番号リストにある概略領域番号が指す概略領域テーブル２４００のレコードの概略形状情報を図形形状Ｒａで更新する。これにより、未配線区間の概略配線処理を終了する。
【０２１８】
また、図５０において、Ｊ１番目の配線パスＲｐに未配線区間があるか否かを判断する（ステップＳ５００１）。未配線区間がある場合（ステップＳ５００１：Ｙｅｓ）、未配線区間の両端座標を区間座標Ｃｄ１，Ｃｄ２に設定する（ステップＳ５００２）。また、区間座標Ｃｄ１，Ｃｄ２に対応する格子管理テーブルＧ（＝Ｇａ）上の格子を格子Ｇ１，Ｇ２とする（ステップＳ５００３）。
【０２１９】
そして、パターン占有率計算処理（ステップＳ４９０３）で得られた格子配列Ｇｐ［］における格子Ｇ１から格子Ｇ２までの最短経路１の格子の並びを、格子配列Ｇｐ１［］とする（ステップＳ５００４）。この最短経路１の探索条件は、以下の１）〜３）とする。
１）始点から終点までの最短経路
２）ただし、１）において、最短経路を元に架空の配線パターンを生成し、経路上の格子にその配線パターンを加算しても１００％を超える格子は存在しないこと
３）ただし、１）において、同じ長さの経路が複数見つかる場合は格子のパターン占有率の総和が最大となる経路を選択する
【０２２０】
このあと、格子配列Ｇｐ１［］＝Φ（空集合）であるか否かを判断する（ステップＳ５００５）。Ｇｐ１［］=Φでない場合（ステップＳ５００５：Ｎｏ）、格子配列Ｇｐ１［］のすべての格子のパターン占有率にライン１本通過分の占有率を加算しておく（ステップＳ５００６）。
【０２２１】
そして、格子配列Ｇｐ１［］のすべての格子の配線パス占有フラグＡｆ２をＡｆ２＝１にする（ステップＳ５００７）。このあと、格子配列Ｇｐ１［］を座標配列Ｃｏ［］とし（ステップＳ５００８）、座標配列Ｃｏ［］に基づいて仮配線経路を求める（ステップＳ５００９）。そして、求められた仮配線経路の座標配列Ｃｏ［］を配線パスＲｐに関連付けて記憶装置に記憶する（ステップＳ５０１０）。
【０２２２】
具体的には、（１）仮配線テーブル２７００に新規レコードを追加し、仮配線経路の座標配列Ｃｏ［］を未配線区間に設定する。そして、（２）上記（１）の新規レコードの仮配線番号を線長調整テーブル２３００の配線グループＲｇに対応する線長調整番号のレコードの仮配線番号リストに追加する。
【０２２３】
つぎに、格子配列Ｇｐ２［］と格子配列Ｇｐ１［］との和集合をとって格子配列Ｇｐ２［］とし（ステップＳ５０１１）、ステップＳ５００１に戻る。また、ステップＳ５００５において、Ｇｐ１［］＝Φである場合（ステップＳ５００５：Ｙｅｓ）、Ｇｐ［］＝Ｇ．Ｇａ［］であるか否かを判断する（ステップＳ５０１２）。すなわち、これ以上、拡大できるか否かを判断する。
【０２２４】
Ｇｐ［］＝Ｇ．Ｇａ［］でない場合（ステップＳ５０１２：Ｎｏ）、図形形状Ｒａを単位サイズＧ．Ｇｕだけ拡大して（ステップＳ５０１３）、図４２に示したパターン占有率計算処理を実行する（ステップＳ５０１４）。
【０２２５】
パターン占有率計算処理（ステップＳ５０１４）では、格子管理テーブルＧ＝Ｇａ、図形形状Ｓ＝Ｒａ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ５０１４）では、引数として渡された図形形状Ｒａと重なる格子群となる格子配列Ｇｐ［］を返す。このあと、ステップＳ５００４に戻る。
【０２２６】
一方、ステップＳ５０１２において、Ｇｐ［］＝Ｇ．Ｇａ［］である場合（ステップＳ５０１２：Ｙｅｓ）、これ以上の拡大はできないため、図４９のステップＳ４９０９に戻る。
【０２２７】
また、ステップＳ５００１において、配線パスＲｐに未配線区間がない場合（ステップＳ５００１：Ｎｏ）、ループ変数Ｉ１をインクリメントして（ステップＳ５０１５）、図４９のステップＳ４９０６に戻る。ここで、未配線区間の概略配線処理（ステップＳ３２０９）の具体例について説明する。
【０２２８】
図５１は、未配線区間の概略配線処理（ステップＳ３２０９）の具体例を示す説明図である。（Ａ）は、図５０のステップＳ５００６〜Ｓ５０１１までの処理の具体例を示している。仮配線経路を求めるため、図形形状Ｒａを単位サイズＧ．Ｇｕ分拡大しておく（ステップＳ４９０２）。最短経路１を構成する格子の並びである格子配列Ｇｐ１［］は、図形形状Ｒａ内で求める。
【０２２９】
最短経路１に仮配線されるとすると、１ライン分の配線パターンが入るため、ステップＳ５００６のような処理をしておく。そして、最短経路１の探索条件に従って、仮配線経路を求める。仮配線経路は最短経路１と同じ経路になる場合もあり、異なる場合もある。座標配列Ｃｏ［］は、仮配線経路を構成する格子の代表座標列とする。代表座標は、格子の特定の頂点座標でもよく中心座標でもよい。
【０２３０】
（Ｂ）は、図４９のステップＳ４９１０〜Ｓ４９１４までの処理の具体例を示している。図形形状Ｒａは、格子の領域変換処理（ステップＳ４９１３）によって得られた図形形状である。これにより、未配線の概略配線を包含する図形形状を得ることができる。
【０２３１】
＜格子の領域変換処理＞
つぎに、格子の領域変換処理について説明する。格子の領域変換処理とは、格子群の和集合をとることにより領域変換をおこなって、最終的な図形形状を求める処理である。したがって、引数を格子配列Ｇｐ［］とし、図形形状Ｓｐを返り値とする。格子の領域変換処理は、ステップＳ４６０６、Ｓ４８１５、Ｓ４９１３で用いられる。
【０２３２】
図５２は、格子の領域変換処理の詳細な処理手順を示すフローチャートである。まず、図形形状Ｓｐ＝Φ（空集合）とし（ステップＳ５２０１）、格子配列Ｇｐ［］＝Φ（空集合）であるか否かを判断する（ステップＳ５２０２）。Ｇｐ［］＝Φでない場合（ステップＳ５２０２：Ｎｏ）、格子配列Ｇｐ［］から格子を１つ取り出して、格子Ｇ１とする（ステップＳ５２０３）。
【０２３３】
そして、取り出された格子Ｇ１の範囲Ａｘ１，Ａｙ１，Ａｘ２，Ａｙ２でできる矩形形状を図形形状Ｓｒとする（ステップＳ５２０４）。そして、図形形状Ｓｐと図形形状Ｓｒとの図形形状の和集合をあらたな図形形状Ｓｐの和集合とする（ステップＳ５２０５）。そして、ステップＳ５２０２に戻る。ステップＳ５２０２において、Ｇｐ［］＝Φである場合（ステップＳ５２０２：Ｙｅｓ）、格子の領域変換処理を終了する。
【０２３４】
図５３は、格子の領域変換処理の具体例を示す説明図である。１）では、ステップＳ５２０３で格子Ｇ１が取り出される都度、格子の反時計回りの多角形形状を求め、図形形状Ｓｒとする。２）では、ステップＳ５２０５において、和集合をとる場合、隣接する場合は、向きが逆となる辺を削除して図形形状Ｓｐとする。また、図形形状Ｓｐと図形形状Ｓｒとが離れていても、１つの図形形状Ｓｐとして和集合をとる。また、図形形状Ｓｐの生成過程で、時計回りの図形が生成された場合は打ち抜きとする。
【０２３５】
＜線長調整領域の概略決定処理＞
つぎに、線長調整領域の概略決定処理について説明する。本実施の形態では、線長調整領域について、概略決定、詳細決定、マッピングという手順を踏む。
【０２３６】
図５４〜図５６は、線長調整領域の概略決定処理（ステップＳ３３０４）の詳細な処理手順を示すフローチャートである。線長調整領域の概略決定処理（ステップＳ３３０４）では、格子管理テーブルＧａおよび配線グループＲｇを引数とし、座標配列Ｃｏ［］、面積Ｒｓ１，Ｒｓ２、図形形状Ｒｂ１，Ｒｂ２を返り値として返す。
【０２３７】
まず、図５４において、配線グループＲｇに関連付けられた図形形状を図形形状Ｒａとする（ステップＳ５４０１）。つぎに、図４２に示したパターン占有率計算処理を実行する（ステップＳ５４０２）。
【０２３８】
パターン占有率計算処理（ステップＳ５４０２）では、格子管理テーブルＧ＝Ｇａ、図形形状Ｓ＝Ｒａ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ５４０２）では、引数として渡された図形形状Ｒａと重なる格子群となる格子配列Ｇｐ［］を返す。
【０２３９】
また、表示例３を実現するため、配線グループＲｇに対するユーザの指示領域を図形形状Ｒｚとする（ステップＳ５４０３）。Ｒｚ＝Φ（空集合）である場合（ステップＳ５４０４：Ｙｅｓ）、ユーザからの領域指示がないこととなり、ステップＳ５４０６に移行する。一方、Ｒｚ＝Φでない場合（ステップＳ５４０４：Ｎｏ）、図形形状Ｒａとユーザの指示領域Ｒｚとの図形形状の積集合をとり、図形形状Ｒａとする（ステップＳ５４０５）。
【０２４０】
図５７は、図形形状Ｒａとユーザの指示領域Ｒｚとの図形形状の積集合結果を示す説明図である。つぎに、配線グループＲｇに定義されている配線パスの中で最長線長の配線パスを配線パスＲｐとし（ステップＳ５４０６）、配線パスＲｐの線長を線長Ｒｘとする（ステップＳ５４０７）。
【０２４１】
そして、配線パスＲｐの線長Ｒｘを基準としたときの配線グループＲｇの各配線パスの不足線長を線長Ｒｙ［］とする（ステップＳ５４０８）。線長Ｒｙ［］の要素は、配線グループＲｇのうち配線パスＲｐ以外の残余の配線パスの不足線長となる。
【０２４２】
そして、線長Ｒｙ［］内の要素の値が比例関係にあるか否かを判断する（ステップＳ５４０９）。比例関係である場合（ステップＳ５４０９：Ｙｅｓ）、図５５のステップＳ５５０１に移行する。一方、比例関係でない場合（ステップＳ５４０９：Ｎｏ）、線長Ｒｙ［］の配線パスの並びで中心の配線パスを配線パスＲｐとする（ステップＳ５４１０）。
【０２４３】
ここで、比例関係の判断について具体的に説明する。配線グループＲｇのうち最小線長となる配線パスＲｐ以外の残余の配線パスの不足線長が比例関係にあるか否かにより、線長調整領域をどこに配置させるかが異なってくる。
【０２４４】
図５８は、不足線長の比例関係に基づく線長調整領域の概略位置決定を示す説明図である。図５８の（Ａ）では、例として、ドライバ１０１とレシーバ１０２との間にバスＢ１とバスＢ２が形成されているものとする。なお、バスＢ１、Ｂ２の右端の矢印は、バスＢ１，Ｂ２内の配線パスの並びを示している。
【０２４５】
また、（Ｂ）は、バスＢ１，Ｂ２ごとの最長線長の配線パスＲｐ以外の残余の配線パスの並び順における不足線長を示すグラフである。（Ｂ）を参照すると、バスＢ１の不足線長はほぼ均等であるのに対し、バスＢ２の不足線長は比例関係にある。したがって、バスＢ１については、どの配線パスも線長調整対象となりうるため、バスＢ１の両側に線長調整領域を設けるのが好ましい。一方、バスＢ２については、配線パスが上に行くほど不足線長が長くなるため、上側の配線パスが線長調整対象になりやすい。したがって、バスＢ２の上側に線長調整領域を設けるのが好ましい。
【０２４６】
また、比例関係にあるか否かは、相関係数を求めて判断することとしてもよい。ここで、変数ｘ，ｙの相関係数ｒは、以下の式で求められる。
【０２４７】
ｒ＝（ｘとｙの共分散）／｛（ｘの標準偏差）×（ｙの標準偏差）｝
【０２４８】
図５９は、相関関係を示すグラフである。相関係数ｒは、正の相関があるとき、０＜ｒ≦１．０、相関がまったくないとき、ｒ＝０、負の相関があるとき、−１．０≦ｒ＜０の値をとる。
【０２４９】
図６０は、図５８で示したバスＢ１，Ｂ２での不足線長および相関係数を示す説明図である。（Ａ）はバスＢ１、（Ｂ）はバスＢ２を示している。この場合、具体的には、相関係数ｒのしきい値ｒ＿ｔ（０＜ｒ＿ｔ＜１．０）を設定しておき、−ｒ＿ｔ＜ｒ＜ｒ＿ｔの場合は、比例関係ではなく、ｒ≦−ｒ＿ｔまたはｒ≧ｒ＿ｔの場合は、比例関係があると判断する。
【０２５０】
また、図５５に戻り、ステップＳ５４０２で得られた格子配列Ｇｐ［］における配線パスＲｐの経路に対する格子の並びを格子配列Ｇｐ１［］とし（ステップＳ５５０１）、格子配列Ｇｐ［］と格子配列Ｇｐ１［］との積集合をとる（ステップＳ５５０２）。ここで、格子配列Ｇｐ［］は、図形形状Ｒａ内に含まれている格子群である。
【０２５１】
そして、積集合が取られた格子配列Ｇｐ１［］がＧｐ１［］＝Φ（空集合）であるか否かを判断する（ステップＳ５５０３）。Ｇｐ１＝Φである場合（ステップＳ５５０３：Ｙｅｓ）、エラー出力して（ステップＳ５５０４）、一連の処理を終了する。一方、Ｇｐ１＝Φでない場合（ステップＳ５５０３：Ｎｏ）、格子配列Ｇｐ１［］の各格子の中心座標からなる配列を、座標配列Ｃｏ［］とする（ステップＳ５５０５）。
【０２５２】
図６１は、ステップＳ５５０５で得られた座標配列Ｃｏ［］を示す説明図である。なお、ハッチングを施した格子配列Ｇｐ１［］は、ステップＳ５５０２で得られた積集合結果である。
【０２５３】
また、図５５に戻って、座標配列Ｃｏ［］の並びの経路の始点および終点を図形形状Ｒａの境界まで最短経路で伸ばし（ステップＳ５５０６、Ｓ５５０７）、図形形状Ｒａを座標配列Ｃｏ［］を境界にして２つに分割する（ステップＳ５５０８）。そして、配線パスＲｐを基準にして、配線グループＲｇの配線パスを２つのグループＲｇ１，Ｒｇ２に分割する（ステップＳ５５０９）。そして、図５６のステップＳ５６０１に移行する。
【０２５４】
図６２は、ステップＳ５５０６〜Ｓ５５０９における分割例を示す説明図である。図形形状Ｒａは、座標配列Ｃｏ［］を境界にして、図形形状Ｒａ１，Ｒａ２に分割される。同様に、配線パスｐ１〜ｐ４を含む配線グループＲｇは、図形形状Ｒａ１内の配線パスｐ２〜ｐ４を含む配線グループＲｇ１と配線グループＲｇ２とに分割される。配線グループＲｐ２には配線パスがない。なお、配線パスｐ１は配線パスＲｐとなるため、どのグループにも属さない。
【０２５５】
また、図５６において、線長Ｒｘを基準としたときの配線グループＲｇ１の各配線パスの不足線長の総和を求めて線長Ｒｘ１とする（ステップＳ５６０１）。つぎに、線長調整換算処理を実行する（ステップＳ５６０２）。線長調整換算処理の詳細は後述するが、線長調整換算処理（ステップＳ５６０２）は、線長Ｒｘ１を引数とし、面積Ｒｓ１を返り値として返す関数である。そして、概略領域割当処理を実行する（ステップＳ５６０３）。概略領域割当処理の詳細は後述するが、概略領域割当処理（ステップＳ５６０３）は、格子管理テーブルＧａ、図形形状Ｒａ１、座標配列Ｃｏ［］、面積Ｒｓ１を引数とし、図形形状Ｒｂ１を返り値として返す関数である。
【０２５６】
同様に、線長Ｒｘを基準としたときの配線グループＲｇ２の各配線パスの不足線長の総和を求めて線長Ｒｘ２とする（ステップＳ５６０４）。つぎに、線長調整換算処理を実行する（ステップＳ５６０５）。線長調整換算処理の詳細は後述するが、線長調整換算処理（ステップＳ５６０５）は、線長Ｒｘ２を引数とし、面積Ｒｓ２を返り値として返す関数である。そして、概略領域割当処理を実行する（ステップＳ５６０６）。概略領域割当処理の詳細は後述するが、概略領域割当処理（ステップＳ５６０６）は、格子管理テーブルＧａ、図形形状Ｒａ２、座標配列Ｃｏ［］、面積Ｒｓ２を引数とし、図形形状Ｒｂ２を返り値として返す関数である。
【０２５７】
このあと、座標配列Ｃｏ［］、面積Ｒｓ１，Ｒｓ２、図形形状Ｒｂ１，Ｒｂ２を、配線グループＲｇと関連付けて記憶装置に記憶する（ステップＳ５６０７）。具体的には、概略領域テーブル２４００に新規レコードを２つ追加し、両レコードの分割線に、座標配列Ｃｏ［］を設定する。また、一方のレコードの概略形状情報に図形形状Ｒｂ１を設定し、他方のレコードの概略形状情報に図形形状Ｒｂ２を設定する。そして、両レコードの概略領域番号を、配線グループＲｇに対応する線長調整テーブル２３００のレコードの概略領域番号リストに追加する。
【０２５８】
また、線長領域テーブル２５００に新規レコードを２つ追加し、両レコードの配線パス番号リストに、配線グループＲｇを構成する配線パス番号を設定する。また、一方のレコードの不足面積に面積Ｒｓ１を設定し、他方のレコードの不足面積に面積Ｒｓ２を設定する。さらに、一方のレコードの概略形状情報に図形形状Ｒｂ１を設定し、他方のレコードの概略形状情報に図形形状Ｒｂ２を設定する。なお、現時点では、両レコードの詳細形状情報および詳細面積は空（未定義）である。これにより、線長調整領域の概略決定処理を終了する。
【０２５９】
図６３は、概略領域割当後の格子管理テーブルＧａを示す説明図である。図形形状Ｒａ１については、概略領域割当処理（ステップＳ５６０３）により、概略領域となる図形形状Ｒｂ１が割当てられる。一方、図形形状Ｒａ２については、配線グループＲｇ２＝Φ（空集合）、すなわち、図形形状Ｒａ２内に配線パスが存在しないため、図形形状Ｒｂ２＝Φ（空集合）となる。
【０２６０】
＜線長調整換算処理＞
つぎに、線長調整換算処理について説明する。線長調整換算処理は、ステップＳ５６０２，Ｓ５６０５で用いられる。線長調整換算処理では、線長Ｒｘ１（またはＲｘ２）を引数とし、換算面積Ｒｓ（Ｒｘ１の場合はＲｓ＝Ｒｓ１、Ｒｘ２の場合はＲｓ＝Ｒｓ２）を返り値として返す。以下、線長Ｒｘ１を例に挙げて説明する。
【０２６１】
図６４は、線長調整換算処理（ステップＳ５６０２，Ｓ５６０５）の詳細な処理手順を示すフローチャートである。まず、設計基準テーブル１３００を参照して、線長調整の迂回経路の間隔を読み出し、線長調整幅Ｗｉｄｔｈとする（ステップＳ６４０１）。そして、下記式により、換算面積Ｒｓ（＝Ｒｓ１）を算出する（ステップＳ６４０２）。
【０２６２】
換算面積Ｒｓ＝１．０３×Ｗｉｄｔｈ×Ｒｘ１
【０２６３】
なお、「１．０３」は、面積をやや大きめに採るための係数である。線長調整幅Ｗｉｄｔｈは格子間隔（定数）となる。
【０２６４】
＜概略領域割当処理＞
つぎに、概略領域割当処理について説明する。概略領域割当処理は、ステップＳ５６０３，Ｓ５６０６で用いられる。概略領域割当処理では、格子管理テーブルＧａ、図形形状Ｒａ（Ｒａ１またはＲａ２）、座標配列Ｃｏ［］、面積Ｒｓ（Ｒｓ１またはＲｓ２）を引数として、図形形状Ｒｂ１（またはＲｂ２）を返り値として返す関数である。なお、ステップＳ５６０３では、線長調整換算処理（ステップＳ５６０２）で得られた図形形状Ｒａ１および面積Ｒｓ１を引数Ｒａ，Ｒｓとし、ステップＳ５６０６では、線長調整換算処理（ステップＳ５６０５）で得られた図形形状Ｒａ２および面積Ｒｓ２を引数Ｒａ，Ｒｓとする。
【０２６５】
図６５〜図７０は、概略領域割当処理（ステップＳ５６０３，Ｓ５６０６）の詳細な処理手順を示すフローチャートである。まず、図６５において、図形形状Ｒａの頂点座標において座標配列Ｃｏ［］の座標配列が含まれない区間の座標配列を座標配列Ｃｐ［］とする（ステップＳ６５０１）。
【０２６６】
つぎに、座標配列Ｃｐ［］の１番目の座標から座標配列Ｃｐ［］の最後の座標までの座標配列を座標配列Ｃｐ１［］とし、座標配列Ｃｐ１［］をつなげた最短経路２をもとめる（ステップＳ６５０２）。
【０２６７】
そして、座標配列Ｃｏ［］と座標配列Ｃｐ１［］とで囲まれる図形形状を図形形状Ｓとし（ステップＳ６５０３）、図４２に示したパターン占有率計算処理を実行する（ステップＳ６５０４）。
【０２６８】
パターン占有率計算処理（ステップＳ６５０４）では、格子管理テーブルＧ＝Ｇａ、図形形状Ｓ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ６５０４）では、引数として渡された図形形状Ｓと重なる格子群となる格子配列Ｇｐ１［］を返す。
【０２６９】
このあと、格子配列の迂回領域取得処理を実行する（ステップＳ６５０５）。格子配列の迂回領域取得処理の詳細は後述するが、格子配列Ｇｐ１［］を引数とし、格子配列Ｇｐ１［］を返り値として返す。
【０２７０】
つぎに、格子配列の面積計算処理を実行する（ステップＳ６５０６）。格子配列の面積計算処理の詳細は後述するが、格子配列Ｇｐ１［］を引数とし、面積Ｒｓ１を返り値として返す。
【０２７１】
そして、Ｒｓ１≧Ｒｓであるか否かを判断する（ステップＳ６５０７）。Ｒｓ１≧Ｒｓでない場合（ステップＳ６５０７：Ｎｏ）、図６６のステップＳ６６０１に移行する。一方、Ｒｓ１≧Ｒｓである場合（ステップＳ６５０７：Ｙｅｓ）、図６８のステップＳ６８０１に移行する。
【０２７２】
図７１は、概略領域割当処理の具体例１を示す説明図である。図７１において、（Ａ）は最短経路２を求める前の格子管理テーブルＧａを示している。最短経路２を求める条件は以下のとおりである。
１）始点から終点までの最短経路
２）ただし、１）において、経路は図形内部を通過しない（境界線上は可）
３）ただし、１）において、同じ長さの経路が複数見つかる場合は図形の境界線上と一致する区間の総長が最大となる経路を選択する
【０２７３】
（Ｂ）では、最短経路２となる座標配列Ｃｐ１［］と座標配列Ｃｏ［］とで囲まれた領域を図形形状Ｓとし、格子配列の迂回領域取得処理（ステップＳ６５０５）により、格子配列ＧＰ１［］を取得することとなる。
【０２７４】
つぎに、図６５のステップＳ６５０７において、Ｒｓ１≧Ｒｓでない場合（ステップＳ６５０７：Ｎｏ）について説明する。
【０２７５】
図６６において、座標配列Ｃｐ［］の１番目の座標から座標配列Ｃｐ［］の最後の座標までの座標配列を座標配列Ｃｐ２［］とし、座標配列Ｃｐ２［］をつなげた最短経路３をもとめる（ステップＳ６６０１）。
【０２７６】
そして、座標配列Ｃｏ［］と座標配列Ｃｐ２［］とで囲まれる図形形状を図形形状Ｓとし（ステップＳ６６０２）、図４２に示したパターン占有率計算処理を実行する（ステップＳ６６０３）。
【０２７７】
パターン占有率計算処理（ステップＳ６６０３）では、格子管理テーブルＧ＝Ｇａ、図形形状Ｓ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ６６０３）では、引数として渡された図形形状Ｓと重なる格子群となる格子配列Ｇｐ２［］を返す。
【０２７８】
このあと、格子配列の迂回領域取得処理を実行する（ステップＳ６６０４）。格子配列の迂回領域取得処理の詳細は後述するが、格子配列Ｇｐ２［］を引数とし、格子配列Ｇｐ２［］を返り値として返す。
【０２７９】
つぎに、格子配列の面積計算処理を実行する（ステップＳ６６０５）。格子配列の面積計算処理の詳細は後述するが、格子配列Ｇｐ２［］を引数とし、面積Ｒｓ１を返り値として返す。
【０２８０】
そして、Ｒｓ１≧Ｒｓであるか否かを判断する（ステップＳ６６０６）。Ｒｓ１≧Ｒｓでない場合（ステップＳ６６０６：Ｎｏ）、図６７のステップＳ６７０１に移行する。一方、Ｒｓ１≧Ｒｓである場合（ステップＳ６６０６：Ｙｅｓ）、図６８のステップＳ６８０１に移行する。
【０２８１】
図７２は、概略領域割当処理の具体例２を示す説明図である。図７２において、（Ａ）は最短経路３を求める前の格子管理テーブルＧａを示している。最短経路３を求める条件は以下のとおりである。
１）始点から終点までの最短経路
２）ただし、１）において、経路は図形内部を通過しない（境界線上は可）
３）ただし、１）において、同じ長さの経路が複数見つかる場合は図形から最も離れたところを通過する経路を選択する
【０２８２】
（Ｂ）では、最短経路３となる座標配列Ｃｐ２［］と座標配列Ｃｏ［］とで囲まれた領域を図形形状Ｓとし、格子配列の迂回領域取得処理（ステップＳ６６０４）により、格子配列Ｇｐ２［］を取得することとなる。
【０２８３】
つぎに、図６６のステップＳ６６０６において、Ｒｓ１≧Ｒｓでない場合（ステップＳ６６０６：Ｎｏ）について説明する。
【０２８４】
図６７において、ステップＳ６６０２で得られた図形形状Ｓと図形形状Ｒａとの和集合をあらたに図形形状Ｓとする（ステップＳ６７０１）。つぎに、概略格子用の１格子当たりのサイズを単位サイズＵａとし（ステップＳ６７０２）、格子配列Ｇｐ３［］＝Φ（空集合）とする（ステップＳ６７０３）。
【０２８５】
また、図形形状Ｓ１＝Φ（空集合）とし（ステップＳ６７０４）、図形形状Ｓ１に図形形状Ｓを与える（ステップＳ６７０５）。そして、図形形状Ｓを座標配列Ｃｏ［］の区間を除いて単位サイズＵａだけ拡大する（ステップＳ６７０６）。
【０２８６】
つぎに、図形形状Ｓと図形形状Ｇ．Ｇｒとの図形形状の積集合をとる（ステップＳ６７０７）。そして、図４２に示したパターン占有率計算処理を実行する（ステップＳ６７０８）。
【０２８７】
パターン占有率計算処理（ステップＳ６７０８）では、格子管理テーブルＧ＝Ｇａ、図形形状Ｓ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ６７０８）では、引数として渡された図形形状Ｓと重なる格子群となる格子配列Ｇｐ３［］を返す。
【０２８８】
このあと、格子配列の迂回領域取得処理を実行する（ステップＳ６７０９）。格子配列の迂回領域取得処理の詳細は後述するが、格子配列Ｇｐ３［］を引数とし、格子配列Ｇｐ３［］を返り値として返す。
【０２８９】
つぎに、格子配列の面積計算処理を実行する（ステップＳ６７１０）。格子配列の面積計算処理の詳細は後述するが、格子配列Ｇｐ３［］を引数とし、面積Ｒｓ１を返り値として返す。
【０２９０】
そして、Ｒｓ１≧Ｒｓであるか否かを判断する（ステップＳ６７１１）。Ｒｓ１≧Ｒｓである場合（ステップＳ６７１１：Ｙｅｓ）、図６８のステップＳ６８０１に移行する。一方、Ｒｓ１≧Ｒｓでない場合（ステップＳ６７１１：Ｎｏ）、図形形状Ｓの面積が図形形状Ｓ１の面積よりも大きいか否かを判断する（ステップＳ６７１２）。図形形状Ｓの面積が図形形状Ｓ１の面積よりも大きい場合（ステップＳ６７１２：Ｙｅｓ）、ステップＳ６７０５に戻る、一方、大きくない場合（ステップＳ６７１２：Ｎｏ）、図６８のステップＳ６８０１に移行する。
【０２９１】
図７３は、概略領域割当処理の具体例３を示す説明図である。図７３では、ステップＳ６７０６の拡大例を示している。具体的には、座標配列Ｃｏ［］を除いた図形形状Ｓを単位サイズＵａずつ拡大している。
【０２９２】
つぎに、Ｒｓ１≧Ｒｓである場合（ステップＳ６５０７：Ｙｅｓ）、（ステップＳ６６０６：Ｙｅｓ）、（ステップＳ６７１１：Ｙｅｓ）について説明する。
【０２９３】
図６８において、格子配列Ｇｐ３［］のすべての格子の優先度ＡｐをＡｐ＝１とし（ステップＳ６８０１）、格子配列Ｇｐ２［］のすべての格子の優先度ＡｐをＡｐ＝１０とし（ステップＳ６８０２）、格子配列Ｇｐ１［］のすべての格子の優先度ＡｐをＡｐ＝１０１とする（ステップＳ６８０３）。優先度Ａｐの値が大きいほど優先順位が高いこととする。そして、単位サイズＧ．Ｇｕ×４を単位サイズＵｂとし（ステップＳ６８０４）、図３５に示した格子管理テーブル作成処理を実行する（ステップＳ６８０５）。
【０２９４】
格子管理テーブル作成処理（ステップＳ６８０５）では、図形形状Ｓ＝Ｇ．Ｇｒ、単位サイズＵ＝Ｕｂを引数に設定して、図３５に示した処理手順にしたがって実行する。これにより、格子管理テーブル作成処理（ステップＳ６８０５）では、格子管理テーブルＧｂを返り値として返す。
【０２９５】
図７４は、格子管理テーブルＧｂを示す説明図である。格子管理テーブルＧｂは、単位サイズＵｂとしたことにより、格子管理テーブルＧａよりも格子を粗くしたテーブルである。図７４では、格子管理テーブルＧａが格子数が縦８個、横１６個のテーブルであるのに対し、格子管理テーブルＧｂは、縦２個、横４個のテーブルである。また、格子管理テーブルＧｂの８個の格子には優先度Ａｐ（の総和）が図６９に示す処理により計算される。
【０２９６】
図６９において、ループ変数Ｉ１をＩ１＝１とし（ステップＳ６９０１）、Ｉ１＞Ｇｂ．Ｇｘであるか否かを判断する（ステップＳ６９０２）。Ｇｂ．ＧｘはＸ軸方向の格子管理テーブルＧｂの格子数である。図７４では、Ｇｂ．Ｇｘ＝４である。
【０２９７】
Ｉ１＞Ｇｂ．Ｇｘでない場合（ステップＳ６９０２：Ｎｏ）、ループ変数Ｉ２をＩ２＝１とし（ステップＳ６９０３）、Ｉ２＞Ｇｂ．Ｇｙであるか否かを判断する（ステップＳ６９０４）。図７４では、Ｇｂ．Ｇｙ＝２である。
【０２９８】
Ｉ２＞Ｇｂ．Ｇｙでない場合（ステップＳ６９０４：Ｎｏ）、格子配列要素Ｇｂ．Ｇａ［Ｉ１，Ｉ２］の矩形形状を図形形状Ｓｒとする（ステップＳ６９０５）。そして、図４２に示したパターン占有率計算処理を実行する（ステップＳ６９０６）。
【０２９９】
パターン占有率計算処理（ステップＳ６９０６）では、格子管理テーブルＧ＝Ｇｂ、図形形状Ｓｒ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ６９０６）では、引数として渡された図形形状Ｓｒと重なる格子群となる格子配列Ｇｐ［］を返す。
【０３００】
そして、格子配列Ｇｐ［］のすべての格子（図７４では、格子管理テーブルＧａでの格子）の優先度Ａｐの総和を、格子配列要素Ｇｂ．Ｇａ［Ｉ１，Ｉ２］の優先度Ｇｂ．Ｇａ［Ｉ１，Ｉ２］．Ａｐとする（ステップＳ６９０７）。このあと、Ｉ２をインクリメントして（ステップＳ６９０８）、ステップＳ６９０４に戻る。一方、ステップＳ６９０４において、Ｉ２＞Ｇｂ．Ｇｙである場合（ステップＳ６９０４：Ｙｅｓ）、Ｉ１をインクリメントして（ステップＳ６９０９）、ステップＳ６９０２に戻る。一方、ステップＳ６９０２において、Ｉ１＞Ｇｂ．Ｇｘである場合（ステップＳ６９０２：Ｙｅｓ）、図７０のステップＳ７００１に移行する。
【０３０１】
また、図７０において、図形形状ＳをＳ＝Φ（空集合）とし（ステップＳ７００１）、格子配列Ｇｐ［］をＧｐ［］＝Φ（空集合）とする（ステップＳ７００２）。つぎに、格子配列Ｇｂ．Ｇａ［］の格子の中で優先度Ａｐが最大の格子を探索して、格子Ｇ１とする（ステップＳ７００３）。最大の優先度Ａｐである格子が複数ある（同値の格子が複数ある）場合、領域が連続するようにするため、前後左右の格子で選択済みの個数が多い方を選択する。また、選択できない場合は、前後左右の格子で選択済みの優先度Ａｐの総和が最小（選択済の格子はステップＳ７００５で負値にしているため）となる格子を選択する。
【０３０２】
そして、探索により選択された格子Ｇ１の優先度Ｇ１．ＡｐがＧ１．Ａｐ≦０であるか否かを判断する（ステップＳ７００４）。Ｇ１．Ａｐ≦０である場合（ステップＳ７００４：Ｙｅｓ）、概略領域割当処理を終了する。
【０３０３】
一方、Ｇ１．Ａｐ≦０でない場合（ステップＳ７００４：Ｎｏ）、優先度Ｇ１．Ａｐを負の値にする（ステップＳ７００５）。そして、格子Ｇ１の矩形形状を図形形状Ｓｒとし（ステップＳ７００６）、図４２に示したパターン占有率計算処理を実行する（ステップＳ７００７）。
【０３０４】
パターン占有率計算処理（ステップＳ７００７）では、格子管理テーブルＧ＝Ｇｂ、図形形状Ｓｒ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ７００７）では、引数として渡された図形形状Ｓｒと重なる格子群となる格子配列Ｇｐ１［］を返す。
【０３０５】
このあと、ループ変数Ｉ１をＩ１＝１とし（ステップＳ７００８）、Ｉ１が格子配列Ｇｐ１［］の格子の個数を超えたか否かを判断する（ステップＳ７００９）。超えていない場合（ステップＳ７００９：Ｎｏ）、格子配列Ｇｐ１［］のＩ１番目の要素を格子Ｇ２とし（ステップＳ７０１０）、格子Ｇ２の優先度Ｇ２．ＡｐがＧ２．Ａｐ＝０であるか否かを判断する（ステップＳ７０１１）。
【０３０６】
Ｇ２．Ａｐ＝０である場合（ステップＳ７０１１：Ｙｅｓ）、ステップＳ７０１３に移行する。一方、Ｇ２．Ａｐ＝０でない場合（ステップＳ７０１１：Ｎｏ）、格子配列Ｇｐ［］と格子Ｇ２との和集合をあらたな格子配列Ｇｐ［］とし（ステップＳ７０１２）、ステップＳ７０１３に移行する。ステップＳ７０１３では、Ｉ１をインクリメントし（ステップＳ７０１３）、ステップＳ７００９に戻る。
【０３０７】
一方、ステップＳ７００９において、Ｉ１が格子配列Ｇｐ１［］の格子の個数を超えた場合（ステップＳ７００９：Ｙｅｓ）、図５２に示した格子の領域変換処理を実行する（ステップＳ７０１４）。格子の領域変換処理（ステップＳ７０１４）では、ステップＳ７０１２で得られた最終的な格子配列Ｇｐ［］を引数とし、図形形状Ｓを返り値として返す。
【０３０８】
図７５は、格子の領域変換処理（ステップＳ７０１４）の処理結果例を示す説明図である。図７５の格子管理テーブルＧｂにおいて、ハッチングが施されている単位サイズＧ．Ｇｕの格子群、ステップＳ７００９〜Ｓ７０１３で得られるＧｐ［］であり、その格子群からなる図形が図形形状Ｓである。
【０３０９】
そして、格子配列の面積計算処理を実行する（ステップＳ７０１５）。格子配列の面積計算処理（ステップＳ７０１５）については後述するが、格子配列Ｇｐ［］を引数として面積Ｒｓ２を返り値として返す。
【０３１０】
このあと、算出された面積Ｒｓ２がＲｓ２＜Ｒｓ１（Ｒｓ１はＳ６７１０で得られた面積）であるか否かを判断する（ステップＳ７０１６）。Ｒｓ２＜Ｒｓ１である場合（ステップＳ７０１６：Ｙｅｓ）、ステップＳ７００３に戻る。一方、Ｒｓ２＜Ｒｓ１でない場合（ステップＳ７０１６：Ｎｏ）、概略領域割当処理を終了する。
【０３１１】
＜格子配列の迂回領域取得処理＞
つぎに、格子配列の迂回領域取得処理について説明する。格子配列の迂回領域取得処理は、図６５のステップＳ６５０５、図６６のステップＳ６６０４、図６７のステップＳ６７０９で用いられる。格子配列の迂回領域取得処理では、格子配列Ｇｐ［］を引数とし、配線パスと接している空き領域の格子配列Ｇｐ１［］を返り値として返す関数である。
【０３１２】
図７６は、格子配列の迂回領域取得処理の具体例を示す説明図である。（Ａ）の格子管理テーブルＧａにおいて、障害物占有フラグＡｆ１＝１の格子と配線パス占有フラグＡｆ２＝１の格子とが設定されている。この状態で、太枠で囲まれた格子配列Ｇｐ［］が渡されたとする。（Ｂ）において、格子配列Ｇｐ［］の領域中、配線パスと接している空き領域（迂回領域）を格子配列Ｇｐ１［］として返す。
【０３１３】
図７７および図７８は、格子配列の迂回領域取得処理の詳細な処理手順を示すフローチャートである。まず、図７７において、格子配列Ｇｐ１［］をＧｐ１［］＝Φ（空集合）にし（ステップＳ７７０１）、格子配列Ｇｐ［］の格子数をＩ１にする（ステップＳ７７０２）。つぎに、格子配列Ｇｐ［］をＧｐ２［］＝Φ（空集合）とし（ステップＳ７７０３）、ループ変数Ｉ２をＩ２＝１にする（ステップＳ７７０４）。
【０３１４】
そして、Ｉ２＞Ｉ１であるか否かを判断する（ステップＳ７７０５）。Ｉ２＞Ｉ１でない場合（ステップＳ７７０５：Ｎｏ）、格子配列Ｇｐ［］のＩ２番目の格子を格子Ｇ２とし（ステップＳ７７０６）、格子Ｇ２の配線パス占有フラグＡｆ２がＡｆ２＝１であるか否かを判断する（ステップＳ７７０７）。
【０３１５】
Ａｆ２＝１でない場合（ステップＳ７７０７：Ｎｏ）、格子Ｇ２の周囲の格子の配線パス占有フラグＡｆ２がＡｆ２＝１であるか否かを判断する（ステップＳ７７０８）。Ａｆ２＝１でない場合（ステップＳ７７０８：Ｎｏ）、Ｉ２をインクリメントし（ステップＳ７７０９）、ステップＳ７７０５に戻る。
【０３１６】
一方、ステップＳ７７０７またはＳ７７０８において配線パス占有フラグＡｆ２＝１である場合（ステップＳ７７０７／Ｓ７７０８：Ｙｅｓ）、格子配列Ｇｐ２［］と格子Ｇ２との和集合をあらたに格子配列Ｇｐ２［］とし（ステップＳ７７１０）、図７８のステップＳ７８０１に移行する。また、ステップＳ７７０５において、Ｉ２＞Ｉ１である場合（ステップＳ７７０５：Ｙｅｓ）、図７８のステップＳ７８０１に移行する。
【０３１７】
つぎに、図７８において、Ｇｐ２［］＝Φ（空集合）であるか否かを判断する（ステップＳ７８０１）。Ｇｐ２［］＝Φである場合（ステップＳ７８０１：Ｙｅｓ）、ステップＳ７８０５に移行する。
【０３１８】
一方、Ｇｐ２［］＝Φでない場合（ステップＳ７８０１：Ｎｏ）、格子配列Ｇｐ２［］の要素を起点に格子配列Ｇｐ［］における塗りつぶし可能な格子を格子配列Ｇｐ２［］にする（ステップＳ７８０２）。塗りつぶし可能な格子の判断は、配線パターンを横切ることができるだけの空きがあるか否かで判断する。具体的には、以下の条件を満足しているかどうかで判断する。
１）障害物占有フラグＡｆ１が１である場合は、配線パターン占有率が所定値（＞０）以下である）こと。
２）配線パス占有フラグＡｆ２が１である場合は、対象の格子の前後左右にある格子のうち任意の１つと、対象の格子とで、それらの配線パターン占有率を足し合わせたときの和が所定値（＞０）以下であること。
つぎに、格子配列Ｇｐ１［］と格子配列Ｇｐ２［］の和集合をあらたに格子配列Ｇｐ１［］にする（ステップＳ７８０３）。そして、格子配列Ｇｐ［］から格子配列Ｇｐ２［］を削除してあらたに格子配列Ｇｐ［］にする（ステップＳ７８０４）。
【０３１９】
このあと、Ｉ１が格子配列Ｇｐ［］の格子数を超えたか否かを判断する（ステップＳ７８０５）。超えている場合（ステップＳ７８０５：Ｙｅｓ）、図７７のステップＳ７７０２に戻る。一方、超えていない場合（ステップＳ７８０５：Ｎｏ）、格子配列の迂回領域取得処理を終了する。
【０３２０】
＜格子配列の面積計算処理＞
つぎに、格子配列の面積計算処理について説明する。格子配列の面積計算処理は、図６７のステップＳ６７１０および図７０のステップＳ７０１５で用いられる。格子配列の面積計算処理は、引数として与えられた格子配列Ｇｐ［］の面積を計算して、面積Ｒｓとして返す関数である。
【０３２１】
図７９は、格子配列の面積計算処理の具体例を示す説明図である。図７９では、例として格子［１，１］〜［３，３］の格子配列Ｇｐ［］を用いる。格子配列の面積計算処理は、格子配列Ｇｐ［］の各格子［１，１］〜［３，３］の面積の総和から、その格子の中に含まれる障害物や配線パスの占めている面積を差し引いた、空いているスペースの面積を求めることと等しい。
【０３２２】
たとえば、関数引数となる格子配列Ｇｐ［］＝｛［１，２］，［２，２］，［３，２］｝において、格子［１，２］，［２，２］，［３，２］から、配線パス（または障害物）７９００の面積だけ差し引いた面積が、面積Ｒｓとなる。
【０３２３】
図８０は、格子配列の面積計算処理の詳細な処理手順を示すフローチャートである。まず、格子配列Ｇｐ［］の面積ＲｓをＲｓ＝０とし（ステップＳ８００１）、格子配列Ｇｐ［］＝Φ（空集合）であるか否かを判断する（ステップＳ８００２）。Ｇｐ［］＝Φでない場合（ステップＳ８００２：Ｎｏ）、格子配列Ｇｐ［］から取り出された格子を格子Ｇ１とし（ステップＳ８００３）、格子Ｇ１の矩形形状を図形形状Ｓｒとする（ステップＳ８００４）。
【０３２４】
そして、図形形状Ｓｒの面積を面積Ｒｓ１とし（ステップＳ８００５）、面積Ｒｓ１に格子Ｇ１のパターン占有率Ｇ１．Ａｒを乗じた値を面積Ｒｓに加算して更新する（ステップＳ８００６）。そして、ステップＳ８００２に戻る。ステップＳ８００２において、Ｇｐ［］＝Φである場合（ステップＳ８００２：Ｙｅｓ）、格子配列の面積計算処理を終了する。
【０３２５】
＜線長調整領域の詳細決定処理＞
つぎに、線長調整領域の詳細決定処理について説明する。線長調整領域の詳細決定処理は、図３３のステップＳ３３０５において実行される。線長調整領域の詳細決定処理（ステップＳ３３０５）は、格子管理テーブルＧａおよび配線グループＲｇを引数とし、線長調整領域となる図形形状Ｒｃ２および面積Ｒｔ２を返り値として返す関数である。
【０３２６】
図８１〜図８４は、線長調整領域の詳細決定処理（ステップＳ３３０５）の詳細な処理手順を示すフローチャートである。図８１において、詳細格子用の１格子当たりのサイズを単位サイズＵｂとし（ステップＳ８１０１）、格子配列Ｇ．Ｇａ［］において、配線パス占有フラグＡｆ２がＡｆ２＝１となる格子群を格子配列Ｇｐ１［］とする（ステップＳ８１０２）。
【０３２７】
そして、配線グループＲｇに関連付けられている図形形状Ｒｂ１とその面積Ｒｓ１（線長調整領域の概略決定処理（ステップＳ３３０４）のステップＳ５６０７（図５６）で関連付け）を読み出す（ステップＳ８１０３）。
【０３２８】
図８５は、線長調整領域の詳細決定処理（ステップＳ３３０５）の具体例１を示す説明図である。図８５において、引数として与えられる格子管理テーブルＧａと、配線パス占有フラグＡｆ２＝１の格子と、線長調整領域の概略決定処理（ステップＳ３３０４）で得られた図形形状Ｒｂ１とが与えられる。
【０３２９】
図８１において、ステップＳ８１０３のあと、図形形状Ｒｂ１を単位サイズＵｂだけ拡大して図形形状Ｓ１とする（ステップＳ８１０４）。このあと、図３５に示した格子管理テーブル作成処理を実行する（ステップＳ８１０５）。
【０３３０】
格子管理テーブル作成処理（ステップＳ８１０５）では、図形形状Ｒｂ１を単位サイズＵｂだけ拡大して図形形状Ｓ１と単位サイズＵｂを引数とし、格子管理テーブルＧｂを返り値として返す。
【０３３１】
このあと、図３８に示した障害物のマッピング処理を実行する（ステップＳ８１０６）。障害物のマッピング処理（ステップＳ８１０６）では、格子管理テーブル作成処理（ステップＳ８１０５）で得られた格子管理テーブルＧｂを引数とし、障害物のマッピング後の格子管理テーブルＧｂを返り値として返す。
【０３３２】
つぎに、図４８に示した配線グループのマッピング処理を実行する（ステップＳ８１０７）。配線グループのマッピング処理（ステップＳ８１０７）では、障害物のマッピング処理（ステップＳ８１０６）で得られた格子管理テーブルＧｂを引数とし、配線グループのマッピング後の格子管理テーブルＧｂを返り値として返す。そして、図８２のステップＳ８２０１に移行する。
【０３３３】
図８６は、線長調整領域の詳細決定処理（ステップＳ３３０５）の具体例２を示す説明図である。図８６では、格子管理テーブルＧｂを示している。
【０３３４】
また、図８１の配線グループのマッピング処理（ステップＳ８１０７）のあと、図８２において、ループ変数Ｉ１をＩ１＝１とし（ステップＳ８２０１）、Ｉ１が格子配列Ｇｐ１［］の個数を超えたか否かを判断する（ステップＳ８２０２）。超えていない場合（ステップＳ８２０２：Ｎｏ）、格子配列Ｇｐ１［］のＩ１番目の格子の矩形形状を図形形状Ｓｒとし（ステップＳ８２０３）、図４２に示したパターン占有率計算処理を実行する（ステップＳ８２０４）。
【０３３５】
パターン占有率計算処理（ステップＳ８２０４）では、格子管理テーブルＧ＝Ｇｂ、図形形状Ｓｒ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ８２０４）では、引数として渡された図形形状Ｓｒと重なる格子群となる格子配列Ｇｐ２［］を返す。
【０３３６】
このあと、返り値として得られた格子配列Ｇｐ２［］の各格子の配線パス占有フラグＡｆ２をＡｆ２＝１とし（ステップＳ８２０５）、ループ変数Ｉ１をインクリメントして（ステップＳ８２０６）、ステップＳ８２０２に戻る。
【０３３７】
図８７は、線長調整領域の詳細決定処理（ステップＳ３３０５）の具体例３を示す説明図である。図８７では、格子管理テーブルＧａ，Ｇｂと、格子配列Ｇｐ１［］と、配線パス占有フラグＡｆ２＝１の格子とを示している。格子配列Ｇｐ１［］と重複する格子も配線パス占有フラグＡｆ２＝１となる。
【０３３８】
図８２に戻って、ステップＳ８２０２において、Ｉ１が格子配列Ｇｐ１［］の個数を超えた場合（ステップＳ８２０２：Ｙｅｓ）、詳細領域割当処理を実行する（ステップＳ８２０７）。詳細領域割当処理（ステップＳ８２０７）の詳細については後述するが、詳細領域割当処理（ステップＳ８２０７）は、格子管理テーブルＧｂ、図形形状Ｒｂ１、面積Ｒｓ１を引数とし、図形形状Ｒｃ１を返り値として返す関数である。
【０３３９】
そして、返り値として得られた図形形状Ｒｃ１の面積を面積Ｒｔ１とし（ステップＳ８２０８）、図形形状Ｒｃ１、面積Ｒｔ１を配線グループＲｇに関連付けて記憶装置に記憶する（ステップＳ８２０９）。具体的には、線長調整領域の概略決定処理（ステップＳ３３０４）において、線長領域テーブル２５００で追加された新規レコードのうち、不足面積にＲｓ１、概略形状情報にＲｂ１が設定された一方のレコードの詳細形状情報に図形形状Ｒｃ１を設定し、詳細面積に面積Ｒｔ１を設定する。そして、図８３のステップＳ８３０１に移行する。
【０３４０】
また、図８３において、配線グループＲｇに関連付けられた図形形状Ｒｂ２、面積Ｒｓ２を読み出し（ステップＳ８３０１）、図形形状Ｒｂ２を単位サイズＵｂだけ拡大して図形形状Ｓ２とする（ステップＳ８３０２）。このあと、図３５に示した格子管理テーブル作成処理を実行する（ステップＳ８３０３）。
【０３４１】
格子管理テーブル作成処理（ステップＳ８３０３）では、図形形状Ｒｂ２を単位サイズＵｂだけ拡大して図形形状Ｓ２と単位サイズＵｂを引数とし、格子管理テーブルＧｂを返り値として返す。
【０３４２】
このあと、図３８に示した障害物のマッピング処理を実行する（ステップＳ８３０４）。障害物のマッピング処理（ステップＳ８３０４）では、格子管理テーブル作成処理（ステップＳ８３０３）で得られた格子管理テーブルＧｂを引数とし、障害物のマッピング後の格子管理テーブルＧｂを返り値として返す。
【０３４３】
つぎに、図４８に示した配線グループのマッピング処理を実行する（ステップＳ８３０５）。配線グループのマッピング処理（ステップＳ８３０５）では、障害物のマッピング処理（ステップＳ８３０４）で得られた格子管理テーブルＧｂを引数とし、配線グループのマッピング後の格子管理テーブルＧｂを返り値として返す。そして、図８４のステップＳ８４０１に移行する。
【０３４４】
つぎに、図８４で示したステップＳ８４０１〜Ｓ８４０９を実行する。図８４に示した処理は、図８２に示した処理を、図形形状Ｒｂ２、面積Ｒｓ２についても実行する処理である。
【０３４５】
図８４において、ループ変数Ｉ１をＩ１＝１とし（ステップＳ８４０１）、Ｉ１が格子配列Ｇｐ１［］の個数を超えたか否かを判断する（ステップＳ８４０２）。超えていない場合（ステップＳ８４０２：Ｎｏ）、格子配列Ｇｐ１［］のＩ１番目の格子の矩形形状を図形形状Ｓｒとし（ステップＳ８４０３）、図４２に示したパターン占有率計算処理を実行する（ステップＳ８４０４）。
【０３４６】
パターン占有率計算処理（ステップＳ８４０４）では、格子管理テーブルＧ＝Ｇｂ、図形形状Ｓｒ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ８４０４）では、引数として渡された図形形状Ｓｒと重なる格子群となる格子配列Ｇｐ２［］を返す。
【０３４７】
このあと、返り値として得られた格子配列Ｇｐ２［］の各格子の配線パス占有フラグＡｆ２をＡｆ２＝１とし（ステップＳ８４０５）、ループ変数Ｉ１をインクリメントして（ステップＳ８４０６）、ステップＳ８４０２に戻る。
【０３４８】
また、ステップＳ８４０２において、Ｉ１が格子配列Ｇｐ１［］の個数を超えた場合（ステップＳ８４０２：Ｙｅｓ）、詳細領域割当処理を実行する（ステップＳ８４０７）。詳細領域割当処理（ステップＳ８４０７）の詳細については後述するが、詳細領域割当処理（ステップＳ８４０７）は、格子管理テーブルＧｂ、図形形状Ｒｂ２、面積Ｒｓ２を引数とし、図形形状Ｒｃ２を返り値として返す関数である。
【０３４９】
そして、返り値として得られた図形形状Ｒｃ２の面積を面積Ｒｔ２とし（ステップＳ８４０８）、図形形状Ｒｃ２、面積Ｒｔ２を配線グループＲｇに関連付けて記憶装置に記憶する（ステップＳ８４０９）。具体的には、線長調整領域の概略決定処理（ステップＳ３３０４）において、線長領域テーブル２５００で追加された新規レコードのうち、不足面積にＲｓ２、概略形状情報にＲｂ２が設定された一方のレコードの詳細形状情報に図形形状Ｒｃ２を設定し、詳細面積に面積Ｒｔ２を設定する。これにより、線長調整領域の詳細決定処理を終了する。
【０３５０】
＜詳細領域割当処理＞
つぎに、詳細領域割当処理について説明する。詳細領域割当処理は、図８２のステップＳ８２０７および図８４のステップＳ８４０７において実行される。詳細領域割当処理（ステップＳ８２０７／Ｓ８４０７）は、格子管理テーブルＧｂ、図形形状Ｒｂおよび面積Ｒｓを引数とし、詳細領域となる図形形状Ｓを返り値として返す関数である。
【０３５１】
図８８は、詳細領域割当処理の具体例１を示す説明図である。図８８において、斜線のハッチングで示した領域が、配線パス占有フラグＡｆ２がＡｆ２＝１となる格子群である。また、点のハッチングで示した領域が関数引数となる図形形状Ｒｂである。詳細領域割当処理では、配線パス占有フラグＡｆ２がＡｆ２＝１となる格子群を伝搬の開始位置として、上下左右の開き領域をつなげることで詳細な領域をもとめていく処理である。
【０３５２】
図８９および図９０は、詳細領域割当処理（ステップＳ８２０７／Ｓ８４０７）の詳細な処理手順を示すフローチャートである。まず、図８９において、詳細領域割当処理（ステップＳ８２０７／Ｓ８４０７）では、図４２に示したパターン占有率計算処理を実行する（ステップＳ８９０１）。
【０３５３】
パターン占有率計算処理（ステップＳ８９０１）では、格子管理テーブルＧ＝Ｇｂ、図形形状Ｒｂ、図形種別フラグＦｋ＝０、加算フラグＦａ＝０に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ８９０１）では、引数として渡された図形形状Ｒｂと重なる格子群となる格子配列Ｇｐ２［］を返す。
【０３５４】
つぎに、格子配列Ｇ．Ｇａ［］において配線パス占有フラグＡｆ２＝１となる格子群を格子配列Ｇｐ１［］とし（ステップＳ８９０２）、格子配列Ｇｐ２［］および格子配列Ｇｐ３［］を空とし（ステップＳ８９０３）、図９０のステップＳ９００１に移行する。
【０３５５】
なお、格子配列Ｇｐ１［］の初期値は、図８８において太枠で囲まれた配線パス占有フラグＡｆ２＝１となる格子群である。また、格子配列Ｇｐ２［］は、格子配列Ｇｐ１［］からの伝搬済みの格子群であり、初期値が空である。
【０３５６】
また、図９０において、格子配列Ｇｐ1［］＝Φ（空集合）であるか否かを判断する（ステップＳ９００１）。Ｇｐ1［］＝Φでない場合（ステップＳ９００１：Ｎｏ）、格子配列Ｇｐ１［］の１番目（先頭）の格子を格子Ｇ１とし（ステップＳ９００２）、格子配列Ｇｐ１［］から格子Ｇ１を削除した格子配列を、あらたな格子配列Ｇｐ１［］とする（ステップＳ９００３）。
【０３５７】
そして、格子Ｇ１が格子配列Ｇｐ２［］に含まれているか否かを判断する（ステップＳ９００４）。含まれている場合（ステップＳ９００４：Ｙｅｓ）、ステップＳ９００１に戻る。一方、含まれていない場合（ステップＳ９００４：Ｎｏ）、格子配列Ｇｐ２［］と格子Ｇ１との和集合をあらたな格子配列Ｇｐ２［］とする（ステップＳ９００５）。
【０３５８】
つぎに、格子Ｇ１は格子配列Ｇｐ［］に含まれているか否かを判断する（ステップＳ９０１６）。ここで、格子配列Ｇｐ［］とは、関数引数である図形形状Ｒｂと交差する格子の集合である。したがって、ステップＳ９００６では、格子Ｇ１が関数引数である図形形状Ｒｂ内の格子であるか否かを判定することとなる。そして、格子Ｇ１が図形形状Ｒｂ内の格子であれば、格子配列Ｇｐ３［］に追加し、格子Ｇ１の上下左右の格子を格子配列Ｇｐ１［］に追加することとなる。
【０３５９】
そして、格子Ｇ１が格子配列Ｇｐ［］に含まれていない場合（ステップＳ９００６：Ｎｏ）、格子の領域変換処理（ステップＳ９０１１）に移行する。一方、格子Ｇ１が格子配列Ｇｐ［］に含まれている場合（ステップＳ９００６：Ｙｅｓ）、格子配列Ｇｐ３［］を格子Ｇ１との和集合をあらたな格子配列Ｇｐ３［］とし（ステップＳ９００７）とし、図８１に示した格子配列の面積計算処理を実行する（ステップＳ９００８）。格子配列の面積計算処理（ステップＳ９００８）では、格子配列Ｇｐ３［］を引数とし、面積Ｒｓ１を返り値として返す。
【０３６０】
そして、格子配列Ｇｐ３［］を構成する図形形状の面積Ｒｓ１の面積がＲｓ１≧Ｒｓであるか否かを判断する（ステップＳ９００９）。Ｒｓ１≧Ｒｓである場合（ステップＳ９００９：Ｙｅｓ）、格子の領域変換処理（ステップＳ９０１１）に移行する。一方、Ｒｓ１≧Ｒｓでない場合（ステップＳ９００９：Ｎｏ）、格子配列Ｇｐ１［］と格子Ｇ１の上下左右の格子との和集合をあらたな格子配列Ｇｐ１［］とし（ステップＳ９０１０）、ステップＳ９００１に戻る。
【０３６１】
一方、格子配列Ｇｐ１［］＝Φである場合（ステップＳ９００１：Ｙｅｓ）、格子の領域変換処理（ステップＳ９０１１）に移行する。格子の領域変換処理（ステップＳ９０１１）では、格子配列Ｇｐ３［］を引数とし、詳細領域である図形形状Ｓを返り値として返す。
【０３６２】
図９１は、詳細領域割当処理の具体例２を示す説明図である。図９１において、太一点鎖線の枠で囲まれた領域が、図形形状Ｓである。
【０３６３】
＜線長調整領域のマッピング処理＞
つぎに、線長調整領域のマッピング処理について説明する。線長調整領域のマッピング処理では、線長調整領域を障害物として反映させる処理である。
【０３６４】
図９２は、図３３に示した線長調整領域のマッピング処理（ステップＳ３３０６）の詳細な処理手順を示すフローチャートである。まず、配線グループＲｇに関連付けられた図形形状Ｒｃ１、Ｒｃ２を図形形状Ｒｃ１、Ｒｃ２とし（ステップＳ９２０１）、図４２に示したパターン占有率計算処理（ステップＳ９２０２、Ｓ９２０３）を実行する。
【０３６５】
パターン占有率計算処理（ステップＳ９２０２）では、格子管理テーブルＧ＝Ｇａ、図形形状Ｒｃ１、図形種別フラグＦｋ＝２、加算フラグＦａ＝１に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ９２０２）では、引数として渡された配線パスの図形形状Ｒｃ１に、格子管理テーブルＧａ内の格子が含まれている割合を計算して、配線パスの図形形状Ｒｃ１に含まれている格子配列Ｇｐ［］を返すこととなる。
【０３６６】
また、パターン占有率計算処理（ステップＳ９２０３）では、格子管理テーブルＧ＝Ｇａ、図形形状Ｒｃ２、図形種別フラグＦｋ＝２、加算フラグＦａ＝１に設定して、図４２に示した処理手順にしたがって実行する。これにより、パターン占有率計算処理（ステップＳ９２０３）では、引数として渡された配線パスの図形形状Ｒｃ２に、格子管理テーブルＧａ内の格子が含まれている割合を計算して、配線パスの図形形状Ｒｃ２に含まれている格子配列Ｇｐ［］を返すこととなる。
【０３６７】
これにより、線長調整領域のマッピング処理（ステップＳ３３０６）では、図形形状Ｒｃ１、Ｒｃ２に含まれる格子配列Ｇｐ［］を線長調整領域を描画対象としてマッピングすることができる。
【０３６８】
＜線長調整領域の代替層割当処理＞
つぎに、線長調整領域の代替層割当処理について説明する。線長調整領域の代替層割当処理は、線長調整領域の不足分を代替層に割り当てる処理であり、具体的には、配線グループＲｇを引数とし、図形形状Ｒｂ３、Ｒｃ３、面積Ｒｓ３、Ｒｔ３を返り値として返す関数である。
【０３６９】
図９３は、図３３に示した線長調整領域の代替層割当処理（ステップＳ３３１１）の詳細な処理手順を示すフローチャートである。まず、配線グループＲｇに関連付けられた面積Ｒｓ１、Ｒｓ２を面積Ｒｓ１、Ｒｓ２とし（ステップＳ９３０１）、配線グループＲｇに関連付けられた面積Ｒｔ１、Ｒｔ２を面積Ｒｔ１、Ｒｔ２とする（ステップＳ９３０２）。
【０３７０】
ここで、面積Ｒｓ１、Ｒｓ２は、線長調整領域の概略決定処理（ステップＳ３３０４）において配線グループＲｇに関連付けられた図形形状Ｒｂ１、Ｒｂ２の面積である。また、面積Ｒｔ１、Ｒｔ２は、線長調整領域の詳細決定処理（ステップＳ３３０５）において配線グループＲｇに関連付けられた図形形状Ｒｃ１、Ｒｃ２の面積である。
【０３７１】
つぎに、面積Ｒｓ３を求める（ステップＳ９３０３）。面積Ｒｓ３は、Ｒｓ３＝（Ｒｓ１＋Ｒｓ２）−（Ｒｔ１＋Ｒｔ２）とする。そして、Ｒｓ３＞０であるか否かを判断する（ステップＳ９３０４）。これにより、線長調整領域が不足しているか否かを判定する。Ｒｓ３＞０でない場合（ステップＳ９３０４：Ｎｏ）、線長調整領域の不足分を代替層に割当せずに終了する。
【０３７２】
一方、Ｒｓ３＞０である場合（ステップＳ９３０４：Ｙｅｓ）、線長調整領域が不足しているため、配線グループＲｇの形状範囲内で線長領域を割り当てる。具体的には、基板の図形形状を図形形状Ｂｄとし（ステップＳ９３０５）、概略格子用の１格子当たりのサイズを単位サイズＵａとし（ステップＳ９３０６）、図３５に示した格子管理テーブル作成処理を実行する（ステップＳ９３０７）。
【０３７３】
格子管理テーブル作成処理（ステップＳ９３０７）では、図形形状Ｓ＝Ｂｄ、単位サイズＵ＝Ｕａを引数とし、格子管理テーブルＧａを返り値として返す。そして、図３８〜図４０に示した障害物のマッピング処理を実行する（ステップＳ９３０８）。障害物のマッピング処理（ステップＳ９３０８）では、格子管理テーブル作成処理（ステップＳ９３０７）で作成された格子管理テーブルＧａを引数とし、障害物マッピング後の格子管理テーブルＧａを返り値として返す。
【０３７４】
そして、配線グループＲｇに関連付けられた図形形状Ｒａを図形形状Ｒａとし（ステップＳ９３０９）、座標配列Ｃｏ［］＝Φ（空集合）とする（ステップＳ９３１０）。そして、図６５〜図７０に示した概略領域割当処理を実行する（ステップＳ９３１１）。
【０３７５】
概略領域割当処理（ステップＳ９３１１）では、格子管理テーブルＧａ、図形形状Ｒａ、座標配列Ｃｏ［］、面積Ｒｓ３を引数とし、図形形状Ｒｂ３を返す。このあと、詳細格子用の１格子当たりのサイズを単位サイズＵｂとし（ステップＳ９３１２）、図３５に示した格子管理テーブル作成処理を実行する（ステップＳ９３１３）。
【０３７６】
格子管理テーブル作成処理（ステップＳ９３１３）では、図形形状Ｓ＝Ｒｂ３、単位サイズＵ＝Ｕｂを引数とし、格子管理テーブルＧｂを返り値として返す。そして、図３８〜図４０に示した障害物のマッピング処理を実行する（ステップＳ９３１４）。障害物のマッピング処理（ステップＳ９３１４）では、格子管理テーブル作成処理（ステップＳ９３１３）で作成された格子管理テーブルＧｂを引数とし、障害物マッピング後の格子管理テーブルＧｂを返り値として返す。
【０３７７】
そして、図８９および図９０に示した詳細領域割当処理を実行する（ステップＳ９３１５）。詳細領域割当処理（ステップＳ９３１５）では、格子管理テーブルＧｂ、図形形状Ｒｂ３、面積Ｒｓ３を引数とし、図形形状Ｒｃ３を返り値として返す。
【０３７８】
そして、図形形状Ｒｃ３の面積を面積Ｒｔ３とし（ステップＳ９３１６）、図形形状Ｒｂ３、Ｒｃ３、面積Ｒｓ３、Ｒｔ３を配線グループＲｇに関連付けて記憶装置に記憶する（ステップＳ９３１７）。
【０３７９】
具体的には、概略領域テーブル２４００に新規レコードを追加し、追加した新規レコードの概略形状情報に図形形状Ｒｂ３を設定する。また、階層番号を、配線グループＲｇに対応する概略領域番号のレコードに設定された階層番号とは異なる番号に設定する。この場合、図形形状Ｒｂ３を配置できる階層であればどの階層でもよいが、配線グループＲｇに対応する概略領域番号のレコードに設定された階層番号に近いほうが好ましい。なお、分割線は未定義となる。
【０３８０】
また、線長領域テーブル２５００に新規レコードを追加し、追加した新規レコードの配線パス番号リストに、対応する配線グループＲｇを構成する配線パスの配線パス番号と設定する。そして、不足面積を未定義とし、概略形状情報に図形形状Ｒｂ３を設定する。また、詳細形状情報に図形形状Ｒｃ３を設定する。また、詳細面積にＲｔ３を設定する。そして、この新規レコードの線長調整番号を、概略領域テーブル２４００で追加された新規レコードの線長領域番号リストに追加する。これにより、線長調整領域の代替層割当処理を終了する。
【０３８１】
＜線長調整領域表示処理＞
つぎに、線長調整領域表示処理について説明する。線長調整領域表示処理では、線長調整領域を表示画面に描画することにより、線長調整領域を表示する処理である。線長調整領域表示処理が終了することで、全処理が終了することとなる。
【０３８２】
図９４は、図３３に示した線長調整領域表示処理（ステップＳ３３１３）の詳細な処理手順を示すフローチャートである。まず、ループ変数Ｉ１をＩ１＝１とし（ステップＳ９４０１）、Ｉ１が配線グループ数より大きいか否かを判断する（ステップＳ９４０２）。Ｉ１が配線グループ数以下である場合（ステップＳ９４０２：Ｎｏ）、Ｉ１番目の配線グループを配線グループＲｇとし（ステップＳ９４０３）、配線グループＲｇに関連付けられたＲｓ１、Ｒｓ２を面積Ｒｓ１、Ｒｓ２とする（ステップＳ９４０４）。また、配線グループＲｇに関連付けられたＲｔ１、Ｒｔ２、Ｒｔ３を面積Ｒｔ１、Ｒｔ２、Ｒｔ３とする（ステップＳ９４０５）。
【０３８３】
つぎに、面積Ｒｓ４を求める（ステップＳ９４０６）。面積Ｒｓ４は、Ｒｓ４＝（Ｒｓ１＋Ｒｓ２）−（Ｒｔ１＋Ｒｔ２＋Ｒｔ３）とする。そして、画面描画の塗りつぶしパターンを、線長調整領域が足りている場合のパターンに変更し（ステップＳ９４０７）、Ｒｓ４＞０であるか否かを判断する（ステップＳ９４０８）。
【０３８４】
Ｒｓ４＞０でない場合（ステップＳ９４０８：Ｎｏ）、ステップＳ９４１０に移行する。一方、Ｒｓ４＞である場合（ステップＳ９４０８：Ｙｅｓ）、画面描画の塗りつぶしパターンを、線長調整領域が不足している場合のパターンに変更し（ステップＳ９４０９）、ステップＳ９４１０に移行する。
【０３８５】
ステップＳ９４１０では、配線グループに関連付けられたＲｃ１、Ｒｃ２、Ｒｃ３を図形形状Ｒｃ１、Ｒｃ２、Ｒｃ３とし（ステップＳ９４１０）、Ｒｃ１＝Φ（空集合）であるか否かを判断する（ステップＳ９４１１）。Ｒｃ１＝Φである場合（ステップＳ９４１１：Ｙｅｓ）、ステップＳ９４１３に移行する。一方、Ｒｃ１＝Φでない場合（ステップＳ９４１１：Ｎｏ）、図形形状Ｒｃ１を描画して（ステップＳ９４１２）、ステップＳ９４１３に移行する。
【０３８６】
ステップＳ９４１３では、Ｒｃ２＝Φ（空集合）であるか否かを判断する（ステップＳ９４１３）。Ｒｃ２＝Φである場合（ステップＳ９４１３：Ｙｅｓ）、ステップＳ９４１５に移行する。一方、Ｒｃ２＝Φでない場合（ステップＳ９４１３：Ｎｏ）、図形形状Ｒｃ２を描画して（ステップＳ９４１４）、ステップＳ９４１５に移行する。
【０３８７】
ステップＳ９４１５では、Ｒｃ３＝Φ（空集合）であるか否かを判断する（ステップＳ９４１５）。Ｒｃ３＝Φである場合（ステップＳ９４１５：Ｙｅｓ）、ステップＳ９４１７に移行する。一方、Ｒｃ３＝Φでない場合（ステップＳ９４１５：Ｎｏ）、図形形状Ｒｃ３を描画して（ステップＳ９４１６）、ステップＳ９４１７に移行する。
【０３８８】
ステップＳ９４１７では、ループ変数Ｉ１をインクリメントし（ステップＳ９４１７）、ステップＳ９４０２に戻る。そして、ステップＳ９４０２において、Ｉ１が配線グループ数より大きい場合（ステップＳ９４０２：Ｙｅｓ）、線長調整領域表示処理を終了する。
【０３８９】
以上のことから、本実施の形態によれば、設計データにおいて、線長制約条件に違反する配線パスを自動的に検出する。そして、線長の違反線長を元に、その配線パスの線長調整に必要な配線領域をその配線パスが属する配線グループの近くに表示させる。
【０３９０】
これにより、違反する配線グループの有無および線長調整に必要な配線領域を設計者に対して一つにまとめて示すことができる。したがって、設計者に対して配線結線前の段階で、配線接続関係を元にして各配線グループが使用する線長調整領域を表示させながら配線経路の検討に使用できる。また、配線の結線作業において先に配線した配線グループの線長調整領域を残しながら配線することが可能となる。このようにして、後の線長調整を考慮しながら配線作業がおこなうことができるようになり、設計の手戻りなく効率的におこなうことが可能となる。
【０３９１】
また、配線グループ内の不足線長の比例関係により、配線グループを分割することで、線長調整が必要な残余の配線パス側に、線長調整領域を割当てることができ、後の線長調整作業がやりやすくすることができる。
【０３９２】
また、比例関係がない場合は、真ん中の配線パスを基準にして分割することで、両側に均等に線長調整領域を割り当てることができ、後の線長調整作業がやりやすくすることができる。
【０３９３】
また、分割した際に、迂回領域を最短経路で取得し、配線グループの近傍から段階的に拡大していくことで、配線グループの近傍の位置を保ちながら、線長調整領域を不足面積に相当する大きさにまで拡張することができる。
【０３９４】
また、障害物と重複しないように線長調整領域を割り当てることで手戻りの防止を図ることができ、設計者が指定した範囲で線長調整領域を割り当てることで設計者が意図して線長調整をおこなうことができる。また、未結線であっても線長調整領域の大きさや位置を予測することができるため、設計者は結線前や結線途中においても事前に線長調整を検討することができる。
【０３９５】
さらに、不足分の面積については異なるように表示することで、事前に線長調整領域が不足していることや不足している面積、不足している面積に相当する領域の配置先がわかる。したがって、配線設計の手戻りの減少を図ることができる。
【０３９６】
なお、本実施の形態で説明した設計支援方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本設計支援プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本設計支援プログラムは、インターネット等のネットワークを介して配布してもよい。
【０３９７】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０３９８】
（付記１）コンピュータを、
送信元から送信先までの配線グループを構成する複数の配線パスの中から、線長が最長となる特定の配線パスを選択する選択手段、
前記選択手段によって選択された特定の配線パスの線長に対する残余の配線パスの不足線長を検出する不足線長検出手段、
前記不足線長検出手段によって検出された前記残余の配線パスの不足線長の総和に応じた不足面積を算出する不足面積算出手段、
前記不足面積算出手段によって算出された不足面積の総和に応じた線長調整領域を、前記配線グループの近傍に割り当てる割当手段、
表示画面を制御して、前記配線グループと前記割当手段によって割当てられた線長調整領域とを前記表示画面に表示する表示制御手段、
として機能させることを特徴とする設計支援プログラム。
【０３９９】
（付記２）前記コンピュータを、
前記各配線パスの並び順を検出する配列位置検出手段、
前記配列位置検出手段によって検出された前記各配線パスの配列順に従って、前記不足線長の列に比例関係があるか否かを判断する比例関係判断手段、
前記比例関係判断手段によって判断された判断結果に基づいて、前記特定の配線パスを含む境界線により前記配線グループを分割する分割手段として機能させ、
前記不足面積算出手段は、
前記分割手段による分割で得られた分割配線グループごとに、当該分割配線グループ内の残余の配線パスの不足線長の総和に応じた不足面積を算出し、
前記割当手段は、
前記分割配線グループごとに、前記不足面積に応じた線長調整を前記分割配線グループの近傍に割り当てることを特徴とする付記１に記載の設計支援プログラム。
【０４００】
（付記３）前記コンピュータを、
前記比例関係判断手段によって比例関係がないと判断された場合、前記複数の配線パスのうち配列順が中央となる配線パスを前記特定の配線パスに再選択する再選択手段として機能させ、
前記分割手段は、
前記再選択手段によって再選択された特定の配線パスを含む境界線により前記配線グループを分割することを特徴とする付記２に記載の設計支援プログラム。
【０４０１】
（付記４）前記コンピュータを、
前記分割配線グループごとに、前記分割配線グループを迂回して前記境界線の一端から他端までの最短経路を探索する探索手段、
前記分割配線グループごとに、前記境界線と前記探索手段によって探索された最短経路とで囲まれた図形の中から、前記分割配線グループを迂回しかつ配線可能な迂回領域を取得する取得手段、
前記分割配線グループごとに、前記取得手段によって取得された迂回領域の面積が前記不足面積以下となるように調整することにより、線長調整領域を設定する設定手段として機能させ、
前記割当手段は、
前記設定手段によって設定された線長調整領域、前記配線グループの近傍に割り当てることを特徴とする付記２または３に記載の設計支援プログラム。
【０４０２】
（付記５）前記コンピュータを、
前記分割配線グループごとに、前記迂回領域の面積が前記不足面積以下であるか否かを判定する判定手段として機能させ、
前記探索手段は、
前記判定手段によって前記不足面積以下であると判定された場合、前記分割配線グループを最大限迂回して前記境界線の一端から他端までの最短経路をあらたに探索し、
前記取得手段は、
前記境界線と前記探索手段によってあらたに探索された最短経路とで囲まれた図形の中から、前記分割配線グループを迂回する迂回領域を取得することを特徴とする付記４に記載の設計支援プログラム。
【０４０３】
（付記６）前記コンピュータを、
前記判定手段によって前記不足面積以下であると判定された場合、前記境界線と前記探索手段によってあらたに探索された最短経路とで囲まれた図形を所定量拡大させた図形を作成する作成手段として機能させ、
前記取得手段は、
前記作成手段によって作成された図形の中から、前記分割配線グループを迂回する迂回領域を取得することを特徴とする付記５に記載の設計支援プログラム。
【０４０４】
（付記７）前記割当手段は、
前記線長調整領域を、障害物がない前記配線グループの近傍に割り当てることを特徴とする付記１〜６のいずれか１つに記載の設計支援プログラム。
【０４０５】
（付記８）前記割当手段は、
前記線長調整領域を、前記配線グループの近傍のうち範囲指定された領域内に割り当てることを特徴とする付記１〜７のいずれか１つに記載の設計支援プログラム。
【０４０６】
（付記９）前記コンピュータを、
前記配線グループのうち未結線の配線パスの仮線長を算出する仮線長算出手段として機能させ、
前記選択手段は、
前記仮線長算出手段によって算出された仮線長を用いて、前記配線グループを構成する複数の配線パスの中から、前記特定の配線パスを選択し、
前記不足線長検出手段は、
前記仮線長算出手段によって算出された仮線長を用いて、前記特定の配線パスの線長に対する残余の配線パスの不足線長を検出し、
前記不足面積算出手段は、
前記仮線長算出手段によって算出された仮線長を用いて、前記残余の配線パスの不足線長の総和に応じた不足面積を算出することを特徴とする付記１〜８のいずれか１つに記載の設計支援プログラム。
【０４０７】
（付記１０）前記割当手段は、
他の線長調整領域と重複しないように割り当てることを特徴とする付記１〜９のいずれか１つに記載の設計支援プログラム。
【０４０８】
（付記１１）前記判定手段は、
前記不足面積に基づいて、前記線長調整領域の面積が充足しているか否かを判定し、
前記割当手段は、
前記判定手段によって不足していると判定された場合、不足分の面積に相当する領域を他の階層に割り当てることを特徴とする付記１〜１０のいずれか１つに記載の設計支援プログラム。
【０４０９】
（付記１２）前記判定手段は、
前記不足面積に基づいて、前記線長調整領域の面積が充足しているか否かを判定し、
前記表示制御手段は、
前記判定手段によって不足していると判定された場合、前記線長調整領域が充足している場合と異なるように前記表示画面に表示することを特徴とする付記１〜１１のいずれか１つに記載の設計支援プログラム。
【０４１０】
（付記１３）送信元から送信先までの配線グループを構成する複数の配線パスの中から、線長が最長となる特定の配線パスを選択する選択手段と、
前記選択手段によって選択された特定の配線パスの線長に対する残余の配線パスの不足線長を検出する不足線長検出手段と、
前記不足線長検出手段によって検出された前記残余の配線パスの不足線長の総和に応じた不足面積を算出する不足面積算出手段と、
前記不足面積算出手段によって算出された不足面積の総和に応じた線長調整領域を、前記配線グループの近傍に割り当てる割当手段と、
表示画面を制御して、前記配線グループと前記割当手段によって割当てられた線長調整領域とを前記表示画面に表示する表示制御手段と、
を備えることを特徴とする設計支援装置。
【０４１１】
（付記１４）選択手段、不足線長検出手段、不足面積算出手段、割当手段および表示制御手段を備えるコンピュータが、
前記選択手段により、送信元から送信先までの配線グループを構成する複数の配線パスの中から、線長が最長となる特定の配線パスを選択する選択工程と、
前記不足線長検出手段により、前記選択工程によって選択された特定の配線パスの線長に対する残余の配線パスの不足線長を検出する不足線長検出工程と、
前記不足面積算出手段により、前記不足線長検出工程によって検出された前記残余の配線パスの不足線長の総和に応じた不足面積を算出する不足面積算出工程と、
前記割当手段により、前記不足面積算出工程によって算出された不足面積の総和に応じた線長調整領域を、前記配線グループの近傍に割り当てる割当工程と、
前記表示制御手段により表示画面を制御して、前記配線グループと前記割当工程によって割当てられた線長調整領域とを前記表示画面に表示する表示工程と、
を実行することを特徴とする設計支援方法。
【符号の説明】
【０４１２】
１３００  設計基準テーブル
１４００  基板テーブル
１５００  ネットテーブル
１６００  ランド形状テーブル
１７００  部品ピンテーブル
１８００  ビアテーブル
１９００  ラインテーブル
２０００  線長制約条件テーブル
２１００  配線パステーブル
２２００  配線ルートテーブル
２３００  線長調整テーブル
２４００  概略領域テーブル
２５００  線長領域テーブル
２６００  指示領域テーブル
２７００  仮配線テーブル
３０００  設計支援装置
３００１  選択部
３００２  不足線長検出部
３００３  不足面積算出部
３００４  割当部
３００５  表示制御部
３００６  配列位置検出部
３００７  比例関係判断部
３００８  分割部
３００９  再選択部
３０１０  探索部
３０１１  取得部
３０１２  設定部
３０１３  仮線長算出部
【図１】
2011086267.tif 000003
【図２】
2011086267.tif 000004
【図３】
2011086267.tif 000005
【図４】
2011086267.tif 000006
【図５】
2011086267.tif 000007
【図６】
2011086267.tif 000008
【図７】
2011086267.tif 000009
【図８】
2011086267.tif 000010
【図９】
2011086267.tif 000011
【図１０】
2011086267.tif 000012
【図１１】
2011086267.tif 000013
【図１２】
2011086267.tif 000014
【図１３】
2011086267.tif 000015
【図１４】
2011086267.tif 000016
【図１５】
2011086267.tif 000017
【図１６】
2011086267.tif 000018
【図１７】
2011086267.tif 000019
【図１８】
2011086267.tif 000020
【図１９】
2011086267.tif 000021
【図２０】
2011086267.tif 000022
【図２１】
2011086267.tif 000023
【図２２】
2011086267.tif 000024
【図２３】
2011086267.tif 000025
【図２４】
2011086267.tif 000026
【図２５】
2011086267.tif 000027
【図２６】
2011086267.tif 000028
【図２７】
2011086267.tif 000029
【図２８】
2011086267.tif 000030
【図２９】
2011086267.tif 000031
【図３０】
2011086267.tif 000032
【図３１】
2011086267.tif 000033
【図３２】
2011086267.tif 000034
【図３３】
2011086267.tif 000035
【図３４】
2011086267.tif 000036
【図３５】
2011086267.tif 000037
【図３６】
2011086267.tif 000038
【図３７】
2011086267.tif 000039
【図３８】
2011086267.tif 000040
【図３９】
2011086267.tif 000041
【図４０】
2011086267.tif 000042
【図４１】
2011086267.tif 000043
【図４２】
2011086267.tif 000044
【図４３】
2011086267.tif 000045
【図４４】
2011086267.tif 000046
【図４５】
2011086267.tif 000047
【図４６】
2011086267.tif 000048
【図４７】
2011086267.tif 000049
【図４８】
2011086267.tif 000050
【図４９】
2011086267.tif 000051
【図５０】
2011086267.tif 000052
【図５１】
2011086267.tif 000053
【図５２】
2011086267.tif 000054
【図５３】
2011086267.tif 000055
【図５４】
2011086267.tif 000056
【図５５】
2011086267.tif 000057
【図５６】
2011086267.tif 000058
【図５７】
2011086267.tif 000059
【図５８】
2011086267.tif 000060
【図５９】
2011086267.tif 000061
【図６０】
2011086267.tif 000062
【図６１】
2011086267.tif 000063
【図６２】
2011086267.tif 000064
【図６３】
2011086267.tif 000065
【図６４】
2011086267.tif 000066
【図６５】
2011086267.tif 000067
【図６６】
2011086267.tif 000068
【図６７】
2011086267.tif 000069
【図６８】
2011086267.tif 000070
【図６９】
2011086267.tif 000071
【図７０】
2011086267.tif 000072
【図７１】
2011086267.tif 000073
【図７２】
2011086267.tif 000074
【図７３】
2011086267.tif 000075
【図７４】
2011086267.tif 000076
【図７５】
2011086267.tif 000077
【図７６】
2011086267.tif 000078
【図７７】
2011086267.tif 000079
【図７８】
2011086267.tif 000080
【図７９】
2011086267.tif 000081
【図８０】
2011086267.tif 000082
【図８１】
2011086267.tif 000083
【図８２】
2011086267.tif 000084
【図８３】
2011086267.tif 000085
【図８４】
2011086267.tif 000086
【図８５】
2011086267.tif 000087
【図８６】
2011086267.tif 000088
【図８７】
2011086267.tif 000089
【図８８】
2011086267.tif 000090
【図８９】
2011086267.tif 000091
【図９０】
2011086267.tif 000092
【図９１】
2011086267.tif 000093
【図９２】
2011086267.tif 000094
【図９３】
2011086267.tif 000095
【図９４】
2011086267.tif 000096