(57)【特許請求の範囲】
【請求項１】
ひとつの信号源端子と複数の信号受信端子とを配線して配線経路を作成するためのプログラムであって、コンピュータに次の（ア）乃至（コ）の機能を実現させるためのプログラム。
（ア）互いに直交するＸ軸とＹ軸からなる２次元座標系において、前記信号源端子の座標と前記複数の信号受信端子のそれぞれの座標を取得する端子座標取得機能。
（イ）前記信号源端子を親ノードと定め、前記複数の信号受信端子を子ノードと定め、前記親ノードを始点とし前記複数の子ノードをそれぞれ終点とする複数のベクトルを未処理ベクトルと定めて、初期状態のベクトルパターンを作成するベクトルパターン作成機能。
（ウ）前記複数の未処理ベクトルに含まれる任意の二つのベクトルからなる可能な全てのベクトルペアについて、そのベクトルペアに属する二つのベクトルのＸ座標の重複値とＹ座標の重複値の和を算出して、その和が最大となるひとつのベクトルペア（以下「選択ベクトルペア」という。）を選択し、その選択ベクトルペアについて前記Ｘ座標の重複値と前記Ｙ座標の重複値からなる座標を終点とし前記信号源端子を始点とするベクトル（以下「重複ベクトル」という。）を作成する重複ベクトル作成機能。
（エ）前記選択ベクトルペアについて、前記重複ベクトルの終点を第１結合点とし、この第１結合点を始点とし前記選択ベクトルペアに係る二つの前記信号受信端子を終点とする二つのベクトルを結線確定ベクトルとし、それらの結線確定ベクトルに係る二つの未処理ベクトルを削除して、前記重複ベクトルを新たに未処理ベクトルと定めて、新しいベクトルパターンを作る第１結合機能。
（オ）前記選択ベクトルペアについて、前記選択ベクトルペアに属する二つのベクトルのうちの短い方のベクトル（以下「短ベクトル」という。）の終点を第２結合点とし、この第２結合点を始点とし前記選択ベクトルペアに属する二つのベクトルのうちの長い方のベクトル（以下「長ベクトル」という。）の終点を終点とするベクトルを結線確定ベクトルとし、前記長ベクトルに係る未処理ベクトルを削除して、前記短ベクトルに係る未処理ベクトルをそのまま残して、新しいベクトルパターンを作る第２結合機能。
（カ）前記選択ベクトルペアについて、前記選択ベクトルペアの長ベクトルの終点を第３結合点とし、この第３結合点を始点として前記選択ベクトルペアの短ベクトルの終点を終点とするベクトルを結線確定ベクトルとし、前記短ベクトルに係る未処理ベクトルを削除して、前記長ベクトルに係る未処理ベクトルをそのまま残して、新しいベクトルパターンを作る第３結合機能。
（キ）前記第１結合機能、第２結合機能及び第３結合機能をそれぞれ実行した後に、未処理ベクトルがひとつであるか否かを判断し、未処理ベクトルがひとつであるときは、その時点でのベクトルパターンを結線候補として取得し、未処理ベクトルが複数であるときは、その時点でのベクトルパターンを未処理パターンとして取得する結線候補取得機能。
（ク）前記未処理パターンが残っているか否かを判断し、未処理パターンが残っているときは任意の未処理パターンを選択して前記重複ベクトル作成機能から前記結線候補取得機能までを繰り返し、未処理パターンが残っていないときは結線候補の取得を完了させる未処理パターン存否判定機能。
（ケ）取得した複数の結線候補のそれぞれについて総配線長を求める総配線長算出機能。
（コ）前記複数の総配線長について、最小の総配線長を有する結線候補がひとつである場合は、その結線候補を最適配線経路として取得し、最小の総配線長を有する結線候補が複数である場合は、それらの結線候補において、前記信号源端子と複数の前記信号受信端子とを結ぶ配線の長さ（以下「ＤＲ間配線長」という。）のうちで最大のものを結線候補同士で互いに比較して、最大ＤＲ間配線長が一番小さい結線候補を最適配線経路として取得する最適配線経路取得機能。
【請求項２】
ひとつの信号源端子と複数の信号受信端子とを配線して配線経路を作成する方法であって、プログラムされたコンピュータが、次の（ア）乃至（コ）のステップを実行する方法。
（ア）互いに直交するＸ軸とＹ軸からなる２次元座標系において、前記信号源端子の座標と前記複数の信号受信端子のそれぞれの座標を取得する端子座標取得ステップ。
（イ）前記信号源端子を親ノードと定め、前記複数の信号受信端子を子ノードと定め、前記親ノードを始点とし前記複数の子ノードをそれぞれ終点とする複数のベクトルを未処理ベクトルと定めて、初期状態のベクトルパターンを作成するベクトルパターン作成ステップ。
（ウ）前記複数の未処理ベクトルに含まれる任意の二つのベクトルからなる可能な全てのベクトルペアについて、そのベクトルペアに属する二つのベクトルのＸ座標の重複値とＹ座標の重複値の和を算出して、その和が最大となるひとつのベクトルペア（以下「選択ベクトルペア」という。）を選択し、その選択ベクトルペアについて前記Ｘ座標の重複値と前記Ｙ座標の重複値からなる座標を終点とし前記信号源端子を始点とするベクトル（以下「重複ベクトル」という。）を作成する重複ベクトル作成ステップ。
（エ）前記選択ベクトルペアについて、前記重複ベクトルの終点を第１結合点とし、この第１結合点を始点とし前記選択ベクトルペアに係る二つの前記信号受信端子を終点とする二つのベクトルを結線確定ベクトルとし、それらの結線確定ベクトルに係る二つの未処理ベクトルを削除して、前記重複ベクトルを新たに未処理ベクトルと定めて、新しいベクトルパターンを作る第１結合ステップ。
（オ）前記選択ベクトルペアについて、前記選択ベクトルペアに属する二つのベクトルのうちの短い方のベクトル（以下「短ベクトル」という。）の終点を第２結合点とし、この第２結合点を始点とし前記選択ベクトルペアに属する二つのベクトルのうちの長い方のベクトル（以下「長ベクトル」という。）の終点を終点とするベクトルを結線確定ベクトルとし、前記長ベクトルに係る未処理ベクトルを削除して、前記短ベクトルに係る未処理ベクトルをそのまま残して、新しいベクトルパターンを作る第２結合ステップ。
（カ）前記選択ベクトルペアについて、前記選択ベクトルペアの長ベクトルの終点を第３結合点とし、この第３結合点を始点として前記選択ベクトルペアの短ベクトルの終点を終点とするベクトルを結線確定ベクトルとし、前記短ベクトルに係る未処理ベクトルを削除して、前記長ベクトルに係る未処理ベクトルをそのまま残して、新しいベクトルパターンを作る第３結合ステップ。
（キ）前記第１結合ステップ、第２結合ステップ及び第３結合ステップをそれぞれ実行した後に、未処理ベクトルがひとつであるか否かを判断し、未処理ベクトルがひとつであるときは、その時点でのベクトルパターンを結線候補として取得し、未処理ベクトルが複数であるときは、その時点でのベクトルパターンを未処理パターンとして取得する結線候補取得ステップ。
（ク）前記未処理パターンが残っているか否かを判断し、未処理パターンが残っているときは任意の未処理パターンを選択して前記重複ベクトル作成ステップから前記結線候補取得ステップまでを繰り返し、未処理パターンが残っていないときは結線候補の取得を完了させる未処理パターン存否判定ステップ。
（ケ）取得した複数の結線候補のそれぞれについて総配線長を求める総配線長算出ステップ。
（コ）前記複数の総配線長について、最小の総配線長を有する結線候補がひとつである場合は、その結線候補を最適配線経路として取得し、最小の総配線長を有する結線候補が複数である場合は、それらの結線候補において、前記信号源端子と複数の前記信号受信端子とを結ぶ配線の長さ（以下「ＤＲ間配線長」という。）のうちで最大のものを結線候補同士で互いに比較して、最大ＤＲ間配線長が一番小さい結線候補を最適配線経路として取得する最適配線経路取得ステップ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ひとつの信号源端子（以下「ドライバ」という。）と複数の信号受信端子（以下「レシーバ」という。）とを配線する経路を作成するための配線経路作成プログラム及び配線経路作成方法に関するものである。
【背景技術】
【０００２】
配線基板等において、ひとつのドライバと複数のレシーバとを結線する場合に、総配線長をできる限り短くしたい、という要望がある。また、他方では、ドライバからレシーバに向かう個々の配線の配線長をできる限り短くしたい、という要望もある。総配線長を短くすることで、配線経路全体の浮遊容量を最小にできて、信号劣化を抑制できる。また、ドライバからレシーバに向かう配線に着目すると、特にその配線の長さを短くすることで、ドライバからレシーバに向かう信号の劣化を抑制できる。
【０００３】
多端子の相互接続に関して、最小の総配線長となるような配線経路を求める手法としてシュタイナー木を用いた解法が知られている。一般に、端子数が多くなると、可能なすべての配線経路を検討することで総配線長が最小となるような最適解を求めるには、膨大な計算が必要になる。これに対して、シュタイナー木の近似解を用いれば、比較的簡単に、最短の配線経路を見つけることができる。特開昭６２−３９０２４号公報（特許文献１）の第３図はその近似解の求め方を示している。それによれば、まず、多数の端子のうち、互いの距離が一番短い二つの端子を選び、その間に仮想経路を作成する。次に、その仮想経路に一番近い距離にある次の端子を選び、その端子と仮想経路を結んで、それを新しい仮想経路とする。以下同様に、次々と端子を結んでいけば、近似的に総配線長が最小の配線経路を求めることができる。この手法は、特開２００５−２７５７８０号公報（特許文献２）の図５でも説明されている。このような手法を、以下、シュタイナー木の近似解と呼ぶことにする。
【０００４】
上述のシュタイナー木の近似解は、総配線長が最小となる経路を簡便に求めるには便利であるが、ドライバとレシーバとを区別していないところに問題がある。ひとつのドライバから複数のレシーバに向かう個々の配線を考えて、それらの経路（レシーバの数だけ存在する。）のうちで一番長い配線の長さを最大ＤＲ間配線長と呼ぶことにする。総配線長が最小となるような配線経路は、複数種類存在することがあり、その中には、最大ＤＲ間配線長が異なるものがあり得る。シュタイナー木の近似解は、総配線長が最小となるような配線経路をひとつだけ探す手法であるので、その配線経路が、総配線長が最小となる複数の配線経路の中で最大ＤＲ間配線長が最小であるとは限らない。すなわち、シュタイナー木の近似解は、ドライバ・レシーバ間の信号の流れまで考慮すると、必ずしも最適な解とは言い難い。
【０００５】
一方、ドライバ・レシーバ間の信号の流れを考慮して最適な配線経路を作成する手法が知られている。特開平１１−１６７５６４号公報（特許文献３）はそのような手法を開示しており、ドライバからレシーバに向かう個々の配線経路について、それらの間の「重複コスト」という概念を用いて、重複コストが最大になるように配線経路を共有させて、最適な配線経路を求めている。この方法を、以下、「重複コスト最大化法」と呼ぶ。この重複コスト最大化法を用いると、常に、ドライバ・レシーバ間の配線経路が最短となるような配線経路を作ることができるが、端子配置によっては、上述のシュタイナー木の近似解のものよりも総配線長が大きくなる。したがって、重複コスト最大化法を用いると、必ずしも総配線長が最小の配線経路は得られない。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開昭６２−３９０２４号公報
【特許文献２】特開２００５−２７５７８０号公報
【特許文献３】特開平１１−１６７５６４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
ある端子配置では、シュタイナー木の近似解を用いることで、総配線長が最小になり、かつ、最大ＤＲ間配線長も最小になり得るが、別の端子配置では、最大ＤＲ間配線長は最小にならない。また、ある端子配置では、重複コスト最大化法を用いることで、最大ＤＲ間配線長が最小になり、かつ、総配線長も最小になり得るが、別の端子配置では、総配線長が最小にならない。
【０００８】
本発明は、上述の問題点を解決するためになされたものであって、その目的は、ひとつのドライバと複数のドライバを配線するための配線経路を作成するプログラムに関して、総配線長が最小になり、かつ、総配線長が最小の配線経路が複数存在する場合は、その中でも最大ＤＲ間配線長が一番小さい配線経路を、自動的に求めることができるようなプログラムを提供することにあり、また、そのようなプログラムを用いて配線経路を作成する方法を提供することにある。
【課題を解決するための手段】
【０００９】
本発明のプログラムは、ひとつの信号源端子と複数の信号受信端子とを配線して配線経路を作成するためのプログラムであって、コンピュータに次の（ア）乃至（コ）の機能を実現させることを特徴とする。（ア）互いに直交するＸ軸とＹ軸からなる２次元座標系において、前記信号源端子の座標と前記複数の信号受信端子のそれぞれの座標を取得する端子座標取得機能。（イ）前記信号源端子を親ノードと定め、前記複数の信号受信端子を子ノードと定め、前記親ノードを始点とし前記複数の子ノードをそれぞれ終点とする複数のベクトルを未処理ベクトルと定めて、初期状態のベクトルパターンを作成するベクトルパターン作成機能。（ウ）前記複数の未処理ベクトルに含まれる任意の二つのベクトルからなる可能な全てのベクトルペアについて、そのベクトルペアに属する二つのベクトルのＸ座標の重複値とＹ座標の重複値の和を算出して、その和が最大となるひとつのベクトルペア（以下「選択ベクトルペア」という。）を選択し、その選択ベクトルペアについて前記Ｘ座標の重複値と前記Ｙ座標の重複値からなる座標を終点とし前記信号源端子を始点とするベクトル（以下「重複ベクトル」という。）を作成する重複ベクトル作成機能。（エ）前記選択ベクトルペアについて、前記重複ベクトルの終点を第１結合点とし、この第１結合点を始点とし前記選択ベクトルペアに係る二つの前記信号受信端子を終点とする二つのベクトルを結線確定ベクトルとし、それらの結線確定ベクトルに係る二つの未処理ベクトルを削除して、前記重複ベクトルを新たに未処理ベクトルと定めて、新しいベクトルパターンを作る第１結合機能。（オ）前記選択ベクトルペアについて、前記選択ベクトルペアに属する二つのベクトルのうちの短い方のベクトル（以下「短ベクトル」という。）の終点を第２結合点とし、この第２結合点を始点とし前記選択ベクトルペアに属する二つのベクトルのうちの長い方のベクトル（以下「長ベクトル」という。）の終点を終点とするベクトルを結線確定ベクトルとし、前記長ベクトルに係る未処理ベクトルを削除して、前記短ベクトルに係る未処理ベクトルをそのまま残して、新しいベクトルパターンを作る第２結合機能。（カ）前記選択ベクトルペアについて、前記選択ベクトルペアの長ベクトルの終点を第３結合点とし、この第３結合点を始点として前記選択ベクトルペアの短ベクトルの終点を終点とするベクトルを結線確定ベクトルとし、前記短ベクトルに係る未処理ベクトルを削除して、前記長ベクトルに係る未処理ベクトルをそのまま残して、新しいベクトルパターンを作る第３結合機能。（キ）前記第１結合機能、第２結合機能及び第３結合機能をそれぞれ実行した後に、未処理ベクトルがひとつであるか否かを判断し、未処理ベクトルがひとつであるときは、その時点でのベクトルパターンを結線候補として取得し、未処理ベクトルが複数であるときは、その時点でのベクトルパターンを未処理パターンとして取得する結線候補取得機能。（ク）前記未処理パターンが残っているか否かを判断し、未処理パターンが残っているときは任意の未処理パターンを選択して前記重複ベクトル作成機能から前記結線候補取得機能までを繰り返し、未処理パターンが残っていないときは結線候補の取得を完了させる未処理パターン存否判定機能。（ケ）取得した複数の結線候補のそれぞれについて総配線長を求める総配線長算出機能。（コ）前記複数の総配線長について、最小の総配線長を有する結線候補がひとつである場合は、その結線候補を最適配線経路として取得し、最小の総配線長を有する結線候補が複数である場合は、それらの結線候補において、前記信号源端子と複数の前記信号受信端子とを結ぶ配線の長さ（以下「ＤＲ間配線長」という。）のうちで最大のものを結線候補同士で互いに比較して、最大ＤＲ間配線長が一番小さい結線候補を最適配線経路として取得する最適配線経路取得機能。
【００１０】
また、本発明の配線経路作成方法は、ひとつの信号源端子と複数の信号受信端子とを配線して配線経路を作成する方法であって、プログラムされたコンピュータが、次の（ア）乃至（コ）のステップを実行することを特徴とする。（ア）互いに直交するＸ軸とＹ軸からなる２次元座標系において、前記信号源端子の座標と前記複数の信号受信端子のそれぞれの座標を取得する端子座標取得ステップ。（イ）前記信号源端子を親ノードと定め、前記複数の信号受信端子を子ノードと定め、前記親ノードを始点とし前記複数の子ノードをそれぞれ終点とする複数のベクトルを未処理ベクトルと定めて、初期状態のベクトルパターンを作成するベクトルパターン作成ステップ。（ウ）前記複数の未処理ベクトルに含まれる任意の二つのベクトルからなる可能な全てのベクトルペアについて、そのベクトルペアに属する二つのベクトルのＸ座標の重複値とＹ座標の重複値の和を算出して、その和が最大となるひとつのベクトルペア（以下「選択ベクトルペア」という。）を選択し、その選択ベクトルペアについて前記Ｘ座標の重複値と前記Ｙ座標の重複値からなる座標を終点とし前記信号源端子を始点とするベクトル（以下「重複ベクトル」という。）を作成する重複ベクトル作成ステップ。（エ）前記選択ベクトルペアについて、前記重複ベクトルの終点を第１結合点とし、この第１結合点を始点とし前記選択ベクトルペアに係る二つの前記信号受信端子を終点とする二つのベクトルを結線確定ベクトルとし、それらの結線確定ベクトルに係る二つの未処理ベクトルを削除して、前記重複ベクトルを新たに未処理ベクトルと定めて、新しいベクトルパターンを作る第１結合ステップ。（オ）前記選択ベクトルペアについて、前記選択ベクトルペアに属する二つのベクトルのうちの短い方のベクトル（以下「短ベクトル」という。）の終点を第２結合点とし、この第２結合点を始点とし前記選択ベクトルペアに属する二つのベクトルのうちの長い方のベクトル（以下「長ベクトル」という。）の終点を終点とするベクトルを結線確定ベクトルとし、前記長ベクトルに係る未処理ベクトルを削除して、前記短ベクトルに係る未処理ベクトルをそのまま残して、新しいベクトルパターンを作る第２結合ステップ。（カ）前記選択ベクトルペアについて、前記選択ベクトルペアの長ベクトルの終点を第３結合点とし、この第３結合点を始点として前記選択ベクトルペアの短ベクトルの終点を終点とするベクトルを結線確定ベクトルとし、前記短ベクトルに係る未処理ベクトルを削除して、前記長ベクトルに係る未処理ベクトルをそのまま残して、新しいベクトルパターンを作る第３結合ステップ。（キ）前記第１結合ステップ、第２結合ステップ及び第３結合ステップをそれぞれ実行した後に、未処理ベクトルがひとつであるか否かを判断し、未処理ベクトルがひとつであるときは、その時点でのベクトルパターンを結線候補として取得し、未処理ベクトルが複数であるときは、その時点でのベクトルパターンを未処理パターンとして取得する結線候補取得ステップ。（ク）前記未処理パターンが残っているか否かを判断し、未処理パターンが残っているときは任意の未処理パターンを選択して前記重複ベクトル作成ステップから前記結線候補取得ステップまでを繰り返し、未処理パターンが残っていないときは結線候補の取得を完了させる未処理パターン存否判定ステップ。（ケ）取得した複数の結線候補のそれぞれについて総配線長を求める総配線長算出ステップ。（コ）前記複数の総配線長について、最小の総配線長を有する結線候補がひとつである場合は、その結線候補を最適配線経路として取得し、最小の総配線長を有する結線候補が複数である場合は、それらの結線候補において、前記信号源端子と複数の前記信号受信端子とを結ぶ配線の長さ（以下「ＤＲ間配線長」という。）のうちで最大のものを結線候補同士で互いに比較して、最大ＤＲ間配線長が一番小さい結線候補を最適配線経路として取得する最適配線経路取得ステップ。
【発明の効果】
【００１１】
本発明は、ひとつのドライバと複数のドライバを結線するための配線経路を作成するプログラムにおいて、総配線長が最小になり、かつ、総配線長が最小の配線経路が複数存在する場合は、その中でも最大ＤＲ間配線長が一番小さい配線経路を、自動的に求めることができる。そのような配線経路を求めるに当たって、可能なすべての結線候補を検討しなくても、特定の条件だけを考慮することで、検討すべき結線候補の数を絞ることができて、かつ、上述の目的を満足するような配線経路を得ることができる。
【図面の簡単な説明】
【００１２】
【図１】図１は本発明で使用する重複ベクトルを説明する説明図である。
【図２】図２は第１結合点の説明図である。
【図３】図３は第２結合点の説明図である。
【図４】図４は第３結合点の説明図である。
【図５】図５は端子配置例１と、配線経路を検討するためのベクトルパターンの初期状態を示したものである。
【図６】図６は条件１〜３のベクトルパターンを示したものである。
【図７】図７は条件１−１〜１−３のベクトルパターンを示したものである。
【図８】図８は条件２−１〜２−３のベクトルパターンを示したものである。
【図９】図９は条件３−１〜３−３のベクトルパターンを示したものである。
【図１０】図１０は条件１−１と条件２−１のベクトルパターンを比較して示したものである。
【図１１】図１１は本発明のプログラムが実現する機能のフローチャートである。
【図１２】図１２は図１１のフローチャート中の結線候補取得のサブルーチンのフローチャートである。
【図１３】図１３は図１１のフローチャート中の最適配線経路取得のサブルーチンのフローチャートである。
【図１４】図１４は端子配置例２とその最適配線経路を示したものである。
【図１５】図１５は第３結合点を採用することの利点を説明するものであり、端子配置例３とその最適配線経路を示したものである。
【図１６】図１６は端子配置例４とその最適配線経路を示している。
【発明を実施するための形態】
【００１３】
以下、図面を参照して、本発明の実施例を詳しく説明する。図１は本発明で使用する「重複ベクトル」という概念を説明する説明図である。信号源端子をドライバと呼び、これを記号Ｄで表すことにする。信号受信端子をレシーバと呼び、これを記号Ｒで表すことにする。互いに直交するＸ軸とＹ軸からなる２次元座標系において、ひとつのドライバＤと二つのレシーバＲ１，Ｒ２を考える。ドライバＤの座標は座標軸の原点（０，０）である。レシーバＲ１の座標は（３，６）であり、レシーバＲ２の座標は（９，３）である。ドライバＤからレシーバＲ１に向かうベクトルＤ→Ｒ１と、ドライバＤからレシーバＲ２に向かうベクトルＤ→Ｒ２を考える。二つのベクトルからなるベクトルペアについて、重複ベクトルは次のように定義される。「重複ベクトル」とは、ベクトルペアに含まれる二つのベクトルのＸ座標の「重複値」（二つのＸ座標の重なり部分）とＹ座標の「重複値」（二つのＹ座標の重なり部分）からなる座標を終点とし、ドライバを始点とするベクトルをいう。図１の例において、二つのベクトルのＸ座標は、それぞれ３と９であり、その重複値は３である。二つのベクトルのＹ座標は、それぞれ６と３であり、その重複値は３である。したがって、重複ベクトルの終点は（３，３）である。始点は座標軸の原点、すなわちドライバＤの位置である。重複ベクトルの終点は、後述する結合点（node）となりうるので、Ｎで表すことにする。なお、重複値を求めるときは座標の正負を考慮する。正の座標と負の座標の重複値はゼロである。
【００１４】
重複ベクトルＤ→Ｎの長さを「重複長さ」と定義する。ただし、本件明細書において、「ベクトルの長さ」とは、ベクトルの始点と終点とをＸ軸とＹ軸に沿って最短で結んだときの長さを意味する。図１の例で説明すると、重複ベクトルＤ→Ｎの長さは、Ｘ軸方向の長さ３とＹ軸方向の長さ３を合計した６である。本発明は、配線経路を作成するためのプログラムに関するものであり、配線方向はＸ軸とＹ軸に沿ったものに限定しているので、ベクトルの長さ（すなわち、配線の長さ）を考える上では、上述のような２方向に沿った長さを採用するのが好都合である。
【００１５】
ベクトルペアの「重複長さ」は、総配線長が小さい配線経路を作成するために重要な因子となる。ドライバＤとレシーバＲ１，Ｒ２とを結線する場合に、個別に結線するよりは、途中までを共通の配線とすれば、総配線長は短くなる。いくつかのベクトルペアを考えると、重複長さが大きいベクトルペアほど、配線の共通化の度合いが高くなる。
【００１６】
本発明のプログラムは、ベクトルペアの配線を途中まで共通化するための方法として３種類の選択肢を用意している。共通化した配線の終点を結合点と呼ぶことにすると、その結合点の決め方に３種類がある。すなわち、第１結合点から第３結合点までを利用して配線経路を検討している。
【００１７】
図２は第１結合点の説明図である。重複ベクトルＤ→Ｎの終点Ｎを結合点とするものであり、これを第１結合点と呼ぶ。ドライバＤから第１結合点Ｎまでは共通の配線とし、この第１結合点Ｎから二つのレシーバＲ１，Ｒ２までを別個に配線する。
【００１８】
図３は第２結合点の説明図である。ベクトルペアを構成する二つのベクトルのうち、短ベクトルの終点Ｒ１を結合点とし、これを第２結合点と呼ぶ。この第２結合点（レシーバＲ１と同じ）までが共通配線であり、そこからレシーバＲ２に向けてさらに配線をする。
【００１９】
図４は第３結合点の説明図である。ベクトルペアを構成する二つのベクトルのうち、長ベクトルの終点Ｒ２を結合点とし、これを第３結合点と呼ぶ。この第３結合点（レシーバＲ２と同じ）までが共通配線であり、そこからレシーバＲ１に向けてさらに配線をする。
【００２０】
次に、具体的な端子配置を用いて本発明の原理を詳しく説明する。図５は端子配置例１と、そのベクトルパターンの初期状態を示す。端子配置例１は、ひとつのドライバＤと三つのレシーバＲ１，Ｒ２，Ｒ３を含んでいる。ドライバＤの座標は座標軸の原点（０，０）である。レシーバＲ１の座標は（４，３）であり、レシーバＲ２の座標は（８，３）でり、レシーバＲ３の座標は（１２，０）である。ドライバから各レシーバに向けてベクトルを引いたものが、初期状態のベクトルパターンであり、ドライバＤからレシーバＲ１に向かうベクトルＤ→Ｒ１と、ドライバＤからレシーバＲ２に向かうベクトルＤ→Ｒ２と、ドライバＤからレシーバＲ３に向かうベクトルＤ→Ｒ３を作ることができる。この状態を初期状態とする。そして、各レシーバに向かうベクトルを途中まで共通化していくことで、総配線長が最小の配線経路を探すものである。図５（及び、その後の図面）において、配線経路が確定していないベクトル（これを「未処理ベクトル」という。）は破線で示すものとする。図５の初期状態のベクトルはすべて破線で示している。初期状態のベクトルパターンの右側に示したものは、ドライバからレシーバに向かうベクトルを木構造で表したものである。初期状態では、ひとつのドライバＤから三つのレシーバＲ１，Ｒ２，Ｒ３に向かって３本の接続線が並列に延びている。
【００２１】
初期状態のベクトルパターンにおいて最初に作業をすべきことは、重複長さが最大となるベクトルペアを選択することである。初期状態のベクトルパターンには３個のベクトルが存在し、その中の任意の二つのベクトルを用いてベクトルペアを作る。ベクトルペアの数は、３個の中から２個を取り出す組み合わせの数であり、３×２÷２＝３通りである。まず、ベクトルＤ→Ｒ１とベクトルＤ→Ｒ２の組み合わせからなるベクトルペアでは、重複ベクトルはＤ→Ｒ１に等しく、その重複長さは７（＝４＋３）である。ベクトルＤ→Ｒ２とベクトルＤ→Ｒ３の組み合わせからなるベクトルペアでは、重複ベクトルの終点は座標（８，０）であり、その重複長さは８である。ベクトルＤ→Ｒ１とベクトルＤ→Ｒ３の組み合わせからなるベクトルペアでは、重複ベクトルの終点は座標（４，０）であり、その重複長さは４である。したがって、最大の重複長さを有するベクトルペアは、ベクトルＤ→Ｒ２とベクトルＤ→Ｒ３の組み合わせである。これが「選択ベクトルペア」となる。
【００２２】
図６は、上述の選択ベクトルペアに対して、条件１〜３のベクトルパターンを示したものである。これらは、上述の選択ベクトルペアに対して三つの結合点を適用して、新たにベクトルパターン（初期状態よりも共通化の進んだベクトルパターン）を作成したものである。
【００２３】
条件１のベクトルパターンは第１結合点を適用したものである。すなわち、重複ベクトルの終点（８，０）を第１結合点Ｎ１とする。この第１結合点Ｎ１を始点としてレシーバＲ２に向かうベクトルと、レシーバＲ３に向かうベクトルとを作成し、これらのベクトルを結線確定ベクトルとする。結線確定ベクトルは、図６（及び、その後の図面）において実線で示している。ドライバＤから第１結合点Ｎ１に向かうベクトルを新しい未処理ベクトルとする。このような処理により、未処理ベクトルがひとつ減る。すなわち、三つの未処理ベクトルが、二つの未処理ベクトルＤ→Ｒ１，Ｄ→Ｎ１になる。条件１のベクトルパターンの図の右側に示した木構造では、ドライバＤからつながっているのはＲ１とＮ１だけであり、Ｎ１の下層にＲ２とＲ３がつながっている。
【００２４】
条件２のベクトルパターンは第２結合点を適用したものである。すなわち、選択ベクトルペアのうちの短ベクトルＤ→Ｒ２の終点（８，３）を第２結合点（Ｒ２と同じ）とする。この第２結合点Ｒ２を始点としてレシーバＲ３に向かうベクトルを作成し、このベクトルを結線確定ベクトルとする。ドライバＤから第２結合点Ｒ２に向かうベクトルはそのまま未処理ベクトルとして残す。この処理でも、未処理ベクトルがひとつ減って、三つの未処理ベクトルが二つの未処理ベクトルＤ→Ｒ１，Ｄ→Ｒ２になる。条件２のベクトルパターンの図の右側に示した木構造では、ドライバＤからつながっているのはＲ１とＲ２だけであり、Ｒ２の下層にＲ３がつながっている。
【００２５】
条件３のベクトルパターンは第３結合点を適用したものである。すなわち、選択ベクトルペアのうちの長ベクトルＤ→Ｒ３の終点（１２，０）を第３結合点（Ｒ３と同じ）とする。この第３結合点Ｒ３を始点としてレシーバＲ２に向かうベクトルを作成し、このベクトルを結線確定ベクトルとする。ドライバＤから第３結合点Ｒ３に向かうベクトルはそのまま未処理ベクトルとして残す。この処理でも、未処理ベクトルがひとつ減って、三つの未処理ベクトルが二つの未処理ベクトルＤ→Ｒ１，Ｄ→Ｒ３となる。条件３のベクトルパターンの図の右側に示した木構造では、ドライバＤからつながっているのはＲ１とＲ３だけであり、Ｒ３の下層にＲ２がつながっている。
【００２６】
条件１〜３のベクトルパターンを見ると、いずれも、未処理ベクトルが二つ残っているので、未処理ベクトルを減らすための、さらなる処理が必要となる。
【００２７】
図７は条件１−１〜１−３のベクトルパターンを示したものであり、これらは、図６の条件１のベクトルパターンを出発点として、さらに三つの結合点を適用して新たに三つのベクトルパターンを作成したものである。条件１のベクトルパターンは未処理ベクトルが二つだけ（Ｄ→Ｒ１とＤ→Ｎ１）なので、ベクトルペアは１種類だけであり、それが選択ベクトルペアとなる。その重複ベクトルの終点は（４，０）である。
【００２８】
図７の条件１−１のベクトルパターンは条件１のベクトルパターン（図６の条件１を参照）に第１結合点を適用したものである。重複ベクトルの終点（４，０）を第１結合点Ｎ２とする。この第１結合点Ｎ２を始点としてレシーバＲ１に向かうベクトルと、結合点Ｎ１に向かうベクトルとを作成し、これらのベクトルを結線確定ベクトルとする。ドライバＤから第１結合点Ｎ２に向かうベクトルを新しい未処理ベクトルとする。この処理により、未処理ベクトルがひとつ減って、二つの未処理ベクトルがひとつの未処理ベクトルＤ→Ｎ２になる。未処理ベクトルがひとつになったときは、その時点でのベクトルパターンを結線候補として取得する。すなわち、条件１−１のベクトルパターンに沿って配線をすることで結線候補としての配線経路が完成する。なお、ベクトルに沿って配線するときはＸ軸またはＹ軸に平行な配線を作るものとする。
【００２９】
図７の条件１−２のベクトルパターンは条件１のベクトルパターン（図６の条件１を参照）に第２結合点を適用したものである。すなわち、選択ベクトルペアのうちの短ベクトルＤ→Ｒ１の終点（４，３）を第２結合点（Ｒ１と同じ）とする。この第２結合点Ｒ１を始点として結合点Ｎ１に向かうベクトルを作成し、このベクトルを結線確定ベクトルとする。ドライバＤから第２結合点Ｒ１に向かうベクトルはそのまま未処理ベクトルとして残す。この処理により、未処理ベクトルがひとつ減って、二つの未処理ベクトルがひとつの未処理ベクトルＤ→Ｒ１となる。未処理ベクトルがひとつになったので、このベクトルパターンを結線候補として取得する。
【００３０】
図７の条件１−３のベクトルパターンは条件１のベクトルパターン（図６の条件１を参照）に第３結合点を適用したものである。すなわち、選択ベクトルペアのうちの長ベクトルＤ→Ｎ１の終点（８，０）を第３結合点とする。この第３結合点Ｎ１を始点としてレシーバＲ１に向かうベクトルを作成し、このベクトルを結線確定ベクトルとする。ドライバＤから第３結合点Ｎ１に向かうベクトルはそのまま未処理ベクトルとして残す。この処理により、未処理ベクトルがひとつ減って、二つの未処理ベクトルがひとつの未処理ベクトルＤ→Ｎ１となる。未処理ベクトルがひとつになったので、このベクトルパターンを結線候補として取得する。
【００３１】
図８は条件２−１〜２−３のベクトルパターンを示したものであり、これらは、図６の条件２のベクトルパターンを出発点として、さらに三つの結合点を適用して新たにベクトルパターンを作成したものである。条件２のベクトルパターンは未処理ベクトルが二つだけなので、ベクトルペアは１種類だけであり、それが選択ベクトルペアとなる。その重複ベクトルの終点は（４，３）であり、レシーバＲ１と同じ位置である。
【００３２】
図８の条件２−１のベクトルパターンは条件２のベクトルパターン（図６の条件２を参照）に第１結合点を適用したものである。重複ベクトルの終点（４，３）すなわちレシーバＲ１を第１結合点とする。この第１結合点Ｒ１を始点として、短ベクトルの終点すなわち同じ地点Ｒ１に向かうベクトル（すなわち、ゼロベクトル）と、レシーバＲ２に向かうベクトルとを作成し、これらのベクトルを結線確定ベクトルとする。ドライバから第１結合点Ｒ１に向かうベクトルを新しい未処理ベクトルとする（これは短ベクトルと同じもの）。この処理により、未処理ベクトルがひとつ減って、二つの未処理ベクトルがひとつの未処理ベクトルＤ→Ｒ１となる。未処理ベクトルがひとつになったので、このベクトルパターンを結線候補として取得する。
【００３３】
図８の条件２−２のベクトルパターンは条件２のベクトルパターン（図６の条件２を参照）に第２結合点を適用したものである。すなわち、選択ベクトルペアのうちの短ベクトルＤ→Ｒ１の終点（４，３）を第２結合点（Ｒ１と同じ）とする。この第２結合点は条件２−１の第１結合点と同じである。その理由は、条件２の選択ベクトルペアは、重複ベクトルと短ベクトルが同じものであるからである。ゆえに、条件２−２のベクトルパターンは条件２−１のベクトルパターンと同じである。これを結線候補として取得する。条件２−１と同じものであるから、結線候補として取得するのを省略する処理としてもよい。
【００３４】
図８の条件２−３のベクトルパターンは条件２のベクトルパターン（図６の条件２を参照）に第３結合点を適用したものである。すなわち、選択ベクトルペアのうちの長ベクトルＤ→Ｒ２の終点（８，３）を第３結合点とする。この第３結合点Ｒ２を始点としてレシーバＲ１に向かうベクトルを作成し、このベクトルを結線確定ベクトルとする。ドライバＤから第３結合点Ｒ２に向かうベクトルはそのまま未処理ベクトルとして残す。この処理により、未処理ベクトルがひとつ減って、二つの未処理ベクトルがひとつの未処理ベクトルＤ→Ｒ２になる。未処理ベクトルがひとつになったので、このベクトルパターンを結線候補として取得する。
【００３５】
図９は条件３−１〜３−３のベクトルパターンを示したものであり、これらは、図６の条件３のベクトルパターンを出発点として、さらに三つの結合点を適用して新たにベクトルパターンを作成したものである。条件３のベクトルパターンは未処理ベクトルが二つだけなので、ベクトルペアは１種類だけであり、それが選択ベクトルペアとなる。その重複ベクトルの終点は（４，０）である。
【００３６】
図９の条件３−１のベクトルパターンは条件３のベクトルパターン（図６の条件３を参照）に第１結合点を適用したものである。重複ベクトルの終点（４，０）を第１結合点Ｎ１とする。この第１結合点Ｎ１を始点としてレシーバＲ１に向かうベクトルと、レシーバＲ３に向かうベクトルとを作成し、これらのベクトルを結線確定ベクトルとする。ドライバＤから第１結合点Ｎ１に向かうベクトルを新しい未処理ベクトルとする。この処理により、未処理ベクトルがひとつ減って、二つの未処理ベクトルがひとつの未処理ベクトルＤ→Ｎ１となる。未処理ベクトルがひとつになったので、このベクトルパターンを結線候補として取得する。
【００３７】
図９の条件３−２のベクトルパターンは条件３のベクトルパターン（図６の条件３を参照）に第２結合点を適用したものである。すなわち、選択ベクトルペアのうちの短ベクトルＤ→Ｒ１の終点（４，３）を第２結合点（Ｒ１と同じ）とする。この第２結合点Ｒ１を始点としてレシーバＲ３に向かうベクトルを作成し、このベクトルを結線確定ベクトルとする。ドライバから第２結合点Ｒ１に向かうベクトルはそのまま未処理ベクトルとして残す。この処理により、未処理ベクトルがひとつ減って、二つの未処理ベクトルがひとつの未処理ベクトルＤ→Ｒ１となる。未処理ベクトルがひとつになったので、このベクトルパターンを結線候補として取得する。
【００３８】
図９の条件３−３のベクトルパターンは条件３のベクトルパターン（図６の条件３を参照）に第３結合点を適用したものである。すなわち、選択ベクトルペアのうちの長ベクトルＤ→Ｒ３の終点（１２，０）を第３結合点とする。この第３結合点Ｒ３を始点としてレシーバＲ１に向かうベクトルを作成し、このベクトルを結線確定ベクトルとする。ドライバからレシーバＲ３に向かうベクトルはそのまま未処理ベクトルとして残す。この処理により、未処理ベクトルがひとつ減って、二つの未処理ベクトルがひとつの未処理ベクトルＤ→Ｒ３となる。未処理ベクトルがひとつになったので、このベクトルパターンを結線候補として取得する。
【００３９】
以上の処理により、未処理のベクトルパターン（未処理ベクトルが二つ以上残っているベクトルパターン）が存在しなくなり、結線候補を取得する作業が完了する。
【００４０】
次に、取得した複数の結線候補、この例では、条件１−１〜３−３の９種類のベクトルパターンについて、総配線長を求める。図７の条件１−１の結線候補について説明すると、総配線長ＴＬ（total lengthの意味）は、ベクトルの長さの合計であり、１８である。この値を、条件１−１のベクトルパターンの図の右上にＴＬ＝１８と記載してある。ドライバとレシーバをつなぐ配線の長さ（これを「ＤＲ間配線長」という。）についても説明する。レシーバは３個あるので、その配線長さも３種類あり、ドライバＤとレシーバＲ１のＤＲ間配線長は７であり、ドライバＤとレシーバＲ２のＤＲ間配線長は１１であり、ドライバＤとレシーバＲ３のＤＲ間配線長は１２である。三つのＤＲ間配線長の中で最大のものを最大ＤＲ間配線長と定義し、これをＰＬ（path lengthの意味）で表すことにする。ＰＬは１２である。これも、ベクトルパターンの図の右上にＰＬ＝１２と記載してある。
【００４１】
図７の条件１−２についても説明すると、総配線長ＴＬは２１となる。この場合、ベクトルＤ→Ｒ１の配線長さについては、Ｘ軸とＹ軸に沿った長さを求めるものとし、７となる。ベクトルＲ１→Ｎ１についても同様に７となる。また、最大ＤＲ間配線長ＰＬは１８である。
【００４２】
図７の条件１−３、図８の条件２−１〜２−３、及び、図９の条件３−１〜３−３のベクトルパターンについても、総配線長ＴＬとＤＲ間配線長ＰＬの値を各ベクトルパターンの右上に記載してある。
【００４３】
上述の９個の結線候補について、それらの総配線長を比較すると、最小の総配線長が１８であることが分かる。そして、最小総配線長１８を有する結線候補は二つあり、それは条件１−１と条件２−１である。その配線経路を図１０に並べて示す。このように、最小総配線数の配線経路が複数得られた場合は、さらに、最大ＤＲ間配線長を互いに比較する。条件１−１の最大ＤＲ間配線長ＰＬは１２であり、条件２−１の最大ＤＲ間配線長ＰＬは１８である。前者の方が小さい。したがって、条件１−１の配線経路を最終的な最適配線経路として取得する。
【００４４】
以上説明してきたプログラムの機能をフローチャートで示すと、図１１〜図１３のようになる。このフローチャートを用いて、本プログラムの機能をおさらいする。図１１において、まず、ドライバ及びレシーバの端子座標を取得する（ステップＳ１１）。この機能は、例えば、図５の端子配置例１をオペレータがコンピュータに入力して、コンピュータがこれを取得することを意味する。
【００４５】
次に、コンピュータは、ドライバから各レシーバに向かうベクトルパターンを作成する（ステップＳ１２）。この機能は、図５の初期状態のベクトルパターンを作成することに相当する。このベクトルパターンに含まれるベクトルはすべて未処理ベクトルである。
【００４６】
次に、コンピュータは、このベクトルパターンに含まれる複数の未処理ベクトルに関して、任意の二つの未処理ベクトルからなる可能な全てのベクトルペアについて、重複長さを算出する（ステップＳ１３）。重複長さとは、そのベクトルペアに属する二つのベクトルのＸ座標の重複値とＹ座標の重複値の和である。その重複長さを可能な全てのベクトルペアについて比較し、重複長さが最大となるベクトルペアを選択する（ステップＳ１４）。その選択ベクトルペアについて重複ベクトルを決定する。重複ベクトルとは、前記Ｘ座標の重複値と前記Ｙ座標の重複値からなる座標を終点とし、ドライバを始点とするベクトルである。図５の初期状態のベクトルパターンでは、選択ベクトルペアはＤ→Ｒ２とＤ→Ｒ３の組み合わせであり、重複ベクトルの終点は（８，０）であり、重複長さは８である。
【００４７】
この選択ベクトルペアが決まると、コンピュータは、結線候補取得のサブルーチンを実行する（ステップＳ１５）。このサブルーチンのフローチャートは図１２に示す。
【００４８】
図１２において、特定の選択ベクトルペアについて、重複ベクトルの終点を第１結合点として、新しいベクトルパターンを作る（ステップＳ２１）。これが図６の条件１に相当する。この新しいベクトルパターンでは、第１結合点を始点とし、選択ベクトルペアに係る二つのレシーバを終点とする二つのベクトルを結線確定ベクトルとする。そして、それらの結線確定ベクトルに係る二つの未処理ベクトルを削除して、重複ベクトルを新たに未処理ベクトルと定める。図６の条件１で説明すると、それまでの二つの未処理ベクトルＤ→Ｒ２とＤ→Ｒ３を削除して、その代わりに、重複ベクトルを新しい未処理ベクトルとする。これにより、未処理ベクトルがひとつ減り、ベクトルパターンの共通化が進む。この新しいベクトルパターンについて、未処理ベクトルの数を判定して（ステップＳ２２）、未処理ベクトルがひとつのときは、このベクトルパターンを結線候補として取得して、第２結合点による処理に移る（ステップＳ２３）。未処理ベクトルが複数のときは、結線候補を取得せずに、第２結合点による処理に移る。図６の条件１では、未処理ベクトルが二つ残っているので、結線候補は取得せずに、第２結合点による処理に移っている。
【００４９】
次に、第２結合点による処理を実施する（ステップＳ２４）。これが図６の条件２に相当する。選択ベクトルペアに属する二つのベクトルのうちの短ベクトルの終点を第２結合点とし、この第２結合点を始点とし選択ベクトルペアに属する二つのベクトルのうちの長ベクトルの終点を終点とするベクトルを結線確定ベクトルとする。前記長ベクトルに係る未処理ベクトルを削除して、前記短ベクトルに係る未処理ベクトルをそのまま残して、新しいベクトルパターンを作る。図６の条件２で説明すると、ベクトルＲ２→Ｒ３を結線確定ベクトルとし、長ベクトルに係る未処理ベクトルＤ→Ｒ３を削除して、短ベクトルに係る未処理ベクトルＤ→Ｒ２をそのまま残す。この第２結合点による処理でも、第１結合点による処理と同様に、新しいベクトルパターンについて、未処理ベクトルの数を判定する（ステップＳ２５）。未処理ベクトルがひとつのときは、このベクトルパターンを結線候補として取得してから、第３結合点による処理に移る（ステップＳ２６）。未処理ベクトルが複数のときは、結線候補を取得せずに、第３結合点による処理に移る。図６の条件２でも、未処理ベクトルが二つ残っているので、結線候補は取得せずに、第３結合点による処理に移っている。
【００５０】
次に、第３結合点による処理を実施する（ステップＳ２７）。これが図６の条件３に相当する。選択ベクトルペアに属する二つのベクトルのうちの長ベクトルの終点を第３結合点とし、この第３結合点を始点とし選択ベクトルペアに属する二つのベクトルのうちの短ベクトルの終点を終点とするベクトルを結線確定ベクトルとする。前記短ベクトルに係る未処理ベクトルを削除して、前記長ベクトルに係る未処理ベクトルをそのまま残して、新しいベクトルパターンを作る。図６の条件３で説明すると、ベクトルＲ３→Ｒ２を結線確定ベクトルとし、短ベクトルに係る未処理ベクトルＤ→Ｒ２を削除して、長ベクトルに係る未処理ベクトルＤ→Ｒ３をそのまま残す。この第３結合点による処理でも、第１結合点及び第２結合点による処理と同様に、新しいベクトルパターンについて、未処理ベクトルの数を判定する（ステップＳ２８）。未処理ベクトルがひとつのときは、このベクトルパターンを結線候補として取得してから（ステップＳ２９）、このサブルーチンを抜けて、図１１のフローチャートに戻る。未処理ベクトルが複数のときは、結線候補を取得せずに、このサブルーチンを抜けて、図１１のフローチャートに戻る。図６の条件３でも、未処理ベクトルが二つ残っているので、結線候補は取得せずに、図１１のフローチャートに戻っている。
【００５１】
図１２の結線候補取得のサブルーチンを実行すると、ひとつのベクトルパターンから新しい三つのベクトルパターンが生まれる。それらのベクトルパターンに含まれる未処理ベクトルがひとつのときは、そのベクトルパターンを結線候補として取得する。未処理ベクトルが複数残っているときは、そのベクトルパターンについて、図１１のフローチャートに戻って選択ベクトルペアを決定した上で、結線候補取得のサブルーチンを繰り返すことになる。レシーバが３個のときは、未処理ベクトルがひとつに減るまでに、結線候補取得ルーチンを２回繰り返すことになる。したがって、取得する結線候補の数は、原則として、３×３＝９個になる。これが図７〜９の条件１−１〜３−３の９個の結線候補である。
【００５２】
結線候補取得のサブルーチンを抜けると、図１１のフローチャートに戻り、未処理パターンの判定を実行する（ステップＳ１６）。ここでは、結線候補の取得に至らないベクトルパターン（すなわち、未処理ベクトルを複数個含むベクトルパターンであり、これを未処理パターンと呼ぶ。）が残っているか否かを判定する。残っている場合は、任意の未処理パターンを選択して（ステップＳ１７）、各ベクトルペアの重複長さを算出するステップに戻る。未処理パターンが残っていなければ、結線候補の取得がすべて完了していることになるので、最適配線経路取得のサブルーチンに移る（ステップＳ１８）。
【００５３】
図１３は最適配線経路取得のサブルーチンのフローチャートである。まず、それまでに取得した複数の結線候補のそれぞれについて総配線長を求める。その中から、最小の総配線長を有する結線候補を探す（ステップＳ３１）。この機能は、図７〜９に示す９個の結線候補の中から、総配線長ＴＬが一番小さいものを探す作業に相当する。その結線候補がひとつである場合は（ステップＳ３２）、その結線候補を最適配線経路として取得する。複数である場合は、それらの結線候補について、さらに最大ＤＲ間配線長を比較する（ステップＳ３３）。そして、最大ＤＲ間配線長が一番小さい結線候補を最適配線経路として取得する（ステップＳ３４）。上述の例では、図１０に示すように、総配線長ＴＬが一番小さいものとして条件１−１と２−２が見つかり、そのうちで、最大ＤＲ間配線長が小さい方の条件２−１を最適配線経路としている。以上で、本プログラムの動作が終了する。
【００５４】
ここで、本プログラムで得られる最適配線経路と、従来技術で得られる最適配線経路とを比較する。図１０に示す条件１−１の配線経路（本プログラムで最適配線経路として得られたもの）は、上述の特許文献３に記載されている重複コスト最大化法でも得られるものである。条件１−１は、２回の結合点処理でいずれも第１結合点を採用したものであり、この処理は、基本的な考え方として、ドライバからレシーバまでの配線距離が常に最短になるように配線経路を共通化していくことに相当する。この考え方は上述の重複コスト最適化法と実質的に同じである。したがって、条件１−１の配線経路が重複コスト最適化法で得られる配線経路と同じになることは当然である。
【００５５】
図１０に示す条件２−１の配線経路（本プログラムでは最適配線経路として採用されなかったもの）は、上述の特許文献１に記載されているシュタイナー木の近似解で得られるものと同じである。シュタイナー木の近似解は、総配線長が最小の配線経路を得るための手法なので、条件２−１のように最小の総配線長のものが得られる。しかし、シュタイナー木の近似解は、ドライバからレシーバまでの配線の長さをできるだけ短くする、という考え方はしていないので、条件１−１の配線経路が得られない。
【００５６】
図５の端子配置例１だけを考えると、本プログラムで得られる配線経路は、重複コスト最大化法で得られる配線経路と同等である。コンピュータによる処理量を比較すると、本プログラムでは、処理の途中段階で複数の結線候補（レシーバの数が増えると、取得する結線候補の数はかなり多くなる）を取得するのに対して、重複コスト最大化法では、基本的には、結線候補は常に１種類だけである。ゆえに、コンピュータによる処理量を比較すると、重複コスト最大化法の方が少なくなり、有利である。しかしながら、後述するように、別の端子配置例を考えると、重複コスト最大化法で得られる配線経路は、本プログラムで得られる配線経路よりも総配線長が長くなってしまう。なぜならば、重複コスト最大化法では、総配線長を最小にするという考え方を持たないからである。
【００５７】
図１４は端子配置例２と、その最適配線経路を示したものである。端子配置例２は、図５の端子配置例に対してさらにドライバ４を追加したものである。この端子配置例２では、ドライバから四つのレシーバに向かう未処理ベクトルまで記載した状態で示している。この端子配置例２に対して、重複コスト最大化法を適用すると、図１４の中段のような配線経路になる。総配線長ＴＬは２１で、最大ＤＲ間配線長は１２である。一方、シュタイナー木の近似解を適用すると、図１４の下段のような配線経路になる。総配線長ＴＬは１８で、最大ＤＲ間配線長は１８である。本発明者が意図している最適配線経路（すなわち、本プログラムが目指すもの）は、総配線長が最小であり、かつ、そのような配線経路が複数存在するのであれば、その中で最大ＤＲ間配線長が最小であるもの、である。したがって、図１４の下段の配線経路の方が、総配線長が小さいので、好ましいものである。そして、端子配置例２に対して本プログラムを適用すると、最適配線経路としては図１４の下段の配線経路が得られる。すなわち、端子配置例２の場合には、重複コスト最大化法では最適配線経路が得られず、シュタイナー木の近似解で得られるもの（そして、本プログラムで得られるもの）が最適配線経路となる。
【００５８】
以上説明したように、「総配線長が最小であり、かつ、そのような配線経路が複数存在するのであれば、その中で最大ＤＲ間配線長が最小であるもの」を探すという目的について、それをどのような端子配置であっても達成するためには、重複コスト最大化法では不十分であり（端子配置例２では最適解が得られない）、また、シュタイナー木の近似解でも不十分である（端子配置例１では最適解が得られない）。本発明のプログラムを用いると、発明者が認識する限りにおいて、どのような端子配置であっても、上述の目的を達成することができる。
【００５９】
ところで、多くの端子配置例において、第１結合点（選択ベクトルペアの重複ベクトルの終点を結合点とするもの）と第２結合点（選択ベクトルペアの短ベクトルの終点を結合点とするもの）だけを採用することで、最適経路配置を得ることができる。しかし、発明者がいろいろと検討してみると、この二つの結合点だけでは、必ずしも最小の総配線長が得られないことが判明した。そこで、本発明では第３結合点（選択ベクトルペアの長ベクトルの終点を結合点とするもの）までを適用して結線候補を取得している。
【００６０】
図１５は第３結合点を採用することの利点を説明するものであり、端子配置例３と、その最適配線経路を示している。端子配置例３は、ひとつのドライバＤと四つのレシーバＲ１〜Ｒ４を含んでいる。第３結合点を考慮しない場合（第１結合点と第２結合点を利用して結線候補を取得した場合）は、最終的に得られる最適配線経路は同図の下段の左側の配線経路となる。総配線長ＴＬは１３で、最大ＤＲ間配線長は９である。一方、第３結合点まで考慮する場合は、最終的に得られる最適配線経路は同図の下段の右側の配線経路となる。総配線長ＴＬは１２で、最大ＤＲ間配線長は１０である。発明者が意図することは、「総配線長が最小であり、かつ、そのような配線経路が複数存在するのであれば、その中で最大ＤＲ間配線長が最小であるもの」を探すことであるから、第３結合点を考慮した場合の最適配線経路の方が発明者の意図に合致するものである。
【００６１】
図１６は端子配置例４とその最適配線経路を示している。この端子配置例４は、現実の配線基板における端子配置を想定したものである。ひとつのドライバＤと６個のレシーバＲ１〜Ｒ６を含んでいる。この端子配置例４に対して本プログラムを適用すると、同図の下段の最適配線経路が得られる。
【符号の説明】
【００６２】
Ｄ  ドライバ（信号源端子）
Ｒ１〜Ｒ６  レシーバ（信号受信端子）
Ｎ１〜Ｎ２  結合点
【図１】
0005590725.tif 000002
【図２】
0005590725.tif 000003
【図３】
0005590725.tif 000004
【図４】
0005590725.tif 000005
【図５】
0005590725.tif 000006
【図６】
0005590725.tif 000007
【図７】
0005590725.tif 000008
【図８】
0005590725.tif 000009
【図９】
0005590725.tif 000010
【図１０】
0005590725.tif 000011
【図１１】
0005590725.tif 000012
【図１２】
0005590725.tif 000013
【図１３】
0005590725.tif 000014
【図１４】
0005590725.tif 000015
【図１５】
0005590725.tif 000016
【図１６】
0005590725.tif 000017