(57)【特許請求の範囲】
【請求項１】
配線の論理接続情報を有するピンを複数備える第１のピン群と、前記第１のピン群の各ピンの配線の接続先となり前記論理接続情報を有するピンを備える第２のピン群とが与えられたとき、前記第１のピン群および前記第２のピン群それぞれにおいて所定距離内にある異なる前記論理接続情報を有するピン同士をペア候補に決定するペア候補決定部と、
前記ペア候補決定部が決定した前記ペア候補を用いて前記第１のピン群および前記第２のピン群それぞれのピンのペアを決定するペア決定部と、
を有することを特徴とする回路設計支援装置。
【請求項２】
前記ペア決定部は、前記各ペア候補について、隣接する前記ペア候補の数が少ない前記ペア候補を優先してペアに決定することを特徴とする請求項１記載の回路設計支援装置。
【請求項３】
前記ペア決定部は、隣接する前記ペア候補の数が等しい前記ペア候補が複数存在する場合、当該ペア候補それぞれの前記第１のピン群での距離および前記第２のピン群での距離の和が小さいペア候補をペアに決定することを特徴とする請求項２記載の回路設計支援装置。
【請求項４】
前記ペア決定部は、隣接する前記ペア候補それぞれの前記第１のピン群および前記第２のピン群での距離の和が等しい場合、当該ペア候補のピンを含む当該ペア候補以外の全ての前記ペア候補の距離の和を前記第１のピン群と前記第２のピン群について求め、前記距離の和が大きい方をペアに決定することを特徴とする請求項３記載の回路設計支援装置。
【請求項５】
前記ペア候補決定部は、ピンに付与された信号の種別を識別する識別情報を参照して、同じ前記識別情報が付与されたピン間について前記ペア候補を決定することを特徴とする請求項１ないし４のいずれかに記載の回路設計支援装置。
【請求項６】
前記ペア候補決定部は、ピンに付与された前記識別情報の組み合わせから決まる前記ピンのペアのなり易さを示す指標を用いて、前記ペア候補を決定することを特徴とする請求項５記載の回路設計支援装置。
【請求項７】
コンピュータが、配線の論理接続情報を有するピンを複数備える第１のピン群と、前記第１のピン群の各ピンの配線の接続先となり前記論理接続情報を有するピンを備える第２のピン群とが与えられたとき、前記第１のピン群および前記第２のピン群それぞれにおいて所定距離内にある異なる前記論理接続情報を有するピン同士をペア候補に決定し、
前記決定された前記ペア候補を用いて前記第１のピン群および前記第２のピン群それぞれのピンのペアを決定する、
ことを特徴とする回路設計支援方法。
【請求項８】
コンピュータに、
配線の論理接続情報を有するピンを複数備える第１のピン群と、前記第１のピン群の各ピンの配線の接続先となり前記論理接続情報を有するピンを備える第２のピン群とが与えられたとき、前記第１のピン群および前記第２のピン群それぞれにおいて所定距離内にある異なる前記論理接続情報を有するピン同士をペア候補に決定し、
決定された前記ペア候補を用いて前記第１のピン群および前記第２のピン群それぞれのピンのペアを決定する、
処理を実行させることを特徴とする回路設計支援プログラム。
【請求項９】
配線の論理接続情報を有するピンを複数備える第１のピン群が与えられたとき、与えられた前記第１のピン群において所定距離内にあるピン同士をペア候補に決定するペア候補決定部と、
前記ペア候補決定部が決定した前記ペア候補を用いて前記第１のピン群のピンのペアを決定するペア決定部と、
前記ペア決定部の決定に応じて前記第１のピン群の各ピンの配線の接続先となるピンを備える第２のピン群の論理接続情報の割り当てを調整する調整部と、
を有することを特徴とする回路設計支援装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は回路設計支援装置、回路設計支援方法および回路設計支援プログラムに関する。
【背景技術】
【０００２】
ＢＧＡ（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）等の電子回路で実現することもできる。
【０１４６】
以上の第１〜第５の実施の形態に関し、さらに以下の付記を開示する。
（付記１）  配線の論理接続情報を有するピンを複数備える第１のピン群と、前記第１のピン群の各ピンの配線の接続先となり前記論理接続情報を有するピンを備える第２のピン群とが与えられたとき、前記第１のピン群および前記第２のピン群それぞれにおいて所定距離内にある同じ前記論理接続情報を有するピン同士をペア候補に決定するペア候補決定部と、
前記ペア候補決定部が決定した前記ペア候補を用いて前記第１のピン群および前記第２のピン群それぞれのピンのペアを決定するペア決定部と、
を有することを特徴とする回路設計支援装置。
【０１４７】
（付記２）  前記ペア決定部は、前記第１のピン群と前記第２のピン群のうちいずれか一方のピン群の前記各ペア候補について、隣接する前記ペア候補の数が少ない前記ペア候補を優先してペアに決定することを特徴とする付記１記載の回路設計支援装置。
【０１４８】
（付記３）  前記ペア決定部は、ペアに決定した前記ペア候補を、隣接する前記ペア候補の数から除外して次のピンのペアを決定する処理を繰り返し実行することを特徴とする付記２記載の回路設計支援装置。
【０１４９】
（付記４）  前記ペア決定部は、隣接する前記ペア候補の数が等しい前記ペア候補が複数存在する場合、当該ペア候補それぞれの前記第１のピン群での距離および前記第２のピン群での距離の和が小さいペア候補をペアに決定することを特徴とする付記２記載の回路設計支援装置。
【０１５０】
（付記５）  前記ペア決定部は、隣接する前記ペア候補それぞれの第１のピン群および前記第２のピン群での距離の和が等しい場合、当該ペア候補のピンを含む当該ペア候補以外の全ての前記ペア候補の距離の和を前記第１のピン群と前記第２のピン群について求め、前記距離の和が大きい方をペアに決定することを特徴とする付記４記載の回路設計支援装置。
【０１５１】
（付記６）  前記ペア候補決定部は、ピンに付与された信号の種別を識別する識別情報を参照して、同じ前記識別情報が付与されたピン間について前記ペア候補を決定することを特徴とする付記１ないし５のいずれかに記載の回路設計支援装置。
【０１５２】
（付記７）  前記ペア候補決定部は、ピンに付与された前記識別情報の組み合わせから決まる前記ピンのペアのなり易さを示す指標を用いて、前記ペア候補を決定することを特徴とする付記６記載の回路設計支援装置。
【０１５３】
（付記８）  コンピュータが、配線の論理接続情報を有するピンを複数備える第１のピン群と、前記第１のピン群の各ピンの配線の接続先となり前記論理接続情報を有するピンを備える第２のピン群とが与えられたとき、前記第１のピン群および前記第２のピン群それぞれにおいて所定距離内にある同じ前記論理接続情報を有するピン同士をペア候補に決定し、
前記決定された前記ペア候補を用いて前記第１のピン群および前記第２のピン群それぞれのピンのペアを決定する、
ことを特徴とする回路設計支援方法。
【０１５４】
（付記９）  コンピュータに、
配線の論理接続情報を有するピンを複数備える第１のピン群と、前記第１のピン群の各ピンの配線の接続先となり前記論理接続情報を有するピンを備える第２のピン群とが与えられたとき、前記第１のピン群および前記第２のピン群それぞれにおいて所定距離内にある同じ前記論理接続情報を有するピン同士をペア候補に決定し、
決定された前記ペア候補を用いて前記第１のピン群および前記第２のピン群それぞれのピンのペアを決定する、
処理を実行させることを特徴とする回路設計支援プログラム。
【０１５５】
（付記１０）  配線の論理接続情報を有するピンを複数備える第１のピン群が与えられたとき、与えられた前記第１のピン群において所定距離内にあるピン同士をペア候補に決定するペア候補決定部と、
前記ペア候補決定部が決定した前記ペア候補を用いて前記第１のピン群のピンのペアを決定するペア決定部と、
前記ペア決定部の決定に応じて前記第１のピン群の各ピンの配線の接続先となるピンを備える第２のピン群の論理接続情報の割り当てを調整する調整部と、
を有することを特徴とする回路設計支援装置。
【０１５６】
（付記１１）  前記ペア決定部は、前記第１のピン群の前記各ペア候補について、隣接するペア候補の数が少ないペア候補を優先してペアに決定することを特徴とする付記１０記載の回路設計支援装置。
【０１５７】
（付記１２）  前記ペア決定部は、ペアに決定した前記ペア候補を、隣接する前記ペア候補の数から除外することを特徴とする付記１１記載の回路設計支援装置。
（付記１３）  前記ペア決定部は、隣接する前記ペア候補の数が等しい前記ペア候補が複数存在する場合、当該ペア候補それぞれの前記第１のピン群での距離の和が小さいペア候補をペアに決定することを特徴とする付記１１記載の回路設計支援装置。
【０１５８】
（付記１４）  前記ペア決定部は、隣接する前記ペア候補それぞれの第１のピン群での距離の和が等しい場合、当該ペア候補のピンを含む当該ペア候補以外の全ての前記ペア候補の距離の和を前記第１のピン群について求め、前記距離の和が大きい方をペアに決定することを特徴とする付記１３記載の回路設計支援装置。
【０１５９】
（付記１５）  前記ペア決定部は、ペアに決定した前記ペア候補を、隣接する前記ペア候補の数から除外して次のピンのペアを決定する処理を繰り返し実行し、
当該ペア候補のピンを含む当該ペア候補以外の全ての前記ペア候補の距離の和が等しい場合、ペアに決定した前記ペア候補を含めた隣接するペア候補の数が少ないペア候補を優先してペアに決定することを特徴とする付記１４記載の回路設計支援装置。
【０１６０】
（付記１６）  前記ペア候補決定部は、ピンに付与された信号の種別を識別する識別情報を参照して、同じ前記識別情報が付与されたピン間についてペア候補を決定することを特徴とする付記１０ないし１５のいずれかに記載の回路設計支援装置。
【０１６１】
（付記１７）  前記ペア候補決定部は、ピンに付与された前記識別情報の組み合わせから決まる前記ピンのペアのなり易さを示す指標を用いて、前記ペア候補を決定することを特徴とする付記１６記載の回路設計支援装置。
【０１６２】
（付記１８）コンピュータが、
配線の論理接続情報を有するピンを複数備える第１のピン群が与えられたとき、与えられた前記第１のピン群において所定距離内にあるピン同士をペア候補に決定し、
決定された前記ペア候補を用いて前記第１のピン群のピンのペアを決定し、
前記ペアの決定に応じて前記第１のピン群の各ピンの配線の接続先となるピンを備える前記第２のピン群の論理接続情報の割り当てを調整する、
ことを特徴とする回路設計支援方法。
【０１６３】
（付記１９）コンピュータに、
配線の論理接続情報を有するピンを複数備える第１のピン群が与えられたとき、与えられた前記第１のピン群において所定距離内にあるピン同士をペア候補に決定し、
決定された前記ペア候補を用いて前記第１のピン群のピンのペアを決定し、
前記ペアの決定に応じて前記第１のピン群の各ピンの配線の接続先となるピンを備える前記第２のピン群の論理接続情報の割り当てを調整する、
処理を実行させることを特徴とする回路設計支援プログラム。
【符号の説明】
【０１６４】
１、１０、１０ａ、１０ｂ  回路設計支援装置
１ａ  基板情報格納部
１ｂ  ペア候補決定部
１ｃ  ペア決定部
１ｄ  配線部
１１  バスピン群記憶部
１２  ピン座標情報記憶部
１２ａ、１２ｂ、１２ｃ  ネットリスト
１３  ネット情報記憶部
１４  部品情報記憶部
１５  ネット種別情報記憶部
１６  ペア候補グラフ作成部
１６ａ、１６ｃ  ソースピン距離管理テーブル
１６ｂ、１６ｄ  ターゲットピン距離管理テーブル
１７  ペア決定部
１７ａ  グラフ管理テーブル
１８  結果出力部
１９  ピンペア情報記憶部
２０  信号種別距離係数記憶部
２０ａ  距離係数テーブル
２１  調整部
１１０  基板
１１１、１１２  領域
Ｐ１、Ｐ１ａ〜Ｐ４ａ、Ｐ１ｂ〜Ｐ４ｂ  バスピン
Ｇ、Ｌ、Ｌ１、Ｌ２、Ｒ、Ｒ１、Ｒ２  グラフ
【図１】
0005776413.tif 000002
【図２】
0005776413.tif 000003
【図３】
0005776413.tif 000004
【図４】
0005776413.tif 000005
【図５】
0005776413.tif 000006
【図６】
0005776413.tif 000007
【図７】
0005776413.tif 000008
【図８】
0005776413.tif 000009
【図９】
0005776413.tif 000010
【図１０】
0005776413.tif 000011
【図１１】
0005776413.tif 000012
【図１２】
0005776413.tif 000013
【図１３】
0005776413.tif 000014
【図１４】
0005776413.tif 000015
【図１５】
0005776413.tif 000016
【図１６】
0005776413.tif 000017
【図１７】
0005776413.tif 000018
【図１８】
0005776413.tif 000019
【図１９】
0005776413.tif 000020
【図２０】
0005776413.tif 000021
【図２１】
0005776413.tif 000022
【図２２】
0005776413.tif 000023
【図２３】
0005776413.tif 000024
【図２４】
0005776413.tif 000025
【図２５】
0005776413.tif 000026
【図２６】
0005776413.tif 000027
【図２７】
0005776413.tif 000028
【図２８】
0005776413.tif 000029
【図２９】
0005776413.tif 000030
【図３０】
0005776413.tif 000031
【図３１】
0005776413.tif 000032
【図３２】
0005776413.tif 000033
【図３３】
0005776413.tif 000034
【図３４】
0005776413.tif 000035
【図３５】
0005776413.tif 000036
【図３６】
0005776413.tif 000037
【図３７】
0005776413.tif 000038
【図３８】
0005776413.tif 000039
【図３９】
0005776413.tif 000040
【図４０】
0005776413.tif 000041
【図４１】
0005776413.tif 000042
【図４２】
0005776413.tif 000043
【図４３】
0005776413.tif 000044
【図４４】
0005776413.tif 000045