配線支援方法及び装置
【課題】配線すべき複数の信号線を、ユーザの指定する目的に従って適切にグループ化する。
【解決手段】配線すべき複数の信号線を複数のグループに分けるための方法は、ユーザから、複数の信号線のグループ化の条件の指定を受け付けるステップと、指定された、グループ化の条件と、データ格納部に格納されている、複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、複数の信号線のグループ化の処理を切り替えて実施する実施ステップとを含む。
【解決手段】配線すべき複数の信号線を複数のグループに分けるための方法は、ユーザから、複数の信号線のグループ化の条件の指定を受け付けるステップと、指定された、グループ化の条件と、データ格納部に格納されている、複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、複数の信号線のグループ化の処理を切り替えて実施する実施ステップとを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、ＬＳＩ（Large Scale Integration）やプリント配線基板などにおける信号線の配線を支援するための技術に関する。
【背景技術】
【０００２】
近年、複数の層を有する多層基板における配線設計作業では信号速度が高速化し、設計制約条件が指示されることが一般的になってきている。設計制約条件の中には、部品間を接続する信号線を流れる信号のタイミングを合わせるために、配線パスに対してその長さが指示されていたり、バスなどのような複数の配線パスからなるグループにおいてはその各配線パスの線長はすべて等しい長さとするという指示がされていたりする。
【０００３】
例えば図１に示すように、信号の送信元であるドライバ１０００から信号の受信先であるレシーバ１１００まで、同一タイミングで信号が到達しなければならない場合には、配線パスの線長は全て等しい長さという等長線長条件が課される。
【０００４】
また、例えば図２Ａ（上面図）及び図２Ｂ（断面図）に示すように、多層基板の場合、第１の層Ｌ１の信号端子１００４から第２の層Ｌ２の信号端子１００３（例えば半導体チップＩＣ１の端子）までをビア１００１を使って配線することができる。しかしながら、各信号はビアを使っての複数層による配線１００２では層間移動での遅延が発生するため、図２Ｃに示すように、ビアを使用しない単層配線をすることが求められてきている。
【０００５】
しかし、図３Ａに示すような始点端子群Ａから終点端子群Ｂまでの多数の信号を含む信号群を単層配線すると、図３Ｂのように迂回する配線などにより配線領域が広がり、また信号間での線長差分が大きくなるという問題が生ずる。
【０００６】
図４Ａに模式的に示すように、高密度実装のため配線領域１６００を小さくする場合には、配線すべき信号群におけるドライバからレシーバまでの最大線長を短くすることになる。しかしながら、配線領域を重視すると、信号群における線長のばらつきが生じて等長線長条件を遵守するための調整が難しくなる場合が生ずる。
【０００７】
一方、図４Ｂに模式的に示すように、等長線長条件を重視して、線長差を小さくするように配線を行う場合には、配線すべき信号群におけるドライバからレシーバまでの最大線長が長くなって、配線領域１７００が大きくなり高密度配線に支障をきたす場合も生ずる。
【０００８】
そのため、配線すべき信号群を複数の層にグループ化し、各層の信号群ではこのような問題が起こらないようにすることが望まれる。
【０００９】
しかしながら、人手で、配線すべき信号群を複数の層に適切にグループ化するのは難しい場合が多い。具体的には、要件を満たすように配線を行うことができないことが後から分かって、グループ化からやり直すといった手戻りを行うという非効率な作業が行われることになる。
【００１０】
また、信号群の仮想配線領域を計算し、他の信号群の領域と重なった領域の信号数を調整し別層に移動するという自動化技術も存在している。しかしながら、このような技術では、他の信号群の存在が前提となっており、線長差の問題については考慮されてない。
【００１１】
さらに、部品の配置、配線の混雑度を評価することで信号群をグループ化し、できるだけグループ化した各信号を近接するように配置して最適な経路を探索する手法も存在している。しかし、この技術でも、グループ化においては制約条件を満たすような考慮はないため、線長の問題を解決できないケースがある。また、グループ化した信号群の概略経路を再考しては評価する作業が繰り返され効率が悪い。また、配線領域の効率化についても考慮がなされていない。
【００１２】
さらに、信号配線間隔を複数本分見積もって束配線し、出力側と入力側で端子の並びが同じ時はプリント基板の同一層内で配線を決定し、異なるときは、任意の折れ曲がり領域にスイッチングエリアを設けて二層に割り当てる技術も存在している。しかしながら、二層に分けるというのはビアを介して接続することを述べており、上で述べたような単層配線で制約条件を満たすものではない。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２００６−１１６８４号公報
【特許文献２】特開２００４−２８７６８１号公報
【特許文献３】特開平７−２９６０２７号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
複数の層で単層配線を行うため、配線すべき複数の信号線をグループ化する場合に、考慮すべき事項は以下のとおりである。すなわち、等長線長条件を充足しやすくする線長調整容易性と、信号線や信号端子を密集させずに配線をし易くすることで配線領域を削減する結線容易性とである。また、これらの両方を考慮する場合であってもいずれを優先させるかという問題もある。従来技術は、このような問題に対処するように、複数の信号線をグループ化することができない。
【００１５】
従って、本技術の目的は、一側面として、配線すべき複数の信号線を、ユーザの指定する目的に従って適切にグループ化する技術を提供することである。
【課題を解決するための手段】
【００１６】
配線すべき複数の信号線を複数のグループに分けるための方法は、（Ａ）ユーザから、複数の信号線のグループ化の条件の指定を受け付けるステップと、（Ｂ）指定された、グループ化の条件と、データ格納部に格納されている、複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、複数の信号線のグループ化の処理を切り替えて実施する実施ステップとを含む。
【発明の効果】
【００１７】
配線すべき複数の信号線を、ユーザの指定する目的に従って適切にグループ化できるようになる。
【図面の簡単な説明】
【００１８】
【図１】図１は、等長線長条件を説明するための模式図である。
【図２Ａ】図２Ａは、ビアを用いた配線の一例を示す平面図である。
【図２Ｂ】図２Ｂは、ビアを用いた配線の一例を示す断面図である。
【図２Ｃ】図２Ｃは、単層配線の一例を示す平面図である。
【図３Ａ】図３Ａは、配線前の信号端子の配置状態を示す図である。
【図３Ｂ】図３Ｂは、配線後の状態を示す図である。
【図４Ａ】図４Ａは、配線領域を小さくした場合の線長の分布を示す模式図である。
【図４Ｂ】図４Ｂは、等長線長条件を満たすようにした場合の配線領域の一例を示す模式図である。
【図５】図５は、実施の形態における配線支援装置の機能ブロック図である。
【図６】図６は、本実施の形態における最上位の処理フローを示す図である。
【図７】図７は、処理Ｂの処理フローを示す図である。
【図８Ａ】図８Ａは、分離の配置パターンの一例を示す図である。
【図８Ｂ】図８Ｂは、分離の配置パターンが成立していない場合の一例を示す図である。
【図８Ｃ】図８Ｃは、分離の配置パターンが成立しており且つ対向の配置パターンも成立している場合の一例を示す図である。
【図８Ｄ】図８Ｄは、分離の配置パターンが成立しており且つ非対向の配置パターンも成立している場合の一例を示す図である。
【図９】図９は、処理ＢＡの処理フローを示す図である。
【図１０】図１０は、処理Ａの処理フローを示す図である。
【図１１】図１１は、処理ＡＢの処理フローを示す図である。
【図１２】図１２は、最小全域木均等分類処理の処理フローを示す図である。
【図１３】図１３は、信号端子群の一例を示す図である。
【図１４】図１４は、最小全域木の一例を示す図である。
【図１５】図１５は、分類結果の一例を示す図である。
【図１６Ａ】図１６Ａは、グループ１の端子群の一例を示す図である。
【図１６Ｂ】図１６Ｂは、グループ２の端子群の一例を示す図である。
【図１６Ｃ】図１６Ｃは、グループ３の端子群の一例を示す図である。
【図１７】図１７は、円探索均等分類処理の処理フローを示す図である。
【図１８】図１８は、集合Ｓと集合Ｔとの一例を示す図である。
【図１９】図１９は、円探索均等分類処理におけるグループ化を説明するための図である。
【図２０】図２０は、ＸＹ分類処理の処理フローを示す図である。
【図２１】図２１は、第１分類処理の処理フローを示す図である。
【図２２】図２２は、水平角度を算出する方法について説明する図である。
【図２３】図２３は、Ｘ方向範囲とＹ方向範囲を説明するための図である。
【図２４】図２４は、初期的なグループ化の結果の一例を示す図である。
【図２５Ａ】図２５Ａは、前提となる線分の分布を示す図である。
【図２５Ｂ】図２５Ｂは、Ｘ方向グループに属する線分の分布を示す図である。
【図２５Ｃ】図２５Ｃは、Ｙ方向グループに属する線分の分布を示す図である。
【図２６】図２６は、第２分類処理の処理フローを示す図である。
【図２７】図２７は、交差する線分の数の一例を示す図である。
【図２８】図２８は、第２分類処理におけるデータの一例を示す図である。
【図２９】図２９は、第２分類処理におけるデータの一例を示す図である。
【図３０】図３０は、第２分類処理におけるデータの一例を示す図である。
【図３１Ａ】図３１Ａは、Ｘ方向グループに属する線分をさらに分類した結果における第１のグループの一例を示す図である。
【図３１Ｂ】図３１Ｂは、Ｘ方向グループに属する線分をさらに分類した結果における第２のグループの一例を示す図である。
【図３２】図３２は、第２分類処理の処理フローを示す図である。
【図３３】図３３は、第２分類処理の処理結果の一例を示す図である。
【図３４】図３４は、信号交換補正処理の処理フローを示す図である。
【図３５Ａ】図３５Ａは、端子群の第１のグループの一例を示す図である。
【図３５Ｂ】図３５Ｂは、端子群の第２のグループの一例を示す図である。
【図３５Ｃ】図３５Ｃは、端子群の第３のグループの一例を示す図である。
【図３６Ａ】図３６Ａは、端子群の第１のグループについて仮配線を実施した結果の一例を示す図である。
【図３６Ｂ】図３６Ｂは、端子群の第２のグループについて仮配線を実施した結果の一例を示す図である。
【図３６Ｃ】図３６Ｃは、端子群の第３のグループについて仮配線を実施した結果の一例を示す図である。
【図３７】図３７は、交換処理の処理フローを示す図である。
【図３８】図３８は、隣接数の計数方法の一例を示す図である。
【図３９】図３９は、隣接コストの計算方法の一例を示す図である。
【図４０】図４０は、隣接数及び隣接コストの計算の一例を説明するための図である。
【図４１】図４１は、隣接数及び隣接コストの計算の一例を説明するための図である。
【図４２】図４２は、線長ベース分類処理の処理フローを示す図である。
【図４３Ａ】図４３Ａは、マンハッタン長テーブルの一例を示す図である。
【図４３Ｂ】図４３Ｂは、所属ネットテーブルの一例を示す図である。
【図４４】図４４は、線長ベース分類処理の処理フローを示す図である。
【図４５】図４５は、マンハッタン長テーブルの一例を示す図である。
【図４６】図４６は、所属ネットテーブルの一例を示す図である。
【図４７】図４７は、マンハッタン長テーブルの一例を示す図である。
【図４８】図４８は、所属ネットテーブルの一例を示す図である。
【図４９】図４９は、マンハッタン長テーブルの一例を示す図である。
【図５０】図５０は、所属ネットテーブルの一例を示す図である。
【図５１】図５１は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１９】
本技術の実施の形態に係る配線支援装置１００の機能ブロック図を図５に示す。配線支援装置１００は、処理部１１０と、処理すべき信号線などのデータを格納する第１データ格納部１３０と、処理部１１０の処理において途中で生成されるデータを格納する第２データ格納部１４０と、処理部１１０の処理結果を格納する第３データ格納部１５０と、ユーザからの指示を受け付ける入力部１６０とを有する。
【００２０】
また、処理部１１０は、制御部１１１と、円探索均等分類処理を実施する第１分類処理部１１２と、最小全域木均等分類処理を実施する第２分類処理部と、ＸＹ分類処理を実施する第３分類処理部１１４と、信号交換補正処理部１１５と、線長ベース分類処理を実施する第４分類処理部１１６と、仮配線処理部１１７と、交差処理部１１８と、最小全域木処理部１１９と、マンハッタン長処理部１２０とを有する。
【００２１】
第１データ格納部１３０は、配線すべき信号線（ネットとも呼ぶ）の識別子と、当該信号線の始点端子識別子と、当該信号線の終点端子識別子と、始点端子の座標値と、終点端子の座標値とが登録されるようになっている。配線すべき信号線については、例えばユーザにより入力部１６０によって指定された信号線であり、その信号線のデータについては、入力部１６０を介して入力するようにしてもよい。また、ネットワークを介して接続されている他のコンピュータなどから、配線すべき信号線のデータを読み出して、第１データ格納部１３０に格納するようにしてもよい。
【００２２】
次に、図６乃至図５０を用いて配線支援装置１００の処理内容について説明する。
【００２３】
まず、入力部１６０は、ユーザに対して、分割数（グループ数とも呼ぶ）ｎ及びグループ化の目的種別の入力を促し、ユーザからこれらのデータを受け付け、第１データ格納部１３０に格納する（図６：ステップＳ１）。本実施の形態では、目的種別は、Ａ：「線長調整容易性」、Ｂ：「結線容易性」、ＡＢ：「線長調整容易性及び結線容易性であって、それらのうち線長調整容易性を優先」、ＢＡ：「結線容易性及び線長調整容易性であって、それらのうち結線容易性を優先」のいずれかである。
【００２４】
また、入力部１６０は、ユーザに対して、配線すべき信号線のデータの指定を促し、ユーザから入力データを受け付け、第１データ格納部１３０に格納する（ステップＳ３）。上でも述べたように、ファイルなどの形式で、他のコンピュータなど外部から読み込み、第１データ格納部１３０に格納するようにしてもよい。
【００２５】
そして、処理部１００の制御部１１１は、第１データ格納部１３０に格納されている、グループ化の目的種別を読み出して、当該目的種別がＢ：「結線容易性」であるか判断する（ステップＳ５）。目的として結線容易性が指定されている場合には、制御部１１１は、以下で述べる処理Ｂを、以下で述べる処理部に実施させる（ステップＳ７）。
【００２６】
一方、目的種別が「結線容易性」ではない場合には、制御部１１１は、目的種別がＡ：「線長調整容易性」であるか判断する（ステップＳ９）。目的として線長調整容易性が指定されている場合には、制御部１１１は、以下で述べる処理Ａを、以下で述べる処理部に実施させる（ステップＳ１１）。
【００２７】
さらに、目的種別が「線長調整容易性」ではない場合には、制御部１１１は、目的種別がＢＡ：「結線容易性及び線長調整容易性であって、それらのうち結線容易性を優先」であるか判断する（ステップＳ１３）。目的として「結線容易性及び線長調整容易性であって、それらのうち結線容易性を優先」である場合には、制御部１１１は、以下で述べる処理ＢＡを、以下で述べる処理部に実施させる（ステップＳ１７）。
【００２８】
一方、目的種別がＢＡ：「結線容易性及び線長調整容易性であって、それらのうち結線容易性を優先」でない場合には、ＡＢ：「結線容易性及び線長調整容易性であって、それらのうち線長調整容易性を優先」であるので、制御部１１１は、以下で述べる処理ＡＢを、以下で述べる処理に実施させる（ステップＳ１５）。
【００２９】
その後、制御部１１１は、第２データ格納部１４０に格納されている分類結果を、第３データ格納部１５０に格納する（ステップＳ１９）。そして処理を終了する。
【００３０】
このように、第１に目的に応じて処理を切り替えるようになっている。
【００３１】
次に、結線容易性の実現を目的とする場合の分類処理である処理Ｂについて、図７乃至図８Ｄを用いて説明する。
【００３２】
制御部１１１は、第１データ格納部１３０に格納されている始点端子群の座標から当該始点端子群を包含する第１の矩形と、第１データ格納部１３０に格納されている終点端子群の座標から当該終点端子群を包含する第２の矩形とを算出し、矩形の頂点の座標データを例えば第２データ格納部１４０に格納する（図７：ステップＳ２１）。そして、制御部１１１は、第１の矩形と第２の矩形とから、始点端子群及び終点端子群の配置パターンを特定する（ステップＳ２３）。
【００３３】
本実施の形態では、図８Ａに示すように、白丸で示される始点端子群を包含する第１の矩形ａと、黒丸で示される終点端子群を包含する第２の矩形ｂとのいずれの矩形内にも、他方の端子が存在しない「分離」という配置パターンが成立しているかを判断する（ステップＳ２５）。図８Ａの例では、黒丸で示される終点端子群のうち一部の終点端子が第１の矩形ａ内に含まれるが、白丸で示される始点端子群については１つも第２の矩形ｂ内に含まれているないので、「分離」が成立している。一方、図８Ｂに示すように、黒丸で示される終点端子群のうち一部の終点端子が第１の矩形ａ内に含まれており、白丸で示される始点端子群についても第２の矩形ｂ内に含まれているので、「分離」パターンが成立していない。
【００３４】
「分離」パターンが成立している場合には、図８Ｃに示すように、第１の矩形ａと第２の矩形ｂとが交差しない「対向」という配置パターンが成立しているか判断する。一方、図８Ｄに示すように、第１の矩形ａと第２の矩形ｂとが交差している（図８Ｄの例では第２の矩形ｂが第１の矩形ａに包含されている）場合には、「対向」していない「非対向」という配置パターンであると判断する。
【００３５】
制御部１１１は、ステップＳ２３で「分離」の配置パターンに該当しないと特定された場合には（ステップＳ２５：Ｎｏルート）、第３分類処理部１１４にＸＹ分類処理を実施させる（ステップＳ２７）。そして呼び出し元の処理に戻る。ＸＹ分類処理については後に詳細に説明する。
【００３６】
一方、ステップＳ２３で「分離」の配置パターンに該当すると特定された場合には（ステップＳ２５：Ｙｅｓルート）、制御部１１１は、ステップＳ２３で「対向」の配置パターンに該当すると特定されたか判断する（ステップＳ２９）。ステップＳ２３で「対向」パターンに該当すると判断された場合には、制御部１１１は、第２分類処理部１１３に最小全域木均等分類処理を実施させる（ステップＳ３１）。そして呼び出し元の処理に戻る。最小全域木均等分類処理については後に詳細に説明する。
【００３７】
一方、ステップＳ２３で「対向」の配置パターンには該当しないと特定された場合には、制御部１１１は、第１分類処理部１１２に円探索均等分類処理を実施させる（ステップＳ３３）。そして呼び出し元の処理に戻る。円探索均等分類処理については後に詳細に説明する。
【００３８】
このような処理Ｂを実施することで、始点端子群及び終点端子群の配置パターンに応じて、結線しやすいように信号線群がグループ化されるようになる。
【００３９】
次に、結線容易性及び線長調整容易性の実現を目的とするが結線容易性を優先する場合の分類処理である処理ＢＡについて、図９を用いて説明する。
【００４０】
制御部１１１は、第１データ格納部１３０に格納されている始点端子群の座標から当該始点端子群を包含する第１の矩形と、同じく第１データ格納部１３０に格納されている終点端子群の座標から当該終点端子群を包含する第２の矩形とを算出し、矩形の頂点の座標データを例えば第２データ格納部１４０に格納する（図９：ステップＳ４１）。そして、制御部１１１は、第１の矩形と第２の矩形とから、始点端子群及び終点端子群の配置パターンを特定する（ステップＳ４３）。この処理は、ステップＳ２３と同じである。
【００４１】
制御部１１１は、ステップＳ４３で「分離」の配置パターンに該当しないと特定された場合には（ステップＳ４５：Ｎｏルート）、第３分類処理部１１４にＸＹ分類処理を実施させる（ステップＳ４７）。ＸＹ分類処理については後に詳細に説明する。そして、ステップＳ５５に移行する。
【００４２】
一方、ステップＳ４３で「分離」の配置パターンに該当すると特定された場合には（ステップＳ４５：Ｙｅｓルート）、制御部１１１は、ステップＳ４３で「対向」の配置パターンに該当すると特定されたか判断する（ステップＳ４９）。ステップＳ４３で「対向」の配置パターンに該当すると判断された場合には、制御部１１１は、第２分類処理部１１３に最小全域木均等分類処理を実施させる（ステップＳ５１）。そしてステップＳ５５に移行する。最小全域木均等分類処理については後に詳細に説明する。
【００４３】
一方、ステップＳ４３で「対向」の配置パターンには該当しないと特定された場合には、制御部１１１は、第１分類処理部１１２に円探索均等分類処理を実施させる（ステップＳ５３）。そしてステップＳ５５に移行する。円探索均等分類処理については後に詳細に説明する。
【００４４】
ここまでは処理Ｂと同様であるが、ステップＳ４７、Ｓ５１又はＳ５３の後に、制御部１１１は、信号交換補正処理部１１５に、信号交換補正処理を実施させる（ステップＳ５５）。そして呼び出し元の処理に戻る。信号交換補正処理については後に詳細に説明する。
【００４５】
このような処理ＢＡを実施することで、処理Ｂと同様に、始点端子群及び終点端子群の配置パターンに応じて、結線しやすいように信号線群がグループ化されるようになる。さらに、以下に詳細に述べる信号交換補正処理を実施するため、配線すべき信号線群における最大線長もある程度短くなるため、等長線長条件を遵守するための線長調整工程がある程度軽減される。
【００４６】
次に、線長調整容易性の実現を目的とする場合の分類処理である処理Ａについて、図１０を用いて説明する。
【００４７】
制御部１１１は、第４分類処理部１１６に対して、線長ベース分類処理を実施させる（ステップＳ５７）。そして呼び出し元の処理に戻る。線長ベース分類処理については後に詳細に説明する。
【００４８】
このような処理を実施することで、以下で述べるように、各グループにおいて、最大線長を短縮するように信号群がグループ化される。すなわち、等長線長条件を遵守するための線長調整工程の困難性が軽減される。
【００４９】
次に、線長調整容易性及び結線容易性の実現を目的とするが線長調整容易性を優先する場合の分類処理である処理ＡＢについて、図１１を用いて説明する。
【００５０】
制御部１１１は、第４分類処理部１１６に対して、線長ベース分類処理を実施させる（ステップＳ６１）。線長ベース分類処理については後に詳細に説明する。その後、制御部１１１は、信号交換補正処理部１１５に、信号交換補正処理を実施させる（ステップＳ６３）。そして呼び出し元の処理に戻る。信号交換補正処理については後に詳細に説明する。
【００５１】
このような処理を実施することで、以下で述べるように、各グループにおいて、最大線長を短縮するように信号群がグループ化される。すなわち、等長線長条件を遵守するための線長調整工程の困難性が軽減される。さらに、以下に詳細に述べる信号交換補正処理を実施するため、配線スペースがある程度確保され、結線容易性もある程度確保される。
【００５２】
以上のように、ユーザから指定された目的と、配線すべき信号線群の始点端子群及び終点端子群の配置パターンとに応じて、適切な分類処理が実施され、目的に応じた適切な信号線の分類がなされるようになる。
【００５３】
次に、各グループについて端子が可能な限り均等に分布するようにグループ化する最小全域木均等分類処理について、図１２乃至図１６を用いて説明する。第２分類処理部１１３は、第２データ格納部１４０に格納されている、矩形のデータに基づき第１の矩形の面積と第２の矩形の面積とを比較して、面積が小さい方の信号端子の集合を集合Ｓとして特定する（図１２：ステップＳ７１）。具体的には、面積が小さい方の信号端子の座標データを第１データ格納部１３０から読み出す。
【００５４】
そして、第２分類処理部１１３は、最小全域木処理部１１９に、集合Ｓについて最小全域木を生成させ、最小全域木のデータを第２データ格納部１４０に格納する（ステップＳ７３）。例えば図１３に黒丸で示されるような信号端子が集合Ｓとして特定されたとすると、図１４に示すような最小全域木が生成される。なお、図１４に示す番号は、ステップＳ７３の段階では特定されていない。なお、最小全域木の生成アルゴリズムについてはよく知られているので、ここでは述べない。
【００５５】
次に、第２分類処理部１１３（又は最小全域木処理部１１９）は、生成した最小全域木に対して深さ優先探索を実施することで、各信号端子に分割数ｎまでの番号を付与する（ステップＳ７５）。深さ優先探索についてはよく知られているのでこれ以上述べない。深さ優先探索を実施すると、図１４に示したように、各信号端子に対して１乃至分割数ｎの番号が付与される。この番号がグループの番号になる。
【００５６】
そして、第２分類処理部１１３は、集合Ｓに含まれる端子の信号線識別子を第１データ格納部１３０から特定し、信号端子にステップＳ７５で付与された番号とを、対応付けて第３データ格納部１５０に格納する（ステップＳ７７）。例えば、図１５に示すようなデータが格納される。図１５の例では、信号線の識別子と、グループ番号とが対応付けて格納される。
【００５７】
図１４に示すように、深さ優先探索で番号を付与すると、比較的隣接する信号端子には異なる番号が付与されるようになるため、端子位置がほぼ均等に分散するようにグループ分けが行われるようになる。すなわち、結線容易性が担保されるようになる。図１３の例では、図１６Ａは番号「１」のグループを表しており、図１６Ｂは番号「２」のグループを表しており、図１６Ｃは番号「３」のグループを表している。このように、端子位置がほぼ均等に分散するようになっていることが分かる。
【００５８】
なお、深さ優先探索ではなく、幅優先選択や最下層幅優先探索などを採用する場合もある。
【００５９】
次に、各グループについて端子が可能な限り均等に分布するようにグループ化する第２の手法である円探索均等分類処理について、図１７乃至図１９を用いて説明する。
【００６０】
第１分類処理部１１２は、第２データ格納部１４０に格納されている矩形のデータに基づき、第１の矩形と第２の矩形のうち、一方が他方を包含している場合には他方の矩形の信号端子の集合を、交差している場合には面積が小さい方の矩形の信号端子の集合を集合Ｓに設定し、残余の信号端子の集合を集合Ｔに設定する（図１７：ステップＳ８１）。具体的には、集合Ｓの信号端子のデータを、第１データ格納部１３０から読み出し、集合Ｔの信号端子のデータを、第１データ格納部１３０から読み出す。
【００６１】
図１８に示すように、白丸の始点端子群の矩形が、黒丸の終点端子群の矩形に包含される場合には、始点端子群が集合Ｓに設定され、黒丸の終点端子群が集合Ｔに設定される。
【００６２】
そして、第１分類処理部１１２は、集合Ｓの矩形の中心座標Ｃを算出し、第２データ格納部１４０に格納する（ステップＳ８３）。図１８の例では、矩形Ｓの中心座標を算出する。そして、第１分類処理部１１２は、中心座標Ｃから、集合Ｔの各信号端子との距離を算出し、距離が大きい順に分割数ｎまでの番号を順に付与する（ステップＳ８５）。
【００６３】
図１８の例では、図１９に示すように、矩形Ｓの中心（星印）からの距離が最も大きい信号端子ｔ１、次に距離が大きい信号端子ｔ２、さらに次に距離が大きい信号端子ｔ３の順で、分割数１乃至ｎの番号が付与される。ｔ１には「１」が付与され、ｔ２には「２」が付与され、ｔ３には「３」が付与される。
【００６４】
その後、第１分類処理部１１２は、集合Ｔに含まれる端子の信号線識別子を第１データ格納部１３０から特定し、信号端子にステップＳ８５で付与された番号とを、対応付けて第３データ格納部１５０に格納する（ステップＳ８７）。例えば、図１５に示すようなデータが格納される。
【００６５】
このように、第１の矩形と第２の矩形とのうち面積の小さい矩形の中心からの距離が大きい順に、各グループに均等に分散するように信号端子をグループ化することで、信号線のグループ化を行っている。これによって、図８Ｄのような分離はしているが対向していない配置パターンにおいて、均等に分散するようにグループ化を行うことができるようになる。
【００６６】
次に、同一グループにおける始点端子と終点端子とをつなぐ線分の交差を削減することで結線容易性を担保するための処理であるＸＹ分類処理について図２０乃至図３３を用いて説明する。
【００６７】
まず、第３分類処理部１１４は、第１分類処理を実施する（図２０：ステップＳ９１）。第１分類処理については、図２１乃至図２５Ｃを用いて説明する。
【００６８】
第３分類処理部１１４は、第１データ格納部１３０に格納されているデータに含まれる信号線のうち、未処理の信号線を１つ特定する（図２１：ステップＳ１１１）。そして、第３分類処理部１１４は、特定された信号線の始点と終点とを結ぶ線分の水平角度を算出し、例えば第２データ格納部１４０に格納する（ステップＳ１１３）。例えば図２２に示したように、始点（白丸）から終点（黒丸）までの線分とＸ軸との角度θを算出する。
【００６９】
そして、第３分類処理部１１４は、ステップＳ１１３で算出した水平角度がＸ方向の範囲内であるかを判断する（ステップＳ１１５）。本実施の形態では、図２３に示すように、Ｘ軸に平行で原点を通過する直線を原点を中心に＋４５°回転させた直線と−４５°回転させた直線とで囲まれる範囲（すなわちＸ軸を囲む範囲）をＸ方向の範囲とする。それ以外はＹ方向の範囲とする。
【００７０】
水平角度がＸ方向の範囲内であれば、第３分類処理部１１４は、特定された信号線をＸ方向グループ（Ｄｘ）に登録する（ステップＳ１１９）。そして、ステップＳ１２１に移行する。一方、水平角度がＹ方向の範囲内であれば、第３分類処理部１１４は、特定された信号線をＹ方向グループ（Ｄｙ）に登録する（ステップＳ１１７）。そして、ステップＳ１２１に移行する。例えば、第２データ格納部１４０には、図２４に示すようなリストが登録される。図２４の例では、Ｄｘの列には、Ｘ方向グループの信号線の識別子が列挙され、Ｄｙの列には、Ｙ方向グループの信号線の識別子が列挙される。
【００７１】
その後、第３分類処理部１１４は、第１データ格納部１３０に格納されているデータに含まれる信号線のうち、未処理の信号線が存在しているか判断する（ステップＳ１２１）。未処理の信号線が存在する場合にはステップＳ１１１に戻る。一方、未処理の信号線が存在しない場合には、呼び出し元の処理に戻る。
【００７２】
なお、図２５Ａに示すような、始点（白丸）から終点（黒丸）までの線分の分布がある場合、第１分類処理では、図２５Ｂに示すようなＸ方向グループと、図２５Ｃに示すようなＹ方向グループとに分けられる。
【００７３】
図２０の処理の説明に戻って、第３分類処理部１１４は、ユーザに指定された分割数ｎが２であるか判断する（ステップＳ９３）。分割数ｎが２であれば、これ以上分類はしないので、ステップＳ１０５に移行する。一方、分割数ｎが３以上であれば、第３分類処理部１１４は、分割グループ数＝２に設定し（ステップＳ９５）、第２分類処理を実施する（ステップＳ９７）。第２分類処理については図２６乃至図３３を用いて説明する。
【００７４】
まず、第３分類処理部１１４は、現在のグループ毎に、交差する線分の数を、交差処理部１１８に算出させ、第２データ格納部１４０に格納させる（図２６：ステップＳ１３１）。例えば図２５Ｂ及び図２５Ｃからすると、図２７に示すように、Ｘ方向グループＤｘについては交差する線分の数６が得られ、Ｙ方向グループＤｙについては交差する線分の数４が得られ、第２データ格納部１４０に格納される。
【００７５】
そして、第３分類処理部１１４は、交差する線分の数が最大のグループを特定する（ステップＳ１３３）。その後、第３分類処理部１１４は、特定されたグループに属する線分について、分割予定グループを「未決定」に設定する（ステップＳ１３５）。例えば図２８に示すようなデータを第２データ格納部１４０に用意する。
【００７６】
そして、第３分類処理部１１４は、分割予定グループが「未決定」の全ての線分の各々について、分割予定グループが「未決定」又は「Ａ」（繰り返しの中で「Ａ」が設定されるので、最初は「Ａ」は存在しない）に属する他の線分との交差数を交差処理部１１８に算出させ、交差数最大値Ｃmaxである線分を線分Ｌmaxとして特定する（ステップＳ１３７）。図２５Ｂの例では、線分１６５１乃至１６５４が交差数「２」で特定され、Ｃmax＝２となる。但し、図２５Ｂの例では、線分１６５２乃至１６５４は互いに交差している。
【００７７】
その後、第３分類処理部１１４は、Ｃmax＝０であるか判断する（ステップＳ１３９）。交差がない場合には、これ以上処理ができないので、第３分類処理部１１４は、第２データ格納部１４０において分割予定グループが「未決定」の線分に対して、分割予定グループ「Ａ」を設定する（ステップＳ１４１）。そして処理は端子Ａを介して図３２の処理に移行する。
【００７８】
一方、Ｃmax＝０ではなく１以上である場合には、第３分類処理部１１４は、線分Ｌmaxに分割予定グループ「Ａｂ」を設定し、線分Ｌmaxと交差し且つ分割予定グループ「未決定」の線分に分割予定グループ「Ａ」を設定する（ステップＳ１４３）。その後、端子Ａを介して図３２の処理に移行する。「Ａ」と「Ａｂ」は、グループ分けを識別するための便宜上の識別子であって、他の識別子を用いてもよい。
【００７９】
例えば、図２５Ｂの例で、線分１６５１をＬmaxとすると、分割予定グループ「Ａｂ」が設定され、線分１６５１に交差する線分１６７１及び１６７２には分割予定グループ「Ａ」が設定される。また、線分１６５２をＬmaxとすると、分割予定グループ「Ａｂ」が設定される。線分１６５２に交差する線分１６５３及び１６５４は、交差数「２」でＬmaxでもある。しかし、このように互いに交差している線分について同じ分割予定グループ「Ａｂ」を設定すると、交差数を減らすことができないので、Ｌmaxについては１つずつ処理することで、線分１６５２に分割予定グループ「Ａｂ」を設定し、これに交差する線分１６５３及び１６５４については分割予定グループ「Ａ」を設定して、同一分割予定グループに分類されないようにする。すなわち、第２データ格納部１４０に格納されるデータは、図２９の状態から、図３０の状態に更新される。図２５Ｂにおける線分の配置状態は、図３１Ａの分割予定グループ「Ａ」の状態と、図３１Ｂの分割予定グループ「Ａｂ」の状態とに分けられる。これによって、分割予定グループ「Ａ」では最大交差数Ｃmaxは「１」になり、分割予定グループ「Ａｂ」では最大交差数Ｃmaxは「０」となる。
【００８０】
図３２の処理の説明に移行して、第３分類処理部１１４は、分割予定グループ「未決定」の線分が残っているのか判断する（ステップＳ１４５）。分割予定グループ「未決定」の線分が残っている場合には端子Ｂを介してステップＳ１３７に戻る。一方、分割予定グループ「未決定」の線分が残っていなければ、第３分類処理部１１４は、分割予定グループ「Ａ」及び「Ａｂ」についての分類結果を、次の第２分類処理のために第２データ格納部１４０に格納する（ステップＳ１４７）。そして呼び出し元の処理に戻る。
【００８１】
上で述べた例では、Ｙ方向グループと、分割予定グループ「Ａ」及び「Ａｂ」とが、次のステップＳ１３１での現在のグループとなるので、例えば図３３に示すようなデータを生成して第２データ格納部１４０に格納する。図３３の例では、分割予定グループ「Ａ」に属する信号識別子のリストと、分割予定グループ「Ａｂ」に属する信号識別子のリストと、Ｙ方向グループＤｙに属する信号識別子のリストとが格納される。
【００８２】
図２０の処理の説明に戻って、第３分類処理部１１４は、第２分類処理においてグループ分割ができたか判断する（ステップＳ９９）。はじめから交差がない、すなわちＣmax＝０であればグループ分割が行われない。従って、グループ分割が行われなかった場合にはステップＳ１０５に移行する。一方、グループ分割が行われた場合には、第３分類処理部１１４は、分割グループ数＝分割グループ数＋１を算出し（ステップＳ１０１）、分割グループ数＝分割数ｎになったか判断する（ステップＳ１０３）。まだ、分割グループ数＝分割数ｎになっていない場合にはステップＳ９７に戻る。一方、分割グループ数＝分割数ｎになった場合には、ステップＳ１０５に移行する。
【００８３】
ステップＳ１０５では、第３分類処理部１１４は、分類処理に基づき、端子の信号識別子と、当該端子に対応するグループ識別子と対応付けて格納する（ステップＳ１０５）。グループ識別子については、番号に直して設定するようにしてもよい。
【００８４】
このように交差を削減するようにグループ化することで、結線容易性を高めることができるようになる。
【００８５】
次に、線長を短縮するための信号交換補正処理について図３４乃至図４１を用いて説明する。まず、信号交換補正処理部１１５は、マンハッタン長処理部１２０に対して、全ての信号線についてマンハッタン長を算出させ、そのうち最も長いマンハッタン長のｋ（例えば１．１）倍を、目標線長に設定する（図３４：ステップＳ１５１）。マンハッタン長についての算出方法はよく知られているので、ここでは述べない。
【００８６】
そして、信号交換補正処理部１１５は、仮配線処理部１１７に、現在の仮配線データ（初期的にはなし）をクリアさせる（ステップＳ１５３）。そして、信号交換補正処理部１１５は、仮配線処理部１１７に、グループ毎に、仮配線を実施させる（ステップＳ１５５）。仮配線のデータ（信号線の識別子、仮配線の図形データ、仮配線長など）については、第２データ格納部１４０に格納される。
【００８７】
例えば、図３５Ａ乃至図３５Ｃのような３つのグループ（但し、始点端子群のみを示す）に分けられているものとする。このような状態で、例えば仮配線を実施すると、図３５Ａのグループについては図３６Ａに示すような仮配線が実施され、図３５Ｂのグループについては図３６Ｂに示すような仮配線が実施され、図３５Ｃのグループについては図３６Ｃに示すような仮配線が実施される。
【００８８】
信号交換補正処理部１１５は、第２データ格納部１４０に格納されている仮配線長のデータから、最も長い仮配線の信号識別子及び所属グループ、並びに仮配線長を特定し、最も長い仮配線長＞目標線長が成立しているか判断する（ステップＳ１５７）。例えば図３６Ａにおいて丸で示す始点端子から伸びる仮配線１７０１が、最も長い仮配線長の信号線として特定されたものとする。
【００８９】
最も長い仮配線長が目標線長以下である場合には、以下の処理を行わずとも配線長が短くなっていると判断できるので、呼び出し元の処理に戻る。
【００９０】
一方、最も長い仮配線長＞目的線長が成立している場合には、信号交換補正処理部１１５は、交換処理を実施する（ステップＳ１５９）。交換処理については、図３７乃至図４１を用いて説明する。
【００９１】
まず、信号交換補正処理部１１５は、最も長い仮配線の信号線が属するグループとは異なるグループの未処理の信号線を１つ特定する（図３７：ステップＳ１７１）。例えば図３６Ｂにおいて、信号端子３６１から順番に、信号端子３６２、３６３、３６４、３６５、３６６といったように選択してゆく。そして、信号交換補正処理部１１５は、最も長い仮配線長の信号線と、特定された信号線とを交換する前と後の隣接数又は隣接コストを算出し、第２データ格納部１４０に格納する（ステップＳ１７３）。
【００９２】
隣接数を算出する場合には、例えば図３８に示すように、注目信号端子（二重丸）から所定の距離Ｄに含まれる信号端子（黒丸）を特定する。そして、単純に、特定された信号端子の数を計数するようにしてもよい。一方、図３９に示すように、端子が整列配置されている場合には、注目信号端子（二重丸）の縦横隣接した信号端子（黒丸）の数を計数するようにしてもよい。但し、単純な信号端子数ではなく、縦横隣接の場合にはコスト１とし、斜め隣接の場合にはコスト０．５として加算するようにしてもよい。
【００９３】
例えば、図４０に示すように、注目信号端子１７１１の場合には、両横と下に隣接端子が存在しているので、隣接数は「３」で、隣接コストも「３」となる。一方、注目信号端子１７１２の場合には、上と斜め左下に隣接端子が存在しているので、隣接数は「１」であり、隣接コストは「１．５」となる。なお、斜め隣接のコストについては０．５ではなく他の値を採用するようにしてもよい。
【００９４】
より具体的に、図４１に示すように、グループＧ１の信号端子１７２１を、グループＧ２に移動させ、仮に信号端子１７２２の位置（すなわち異なる層の同一位置）に配置するものとする。代わりに、グループＧ２の信号端子１７３１を、グループＧ１に移動させ、仮に信号端子１７３２の位置（すなわち異なる層の同一位置）に配置するものとする。そうすると、丸で囲まれた交換前では、信号端子１７２１についての隣接数は「０」、隣接コストは「０．５」と算出され、矢印の先の交換後では、信号端子１７２２についての隣接数は「０」、隣接コストは「０．５」と算出される。すなわち、交換前後で変化なしということになる。一方、丸で囲まれた交換前では、信号端子１７３１についての隣接数は「０」、隣接コストは「０」と算出され、矢印の先の交換後では、信号端子１７３２についての隣接数は「０」、隣接コスト「１．０」と算出される。すなわち、交換前後で、隣接数は変化していないが、隣接コストは「＋１．０」となっている。なお、単層配線を行うので、始点端子又は終点端子のみではなく、両方の端子について隣接数又は隣接コストを算出する。
【００９５】
そして、信号交換補正処理部１１５は、ステップＳ１７３で算出された隣接数又は隣接コストが条件を満たしているか判断する（ステップＳ１７５）。例えば、交換前後で隣接数が増加していないという条件、交換前後で隣接コストが増加していないという条件を満たしているか判断する。なお両方を満たすような条件設定がなされる場合もある。
【００９６】
ステップＳ１７３で算出された隣接数又は隣接コストが条件を満たしていない場合にはステップＳ１８３に移行する。一方、ステップＳ１７３で算出された隣接数又は隣接コストが条件を満たしている場合には、信号交換補正処理部１１５は、最も長い仮配線長の信号線が属するグループと、ステップＳ１７１で特定された信号線のグループとで、交換を実施した後の状態について、仮配線処理部１１７に対して仮配線を実施させ、仮配線のデータ（信号線の識別子、仮配線の図形データ、仮配線長など）を第２データ格納部１４０に格納させる（ステップＳ１７７）。
【００９７】
そして、信号交換補正処理部１１５は、最も長い仮配線長の信号線が属するグループ及びステップＳ１７１で特定された信号線のグループの各グループについて、最も長い仮配線長が増加したか判断する（ステップＳ１７９）。各グループについて、最も長い仮配線長が増加していない場合には、交換可能であると判断して、信号交換補正処理部１１５は、所属グループの交換を第２データ格納部１４０に登録する（ステップＳ１８１）。具体的には、ステップＳ１５５で特定された最も長い仮配線長の信号線の所属グループを、ステップＳ１７１で特定された信号線のグループに変更し、ステップＳ１７１で特定された信号線のグループを、ステップＳ１５５で特定された最も長い仮配線長の信号線の所属グループに変更する。そして呼び出し元の処理に戻る。
【００９８】
一方、最も長い仮配線長が増加している場合には、交換不可能であると判断して、信号交換補正処理部１１５は、未処理の信号線が存在しているか判断する（ステップＳ１８３）。未処理の信号線が存在している場合にはステップＳ１７１に戻る。一方、未処理の信号線が存在しない場合には、呼び出し元の処理に戻る。
【００９９】
このようにすれば、最も長い仮配線長が短くなるように所属グループを変更することができるようになる。最も長い仮配線長が短くなるというのは、線長調整容易性及び結線容易性のいずれにも効果的である。
【０１００】
図３４の処理の説明に戻って、信号交換補正処理部１１５は、信号線の交換が行われたか判断する（ステップＳ１６１）。信号線の交換が行われた場合にはステップＳ１５３に戻る。すなわち、交換後の状態で、最も長い仮配線長が目標線長以下になっているかを確認する。なお、影響のあるグループについてはステップＳ１５９で仮配線を再度実施しているのでステップＳ１５７に戻るようにしてもよい。一方、信号線の交換が行われていない場合には、これ以上の調整は不可能なので処理を終了し、呼び出し元の処理に戻る。
【０１０１】
以上のような処理を実施することで、最も長い仮配線長を短縮するような分類の補正を行うことができ、線長調整容易性及び結線容易性の向上が行われる。
【０１０２】
次に、複数のグループ間で線長の分布の偏りを抑えつつ最長線長が短縮されるようにグループ化を行うための線長ベース分類処理について、図４２乃至図５０を用いて説明する。
【０１０３】
第４分類処理部１１６は、マンハッタン長処理部１２０に、各信号線について、マンハッタン長及び目標線長（例えばマンハッタン長×ｋ（＝１．１））を算出させ、長い順にソートした後、第２データ格納部１４０におけるマンハッタン長テーブルに登録する（図４２：ステップＳ２０１）。例えば、図４３Ａに示すようなマンハッタン長テーブルが生成されたものとする。図４３Ａの例では、信号線識別子と、マンハッタン長と、目標線長と、仮配線長と、分割予定グループとが登録されるようになっている。仮配線長と分割予定グループとについては、現段階では登録されない。また、マンハッタン長が長い順に信号線はソートされている。
【０１０４】
次に、第４分類処理部１１６は、分割数ｎ個のグループの各々について信号線数を登録するための所属ネットテーブルを生成し、第２データ格納部１４０に格納する（ステップＳ２０３）。図４３Ｂのような所属ネットテーブルが生成される。図４３Ｂの例では、グループＡ、グループＢ及ぶグループＣについて、割当予定信号線数を登録するようになっている。
【０１０５】
そして、第４分類処理部１１６は、所属ネットテーブルのレコードを割当予定信号線数の少ない順にソートする（ステップＳ２０５）。最初は全てのグループについて割当予定信号線数は０であるので、図４３Ｂの状態から変化しない。このようにすれば、できるだけ各グループに均等に信号線を割り当てることができるようになる。
【０１０６】
その後、第４分類処理部１１６は、分割予定グループが未決定で且つ最上位である信号線Ｘを、マンハッタン長テーブルから特定する（ステップＳ２０７）。図４３Ａの例では、最初に、先頭のレコードに含まれる信号線「１」が特定される。
【０１０７】
そして、第４分類処理部１１６は、カウンタｉを１に初期化して（ステップＳ２０９）、ソート後の所属ネットテーブルにおけるｉ番目のグループＧを特定する（ステップＳ２１１）。図４３Ｂの例では、ｉ＝１であればグループ「Ａ」が特定される。
【０１０８】
その後、第４分類処理部１１６は、仮配線処理部１１７に、グループＧの層において信号線Ｘを含む仮配線を実施させ、信号線Ｘの仮配線長ＶＬを算出させ、第２データ格納部１４０におけるマンハッタン長テーブルに登録させる（ステップＳ２１３）。最初は、まだグループＧに所属するとされる信号線はないので、信号線Ｘのみについて仮配線が実施される。次回以降は、グループＧに所属するとされる他の信号線とともに仮配線が行われる。このように、マンハッタン長が長い信号線から順番に仮配線を行えば、仮配線を阻害する他の信号線が少ないため、仮配線長が短くなるということが期待される。すなわち、仮配線長の最大値を小さくすることができるようになる。処理は端子Ｃを介して図４４の処理に移行する。
【０１０９】
そして、第４分類処理部１１６は、ステップＳ２１３で算出された仮配線長ＶＬ＞信号線Ｘの目標線長ＴＬという条件が成立しているか判断する（ステップＳ２１５）。仮配線長ＶＬ＞目標線長ＴＬという条件が成立している場合には、グループＧに信号線Ｘを割り当てても仮配線長ＶＬが目標線長ＴＬよりも長くなってしまうので、他のグループに割り当てることを試みる。すなわち、第４分類処理部１１６は、カウンタｉを１インクリメントして（ステップＳ２１７）、カウンタｉの値が分割数ｎを超えたか判断する（ステップＳ２１９）。なお、この際にはステップＳ２１３で生成された仮配線のデータをもクリアする。カウンタｉの値が分割数ｎ以下であれば、端子Ｄを介してステップＳ２１１に戻る。
【０１１０】
一方、カウンタｉの値が分割数ｎを超えていれば、第４分類処理部１１６は、マンハッタン長から目標線長ＴＬを算出する際に用いる係数ｋの値を増加させる（ステップＳ２２１）。例えば、ｋ＝ｋ＋０．１を算出する。これは、現在の前提ではグループ分けができないということであるため、目標線長ＴＬを変更するためである。そして、処理は端子Ｅを介して図４２のステップＳ２０１に戻る。再度処理をやり直すためである。
【０１１１】
一方、ステップＳ２１５で、仮配線長ＶＬが信号線Ｘの目標線長ＴＬ以下であれば、第４分類処理部１１６は、信号線Ｘについてマンハッタン長テーブルにおいて割当予定グループとしてグループＧを設定し、所属ネットテーブルにおいてグループＧの割当予定信号数を１インクリメントする（ステップＳ２２５）。
【０１１２】
例えば、信号線識別子「１」の信号線Ｘについて、仮配線長ＶＬ＝８０．０６０ｍｍで、目標線長ＴＬ＝８３．６００ｍｍであれば、仮配線長ＶＬが目標線長ＴＬ以下であるので、図４５に示すように、分割予定グループとして「Ａ」が登録される。さらに、図４６に示すように、所属ネットテーブルにおいてグループＡの割当予定信号数も「１」に更新される。
【０１１３】
その後、第４分類処理部１１６は、マンハッタン長テーブルにおいて全ての信号線について分割予定グループが設定されたか判断する（ステップＳ２２７）。分割予定グループが未設定の信号線が存在している場合には、端子Ｆを介して図４２のステップＳ２０５に戻る。
【０１１４】
上で述べた例では、図４７に示すように、マンハッタン長テーブルにおいて２番目のレコードの信号線「４」が信号線Ｘに設定される。また、所属ネットテーブルのレコードをソートして、図４８に示すようにグループＢが先頭になる。すなわち、グループＢ、グループＣ、グループＡの順番で信号線「４」の割り当てを試みることになる。
【０１１５】
一方、ステップＳ２２７で、全ての信号線について分割予定グループが設定された場合には、第４分類処理部１１６は、マンハッタン長テーブルに従って、信号線識別子とグループの識別子との対応付けを第２データ格納部１４０に格納する（ステップＳ２２９）。例えばグループ毎に、所属信号線のリストを生成して格納する。
【０１１６】
その後上で述べた処理を繰り返せば、最終的にマンハッタン長テーブルは、図４９に示すような状態になる。また、所属ネットテーブルは、図５０に示すような状態になる。上でも述べたように、マンハッタン長が長い順に、割当予定信号数が少ないグループに信号線を割り当てることになっている。すなわち、複数のグループ間で線長の分布及び信号線の数の偏りを抑えつつ最長線長が短縮されるようにグループ化がなされるようになる。
【０１１７】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、図５に示した配線支援装置１００の機能ブロック図は一例であって、必ずしも実際のプログラムモジュール構成とは一致しない場合もある。また、処理フローについても、処理結果が変わらない限り、ステップの順番を入れ替えたり、並列に実行するようにしてもよい。データの保持方法についても、上で述べた方法は一例であって、他の方法を用いるようにしてもよい。
【０１１８】
上では１台のコンピュータ配線支援装置１００を構成する例を示したが、複数のコンピュータで構成するようにしてもよい。さらに、スタンドアロン型システムであってもよいし、クライアント−サーバ型システムを構築するようにしてもよい。すなわち、クライアント端末からの要求に応じてサーバが上で述べたような処理を実施する。
【０１１９】
なお、上で述べた配線支援装置１００は、コンピュータ装置であって、図５１に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１２０】
以上述べた本実施の形態をまとめると、以下のようになる。
【０１２１】
本実施の形態にかかる、配線すべき複数の信号線を複数のグループに分けるための配線支援方法は、（Ａ）複数の信号線の線長調整容易性と結線容易性とのうちいずれか又は線長調整容易性及び結線容易性を含み且ついずれを優先させるかの指定を、ユーザから複数の信号線のグループ化の条件として受け付けるステップと、（Ｂ）指定されたグループ化の条件と、データ格納部に格納されている複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、複数の信号線のグループ化の処理を切り替えて実施する実施ステップとを含む。
【０１２２】
これによってユーザが指定した配線の目的に応じて信号線を適切にグループ化することができる。具体的には、単層配線を複数の層で実施する際に、線長調整容易性を求めるケース、結線容易性を求めるケース、両方を求めるが線長調整容易性を優先して求めるケース、両方を求めるが結線容易性を優先して求めるケースのいずれかと、配線すべき信号線の始点端子群と終点端子群との配置パターンとに応じて、グループ化アルゴリズムを切り替えるため、適切にグループ化を行うことができるようになる。
【０１２３】
また、上で述べた実施ステップが、（Ｂ１）グループ化の条件が結線容易性の指定と結線容易性を優先させる指定とのいずれかである場合には、複数の信号線の始点端子群と終点端子群との配置パターンに基づき、結線容易性を担保するためのグループ化処理を切り替えて実施する第１処理ステップと、（Ｂ２）グループ化の条件が線長調整容易性の指定と線長調整容易性を優先させる指定とのいずれかである場合には、複数のグループ間で線長の分布の偏りを抑えつつ最長線長が短縮されるようにグループ化処理を実施する第２処理ステップとを含むようにしてもよい。線長調整容易性の指定又は線長調整容易性を優先させる指定の場合には、配線すべき信号線の始点端子群と終点端子群との配置パターンに拘わらず、上で述べたようなグループ化処理を実施することで、線長調整容易性を担保して、信号線を適切にグループ化することができる。
【０１２４】
なお、上で述べた配置パターンが、（Ｐ１）始点端子群を包含する第１の矩形と終点端子群を包含する第２の矩形とのいずれかに他方の矩形に包含される端子が存在するという第１のパターンと、（Ｐ２）第１の矩形と第２の矩形とのいずれかに他方の矩形に包含される端子が存在せず且つ第１の矩形と前記第２の矩形とが交差する第２のパターンと、（Ｐ３）第１の矩形と第２の矩形とのいずれかに他方の矩形に包含される端子が存在せず且つ第１の矩形と第２の矩形とが交差しない第３のパターンとを含むようにしてもよい。その場合、上で述べた第１処理ステップが、（Ｂ１１）第３のパターンの場合には、第１の矩形と第２の矩形とのうち面積が小さい方の矩形に含まれる端子の位置が、複数のグループの各々に均等に分散するように、複数の信号線を分類するための処理を実施するステップと、（Ｂ１２）第２のパターンの場合には、第１の矩形と第２の矩形とのうち面積が小さいの方の矩形の中心から他方の矩形に含まれる端子までの距離が長い順に複数のグループの各々に均等に分散するように、複数の信号線を分類するための処理を実施するステップと、（Ｂ１３）第１のパターンの場合には、始点端子群と終点端子群とを結ぶ線分の方向及び当該線分の交差状態に基づき、複数の信号線を分類するための処理を実施するステップとを含むようにしてもよい。配置パターンによって実際に行われる配線の状態が異なるため、このような場合分けがなされる。
【０１２５】
また、上で述べた配線支援方法は、（Ｃ）指定されたグループ化の条件が線長調整容易性及び結線容易性のうちいずれを優先させるかの指定を含む場合には、仮配線を実施して最長の仮配線長となった信号線を、当該信号線の所属グループ及び交換対象のグループにおける仮配線長及び端子の隣接関係が所定の条件（例えば信号線の交換が悪影響を与えないという条件）を満たす、交換対象のグループの信号線と交換する処理を実施するステップをさらに含むようにしてもよい。このような処理によれば、仮配線長が短くなり、配線領域を削減するように信号線の交換が行われるので、線長調整容易性を優先する場合には結線容易性を向上させ、結線容易性を優先させる場合には線長調整容易性を向上させることができる。
【０１２６】
なお、上で述べたような処理をコンピュータに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭなどの光ディスク、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
【０１２７】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１２８】
（付記１）
配線すべき複数の信号線を複数のグループに分けるためのプログラムであって、
コンピュータに、
ユーザから、前記複数の信号線のグループ化の条件の指定を受け付けるステップと、
指定された前記グループ化の条件と、データ格納部に格納されている前記複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、前記複数の信号線のグループ化の処理を切り替えて実施する実施ステップと、
を実行させるためのプログラム。
【０１２９】
（付記２）
前記グループ化の条件が、第１の要件と第２の要件とのうちいずれか、又は第１の要件及び第２の要件を含み且ついずれかを優先させるかを含み、
前記実施ステップが、
前記グループ化の条件が前記第１の要件の指定と前記第１の要件を優先させる指定とのいずれかである場合には、前記複数の信号線の始点端子群と終点端子群との配置パターンに基づき、前記第１の要件を担保するためのグループ化処理を切り替えて実施する第１処理ステップと、
前記グループ化の条件が前記第２の要件の指定と前記第２の要件を優先させる指定とのいずれかである場合には、前記複数のグループ間で線長の分布の偏りを抑えつつ最長線長が短縮されるようにグループ化処理を実施する第２処理ステップと、
を含む付記１記載のプログラム。
【０１３０】
（付記３）
前記配置パターンが、
前記始点端子群を包含する第１の矩形と前記終点端子群を包含する第２の矩形とのいずれかに他方の矩形に包含される端子が存在するという第１のパターンと、
前記第１の矩形と前記第２の矩形とのいずれかに他方の矩形に包含される端子が存在せず且つ前記第１の矩形と前記第２の矩形とが交差する第２のパターンと、
前記第１の矩形と前記第２の矩形とのいずれかに他方の矩形に包含される端子が存在せず且つ前記第１の矩形と前記第２の矩形とが交差しない第３のパターンと、
を含み、
前記第１処理ステップが、
前記第１のパターンの場合には、前記始点端子群と前記終点端子群とを結ぶ線分の方向及び当該線分の交差状態に基づき、前記複数の信号線を分類するための処理を実施するステップと、
前記第２のパターンの場合には、前記第１の矩形と前記第２の矩形とのうち面積が小さいの方の矩形の中心から他方の矩形に含まれる端子までの距離が長い順に前記複数のグループの各々に均等に分散するように、前記複数の信号線を分類するための処理を実施するステップと、
前記第３のパターンの場合には、前記第１の矩形と前記第２の矩形とのうち面積が小さい方の矩形に含まれる端子の位置が、前記複数のグループの各々に均等に分散するように、前記複数の信号線を分類するための処理を実施するステップと、
を含む付記２記載のプログラム。
【０１３１】
（付記４）
指定された前記グループ化の条件が前記第２の要件及び前記第１の要件のうちいずれを優先させるかの指定を含む場合には、仮配線を実施して最長の仮配線長となった信号線を、当該信号線の所属グループ及び交換対象のグループにおける仮配線長及び端子の隣接関係が所定の条件を満たす、前記交換対象のグループの信号線と交換する処理を実施するステップ
を、さらに前記コンピュータに実行させるための付記２記載のプログラム。
【０１３２】
（付記５）
配線すべき複数の信号線を複数のグループに分けるための方法であって、
ユーザから、前記複数の信号線のグループ化の条件の指定を受け付けるステップと、
指定された前記グループ化の条件と、データ格納部に格納されている前記複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、前記複数の信号線のグループ化の処理を切り替えて実施するステップと、
を含み、コンピュータにより実行される方法。
【０１３３】
（付記６）
配線すべき複数の信号線の始点端子群と終点端子群とのデータを格納するデータ格納部と、
ユーザから、前記複数の信号線のグループ化の条件の指定を受け付ける入力部と、
指定された前記グループ化の条件と、データ格納部に格納されている前記複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、前記複数の信号線のグループ化の処理を切り替えて実施する処理部と、
を有する信号線グループ化支援装置。
【符号の説明】
【０１３４】
１００ 配線支援装置
１１０ 処理部
１１１ 制御部
１１２ 第１分類処理部
１１３ 第２分類処理部
１１４ 第３分類処理部
１１５ 信号交換補正処理部
１１６ 第４分類処理部
１１７ 仮配線処理部
１１８ 交差処理部
１１９ 最小全域木処理部
１２０ マンハッタン長処理部
１３０ 第１データ格納部
１４０ 第２データ格納部
１５０ 第３データ格納部
１６０ 入力部
【技術分野】
【０００１】
本技術は、ＬＳＩ（Large Scale Integration）やプリント配線基板などにおける信号線の配線を支援するための技術に関する。
【背景技術】
【０００２】
近年、複数の層を有する多層基板における配線設計作業では信号速度が高速化し、設計制約条件が指示されることが一般的になってきている。設計制約条件の中には、部品間を接続する信号線を流れる信号のタイミングを合わせるために、配線パスに対してその長さが指示されていたり、バスなどのような複数の配線パスからなるグループにおいてはその各配線パスの線長はすべて等しい長さとするという指示がされていたりする。
【０００３】
例えば図１に示すように、信号の送信元であるドライバ１０００から信号の受信先であるレシーバ１１００まで、同一タイミングで信号が到達しなければならない場合には、配線パスの線長は全て等しい長さという等長線長条件が課される。
【０００４】
また、例えば図２Ａ（上面図）及び図２Ｂ（断面図）に示すように、多層基板の場合、第１の層Ｌ１の信号端子１００４から第２の層Ｌ２の信号端子１００３（例えば半導体チップＩＣ１の端子）までをビア１００１を使って配線することができる。しかしながら、各信号はビアを使っての複数層による配線１００２では層間移動での遅延が発生するため、図２Ｃに示すように、ビアを使用しない単層配線をすることが求められてきている。
【０００５】
しかし、図３Ａに示すような始点端子群Ａから終点端子群Ｂまでの多数の信号を含む信号群を単層配線すると、図３Ｂのように迂回する配線などにより配線領域が広がり、また信号間での線長差分が大きくなるという問題が生ずる。
【０００６】
図４Ａに模式的に示すように、高密度実装のため配線領域１６００を小さくする場合には、配線すべき信号群におけるドライバからレシーバまでの最大線長を短くすることになる。しかしながら、配線領域を重視すると、信号群における線長のばらつきが生じて等長線長条件を遵守するための調整が難しくなる場合が生ずる。
【０００７】
一方、図４Ｂに模式的に示すように、等長線長条件を重視して、線長差を小さくするように配線を行う場合には、配線すべき信号群におけるドライバからレシーバまでの最大線長が長くなって、配線領域１７００が大きくなり高密度配線に支障をきたす場合も生ずる。
【０００８】
そのため、配線すべき信号群を複数の層にグループ化し、各層の信号群ではこのような問題が起こらないようにすることが望まれる。
【０００９】
しかしながら、人手で、配線すべき信号群を複数の層に適切にグループ化するのは難しい場合が多い。具体的には、要件を満たすように配線を行うことができないことが後から分かって、グループ化からやり直すといった手戻りを行うという非効率な作業が行われることになる。
【００１０】
また、信号群の仮想配線領域を計算し、他の信号群の領域と重なった領域の信号数を調整し別層に移動するという自動化技術も存在している。しかしながら、このような技術では、他の信号群の存在が前提となっており、線長差の問題については考慮されてない。
【００１１】
さらに、部品の配置、配線の混雑度を評価することで信号群をグループ化し、できるだけグループ化した各信号を近接するように配置して最適な経路を探索する手法も存在している。しかし、この技術でも、グループ化においては制約条件を満たすような考慮はないため、線長の問題を解決できないケースがある。また、グループ化した信号群の概略経路を再考しては評価する作業が繰り返され効率が悪い。また、配線領域の効率化についても考慮がなされていない。
【００１２】
さらに、信号配線間隔を複数本分見積もって束配線し、出力側と入力側で端子の並びが同じ時はプリント基板の同一層内で配線を決定し、異なるときは、任意の折れ曲がり領域にスイッチングエリアを設けて二層に割り当てる技術も存在している。しかしながら、二層に分けるというのはビアを介して接続することを述べており、上で述べたような単層配線で制約条件を満たすものではない。
【先行技術文献】
【特許文献】
【００１３】
【特許文献１】特開２００６−１１６８４号公報
【特許文献２】特開２００４−２８７６８１号公報
【特許文献３】特開平７−２９６０２７号公報
【発明の概要】
【発明が解決しようとする課題】
【００１４】
複数の層で単層配線を行うため、配線すべき複数の信号線をグループ化する場合に、考慮すべき事項は以下のとおりである。すなわち、等長線長条件を充足しやすくする線長調整容易性と、信号線や信号端子を密集させずに配線をし易くすることで配線領域を削減する結線容易性とである。また、これらの両方を考慮する場合であってもいずれを優先させるかという問題もある。従来技術は、このような問題に対処するように、複数の信号線をグループ化することができない。
【００１５】
従って、本技術の目的は、一側面として、配線すべき複数の信号線を、ユーザの指定する目的に従って適切にグループ化する技術を提供することである。
【課題を解決するための手段】
【００１６】
配線すべき複数の信号線を複数のグループに分けるための方法は、（Ａ）ユーザから、複数の信号線のグループ化の条件の指定を受け付けるステップと、（Ｂ）指定された、グループ化の条件と、データ格納部に格納されている、複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、複数の信号線のグループ化の処理を切り替えて実施する実施ステップとを含む。
【発明の効果】
【００１７】
配線すべき複数の信号線を、ユーザの指定する目的に従って適切にグループ化できるようになる。
【図面の簡単な説明】
【００１８】
【図１】図１は、等長線長条件を説明するための模式図である。
【図２Ａ】図２Ａは、ビアを用いた配線の一例を示す平面図である。
【図２Ｂ】図２Ｂは、ビアを用いた配線の一例を示す断面図である。
【図２Ｃ】図２Ｃは、単層配線の一例を示す平面図である。
【図３Ａ】図３Ａは、配線前の信号端子の配置状態を示す図である。
【図３Ｂ】図３Ｂは、配線後の状態を示す図である。
【図４Ａ】図４Ａは、配線領域を小さくした場合の線長の分布を示す模式図である。
【図４Ｂ】図４Ｂは、等長線長条件を満たすようにした場合の配線領域の一例を示す模式図である。
【図５】図５は、実施の形態における配線支援装置の機能ブロック図である。
【図６】図６は、本実施の形態における最上位の処理フローを示す図である。
【図７】図７は、処理Ｂの処理フローを示す図である。
【図８Ａ】図８Ａは、分離の配置パターンの一例を示す図である。
【図８Ｂ】図８Ｂは、分離の配置パターンが成立していない場合の一例を示す図である。
【図８Ｃ】図８Ｃは、分離の配置パターンが成立しており且つ対向の配置パターンも成立している場合の一例を示す図である。
【図８Ｄ】図８Ｄは、分離の配置パターンが成立しており且つ非対向の配置パターンも成立している場合の一例を示す図である。
【図９】図９は、処理ＢＡの処理フローを示す図である。
【図１０】図１０は、処理Ａの処理フローを示す図である。
【図１１】図１１は、処理ＡＢの処理フローを示す図である。
【図１２】図１２は、最小全域木均等分類処理の処理フローを示す図である。
【図１３】図１３は、信号端子群の一例を示す図である。
【図１４】図１４は、最小全域木の一例を示す図である。
【図１５】図１５は、分類結果の一例を示す図である。
【図１６Ａ】図１６Ａは、グループ１の端子群の一例を示す図である。
【図１６Ｂ】図１６Ｂは、グループ２の端子群の一例を示す図である。
【図１６Ｃ】図１６Ｃは、グループ３の端子群の一例を示す図である。
【図１７】図１７は、円探索均等分類処理の処理フローを示す図である。
【図１８】図１８は、集合Ｓと集合Ｔとの一例を示す図である。
【図１９】図１９は、円探索均等分類処理におけるグループ化を説明するための図である。
【図２０】図２０は、ＸＹ分類処理の処理フローを示す図である。
【図２１】図２１は、第１分類処理の処理フローを示す図である。
【図２２】図２２は、水平角度を算出する方法について説明する図である。
【図２３】図２３は、Ｘ方向範囲とＹ方向範囲を説明するための図である。
【図２４】図２４は、初期的なグループ化の結果の一例を示す図である。
【図２５Ａ】図２５Ａは、前提となる線分の分布を示す図である。
【図２５Ｂ】図２５Ｂは、Ｘ方向グループに属する線分の分布を示す図である。
【図２５Ｃ】図２５Ｃは、Ｙ方向グループに属する線分の分布を示す図である。
【図２６】図２６は、第２分類処理の処理フローを示す図である。
【図２７】図２７は、交差する線分の数の一例を示す図である。
【図２８】図２８は、第２分類処理におけるデータの一例を示す図である。
【図２９】図２９は、第２分類処理におけるデータの一例を示す図である。
【図３０】図３０は、第２分類処理におけるデータの一例を示す図である。
【図３１Ａ】図３１Ａは、Ｘ方向グループに属する線分をさらに分類した結果における第１のグループの一例を示す図である。
【図３１Ｂ】図３１Ｂは、Ｘ方向グループに属する線分をさらに分類した結果における第２のグループの一例を示す図である。
【図３２】図３２は、第２分類処理の処理フローを示す図である。
【図３３】図３３は、第２分類処理の処理結果の一例を示す図である。
【図３４】図３４は、信号交換補正処理の処理フローを示す図である。
【図３５Ａ】図３５Ａは、端子群の第１のグループの一例を示す図である。
【図３５Ｂ】図３５Ｂは、端子群の第２のグループの一例を示す図である。
【図３５Ｃ】図３５Ｃは、端子群の第３のグループの一例を示す図である。
【図３６Ａ】図３６Ａは、端子群の第１のグループについて仮配線を実施した結果の一例を示す図である。
【図３６Ｂ】図３６Ｂは、端子群の第２のグループについて仮配線を実施した結果の一例を示す図である。
【図３６Ｃ】図３６Ｃは、端子群の第３のグループについて仮配線を実施した結果の一例を示す図である。
【図３７】図３７は、交換処理の処理フローを示す図である。
【図３８】図３８は、隣接数の計数方法の一例を示す図である。
【図３９】図３９は、隣接コストの計算方法の一例を示す図である。
【図４０】図４０は、隣接数及び隣接コストの計算の一例を説明するための図である。
【図４１】図４１は、隣接数及び隣接コストの計算の一例を説明するための図である。
【図４２】図４２は、線長ベース分類処理の処理フローを示す図である。
【図４３Ａ】図４３Ａは、マンハッタン長テーブルの一例を示す図である。
【図４３Ｂ】図４３Ｂは、所属ネットテーブルの一例を示す図である。
【図４４】図４４は、線長ベース分類処理の処理フローを示す図である。
【図４５】図４５は、マンハッタン長テーブルの一例を示す図である。
【図４６】図４６は、所属ネットテーブルの一例を示す図である。
【図４７】図４７は、マンハッタン長テーブルの一例を示す図である。
【図４８】図４８は、所属ネットテーブルの一例を示す図である。
【図４９】図４９は、マンハッタン長テーブルの一例を示す図である。
【図５０】図５０は、所属ネットテーブルの一例を示す図である。
【図５１】図５１は、コンピュータの機能ブロック図である。
【発明を実施するための形態】
【００１９】
本技術の実施の形態に係る配線支援装置１００の機能ブロック図を図５に示す。配線支援装置１００は、処理部１１０と、処理すべき信号線などのデータを格納する第１データ格納部１３０と、処理部１１０の処理において途中で生成されるデータを格納する第２データ格納部１４０と、処理部１１０の処理結果を格納する第３データ格納部１５０と、ユーザからの指示を受け付ける入力部１６０とを有する。
【００２０】
また、処理部１１０は、制御部１１１と、円探索均等分類処理を実施する第１分類処理部１１２と、最小全域木均等分類処理を実施する第２分類処理部と、ＸＹ分類処理を実施する第３分類処理部１１４と、信号交換補正処理部１１５と、線長ベース分類処理を実施する第４分類処理部１１６と、仮配線処理部１１７と、交差処理部１１８と、最小全域木処理部１１９と、マンハッタン長処理部１２０とを有する。
【００２１】
第１データ格納部１３０は、配線すべき信号線（ネットとも呼ぶ）の識別子と、当該信号線の始点端子識別子と、当該信号線の終点端子識別子と、始点端子の座標値と、終点端子の座標値とが登録されるようになっている。配線すべき信号線については、例えばユーザにより入力部１６０によって指定された信号線であり、その信号線のデータについては、入力部１６０を介して入力するようにしてもよい。また、ネットワークを介して接続されている他のコンピュータなどから、配線すべき信号線のデータを読み出して、第１データ格納部１３０に格納するようにしてもよい。
【００２２】
次に、図６乃至図５０を用いて配線支援装置１００の処理内容について説明する。
【００２３】
まず、入力部１６０は、ユーザに対して、分割数（グループ数とも呼ぶ）ｎ及びグループ化の目的種別の入力を促し、ユーザからこれらのデータを受け付け、第１データ格納部１３０に格納する（図６：ステップＳ１）。本実施の形態では、目的種別は、Ａ：「線長調整容易性」、Ｂ：「結線容易性」、ＡＢ：「線長調整容易性及び結線容易性であって、それらのうち線長調整容易性を優先」、ＢＡ：「結線容易性及び線長調整容易性であって、それらのうち結線容易性を優先」のいずれかである。
【００２４】
また、入力部１６０は、ユーザに対して、配線すべき信号線のデータの指定を促し、ユーザから入力データを受け付け、第１データ格納部１３０に格納する（ステップＳ３）。上でも述べたように、ファイルなどの形式で、他のコンピュータなど外部から読み込み、第１データ格納部１３０に格納するようにしてもよい。
【００２５】
そして、処理部１００の制御部１１１は、第１データ格納部１３０に格納されている、グループ化の目的種別を読み出して、当該目的種別がＢ：「結線容易性」であるか判断する（ステップＳ５）。目的として結線容易性が指定されている場合には、制御部１１１は、以下で述べる処理Ｂを、以下で述べる処理部に実施させる（ステップＳ７）。
【００２６】
一方、目的種別が「結線容易性」ではない場合には、制御部１１１は、目的種別がＡ：「線長調整容易性」であるか判断する（ステップＳ９）。目的として線長調整容易性が指定されている場合には、制御部１１１は、以下で述べる処理Ａを、以下で述べる処理部に実施させる（ステップＳ１１）。
【００２７】
さらに、目的種別が「線長調整容易性」ではない場合には、制御部１１１は、目的種別がＢＡ：「結線容易性及び線長調整容易性であって、それらのうち結線容易性を優先」であるか判断する（ステップＳ１３）。目的として「結線容易性及び線長調整容易性であって、それらのうち結線容易性を優先」である場合には、制御部１１１は、以下で述べる処理ＢＡを、以下で述べる処理部に実施させる（ステップＳ１７）。
【００２８】
一方、目的種別がＢＡ：「結線容易性及び線長調整容易性であって、それらのうち結線容易性を優先」でない場合には、ＡＢ：「結線容易性及び線長調整容易性であって、それらのうち線長調整容易性を優先」であるので、制御部１１１は、以下で述べる処理ＡＢを、以下で述べる処理に実施させる（ステップＳ１５）。
【００２９】
その後、制御部１１１は、第２データ格納部１４０に格納されている分類結果を、第３データ格納部１５０に格納する（ステップＳ１９）。そして処理を終了する。
【００３０】
このように、第１に目的に応じて処理を切り替えるようになっている。
【００３１】
次に、結線容易性の実現を目的とする場合の分類処理である処理Ｂについて、図７乃至図８Ｄを用いて説明する。
【００３２】
制御部１１１は、第１データ格納部１３０に格納されている始点端子群の座標から当該始点端子群を包含する第１の矩形と、第１データ格納部１３０に格納されている終点端子群の座標から当該終点端子群を包含する第２の矩形とを算出し、矩形の頂点の座標データを例えば第２データ格納部１４０に格納する（図７：ステップＳ２１）。そして、制御部１１１は、第１の矩形と第２の矩形とから、始点端子群及び終点端子群の配置パターンを特定する（ステップＳ２３）。
【００３３】
本実施の形態では、図８Ａに示すように、白丸で示される始点端子群を包含する第１の矩形ａと、黒丸で示される終点端子群を包含する第２の矩形ｂとのいずれの矩形内にも、他方の端子が存在しない「分離」という配置パターンが成立しているかを判断する（ステップＳ２５）。図８Ａの例では、黒丸で示される終点端子群のうち一部の終点端子が第１の矩形ａ内に含まれるが、白丸で示される始点端子群については１つも第２の矩形ｂ内に含まれているないので、「分離」が成立している。一方、図８Ｂに示すように、黒丸で示される終点端子群のうち一部の終点端子が第１の矩形ａ内に含まれており、白丸で示される始点端子群についても第２の矩形ｂ内に含まれているので、「分離」パターンが成立していない。
【００３４】
「分離」パターンが成立している場合には、図８Ｃに示すように、第１の矩形ａと第２の矩形ｂとが交差しない「対向」という配置パターンが成立しているか判断する。一方、図８Ｄに示すように、第１の矩形ａと第２の矩形ｂとが交差している（図８Ｄの例では第２の矩形ｂが第１の矩形ａに包含されている）場合には、「対向」していない「非対向」という配置パターンであると判断する。
【００３５】
制御部１１１は、ステップＳ２３で「分離」の配置パターンに該当しないと特定された場合には（ステップＳ２５：Ｎｏルート）、第３分類処理部１１４にＸＹ分類処理を実施させる（ステップＳ２７）。そして呼び出し元の処理に戻る。ＸＹ分類処理については後に詳細に説明する。
【００３６】
一方、ステップＳ２３で「分離」の配置パターンに該当すると特定された場合には（ステップＳ２５：Ｙｅｓルート）、制御部１１１は、ステップＳ２３で「対向」の配置パターンに該当すると特定されたか判断する（ステップＳ２９）。ステップＳ２３で「対向」パターンに該当すると判断された場合には、制御部１１１は、第２分類処理部１１３に最小全域木均等分類処理を実施させる（ステップＳ３１）。そして呼び出し元の処理に戻る。最小全域木均等分類処理については後に詳細に説明する。
【００３７】
一方、ステップＳ２３で「対向」の配置パターンには該当しないと特定された場合には、制御部１１１は、第１分類処理部１１２に円探索均等分類処理を実施させる（ステップＳ３３）。そして呼び出し元の処理に戻る。円探索均等分類処理については後に詳細に説明する。
【００３８】
このような処理Ｂを実施することで、始点端子群及び終点端子群の配置パターンに応じて、結線しやすいように信号線群がグループ化されるようになる。
【００３９】
次に、結線容易性及び線長調整容易性の実現を目的とするが結線容易性を優先する場合の分類処理である処理ＢＡについて、図９を用いて説明する。
【００４０】
制御部１１１は、第１データ格納部１３０に格納されている始点端子群の座標から当該始点端子群を包含する第１の矩形と、同じく第１データ格納部１３０に格納されている終点端子群の座標から当該終点端子群を包含する第２の矩形とを算出し、矩形の頂点の座標データを例えば第２データ格納部１４０に格納する（図９：ステップＳ４１）。そして、制御部１１１は、第１の矩形と第２の矩形とから、始点端子群及び終点端子群の配置パターンを特定する（ステップＳ４３）。この処理は、ステップＳ２３と同じである。
【００４１】
制御部１１１は、ステップＳ４３で「分離」の配置パターンに該当しないと特定された場合には（ステップＳ４５：Ｎｏルート）、第３分類処理部１１４にＸＹ分類処理を実施させる（ステップＳ４７）。ＸＹ分類処理については後に詳細に説明する。そして、ステップＳ５５に移行する。
【００４２】
一方、ステップＳ４３で「分離」の配置パターンに該当すると特定された場合には（ステップＳ４５：Ｙｅｓルート）、制御部１１１は、ステップＳ４３で「対向」の配置パターンに該当すると特定されたか判断する（ステップＳ４９）。ステップＳ４３で「対向」の配置パターンに該当すると判断された場合には、制御部１１１は、第２分類処理部１１３に最小全域木均等分類処理を実施させる（ステップＳ５１）。そしてステップＳ５５に移行する。最小全域木均等分類処理については後に詳細に説明する。
【００４３】
一方、ステップＳ４３で「対向」の配置パターンには該当しないと特定された場合には、制御部１１１は、第１分類処理部１１２に円探索均等分類処理を実施させる（ステップＳ５３）。そしてステップＳ５５に移行する。円探索均等分類処理については後に詳細に説明する。
【００４４】
ここまでは処理Ｂと同様であるが、ステップＳ４７、Ｓ５１又はＳ５３の後に、制御部１１１は、信号交換補正処理部１１５に、信号交換補正処理を実施させる（ステップＳ５５）。そして呼び出し元の処理に戻る。信号交換補正処理については後に詳細に説明する。
【００４５】
このような処理ＢＡを実施することで、処理Ｂと同様に、始点端子群及び終点端子群の配置パターンに応じて、結線しやすいように信号線群がグループ化されるようになる。さらに、以下に詳細に述べる信号交換補正処理を実施するため、配線すべき信号線群における最大線長もある程度短くなるため、等長線長条件を遵守するための線長調整工程がある程度軽減される。
【００４６】
次に、線長調整容易性の実現を目的とする場合の分類処理である処理Ａについて、図１０を用いて説明する。
【００４７】
制御部１１１は、第４分類処理部１１６に対して、線長ベース分類処理を実施させる（ステップＳ５７）。そして呼び出し元の処理に戻る。線長ベース分類処理については後に詳細に説明する。
【００４８】
このような処理を実施することで、以下で述べるように、各グループにおいて、最大線長を短縮するように信号群がグループ化される。すなわち、等長線長条件を遵守するための線長調整工程の困難性が軽減される。
【００４９】
次に、線長調整容易性及び結線容易性の実現を目的とするが線長調整容易性を優先する場合の分類処理である処理ＡＢについて、図１１を用いて説明する。
【００５０】
制御部１１１は、第４分類処理部１１６に対して、線長ベース分類処理を実施させる（ステップＳ６１）。線長ベース分類処理については後に詳細に説明する。その後、制御部１１１は、信号交換補正処理部１１５に、信号交換補正処理を実施させる（ステップＳ６３）。そして呼び出し元の処理に戻る。信号交換補正処理については後に詳細に説明する。
【００５１】
このような処理を実施することで、以下で述べるように、各グループにおいて、最大線長を短縮するように信号群がグループ化される。すなわち、等長線長条件を遵守するための線長調整工程の困難性が軽減される。さらに、以下に詳細に述べる信号交換補正処理を実施するため、配線スペースがある程度確保され、結線容易性もある程度確保される。
【００５２】
以上のように、ユーザから指定された目的と、配線すべき信号線群の始点端子群及び終点端子群の配置パターンとに応じて、適切な分類処理が実施され、目的に応じた適切な信号線の分類がなされるようになる。
【００５３】
次に、各グループについて端子が可能な限り均等に分布するようにグループ化する最小全域木均等分類処理について、図１２乃至図１６を用いて説明する。第２分類処理部１１３は、第２データ格納部１４０に格納されている、矩形のデータに基づき第１の矩形の面積と第２の矩形の面積とを比較して、面積が小さい方の信号端子の集合を集合Ｓとして特定する（図１２：ステップＳ７１）。具体的には、面積が小さい方の信号端子の座標データを第１データ格納部１３０から読み出す。
【００５４】
そして、第２分類処理部１１３は、最小全域木処理部１１９に、集合Ｓについて最小全域木を生成させ、最小全域木のデータを第２データ格納部１４０に格納する（ステップＳ７３）。例えば図１３に黒丸で示されるような信号端子が集合Ｓとして特定されたとすると、図１４に示すような最小全域木が生成される。なお、図１４に示す番号は、ステップＳ７３の段階では特定されていない。なお、最小全域木の生成アルゴリズムについてはよく知られているので、ここでは述べない。
【００５５】
次に、第２分類処理部１１３（又は最小全域木処理部１１９）は、生成した最小全域木に対して深さ優先探索を実施することで、各信号端子に分割数ｎまでの番号を付与する（ステップＳ７５）。深さ優先探索についてはよく知られているのでこれ以上述べない。深さ優先探索を実施すると、図１４に示したように、各信号端子に対して１乃至分割数ｎの番号が付与される。この番号がグループの番号になる。
【００５６】
そして、第２分類処理部１１３は、集合Ｓに含まれる端子の信号線識別子を第１データ格納部１３０から特定し、信号端子にステップＳ７５で付与された番号とを、対応付けて第３データ格納部１５０に格納する（ステップＳ７７）。例えば、図１５に示すようなデータが格納される。図１５の例では、信号線の識別子と、グループ番号とが対応付けて格納される。
【００５７】
図１４に示すように、深さ優先探索で番号を付与すると、比較的隣接する信号端子には異なる番号が付与されるようになるため、端子位置がほぼ均等に分散するようにグループ分けが行われるようになる。すなわち、結線容易性が担保されるようになる。図１３の例では、図１６Ａは番号「１」のグループを表しており、図１６Ｂは番号「２」のグループを表しており、図１６Ｃは番号「３」のグループを表している。このように、端子位置がほぼ均等に分散するようになっていることが分かる。
【００５８】
なお、深さ優先探索ではなく、幅優先選択や最下層幅優先探索などを採用する場合もある。
【００５９】
次に、各グループについて端子が可能な限り均等に分布するようにグループ化する第２の手法である円探索均等分類処理について、図１７乃至図１９を用いて説明する。
【００６０】
第１分類処理部１１２は、第２データ格納部１４０に格納されている矩形のデータに基づき、第１の矩形と第２の矩形のうち、一方が他方を包含している場合には他方の矩形の信号端子の集合を、交差している場合には面積が小さい方の矩形の信号端子の集合を集合Ｓに設定し、残余の信号端子の集合を集合Ｔに設定する（図１７：ステップＳ８１）。具体的には、集合Ｓの信号端子のデータを、第１データ格納部１３０から読み出し、集合Ｔの信号端子のデータを、第１データ格納部１３０から読み出す。
【００６１】
図１８に示すように、白丸の始点端子群の矩形が、黒丸の終点端子群の矩形に包含される場合には、始点端子群が集合Ｓに設定され、黒丸の終点端子群が集合Ｔに設定される。
【００６２】
そして、第１分類処理部１１２は、集合Ｓの矩形の中心座標Ｃを算出し、第２データ格納部１４０に格納する（ステップＳ８３）。図１８の例では、矩形Ｓの中心座標を算出する。そして、第１分類処理部１１２は、中心座標Ｃから、集合Ｔの各信号端子との距離を算出し、距離が大きい順に分割数ｎまでの番号を順に付与する（ステップＳ８５）。
【００６３】
図１８の例では、図１９に示すように、矩形Ｓの中心（星印）からの距離が最も大きい信号端子ｔ１、次に距離が大きい信号端子ｔ２、さらに次に距離が大きい信号端子ｔ３の順で、分割数１乃至ｎの番号が付与される。ｔ１には「１」が付与され、ｔ２には「２」が付与され、ｔ３には「３」が付与される。
【００６４】
その後、第１分類処理部１１２は、集合Ｔに含まれる端子の信号線識別子を第１データ格納部１３０から特定し、信号端子にステップＳ８５で付与された番号とを、対応付けて第３データ格納部１５０に格納する（ステップＳ８７）。例えば、図１５に示すようなデータが格納される。
【００６５】
このように、第１の矩形と第２の矩形とのうち面積の小さい矩形の中心からの距離が大きい順に、各グループに均等に分散するように信号端子をグループ化することで、信号線のグループ化を行っている。これによって、図８Ｄのような分離はしているが対向していない配置パターンにおいて、均等に分散するようにグループ化を行うことができるようになる。
【００６６】
次に、同一グループにおける始点端子と終点端子とをつなぐ線分の交差を削減することで結線容易性を担保するための処理であるＸＹ分類処理について図２０乃至図３３を用いて説明する。
【００６７】
まず、第３分類処理部１１４は、第１分類処理を実施する（図２０：ステップＳ９１）。第１分類処理については、図２１乃至図２５Ｃを用いて説明する。
【００６８】
第３分類処理部１１４は、第１データ格納部１３０に格納されているデータに含まれる信号線のうち、未処理の信号線を１つ特定する（図２１：ステップＳ１１１）。そして、第３分類処理部１１４は、特定された信号線の始点と終点とを結ぶ線分の水平角度を算出し、例えば第２データ格納部１４０に格納する（ステップＳ１１３）。例えば図２２に示したように、始点（白丸）から終点（黒丸）までの線分とＸ軸との角度θを算出する。
【００６９】
そして、第３分類処理部１１４は、ステップＳ１１３で算出した水平角度がＸ方向の範囲内であるかを判断する（ステップＳ１１５）。本実施の形態では、図２３に示すように、Ｘ軸に平行で原点を通過する直線を原点を中心に＋４５°回転させた直線と−４５°回転させた直線とで囲まれる範囲（すなわちＸ軸を囲む範囲）をＸ方向の範囲とする。それ以外はＹ方向の範囲とする。
【００７０】
水平角度がＸ方向の範囲内であれば、第３分類処理部１１４は、特定された信号線をＸ方向グループ（Ｄｘ）に登録する（ステップＳ１１９）。そして、ステップＳ１２１に移行する。一方、水平角度がＹ方向の範囲内であれば、第３分類処理部１１４は、特定された信号線をＹ方向グループ（Ｄｙ）に登録する（ステップＳ１１７）。そして、ステップＳ１２１に移行する。例えば、第２データ格納部１４０には、図２４に示すようなリストが登録される。図２４の例では、Ｄｘの列には、Ｘ方向グループの信号線の識別子が列挙され、Ｄｙの列には、Ｙ方向グループの信号線の識別子が列挙される。
【００７１】
その後、第３分類処理部１１４は、第１データ格納部１３０に格納されているデータに含まれる信号線のうち、未処理の信号線が存在しているか判断する（ステップＳ１２１）。未処理の信号線が存在する場合にはステップＳ１１１に戻る。一方、未処理の信号線が存在しない場合には、呼び出し元の処理に戻る。
【００７２】
なお、図２５Ａに示すような、始点（白丸）から終点（黒丸）までの線分の分布がある場合、第１分類処理では、図２５Ｂに示すようなＸ方向グループと、図２５Ｃに示すようなＹ方向グループとに分けられる。
【００７３】
図２０の処理の説明に戻って、第３分類処理部１１４は、ユーザに指定された分割数ｎが２であるか判断する（ステップＳ９３）。分割数ｎが２であれば、これ以上分類はしないので、ステップＳ１０５に移行する。一方、分割数ｎが３以上であれば、第３分類処理部１１４は、分割グループ数＝２に設定し（ステップＳ９５）、第２分類処理を実施する（ステップＳ９７）。第２分類処理については図２６乃至図３３を用いて説明する。
【００７４】
まず、第３分類処理部１１４は、現在のグループ毎に、交差する線分の数を、交差処理部１１８に算出させ、第２データ格納部１４０に格納させる（図２６：ステップＳ１３１）。例えば図２５Ｂ及び図２５Ｃからすると、図２７に示すように、Ｘ方向グループＤｘについては交差する線分の数６が得られ、Ｙ方向グループＤｙについては交差する線分の数４が得られ、第２データ格納部１４０に格納される。
【００７５】
そして、第３分類処理部１１４は、交差する線分の数が最大のグループを特定する（ステップＳ１３３）。その後、第３分類処理部１１４は、特定されたグループに属する線分について、分割予定グループを「未決定」に設定する（ステップＳ１３５）。例えば図２８に示すようなデータを第２データ格納部１４０に用意する。
【００７６】
そして、第３分類処理部１１４は、分割予定グループが「未決定」の全ての線分の各々について、分割予定グループが「未決定」又は「Ａ」（繰り返しの中で「Ａ」が設定されるので、最初は「Ａ」は存在しない）に属する他の線分との交差数を交差処理部１１８に算出させ、交差数最大値Ｃmaxである線分を線分Ｌmaxとして特定する（ステップＳ１３７）。図２５Ｂの例では、線分１６５１乃至１６５４が交差数「２」で特定され、Ｃmax＝２となる。但し、図２５Ｂの例では、線分１６５２乃至１６５４は互いに交差している。
【００７７】
その後、第３分類処理部１１４は、Ｃmax＝０であるか判断する（ステップＳ１３９）。交差がない場合には、これ以上処理ができないので、第３分類処理部１１４は、第２データ格納部１４０において分割予定グループが「未決定」の線分に対して、分割予定グループ「Ａ」を設定する（ステップＳ１４１）。そして処理は端子Ａを介して図３２の処理に移行する。
【００７８】
一方、Ｃmax＝０ではなく１以上である場合には、第３分類処理部１１４は、線分Ｌmaxに分割予定グループ「Ａｂ」を設定し、線分Ｌmaxと交差し且つ分割予定グループ「未決定」の線分に分割予定グループ「Ａ」を設定する（ステップＳ１４３）。その後、端子Ａを介して図３２の処理に移行する。「Ａ」と「Ａｂ」は、グループ分けを識別するための便宜上の識別子であって、他の識別子を用いてもよい。
【００７９】
例えば、図２５Ｂの例で、線分１６５１をＬmaxとすると、分割予定グループ「Ａｂ」が設定され、線分１６５１に交差する線分１６７１及び１６７２には分割予定グループ「Ａ」が設定される。また、線分１６５２をＬmaxとすると、分割予定グループ「Ａｂ」が設定される。線分１６５２に交差する線分１６５３及び１６５４は、交差数「２」でＬmaxでもある。しかし、このように互いに交差している線分について同じ分割予定グループ「Ａｂ」を設定すると、交差数を減らすことができないので、Ｌmaxについては１つずつ処理することで、線分１６５２に分割予定グループ「Ａｂ」を設定し、これに交差する線分１６５３及び１６５４については分割予定グループ「Ａ」を設定して、同一分割予定グループに分類されないようにする。すなわち、第２データ格納部１４０に格納されるデータは、図２９の状態から、図３０の状態に更新される。図２５Ｂにおける線分の配置状態は、図３１Ａの分割予定グループ「Ａ」の状態と、図３１Ｂの分割予定グループ「Ａｂ」の状態とに分けられる。これによって、分割予定グループ「Ａ」では最大交差数Ｃmaxは「１」になり、分割予定グループ「Ａｂ」では最大交差数Ｃmaxは「０」となる。
【００８０】
図３２の処理の説明に移行して、第３分類処理部１１４は、分割予定グループ「未決定」の線分が残っているのか判断する（ステップＳ１４５）。分割予定グループ「未決定」の線分が残っている場合には端子Ｂを介してステップＳ１３７に戻る。一方、分割予定グループ「未決定」の線分が残っていなければ、第３分類処理部１１４は、分割予定グループ「Ａ」及び「Ａｂ」についての分類結果を、次の第２分類処理のために第２データ格納部１４０に格納する（ステップＳ１４７）。そして呼び出し元の処理に戻る。
【００８１】
上で述べた例では、Ｙ方向グループと、分割予定グループ「Ａ」及び「Ａｂ」とが、次のステップＳ１３１での現在のグループとなるので、例えば図３３に示すようなデータを生成して第２データ格納部１４０に格納する。図３３の例では、分割予定グループ「Ａ」に属する信号識別子のリストと、分割予定グループ「Ａｂ」に属する信号識別子のリストと、Ｙ方向グループＤｙに属する信号識別子のリストとが格納される。
【００８２】
図２０の処理の説明に戻って、第３分類処理部１１４は、第２分類処理においてグループ分割ができたか判断する（ステップＳ９９）。はじめから交差がない、すなわちＣmax＝０であればグループ分割が行われない。従って、グループ分割が行われなかった場合にはステップＳ１０５に移行する。一方、グループ分割が行われた場合には、第３分類処理部１１４は、分割グループ数＝分割グループ数＋１を算出し（ステップＳ１０１）、分割グループ数＝分割数ｎになったか判断する（ステップＳ１０３）。まだ、分割グループ数＝分割数ｎになっていない場合にはステップＳ９７に戻る。一方、分割グループ数＝分割数ｎになった場合には、ステップＳ１０５に移行する。
【００８３】
ステップＳ１０５では、第３分類処理部１１４は、分類処理に基づき、端子の信号識別子と、当該端子に対応するグループ識別子と対応付けて格納する（ステップＳ１０５）。グループ識別子については、番号に直して設定するようにしてもよい。
【００８４】
このように交差を削減するようにグループ化することで、結線容易性を高めることができるようになる。
【００８５】
次に、線長を短縮するための信号交換補正処理について図３４乃至図４１を用いて説明する。まず、信号交換補正処理部１１５は、マンハッタン長処理部１２０に対して、全ての信号線についてマンハッタン長を算出させ、そのうち最も長いマンハッタン長のｋ（例えば１．１）倍を、目標線長に設定する（図３４：ステップＳ１５１）。マンハッタン長についての算出方法はよく知られているので、ここでは述べない。
【００８６】
そして、信号交換補正処理部１１５は、仮配線処理部１１７に、現在の仮配線データ（初期的にはなし）をクリアさせる（ステップＳ１５３）。そして、信号交換補正処理部１１５は、仮配線処理部１１７に、グループ毎に、仮配線を実施させる（ステップＳ１５５）。仮配線のデータ（信号線の識別子、仮配線の図形データ、仮配線長など）については、第２データ格納部１４０に格納される。
【００８７】
例えば、図３５Ａ乃至図３５Ｃのような３つのグループ（但し、始点端子群のみを示す）に分けられているものとする。このような状態で、例えば仮配線を実施すると、図３５Ａのグループについては図３６Ａに示すような仮配線が実施され、図３５Ｂのグループについては図３６Ｂに示すような仮配線が実施され、図３５Ｃのグループについては図３６Ｃに示すような仮配線が実施される。
【００８８】
信号交換補正処理部１１５は、第２データ格納部１４０に格納されている仮配線長のデータから、最も長い仮配線の信号識別子及び所属グループ、並びに仮配線長を特定し、最も長い仮配線長＞目標線長が成立しているか判断する（ステップＳ１５７）。例えば図３６Ａにおいて丸で示す始点端子から伸びる仮配線１７０１が、最も長い仮配線長の信号線として特定されたものとする。
【００８９】
最も長い仮配線長が目標線長以下である場合には、以下の処理を行わずとも配線長が短くなっていると判断できるので、呼び出し元の処理に戻る。
【００９０】
一方、最も長い仮配線長＞目的線長が成立している場合には、信号交換補正処理部１１５は、交換処理を実施する（ステップＳ１５９）。交換処理については、図３７乃至図４１を用いて説明する。
【００９１】
まず、信号交換補正処理部１１５は、最も長い仮配線の信号線が属するグループとは異なるグループの未処理の信号線を１つ特定する（図３７：ステップＳ１７１）。例えば図３６Ｂにおいて、信号端子３６１から順番に、信号端子３６２、３６３、３６４、３６５、３６６といったように選択してゆく。そして、信号交換補正処理部１１５は、最も長い仮配線長の信号線と、特定された信号線とを交換する前と後の隣接数又は隣接コストを算出し、第２データ格納部１４０に格納する（ステップＳ１７３）。
【００９２】
隣接数を算出する場合には、例えば図３８に示すように、注目信号端子（二重丸）から所定の距離Ｄに含まれる信号端子（黒丸）を特定する。そして、単純に、特定された信号端子の数を計数するようにしてもよい。一方、図３９に示すように、端子が整列配置されている場合には、注目信号端子（二重丸）の縦横隣接した信号端子（黒丸）の数を計数するようにしてもよい。但し、単純な信号端子数ではなく、縦横隣接の場合にはコスト１とし、斜め隣接の場合にはコスト０．５として加算するようにしてもよい。
【００９３】
例えば、図４０に示すように、注目信号端子１７１１の場合には、両横と下に隣接端子が存在しているので、隣接数は「３」で、隣接コストも「３」となる。一方、注目信号端子１７１２の場合には、上と斜め左下に隣接端子が存在しているので、隣接数は「１」であり、隣接コストは「１．５」となる。なお、斜め隣接のコストについては０．５ではなく他の値を採用するようにしてもよい。
【００９４】
より具体的に、図４１に示すように、グループＧ１の信号端子１７２１を、グループＧ２に移動させ、仮に信号端子１７２２の位置（すなわち異なる層の同一位置）に配置するものとする。代わりに、グループＧ２の信号端子１７３１を、グループＧ１に移動させ、仮に信号端子１７３２の位置（すなわち異なる層の同一位置）に配置するものとする。そうすると、丸で囲まれた交換前では、信号端子１７２１についての隣接数は「０」、隣接コストは「０．５」と算出され、矢印の先の交換後では、信号端子１７２２についての隣接数は「０」、隣接コストは「０．５」と算出される。すなわち、交換前後で変化なしということになる。一方、丸で囲まれた交換前では、信号端子１７３１についての隣接数は「０」、隣接コストは「０」と算出され、矢印の先の交換後では、信号端子１７３２についての隣接数は「０」、隣接コスト「１．０」と算出される。すなわち、交換前後で、隣接数は変化していないが、隣接コストは「＋１．０」となっている。なお、単層配線を行うので、始点端子又は終点端子のみではなく、両方の端子について隣接数又は隣接コストを算出する。
【００９５】
そして、信号交換補正処理部１１５は、ステップＳ１７３で算出された隣接数又は隣接コストが条件を満たしているか判断する（ステップＳ１７５）。例えば、交換前後で隣接数が増加していないという条件、交換前後で隣接コストが増加していないという条件を満たしているか判断する。なお両方を満たすような条件設定がなされる場合もある。
【００９６】
ステップＳ１７３で算出された隣接数又は隣接コストが条件を満たしていない場合にはステップＳ１８３に移行する。一方、ステップＳ１７３で算出された隣接数又は隣接コストが条件を満たしている場合には、信号交換補正処理部１１５は、最も長い仮配線長の信号線が属するグループと、ステップＳ１７１で特定された信号線のグループとで、交換を実施した後の状態について、仮配線処理部１１７に対して仮配線を実施させ、仮配線のデータ（信号線の識別子、仮配線の図形データ、仮配線長など）を第２データ格納部１４０に格納させる（ステップＳ１７７）。
【００９７】
そして、信号交換補正処理部１１５は、最も長い仮配線長の信号線が属するグループ及びステップＳ１７１で特定された信号線のグループの各グループについて、最も長い仮配線長が増加したか判断する（ステップＳ１７９）。各グループについて、最も長い仮配線長が増加していない場合には、交換可能であると判断して、信号交換補正処理部１１５は、所属グループの交換を第２データ格納部１４０に登録する（ステップＳ１８１）。具体的には、ステップＳ１５５で特定された最も長い仮配線長の信号線の所属グループを、ステップＳ１７１で特定された信号線のグループに変更し、ステップＳ１７１で特定された信号線のグループを、ステップＳ１５５で特定された最も長い仮配線長の信号線の所属グループに変更する。そして呼び出し元の処理に戻る。
【００９８】
一方、最も長い仮配線長が増加している場合には、交換不可能であると判断して、信号交換補正処理部１１５は、未処理の信号線が存在しているか判断する（ステップＳ１８３）。未処理の信号線が存在している場合にはステップＳ１７１に戻る。一方、未処理の信号線が存在しない場合には、呼び出し元の処理に戻る。
【００９９】
このようにすれば、最も長い仮配線長が短くなるように所属グループを変更することができるようになる。最も長い仮配線長が短くなるというのは、線長調整容易性及び結線容易性のいずれにも効果的である。
【０１００】
図３４の処理の説明に戻って、信号交換補正処理部１１５は、信号線の交換が行われたか判断する（ステップＳ１６１）。信号線の交換が行われた場合にはステップＳ１５３に戻る。すなわち、交換後の状態で、最も長い仮配線長が目標線長以下になっているかを確認する。なお、影響のあるグループについてはステップＳ１５９で仮配線を再度実施しているのでステップＳ１５７に戻るようにしてもよい。一方、信号線の交換が行われていない場合には、これ以上の調整は不可能なので処理を終了し、呼び出し元の処理に戻る。
【０１０１】
以上のような処理を実施することで、最も長い仮配線長を短縮するような分類の補正を行うことができ、線長調整容易性及び結線容易性の向上が行われる。
【０１０２】
次に、複数のグループ間で線長の分布の偏りを抑えつつ最長線長が短縮されるようにグループ化を行うための線長ベース分類処理について、図４２乃至図５０を用いて説明する。
【０１０３】
第４分類処理部１１６は、マンハッタン長処理部１２０に、各信号線について、マンハッタン長及び目標線長（例えばマンハッタン長×ｋ（＝１．１））を算出させ、長い順にソートした後、第２データ格納部１４０におけるマンハッタン長テーブルに登録する（図４２：ステップＳ２０１）。例えば、図４３Ａに示すようなマンハッタン長テーブルが生成されたものとする。図４３Ａの例では、信号線識別子と、マンハッタン長と、目標線長と、仮配線長と、分割予定グループとが登録されるようになっている。仮配線長と分割予定グループとについては、現段階では登録されない。また、マンハッタン長が長い順に信号線はソートされている。
【０１０４】
次に、第４分類処理部１１６は、分割数ｎ個のグループの各々について信号線数を登録するための所属ネットテーブルを生成し、第２データ格納部１４０に格納する（ステップＳ２０３）。図４３Ｂのような所属ネットテーブルが生成される。図４３Ｂの例では、グループＡ、グループＢ及ぶグループＣについて、割当予定信号線数を登録するようになっている。
【０１０５】
そして、第４分類処理部１１６は、所属ネットテーブルのレコードを割当予定信号線数の少ない順にソートする（ステップＳ２０５）。最初は全てのグループについて割当予定信号線数は０であるので、図４３Ｂの状態から変化しない。このようにすれば、できるだけ各グループに均等に信号線を割り当てることができるようになる。
【０１０６】
その後、第４分類処理部１１６は、分割予定グループが未決定で且つ最上位である信号線Ｘを、マンハッタン長テーブルから特定する（ステップＳ２０７）。図４３Ａの例では、最初に、先頭のレコードに含まれる信号線「１」が特定される。
【０１０７】
そして、第４分類処理部１１６は、カウンタｉを１に初期化して（ステップＳ２０９）、ソート後の所属ネットテーブルにおけるｉ番目のグループＧを特定する（ステップＳ２１１）。図４３Ｂの例では、ｉ＝１であればグループ「Ａ」が特定される。
【０１０８】
その後、第４分類処理部１１６は、仮配線処理部１１７に、グループＧの層において信号線Ｘを含む仮配線を実施させ、信号線Ｘの仮配線長ＶＬを算出させ、第２データ格納部１４０におけるマンハッタン長テーブルに登録させる（ステップＳ２１３）。最初は、まだグループＧに所属するとされる信号線はないので、信号線Ｘのみについて仮配線が実施される。次回以降は、グループＧに所属するとされる他の信号線とともに仮配線が行われる。このように、マンハッタン長が長い信号線から順番に仮配線を行えば、仮配線を阻害する他の信号線が少ないため、仮配線長が短くなるということが期待される。すなわち、仮配線長の最大値を小さくすることができるようになる。処理は端子Ｃを介して図４４の処理に移行する。
【０１０９】
そして、第４分類処理部１１６は、ステップＳ２１３で算出された仮配線長ＶＬ＞信号線Ｘの目標線長ＴＬという条件が成立しているか判断する（ステップＳ２１５）。仮配線長ＶＬ＞目標線長ＴＬという条件が成立している場合には、グループＧに信号線Ｘを割り当てても仮配線長ＶＬが目標線長ＴＬよりも長くなってしまうので、他のグループに割り当てることを試みる。すなわち、第４分類処理部１１６は、カウンタｉを１インクリメントして（ステップＳ２１７）、カウンタｉの値が分割数ｎを超えたか判断する（ステップＳ２１９）。なお、この際にはステップＳ２１３で生成された仮配線のデータをもクリアする。カウンタｉの値が分割数ｎ以下であれば、端子Ｄを介してステップＳ２１１に戻る。
【０１１０】
一方、カウンタｉの値が分割数ｎを超えていれば、第４分類処理部１１６は、マンハッタン長から目標線長ＴＬを算出する際に用いる係数ｋの値を増加させる（ステップＳ２２１）。例えば、ｋ＝ｋ＋０．１を算出する。これは、現在の前提ではグループ分けができないということであるため、目標線長ＴＬを変更するためである。そして、処理は端子Ｅを介して図４２のステップＳ２０１に戻る。再度処理をやり直すためである。
【０１１１】
一方、ステップＳ２１５で、仮配線長ＶＬが信号線Ｘの目標線長ＴＬ以下であれば、第４分類処理部１１６は、信号線Ｘについてマンハッタン長テーブルにおいて割当予定グループとしてグループＧを設定し、所属ネットテーブルにおいてグループＧの割当予定信号数を１インクリメントする（ステップＳ２２５）。
【０１１２】
例えば、信号線識別子「１」の信号線Ｘについて、仮配線長ＶＬ＝８０．０６０ｍｍで、目標線長ＴＬ＝８３．６００ｍｍであれば、仮配線長ＶＬが目標線長ＴＬ以下であるので、図４５に示すように、分割予定グループとして「Ａ」が登録される。さらに、図４６に示すように、所属ネットテーブルにおいてグループＡの割当予定信号数も「１」に更新される。
【０１１３】
その後、第４分類処理部１１６は、マンハッタン長テーブルにおいて全ての信号線について分割予定グループが設定されたか判断する（ステップＳ２２７）。分割予定グループが未設定の信号線が存在している場合には、端子Ｆを介して図４２のステップＳ２０５に戻る。
【０１１４】
上で述べた例では、図４７に示すように、マンハッタン長テーブルにおいて２番目のレコードの信号線「４」が信号線Ｘに設定される。また、所属ネットテーブルのレコードをソートして、図４８に示すようにグループＢが先頭になる。すなわち、グループＢ、グループＣ、グループＡの順番で信号線「４」の割り当てを試みることになる。
【０１１５】
一方、ステップＳ２２７で、全ての信号線について分割予定グループが設定された場合には、第４分類処理部１１６は、マンハッタン長テーブルに従って、信号線識別子とグループの識別子との対応付けを第２データ格納部１４０に格納する（ステップＳ２２９）。例えばグループ毎に、所属信号線のリストを生成して格納する。
【０１１６】
その後上で述べた処理を繰り返せば、最終的にマンハッタン長テーブルは、図４９に示すような状態になる。また、所属ネットテーブルは、図５０に示すような状態になる。上でも述べたように、マンハッタン長が長い順に、割当予定信号数が少ないグループに信号線を割り当てることになっている。すなわち、複数のグループ間で線長の分布及び信号線の数の偏りを抑えつつ最長線長が短縮されるようにグループ化がなされるようになる。
【０１１７】
以上本技術の実施の形態を説明したが、本技術はこれに限定されるものではない。例えば、図５に示した配線支援装置１００の機能ブロック図は一例であって、必ずしも実際のプログラムモジュール構成とは一致しない場合もある。また、処理フローについても、処理結果が変わらない限り、ステップの順番を入れ替えたり、並列に実行するようにしてもよい。データの保持方法についても、上で述べた方法は一例であって、他の方法を用いるようにしてもよい。
【０１１８】
上では１台のコンピュータ配線支援装置１００を構成する例を示したが、複数のコンピュータで構成するようにしてもよい。さらに、スタンドアロン型システムであってもよいし、クライアント−サーバ型システムを構築するようにしてもよい。すなわち、クライアント端末からの要求に応じてサーバが上で述べたような処理を実施する。
【０１１９】
なお、上で述べた配線支援装置１００は、コンピュータ装置であって、図５１に示すように、メモリ２５０１とＣＰＵ（Central Processing Unit）２５０３とハードディスク・ドライブ（ＨＤＤ：Hard Disk Drive）２５０５と表示装置２５０９に接続される表示制御部２５０７とリムーバブル・ディスク２５１１用のドライブ装置２５１３と入力装置２５１５とネットワークに接続するための通信制御部２５１７とがバス２５１９で接続されている。オペレーティング・システム（ＯＳ：Operating System）及び本実施例における処理を実施するためのアプリケーション・プログラムは、ＨＤＤ２５０５に格納されており、ＣＰＵ２５０３により実行される際にはＨＤＤ２５０５からメモリ２５０１に読み出される。ＣＰＵ２５０３は、アプリケーション・プログラムの処理内容に応じて表示制御部２５０７、通信制御部２５１７、ドライブ装置２５１３を制御して、所定の動作を行わせる。また、処理途中のデータについては、主としてメモリ２５０１に格納されるが、ＨＤＤ２５０５に格納されるようにしてもよい。本技術の実施例では、上で述べた処理を実施するためのアプリケーション・プログラムはコンピュータ読み取り可能なリムーバブル・ディスク２５１１に格納されて頒布され、ドライブ装置２５１３からＨＤＤ２５０５にインストールされる。インターネットなどのネットワーク及び通信制御部２５１７を経由して、ＨＤＤ２５０５にインストールされる場合もある。このようなコンピュータ装置は、上で述べたＣＰＵ２５０３、メモリ２５０１などのハードウエアとＯＳ及びアプリケーション・プログラムなどのプログラムとが有機的に協働することにより、上で述べたような各種機能を実現する。
【０１２０】
以上述べた本実施の形態をまとめると、以下のようになる。
【０１２１】
本実施の形態にかかる、配線すべき複数の信号線を複数のグループに分けるための配線支援方法は、（Ａ）複数の信号線の線長調整容易性と結線容易性とのうちいずれか又は線長調整容易性及び結線容易性を含み且ついずれを優先させるかの指定を、ユーザから複数の信号線のグループ化の条件として受け付けるステップと、（Ｂ）指定されたグループ化の条件と、データ格納部に格納されている複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、複数の信号線のグループ化の処理を切り替えて実施する実施ステップとを含む。
【０１２２】
これによってユーザが指定した配線の目的に応じて信号線を適切にグループ化することができる。具体的には、単層配線を複数の層で実施する際に、線長調整容易性を求めるケース、結線容易性を求めるケース、両方を求めるが線長調整容易性を優先して求めるケース、両方を求めるが結線容易性を優先して求めるケースのいずれかと、配線すべき信号線の始点端子群と終点端子群との配置パターンとに応じて、グループ化アルゴリズムを切り替えるため、適切にグループ化を行うことができるようになる。
【０１２３】
また、上で述べた実施ステップが、（Ｂ１）グループ化の条件が結線容易性の指定と結線容易性を優先させる指定とのいずれかである場合には、複数の信号線の始点端子群と終点端子群との配置パターンに基づき、結線容易性を担保するためのグループ化処理を切り替えて実施する第１処理ステップと、（Ｂ２）グループ化の条件が線長調整容易性の指定と線長調整容易性を優先させる指定とのいずれかである場合には、複数のグループ間で線長の分布の偏りを抑えつつ最長線長が短縮されるようにグループ化処理を実施する第２処理ステップとを含むようにしてもよい。線長調整容易性の指定又は線長調整容易性を優先させる指定の場合には、配線すべき信号線の始点端子群と終点端子群との配置パターンに拘わらず、上で述べたようなグループ化処理を実施することで、線長調整容易性を担保して、信号線を適切にグループ化することができる。
【０１２４】
なお、上で述べた配置パターンが、（Ｐ１）始点端子群を包含する第１の矩形と終点端子群を包含する第２の矩形とのいずれかに他方の矩形に包含される端子が存在するという第１のパターンと、（Ｐ２）第１の矩形と第２の矩形とのいずれかに他方の矩形に包含される端子が存在せず且つ第１の矩形と前記第２の矩形とが交差する第２のパターンと、（Ｐ３）第１の矩形と第２の矩形とのいずれかに他方の矩形に包含される端子が存在せず且つ第１の矩形と第２の矩形とが交差しない第３のパターンとを含むようにしてもよい。その場合、上で述べた第１処理ステップが、（Ｂ１１）第３のパターンの場合には、第１の矩形と第２の矩形とのうち面積が小さい方の矩形に含まれる端子の位置が、複数のグループの各々に均等に分散するように、複数の信号線を分類するための処理を実施するステップと、（Ｂ１２）第２のパターンの場合には、第１の矩形と第２の矩形とのうち面積が小さいの方の矩形の中心から他方の矩形に含まれる端子までの距離が長い順に複数のグループの各々に均等に分散するように、複数の信号線を分類するための処理を実施するステップと、（Ｂ１３）第１のパターンの場合には、始点端子群と終点端子群とを結ぶ線分の方向及び当該線分の交差状態に基づき、複数の信号線を分類するための処理を実施するステップとを含むようにしてもよい。配置パターンによって実際に行われる配線の状態が異なるため、このような場合分けがなされる。
【０１２５】
また、上で述べた配線支援方法は、（Ｃ）指定されたグループ化の条件が線長調整容易性及び結線容易性のうちいずれを優先させるかの指定を含む場合には、仮配線を実施して最長の仮配線長となった信号線を、当該信号線の所属グループ及び交換対象のグループにおける仮配線長及び端子の隣接関係が所定の条件（例えば信号線の交換が悪影響を与えないという条件）を満たす、交換対象のグループの信号線と交換する処理を実施するステップをさらに含むようにしてもよい。このような処理によれば、仮配線長が短くなり、配線領域を削減するように信号線の交換が行われるので、線長調整容易性を優先する場合には結線容易性を向上させ、結線容易性を優先させる場合には線長調整容易性を向上させることができる。
【０１２６】
なお、上で述べたような処理をコンピュータに実施させるためのプログラムを作成することができ、当該プログラムは、例えばフレキシブル・ディスク、ＣＤ−ＲＯＭなどの光ディスク、光磁気ディスク、半導体メモリ（例えばＲＯＭ）、ハードディスク等のコンピュータ読み取り可能な記憶媒体又は記憶装置に格納される。なお、処理途中のデータについては、ＲＡＭ等の記憶装置に一時保管される。
【０１２７】
以上の実施例を含む実施形態に関し、さらに以下の付記を開示する。
【０１２８】
（付記１）
配線すべき複数の信号線を複数のグループに分けるためのプログラムであって、
コンピュータに、
ユーザから、前記複数の信号線のグループ化の条件の指定を受け付けるステップと、
指定された前記グループ化の条件と、データ格納部に格納されている前記複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、前記複数の信号線のグループ化の処理を切り替えて実施する実施ステップと、
を実行させるためのプログラム。
【０１２９】
（付記２）
前記グループ化の条件が、第１の要件と第２の要件とのうちいずれか、又は第１の要件及び第２の要件を含み且ついずれかを優先させるかを含み、
前記実施ステップが、
前記グループ化の条件が前記第１の要件の指定と前記第１の要件を優先させる指定とのいずれかである場合には、前記複数の信号線の始点端子群と終点端子群との配置パターンに基づき、前記第１の要件を担保するためのグループ化処理を切り替えて実施する第１処理ステップと、
前記グループ化の条件が前記第２の要件の指定と前記第２の要件を優先させる指定とのいずれかである場合には、前記複数のグループ間で線長の分布の偏りを抑えつつ最長線長が短縮されるようにグループ化処理を実施する第２処理ステップと、
を含む付記１記載のプログラム。
【０１３０】
（付記３）
前記配置パターンが、
前記始点端子群を包含する第１の矩形と前記終点端子群を包含する第２の矩形とのいずれかに他方の矩形に包含される端子が存在するという第１のパターンと、
前記第１の矩形と前記第２の矩形とのいずれかに他方の矩形に包含される端子が存在せず且つ前記第１の矩形と前記第２の矩形とが交差する第２のパターンと、
前記第１の矩形と前記第２の矩形とのいずれかに他方の矩形に包含される端子が存在せず且つ前記第１の矩形と前記第２の矩形とが交差しない第３のパターンと、
を含み、
前記第１処理ステップが、
前記第１のパターンの場合には、前記始点端子群と前記終点端子群とを結ぶ線分の方向及び当該線分の交差状態に基づき、前記複数の信号線を分類するための処理を実施するステップと、
前記第２のパターンの場合には、前記第１の矩形と前記第２の矩形とのうち面積が小さいの方の矩形の中心から他方の矩形に含まれる端子までの距離が長い順に前記複数のグループの各々に均等に分散するように、前記複数の信号線を分類するための処理を実施するステップと、
前記第３のパターンの場合には、前記第１の矩形と前記第２の矩形とのうち面積が小さい方の矩形に含まれる端子の位置が、前記複数のグループの各々に均等に分散するように、前記複数の信号線を分類するための処理を実施するステップと、
を含む付記２記載のプログラム。
【０１３１】
（付記４）
指定された前記グループ化の条件が前記第２の要件及び前記第１の要件のうちいずれを優先させるかの指定を含む場合には、仮配線を実施して最長の仮配線長となった信号線を、当該信号線の所属グループ及び交換対象のグループにおける仮配線長及び端子の隣接関係が所定の条件を満たす、前記交換対象のグループの信号線と交換する処理を実施するステップ
を、さらに前記コンピュータに実行させるための付記２記載のプログラム。
【０１３２】
（付記５）
配線すべき複数の信号線を複数のグループに分けるための方法であって、
ユーザから、前記複数の信号線のグループ化の条件の指定を受け付けるステップと、
指定された前記グループ化の条件と、データ格納部に格納されている前記複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、前記複数の信号線のグループ化の処理を切り替えて実施するステップと、
を含み、コンピュータにより実行される方法。
【０１３３】
（付記６）
配線すべき複数の信号線の始点端子群と終点端子群とのデータを格納するデータ格納部と、
ユーザから、前記複数の信号線のグループ化の条件の指定を受け付ける入力部と、
指定された前記グループ化の条件と、データ格納部に格納されている前記複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、前記複数の信号線のグループ化の処理を切り替えて実施する処理部と、
を有する信号線グループ化支援装置。
【符号の説明】
【０１３４】
１００ 配線支援装置
１１０ 処理部
１１１ 制御部
１１２ 第１分類処理部
１１３ 第２分類処理部
１１４ 第３分類処理部
１１５ 信号交換補正処理部
１１６ 第４分類処理部
１１７ 仮配線処理部
１１８ 交差処理部
１１９ 最小全域木処理部
１２０ マンハッタン長処理部
１３０ 第１データ格納部
１４０ 第２データ格納部
１５０ 第３データ格納部
１６０ 入力部
【特許請求の範囲】
【請求項１】
配線すべき複数の信号線を複数のグループに分けるためのプログラムであって、
コンピュータに、
ユーザから、前記複数の信号線のグループ化の条件の指定を受け付けるステップと、
指定された前記グループ化の条件と、データ格納部に格納されている前記複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、前記複数の信号線のグループ化の処理を切り替えて実施する実施ステップと、
を実行させるためのプログラム。
【請求項２】
前記グループ化の条件が、第１の要件と第２の要件とのうちいずれか、又は第１の要件及び第２の要件を含み且ついずれかを優先させるかを含み、
前記実施ステップが、
前記グループ化の条件が前記第１の要件の指定と前記第１の要件を優先させる指定とのいずれかである場合には、前記複数の信号線の始点端子群と終点端子群との配置パターンに基づき、前記第１の要件を担保するためのグループ化処理を切り替えて実施する第１処理ステップと、
前記グループ化の条件が前記第２の要件の指定と前記第２の要件を優先させる指定とのいずれかである場合には、前記複数のグループ間で線長の分布の偏りを抑えつつ最長線長が短縮されるようにグループ化処理を実施する第２処理ステップと、
を含む請求項１記載のプログラム。
【請求項３】
前記配置パターンが、
前記始点端子群を包含する第１の矩形と前記終点端子群を包含する第２の矩形とのいずれかに他方の矩形に包含される端子が存在するという第１のパターンと、
前記第１の矩形と前記第２の矩形とのいずれかに他方の矩形に包含される端子が存在せず且つ前記第１の矩形と前記第２の矩形とが交差する第２のパターンと、
前記第１の矩形と前記第２の矩形とのいずれかに他方の矩形に包含される端子が存在せず且つ前記第１の矩形と前記第２の矩形とが交差しない第３のパターンと、
を含み、
前記第１処理ステップが、
前記第１のパターンの場合には、前記始点端子群と前記終点端子群とを結ぶ線分の方向及び当該線分の交差状態に基づき、前記複数の信号線を分類するための処理を実施するステップと、
前記第２のパターンの場合には、前記第１の矩形と前記第２の矩形とのうち面積が小さいの方の矩形の中心から他方の矩形に含まれる端子までの距離が長い順に前記複数のグループの各々に均等に分散するように、前記複数の信号線を分類するための処理を実施するステップと、
前記第３のパターンの場合には、前記第１の矩形と前記第２の矩形とのうち面積が小さい方の矩形に含まれる端子の位置が、前記複数のグループの各々に均等に分散するように、前記複数の信号線を分類するための処理を実施するステップと、
を含む請求項２記載のプログラム。
【請求項４】
指定された前記グループ化の条件が前記第２の要件及び前記第１の要件のうちいずれを優先させるかの指定を含む場合には、仮配線を実施して最長の仮配線長となった信号線を、当該信号線の所属グループ及び交換対象のグループにおける仮配線長及び端子の隣接関係が所定の条件を満たす、前記交換対象のグループの信号線と交換する処理を実施するステップ
を、さらに前記コンピュータに実行させるための請求項２記載のプログラム。
【請求項５】
配線すべき複数の信号線を複数のグループに分けるための方法であって、
ユーザから、前記複数の信号線のグループ化の条件の指定を受け付けるステップと、
指定された前記グループ化の条件と、データ格納部に格納されている前記複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、前記複数の信号線のグループ化の処理を切り替えて実施するステップと、
を含み、コンピュータにより実行される方法。
【請求項６】
配線すべき複数の信号線の始点端子群と終点端子群とのデータを格納するデータ格納部と、
ユーザから、前記複数の信号線のグループ化の条件の指定を受け付ける入力部と、
指定された前記グループ化の条件と、データ格納部に格納されている前記複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、前記複数の信号線のグループ化の処理を切り替えて実施する処理部と、
を有する信号線グループ化支援装置。
【請求項１】
配線すべき複数の信号線を複数のグループに分けるためのプログラムであって、
コンピュータに、
ユーザから、前記複数の信号線のグループ化の条件の指定を受け付けるステップと、
指定された前記グループ化の条件と、データ格納部に格納されている前記複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、前記複数の信号線のグループ化の処理を切り替えて実施する実施ステップと、
を実行させるためのプログラム。
【請求項２】
前記グループ化の条件が、第１の要件と第２の要件とのうちいずれか、又は第１の要件及び第２の要件を含み且ついずれかを優先させるかを含み、
前記実施ステップが、
前記グループ化の条件が前記第１の要件の指定と前記第１の要件を優先させる指定とのいずれかである場合には、前記複数の信号線の始点端子群と終点端子群との配置パターンに基づき、前記第１の要件を担保するためのグループ化処理を切り替えて実施する第１処理ステップと、
前記グループ化の条件が前記第２の要件の指定と前記第２の要件を優先させる指定とのいずれかである場合には、前記複数のグループ間で線長の分布の偏りを抑えつつ最長線長が短縮されるようにグループ化処理を実施する第２処理ステップと、
を含む請求項１記載のプログラム。
【請求項３】
前記配置パターンが、
前記始点端子群を包含する第１の矩形と前記終点端子群を包含する第２の矩形とのいずれかに他方の矩形に包含される端子が存在するという第１のパターンと、
前記第１の矩形と前記第２の矩形とのいずれかに他方の矩形に包含される端子が存在せず且つ前記第１の矩形と前記第２の矩形とが交差する第２のパターンと、
前記第１の矩形と前記第２の矩形とのいずれかに他方の矩形に包含される端子が存在せず且つ前記第１の矩形と前記第２の矩形とが交差しない第３のパターンと、
を含み、
前記第１処理ステップが、
前記第１のパターンの場合には、前記始点端子群と前記終点端子群とを結ぶ線分の方向及び当該線分の交差状態に基づき、前記複数の信号線を分類するための処理を実施するステップと、
前記第２のパターンの場合には、前記第１の矩形と前記第２の矩形とのうち面積が小さいの方の矩形の中心から他方の矩形に含まれる端子までの距離が長い順に前記複数のグループの各々に均等に分散するように、前記複数の信号線を分類するための処理を実施するステップと、
前記第３のパターンの場合には、前記第１の矩形と前記第２の矩形とのうち面積が小さい方の矩形に含まれる端子の位置が、前記複数のグループの各々に均等に分散するように、前記複数の信号線を分類するための処理を実施するステップと、
を含む請求項２記載のプログラム。
【請求項４】
指定された前記グループ化の条件が前記第２の要件及び前記第１の要件のうちいずれを優先させるかの指定を含む場合には、仮配線を実施して最長の仮配線長となった信号線を、当該信号線の所属グループ及び交換対象のグループにおける仮配線長及び端子の隣接関係が所定の条件を満たす、前記交換対象のグループの信号線と交換する処理を実施するステップ
を、さらに前記コンピュータに実行させるための請求項２記載のプログラム。
【請求項５】
配線すべき複数の信号線を複数のグループに分けるための方法であって、
ユーザから、前記複数の信号線のグループ化の条件の指定を受け付けるステップと、
指定された前記グループ化の条件と、データ格納部に格納されている前記複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、前記複数の信号線のグループ化の処理を切り替えて実施するステップと、
を含み、コンピュータにより実行される方法。
【請求項６】
配線すべき複数の信号線の始点端子群と終点端子群とのデータを格納するデータ格納部と、
ユーザから、前記複数の信号線のグループ化の条件の指定を受け付ける入力部と、
指定された前記グループ化の条件と、データ格納部に格納されている前記複数の信号線の始点端子群と終点端子群との配置パターンとに基づいて、前記複数の信号線のグループ化の処理を切り替えて実施する処理部と、
を有する信号線グループ化支援装置。
【図１】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３Ａ】
【図３Ｂ】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図８Ｄ】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６Ａ】
【図１６Ｂ】
【図１６Ｃ】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５Ａ】
【図２５Ｂ】
【図２５Ｃ】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１Ａ】
【図３１Ｂ】
【図３２】
【図３３】
【図３４】
【図３５Ａ】
【図３５Ｂ】
【図３５Ｃ】
【図３６Ａ】
【図３６Ｂ】
【図３６Ｃ】
【図３７】
【図３８】
【図３９】
【図４０】
【図４１】
【図４２】
【図４３Ａ】
【図４３Ｂ】
【図４４】
【図４５】
【図４６】
【図４７】
【図４８】
【図４９】
【図５０】
【図５１】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図３Ａ】
【図３Ｂ】
【図４Ａ】
【図４Ｂ】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図８Ｃ】
【図８Ｄ】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６Ａ】
【図１６Ｂ】
【図１６Ｃ】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２５Ａ】
【図２５Ｂ】
【図２５Ｃ】
【図２６】
【図２７】
【図２８】
【図２９】
【図３０】
【図３１Ａ】
【図３１Ｂ】
【図３２】
【図３３】
【図３４】
【図３５Ａ】
【図３５Ｂ】
【図３５Ｃ】
【図３６Ａ】
【図３６Ｂ】
【図３６Ｃ】
【図３７】
【図３８】
【図３９】
【図４０】
【図４１】
【図４２】
【図４３Ａ】
【図４３Ｂ】
【図４４】
【図４５】
【図４６】
【図４７】
【図４８】
【図４９】
【図５０】
【図５１】
【公開番号】特開２０１３−７３５８５（Ｐ２０１３−７３５８５Ａ）
【公開日】平成２５年４月２２日（２０１３．４．２２）
【国際特許分類】
【出願番号】特願２０１１−２１４４６５（Ｐ２０１１−２１４４６５）
【出願日】平成２３年９月２９日（２０１１．９．２９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２５年４月２２日（２０１３．４．２２）
【国際特許分類】
【出願日】平成２３年９月２９日（２０１１．９．２９）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]