JP5776413B2 - 回路設計支援装置、回路設計支援方法および回路設計支援プログラム - Google Patents

Description

本発明は回路設計支援装置、回路設計支援方法および回路設計支援プログラムに関する。

ＢＧＡ（Ball Grid Array）のピン間を配線するバスについて、所属するネット（論理接続情報）の引き出し経路を１ネットずつ探索して、バス内の全てのネットがＢＧＡ外に脱出できるような配線引き出し経路を決定する技術が知られている。

また、配線複数本分の間隔の総和を配線幅とする１本の仮想配線としてレイアウトした後に仮想配線を配線群に置換する技術が知られている。

特開２００２−２１７３０２号公報

Lijuan Luo、他４名、「B-Escape: A Simultaneous Escape Routing Algorithm Based on Boundary Routing」、International Symposium on Physical Design Proceedings of the 19th international symposium on Physical design San Francisco, California USA 2010年 p.19-25

ピンが密集している場合、仮想配線に含めるネットのピンの候補が近隣に複数存在するため、どのピンのネットをペアにして１つのバスとするべきかの判断が容易ではないという問題があった。

本発明はこのような点に鑑みてなされたものであり、ペアにするネットのピンの判断を容易にする回路設計支援装置、回路設計支援方法および回路設計支援プログラムを提供することを目的とする。

上記目的を達成するために、開示の回路設計支援装置が提供される。この回路設計支援装置は、ペア候補決定部とペア決定部とを有している。
ペア候補決定部は、配線の論理接続情報を有するピンを複数備える第１のピン群と、この第１のピン群の各ピンの配線の接続先となり論理接続情報を有するピンを備える第２のピン群とが与えられたとき、第１のピン群および第２のピン群それぞれにおいて所定距離内にある異なる論理接続情報を有するピン同士をペア候補に決定する。

ペア決定部は、ペア候補決定部が決定したペア候補を用いて第１のピン群および第２のピン群それぞれのピンのペアを決定する。

ペアにするネットのピンの判断を容易にすることができる。

第１の実施の形態の回路設計支援装置を説明する図である。 第２の実施の形態の回路設計支援装置のハードウェア構成を示す図である。 第２の実施の形態の回路設計支援装置の機能を示すブロック図である。 バスピン群記憶部に記憶されている情報を説明する図である。 ピン座標情報記憶部に記憶されている情報の一例を示す図である。 ペア候補グラフ作成部の処理を説明する図である。 ペア候補グラフ作成部の処理を説明する図である。 ペア候補グラフ作成部が作成したグラフを説明する図である。 ペア決定部が作成したグラフを説明する図である。 グラフ管理テーブルを示す図である。 ペア決定部の処理を説明する図である。 ペア決定部の処理を説明する図である。 ペア決定部の処理を説明する図である。 ペア決定部の処理を説明する図である。 ペア決定部の処理を説明する図である。 ペア決定部の処理を説明する図である。 ペア決定部の処理を説明する図である。 グラフの推移を示す図である。 ピンペア情報記憶部に記憶されたターゲットピンのペアに関する情報を説明する図である。 第２の実施の形態のペア候補グラフ作成部およびペア決定部の処理を示すフローチャートである。 テーブル更新処理を示すフローチャートである。 第３の実施の形態のネットリストを示す図である。 第３の実施の形態のペア候補グラフ作成部が作成したグラフを示す図である。 配線スペースが効率よく使える理由を説明する図である。 第４の実施の形態の回路設計支援装置の機能を示すブロック図である。 第４の実施の形態のネットリストを示す図である。 信号種別距離係数記憶部に記憶されている情報を説明する図である。 第４の実施の形態のソースピン距離管理テーブルを示す図である。 第４の実施の形態のターゲットピン距離管理テーブルを示す図である。 第４の実施の形態のペア候補グラフ作成部が作成したグラフを説明する図である。 第４の実施の形態のペア候補グラフ作成部およびペア決定部の処理を示すフローチャートである。 第５の実施の形態の回路設計支援装置の機能を示すブロック図である。 第５の実施の形態のペア候補グラフ作成部の処理を説明する図である。 第５の実施の形態のグラフ管理テーブルを示す図である。 第５の実施の形態のペア決定部の処理を説明する図である。 第５の実施の形態のペア決定部の処理を説明する図である。 第５の実施の形態のペア決定部の処理を説明する図である。 第５の実施の形態のペア決定部の処理を説明する図である。 第５の実施の形態のペア決定部の処理を説明する図である。 第５の実施の形態のペア決定部の処理を説明する図である。 第５の実施の形態のペア決定部の処理を説明する図である。 第５の実施の形態のピンペア情報記憶部に記憶されたターゲットピンのペアに関する情報を説明する図である。 第５の実施の形態のペア候補グラフ作成部およびペア決定部の処理を示すフローチャートである。 第５の実施の形態のテーブル更新処理を示すフローチャートである。

以下、実施の形態の回路設計支援装置を、図面を参照して詳細に説明する。第１の実施の形態において、開示の回路設計支援装置の実施の形態について説明し、その後、第２の実施の形態において、開示の回路設計支援装置をより具体的に説明する。

＜第１の実施の形態＞
図１は、第１の実施の形態の回路設計支援装置を説明する図である。
第１の実施の形態の回路設計支援装置（コンピュータ）１は、プリント配線板（ＰＣＢ）等に配置されたＢＧＡ等の配線設計を支援する装置である。この回路設計支援装置１は、基板情報格納部１ａとペア候補決定部１ｂとペア決定部１ｃと配線部１ｄとを有している。なお、本実施の形態では、回路設計支援装置１が基板情報格納部１ａを有する構成としたが、基板情報格納部１ａは、回路設計支援装置１の外部に設けられていてもよい。

基板情報格納部１ａには、基板の同一層の所定の領域に設定されたバスピン間を接続する配線のネット（論理接続情報）等がリスト化された基板情報が格納されている。図１では、基板情報により具現化された基板２を示している。この基板２は、ＢＧＡを配置する領域２ａ、２ｂを有している。領域２ａには、ネットを有するピンｐ１、ｐ２、ｐ３、ｐ４を備える第１のピン群３と、第１のピン群３の各ピンｐ１、ｐ２、ｐ３、ｐ４の配線の接続先となるネットを有するピンｐ５、ｐ６、ｐ７、ｐ８を備える第２のピン群４とを有している。接続されるネット同士には、同じネット名（Ａ、Ｂ、Ｃ、Ｄ）を示している。以下、例えばネット名Ａのネットを「ネットＡ」と表記する。例えば、同じネットＡの第１のピン群３のピンｐ１と第２のピン群４のピンｐ５が接続される。

ペア候補決定部１ｂは、第１のピン群３および第２のピン群４それぞれにおいてピン間の距離を計測する。例えば基板２では、各ピンの一区画を距離１であるものと仮定すると、ピンｐ１とｐ２の最短距離は１である。ペア候補決定部１ｂは、第１のピン群３および第２のピン群４それぞれにおいて所定の距離内にある同じネットを有するピン同士をペア候補に決定する。図１に示す例では、ピンの距離が２以下のピン同士をペア候補に決定する。第１のピン群３においてピンｐ２とピンｐ４の組み合わせ、つまり、ネットＢとネットＤのピンの組み合わせは距離が２以上であるため、ペア候補から除外する。また、第２のピン群４においてピンｐ５とピンｐ６の組み合わせ、つまり、ネットＡとネットＢのピンの組み合わせは距離が２以上であるため、ペア候補から除外する。この結果、図１におけるペア候補は、ネットＢとネットＤおよびネットＡとネットＢのピンの組み合わせを除外したネットＡとネットＣのピンの組み合わせ、ネットＡとネットＤのピンの組み合わせ、ネットＢとネットＣのピンの組み合わせ、およびネットＣとネットＤのピンの組み合わせの４つになる。図１では、各ネットのピンの組み合わせを、ピン間に直線を配置することで示している。

ところで、ペア候補決定部１ｂは、第１のピン群３において所定の距離内にあるピン同士を計測した後に、第１のピン群３においてピンの距離が２以下のネットのピンについてのみ、ピン間の距離を計測するのが好ましい。この処理によって、ピンの距離を計測する回数を減らすことができる。

ペア決定部１ｃは、ペア候補決定部１ｂが決定したペア候補を用いて第１のピン群３および第２のピン群４それぞれのピンのペアを決定する。ここで、ペア候補決定部１ｂが決定したペア候補は、それぞれのピン間隔が所定距離内にある。従って、ペア決定部１ｃが、ペア候補に基づきペアを決定することで、ペア間に行った配線に他のペアの配線が入り込んでしまう可能性を減らすことができる。例えば、第１のピン群３側のピン間の距離が短くなる組み合わせを考慮してピンｐ１、ｐ２と、ピンｐ３、ｐ４をペア候補に決定し、第２のピン群４側のピンｐ５、ｐ６とピンｐ７、ｐ８を最短距離で配線すると、配線が重なってしまう。このため、最短距離で配線をすることができない。

ペア決定部１ｃは、第１のピン群３と第２のピン群４のうちいずれか一方のピン群の各ペア候補について、隣接するペア候補の数が少ないペア候補を優先してペアに決定するのが好ましい。この処理により、他のピンのペアの成立に影響を及す可能性が低いピンを優先してペアに決定することで、ペアを成立する機会を増やすことができる。図１では、例えば、ピンｐ２は、ピンｐ３以外のペア候補が存在しないので、ピンｐ２とピンｐ３の組み合わせを最初にペアに決定するのが好ましい。この結果、ネットＢとネットＣのピンがペアになるので、残りのネットＡとネットＤのピンがペアになる。図１では、決定したペアを示している。

配線部１ｄは、ペア決定部１ｃが決定したピンのペアを接続する配線を行う。具体的には、領域２ａのピンのペアと領域２ｂのピンのペアを１つの配線で仮想的に接続した後にネットそれぞれの配線を行う。図１では、配線部１ｄが行った配線の一例を示している。

なお、ペア候補決定部１ｂ、ペア決定部１ｃおよび配線部１ｄは、回路設計支援装置１が有するＣＰＵ（Central Processing Unit）が備える機能により実現することができる。また、基板情報格納部１ａは、回路設計支援装置１が有するＲＡＭ（Random Access Memory）やハードディスクドライブ（ＨＤＤ:Hard Disk Drive）等が備えるデータ記憶領域により実現することができる。

＜第２の実施の形態＞
図２は、第２の実施の形態の回路設計支援装置のハードウェア構成を示す図である。
回路設計支援装置１０は、ＣＰＵ１０１によって装置全体が制御されている。ＣＰＵ１０１には、バス１０８を介してＲＡＭ１０２と複数の周辺機器が接続されている。

ＲＡＭ１０２は、回路設計支援装置１０の主記憶装置として使用される。ＲＡＭ１０２には、ＣＰＵ１０１に実行させるＯＳ（Operating System）のプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、ＣＰＵ１０１による処理に使用する各種データが格納される。

バス１０８には、ハードディスクドライブ１０３、グラフィック処理装置１０４、入力インタフェース１０５、ドライブ装置１０６、および通信インタフェース１０７が接続されている。

ハードディスクドライブ１０３は、内蔵したディスクに対して、磁気的にデータの書き込みおよび読み出しを行う。ハードディスクドライブ１０３は、回路設計支援装置１０の二次記憶装置として使用される。ハードディスクドライブ１０３には、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。なお、二次記憶装置としては、フラッシュメモリ等の半導体記憶装置を使用することもできる。

グラフィック処理装置１０４には、モニタ１０４ａが接続されている。グラフィック処理装置１０４は、ＣＰＵ１０１からの命令に従って、画像をモニタ１０４ａの画面に表示させる。モニタ１０４ａとしては、ＣＲＴ（Cathode Ray Tube）や液晶表示装置等が挙げられる。

入力インタフェース１０５には、キーボード１０５ａとマウス１０５ｂとが接続されている。入力インタフェース１０５は、キーボード１０５ａやマウス１０５ｂから送られてくる信号をＣＰＵ１０１に送信する。なお、マウス１０５ｂは、ポインティングデバイスの一例であり、他のポインティングデバイスを使用することもできる。他のポインティングデバイスとしては、例えばタッチパネル、タブレット、タッチパッド、トラックボール等が挙げられる。

ドライブ装置１０６は、例えば、光の反射によって読み取り可能なようにデータが記録された光ディスクや、ＵＳＢ（Universal Serial Bus）メモリ等の持ち運び可能な記録媒体に記録されたデータの読み取りを行う。例えば、ドライブ装置１０６が光学ドライブ装置である場合、レーザ光等を利用して、光ディスク２００に記録されたデータの読み取りを行う。光ディスク２００には、Ｂｌｕ−ｒａｙ（登録商標）、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等が挙げられる。

通信インタフェース１０７は、ネットワーク５０に接続されている。通信インタフェース１０７は、ネットワーク５０を介して、他のコンピュータまたは通信機器との間でデータを送受信する。

以上のようなハードウェア構成によって、本実施の形態の処理機能を実現することができる。
回路設計支援装置１０は、回路設計対象の基板上に配置されるＢＧＡ等の部品間を接続する各バス（ネットの束）について、配線プラン（バスの配線経路および配線層の割り当てを示す情報）を生成する機能を有している。回路設計支援装置１０内には、以下のような機能が設けられる。

図３は、第２の実施の形態の回路設計支援装置の機能を示すブロック図である。
回路設計支援装置１０は、バスピン群記憶部１１と、ピン座標情報記憶部１２と、ネット情報記憶部１３と、部品情報記憶部１４と、ネット種別情報記憶部１５と、ペア候補グラフ作成部１６と、ペア決定部１７と、結果出力部１８と、ピンペア情報記憶部１９とを有している。

図４は、バスピン群記憶部に記憶されている情報を説明する図である。
図４に示す基板１１０には、それぞれ複数のピンホールＰＨ１が形成された領域１１１、１１２が設けられている。領域１１１、１１２には、ＢＧＡ等の部品が載置される。領域１１１、１１２の所定のピンホールＰＨ１には、バスピンＰ１が配置されている。図４では、バスピンＰ１が配置されている箇所にバスピンのネットを示すアルファベットを示している。領域１１１に配置されたバスピンＰ１に付したアルファベットと領域１１２に配置されたバスピンＰ１に付したアルファベットの一致するバスピンＰ１が、同じネットのバスピンＰ１である。

バスピン群記憶部１１には、領域１１１、１１２の各バスピンＰ１の座標、バスピンＰ１に接続されるネット（論理接続情報）のＩＤ、バスピンの形状（円、矩形等）、およびバスピンの半径等が記憶されている。

バスピンＰ１は、シングル（他のバスピンＰ１との組み合わせが決定していない）のバスピンＰ１と、他のバスピンＰ１との組み合わせが決定している差動ペアのバスピンＰ１が存在する。例えば、ネットＮのバスピンＰ１とネットＯのバスピンＰ１とは差動ペアを構成するバスピンＰ１であり、ペアが確定している。ネットＡ〜ネットＭのバスピンは、ペアが未確定である。

回路設計支援装置１０は、ペアが未確定のネットＡ〜ネットＭをグループにして単層のバス配線で領域１１１、１１２間を接続する処理を行う。本実施の形態では、２つのネットをグループにした１つのバス配線で領域１１１、１１２間を接続する場合について説明するが、３つ以上のネットをグループにした１つのバス配線で領域１１１、１１２間を接続する場合にも適用することができる。

領域１１１および領域１１２には、各バスピンＰ１の位置を識別する座標（相対座標）が、配線設計に対する入力情報として予め設定されている。例えば、領域１１１、１１２の左上が原点（０，０）に設定されており、領域１１１のネットＡのバスピンＰ１の座標は（１，１）である。

以下、領域１１１に配置されたバスピンＰ１を「ソースピンＰ１」とも言い、領域１１２に配置されたバスピンＰ１を「ターゲットピンＰ１」とも言う。
図５は、ピン座標情報記憶部に記憶されている情報の一例を示す図である。

本実施の形態では、情報がテーブル化されてピン座標情報記憶部に記憶されている。
図５に示すネットリスト１２ａには、ピンＩＤ、ピン群ＩＤ、ネット、座標およびペアピンＩＤの欄が設けられている。横方向に並べられた情報同士が互いに関連づけられている。

ピンＩＤの欄には、バスピンＰ１それぞれを識別するＩＤが設定されている。ピンＩＤは、バスピンＰ１毎に設けられており、同じネットのバスピンＰ１であってもピンＩＤは異なる。

ピン群ＩＤの欄には、領域１１１のバスピンＰ１か、領域１１２のバスピンＰ１かを識別する情報が設定されている。具体的には、領域１１１のバスピンＰ１には「左」、領域１１２のバスピンＰ２には「右」が設定されている。

ネットの欄には、バスピンＰ１のネットを識別する情報が設定されている。
座標の欄には、バスピンＰ１の相対座標が設定されている。
ペアピンＩＤの欄には、差動ペアを構成するバスピンを識別する番号が設定されている。例えば、ペアピンＩＤに「２８」が設定されバスピンＩＤ２７のバスピンＰ１は、バスピンＩＤ２８のバスピンＰ１と差動ペアを構成するピンである。

再び図３に戻って説明する。ネット情報記憶部１３には、バスに属するネット毎に、ネットが所属するバス、ソースピンＰ１、ターゲットピンＰ１および配線幅等を識別する情報が記憶されている。

部品情報記憶部１４には、領域１１１、１１２毎に、領域の基準位置（例えば、領域１１１の左上の頂点）の座標、左上ピン（例えば、ピン番号ＡのバスピンＰ１）の中心座標、領域の幅や高さ、バスピンＰ１間の距離、バスピンＰ１の配列数等が記憶されている。

ネット種別情報記憶部１５には、ネットの種別を識別する情報が記憶されている。
ペア候補グラフ作成部１６は、ネットリスト１２ａを用いてバスピンＰ１のペアを構成する候補（ペア候補）のグラフを作成する。なお、ここで言うグラフはグラフ理論上のグラフである。ペア候補グラフ作成部１６は、グラフを作成する際、領域１１１、１１２それぞれにおいてバスピンＰ１間の距離を記憶したソースピン距離管理テーブルを作成する。

図６は、ペア候補グラフ作成部の処理を説明する図である。
図６に示すソースピン距離管理テーブル１６ａは、ペア候補グラフ作成部１６が測定したソースピンＰ１間の距離を記憶するテーブルである。ソースピン距離管理テーブル１６ａの行方向および列方向には、それぞれピンＩＤおよびネットの欄が設定されている。

ペア候補グラフ作成部１６は、各ソースピンＰ１間の距離を測定し、距離が２以下のソースピンＰ１の組み合わせを抽出する。この処理により、距離が２より大きな箇所のソースピンＰ１の組み合わせは、ペア候補から除外する。なお、距離が２以下は一例である。図６では、抽出したソースピンＰ１の組み合わせを斜線で示している。なお、図６においては、距離が２より大きいソースピンＰ１の組み合わせの箇所は、「＞２」または、実測値を示している。

次に、ペア候補グラフ作成部１６は、距離が２以下のソースピンＰ１の組み合わせを抽出した箇所を明記したターゲットピン距離管理テーブルを作成する。
図７は、ペア候補グラフ作成部の処理を説明する図である。

図７に示すターゲットピン距離管理テーブル１６ｂは、ペア候補グラフ作成部１６が測定したターゲットピンＰ１間の距離を記憶するテーブルである。ターゲットピン距離管理テーブル１６ｂの行方向および列方向には、それぞれピンＩＤおよびネットの欄が設定されている。図７では、距離が２以下のソースピンＰ１の組み合わせのネットと同じネットの組み合わせを斜線で示している。ペア候補グラフ作成部１６は、ターゲットピン距離管理テーブル１６ｂの斜線で示された箇所について、ターゲットピンＰ１間の距離を測定する。すなわち、ペア候補グラフ作成部１６は、距離が２より大きな箇所のソースピンＰ１の組み合わせは、ペア候補から除外したので、ターゲットピンＰ１側でも距離の測定を省略する。測定を省略することにより、距離を測定する箇所を減らすことができる。図７では、距離が２以下のターゲットピンＰ１の組み合わせの実測値を示し、距離が２より大きいターゲットピンＰ１の組み合わせは、実測値の図示を省略している。そして、ペア候補グラフ作成部１６は、抽出したソースピンＰ１の組み合わせおよびターゲットピンＰ１の組み合わせに基づいて、グラフを作成する。

図８は、ペア候補グラフ作成部が作成したグラフを説明する図である。
図８には、ペア候補グラフ作成部１６が作成したグラフＬとグラフＲを示している。グラフＬは、各ソースピンＰ１をノードに設定し、ソースピン距離管理テーブル１６ａにおいて距離が２以下のソースピンＰ１間に枝を張ったグラフである。グラフＲは、各ターゲットピンＰ１をノードに設定し、ターゲットピン距離管理テーブル１６ｂにおいて距離が２以下のターゲットピンＰ１間に枝を張ったグラフである。なお、グラフＲでは、距離が２以下のターゲットピンＰ１の組み合わせのうち、グラフＬ側で距離が２より大きいソースピンＰ１の組み合わせに対応するターゲットピンＰ１の組み合わせを点線で示している。点線で示した組み合わせは、距離の測定を省略した組み合わせである。

ペア決定部１７は、ペア候補グラフ作成部１６が作成したグラフＬおよびグラフＲに基づいて、バス配線を行うバスピンＰ１のペアを決定する。ペア決定部１７は、グラフＬおよびグラフＲに基づき、バスピンＰ１のペアを決定することで、ペアのネットの配線経路の間に他のネットの配線経路が入り込んでしまう可能性を減らすことができる。具体的には、まず、ペア決定部１７は、グラフＲの各枝を頂点とし、グラフＲで隣接（頂点を共有）する枝間に枝を出したグラフ（以下、グラフＧと言う）を作成する。

図９は、ペア決定部が作成したグラフを説明する図である。
図９では、グラフＲの枝に１から１６までＩＤを振っている。グラフＧの頂点のＩＤが、グラフＲの枝の番号に対応している。すなわち、グラフＧの１つの頂点が１つのペア候補に対応している。例えば、グラフＧのＩＤ「１」の頂点は、ＩＤ「２」、ＩＤ「３」およびＩＤ「４」の頂点に接続されている。これは、ネットＡのターゲットピンＰ１とネットＤのターゲットピンＰ１のペア候補は、ネットＡのターゲットピンＰ１とネットＢのターゲットピンＰ１のペア候補、ネットＤのターゲットピンＰ１とネットＦのターゲットピンＰ３のペア候補、およびネットＤのターゲットピンＰ１とネットＢのターゲットピンＰ１のペア候補に隣接していることを示している。なお、グラフＧの形状は特に限定されない。

ペア決定部１７は、作成したグラフＧの各頂点から出ている枝の数（以下、次数と言う）を計数し、グラフ管理テーブルを作成する。
図１０は、グラフ管理テーブルを示す図である。

グラフ管理テーブル１７ａは、Ｇ頂点ＩＤ、ネットの組、採否、採択順、次数、隣接頂点、枝距離、および機会逸失距離の欄が設けられている。横方向に並べられた情報同士が互いに関連づけられている。

Ｇ頂点ＩＤの欄には、グラフＧの頂点のＩＤが設定される。
ネットの組の欄には、Ｇ頂点ＩＤに対応するペア候補を構成するターゲットピンＰ１のネットの組み合わせが設定される。

採否の欄には、Ｇ頂点ＩＤに対応するペア候補がペアとして採択されたか否かを識別する情報が設定される。具体的には、採択されたペア候補の欄には「採」が設定される。採択されなかったペア候補の欄には「否」が設定される。なお、初期状態は未決を示す「未」が設定されている。

採択順の欄には、ペアを採択した順序を示す値が設定される。初期状態は空白である。
次数の欄には、前述したように、作成したグラフＧの各頂点から出ている枝の数が設定される。

隣接頂点の欄には、Ｇ頂点ＩＤの欄のＩＤを備える頂点に隣接する頂点のＧ頂点ＩＤが設定される。
枝距離の欄には、さらに、左Ｌ、右Ｒ、合計の欄が設けられている。左Ｌの欄には、ネットの組の欄に設定されたネットのグラフＬのソースピンＰ１の距離が設定される。例えば、１行目のネットＡのソースピンＰ１とネットＤのソースピンＰ１間の距離１．４（小数点２桁以下切り捨て）が設定されている。右Ｒの欄には、ネットの組の欄に設定されたネットのグラフＲのターゲットピンＰ１の距離が設定される。合計の欄には、左Ｌの欄に設定された距離と右Ｒの欄に設定された距離の合計値が設定される。

機会逸失距離の欄には、さらに左Ｌ、右Ｒ、合計の欄が設けられている。左Ｌの欄には、当該レコードのネットの組を採択することによりペアの成立機会を逸失するグラフＬ側のソースピンＰ１のペアの距離が設定されている。右Ｒの欄には、当該レコードのネットの組を採択することによりペアの成立機会を逸失するグラフＲ側のターゲットピンＰ１のペアの距離が設定されている。合計の欄には、左Ｌの欄に設定された距離と右Ｒの欄に設定された距離の合計値が設定される。

ペア決定部１７は、グラフ管理テーブル１７ａを用いてターゲットピンＰ１のペア候補からターゲットピンＰ１のペアを決定する処理を繰り返し行う。以下、グラフ管理テーブル１７ａを用いてペア決定部１７の処理を説明する。

図１１〜図１７は、ペア決定部の処理を説明する図である。
ペア決定部１７は、グラフ管理テーブル１７ａを参照し、次数の最も小さいグラフＧのＧ頂点ＩＤを取得する。図１１に示すグラフ管理テーブル１７ａでは、Ｇ頂点ＩＤ「１５」の次数が「１」で最も小さい。このため、ペア決定部１７は、Ｇ頂点ＩＤ「１５」に対応するネットＫのターゲットピンＰ１とネットＭのターゲットピンＰ１のペア候補をペアに決定する。すなわち、ペア決定部１７は、Ｇ頂点ＩＤ「１５」の採否の欄を「採」に設定する。また、Ｇ頂点ＩＤ「１５」の採択順の欄に「１」を設定する。このように、次数が小さい順にペアに決定すること、すなわち、他のターゲットピンＰ１のペアの成否に影響を与える可能性の少ないペア候補から順に処理を進めることで、最終的に成立するペアの個数が増える可能性を高めることができる。

ところで、図９のグラフＲを参照すると、ネットＫのターゲットピンＰ１とネットＭのターゲットピンＰ１のペアの決定により、枝「１４」により接続されたターゲットピンＰ１のペア、すなわち、ネットＬのターゲットピンＰ１とネットＭのターゲットピンＰ１のペアの可能性がなくなる。従って、ペア決定部１７は、Ｇ頂点ＩＤ「１４」の頂点を、グラフＧから削除する処理を行う。具体的には、ペア決定部１７は、Ｇ頂点ＩＤ「１４」の採否の欄を「否」に設定する。また、ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄が「未」の全てのレコードの隣接頂点の欄から、「１４」を削除する。「１４」を削除した結果、Ｇ頂点ＩＤ「１３」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１３」の次数の欄を３から２に更新する。図１１の円で囲った「２＜３」は、次数が３から２に更新されたことを示している。なお、以下の図面の説明においても、注目すべき箇所を円で囲むこととする。なお、ペア決定部１７は、次数の更新に伴い、グラフ管理テーブル１７ａの枝距離および機会逸失距離も更新する。更新のタイミングは任意である。また、採否の欄が「採」または「否」の枝距離および機会逸失距離については、更新しなくてもよい。以下、グラフ管理テーブル１７ａにおいて、採否の欄を「否」に設定したレコードのＧ頂点ＩＤ、次数および隣接頂点の欄を斜線で示す。また、採否の欄を「採」に設定したレコードの隣接頂点の欄を斜線で示す。採否の欄を「否」に設定したレコードについては、次数の欄を更新しない。

１つのペアを決定したので、ペア決定部１７は、再び次数の最も少なく、かつ、採否の欄が「未」であるＧ頂点ＩＤを取得する。図１１に示すグラフ管理テーブル１７ａでは、Ｇ頂点ＩＤ「１３」およびＧ頂点ＩＤ「１６」の次数がそれぞれ「２」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「１３」およびＧ頂点ＩＤ「１６」それぞれの枝距離の合計の欄を参照し、値が小さいＧ頂点ＩＤに対応するターゲットピンＰ１のペア候補をペアに決定する。ここで、Ｇ頂点ＩＤ「１３」およびＧ頂点ＩＤ「１６」それぞれの枝距離の合計の欄はともに「２．８」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「１３」およびＧ頂点ＩＤ「１６」それぞれの機会逸失距離の合計の欄を参照し、値が大きいＧ頂点ＩＤに対応するターゲットピンＰ１のペア候補をペアに決定する。

ここで、Ｇ頂点ＩＤ「１３」の機会逸失距離の合計の欄には「５．８」が設定されており、Ｇ頂点ＩＤ「１６」の機会逸失距離の合計の欄には「４．８」が設定されている。このため、ペア決定部１７は、図１２に示すように、グラフＧ頂点ＩＤ「１３」に対応するネットＪのターゲットピンＰ１とネットＬのターゲットピンＰ１のペア候補をペアに決定する。これは、Ｇ頂点ＩＤ「１３」を残すと、Ｇ頂点ＩＤ「１３」のネットの組のターゲットピンＰ１とその他のターゲットピンＰ１の距離が、Ｇ頂点ＩＤ「１６」を残した場合に比べ大きくなってしまい、ペアの成立する可能性が減ってしまうからである。ペア決定部１７は、Ｇ頂点ＩＤ「１３」の採否の欄を「採」に設定する。また、Ｇ頂点ＩＤ「１３」の採択順の欄に「２」を設定する。ここで、図９のグラフＲを参照すると、ネットＪのターゲットピンＰ１とネットＬのターゲットピンＰ１のペアの決定により、新たに枝「１０」および枝「１２」のペアの可能性がなくなる。従って、ペア決定部１７は、Ｇ頂点ＩＤ「１０」および「１２」の頂点を、グラフＧから削除する処理を行う。具体的には、ペア決定部１７は、図１３に示すように、Ｇ頂点ＩＤ「１０」および「１２」の採否の欄を「否」に設定する。また、ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄が「未」の全てのレコードの隣接頂点の欄から、「１０」および「１２」を削除する。「１０」および「１２」を削除した結果、Ｇ頂点ＩＤ「５」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「５」の次数の欄を４から３に更新する。また、Ｇ頂点ＩＤ「９」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「９」の次数の欄を４から３に更新する。また、Ｇ頂点ＩＤ「１１」の隣接頂点の数が２つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１１」の次数の欄を４から２に更新する。

１つのペアを決定したので、ペア決定部１７は、再び次数の最も少なく、かつ、採否の欄が「未」であるＧ頂点ＩＤを取得する。図１３に示すグラフ管理テーブル１７ａでは、Ｇ頂点ＩＤ「１１」およびＧ頂点ＩＤ「１６」の次数がそれぞれ「２」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「１１」およびＧ頂点ＩＤ「１６」それぞれの枝距離の合計の欄を参照し、値が小さいＧ頂点ＩＤに対応するターゲットピンＰ１のペア候補をペアに決定する。ここで、Ｇ頂点ＩＤ「１１」の枝距離の合計の欄は「２．４」であり、Ｇ頂点ＩＤ「１６」の枝距離の合計の欄は「２．８」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「１１」に対応するターゲットピンＰ１のペア候補をペアに決定する。ペア決定部１７は、Ｇ頂点ＩＤ「１１」の採否の欄を「採」に設定する。また、Ｇ頂点ＩＤ「１１」の採択順の欄に「３」を設定する。ここで、図９のグラフＲを参照すると、ネットＧのターゲットピンＰ１とネットＩのターゲットピンＰ１のペアの決定により、新たに枝「５」および枝「９」のペアの可能性がなくなる。従って、ペア決定部１７は、Ｇ頂点ＩＤ「５」および「９」の頂点を、グラフＧから削除する処理を行う。具体的には、ペア決定部１７は、図１４に示すように、Ｇ頂点ＩＤ「５」および「９」の採否の欄を「否」に設定する。また、ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄が「未」の全てのレコードの隣接頂点の欄から、「５」および「９」を削除する。「５」および「９」を削除した結果、Ｇ頂点ＩＤ「３」の隣接頂点の数が２つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「３」の次数の欄を４から２に更新する。

１つのペアを決定したので、ペア決定部１７は、再び次数の最も少なく、かつ、採否の欄が「未」であるＧ頂点ＩＤを取得する。図１４に示すグラフ管理テーブル１７ａでは、Ｇ頂点ＩＤ「３」およびＧ頂点ＩＤ「１６」の次数がそれぞれ「２」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「３」およびＧ頂点ＩＤ「１６」それぞれの枝距離の合計の欄を参照し、値が小さいＧ頂点ＩＤに対応するターゲットピンＰ１のペア候補をペアに決定する。ここで、Ｇ頂点ＩＤ「３」およびＧ頂点ＩＤ「１６」それぞれの枝距離の合計の欄はともに「２．８」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「３」およびＧ頂点ＩＤ「１６」それぞれの機会逸失距離の合計の欄を参照し、値が大きいＧ頂点ＩＤに対応するターゲットピンＰ１のペア候補をペアに決定する。ここで、Ｇ頂点ＩＤ「３」の機会逸失距離の合計は「５．２」が設定されており、Ｇ頂点ＩＤ「１６」の機会逸失距離の合計の欄には「４．８」が設定されている。このため、ペア決定部１７は、グラフＧ頂点ＩＤ「３」に対応するネットＤのターゲットピンＰ１とネットＦのターゲットピンＰ１のペア候補をペアに決定する。ペア決定部１７は、Ｇ頂点ＩＤ「３」の採否の欄を「採」に設定する。また、Ｇ頂点ＩＤ「３」の採択順の欄に「４」を設定する。ここで、図９のグラフＲを参照すると、ネットＤのターゲットピンＰ１とネットＦのターゲットピンＰ１のペアの決定により、新たに枝「１」および枝「４」のペアの可能性がなくなる。従って、ペア決定部１７は、Ｇ頂点ＩＤ「１」およびＧ頂点ＩＤ「４」の頂点を、グラフＧから削除する処理を行う。具体的には、ペア決定部１７は、図１５に示すように、Ｇ頂点ＩＤ「１」および「４」の採否の欄を「否」に設定する。また、ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄が「未」の全てのレコードの隣接頂点の欄から、「１」および「４」を削除する。「１」および「４」を削除した結果、Ｇ頂点ＩＤ「６」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「６」の次数の欄を５から４に更新する。また、Ｇ頂点ＩＤ「７」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「７」の次数の欄を４から３に更新する。

１つのペアを決定したので、ペア決定部１７は、再び次数の最も少なく、かつ、採否の欄が「未」であるＧ頂点ＩＤを取得する。図１５に示すグラフ管理テーブル１７ａでは、Ｇ頂点ＩＤ「２」およびＧ頂点ＩＤ「１６」の次数がそれぞれ「２」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「２」およびＧ頂点ＩＤ「１６」それぞれの枝距離の合計の欄を参照し、値が小さいＧ頂点ＩＤに対応するターゲットピンＰ１のペア候補をペアに決定する。ここで、Ｇ頂点ＩＤ「２」の枝距離の合計の欄は「３」であり、Ｇ頂点ＩＤ「１６」の枝距離の合計の欄は「２．８」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「１６」に対応するターゲットピンＰ１のペア候補をペアに決定する。ペア決定部１７は、Ｇ頂点ＩＤ「１６」の採否の欄を「採」に設定する。また、Ｇ頂点ＩＤ「１６」の採択順の欄に「５」を設定する。ここで、図９のグラフＲを参照すると、ネットＢのターゲットピンＰ１とネットＣのターゲットピンＰ１のペアの決定により、新たに枝「６」および枝「８」のペアの可能性がなくなる。従って、ペア決定部１７は、Ｇ頂点ＩＤ「６」および「８」の頂点を、グラフＧから削除する処理を行う。具体的には、ペア決定部１７は、図１６に示すように、Ｇ頂点ＩＤ「６」および「８」の採否の欄を「否」に設定する。また、ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄が「未」の全てのレコードの隣接頂点の欄から、「６」および「８」を削除する。「６」および「８」を削除した結果、Ｇ頂点ＩＤ「２」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「２」の次数の欄を２から１に更新する。「６」および「８」を削除した結果、Ｇ頂点ＩＤ「７」の隣接頂点の数が２つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「７」の次数の欄を３から１に更新する。

１つのペアを決定したので、ペア決定部１７は、再び次数の最も少なく、かつ、採否の欄が「未」であるＧ頂点ＩＤを取得する。図１６に示すグラフ管理テーブル１７ａでは、Ｇ頂点ＩＤ「２」およびＧ頂点ＩＤ「７」の次数がそれぞれ「１」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「２」およびＧ頂点ＩＤ「７」それぞれの枝距離の合計の欄を参照し、値が小さいＧ頂点ＩＤに対応するターゲットピンＰ１のペア候補をペアに決定する。ここで、Ｇ頂点ＩＤ「２」の枝距離の合計の欄は「３」であり、Ｇ頂点ＩＤ「７」の枝距離の合計の欄は「２」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「７」に対応するターゲットピンＰ１のペア候補をペアに決定する。ペア決定部１７は、Ｇ頂点ＩＤ「７」の採否の欄を「採」に設定する。また、Ｇ頂点ＩＤ「７」の採択順の欄に「６」を設定する。ここで、図９のグラフＲを参照すると、ネットＥのターゲットピンＰ１とネットＨのターゲットピンＰ１のペアの決定により、新たに枝「２」のペアの可能性がなくなる。従って、ペア決定部１７は、Ｇ頂点ＩＤ「２」の頂点を、グラフＧから削除する処理を行う。具体的には、ペア決定部１７は、図１７に示すように、Ｇ頂点ＩＤ「２」の採否の欄を「否」に設定する。この結果、グラフ管理テーブル１７ａの全ての採否の欄が「採」または「否」となったので、ペア決定部１７は、処理を終了する。

図１８は、グラフの推移を示す図である。
図１０に示すグラフ管理テーブル１７ａから図１１に示すグラフ管理テーブル１７ａに処理が遷移すると、処理状況が、図１８（ａ）に示すグラフＲから図１８（ｂ）に示すグラフＲに遷移する。図１１に示すグラフ管理テーブル１７ａから図１２に示すグラフ管理テーブル１７ａに処理が遷移すると、処理状況が、図１８（ｂ）に示すグラフＲから図１８（ｃ）に示すグラフＲに遷移する。図１２に示すグラフ管理テーブル１７ａから図１３に示すグラフ管理テーブル１７ａに処理が遷移すると、処理状況が、図１８（ｃ）に示すグラフＲから図１８（ｄ）に示すグラフＲに遷移する。図１３に示すグラフ管理テーブル１７ａから図１４に示すグラフ管理テーブル１７ａに処理が遷移すると、処理状況が、図１８（ｄ）に示すグラフＲから図１８（ｅ）に示すグラフＲに遷移する。図１４に示すグラフ管理テーブル１７ａから図１５に示すグラフ管理テーブル１７ａに処理が遷移すると、処理状況が、図１８（ｅ）に示すグラフＲから図１８（ｆ）に示すグラフＲに遷移する。図１５に示すグラフ管理テーブル１７ａから図１６に示すグラフ管理テーブル１７ａに処理が遷移すると、処理状況が、図１８（ｆ）に示すグラフＲから図１８（ｇ）に示すグラフＲに遷移する。

結果出力部１８は、ペア決定部１７が決定したターゲットピンＰ１のペアに関する情報をピンペア情報記憶部１９に記憶する。また、結果出力部１８は、ペア決定部１７が決定したターゲットピンＰ１のペアに関する情報をモニタ１０４ａに出力してもよい。

図１９は、ピンペア情報記憶部に記憶されたターゲットピンのペアに関する情報を説明する図である。
ピンペア情報記憶部１９には、図１８（ｇ）に示したグラフＲを形成し得る情報が記憶される。また、ペア決定部１７が決定したターゲットピンＰ１のペアに関する情報を用いてソースピンＰ１のペアを形成すると、図１９に示すグラフＬのようになる。

次に、前述したペア候補グラフ作成部１６およびペア決定部１７の処理を、フローチャートを用いて説明する。
図２０は、第２の実施の形態のペア候補グラフ作成部およびペア決定部の処理を示すフローチャートである。

［ステップＳ１］ ペア候補グラフ作成部１６は、ネットリスト１２ａからソースピンＰ１群およびターゲットピンＰ１群の座標データを読み込む。その後、ステップＳ２に遷移する。

［ステップＳ２］ ペア候補グラフ作成部１６は、ステップＳ１にて読み込んだ座標データに基づいて領域１１１に配置されたソースピンＰ１間の距離を測定し、測定結果をソースピン距離管理テーブル１６ａに記憶する。そして、ペア候補グラフ作成部１６は、距離が２以下のソースピンＰ１の組み合わせを抽出してグラフＬを作成する。その後、ステップＳ３に遷移する。

［ステップＳ３］ ペア候補グラフ作成部１６は、ターゲットピン距離管理テーブル１６ｂを参照する。そして、ペア候補グラフ作成部１６は、距離が２以下のソースピンＰ１の組み合わせを抽出した箇所について、ターゲットピンＰ１間の距離を測定し、測定結果をターゲットピン距離管理テーブル１６ｂに記憶する。そして、ペア候補グラフ作成部１６は、距離が２以下のターゲットピンＰ１の組み合わせを抽出してグラフＲを作成する。その後、ステップＳ４に遷移する。

［ステップＳ４］ ペア決定部１７は、ステップＳ２にて作成されたグラフＬおよびステップＳ３にて作成されたグラフＲに基づいて、グラフＧおよびグラフ管理テーブル１７ａを作成する。その後、ステップＳ５に遷移する。

［ステップＳ５］ ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄が「未」のＧ頂点ＩＤを次の（１）〜（３）のキーワードでソートする。（１）次数（昇順）、（２）枝距離の合計（昇順）、（３）機会逸失距離（降順）。その後、ステップＳ６に遷移する。

［ステップＳ６］ ペア決定部１７は、ステップＳ５のソートの結果に基づいて、グラフ管理テーブル１７ａを更新するテーブル更新処理を行う。なお、テーブル更新処理については後述する。テーブル更新処理が終了するとステップＳ７に遷移する。

［ステップＳ７］ ペア決定部１７は、グラフＧの頂点の採否が全て終了したか否かを判断する。具体的には、ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄に「未」が存在するか否かを判断する。グラフ管理テーブル１７ａの採否の欄に「未」が存在する場合（ステップＳ７のＹｅｓ）、ステップＳ５に遷移する。グラフ管理テーブル１７ａの採否の欄に「未」が存在しない場合、すなわち、採否の欄が全て「採」または「否」の場合（ステップＳ７のＮｏ）、ステップＳ８に遷移する。

［ステップＳ８］ ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄に「採」が設定されたターゲットピンＰ１のペアの情報をピンペア情報記憶部１９に記憶する。その後、図２０の処理を終了する。

以上で図２０の処理の説明を終了する。
次に、ステップＳ６のテーブル更新処理を説明する。
図２１は、テーブル更新処理を示すフローチャートである。

［ステップＳ６ａ］ ペア決定部１７は、ステップＳ５のソートの結果、一番上に表示されたＧ頂点ＩＤを変数Ｖｔに設定する。その後、ステップＳ６ｂに遷移する。
［ステップＳ６ｂ］ ペア決定部１７は、グラフ管理テーブル１７ａの隣接頂点の欄を参照し、変数Ｖｔに隣接するＧ頂点ＩＤを全て抽出する。その後、ステップＳ６ｃに遷移する。

［ステップＳ６ｃ］ ペア決定部１７は、ステップＳ６ｂにて抽出したＧ頂点ＩＤを１つ選択する。その後、ステップＳ６ｄに遷移する。
［ステップＳ６ｄ］ ペア決定部１７は、ステップＳ６ｃにて選択したＧ頂点ＩＤを変数Ｖｘに代入する。その後、ステップＳ６ｅに遷移する。

［ステップＳ６ｅ］ ペア決定部１７は、グラフ管理テーブル１７ａの、変数Ｖｘに隣接する全てのＧ頂点ＩＤの次数を１減らす。その後、ステップＳ６ｆに遷移する。
［ステップＳ６ｆ］ ペア決定部１７は、グラフ管理テーブル１７ａの、変数Ｖｘに隣接する全てのＧ頂点ＩＤの機会逸失距離を更新する。その後、ステップＳ６ｇに遷移する。

［ステップＳ６ｇ］ ペア決定部１７は、変数Ｖｘの採否の欄を「否」に設定する。その後、ステップＳ６ｈに遷移する。
［ステップＳ６ｈ］ ペア決定部１７は、ステップＳ６ｂにて抽出した全てのＧ頂点ＩＤについてステップＳ６ｃ〜Ｓ６ｇの処理を行ったか否かを判断する。ステップＳ６ｂにて抽出した全てのＧ頂点ＩＤについてステップＳ６ｃ〜Ｓ６ｇの処理を行った場合（ステップＳ６ｈのＹｅｓ）、ステップＳ６ｉに遷移する。ステップＳ６ｂにて抽出した全てのＧ頂点ＩＤについてステップＳ６ｃ〜Ｓ６ｇの処理を行っていない場合（ステップＳ６ｈのＮｏ）、ステップＳ６ｃに遷移し、ステップＳ６ｃ以降の処理を引き続き行う。

［ステップＳ６ｉ］ ペア決定部１７は、変数Ｖｔに設定されているＧ頂点ＩＤの採否の欄を「採」に設定する。その後、テーブル更新処理を終了する。
以上述べたように、回路設計支援装置１０によれば、ペア候補グラフ作成部１６が、領域１１１、１１２それぞれのバスピンＰ１間の距離がいずれも所定距離以内であるバスピンＰ１のペア候補を決定したグラフＲを作成した。ペア決定部１７が、このグラフＲを用いてペアを決定することにより、間に他のバス配線が入り込むようなペアが作成される可能性を低くすることができる。

また、２ネットずつ同時に経路を求めることができるため、バス配線の処理時間を短縮することができる。例えば探索するＮ本のネットの配線引き出し順の組み合わせをＮ！から（Ｎ／２）！に削減することができる。例えば、Ｎ＝４であれば、２４通りを２通りにすることができる。

＜第３の実施の形態＞
次に、第３の実施の形態の回路設計支援装置について説明する。
以下、第３の実施の形態の回路設計支援装置について、前述した第２の実施の形態との相違点を中心に説明し、同様の事項については、その説明を省略する。

第３の実施の形態の回路設計支援装置１０は、領域１１１に配置された各ソースピンＰ１および領域１１２に配置された各ターゲットピンＰ１が２つの信号種別毎に区別されている点が第２の実施の形態と異なっている。

図２２は、第３の実施の形態のネットリストを示す図である。
図２２に示すネットリスト１２ｂには、ネットリスト１２ａに比べ、信号種ＩＤの欄がさらに設けられている。信号種ＩＤの欄には、「１」または「２」が設定されており、値が等しい信号種を備えるネット同士は、ピン間に２本セットで通す配線ができて異なる信号種のネット同士は同じピン間を通すことができないように決められている。

この場合、同じ信号種のネット同士をまとめて同じピン間に通すようにした方が配線スペースを効率よく使うことができる。以下、第３の実施の形態のペア候補グラフ作成部１６の処理を説明する。

第３の実施の形態のペア候補グラフ作成部１６は、ネットリスト１２ｂを用いてペア候補のグラフを作成する。
ペア候補グラフ作成部１６は、各ソースピンＰ１間の距離を測定し、距離が２以下、かつ、信号種別が同種のソースピンＰ１の組み合わせを抽出する。

また、ペア候補グラフ作成部１６は、図７に示すターゲットピン距離管理テーブル１６ｂの距離が２以下、かつ、信号種別が同種のソースピンＰ１の組み合わせを抽出した箇所について、距離が２以下、かつ、信号種別が同種のターゲットピンＰ１の組み合わせを抽出する。

図２３は、第３の実施の形態のペア候補グラフ作成部が作成したグラフを示す図である。
図２３には、図６に示すソースピン距離管理テーブル１６ａにおいて、距離が２以下、かつ、信号種別が同種のソースピンＰ１間に枝を張ったグラフＬ１と、図７に示すターゲットピン距離管理テーブル１６ｂにおいて、距離が２以下、かつ、信号種別が同種のターゲットピンＰ１間に枝を張ったグラフＲ１を示している。グラフＬ１、Ｒ１において、信号種が異なるバスピンＰ１間には枝が存在しないため、信号種が異なるバスピンＰ１のペアが生じる可能性がない。

この第３の実施の形態の回路設計支援装置１０によれば、第２の実施の形態の回路設計支援装置１０と同様の効果が得られる。
そして、第３の実施の形態の回路設計支援装置１０によれば、同じ信号種ＩＤを備えるピンの配線が隣接する可能性を高めることができる。このため、配線スペースを効率よく使うことができる。

図２４は、配線スペースが効率よく使える理由を説明する図である。
バスピンＰ１ａ、Ｐ３ａが同じ信号種ＩＤを有しており、バスピンＰ２ａ、Ｐ４ａが同じ信号種ＩＤを有しているものとする。そして、同じ信号種ＩＤの配線同士は隣接してよいが、異なる信号種ＩＤの配線は少なくとも１マス開けるという配線ルールが設定されているものとする。この配線ルールでは、同じ信号種ＩＤの配線同士を隣接させて配線した方が、配線スペースを効率よく使える場合が多い。例えば図２４（ａ）は、ピンの信号種ＩＤを考慮せずに配線した例を示している。ピンの信号種ＩＤを考慮せずに配線した結果、同じ信号種ＩＤの配線同士が隣接せずに配線されている。対して図２４（ｂ）は、ピンの信号種ＩＤを考慮して回路設計支援装置１０が配線をした例を示している。図２４（ａ）、（ｂ）の斜線部は、いずれも他のピンについて配線ができないデッドスペースを示している。図２４（ｂ）の斜線部の面積は、図２４（ａ）の斜線部の面積に比べ少ないことが確認できる。このため、同じ信号種ＩＤの配線同士を隣接させて配線した方が、配線スペースを効率よく使うことができる。

なお、本実施の形態の回路設計支援装置１０では、２つの信号種ＩＤを備える場合を説明したが、３つ以上の信号種ＩＤを備えていてもよい。
＜第４の実施の形態＞
次に、第４の実施の形態の回路設計支援装置について説明する。

以下、第４の実施の形態の回路設計支援装置について、前述した第３の実施の形態との相違点を中心に説明し、同様の事項については、その説明を省略する。
図２５は、第４の実施の形態の回路設計支援装置の機能を示すブロック図である。

第４の実施の形態の回路設計支援装置１０ａは、信号種別距離係数記憶部２０をさらに有している。
図２６は、第４の実施の形態のネットリストを示す図である。

図２６に示すネットリスト１２ｃの信号種ＩＤの欄には、信号の種別を示す「１」、「２」または「３」が設定されている。
図２７は、信号種別距離係数記憶部に記憶されている情報を説明する図である。

図２７では情報がテーブル化されて記憶されている。
図２７に示す距離係数テーブル２０ａは、信号種ＩＤ（ａ）、信号種ＩＤ（ｂ）および距離係数の欄が設けられている。横方向に並べられた情報同士が互いに関連づけられている。

信号種ＩＤ（ａ）の欄および信号種ＩＤ（ｂ）の欄には、ネットリスト１２ｃに設定した信号種ＩＤの組み合わせが設定されている。
距離係数の欄には、信号種ＩＤ（ａ）の欄の信号種ＩＤを持つバスピンＰ１と信号種ＩＤ（ｂ）の欄の信号種ＩＤを持つバスピンＰ１とのペアになり易さを示す指標が設定されている。本実施の形態では、「１」が最もペアとなり易く、「３」が最もペアとなりにくい。この距離係数テーブル２０ａにより、例えば、図２６に示すネットリスト１２ｃのピンＩＤ「１」のソースピンＰ１は、ピンＩＤ「２」、「３」、「４」、「６」、「７」のソースピンＰ１とペアになり易く、ピンＩＤ「５」のソースピンＰ１とペアになりにくいことが確認できる。なお、距離係数を「１」に設定する一例としては、信号種ＩＤ（ａ）の欄および信号種ＩＤ（ｂ）の欄の信号種ＩＤによって特定される信号種が差動信号である場合が挙げられる。また、距離係数を「３」に設定する一例としては、信号種ＩＤ（ａ）の欄および信号種ＩＤ（ｂ）の欄の信号種ＩＤによって特定される信号種のいずれかがクロック信号である場合が挙げられる。

次に、第４の実施の形態のペア候補グラフ作成部１６の処理を説明する。
ペア候補グラフ作成部１６は、領域１１１の各ソースピンＰ１について、各ソースピンＰ１間の距離を求める。そして、ペア候補グラフ作成部１６は、距離係数テーブル２０ａを参照し、求めた距離それぞれに距離係数を掛ける。そして、距離が２以下のソースピンＰ１の組み合わせを抽出する。

図２８は、第４の実施の形態のソースピン距離管理テーブルを示す図である。
図２８に示すソースピン距離管理テーブル１６ｃは、距離が２以下である箇所を斜線で示している。また、ソースピン距離管理テーブル１６ｃは、ソースピン距離管理テーブル１６ａでは距離が２以下となっていた箇所であって、ソースピン距離管理テーブル１６ｃでは距離が２より大きくなった箇所について計算式を示している。

図２９は、第４の実施の形態のターゲットピン距離管理テーブルを示す図である。
図２９に示すターゲットピン距離管理テーブル１６ｄは、距離が２以下のターゲットピンＰ１の組み合わせを抽出した箇所を斜線で示している。ここで、ピンＩＤ「１４」とピンＩＤ「１６」のターゲットピンＰ１の距離は２以下の「１．４」であるが、後述するグラフＬ２に枝が存在しない。このため、後述するグラフＲ２の作成対象から除外する。

図３０は、第４の実施の形態のペア候補グラフ作成部が作成したグラフを説明する図である。
図３０には、ペア候補グラフ作成部１６が作成したグラフＬ２とグラフＲ２を示している。グラフＬ２とグラフＲ２には、それぞれ同じ信号種ＩＤを持つバスピンＰ１の周辺には同じ模様を示している。グラフＬ２は、各ソースピンＰ１をノードに設定し、ソースピン距離管理テーブル１６ｃにおいて距離が２以下のソースピンＰ１間に枝を張ったグラフである。グラフＲ２は、各ターゲットピンＰ１をノードに設定し、ターゲットピン距離管理テーブル１６ｄにおいて距離が２以下のターゲットピンＰ１間に枝を張ったグラフである。第４の実施の形態のペア候補グラフ作成部１６の処理の結果、同じ信号種のソースピンＰ１間およびターゲットピンＰ１に枝が張られていることが確認できる。

次に、第４の実施の形態のペア候補グラフ作成部１６およびペア決定部１７の処理を、フローチャートを用いて説明する。
図３１は、第４の実施の形態のペア候補グラフ作成部およびペア決定部の処理を示すフローチャートである。

［ステップＳ１１］ ペア候補グラフ作成部１６は、ネットリスト１２ｃからソースピンＰ１群およびターゲットピンＰ１群の座標データを読み込む。その後、ステップＳ１２に遷移する。

［ステップＳ１２］ ペア候補グラフ作成部１６は、ステップＳ１１にて読み込んだ座標データに基づいて領域１１１に配置されたソースピンＰ１間の距離を測定する。そして、ペア候補グラフ作成部１６は、距離係数テーブル２０ａを参照し、測定結果に距離係数を掛けてソースピン距離管理テーブル１６ｃに記憶する。そして、ペア候補グラフ作成部１６は、距離が２以下のソースピンＰ１の組み合わせを抽出してグラフＬ２を作成する。その後、ステップＳ１３に遷移する。

［ステップＳ１３］ ペア候補グラフ作成部１６は、ターゲットピン距離管理テーブル１６ｂを参照する。そして、ペア候補グラフ作成部１６は、距離が２以下のソースピンＰ１の組み合わせを抽出した箇所について、ターゲットピンＰ１間の距離を測定する。そして、距離係数テーブル２０ａを参照し、測定結果に距離係数を掛けてターゲットピン距離管理テーブル１６ｄに記憶する。そして、ペア候補グラフ作成部１６は、グラフＬ２に同区間の枝が存在する距離が２以下のターゲットピンＰ１の組み合わせを抽出してグラフＲ２を作成する。その後、ステップＳ１４に遷移する。

ステップＳ１４からステップＳ１８は、ペア決定部１７は、ステップＳ４からステップＳ８と同じ処理を行う。以上で図３１の処理の説明を終了する。
この第４の実施の形態の回路設計支援装置１０によれば、第３の実施の形態の回路設計支援装置１０と同様の効果が得られる。

＜第５の実施の形態＞
次に、第５の実施の形態の回路設計支援装置について説明する。
以下、第５の実施の形態の回路設計支援装置について、前述した第２の実施の形態との相違点を中心に説明し、同様の事項については、その説明を省略する。

第５の実施の形態のペア候補グラフ作成部１６は、領域１１２側のターゲットピンＰ１のネット分布を考慮せずにペア候補を作成する。
図３２は、第５の実施の形態の回路設計支援装置の機能を示すブロック図である。

第５の実施の形態の回路設計支援装置１０ｂは、さらに、調整部２１を有している。調整部２１は、ペア決定部１７の決定に応じて領域１１２の各ターゲットピンＰ１のネットＡ〜Ｍの割り当てを調整する。また、調整部２１は、調整した各ターゲットピンＰ１のネットＡ〜Ｍの割り当てを、ピンペア情報記憶部１９に記憶させる。第５の実施の形態の回路設計支援装置１０ｂの処理は、例えば、領域１１１がＡＳＩＣ（Application Specific Integrated Circuit）を配置する領域であり、領域１１２がＦＰＧＡ（Field-Programmable Gate Array）を配置する領域である場合に適用することができる。

図３３は、第５の実施の形態のペア候補グラフ作成部の処理を説明する図である。
第５の実施の形態のペア候補グラフ作成部１６は、第２の実施の形態と同様に、グラフＬを作成する。

ペア決定部１７は、グラフＬの各枝を頂点とし、グラフＬで隣接（頂点を共有）する枝間に枝を出したグラフＧ１を作成する。そして、ペア決定部１７は、作成したグラフＧ１の次数を計数し、グラフ管理テーブルを作成する。

図３４は、第５の実施の形態のグラフ管理テーブルを示す図である。
グラフ管理テーブル１７ｂには、Ｇ頂点ＩＤ、ネットの組、採否、採択順、次数、隣接頂点、枝距離および機会逸失距離の欄が設けられている。横方向に並べられた情報同士が互いに関連づけられている。

Ｇ頂点ＩＤの欄には、グラフＧ１の頂点のＩＤが設定される。
ネットの組の欄には、Ｇ頂点ＩＤに対応するペア候補を構成するソースピンＰ１のネットの組み合わせが設定される。

採否の欄、採択順の欄、次数の欄および隣接頂点の欄は、それぞれグラフ管理テーブル１７ａと同様の情報が設定される。
枝距離の欄には、ネットの組の欄に設定されたネットのグラフＬのソースピンＰ１の距離が設定される。

機会逸失距離の欄には、当該レコードのネットの組を採択することによりペアの成立機会を逸失するグラフＬのソースピンＰ１のペアの距離が設定されている。
ペア決定部１７は、グラフ管理テーブル１７ｂを用いてペア候補からペアを決定する処理を繰り返し行う。以下、グラフ管理テーブル１７ｂを用いてペア決定部１７の処理を説明する。

図３５〜図４１は、第５の実施の形態のペア決定部の処理を説明する図である。
ペア決定部１７は、グラフ管理テーブル１７ｂを参照し、次数の最も小さいグラフＧ１の頂点を取得する。図３４に示すグラフ管理テーブル１７ｂでは、Ｇ頂点ＩＤ「２４」の次数が「３」で最も小さい。このため、ペア決定部１７は、Ｇ頂点ＩＤ「２４」に対応するネットＫのターゲットピンＰ１とネットＭのターゲットピンＰ１のペア候補をペアに決定する。すなわち、ペア決定部１７は、図３５に示すように、Ｇ頂点ＩＤ「２４」の採否の欄を「採」に設定する。また、Ｇ頂点ＩＤ「２４」の採択順の欄に「１」を設定する。ここで、図３３のグラフＬを参照すると、ネットＫのターゲットピンＰ１とネットＭのターゲットピンＰ１のペアの決定により、枝「２１」、「２２」および「２３」のペアの可能性がなくなる。従って、ペア決定部１７は、Ｇ頂点ＩＤ「２１」、「２２」および「２３」の頂点を、グラフＧ１から削除する処理を行う。具体的には、図３６に示すように、ペア決定部１７は、Ｇ頂点ＩＤ「２１」、「２２」および「２３」の採否の欄を「否」に設定する。また、ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄が「未」の全てのレコードの隣接頂点の欄から、「２１」、「２２」および「２３」を削除する。隣接頂点「２１」、「２２」および「２３」を削除した結果、Ｇ頂点ＩＤ「１６」の隣接頂点の数が２つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１６」の次数の欄を９から７に更新する。また、隣接頂点「２１」、「２２」および「２３」を削除した結果、Ｇ頂点ＩＤ「１８」の隣接頂点の数が２つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１８」の次数の欄を７から５に更新する。また、隣接頂点「２１」、「２２」および「２３」を削除した結果、Ｇ頂点ＩＤ「１９」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１９」の次数の欄を５から４に更新する。隣接頂点「２１」、「２２」および「２３」を削除した結果、Ｇ頂点ＩＤ「２０」の隣接頂点の数が３つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「２０」の次数の欄を６から３に更新する。

１つのペアを決定したので、ペア決定部１７は、再び次数の最も少なく、かつ、採否の欄が「未」であるＧ頂点ＩＤを取得する。
図３６に示すグラフ管理テーブル１７ｂでは、Ｇ頂点ＩＤ「２０」の次数が「３」で最も小さい。このため、ペア決定部１７は、Ｇ頂点ＩＤ「２０」に対応するネットＪのターゲットピンＰ１とネットＬのターゲットピンＰ１のペア候補をペアに決定する。すなわち、ペア決定部１７は、Ｇ頂点ＩＤ「２０」の採否の欄を「採」に設定する。また、Ｇ頂点ＩＤ「２０」の採択順の欄に「２」を設定する。ここで、図３３のグラフＬを参照すると、ネットＪのターゲットピンＰ１とネットＬのターゲットピンＰ１のペアの決定により、新たに枝「１６」、「１８」および「１９」のペアの可能性がなくなる。従って、ペア決定部１７は、Ｇ頂点ＩＤ「１６」、「１８」および「１９」の頂点を、グラフＧ１から削除する処理を行う。具体的には、図３７に示すように、ペア決定部１７は、Ｇ頂点ＩＤ「１６」、「１８」および「１９」の採否の欄を「否」に設定する。また、ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄が「未」の全てのレコードの隣接頂点の欄から、「１６」、「１８」および「１９」を削除する。隣接頂点「１６」、「１８」および「１９」を削除した結果、Ｇ頂点ＩＤ「１０」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１０」の次数の欄を８から７に更新する。また、隣接頂点「１６」、「１８」および「１９」を削除した結果、Ｇ頂点ＩＤ「１１」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１１」の次数の欄を９から８に更新する。また、隣接頂点「１６」、「１８」および「１９」を削除した結果、Ｇ頂点ＩＤ「１３」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１３」の次数の欄を９から８に更新する。また、隣接頂点「１６」、「１８」および「１９」を削除した結果、Ｇ頂点ＩＤ「１４」の隣接頂点の数が２つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１４」の次数の欄を６から４に更新する。また、隣接頂点「１６」、「１８」および「１９」を削除した結果、Ｇ頂点ＩＤ「１５」の隣接頂点の数が３つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１５」の次数の欄を８から５に更新する。また、隣接頂点「１６」、「１８」および「１９」を削除した結果、Ｇ頂点ＩＤ「１７」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１７」の次数の欄を７から６に更新する。

１つのペアを決定したので、ペア決定部１７は、再び次数の最も少なく、かつ、採否の欄が「未」であるＧ頂点ＩＤを取得する。
図３７に示すグラフ管理テーブル１７ｂでは、Ｇ頂点ＩＤ「７」およびＧ頂点ＩＤ「１４」の次数がそれぞれ「４」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「７」およびＧ頂点ＩＤ「１４」それぞれの枝距離の欄を参照し、値が小さいＧ頂点ＩＤに対応するペア候補をペアに決定する。ここで、Ｇ頂点ＩＤ「７」の枝距離は、「２」であり、Ｇ頂点ＩＤ「１４」の枝距離は「１」である。このため、ペア決定部１７は、グラフＧ頂点ＩＤ「１４」に対応するネットＦのターゲットピンＰ１とネットＩのターゲットピンＰ１のペア候補をペアに決定する。すなわち、ペア決定部１７は、Ｇ頂点ＩＤ「１４」の採否の欄を「採」に設定する。なお、図３７〜図４１においては、紙面の都合上、ネットの組の欄の図示を省略している。また、Ｇ頂点ＩＤ「２０」の採択順の欄に「２」を設定する。ここで、図３３のグラフＬを参照すると、ネットＦのターゲットピンＰ１とネットＩのターゲットピンＰ１のペアの決定により、新たに枝「１」、「８」、「１０」、および「１５」のペアの可能性がなくなる。従って、ペア決定部１７は、Ｇ頂点ＩＤ「１」、「８」、「１０」、および「１５」の頂点を、グラフＧ１から削除する処理を行う。具体的には、図３８に示すように、ペア決定部１７は、Ｇ頂点ＩＤ「１」、「８」、「１０」、および「１５」の採否の欄を「否」に設定する。また、ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄が「未」の全てのレコードの隣接頂点の欄から、「１」、「８」、「１０」、および「１５」を削除する。隣接頂点「１」、「８」、「１０」、および「１５」を削除した結果、Ｇ頂点ＩＤ「２」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「２」の次数の欄を５から４に更新する。また、隣接頂点「１」、「８」、「１０」、および「１５」を削除した結果、Ｇ頂点ＩＤ「３」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「３」の次数の欄を７から６に更新する。また、隣接頂点「１」、「８」、「１０」、および「１５」を削除した結果、Ｇ頂点ＩＤ「９」の隣接頂点の数が２つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「９」の次数の欄を６から４に更新する。また、隣接頂点「１」、「８」、「１０」、および「１５」を削除した結果、Ｇ頂点ＩＤ「１１」の隣接頂点の数が３つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１１」の次数の欄を８から５に更新する。また、隣接頂点「１」、「８」、「１０」、および「１５」を削除した結果、Ｇ頂点ＩＤ「１２」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１２」の次数の欄を８から７に更新する。また、隣接頂点「１」、「８」、「１０」、および「１５」を削除した結果、Ｇ頂点ＩＤ「１３」の隣接頂点の数が２つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１３」の次数の欄を８から６に更新する。また、隣接頂点「１」、「８」、「１０」、および「１５」を削除した結果、Ｇ頂点ＩＤ「１７」の隣接頂点の数が２つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１７」の次数の欄を６から４に更新する。

１つのペアを決定したので、ペア決定部１７は、再び次数の最も少なく、かつ、採否の欄が「未」であるＧ頂点ＩＤを取得する。
図３８に示すグラフ管理テーブル１７ｂでは、Ｇ頂点ＩＤ「２」、Ｇ頂点ＩＤ「７」、Ｇ頂点ＩＤ「９」、およびＧ頂点ＩＤ「１７」の次数がそれぞれ「４」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「２」、Ｇ頂点ＩＤ「７」、Ｇ頂点ＩＤ「９」、およびＧ頂点ＩＤ「１７」それぞれの枝距離の欄を参照し、値が小さいＧ頂点ＩＤに対応するペア候補をペアに決定する。ここで、Ｇ頂点ＩＤ「２」、「７」、「１７」の枝距離は、「２」であり、Ｇ頂点ＩＤ「９」の枝距離は「１．４」である。このため、ペア決定部１７は、グラフＧ頂点ＩＤ「９」に対応するネットＡのターゲットピンＰ１とネットＤのターゲットピンＰ１のペア候補をペアに決定する。すなわち、ペア決定部１７は、Ｇ頂点ＩＤ「９」の採否の欄を「採」に設定する。また、Ｇ頂点ＩＤ「９」の採択順の欄に「４」を設定する。ここで、図３３のグラフＬを参照すると、ネットＡのターゲットピンＰ１とネットＤのターゲットピンＰ１のペアの決定により、新たに枝「２」、「３」、「１１」、および「１２」のペアの可能性がなくなる。従って、ペア決定部１７は、Ｇ頂点ＩＤ「２」、「３」、「１１」、および「１２」の頂点を、グラフＧ１から削除する処理を行う。具体的には、図３８に示すように、ペア決定部１７は、Ｇ頂点ＩＤ「２」、「３」、「１１」、および「１２」の採否の欄を「否」に設定する。また、ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄が「未」の全てのレコードの隣接頂点の欄から、「２」、「３」、「１１」、および「１２」を削除する。隣接頂点「２」、「３」、「１１」、および「１２」を削除した結果、Ｇ頂点ＩＤ「４」の隣接頂点の数が３つ減るので、ペア決定部１７は、図３９に示すように、Ｇ頂点ＩＤ「４」の次数の欄を７から４に更新する。また、隣接頂点「２」、「３」、「１１」、および「１２」を削除した結果、Ｇ頂点ＩＤ「５」の隣接頂点の数が２つ減るので、ペア決定部１７は、図３９に示すように、Ｇ頂点ＩＤ「５」の次数の欄を５から３に更新する。また、隣接頂点「２」、「３」、「１１」、および「１２」を削除した結果、Ｇ頂点ＩＤ「６」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「６」の次数の欄を６から５に更新する。また、隣接頂点「２」、「３」、「１１」、および「１２」を削除した結果、Ｇ頂点ＩＤ「１３」の隣接頂点の数が２つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１３」の次数の欄を６から４に更新する。また、隣接頂点「２」、「３」、「１１」、および「１２」を削除した結果、Ｇ頂点ＩＤ「１７」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１７」の次数の欄を４から３に更新する。また、隣接頂点「２」、「３」、「１１」、および「１２」を削除した結果、Ｇ頂点ＩＤ「２５」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「２５」の次数の欄を６から５に更新する。

１つのペアを決定したので、ペア決定部１７は、再び次数の最も少なく、かつ、採否の欄が「未」であるＧ頂点ＩＤを取得する。
図３９に示すグラフ管理テーブル１７ｂでは、Ｇ頂点ＩＤ「５」およびＧ頂点ＩＤ「１７」の次数がそれぞれ「３」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「５」およびＧ頂点ＩＤ「１７」それぞれの枝距離の欄を参照し、値が小さいＧ頂点ＩＤに対応するペア候補をペアに決定する。ここで、Ｇ頂点ＩＤ「５」の枝距離は、「１」であり、Ｇ頂点ＩＤ「１７」の枝距離は「２」である。このため、ペア決定部１７は、グラフＧ頂点ＩＤ「５」に対応するネットＢのターゲットピンＰ１とネットＣのターゲットピンＰ１のペア候補をペアに決定する。すなわち、ペア決定部１７は、Ｇ頂点ＩＤ「５」の採否の欄を「採」に設定する。また、Ｇ頂点ＩＤ「５」の採択順の欄に「５」を設定する。ここで、図３３のグラフＬを参照すると、ネットＢのターゲットピンＰ１とネットＣのターゲットピンＰ１のペアの決定により、新たに枝「４」、「６」、および「７」のペアの可能性がなくなる。従って、ペア決定部１７は、Ｇ頂点ＩＤ「４」、「６」、および「７」の頂点を、グラフＧ１から削除する処理を行う。具体的には、図４０に示すように、ペア決定部１７は、Ｇ頂点ＩＤ「４」、「６」、および「７」の採否の欄を「否」に設定する。また、ペア決定部１７は、グラフ管理テーブル１７ａの採否の欄が「未」の全てのレコードの隣接頂点の欄から、「４」、「６」、および「７」を削除する。隣接頂点「４」、「６」、および「７」を削除した結果、Ｇ頂点ＩＤ「１３」の隣接頂点の数が２つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１３」の次数の欄を４から２に更新する。また、隣接頂点「４」、「６」、および「７」を削除した結果、Ｇ頂点ＩＤ「１７」の隣接頂点の数が１つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「１７」の次数の欄を３から２に更新する。また、隣接頂点「４」、「６」、および「７」を削除した結果、Ｇ頂点ＩＤ「２５」の隣接頂点の数が３つ減るので、ペア決定部１７は、Ｇ頂点ＩＤ「２５」の次数の欄を５から２に更新する。

１つのペアを決定したので、ペア決定部１７は、再び次数の最も少なく、かつ、採否の欄が「未」であるＧ頂点ＩＤを取得する。
図４１に示すグラフ管理テーブル１７ｂでは、Ｇ頂点ＩＤ「１３」、Ｇ頂点ＩＤ「１７」およびＧ頂点ＩＤ「２５」の次数がそれぞれ「２」である。このため、ペア決定部１７は、Ｇ頂点ＩＤ「１３」、Ｇ頂点ＩＤ「１７」およびＧ頂点ＩＤ「２５」それぞれの枝距離の欄を参照し、値が小さいＧ頂点ＩＤに対応するペア候補をペアに決定する。ここで、Ｇ頂点ＩＤ「１３」およびＧ頂点「２５」の枝距離は、「１．４」であり、Ｇ頂点ＩＤ「１７」の枝距離は「２」である。このため、ペア決定部１７は、ここで、Ｇ頂点ＩＤ「１３」およびＧ頂点「２５」それぞれの機会逸失距離の欄を参照し、値が小さいＧ頂点ＩＤに対応するペア候補をペアに決定する。ここで、Ｇ頂点ＩＤ「１３」の機会逸失距離は、「３．４」であり、Ｇ頂点ＩＤ「２５」の機会逸失距離は「３．４」である。そこで、初期の次数（隣接頂点の数）を比較し、値が小さいＧ頂点ＩＤに対応するペア候補をペアに決定する。ここで、Ｇ頂点ＩＤ「１３」の初期の次数は、「９」であり、Ｇ頂点ＩＤ「２５」の初期の次数は「６」である。このため、ペア決定部１７は、グラフＧ頂点ＩＤ「２５」に対応するネットＥのターゲットピンＰ１とネットＨのターゲットピンＰ１のペア候補をペアに決定する。すなわち、ペア決定部１７は、Ｇ頂点ＩＤ「２５」の採否の欄を「採」に設定する。また、Ｇ頂点ＩＤ「２５」の採択順の欄に「６」を設定する。ここで、図３３のグラフＬを参照すると、ネットＥのターゲットピンＰ１とネットＨのターゲットピンＰ１のペアの決定により、新たに枝「１３」および「１７」のペアの可能性がなくなる。従って、ペア決定部１７は、Ｇ頂点ＩＤ「１３」およびＧ頂点ＩＤ「１７」の頂点を、グラフＧ１から削除する処理を行う。具体的には、図４１に示すように、ペア決定部１７は、Ｇ頂点ＩＤ「１３」およびＧ頂点ＩＤ「１７」の採否の欄を「否」に設定する。この結果、グラフ管理テーブル１７ｂの全ての採否の欄が「採」または「否」となったのでターゲットピンＰ１のペアを決定する処理を終了する。

図４２は、第５の実施の形態のピンペア情報記憶部に記憶されたターゲットピンのペアに関する情報を説明する図である。
グラフ管理テーブル１７ｂの採否の欄が「採」のＧ頂点ＩＤ「５」、「９」、「１４」、「２０」、「２４」、「２５」に対応する枝により、ソースピンＰ１同士が接続されている。

図４３は、第５の実施の形態のペア候補グラフ作成部およびペア決定部の処理を示すフローチャートである。
［ステップＳ２１］ ペア候補グラフ作成部１６は、ネットリスト１２ａからソースピンＰ１群およびターゲットピンＰ１群の座標データを読み込む。その後、ステップＳ２２に遷移する。

［ステップＳ２２］ ペア候補グラフ作成部１６は、ステップＳ２１にて読み込んだ座標データに基づいて領域１１１に配置されたソースピンＰ１間の距離を測定する。そして、ペア候補グラフ作成部１６は、距離係数テーブル２０ａを参照し、測定結果に距離係数を掛けてソースピン距離管理テーブル１６ｃに記憶する。そして、ペア候補グラフ作成部１６は、距離が２以下のソースピンＰ１の組み合わせを抽出してグラフＬを作成する。その後、ステップＳ２３に遷移する。

［ステップＳ２３］ ペア決定部１７は、ステップＳ２２にて作成されたグラフＬに基づいて、グラフＧ１およびグラフ管理テーブル１７ｂを作成する。その後、ステップＳ２４に遷移する。

［ステップＳ２４］ ペア決定部１７は、グラフ管理テーブル１７ｂの採否の欄が「未」のＧ頂点ＩＤを次の（１）〜（４）のキーワードでソートする。（１）次数（昇順）、（２）頂点に対応するグラフＬの枝距離（昇順）、（３）機会逸失距離（降順）、（４）初期状態での次数（昇順）。その後、ステップＳ２５に遷移する。

［ステップＳ２５］ ペア決定部１７は、ステップＳ２４のソートの結果に基づいて、グラフ管理テーブル１７ｂを更新するテーブル更新処理を行う。なお、テーブル更新処理については後述する。テーブル更新処理が終了するとステップＳ２６に遷移する。

［ステップＳ２６］ ペア決定部１７は、グラフＧ１の頂点の採否が全て終了したか否かを判断する。具体的には、ペア決定部１７は、グラフ管理テーブル１７ｂの採否の欄に「未」が存在するか否かを判断する。グラフ管理テーブル１７ｂの採否の欄に「未」が存在する場合（ステップＳ２６のＹｅｓ）、ステップＳ２４に遷移する。グラフ管理テーブル１７ｂの採否の欄に「未」が存在しない場合、すなわち、採否の欄が全て「採」または「否」の場合（ステップＳ２６のＮｏ）、ステップＳ２７に遷移する。

［ステップＳ２７］ ペア決定部１７は、グラフ管理テーブル１７ｂの採否の欄に「採」が設定されたバスピンＰ１のペアの情報をピンペア情報記憶部１９に記憶する。その後、図４３の処理を終了する。

次に、ステップＳ２５のテーブル更新処理を説明する。
図４４は、第５の実施の形態のテーブル更新処理を示すフローチャートである。
［ステップＳ２５ａ］ ペア決定部１７は、ステップＳ５のソートの結果、一番上に表示されたＧ頂点ＩＤを変数Ｖｔに設定する。その後、ステップＳ２５ｂに遷移する。

［ステップＳ２５ｂ］ ペア決定部１７は、グラフ管理テーブル１７ｂの隣接頂点の欄を参照し、変数Ｖｔに隣接するＧ頂点ＩＤを全て抽出する。その後、ステップＳ２５ｃに遷移する。

［ステップＳ２５ｃ］ ペア決定部１７は、ステップＳ２５ｂにて抽出したＧ頂点ＩＤを１つ選択する。その後、ステップＳ２５ｄに遷移する。
［ステップＳ２５ｄ］ ペア決定部１７は、ステップＳ２５ｃにて選択したＧ頂点ＩＤを変数Ｖｘに代入する。その後、ステップＳ２５ｅに遷移する。

［ステップＳ２５ｅ］ ペア決定部１７は、変数Ｖｘに隣接する全てのＧ頂点ＩＤの次数を１減らす。その後、ステップＳ２５ｆに遷移する。
［ステップＳ２５ｆ］ ペア決定部１７は、変数Ｖｘの採否の欄を「否」に設定する。その後、ステップＳ２５ｇに遷移する。

［ステップＳ２５ｇ］ ペア決定部１７は、ステップＳ２５ｂにて抽出した全てのＧ頂点ＩＤについてステップＳ２５ｃ〜Ｓ２５ｆの処理を行ったか否かを判断する。ステップＳ２５ｂにて抽出した全てのＧ頂点ＩＤについてステップＳ２５ｃ〜Ｓ２５ｆの処理を行った場合（ステップＳ２５ｇのＹｅｓ）、ステップＳ２５ｈに遷移する。ステップＳ２５ｂにて抽出した全てのＧ頂点ＩＤについてステップＳ２５ｃ〜Ｓ２５ｆの処理を行っていない場合（ステップＳ２５ｇのＮｏ）、ステップＳ２５ｃに遷移し、ステップＳ２５ｃ以降の処理を引き続き行う。

［ステップＳ２５ｈ］ ペア決定部１７は、変数Ｖｔに設定されているＧ頂点ＩＤの採否の欄を「採」に設定する。その後、テーブル更新処理を終了する。
この第５の実施の形態の回路設計支援装置１０によれば、第２の実施の形態の回路設計支援装置１０と同様の効果が得られる。

そして、第５の実施の形態の回路設計支援装置１０によれば、ネットの変更が可能な集積回路が領域１１２に配置される場合には、ターゲットピンＰ１側のネット分布を考慮せず領域１１１に配置されたソースピンＰ１側のみでペアを決定することができる。そして、調整部２１が、ペア決定部１７が決定したソースピンＰ１のペアのネットと同じネットのターゲットピンＰ１の距離が２以下になるように、ターゲットピンＰ１のネットの割り当てを調整することで、配線スペースを効率よく使った配線を実現することができる。

なお、回路設計支援装置１０が行った処理が、複数の装置によって分散処理されるようにしてもよい。例えば、１つの装置が、グラフＬ、Ｒ、Ｇの作成までを行ってペア候補を作成しておき、他の装置が、そのペア候補を用いてバスピンＰ１のペアを決定するようにしてもよい。

以上、本発明の回路設計支援装置、回路設計支援方法および回路設計支援プログラムを、図示の実施の形態に基づいて説明したが、本発明はこれに限定されるものではなく、各部の構成は、同様の機能を有する任意の構成のものに置換することができる。また、本発明に、他の任意の構成物や工程が付加されていてもよい。

また、本発明は、前述した各実施の形態のうちの、任意の２以上の構成（特徴）を組み合わせたものであってもよい。
なお、上記の処理機能は、コンピュータによって実現することができる。その場合、回路設計支援装置１、１０、１０ａ、１０ｂが有する機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリ等が挙げられる。磁気記憶装置には、ハードディスクドライブ、フレキシブルディスク（ＦＤ）、磁気テープ等が挙げられる。光ディスクには、ＤＶＤ、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ／ＲＷ等が挙げられる。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）等が挙げられる。

プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。

プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、ネットワークを介して接続されたサーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。

また、上記の処理機能の少なくとも一部を、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＰＬＤ（Programmable Logic Device）等の電子回路で実現することもできる。

以上の第１〜第５の実施の形態に関し、さらに以下の付記を開示する。
（付記１） 配線の論理接続情報を有するピンを複数備える第１のピン群と、前記第１のピン群の各ピンの配線の接続先となり前記論理接続情報を有するピンを備える第２のピン群とが与えられたとき、前記第１のピン群および前記第２のピン群それぞれにおいて所定距離内にある同じ前記論理接続情報を有するピン同士をペア候補に決定するペア候補決定部と、
前記ペア候補決定部が決定した前記ペア候補を用いて前記第１のピン群および前記第２のピン群それぞれのピンのペアを決定するペア決定部と、
を有することを特徴とする回路設計支援装置。

（付記２） 前記ペア決定部は、前記第１のピン群と前記第２のピン群のうちいずれか一方のピン群の前記各ペア候補について、隣接する前記ペア候補の数が少ない前記ペア候補を優先してペアに決定することを特徴とする付記１記載の回路設計支援装置。

（付記３） 前記ペア決定部は、ペアに決定した前記ペア候補を、隣接する前記ペア候補の数から除外して次のピンのペアを決定する処理を繰り返し実行することを特徴とする付記２記載の回路設計支援装置。

（付記４） 前記ペア決定部は、隣接する前記ペア候補の数が等しい前記ペア候補が複数存在する場合、当該ペア候補それぞれの前記第１のピン群での距離および前記第２のピン群での距離の和が小さいペア候補をペアに決定することを特徴とする付記２記載の回路設計支援装置。

（付記５） 前記ペア決定部は、隣接する前記ペア候補それぞれの第１のピン群および前記第２のピン群での距離の和が等しい場合、当該ペア候補のピンを含む当該ペア候補以外の全ての前記ペア候補の距離の和を前記第１のピン群と前記第２のピン群について求め、前記距離の和が大きい方をペアに決定することを特徴とする付記４記載の回路設計支援装置。

（付記６） 前記ペア候補決定部は、ピンに付与された信号の種別を識別する識別情報を参照して、同じ前記識別情報が付与されたピン間について前記ペア候補を決定することを特徴とする付記１ないし５のいずれかに記載の回路設計支援装置。

（付記７） 前記ペア候補決定部は、ピンに付与された前記識別情報の組み合わせから決まる前記ピンのペアのなり易さを示す指標を用いて、前記ペア候補を決定することを特徴とする付記６記載の回路設計支援装置。

（付記８） コンピュータが、配線の論理接続情報を有するピンを複数備える第１のピン群と、前記第１のピン群の各ピンの配線の接続先となり前記論理接続情報を有するピンを備える第２のピン群とが与えられたとき、前記第１のピン群および前記第２のピン群それぞれにおいて所定距離内にある同じ前記論理接続情報を有するピン同士をペア候補に決定し、
前記決定された前記ペア候補を用いて前記第１のピン群および前記第２のピン群それぞれのピンのペアを決定する、
ことを特徴とする回路設計支援方法。

（付記９） コンピュータに、
配線の論理接続情報を有するピンを複数備える第１のピン群と、前記第１のピン群の各ピンの配線の接続先となり前記論理接続情報を有するピンを備える第２のピン群とが与えられたとき、前記第１のピン群および前記第２のピン群それぞれにおいて所定距離内にある同じ前記論理接続情報を有するピン同士をペア候補に決定し、
決定された前記ペア候補を用いて前記第１のピン群および前記第２のピン群それぞれのピンのペアを決定する、
処理を実行させることを特徴とする回路設計支援プログラム。

（付記１０） 配線の論理接続情報を有するピンを複数備える第１のピン群が与えられたとき、与えられた前記第１のピン群において所定距離内にあるピン同士をペア候補に決定するペア候補決定部と、
前記ペア候補決定部が決定した前記ペア候補を用いて前記第１のピン群のピンのペアを決定するペア決定部と、
前記ペア決定部の決定に応じて前記第１のピン群の各ピンの配線の接続先となるピンを備える第２のピン群の論理接続情報の割り当てを調整する調整部と、
を有することを特徴とする回路設計支援装置。

（付記１１） 前記ペア決定部は、前記第１のピン群の前記各ペア候補について、隣接するペア候補の数が少ないペア候補を優先してペアに決定することを特徴とする付記１０記載の回路設計支援装置。

（付記１２） 前記ペア決定部は、ペアに決定した前記ペア候補を、隣接する前記ペア候補の数から除外することを特徴とする付記１１記載の回路設計支援装置。
（付記１３） 前記ペア決定部は、隣接する前記ペア候補の数が等しい前記ペア候補が複数存在する場合、当該ペア候補それぞれの前記第１のピン群での距離の和が小さいペア候補をペアに決定することを特徴とする付記１１記載の回路設計支援装置。

（付記１４） 前記ペア決定部は、隣接する前記ペア候補それぞれの第１のピン群での距離の和が等しい場合、当該ペア候補のピンを含む当該ペア候補以外の全ての前記ペア候補の距離の和を前記第１のピン群について求め、前記距離の和が大きい方をペアに決定することを特徴とする付記１３記載の回路設計支援装置。

（付記１５） 前記ペア決定部は、ペアに決定した前記ペア候補を、隣接する前記ペア候補の数から除外して次のピンのペアを決定する処理を繰り返し実行し、
当該ペア候補のピンを含む当該ペア候補以外の全ての前記ペア候補の距離の和が等しい場合、ペアに決定した前記ペア候補を含めた隣接するペア候補の数が少ないペア候補を優先してペアに決定することを特徴とする付記１４記載の回路設計支援装置。

（付記１６） 前記ペア候補決定部は、ピンに付与された信号の種別を識別する識別情報を参照して、同じ前記識別情報が付与されたピン間についてペア候補を決定することを特徴とする付記１０ないし１５のいずれかに記載の回路設計支援装置。

（付記１７） 前記ペア候補決定部は、ピンに付与された前記識別情報の組み合わせから決まる前記ピンのペアのなり易さを示す指標を用いて、前記ペア候補を決定することを特徴とする付記１６記載の回路設計支援装置。

（付記１８）コンピュータが、
配線の論理接続情報を有するピンを複数備える第１のピン群が与えられたとき、与えられた前記第１のピン群において所定距離内にあるピン同士をペア候補に決定し、
決定された前記ペア候補を用いて前記第１のピン群のピンのペアを決定し、
前記ペアの決定に応じて前記第１のピン群の各ピンの配線の接続先となるピンを備える前記第２のピン群の論理接続情報の割り当てを調整する、
ことを特徴とする回路設計支援方法。

（付記１９）コンピュータに、
配線の論理接続情報を有するピンを複数備える第１のピン群が与えられたとき、与えられた前記第１のピン群において所定距離内にあるピン同士をペア候補に決定し、
決定された前記ペア候補を用いて前記第１のピン群のピンのペアを決定し、
前記ペアの決定に応じて前記第１のピン群の各ピンの配線の接続先となるピンを備える前記第２のピン群の論理接続情報の割り当てを調整する、
処理を実行させることを特徴とする回路設計支援プログラム。

１、１０、１０ａ、１０ｂ 回路設計支援装置
１ａ 基板情報格納部
１ｂ ペア候補決定部
１ｃ ペア決定部
１ｄ 配線部
１１ バスピン群記憶部
１２ ピン座標情報記憶部
１２ａ、１２ｂ、１２ｃ ネットリスト
１３ ネット情報記憶部
１４ 部品情報記憶部
１５ ネット種別情報記憶部
１６ ペア候補グラフ作成部
１６ａ、１６ｃ ソースピン距離管理テーブル
１６ｂ、１６ｄ ターゲットピン距離管理テーブル
１７ ペア決定部
１７ａ グラフ管理テーブル
１８ 結果出力部
１９ ピンペア情報記憶部
２０ 信号種別距離係数記憶部
２０ａ 距離係数テーブル
２１ 調整部
１１０ 基板
１１１、１１２ 領域
Ｐ１、Ｐ１ａ〜Ｐ４ａ、Ｐ１ｂ〜Ｐ４ｂ バスピン
Ｇ、Ｌ、Ｌ１、Ｌ２、Ｒ、Ｒ１、Ｒ２ グラフ

Claims (9)

1. 配線の論理接続情報を有するピンを複数備える第１のピン群と、前記第１のピン群の各ピンの配線の接続先となり前記論理接続情報を有するピンを備える第２のピン群とが与えられたとき、前記第１のピン群および前記第２のピン群それぞれにおいて所定距離内にある異なる前記論理接続情報を有するピン同士をペア候補に決定するペア候補決定部と、
   前記ペア候補決定部が決定した前記ペア候補を用いて前記第１のピン群および前記第２のピン群それぞれのピンのペアを決定するペア決定部と、
   を有することを特徴とする回路設計支援装置。
2. 前記ペア決定部は、前記各ペア候補について、隣接する前記ペア候補の数が少ない前記ペア候補を優先してペアに決定することを特徴とする請求項１記載の回路設計支援装置。
3. 前記ペア決定部は、隣接する前記ペア候補の数が等しい前記ペア候補が複数存在する場合、当該ペア候補それぞれの前記第１のピン群での距離および前記第２のピン群での距離の和が小さいペア候補をペアに決定することを特徴とする請求項２記載の回路設計支援装置。
4. 前記ペア決定部は、隣接する前記ペア候補それぞれの前記第１のピン群および前記第２のピン群での距離の和が等しい場合、当該ペア候補のピンを含む当該ペア候補以外の全ての前記ペア候補の距離の和を前記第１のピン群と前記第２のピン群について求め、前記距離の和が大きい方をペアに決定することを特徴とする請求項３記載の回路設計支援装置。
5. 前記ペア候補決定部は、ピンに付与された信号の種別を識別する識別情報を参照して、同じ前記識別情報が付与されたピン間について前記ペア候補を決定することを特徴とする請求項１ないし４のいずれかに記載の回路設計支援装置。
6. 前記ペア候補決定部は、ピンに付与された前記識別情報の組み合わせから決まる前記ピンのペアのなり易さを示す指標を用いて、前記ペア候補を決定することを特徴とする請求項５記載の回路設計支援装置。
7. コンピュータが、配線の論理接続情報を有するピンを複数備える第１のピン群と、前記第１のピン群の各ピンの配線の接続先となり前記論理接続情報を有するピンを備える第２のピン群とが与えられたとき、前記第１のピン群および前記第２のピン群それぞれにおいて所定距離内にある異なる前記論理接続情報を有するピン同士をペア候補に決定し、
   前記決定された前記ペア候補を用いて前記第１のピン群および前記第２のピン群それぞれのピンのペアを決定する、
   ことを特徴とする回路設計支援方法。
8. コンピュータに、
   配線の論理接続情報を有するピンを複数備える第１のピン群と、前記第１のピン群の各ピンの配線の接続先となり前記論理接続情報を有するピンを備える第２のピン群とが与えられたとき、前記第１のピン群および前記第２のピン群それぞれにおいて所定距離内にある異なる前記論理接続情報を有するピン同士をペア候補に決定し、
   決定された前記ペア候補を用いて前記第１のピン群および前記第２のピン群それぞれのピンのペアを決定する、
   処理を実行させることを特徴とする回路設計支援プログラム。
9. 配線の論理接続情報を有するピンを複数備える第１のピン群が与えられたとき、与えられた前記第１のピン群において所定距離内にあるピン同士をペア候補に決定するペア候補決定部と、
   前記ペア候補決定部が決定した前記ペア候補を用いて前記第１のピン群のピンのペアを決定するペア決定部と、
   前記ペア決定部の決定に応じて前記第１のピン群の各ピンの配線の接続先となるピンを備える第２のピン群の論理接続情報の割り当てを調整する調整部と、
   を有することを特徴とする回路設計支援装置。

Images