(57)【要約】【課題】対話型の配線設計を行う際、基板全体にわたる大域な配線経路設計が容易で、容易にフィージビリティ・スタディが実施できる対話型フロアプランナ装置を提供する。【解決手段】ディスプレイに表示された接続端子間を連結するラッツネストを、マウス操作により自在に折り曲げディスプレイ表示させるラッツネスト変形表示手段を備える。設計者は、ディスプレイの各ラッツネストを、自由に折曲表示させ、この変形ラッツネストを使用して全体の配線位相経路の設計を行う。これにより全体の概略配線経路を図形として直感的に容易に視認することができ設計効率が上がる。また、位相配線経路を、折れ曲りラッツネストという形で具体的にディスプレイに視覚化することで、フィージビリティ・スタディの実施ができる。【選択図】        図１
2006039782.tif 000002
【特許請求の範囲】
【請求項１】
回路のレイアウト設計において、対話配線により配線設計を行うための対話型フロアプランナ装置であって、
ディスプレイ上に表示された接続端子間を連結するラッツネストを、マウスその他のポインティングデバイスの入力操作により自在に折り曲げてディスプレイ上に表示させるラッツネスト変形表示手段を備えていることを特徴とする対話型フロアプランナ装置。
【請求項２】
前記ラッツネスト変形表示手段は、
ディスプレイ上に表示されたラッツネストの中から、変形処理の対象となるラッツネスト（以下、「対象ラッツネスト」という。）を選択する変形ラッツネスト選択手段と、
前記対象ラッツネスト上に折曲点を設定し、当該折曲点をディスプレイ上に表示する折曲点設定手段と、
前記折曲点のうち、マウスその他のポインティングデバイスのクリックにより選択された折曲点（以下、「対象折曲点」という。）をドラッグによってディスプレイ上に移動表示し、ドロップによって当該対象折曲点の移動後の位置を確定する折曲点移動手段と、
前記折曲点移動手段によって前記対象折曲点が移動表示されるのに伴い、前記対象ラッツネストを前記各折曲点において折れ曲がった折線としてディスプレイ上に再表示するラッツネスト変形手段と、
を備えていることを特徴とする請求項１記載の対話型フロアプランナ装置。
【請求項３】
前記折曲点設定手段は、前記変形ラッツネスト選択手段により選択された対象ラッツネストに対して、当該対象ラッツネストを３分割する２つの折曲点を対象ラッツネスト上に設定することを特徴とする請求項２記載の対話型フロアプランナ装置。
【請求項４】
ディスプレイ上に表示されたラッツネストの中から、ビア打ち処理の対象となるラッツネスト（以下、「ビア打ちラッツネスト」という。）を選択するビア打ちラッツネスト選択手段と、
前記ビア打ちラッツネストに２つの前記折曲点が設定されている場合において、
前記ビア打ちラッツネストの２つの端点のレイヤ属性が同一の作図レイヤである場合には、前記２つの折曲点にビアを設定するとともに、前記２つのビアの間のラッツネスト部分のレイヤ属性を前記端点が属する作図レイヤ以外の作図レイヤに設定する一方、
前記ビア打ちラッツネストの２つの端点のレイヤ属性が異なる作図レイヤである場合には、前記折曲点のうちの一つにビアを設定するとともに、前記ビアにより分割される２つのラッツネスト部分のレイヤ属性を、そのラッツネスト部分の上の前記端点のレイヤ属性に設定するビア設定手段と、
を備えていることを特徴とする請求項１記載の対話型フロアプランナ装置。
【請求項５】
前記ラッツネスト変形表示手段は、
ディスプレイ上に表示された各接続用端子の接続関係を表示するラッツネストの中から、変形処理を行う対象となる一群のラッツネストからなるラッツネスト束（以下、「対象ラッツネスト束」という。）を選択する変形ラッツネスト束選択手段と、
前記対象ラッツネスト束の端点又は折曲点の代表点を設定し、前記各代表点をディスプレイ上に表示する代表点設定手段と、
前記代表点のうち、マウスその他のポインティングデバイスのクリックにより選択されたものをドラッグによってディスプレイ上に移動表示し、ドロップによって当該代表点の移動後の位置を確定する代表点移動手段と、
前記代表点移動手段によって前記代表点が移動されるのに伴い、前記各代表点に対応する前記ラッツネスト束内の各ラッツネストの折曲点（以下、「個別折曲点」という。）を決定する個別折曲点設定手段と、
前記ラッツネスト束内の各ラッツネストを前記個別折曲点において折れ曲がった折線としてディスプレイ上に再表示するラッツネスト束変形手段と、
を備えていることを特徴とする請求項１記載の対話型フロアプランナ装置。
【請求項６】
前記代表点設定手段は、前記ラッツネスト束内の各ラッツネストの始点及び終点の重心を、それぞれ前記始点及び終点の代表点とし、各ラッツネスト束内の各ラッツネストの折曲点の重心をそれぞれ前記折曲点の代表点として算出するものであることを特徴とする請求項５記載の対話型フロアプランナ装置。
【請求項７】
前記個別折曲点設定手段は、前記各折曲点の代表点について、当該代表点に対応するすべての個別折曲点の重心が当該代表点となるように前記個別折曲点の位置座標を決定するものであることを特徴とする請求項５又は６記載の対話型フロアプランナ装置。
【請求項８】
ディスプレイ上に表示された各接続用端子の接続関係を表示するラッツネストの中から、バスの整形処理を行う対象となる複数のラッツネストからなるラッツネスト束（以下、「対象ラッツネスト束」という。）を選択する整形ラッツネスト束選択手段と、
前記ラッツネスト束の一端を始点、他端を終点とし、ラッツネスト束内の各ラッツネストに設定されたビアのうち前記始点の側から第ｉ番目（ｉ＝１，２，…，ｎ−１）のビアを第ｉビア、前記第ｉビアの集合を第ｉビア群、始点と第１ビアとを結ぶ部分ラッツネストを第１部分ラッツネスト、第ｉビア（１≦ｉ≦ｎ−２）と第ｉ＋１ビアとを結ぶ部分ラッツネストを第ｉ＋１部分ラッツネスト、第ｎ−１ラッツネストと終点とを結ぶ部分ラッツネストを第ｎ部分ラッツネスト、ラッツネスト束内のすべての第ｉラッツネスト（１≦ｉ≦ｎ）の束を第ｉラッツネスト束としたとき、第１ビア群から第ｎ−２ビア群にかけて順次、第ｉ部分ラッツネスト群の部分ラッツネストが交差しないように第ｉビア群の各ビアの配置を変更するとともに、第ｎ−２ビア群の配置が決定した場合に、第ｎ−１部分ラッツネスト群の部分ラッツネストが交差せず、かつ第ｎ部分ラッツネスト群の部分ラッツネストが交差しないように第ｎ−１ビア群の各ビアの配置を変更するビア配置変更手段と、
を備えていることを特徴とする請求項１記載の対話型フロアプランナ装置。
【請求項９】
複数のビア配置パターンを記憶するビア配置記憶手段を備え、
前記ビア配置変更手段は、第１ビア群から第ｎ−２ビア群にかけて順次、第ｉ部分ラッツネスト群の部分ラッツネストが交差しないような第ｉビア群の各ビアの配置を前記ビア配置記憶手段に記憶されたビア配置パターンの中から選択するとともに、第ｎ−２ビア群の配置が決定した場合に、第ｎ−１部分ラッツネスト群の部分ラッツネストが交差せず、かつ第ｎ部分ラッツネスト群の部分ラッツネストが交差しないような第ｎ−１ビア群の各ビアの配置を前記ビア配置記憶手段に記憶されたビア配置パターンの中から選択するものである
ことを特徴とする請求項８記載の対話型フロアプランナ装置。
【請求項１０】
コンピュータに読み込んで実行することにより、コンピュータを請求項１乃至９の何れか一記載の対話型フロアプランナ装置として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プリント配線基板、セラミックス配線基板、又はＬＳＩパッケージ等のレイアウト設計を行うためのＣＡＤ（Computer Aided Design：コンピュータ支援設計）装置において、対話配線により配線設計を行うための配線設計技術に関する。
【背景技術】
【０００２】
従来から、プリント配線基板やセラミックス配線基板等に実装する部品の配置は、ＣＡＤ装置を用いて行われている。ＣＡＤ装置の中には、各配置部品間の配線を自動配線により行うものもある。しかし、プリント配線基板などで複雑な配線になると配線設計の困難性が高く、自動配線により十分な設計品質を達成できない場合が多い。そのような場合、対話設計型のＣＡＤ装置（以下、「対話型フロアプランナ装置」という。）が用いられる。
【０００３】
対話型フロアプランナ装置においては、設計者が配線設計をする際、あらかじめ設計された回路情報（ネットリスト等）に基づいて、それぞれの接続すべき端子（以下、「接続端子」という。）の対（以下、「接続端子対」という。）に対して、接続端子対間を連結する細い直線が表示される。この各接続端子間の接続関係を直線的に表示した線分を「ラッツネスト（rats nest：未配線結線）」という。
【０００４】
対話型フロアプランナ装置により配線設計を行う場合、設計者は、これから配線設計を行おうとする一つのラッツネストを選択する。選択したラッツネスト（以下、「対象ラッツネスト」という。）の両端の接続端子が同一の配線レイヤにない場合には、設計者は、まず各接続端子が属する配線レイヤ間を電気的に接続するビア（Via）の挿入を行う。設計者が対話型フロアプランナ装置に対してビアの挿入指示を入力すると、対話型フロアプランナ装置は、ビアを挿入するとともに対象ラッツネストをディスプレイ上から消去する。そして、新たに挿入されたビアを接続端子の一つとして、もとの対象ラッツネストの両端の接続端子と新たに挿入されたビアとを接続するラッツネストを生成し、ディスプレイ上に表示する。このとき、新しく表示されたラッツネストは、同一の配線レイヤを接続するものである。
【０００５】
また、対象ラッツネストの両端の接続端子が同一の配線レイヤに配置されている場合であっても、設計者の判断によっては、当該接続端子対間をあえて複数の配線レイヤを経由する配線で接続する場合がある。かかる場合、設計者は、上述の場合と同様にして、偶数個のビアを挿入する。これにより、設計者はラッツを自分の意図通りの接続端子間を結ぶように修正することができる。
【０００６】
次に、対象ラッツネストの両端の端子が同一の配線レイヤにあり、それらの接続端子間をその配線レイヤ内で配線接続する場合、設計者は、一方の接続端子から出発して他方の接続端子で終端する所定の幅の折線又は曲線（以下、「物理配線」という。）を、対話型フロアプランナ装置に対して入力する。この場合、物理配線は、その周囲にある障害物（例えば、スルーホールランドや表面実装部品の部品搭載パッド等）との間隔（クリアランス）を、常に設計ルールで定められた最小間隔以上に保たなければならない。すなわち、物理配線を作成する際には、常にクリアランスが所定の最小間隔以上であるという制約条件下において、両接続端子間を接続する物理配線を作成する必要がある。
【０００７】
そのため、設計者は、まず配線レイヤに配置された障害物の配置の全体を眺めながら、上記制約条件を満たしつつ適宜周囲の障害物を迂回して両接続端子間を接続することができそうな概略の配線経路（以下、「概略経路」という。）を頭の中で思い描く。そして、思い描いた概略経路に沿って、実際に上記設計ルールを満たすような物理配線を対話型フロアプランナ装置に対して入力するという作業を行う必要がある。
【０００８】
上記対話型フロアプランナ装置に関する公知技術として、特許文献１に記載の対話配線方式がある。この方式では、まず、物理配線を行おうとする２つの接続端子（始点及び終点）を含む領域のビア、端子、既に設計の終わった物理配線（既配線）等の障害物がディスプレイ上に表示される。設計者は、まず、ディスプレイ上の表示を見ながら始点と終点の間の概略経路を入力する。ディスプレイ上には、始点と終点の間にある各種の障害物が表示されているので、設計者は、始点と終点との間でなるべく短くかつ障害物の混雑が少ない部分を通る概略経路を入力することができる。入力された概略経路は、対話型フロアプランナ装置の概略配線記憶部に記憶される。そして、対話型フロアプランナ装置は、始点から終点に向かって、概略配線記憶部に記憶された概略経路に沿って、物理配線の設計を行っている部分を順次拡大表示ウィンドウに拡大して表示する。これにより、煩雑なウィンドウ操作をなくして物理配線の設計効率の向上を図ったものである。
【０００９】
また、他の公知技術として、設計者がこれから物理配線を行おうとする接続端子対間を連結するラッツネストのみを順次表示する対話型フロアプランナ装置がある（特許文献２参照）。このように、物理配線を行おうとする接続端子対間のラッツネストを接続端子対間の物理配線の入力順に従って順番に表示して行くことにより、設計者はラッツネストによる案内に従って物理配線を容易に入力することができる。また、物理配線の入力誤りを防止することができる。
【００１０】
更に、他の公知技術として、対象ラッツネストに対して一方の接続端子（始点）から他方の接続端子（終点）に向かって物理配線の一部が入力されると、対象ラッツネストを、入力が終わった物理配線の先端点と終点とを連結するラッツネストに逐次更新していく方法がある（特許文献３参照）。この場合、ラッツネストの始点及び終点が指し示すものは、接続端子又は物理配線上の特定部分である。この接続端子又は物理配線上の特定部分を総称して「接続点」という。ラッツネストは、常に接続点間を直接結ぶ直線として表示される。対話型フロアプランナ装置は、一対の接続端子間の全体について物理配線が完了した場合には、当該ラッツネストを消去する。そして、設計者は、接続を完了した物理配線を新たな障害物として、別の接続端子間を結ぶラッツネストについて、同様の物理配線設計作業を繰り返す。
【００１１】
尚、対話型フロアプランナ装置において物理配線設計の労力を軽減する方法としては、ラバーバンドを用いて結線処理を行う方法が公知である（特許文献４参照）。この方法は、接続端子数が少ない場合には有効である。しかしながら、近年の各種電子機器の設計においては、一般に接続端子数がきわめて多い場合には、この方法は有効ではないと考えられる。なぜならば、実際の物理配線においては、経路の各線分は、隣接する配線や障害物とのクリアランスを厳密に保つ（ＤＲＶ（design rule violation：設計ルール違反）がない）ように決定する必要がある。従って、物理配線設計の経路決定の過程で設計者はＤＲＶを生じないようにラバーバンドを変形する必要があり、大きな設計労力の軽減とはならない。
【００１２】
そこで、上記欠点を解決する技術として、接続端子又は障害物に対する位相的な位置関係のみを入力することにより、位相物理変換アルゴリズムを用いて物理配線を生成する方法が公知である（例えば、特許文献５、非特許文献１参照）。この方法では、設計者は、物理配線の概略経路の曲がり点を入力する。この曲がり点は、概略経路の接続端子又は障害物に対する位相的な位置関係を表すものであり、必ずしも物理配線が通過しなければならない点を示すものではない。次に、接続端子や接続端子以外の配線禁止領域を含む障害物から円弧状の禁止領域を生成する。そして、概略経路の上記位相的な位置関係に従って、生成された禁止領域を通過しないような最短経路をゴムひもを変形する要領で求めることにより、物理配線を生成する。従って、この技術を使用すれば、設計者が概略経路の入力を完了した時点で、設計者が概略経路により意図した物理経路が設計される。
【特許文献１】特開平５−１０８７６２号公報
【特許文献２】特開平５−２４２２０２号公報
【特許文献３】特開２０００−３５７１８２号公報
【特許文献４】特開平６−１１０９６８号公報
【特許文献５】特開平１０−２１４８９８号公報
【非特許文献１】Wayne Wei-Ming Dai, Tal Dayan and David Staepelaere, "Topological routing in SURF: Generating a rubber-band sketch," Proceedings of the 28th conference on ACM/IEEE design automation, 1991, pp.39-44.
【発明の開示】
【発明が解決しようとする課題】
【００１３】
上述のように、従来の対話型フロアプランナ装置では、一つのラッツネストの始点及び終点が指し示す接続端子間の物理配線を設計するにあたり、設計者は、両接続端子間を直線的に接続したラッツネストのみを手がかりとして、周囲の障害物との間のクリアランスをとった概略経路を想定することが必要とされる。そのため、複雑な思考作業を要し、設計労力が大きく設計時間も長期化する。この問題は、特に、両接続端子間に多くの障害物がある場合には顕著となる。
【００１４】
また、上記従来の対話型フロアプランナ装置は、いずれも複数の物理配線を逐次設計する設計思想のもとに構成されている。すなわち、設計者が物理配線設計を行う場合には、一のラッツネストに注目して、そのラッツネストの始点及び終点が指示する接続端子間の物理配線を行い、それが終わると次のラッツネストに注目して同様の設計を繰り返すという作業を行うことを想定して構成されている。
【００１５】
しかしながら、複数の物理配線を逐次設計する過程において、ある接続端子間の物理配線を設計しようとした場合、先に設計を行った物理配線の一部が障害となり、当該接続端子間については設計ルールを守って物理配線を行うことが不可能な事態に陥ることがある。かかる事態に陥った場合、設計者は、障害となる物理配線（以下、「障害既配線」という。）を引き剥がし、この障害既配線と現在設計中の物理配線（以下、「現配線」という。）とを再設計する必要がある。
【００１６】
この物理配線の再設計に当たっては、設計者は、現配線と障害既配線とをどのような経路で配線すればＤＲＶを回避できるかという観点から、現配線と障害既配線との概略経路を頭の中で描写する。かかる思考作業を補助するために、従来の対話型フロアプランナ装置では、障害既配線の一部を引き剥がしてラッツネストを表示する機能、いったん引き剥がした物理配線をアンドゥ機能によりものと配線完了状態に復帰する機能、仮引き剥がしを行った物理配線の表示を仮想線で残すとともにラッツネストを表示する機能等の思考補助機能が備えられているものが多い。設計者はこれらの思考補助機能を活用して、試行錯誤により、現配線と障害既配線との概略経路について、互いが他の障害とならないような迂回経路を検討し、決定する。そして、改めて決定した概略経路に従って、現配線と障害配線についての物理配線設計を行う。
【００１７】
このように、現配線と障害既配線との再設計を行う場合には、引き剥がしを行った障害既配線に対するラッツネストと現配線に対するラッツネストとの２本の直線を手がかりとして、複数の配線が互いに障害とならないように巧妙に迂曲された複数の概略経路を、同時に頭の中で検討する必要がある。従って、きわめて複雑な思考錯誤が必要となり、設計時間もきわめて長くなる。
【００１８】
また、装置設計の初期段階でのフィージビリティ・スタディにおいては、詳細な回路設計結果までは求めはしないが、設計することが可能であるか否かということだけの判断を早急求められる。しかしながら、従来の対話型フロアプランナ装置では、詳細な物理配線の設計を行った上でなければ、設計可能性についての結論を導出することができないため不効率であるという問題もあった。
【００１９】
尚、上述の位相物理変換アルゴリズムを用いて物理配線を生成する方法（特許文献５、非特許文献１参照）は、個々の物理配線の入力の手間が軽減されるものの、個々の又は複数の物理配線の概略経路を検討する思考労力が軽減されるものではない。また、詳細設計を行うことなくフィージビリティ・スタディを実施できるものでもない。
【００２０】
また、上述の物理配線の設計進行とともにラッツネストを動的に変更する方法（特許文献３参照）を用いれば、ある接続端子間の物理配線の設計を途中まで行った段階で、他の接続端子間の物理配線の設計に移ることも可能である。従って、この対話型フロアプランナ装置を使用すれば、複数の接続端子対について同時並行的に物理配線の設計を成長させていく設計手法を採ることが可能である。具体的には、例えば、基板の左下隅から、物理配線の設計が完了した領域を円弧状に拡大していくという設計戦略を採ることが可能である。かかる設計戦略を採れば、局所的には複数の物理配線の経路を互いに設計ルールとの整合を取りながら最適化を図ることが可能である。しかしながら、この方法では、局所的に物理配線設計の整合性は確保できても、基板全体にわたって鳥瞰的な視点からの整合性を保つことは困難である。従って、結局は、個別又は複数の概略経路について大域的な配線経路の検討を行うための思考労力が軽減されるものではない。また、詳細設計を行うことなくフィージビリティ・スタディを実施できるものでもない。
【００２１】
そこで、本発明の目的は、プリント基板等の配線設計を行う場合に、基板全体にわたって大域な配線経路の設計が容易であり、また詳細設計を行うことなくフィージビリティ・スタディを実施することを可能とする対話型フロアプランナ装置を提供することにある。
【課題を解決するための手段】
【００２２】
本発明に係る対話型フロアプランナ装置の第１の構成は、回路のレイアウト設計において、対話配線により配線設計を行うための対話型フロアプランナ装置であって、ディスプレイ上に表示された接続端子間を連結するラッツネストを、マウスその他のポインティングデバイスの入力操作により自在に折り曲げてディスプレイ上に表示させるラッツネスト変形表示手段を備えていることを特徴とする。
【００２３】
この構成により、設計者は、ディスプレイ上に表示されたそれぞれのラッツネストを、自由に折り曲げて変形し表示させ、この折れ曲げ変形したラッツネストを使用することによって、物理的な配線パターンの概略経路の設計を容易に行うことが可能となる。すなわち、折れ曲げ変形したラッツネストによって、物理配線の概略設計をディスプレイ上に表示させることにより、設計者は配線設計の各時点における概略配線経路の配置を図形として視覚的・直感的に容易に認知することが可能である。そして、設計者は、このような配線経路の概略設計の状態を基板全体にわたって鳥瞰しながら、設計ルールに整合しやすいように接続用端子の配置変更やビアを適宜変更又は配置することが可能となる。結果として、最終的な詳細な物理的配置・物理配線の設計に入る前段階において、物理的に無理のない接続端子やビアの配置、配線の経路等を概略的に設計することが可能となる。従って、レイアウト設計における配線設計の効率を向上させることができる。
【００２４】
また、屈曲するラッツネストを用いて配線経路の概略設計を行うことにより、詳細なレイアウト設計を行うことなく、設計が可能であるか否かについての正確な判断が可能となる。すなわち、位相配線経路が曲げられたラッツネストという形で具体的にディスプレイ上に視覚化されることにより、それが設計者が意図する位相的経路を保ち、かつ設計基準に適合した物理配線に変換することが可能であるか否かを直感的に認識することができ、かつ、そのことを計算により確認することができる。従って、設計者は、詳細設計を行うことなく、フィージビリティ・スタディを実施することが可能となる。
【００２５】
また、従来の位相物理変換アルゴリズムを用いて物理配線を生成する対話型フロアプランナ装置（特許文献５、非特許文献１参照）では、個々の接続端子対間の配線設計のたびに位相物理変換（位相配線から物理配線への変換）を行っていたが、本発明では、回路全体のフィージビリティが確保されるまでは位相物理変換を一度も実行する必要はなく、回路全体のフィージビリティが確保された後に位相物理変換を一回実行すればよい。従って、従来に比べて設計業務の効率化が図られる。
【００２６】
本発明に係る対話型フロアプランナ装置の第２の構成は、前記第１の構成において、前記ラッツネスト変形表示手段は、ディスプレイ上に表示されたラッツネストの中から、変形処理の対象となるラッツネスト（以下、「対象ラッツネスト」という。）を選択する変形ラッツネスト選択手段と、前記対象ラッツネスト上に折曲点を設定し、当該折曲点をディスプレイ上に表示する折曲点設定手段と、前記折曲点のうち、マウスその他のポインティングデバイスのクリックにより選択された折曲点（以下、「対象折曲点」という。）をドラッグによってディスプレイ上に移動表示し、ドロップによって当該対象折曲点の移動後の位置を確定する折曲点移動手段と、前記折曲点移動手段によって前記対象折曲点が移動表示されるのに伴い、前記対象ラッツネストを前記各折曲点において折れ曲がった折線としてディスプレイ上に再表示するラッツネスト変形手段と、を備えていることを特徴とする。
【００２７】
このように、マウス等のポインティングのクリックやドラッグによってラッツネストの折り曲げ操作を可能とすることにより、ディスプレイ上に表示されたラッツネストを見ながらラッツネストの変形を容易に素早く行うことができる。従って、設計者は、余計な入力操作に煩わされることなく、配線設計に集中することができ、設計効率が向上する。
【００２８】
本発明に係る対話型フロアプランナ装置の第３の構成は、前記第２の構成において、前記折曲点設定手段は、前記変形ラッツネスト選択手段により選択された対象ラッツネストに対して、当該対象ラッツネストを３分割する２つの折曲点を対象ラッツネスト上に設定することを特徴とする。
【００２９】
この構成によれば、ラッツネストを折れ曲げ変形する際に、折曲点数を２つとする固定的な形式をもつデータとしたことによって、各ラッツネストごとに折曲点数が異なるというような複雑な状況が生じることが防止される。
【００３０】
また、これによって、複数のラッツネストを一括した束として操作することが容易となる。すなわち、各ラッツネストの折曲点の数は同じなので、設計者は個別の接続端子対にこだわらず、複数のラッツネストを同じ折曲点数のラッツネスト束として変形操作等することが可能となる。
【００３１】
本発明に係る対話型フロアプランナ装置の第４の構成は、前記第１の構成において、ディスプレイ上に表示されたラッツネストの中から、ビア打ち処理の対象となるラッツネスト（以下、「ビア打ちラッツネスト」という。）を選択するビア打ちラッツネスト選択手段と、前記ビア打ちラッツネストに２つの前記折曲点が設定されている場合において、前記ビア打ちラッツネストの２つの端点のレイヤ属性が同一の作図レイヤである場合には、前記２つの折曲点にビアを設定するとともに、前記２つのビアの間のラッツネスト部分のレイヤ属性を前記端点が属する作図レイヤ以外の作図レイヤに設定する一方、前記ビア打ちラッツネストの２つの端点のレイヤ属性が異なる作図レイヤである場合には、前記折曲点のうちの一つにビアを設定するとともに、前記ビアにより分割される２つのラッツネスト部分のレイヤ属性を、そのラッツネスト部分の上の前記端点のレイヤ属性に設定するビア設定手段と、を備えていることを特徴とする。
【００３２】
この構成により、多層基板を設計する際に、ラッツネストの交差が回避できない場合や、接続端子がそれぞれ異なる配線レイヤにある際にも、ラッツネスト上にビアを打つことによって、ラッツネストによる概略経路の設計を容易に行うことができる。
【００３３】
本発明に係る対話型フロアプランナ装置の第５の構成は、前記第１の構成において、前記ラッツネスト変形表示手段は、ディスプレイ上に表示された各接続用端子の接続関係を表示するラッツネストの中から、変形処理を行う対象となる一群のラッツネストからなるラッツネスト束（以下、「対象ラッツネスト束」という。）を選択する変形ラッツネスト束選択手段と、前記対象ラッツネスト束の端点又は折曲点の代表点を設定し、前記各代表点をディスプレイ上に表示する代表点設定手段と、前記代表点のうち、マウスその他のポインティングデバイスのクリックにより選択されたものをドラッグによってディスプレイ上に移動表示し、ドロップによって当該代表点の移動後の位置を確定する代表点移動手段と、前記代表点移動手段によって前記代表点が移動されるのに伴い、前記各代表点に対応する前記ラッツネスト束内の各ラッツネストの折曲点（以下、「個別折曲点」という。）を決定する個別折曲点設定手段と、前記ラッツネスト束内の各ラッツネストを前記個別折曲点において折れ曲がった折線としてディスプレイ上に再表示するラッツネスト束変形手段と、を備えていることを特徴とする。
【００３４】
この構成により、複数のラッツネストを束線として操作することによって、設計者は個別の接続端子対にこだわらず、ラッツネスト束をグループとして捉えた大局的な配線の取り回しの概略経路の設計を容易に行うことが可能となる。
【００３５】
本発明に係る対話型フロアプランナ装置の第６の構成は、前記第５の構成において、前記代表点設定手段は、前記ラッツネスト束内の各ラッツネストの始点及び終点の重心を、それぞれ前記始点及び終点の代表点とし、各ラッツネスト束内の各ラッツネストの折曲点の重心をそれぞれ前記折曲点の代表点として算出するものであることを特徴とする。
【００３６】
このように、ラッツネスト束内の各ラッツネストの始点、終点、及び折曲点の代表点を、これらのラッツネストの始点、終点、及び折曲点の重心とすることにより、代表線（各代表線を通る折線）はラッツネスト束のほぼ中心を通る折線となる。従って、ディスプレイ上に表示される代表点（ハンドル）が、各ラッツネストのどの折曲点に対応するのかを視覚的に容易に認識することができ、操作性が向上する。
【００３７】
本発明に係る対話型フロアプランナ装置の第７の構成は、前記第５又は６の構成において、前記個別折曲点設定手段は、前記各折曲点の代表点について、当該代表点に対応するすべての個別折曲点の重心が当該代表点となるように前記個別折曲点の位置座標を決定するものであることを特徴とする。
【００３８】
このようにして代表点１点の移動に対応してラッツ束の全体を適切に整形しながらも移動されない部分の変化を小さく抑えているので、設計者の意図を超えた変化による思考の妨害を避けながら自動処理による設計の効率が向上する。
【００３９】
本発明に係る対話型フロアプランナ装置の第８の構成は、前記第１の構成において、ディスプレイ上に表示された各接続用端子の接続関係を表示するラッツネストの中から、バスの整形処理を行う対象となる複数のラッツネストからなるラッツネスト束（以下、「対象ラッツネスト束」という。）を選択する整形ラッツネスト束選択手段と、前記ラッツネスト束の一端を始点、他端を終点とし、ラッツネスト束内の各ラッツネストに設定されたビアのうち前記始点の側から第ｉ番目（ｉ＝１，２，…，ｎ−１）のビアを第ｉビア、前記第ｉビアの集合を第ｉビア群、始点と第１ビアとを結ぶ部分ラッツネストを第１部分ラッツネスト、第ｉビア（１≦ｉ≦ｎ−２）と第ｉ＋１ビアとを結ぶ部分ラッツネストを第ｉ＋１部分ラッツネスト、第ｎ−１ラッツネストと終点とを結ぶ部分ラッツネストを第ｎ部分ラッツネスト、ラッツネスト束内のすべての第ｉラッツネスト（１≦ｉ≦ｎ）の束を第ｉラッツネスト束としたとき、第１ビア群から第ｎ−２ビア群にかけて順次、第ｉ部分ラッツネスト群の部分ラッツネストが交差しないように第ｉビア群の各ビアの配置を変更するとともに、第ｎ−２ビア群の配置が決定した場合に、第ｎ−１部分ラッツネスト群の部分ラッツネストが交差せず、かつ第ｎ部分ラッツネスト群の部分ラッツネストが交差しないように第ｎ−１ビア群の各ビアの配置を変更するビア配置変更手段と、を備えていることを特徴とする。
【００４０】
この構成によれば、個別のラッツネストを設計した際にラッツネスト同士が複雑に交差した状態になってしまったような場合に、ビア配置変更手段によって各ラッツネスト同士が交差しないようにビアの再配置を自動的に行うことが可能となる。これにより、細部での視覚的な複雑さに気を取られることなく鳥瞰的な配線構造の最適化を進めることが促進、設計効率が向上し設計時間を短縮することができる。
【００４１】
本発明に係る対話型フロアプランナ装置の第９の構成は、前記第８の構成において、複数のビア配置パターンを記憶するビア配置記憶手段を備え、前記ビア配置変更手段は、第１ビア群から第ｎ−２ビア群にかけて順次、第ｉ部分ラッツネスト群の部分ラッツネストが交差しないような第ｉビア群の各ビアの配置を前記ビア配置記憶手段に記憶されたビア配置パターンの中から選択するとともに、第ｎ−２ビア群の配置が決定した場合に、第ｎ−１部分ラッツネスト群の部分ラッツネストが交差せず、かつ第ｎ部分ラッツネスト群の部分ラッツネストが交差しないような第ｎ−１ビア群の各ビアの配置を前記ビア配置記憶手段に記憶されたビア配置パターンの中から選択するものであることを特徴とする。
【００４２】
これにより特定の方向に直列したビア配置が避けられ大略円形あるいは正方形の領域にビア群をとどめることができるので、そのビア群がバスの連結点であるという構造上の特徴とビア群が必要とする配置領域の大きさを視覚的直感的に把握することができ、それにより鳥瞰的なバス構配線構造の最適化を計ることが促され、設計効率が向上し、設計時間を短縮することができる。
【００４３】
本発明に係るプログラムは、コンピュータに読み込んで実行することにより、コンピュータを上記第１乃至９の何れか一の構成の対話型フロアプランナ装置として機能させることを特徴とする。
【発明の効果】
【００４４】
以上のように、本発明によれば、設計者はディスプレイ上に表示されたそれぞれのラッツネストを自由に折り曲げて変形し表示させることができるため、配線設計の各時点における配線経路の概略的な配置を図形として視覚的・直感的に容易に認知することができる。このように概略配線経路をディスプレイ上に図形表示することにより、従来設計者がすべて頭の中で行っていた概略経路検討作業のうち、最も有望な概略経路を頭に記憶しておくという部分を、対話型フロアプランナ装置が代わって行う。従って、設計者は、ディスプレイ上に明示された概略経路に基づいて、更に配線長の最短化等の改善を検討する作業に、より集中することができる。従って、設計効率が向上し、設計時間を短縮することができる。
【００４５】
また、設計者は、複数の接続端子対についての概略経路を検討する局面において、それぞれの接続端子対について概略経路を試行錯誤する際に、各接続端子対間の概略経路はディスプレイ上に表示記録されるので、概略経路を頭に記憶しておく必要がなくなる。従って、概略経路の設計過程において、概略経路に交差がないか等の検証はディスプレイ上の画像を見れば容易に知ることができるので、設計効率が向上する。
【００４６】
また、ラッツネストで示される概略配線経路をディスプレイ上に図形表示することで、設計者が基板全体にわたる概略配線経路を直感的に鳥瞰することを容易化する。そして、最終的な物理的配置・配線の設計に入る前段階において、ディスプレイ上に表示されたラッツネストによって設計ルールにほぼ整合した物理的な配線パターンの概略設計を行うことが可能となる。これにより、概略設計の段階で、基板全域にわたって物理的に無理のない接続端子やビアの配置、配線の経路等を概略的に設計することができ、レイアウト設計における配線設計の効率を向上させることができる。
【００４７】
さらには、この屈曲するラッツネストを用いて配線経路の概略設計を行うことにより、詳細なレイアウト設計を行うことなく、フィージビリティ・スタディを実施することが可能となる。
【発明を実施するための最良の形態】
【００４８】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【００４９】
図１は、本発明の実施例１に係る対話型フロアプランナ装置の機能的構成を表す図である。本発明の対話型フロアプランナ装置１は、コンピュータプログラムをコンピュータ２により実行することにより実現される。コンピュータ２には、外部入力装置として、ポインティングデバイスの一つであるマウス３が接続され、外部出力装置としてディスプレイ４が接続されている。また、コンピュータ２の内部には、マウス３の操作によるカーソルの制御を行うマウスカーソル制御部５と、ディスプレイ４に表示する画像を記憶するためのグラフィックスメモリ６が内蔵されている。ディスプレイ４は、グラフィックスメモリ６に記憶された画像を表示する。
【００５０】
対話型フロアプランナ装置１は、コンピュータ２の内部の中央演算装置がプログラムを実行することによって実現される。対話型フロアプランナ装置１は、レイアウト情報記憶手段１０、連結情報記憶手段１１、ラッツネスト生成手段１２、ラッツネスト記憶手段１３、レイアウト表示手段１４、ラッツネスト表示手段１５、ラッツネスト変形表示手段１６、ビア打ちラッツネスト選択手段１７、ビア設定手段１８、整形ラッツネスト選択手段１９、ビア配置変更手段２０、及びビア配置記憶手段２１を備えている。
【００５１】
また、ラッツネスト変形表示手段１６は、仮想端子設定手段２９、変形ラッツネスト選択手段３０、折曲点設定手段３１、折曲点移動手段３２、ラッツネスト変形手段３３、変形ラッツネスト束選択手段３４、代表点設定手段３６、代表点移動手段３７、個別折曲点設定手段３８、及びラッツネスト束変形手段３９を備えている。
【００５２】
レイアウト情報記憶手段１０は、部品、接続端子、ビア、既設計の物理配線等の形状及び配置に関する情報（以下、「レイアウト情報」という。）を記憶する。連結情報記憶手段１１は、各接続端子間の連結関係に関する情報（以下、「連結情報」という。）を記憶する。ラッツネスト生成手段１２は、レイアウト情報記憶手段１０に記憶されたレイアウト情報と、連結情報記憶手段１１に記憶された連結情報とに基づいて、ラッツネストを生成し、ラッツネスト記憶手段１３に保存する。ラッツネスト記憶手段１３は、各ラッツネストの始点及び終点の座標を記憶する。
【００５３】
レイアウト表示手段１４は、レイアウト情報記憶手段１０に記憶されたレイアウト情報に基づき、使用者により設定される表示ウィンドウ内に表示するための、使用者により設定される配線レイヤのレイアウト画像を生成し、ディスプレイ４にグラフィックスメモリ６に保存する。ディスプレイ４は、グラフィックスメモリ６に保存されたレイアウト画像を表示する。
【００５４】
ここで、「表示ウィンドウ」とは、設計を行う回路レイアウト全体の一部をディスプレイ４に表示する場合に、ディスプレイに表示する部分を表す窓のことをいう。表示ウィンドウの拡大・縮小又は移動は、通常のＣＡＤ装置と同様に、使用者の操作により自由に行うことができる。また、「配線レイヤ」とは、多層基板の設計を行う際に、配線を行う各層のことをいう。
【００５５】
ラッツネスト表示手段１５は、ラッツネスト記憶手段１３に記憶されたラッツネストに基づき、使用者により設定される表示ウィンドウ内に表示するためのラッツネスト画像を生成し、グラフィックスメモリ６に保存する。ディスプレイ４は、このラッツネスト画像を、レイアウト画像に重ねて表示する。
【００５６】
尚、図１の他の構成部分の機能については、以下の対話型フロアプランナ装置１の動作説明の中で併せて説明する。
【００５７】
次に、本実施例の対話型フロアプランナ装置１を用いた配線設計の、レイアウト設計全体の流れの中の位置づけについて簡単に説明しておく。図２は、実施例１の対話型フロアプランナ装置１を用いたレイアウト設計の流れを表す図である。まず、回路設計工程により設計された回路図（ネットリスト）に基づき、必要な部品を基板上に配置する（Ｓ１）。そして、各部品の接続端子等を基板に接続するためのランドやその他の接続端子を基板上に配置する（Ｓ２）。基板上への部品の配置やランドやその他の接続端子の配置情報及びそれらの形状情報は、レイアウト情報記憶手段１０に記憶される。また、回路設計工程により設計された回路図（ネットリスト）から抽出される各接続端子間の連結情報は、連結情報記憶手段１１に記憶される。
【００５８】
次に、対話型フロアプランナ装置１を用いて、回路設計工程により設計された回路図（ネットリスト）に基づいて、基板上の各接続端子間を連結するラッツネストをディスプレイ４上に表示し、このラッツネストを変形等することにより、各接続端子間の配線の概略経路（位相配線経路）の設計を行う（Ｓ３）。
【００５９】
最後に、位相配線経路に基づき詳細な物理配線の設計を行い（Ｓ４）、次工程に進む。
【００６０】
本実施例に係る対話型フロアプランナ装置１を使用した設計工程は、詳細な物理配線設計を行う前工程として、ラッツネストによる各接続端子間の配線の概略経路の設計を行うことにある。以下、この各接続端子間の位相配線経路の設計について詳細に説明する。
【００６１】
〔１〕個別ラッツネストの変形処理
図３は、実施例１に係る対話型フロアプランナ装置１のラッツネスト変形処理機能に関するフローチャート、図４は、ディスプレイ上に表示されたラッツネストの一例を示す図、図５は、ディスプレイ上に表示されたラッツを折り曲げる操作を表す説明図である。
【００６２】
最初に、レイアウト表示手段１４及びラッツネスト表示手段１５により、部品及び接続端子のレイアウトとラッツネストがディスプレイ４上に表示される。図４はその一例を示している。図４において、灰色で表された図形が部品、既設計の物理配線及び接続端子である。そして、各接続端子間を結ぶ直線がラッツである。
【００６３】
図５（ａ）は図４に示したような接続端子とラッツネストのうち、一対の接続端子４０，４１とそれらを接続する１本のラッツネスト４２を抜き出して模式的に示したものである。
【００６４】
まず、設計者は、メニュー（プルダウン・メニュー、ツールバー・メニュー、ショートカット・メニュー等）の選択又はコントロールキーによる入力により、対話型フロアプランナ装置１の動作状態を、ラッツネスト変形作業モードにする（Ｓ１０）。
【００６５】
そして、設計者は、マウス３により、マウスカーソル４３をラッツネスト４２上に移動させ、ラッツネスト４２をクリックする。これにより、変形ラッツネスト選択手段３０は、マウス３のクリックにより指定されたラッツネスト４２を選択状態とし、ディスプレイ４上の選択されたラッツネスト４２の表示色を、選択状態の表示色に変更する（Ｓ１１）。以下、この選択されたラッツネストを「対象ラッツネスト」という。
【００６６】
次に、対象ラッツネスト４２が選択されると、折曲点設定手段３１は、対象ラッツネスト４２を３等分する点に折曲点４４，４５を設定する。そして、折曲点設定手段３１は、図５（ｂ）に示したように、対象ラッツネスト４２上に設定した折曲点４４，４５をディスプレイ４上に表示する（Ｓ１２）。
【００６７】
次に、設計者は、マウス３を操作して、ディスプレイ４上に表示された折曲点４４，４５の何れか一方にマウスカーソルを合わせクリックし、当該折曲点を移動したい場所までドラッグし、移動先の場所においてドロップする。折曲点移動手段３２は、マウスのクリック時にマウスカーソルが合わされている折曲点が移動対象（以下、この折曲点を「対象折曲点」という。）として選択されたものと判定する（Ｓ１３）。そして、マウス３のドラッグに合わせて（Ｓ１４）、折曲点移動手段３２は対象折曲点をディスプレイ４上に移動表示する。また、それに合わせてラッツネスト変形手段３３は、対象ラッツネスト４２を、各折曲点４４，４５において折れ曲がった折線としてディスプレイ４上に再描画する（Ｓ１５）。そして、マウス３がドロップされると（Ｓ１６）、折曲点移動手段３２は、当該対象折曲点の移動後の位置をドロップ時の位置に確定する。
【００６８】
例えば、図５（ｂ）に示したように、折曲点４４にマウスカーソル４３を合わせてマウス３をクリックし、図５（ｃ）に示したように、マウス３をドラッグしてマウスカーソル４３を移動させる。そうすると、マウスカーソル４３の移動に合わせて折曲点４４が移動するとともに、対象ラッツネスト４２が接続端子４０−折曲点４４−折曲点４５−接続端子４１を結ぶ折線として再描画される。
【００６９】
そして、対象ラッツネスト４２の選択が解除されるまで（Ｓ１７）、以上のステップＳ１３〜Ｓ１５までの動作を繰り返す。
【００７０】
設計者がマウス３を操作してマウスカーソル４３を対象ラッツネスト４２以外の場所に移動させてクリックすると、対象ラッツネスト４２の選択が解除される（Ｓ１７）。これにより、当該ラッツネスト４２の一連の変形処理が終了する。
【００７１】
使用者は、以上のような係る対話型フロアプランナ装置１の変形処理機能を利用して、それぞれのラッツネストについて変形処理を施すことにより、各接続端子間の配線についての概略経路の設計（配線位相設計）を行うことができる。
【００７２】
例えば、ラッツネストの変形処理を行う前において、ディスプレイ４上には図６（ａ）のようなレイアウト及びラッツネストが表示されていたとする。設計者は図６（ａ）の表示画面を見た場合、ラッツネストによって各接続端子間の接続関係を視覚的に認識することができる。
【００７３】
しかしながら、実際の物理配線においては、ラッツネスト同士が交差したりラッツネストと接続端子等の障害物が重なったりした部分において、物理配線同士が重なることなく、これらの障害物を避けて物理配線を引き回す必要がある。また、配線−配線間又は配線−接続端子間のクリアランスを一定の値以上に保つ等の設計基準を充足した物理配線の引き回しを行う必要がある。従って、設計者は、図６（ａ）を見ただけでは、どのように物理配線を引き回せばよいのかを直感的に視認するのは困難である。従って、この状態から直接物理配線の設計を行う場合には、設計者は頭の中で回路全体の各物理配線の引き回しの概略経路を想定しながら物理配線の設計を行う必要があり、設計効率は悪い。
【００７４】
また、ラッツネストが混雑した部分では、どの接続端子とどの接続端子とがラッツネストにより接続されているのかがわかりにくい。
【００７５】
そこで、各ラッツネストについて上述したラッツネストについて変形処理を行い、図６（ｂ）に示したように、各ラッツネストが物理配線の概略経路を示す折線となるように変形する。これにより、設計者は、ディスプレイ上の表示画像をみただけで、回路全体にわたる物理配線の概略経路を容易に視認することが可能となる。従って、設計者は物理配線設計を、図６（ｂ）に折線で示されたラッツネストの配線位相経路を参考に進めればよく、物理配線の設計が極めて容易化される。
【００７６】
また、最初に回路全体にわたって配線位相経路を整合させる設計を行った後に詳細な物理配線の設計を行うため、物理設計の段階において配線経路の整合性がとれなくなるような事態を回避することができる。従って、物理配線の設計段階において、後に設計する物理配線の経路を確保することができなくなり先に設計した既配線を引き剥がして再設計するといった試行錯誤を回避できるため、設計効率が向上する。
【００７７】
また、図６（ａ）の下部付近に示されたように、ラッツネストが混雑した部分は、ラッツネストを折り曲げることによって図６（ｂ）に示したように混雑が解消される。従って、設計者は、どの接続端子とどの接続端子とがラッツネストにより接続されているのかを容易に視認することができるようになる。
【００７８】
更に、折れ曲がるラッツネストを利用して、図６（ｂ）のように回路全体にわたって配線位相経路を整合させる設計を行うことにより、上述したようにフィージビリティ・スタディを行うことが可能である。
【００７９】
尚、一つのラッツネストについて２つ以上の折曲点を設定する場合について、図７を参照しながら補足説明しておく。この場合、上述と同様に、設計者は、マウス３を操作して、マウスカーソル４３を対象ラッツネスト４２上に移動してクリックする。これにより、変形ラッツネスト選択手段３０は、上述のように対象ラッツネストの選択処理を行う。
【００８０】
次に、設計者は、メニューの選択又はコントロールキーの入力により対話型フロアプランナ装置１に対して仮想端子モード移行指示を入力し、ラッツネスト４２上の仮想端子を設定したい場所にマウスカーソル４３を移動させクリックする。
【００８１】
仮想端子設定手段２９は、仮想端子モード移行指示が入力された後に、マウスカーソル４３がラッツネスト４２上の点に位置した状態でマウス３がクリックされると、マウスカーソル４３が位置する点に仮想端子４６を設定し、当該仮想端子４６の位置情報をレイアウト情報記憶手段１０に保存する。そして、仮想端子設定手段２９は、当該仮想端子４６の位置においてラッツネスト４２を二つのラッツネストに分割し、接続端子４０と仮想端子４６とを連結するラッツネスト４２ａ、及び接続端子４１と仮想端子４６とを連結するラッツネスト４２ｂとしてラッツネスト記憶手段１３に保存する（図７（ｂ）参照）。
【００８２】
これにより、ラッツネスト４２は２つのラッツネスト４２ａ，４２ｂとなるので、それぞれのラッツネスト４２ａ，４２ｂに対して、図３で説明したような個別のラッツネストの変形処理を行うことにより、２以上の点においてラッツネストを折り曲げることが可能となる。
【００８３】
尚、ここで「仮想折曲点」とは、大きさが０の仮想的な一種のランドであり、接続端子と同様にレイアウト上に物理的に固定された仮想点である。尚、ビアや仮想折曲点は、配線位相設計において、その位置を変更することが可能である。
【００８４】
〔２〕個別ラッツネストのビア打ち処理
次に、折曲点が設定されているラッツネストに対するビア打ち処理について説明する。図８は、ラッツネストに対するビア打ち処理を表すフローチャート、図９は、ディスプレイ上に表示されたラッツネストに対するビア打ち処理を表す説明図である。
【００８５】
（１）ラッツネスト両端の接続端子が同一の配線レイヤに属する場合
まず、ディスプレイ４上には図９（ａ）に示したように、２つの接続端子４０，４１と、折曲点４４，４５、及び２つの折曲点４４，４５で折れ曲がったラッツネスト４２が表示されているものとする。以下では、ラッツネスト４２の３つの直線部分（部分ラッツネスト）を符号４２−１〜４２−３で表す。部分ラッツネスト４２−１は接続端子４０〜折曲点４４間、部分ラッツネスト４２−２は折曲点４４〜折曲点４５間、部分ラッツネスト４２−３は接続端子４１〜折曲点４５間をそれぞれ連結している。また、図９（ａ）においては、接続端子４０，４１は、ともに同じ配線レイヤに配置されているものとする。
【００８６】
まず、使用者は、マウス３を操作してマウスカーソル４３をラッツネスト４２の上に移動させてクリックする。これにより、ビア打ちラッツネスト選択手段１７は、ラッツネスト４２を選択状態に設定する。このとき、選択状態とされたディスプレイ４上のラッツネストは、選択状態であることが分かるように異なる色で表示される（Ｓ２０）。
【００８７】
次に、設計者は、メニューの選択又はコントロールキーの入力により、ビア打ち指示を入力する（Ｓ２１）。ビア打ち指示が入力された場合、ビア設定手段１８は、選択されたラッツネスト４２の両端の接続端子４０，４１のレイヤ属性をレイアウト情報記憶手段１０から読み出して参照し、両者が同一の配線レイヤにあるか否かを検査する（Ｓ２２）。この場合、接続端子４０，４１は同一の配線レイヤに属しているので、ビア設定手段１８は、２つの折曲点４４，４５の位置にビア４７，４８を設定する。それとともに、ビア設定手段１８は、ラッツネスト４２の中央の部分ラッツネスト４２−２を、接続端子４０，４１が属する配線レイヤとは異なる配線レイヤに移動する（Ｓ２３）。尚、どの配線レイヤに移動するかの規則は、予め決められているものとする。
【００８８】
これにより、ラッツネスト４２はビア４７，４８によって３分割され、ラッツネスト４２ａ，４２ｂ，４２ｃが生成される（図９（ｂ）参照）。そして、各ラッツネスト４２ａ，４２ｂ，４２ｃのそれぞれに、当該ラッツネストを３分割する点に折曲点４４ａ，４５ａ、４４ｂ，４５ｂ、４４ｃ，４５ｃが設定される。
【００８９】
以上の処理により、ビア打ち処理が終了する。
【００９０】
（２）ラッツネスト両端の接続端子が異なる配線レイヤに属する場合
次に、ラッツネスト両端の接続端子が異なる配線レイヤに属する場合のビア打ち処理について説明する。まず、ディスプレイ４上には図９（ｃ）に示したように、接続端子４０，４１と、折曲点４４，４５、及び２つの折曲点４４，４５で折れ曲がったラッツネスト４２が表示されているものとする。以下では、接続端子４０の属する配線レイヤを第１レイヤ、接続端子４１の属する配線レイヤを第２レイヤと呼ぶ。初期状態では、ラッツネスト４２は第１レイヤに属しているものとする。また、上記（１）の場合と同様に、ラッツネスト４２の３つの部分ラッツネストを符号４２−１〜４２−３で表す。
【００９１】
まず、ステップ２０，２１は上記（１）の場合と同様なので省略する。ステップＳ２１において、設計者によりビア打ち指示が入力された場合、ビア設定手段１８は、選択されたラッツネスト４２の両端の接続端子４０，４１のレイヤ属性をレイアウト情報記憶手段１０から読み出して参照し、両者が同一の配線レイヤにあるか否かを検査する（Ｓ２２）。この場合、接続端子４０，４１は異なる配線レイヤに属しているので、ビア設定手段１８は、２つの折曲点４４，４５のうち、ラッツネスト４２と異なる配線レイヤに属する接続端子４１に近い側の折曲点４５の位置にビア４７を設定する。それとともに、ビア設定手段１８は、接続端子４１の側の部分ラッツネスト４２−３を、接続端子４１が属する配線レイヤに移動する（Ｓ２４）。
【００９２】
これにより、ラッツネスト４２はビア４７によって２分割され、ラッツネスト４２ａ，４２ｂが生成される（図９（ｄ）参照）。そして、各ラッツネスト４２ａ，４２ｂのそれぞれに、当該ラッツネストを３分割する点に折曲点４４ａ，４５ａ、４４ｂ，４５ｂが設定される。尚、ラッツネスト４２ａには、既に最初の折曲点４４が設定されているので、この折曲点４４を折曲点４４ａとし、更にもう一つの折曲点４４ｂが、折曲点４４ａとビア４７とを連結する部分ラッツネストを２分割する位置に設定される。
【００９３】
以上の処理により、ビア打ち処理が終了する。
【００９４】
このように、ラッツネストによる配線位相設計の過程で、各ラッツネストに対してビア打ち処理を行うことを可能としたことにより、複数の配線レイヤにまたがった３次元的な配線位相設計を行うことが容易となる。
【００９５】
〔３〕ラッツネスト束の折り曲げ処理
次に、複数のラッツネストを一つの束として取り扱い、まとめて変形処理を行う対話型フロアプランナ装置１の機能について説明する。
【００９６】
図１０は、実施例１に係る対話型フロアプランナ装置１のラッツネスト束変形処理のフローチャート、図１１は、図１０のバス構造の内部認識計算処理のフローチャートである。
【００９７】
まず、設計者は、メニューの選択又はコントロールキーによる入力により、対話型フロアプランナ装置１の動作状態を、ラッツネスト変形作業モードにする（Ｓ３０）。
【００９８】
次に、設計者は、マウス３を操作することにより、ラッツネスト束（又は、可動端子群）を選択する（Ｓ３１）。ここで、「ラッツネスト束」とは、両端の接続端子が互いに近接する一群のラッツネストをいう。また、「可動端子」とは、位相配線経路の設計において動かすことが可能な接続端子をいう。具体的には、ビアや仮想端子等は可動端子であるが、部品取り付け用のパッドやスルーホール等は固定端子（位相配線経路の設計において動かすことができない端子）である。固定端子は、その端子を動かすことによって部品配置まで変更されるため、位相配線経路の設計においては固定とされている。
【００９９】
この操作を図１２を用いて具体的に説明すると、例えば、設計者がマウス３の左ボタンのドラッグで矩形領域を指定する。例えば、図１２の点Ａにおいてマウス３をクリックし、矢印Ｐの方向にドラッグして、点Ｂにおいてドロップする。これにより、点線により表された矩形領域が指定される。
【０１００】
このとき、変形ラッツネスト束選択手段３４は、指定された矩形領域に交差するラッツネストを選択状態とする（図１２（ａ）参照）。以下、この選択されたラッツネスト束のことを「対象ラッツネスト束」という。例えば、図１２（ａ）においては、記号Ｓで示された一群のラッツネストが選択されることになる。
【０１０１】
一方、指定された矩形領域に可動端子が含まれている場合には、当該矩形領域内に含まれる可動端子も選択状態とし、ディスプレイ４上の選択された可動端子の表示色を、選択状態の表示色に変更する（図１２（ｂ）参照）。以下、この選択された一群の可動端子のことを「対象可動端子」という。例えば、図１２（ｂ）においては、斜線で示された一群のビアが選択されることになる。
【０１０２】
ラッツネスト束又は可動端子群が選択されると、次に、選択されたラッツネスト束又は、可動端子群のバス構造の内部認識計算処理が行われる（Ｓ３２）。このバス構造の内部認識計算処理を図１１に示した。
【０１０３】
図１１において、まず、変形ラッツネスト束選択手段３４は、選択された対象ラッツネスト束又は可動端子群のデータの把握を行う（Ｓ４０）。すなわち、変形ラッツネスト束選択手段３４は、レイアウト情報記憶手段１０から、対象ラッツネスト束の各ラッツネストの両端点に位置する接続端子又は可動端子群に属する各接続端子のレイアウトデータを読み出す。
【０１０４】
次に、代表点設定手段３６は、レイアウトデータが読み出された各接続端子を、接続端子の種類（可動端子か固定端子かの類別）及び各接続端子間の距離により分類する（Ｓ４１）。ここで、各接続端子間の距離による分類は、ある接続端子Ａと最も隣接する同種の接続端子Ｂとの距離が所定の閾値以下であれば、接続端子Ａと接続端子Ｂとは同じ端子集合に属するものとするとして分類が行われる。以下では、接続端子の種類及び距離による分類により分けられた端子集合のことを「端子群」という。
【０１０５】
次に、各対象ラッツネストを、それが接続する接続端子が属する端子群対によって分類する（Ｓ４２）。以下では、両端の端子群対により分類された各ラッツネストの集合を、「ラッツネスト群」という。
【０１０６】
（例１）
例えば、ラッツネスト両端の端子対が（表１）のように分類されたとする。
【０１０７】
【表１】
2006039782.tif 000003
【０１０８】
この場合、各ラッツネストは、｛ａ，ｂ，ｃ｝、｛ｄ，ｅ，ｆ｝、｛ｇ，ｈ，ｉ｝のように３つのラッツネスト群に分類される。
（例終わり）
【０１０９】
次に、代表点設定手段３６は、各端子群に対して、その端子群に属する各接続端子の位置の重心を求め、その重心点を当該端子群の代表点（以下、「代表端点」という。）とする（Ｓ４３）。
【０１１０】
そして、代表点設定手段３６は、各ラッツネスト群の２つの折曲点のそれぞれについて重心点を求め、それら２つの重心点を当該ラッツネスト群の２つの折曲点の代表点（以下、「代表折曲点」という。）とする（Ｓ４４）。これらの代表点を連結して、代表線とする。代表点設定手段３６は、求めた各代表点をディスプレイ４上に表示する。以下では、ディスプレイ４上に表示された代表点を「ハンドル」と呼ぶ。
【０１１１】
尚、ラッツネスト群に属するかどうかの判断には、折曲点の位置は考慮されず、各ラッツネストの端点の位置のみが考慮される。これは、次のような理由による。
【０１１２】
現設計状態において、ラッツネストの途中の迂回経路が大きく異なる場合、設計者が今後も各ラッツネストを一つずつ全く別の経路として設計を続行したいのであれば、設計者は片方のラッツネストしか選択しないと考えられる。しかし、逆に、設計者が途中の経路が大きく異なる２本のラッツネストをあえて選択したとすれば、この２本のラッツネストは端点が近いことから、設計者はこの２本のラッツネストを、だいたい互いに寄り沿って進むような新たな経路に設計し直したいという意図を持っているのであろうと推測される。従って、この場合はむしろ両者を対象ラッツネスト束に属するとしたほうが妥当である。従って、対象ラッツネスト束に属するかどうかの判断には、折曲点の位置は考慮しないこととされているのである。
【０１１３】
（例２）
図１３は選択された対象ラッツネスト束及び可動端子群の一例を示す。図１３において四角形で表示された端子が固定端子、円で表示された端子が可動端子である。また、各固定端子又は可動端子間を連結する折線がラッツネストである。
【０１１４】
まず、最初に、代表点設定手段３６は、各接続端子（固定端子及び可動端子）の分類を行う。この場合、固定端子１〜４が固定端子群１、固定端子５，６が固定端子群２、固定端子７，８が固定端子群３、固定端子９〜１２が固定端子群４として分類される。また、可動端子１〜４は可動端子群１に分類される。
【０１１５】
次に、代表点設定手段３６は、各ラッツネストの分類を行う。この場合、各ラッツネストの端子によるラッツネスト群への分類は（表２）のようになる。
【０１１６】
【表２】
2006039782.tif 000004
【０１１７】
最後に、代表点設定手段３６は、各端子群（固定端子群及び可動端子群）の代表点と各ラッツネスト群の折曲点の代表点を算出する。図１３において各代表点は三角形で示されている。尚、図１３に示されたハンドルのうち、折曲点と可動端点に対応する代表点のみが、ハンドルとしてディスプレイ４上に表示される。
（例終わり）
【０１１８】
再び図１０に戻って、ステップＳ３２でバス構造の内部認識計算処理が行われると、ディスプレイ４上にハンドルが表示された状態となる。設計者は、マウス３を操作して、このハンドルのうちの折曲点群又は可動端子群に対応するものの何れかの上にマウスカーソルを移動しクリックすることにより選択する（Ｓ３３）。そして、設計者が当該ハンドルをドラッグすると（Ｓ３４）、代表点移動手段３７は、ハンドルを移動表示する。それに合わせて、当該ハンドルに代表される折曲点群又は可動端子群を移動表示する（Ｓ３５）。更に、ハンドル（代表点）の移動によって影響を受けるラッツネスト群に対して、代表線を更新する（Ｓ３６）。すなわち、代表線を、移動後のハンドル（代表点）を通過する折線に変更する。そして、代表線が変更されたラッツネスト群について、当該ラッツネスト群に属する各ラッツネストを代表線に沿って再描画する（Ｓ３７）。
【０１１９】
設計者は、マウス３によりハンドルを移動させたい位置までドラッグした後、ドロップする。これにより、ハンドルの選択が解除され（Ｓ３８）、当該ハンドルの移動後の位置が確定される。
【０１２０】
その後、設計者は、他のハンドルを移動させたいときには、他のハンドルをマウス３で選択し、ステップＳ３３〜Ｓ３８の動作を繰り返す。ラッツネスト束の折り曲げ処理を終了したい場合には、設計者は、マウスカーソルを対象ラッツネスト束以外の位置に移動させてクリックすることにより、ラッツネスト束の指定を解除し（Ｓ３９）、処理を終了する。
【０１２１】
尚、ステップＳ３７において、代表線が変更された場合にラッツネスト群に属する各ラッツネストを再描画する処理について図１４を参照して補足説明する。
【０１２２】
ラッツネストＡ，Ｂ，Ｃからなるラッツネスト群の代表線をＤとする。ラッツネストＡ，Ｂ，Ｃ及び代表線Ｄの始点をＡ１，Ｂ１，Ｃ１，及びＤ１とし、終点をＡ４，Ｂ４，Ｃ４，及びＤ４とする。また、ラッツネストＡ，Ｂ，Ｃ及び代表線Ｄの始点側の折曲点をＡ２，Ｂ２，Ｃ２，及びＤ２とし、終点側の折曲点をＡ３，Ｂ３，Ｃ３，及びＤ３とする。代表線Ｄの端点Ｄ１，Ｄ４及び折曲点Ｄ２，Ｄ３は、ハンドルとしてディスプレイ４上に表示される。
【０１２３】
今、代表線Ｄの折曲点Ｄ２，Ｄ３の何れかが、上述したマウス３のドラッグ操作により移動されたとする。移動後の状態が、例えば、図１４（ａ）に示した状態であるとする。
【０１２４】
まず、個別折曲点設定手段３８は、各ラッツネストの始点が、代表線Ｄの付近において上からどの順に並んでいるかを調べる。図１４（ａ）の例では、Ａ１，Ｂ１，Ｃ１の順に並んでいる。
【０１２５】
次に、個別折曲点設定手段３８は、それぞれのラッツネストに対して、代表線Ｄに対する目標オフセットの距離を、先に求めた始点の順序と最小配線ピッチとによって定める。図１４の例で、最小配線ピッチを１とすれば、ラッツネストＡの目標オフセットの距離は１、ラッツネストＢの目標オフセットの距離は０、ラッツネストＣの目標オフセットの距離は−１となる。ここで、代表線Ｄからみて、各ラッツネストをそれぞれの目標オフセットの距離だけ上側に離して配線できるとすれば、配線ルールを満たし、且つ移動後の代表線が代表線Ｄに一致する。
【０１２６】
次に、個別折曲点設定手段３８は、それぞれのラッツネストについて、２つの折曲点の座標を以下のようにして計算する。
【０１２７】
まず、ラッツネストＡについて、始点Ａ１側の折曲点Ａ２を次のように計算する。
【０１２８】
半直線Ｐを、始点Ａ１から出発して線分Ｄ１Ｄ２に平行な半直線とする。直線Ｈを代表線Ｄの折曲点Ｄ２における内角の二等分線とする。但し、代表線Ｄが折曲点Ｄ１において逆行する場合（正確には、内角θが−３０°＜θ＜３０°の条件を満たすとき。尚、±３０°という数値はデフォルトであり、ユーザー設定可能であるとする。）は、内角の２等分線に折曲点Ｄ１で直交する直線を、直線Ｈとする。直線Ｒを線分Ｄ２Ｄ３に平行で、線分Ｄ２Ｄ３からラッツネストＡの目標オフセットの距離だけ離れた直線とする。このとき、
（１）代表線Ｄが折曲点Ｄ１で逆行せず、且つ半直線Ｐと直線Ｒとが交点を持つときは、その交点を折曲点Ａ２とする（図１４（ｂ）参照）。
（２）前記（１）の条件を満たさず、半直線Ｐと直線Ｒとが交点を持つときは、その交点を折曲点Ａ２とする（図１４（ｃ）参照）。
（３）上記（１）（２）の何れでもないときは、直線Ｈと直線Ｒの交点を折曲点Ａ２とする（図１４（ｄ）参照）。
【０１２９】
次に、ラッツネストＡについて、終点Ａ４側の折曲点Ａ３は、上述の折曲点Ａ２の求め方を、進行方向を逆にした手順により求める。図１４（ｅ）の例では、折曲点Ａ３も折曲点Ａ２と同様に、半直線Ｐと直線Ｒとの交点として求められている。
【０１３０】
他のラッツネストＢ，Ｃについても、ラッツネストＡと同様にして折曲点の位置を計算する。
【０１３１】
最後に、ラッツネスト束変形手段３９は、各ラッツネストの始点、折曲点、終点を結ぶラッツネストを、ディスプレイ４上に表示する（図１４（ｆ）参照）。
【０１３２】
（例３）
図１５（ａ）のようなラッツネスト束が選択されたとする。図１５（ａ）において、四角形で表示された接続端子は固定端子であり、各固定端子間を結ぶ直線がラッツネストである。このとき、代表点設定手段３６は、図１５（ａ）の三角形で示された２つのハンドルをディスプレイ４上に表示する。このとき、設計者は、２つのハンドルの何れか一方にマウスカーソル４３を移動し、ハンドルをドラッグすることによって、図１５（ｂ）に示されたようにラッツネスト束を一括して折り曲げることができる。
（例終わり）
【０１３３】
（例４）
図１５（ｃ）のようなラッツネスト束が選択されたとする。図１５（ｃ）において、四角形で表示された接続端子は固定端子、丸で表示された接続端子は可動端子であり、各固定端子と可動端子間を結ぶ直線がラッツネストである。このとき、代表点設定手段３６は、図１５（ｃ）の三角形で示された５つのハンドルをディスプレイ４上に表示する。このとき、設計者は、例えば、可動端子に対応するハンドルにマウスカーソル４３を移動し、ハンドルをドラッグすることによって、図１５（ｄ）に示されたように可動端子を一括して移動させるとともに、ラッツネスト束を一括して折り曲げることができる。
（例終わり）
【０１３４】
〔４〕ビアの再配置処理
最後に、複数のビアを配線の位相経路に交差が生じないように一括して再配置を行うビアの再配置処理について説明する。対話型フロアプランナ装置１により折れ曲がったラッツネストを用いて配線位相設計を行う場合、設計の途中で複数のラッツネスト束が互いに交差した状態となったり、ビアやラッツネストのクリアランスは不十分となったりする場合がある。
【０１３５】
例えば、図１６（ａ）のように、固定端子群Ａ、ビア群Ｂ、ビア群Ｃ、固定端子群Ｄの間をラッツネスト群α、β、γにより連結されている場合を考える。各ラッツネスト群は６本のラッツネストから構成されている。ラッツネスト群α，γは第１レイヤ内に配線されており、ラッツネスト群βは第２レイヤ内に配線されている。
【０１３６】
この場合、ビア群Ｂ，Ｃの各ビアは、クリアランスが設計基準を充足しておらず、ラッツネスト群αの各ラッツネストは、ビア群Ｂとの接続部分付近において、クリアランスが設計基準を充足していない。
【０１３７】
そこで、図１６（ｂ）に示すように、ビア群Ｂ，Ｃの各ビアの再配置を行う。図１６（ｂ）では、ビア群Ｂ，Ｃの各ビアはできるだけ分散し、且つ接続するラッツネストが交差しないように配置されている。これにより、ビア群Ｂ，Ｃ及び各ラッツネスト群は、設計基準を充足することができる。このような処理を「ビアの再配置処理」又は「ビアのスタガライズ（千鳥化）処理」という。
【０１３８】
図１７は、本発明の実施例１に係る対話型フロアプランナ装置１のビアの再配置処理を表すフローチャートである。
【０１３９】
まず、設計者は、ビアの再配置を行いたいラッツネスト及び接続端子を指定する（Ｓ５０）。尚、指定の方法については、図３のステップＳ１１又は図１０のステップＳ３１の場合と同様である。ラッツネスト及び接続端子の指定が入力されると、整形ラッツネスト選択手段１９は、指定されたラッツネスト及び接続端子を選択状態とする。
【０１４０】
次に、整形ラッツネスト選択手段１９は、選択状態にあるラッツネスト及び接続端子についてバス構造の内部認識計算処理を行う（Ｓ５１）。このバス構造の内部認識計算処理については、図１１において説明した通りである。この処理によって、選択されたラッツネスト及び接続端子が、その位置と種類によって、ラッツネスト群及び接続端子群に分類される。また、各接続端子群の代表点が計算される。可動端子の代表点と選択されたラッツネスト群の折曲点は、ディスプレイ４上にハンドルとして表示される。
【０１４１】
次に、この状態で設計者は、メニューの選択又はコントロールキーの操作により、ビアのスタガライズ実行指示を入力する（Ｓ５２）。
【０１４２】
ビア配置変更手段２０は、ビアのスタガライズ実行指示が入力されると、ラッツネストの並び順に自由度があるか否かを判定する。ここで、「ラッツネストの並び順の自由度の有無」とは、一連のラッツネストにより表される接続端子の接続関係を変えることなくラッツネストの並び順のみを入れ替えることができる区間があるか否かをいう。
【０１４３】
例えば、図１８（ａ）のようなラッツネスト束の場合、接続端子Ａｉ，Ｂｉ，Ｃｉ，Ｄｉ（ｉ＝１，２，３，４，５）が、それぞれ、ラッツネストαｉ，βｉ，γｉで接続されている。接続端子Ａｉ，Ｄｉ（ｉ＝１，２，３，４，５）は固定端子であり、接続端子Ｂｉ，Ｄｉ（ｉ＝１，２，３，４，５）は可動端子である。この場合、ラッツネストの並び順は、（α１，α２，α３，α４，α５），（β１，β２，β４，β３，β５），（γ１，γ２，γ４，γ３，γ５）である。一方、図１８（ｂ）のように、各接続端子間の接続関係は変えずに、可動端子の並べ替えを行った場合、ラッツネストの並び順は、（α１，α２，α３，α４，α５），（β１，β４，β２，β３，β５），（γ１，γ２，γ４，γ３，γ５）となる。このように、接続端子の接続関係を変えることなくラッツネストの並び順のみを入れ替えることができる区間がある場合、「ラッツネストの並び順の自由度がある」という。
【０１４４】
一方、図１８（ｃ）のような場合には、接続端子の接続関係を変えることなくラッツネストの並び順のみを入れ替えることはできない。この場合、可動端子を動かして無理にラッツネストの順番を変えようとすると、ラッツネストが交差してしまい配線の位相関係が変化するので、ラッツネストの並び順を入れ替えることは不可能である。
【０１４５】
要するに、両端の接続端子が可動端子であるようなラッツネストからなるラッツネスト群がある場合にはラッツネストの並び順の自由度があり、そのようなラッツネスト群がない場合にはラッツネストの並び順の自由度がないといえる。
【０１４６】
ステップＳ５３において、ラッツネストの並び順の自由度がないと判定された場合には、後述のステップＳ５５に移る。
【０１４７】
一方、ステップＳ５３において、ラッツネストの並び順の自由度があると判断された場合には、ビア配置変更手段２０は、並べ替えが可能なラッツ群が連結する何れか一つのビア群の並び順を数通り生成する。そして、その中でビアが最も拡散して配置されるようなラッツネストの並び順を求める（Ｓ５４）。
【０１４８】
次に、ビア配置変更手段２０は、各ラッツネスト群の代表線に沿うように各ラッツネストの経路を再計算する。そして、再計算により得られる各ラッツネストの交点にビアを配置し、処理を終了する（Ｓ５５）。
【０１４９】
以上のようなビアの再配置処理を行うことで、一群のビアについて、クリアランスが最大となるようなビアの配置を自動的に行うことができるので、設計者の配線位相経路の設計が容易化される。
【０１５０】
ここで、ステップＳ５４の処理について、補足説明を行う。ビアの再配置処理では、ビア配置変更手段２０は、選択されたラッツネスト群及びビア群に関係するラッツネスト群及びビア群を、まず、固定端子によりネット（信号）の並び順が固定されたラッツネスト束と、両端が可動端子（ビア）であるラッツネスト束とに分類する。ここでは便宜上、ネットの並び順が固定されたラッツネスト束の向きを垂直とし、このラッツネスト束を「垂直チャネル（垂直トラック束）」と呼ぶ。また、両端が可動端子（ビア）であるラッツネスト束の向きを、便宜上、水平とし、このラッツネスト束を「水平チャネル（水平トラック束）」と呼ぶ。ビア配置変更手段２０は、垂直チャネルと水平チャネルとがはしご状に連結した部分構造に分割して認識する。
【０１５１】
例えば、図１９（ａ）のようなラッツネスト束及び接続端子が選択されているとする。この場合、接続端子群Ｆ１，Ｆ２，Ｆ３は固定端子群、接続端子群Ｍ１，Ｍ２，Ｍ３は可動端子群である。従って、ラッツネスト群Ｖ１，Ｖ２，Ｖ３が垂直チャネル、ラッツネスト群Ｈ１，Ｈ２が水平チャネルとして認識される。そして、ビア群Ｍ１，Ｍ２，Ｍ３の部分構造が図１９（ｂ）に示したようなはしご型構造として分割認識される。図１９（ｂ）の水平及び垂直の直線を「トラック」という。
【０１５２】
そして、ビア配置変更手段２０は、各部分構造において、水平チャネルと各垂直チャネルの交点部分にあたるビア群Ｍ１，Ｍ２，Ｍ３のそれぞれについて、ビアの並びを以下のようにして定める。
【０１５３】
水平チャネルでは、トラックへのネットの割り当ては自由である。但し、水平トラック全体を非交差に配線するためには、直列接続された水平方向のラッツネスト群を通して、同じトラックには同じネットを割り当てる必要がある。また、各水平トラックに対してある順番でネットの割り当てを行った場合、各ビア群の部分においてビアを置く位置は、同じネットが割り当てられた水平トラックと垂直トラックとの交点に決定される。逆に、そのような位置にビアを打てば、水平トラックに対してネットの割り当てをどのような順番に決定しても、水平トラックと垂直トラックとは、ともに交差せずに配線することが可能であることが保証される。
【０１５４】
また、上記性質により、各ビア群においてビアの配置を独立に決定することはできないことが分かる。すなわち、水平トラックへのネットの割り当てを任意であるとすれば、水平トラックに対してある順序でネットを割り当てた場合、各ビア群におけるビア配置は一意的に定まる。換言すれば、すべてのビア群に対してビア配置を決定することは、水平トラックに対するネットの割り当ての順序をある一つの順序に決定することと等価である。従って、ビア配置変更手段２０は、水平トラックに対するネットの割り当ての順序を決定すればよい。
【０１５５】
水平トラックに対するネットの割り当ては、各ビア群における「ビア分散指標」の合計を最小化するように行われる。ここで、各ビア群における「ビア分散指標」は、（数１）で定義される。
【０１５６】
【数１】
2006039782.tif 000005
【０１５７】
ここで、α１，α２はユーザ設定可能な重み係数であり、デフォルトではα１＝１，α２＝０．１に設定されているものとする。
【０１５８】
ｄｍｉｎは隣接する垂直トラック上のビアの垂直位置の差ｄの最小値である。すなわち、あるビア群Ｍに属するビアをｂｉ（ｉ＝１，２，…，ｎ）とすると、ｄｍｉｎは（数２）により表される。
【０１５９】
【数２】
2006039782.tif 000006
【０１６０】
例えば、図１９（ｂ）では、ｂ１＝（０，４），ｂ２＝（１，３），ｂ３＝（２，２），ｂ４＝（３，０），ｂ５＝（４，１）なので、左から、ｄは１，１，２，１となる。従って、ｄｍｉｎ＝１である。
【０１６１】
ｎｔｈｒｅｅｓは、斜めに連続して３つ並ぶ場合の数である。例えば、図１９（ｂ）では、ｎｔｈｒｅｅｓ＝１、図１９（ｃ）では、ｎｔｈｒｅｅｓ＝３である。
【０１６２】
（数１）の指標を用いると、図１９（ｄ）のような配置が最もよい配置として認識される。そこで、次にビア分散指標の最小化を図るようなネットの割り当て方法について説明する。
【０１６３】
まず、総当たり計算をしても計算時間があまり多くならない場合（具体的には、水平トラック数がｎｍｉｎ以下の場合。ｎｍｉｎはユーザ設定可能であり、デフォルトはｎｍｉｎ＝３）には、水平トラックへのネットの割り当ての仕方をすべて列挙し、その中で各ビア群におけるビア分散指標の合計が最小となるネットの割り当てを決定する。尚、水平トラックの本数をｋ本とすると、ネットの割り当ての仕方はｋ！通りあることになる。
【０１６４】
総当たり計算では時間がかかりすぎる場合（具体的には、水平トラック数がｎｍｉｎより大きい場合）には、トラック数が最も多い垂直トラックに接続されたビア群を任意に選び、そのビア群にとってビア分散指標が小さくなるビア配置候補を所定数だけ列挙する。尚、この列挙の方法については後述する「水平チャネルネット割り当て候補作成手法」を使用する。そして、それぞれのビア配置候補について、対応する水平チャネルに対してネットを割り当て、他のビア群におけるビア配置を求め、前述のビア分散指標の合計値を計算する。そして、求められるビア分散指標の合計が最小となるようなビア配置候補を選択し、このビア配置候補に対応するネットの割り当て及び各ビア群におけるビア配置を決定する。
【０１６５】
以上のようにして、ビア配置を決定した結果、例えば、図１９（ａ）の各ビア群の配置は図１９（ｅ）のように再配置される。
【０１６６】
〔水平チャネルネット割り当て候補作成手法〕
水平トラック数をｎとする。配置ピッチｐを（数３）により定義する。
【０１６７】
【数３】
2006039782.tif 000007
【０１６８】
水平チャネルネット割り当て候補はｐ個生成する。垂直トラック数はｎ以下であることが、全体アルゴリズムにおいて構造を抽出する際に保証されている。
【０１６９】
候補ｉ（ｉ＝１，２，…，ｎ）を作成するには、まず左端垂直トラック上で、下端からｐ番目の水平トラック位置にビアを配置する。次に、その右側の垂直トラックに注目し、先にビアを配置した水平トラックよりもｐだけ上の水平トラックにビアを配置する。この作業を順次繰り返す。但し、最上の水平トラックを越えた場合には、先ほどより水平トラック位置を１段下げた位置に配置する。このようにして、すべての垂直トラックについてビア位置を決定する。
【０１７０】
このように、各候補においてすべての垂直トラックについてビアが配置される。但し、垂直トラック数が水平トラック数よりも少ない場合には、水平トラックにはビアが配置されないものが残る。そのような水平トラックがある場合には、その水平トラックには残りのネットをランダムに割り当てる。
【０１７１】
（例５）
図２０は、水平トラック数ｎが９、垂直トラック数も９の例について作成される３つの候補を示す。図２０（ａ）では、左端の垂直トラック上で、まず最も下の水平トラック上にビアｂ１が配置される。次に、その右の垂直トラックでは、ビアｂ１よりもｐ＝３だけ上の水平トラックの位置にビアｂ２が配置される。更にその右の垂直トラックでは、ビアｂ２よりもｐ＝３だけ上の水平トラックの位置にビアｂ３が配置される。左から４番目の垂直トラックでは、あらためて水平トラックの下方に回り込み、先ほどよりも１段下の位置に同様にビアを配置する。
【０１７２】
図２０（ｂ）（ｃ）の候補では、左端の垂直トラックにおけるビアの水平位置を、一ずつずらしながら候補を作成している。
（例終わり）
【０１７３】
以上のようにして候補を作成することで、ここで選ばれたビア群については、少なくとも理想に近い（クリアランスが最も大きくなる）ビア配置が保証されることになる。また、複数の候補が作成されるため、他のビア群についてのビア配置も、ある程度分散した配置となることが期待される。更に、候補がｎの平方根数しか作られないので、計算スピードも高速化される。
【０１７４】
尚、ここでは、ビア群におけるビアの配置候補は計算により生成する例を示したが、水平トラック数に応じてビア配置記憶手段２１に予め記憶されているビア配置を読み出して使用する構成としてもよい。
【図面の簡単な説明】
【０１７５】
【図１】本発明の実施例１に係る対話型フロアプランナ装置の機能的構成を表す図である。
【図２】実施例１の対話型フロアプランナ装置１を用いたレイアウト設計の流れを表す図である。
【図３】実施例１に係る対話型フロアプランナ装置１の変形処理機能に関するフローチャートである。
【図４】ディスプレイ上に表示されたラッツネストの一例を示す図である。
【図５】ディスプレイ上に表示されたラッツネストを折り曲げる操作を表す説明図である。
【図６】ラッツネストの変形処理による配線位相設計の例を表す図である。
【図７】ディスプレイ上に表示されたラッツネストに２以上の折曲点を設定する場合を表す説明図である。
【図８】ラッツネストに対するビア打ち処理を表すフローチャートである。
【図９】ディスプレイ上に表示されたラッツネストに対するビア打ち処理を表す説明図である。
【図１０】実施例１に係る対話型フロアプランナ装置１のラッツネスト束変形処理のフローチャートである。
【図１１】図１０のバス構造の内部認識計算処理のフローチャートである。
【図１２】ラッツネスト束及び可動端子群を選択する操作を説明する図である。
【図１３】選択された対象ラッツネスト束及び可動端子群の一例を示す図である。
【図１４】代表折曲点が移動された場合にラッツネスト群に属する各ラッツネストを再描画する処理を説明する図である。
【図１５】ラッツネスト束変形処理の例を説明する図である。
【図１６】ビアの再配置処理の概要を説明する図である。
【図１７】本発明の実施例１に係る対話型フロアプランナ装置１のビアの再配置処理を表すフローチャートである。
【図１８】ラッツネストの並び順の自由度について説明する図である。
【図１９】ビアの再配置処理の説明図である。
【図２０】水平トラック数９、垂直トラック数９の場合のビア配置候補を示す図である。
【符号の説明】
【０１７６】
１  対話型フロアプランナ装置
２  コンピュータ
３  マウス
４  ディスプレイ
５  マウスカーソル制御部
６  グラフィックスメモリ
１０  レイアウト情報記憶手段
１１  連結情報記憶手段
１２  ラッツネスト生成手段
１３  ラッツネスト記憶手段
１４  レイアウト表示手段
１５  ラッツネスト表示手段
１６  ラッツネスト変形表示手段
１７  ビア打ちラッツネスト選択手段
１８  ビア設定手段
１９  整形ラッツネスト選択手段
２０  ビア配置変更手段
２１  ビア配置記憶手段
２９  仮想端子設定手段
３０  変形ラッツネスト選択手段
３１  折曲点設定手段
３２  折曲点移動手段
３３  ラッツネスト変形手段
３４  変形ラッツネスト束選択手段
３６  代表点設定手段
３７  代表点移動手段
３８  個別折曲点設定手段
３９  ラッツネスト束変形手段
４０，４１  接続端子
４２，４２ａ，４２ｂ  ラッツネスト（対象ラッツネスト）
４２−１〜４２−３  部分ラッツネスト
４３  マウスカーソル
４４，４４ａ，４４ｂ，４４ｃ，４５，４５ａ，４５ｂ，４５ｃ，４７，４８，４９，５０  折曲点
４６  仮想端子
４７，４８  ビア
【図１】
2006039782.tif 000008
【図２】
2006039782.tif 000009
【図３】
2006039782.tif 000010
【図４】
2006039782.tif 000011
【図５】
2006039782.tif 000012
【図６】
2006039782.tif 000013
【図７】
2006039782.tif 000014
【図８】
2006039782.tif 000015
【図９】
2006039782.tif 000016
【図１０】
2006039782.tif 000017
【図１１】
2006039782.tif 000018
【図１２】
2006039782.tif 000019
【図１３】
2006039782.tif 000020
【図１４】
2006039782.tif 000021
【図１５】
2006039782.tif 000022
【図１６】
2006039782.tif 000023
【図１７】
2006039782.tif 000024
【図１８】
2006039782.tif 000025
【図１９】
2006039782.tif 000026
【図２０】
2006039782.tif 000027