(57)【要約】【課題】  基板上の配線のルートを、基板上において障害物と交差しないよう短時間で自動的に決定できる自動配線決定装置及び方法並びにこれをコンピュータに実行させるためのコンピュータプログラムを実現する。【解決手段】  自動配線決定装置１は、配線の始点と終点とを結ぶ直線上に存在する障害物に接する始点側ルート候補及び終点側ルート候補を設定する手段１１と、この直線上に障害物が複数存在する場合、２つの障害物間毎に、当該２つの障害物のみに接し当該２つの障害物以外の障害物とは交差しない中間ルート候補を設定する手段１２と、始点側ルート候補のいずれか１つ及び終点側ルート候補のいずれか１つを含み、障害物が複数存在する場合には、２つの障害物間毎に選択される中間ルート候補のいずれかを更に含み得る仮ルートが設定される手段１３と、これら仮ルートのうち始点と終点との間の距離が最短のものを配線の最適ルートとする手段１４とを備える。【選択図】      図１
2006331017.tif 000002
【特許請求の範囲】
【請求項１】
基板上の配線のルートを、該基板上における少なくとも１つの障害物と交差しないよう、演算処理により自動的に決定する自動配線決定装置であって、
配線の始点および終点となるべき２点間を結ぶ直線上に存在する障害物に接する、前記始点からの直線ルートを始点側ルート候補として設定するとともに、前記障害物に接する前記終点からの直線ルートを終点側ルート候補として設定する第１のルート候補設定手段と、
配線の始点および終点となるべき２点間を結ぶ直線上に障害物が複数存在する場合において、２つの障害物間ごとに、当該２つの障害物のみに接しかつ当該２つの障害物以外の障害物とは交差しない直線ルートを中間ルート候補として設定する第２のルート候補設定手段と、
前記始点側ルート候補のいずれか１つと、前記終点側ルート候補のいずれか１つと、を少なくとも含み、前記障害物が複数存在する場合には、前記２つの障害物間ごとに選択される、前記中間ルート候補のいずれか１つ、をさらに含み得る仮ルートを設定する仮ルート設定手段と、
前記仮ルートのうち、前記始点から前記終点までの間の距離が最短となる仮ルートを、配線の最適なルートとして確定する最適ルート確定手段と、
を備えることを特徴とする自動配線決定装置。
【請求項２】
前記最適ルート確定手段により確定した前記最適なルートが、該最適なルートが交差を回避した前記障害物以外の障害物と交差することになるとき、該最適なルートが交差を回避した前記障害物近傍の該最適なルート上の点を、配線の新たなる始点に設定して、前記第１のルート候補設定手段、前記第２のルート候補設定手段、前記仮ルート設定手段および前記最適ルート確定手段による前記の処理をさらに実行する請求項１に記載の自動配線決定装置。
【請求項３】
前記配線の新たなる始点として設定される、前記最適なルートが交差を回避した前記障害物近傍の該最適なルート上の点は、当該最適なルートと当該障害物との接点である請求項２に記載の自動配線決定装置。
【請求項４】
配線の始点および終点となるべき２点間を結ぶ直線上に障害物が存在するか否かを判定する判定手段をさらに備える請求項１または２に記載の自動配線決定装置。
【請求項５】
前記最適なルートと前記障害物との間のクリアランスを確保するよう、該最適なルートを補正するクリアランス確保手段をさらに備える請求項１または２に記載の自動配線決定装置。
【請求項６】
前記第１のルート候補設定手段は、多角形状を有する前記障害物の各頂点上を通過する前記始点からの直線ルートのうち、頂点上以外の位置では当該障害物と交差することのない直線ルートを前記始点側ルート候補として設定するとともに、前記障害物の各頂点上を通過する前記終点からの直線ルートのうち、頂点上以外の位置では当該障害物と交差することのない直線ルートを前記終点側ルート候補として設定し、
前記第２のルート候補設定手段は、２つの前記障害物の各頂点上を通過する直線ルートのうち、頂点上以外の位置では当該２つの障害物および当該２つの障害物以外の障害物とは交差することのない直線ルートを前記中間ルート候補として設定する請求項１に記載の自動配線決定装置。
【請求項７】
前記第２のルート候補設定手段は、
前記２つの前記障害物のそれぞれについて、一方の前記障害物の各頂点上を通過する他方の前記障害物の各頂点からの直線ルートのうち、当該一方の障害物の頂点上以外の位置では当該一方の障害物と交差することのない直線ルートを仮中間ルート候補として設定する仮中間ルート候補設定手段と、
前記仮中間ルート候補のうち、前記２つの障害物の双方から引かれた仮中間ルート候補を前記中間ルート候補として設定する中間ルート候補設定手段と、
を有する請求項６に記載の自動配線決定装置。
【請求項８】
前記仮中間ルート候補設定手段は、前記障害物の頂点が凹頂点である頂点からの直線ルートを前記仮中間ルート候補には含めない請求項７に記載の自動配線決定装置。
【請求項９】
前記第１のルート候補設定手段は、前記障害物の各頂点上を通過する前記始点からの各直線ルートと、前記始点と前記終点とを結ぶ直線である交差チェック基準線と、のなす角が最大角度となる直線ルートを前記始点側ルート候補として設定するとともに、前記障害物の各頂点上を通過する前記終点からの各直線ルートと、前記交差チェック基準線と、のなす角が最大角度となる直線ルートを前記終点側ルート候補として設定する請求項６に記載の自動配線決定装置。
【請求項１０】
基板上の配線のルートを、該基板上における少なくとも１つの障害物と交差しないよう、演算処理により自動的に決定する自動配線決定装置であって、
配線の始点および終点となるべき２点間を結ぶ直線上に存在する障害物を所定のクリアランス分だけ太らせた仮想障害物を設定する仮想障害物設定手段と、
前記仮想障害物に接する、前記始点からの直線ルートを始点側ルート候補として設定するとともに、前記仮想障害物に接する前記終点からの直線ルートを終点側ルート候補として設定する第１のルート候補設定手段と、
配線の始点および終点となるべき２点間を結ぶ直線上に障害物が複数存在する場合において、２つの仮想障害物間ごとに、当該２つの仮想障害物のみに接しかつ当該２つの仮想障害物以外の仮想障害物とは交差しない直線ルートを中間ルート候補として設定する第２のルート候補設定手段と、
前記始点側ルート候補のいずれか１つと、前記終点側ルート候補のいずれか１つと、を少なくとも含み、前記障害物が複数存在する場合には、前記２つの仮想障害物間ごとに選択される、前記中間ルート候補のいずれか１つ、をさらに含み得る仮ルートを設定する仮ルート設定手段と、
前記仮ルートのうち、前記始点から前記終点までの間の距離が最短となる仮ルートを、配線の最適なルートとして確定する最適ルート確定手段と、
を備えることを特徴とする自動配線決定装置。
【請求項１１】
前記最適ルート確定手段により確定した前記最適なルートが、該最適なルートが交差を回避した前記仮想障害物以外の仮想障害物と交差することになるとき、該最適なルートが交差を回避した前記仮想障害物近傍の該最適なルート上の点を、配線の新たなる始点に設定して、前記第１のルート候補設定手段、前記第２のルート候補設定手段、前記仮ルート設定手段および前記最適ルート確定手段による前記の処理をさらに実行する請求項１０に記載の自動配線決定装置。
【請求項１２】
前記配線の新たなる始点として設定される、前記最適なルートが交差を回避した前記仮想障害物近傍の該最適なルート上の点は、当該最適なルートと当該仮想障害物との接点である請求項１１に記載の自動配線決定装置。
【請求項１３】
配線の始点および終点となるべき２点間を結ぶ直線上に障害物が存在するか否かを判定する判定手段をさらに備える請求項１０に記載の自動配線決定装置。
【請求項１４】
前記第１のルート候補設定手段は、多角形状を有する前記仮想障害物の各頂点上を通過する前記始点からの直線ルートのうち、頂点上以外の位置では当該仮想障害物と交差することのない直線ルートを前記始点側ルート候補として設定するとともに、前記仮想障害物の各頂点上を通過する前記終点からの直線ルートのうち、頂点上以外の位置では当該仮想障害物と交差することのない直線ルートを前記終点側ルート候補として設定し、
前記第２のルート候補設定手段は、２つの前記仮想障害物の各頂点上を通過する直線ルートのうち、頂点上以外の位置では当該２つの仮想障害物および当該２つの仮想障害物以外の仮想障害物とは交差することのない直線ルートを前記中間ルート候補として設定する請求項１０に記載の自動配線決定装置。
【請求項１５】
前記第２のルート候補設定手段は、
前記２つの前記仮想障害物のそれぞれについて、一方の前記仮想障害物の各頂点上を通過する他方の前記仮想障害物の頂点からの直線ルートのうち、当該一方の仮想障害物の頂点上以外の位置では当該一方の仮想障害物と交差することのない直線ルートを仮中間ルート候補として設定する仮中間ルート候補設定手段と、
前記仮中間ルート候補のうち、前記２つの仮想障害物の双方から引かれた仮中間ルート候補を前記中間ルート候補として設定する中間ルート候補設定手段と、
を有する請求項１４に記載の自動配線決定装置。
【請求項１６】
前記仮中間ルート候補設定手段は、前記仮想障害物の頂点が凹頂点である頂点からの直線ルートを前記仮中間ルート候補には含めない請求項１５に記載の自動配線決定装置。
【請求項１７】
前記第１のルート候補設定手段は、前記仮想障害物の各頂点上を通過する前記始点からの各直線ルートと、前記始点と前記終点とを結ぶ直線である交差チェック基準線と、のなす角が最大角度となる直線ルートを前記始点側ルート候補として設定するとともに、前記仮想障害物の各頂点上を通過する前記終点からの各直線ルートと、前記交差チェック基準線と、のなす角が最大角度となる直線ルートを、前記終点側ルート候補として設定する請求項１４に記載の自動配線決定装置。
【請求項１８】
基板上の配線のルートを、該基板上における少なくとも１つの障害物と交差しないよう、演算処理により自動的に決定する自動配線決定処理をコンピュータに実行させるためのコンピュータプログラムであって、
配線の始点および終点となるべき２点間を結ぶ直線上に存在する障害物に接する、前記始点からの直線ルートを始点側ルート候補として設定するとともに、前記障害物に接する前記終点からの直線ルートを終点側ルート候補として設定する第１のルート候補設定ステップと、
前記始点側ルート候補のいずれか１つと、前記終点側ルート候補のいずれか１つと、を少なくとも含み、前記障害物が複数存在する場合には、前記２つの障害物間ごとに選択される、前記中間ルート候補のいずれか１つ、をさらに含み得る仮ルートを設定する仮ルート設定ステップと、
前記仮ルートのうち、前記始点から前記終点までの間の距離が最短となる仮ルートを、配線の最適なルートとして確定する最適ルート確定ステップと、
を備えることを特徴とする自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項１９】
前記最適ルート確定ステップにより確定した前記最適なルートが、該最適なルートが交差を回避した前記障害物以外の障害物と交差することになるとき、該最適なルートが交差を回避した前記障害物近傍の該最適なルート上の点を、配線の新たなる始点に設定して、前記第１のルート候補設定ステップ、前記第２のルート候補設定ステップ、前記仮ルート設定ステップおよび前記最適ルート確定ステップによる前記の処理をさらに実行する請求項１８に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項２０】
前記配線の新たなる始点として設定される、前記最適なルートが交差を回避した前記障害物近傍の該最適なルート上の点は、当該最適なルートと当該障害物との接点である請求項１９に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項２１】
配線の始点および終点となるべき２点間を結ぶ直線上に障害物が存在するか否かを判定する判定ステップをさらに備える請求項１８に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項２２】
前記最適なルートと前記障害物との間のクリアランスを確保するよう、該最適なルートを補正するクリアランス確保ステップをさらに備える請求項１８に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項２３】
前記第１のルート候補設定ステップは、多角形状を有する前記障害物の各頂点上を通過する前記始点からの直線ルートのうち、頂点上以外の位置では当該障害物と交差することのない直線ルートを前記始点側ルート候補として設定するとともに、前記障害物の各頂点上を通過する前記終点からの直線ルートのうち、頂点上以外の位置では当該障害物と交差することのない直線ルートを前記終点側ルート候補として設定し、
前記第２のルート候補設定ステップは、２つの前記障害物の各頂点上を通過する直線ルートのうち、頂点上以外の位置では当該２つの障害物および当該２つの障害物以外の障害物とは交差することのない直線ルートを前記中間ルート候補として設定する請求項１８に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項２４】
前記第２のルート候補設定ステップは、
前記２つの前記障害物のそれぞれについて、一方の前記障害物の各頂点上を通過する他方の前記障害物の各頂点からの直線ルートのうち、当該一方の障害物の頂点上以外の位置では当該一方の障害物と交差することのない直線ルートを仮中間ルート候補として設定する仮中間ルート候補設定ステップと、
前記仮中間ルート候補のうち、前記２つの障害物の双方から引かれた仮中間ルート候補を前記中間ルート候補として設定する中間ルート候補設定ステップと、
を有する請求項２３に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項２５】
前記仮中間ルート候補設定ステップは、前記障害物の頂点が凹頂点である頂点からの直線ルートを前記仮中間ルート候補には含めない請求項２４に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項２６】
前記第１のルート候補設定ステップは、前記障害物の各頂点上を通過する前記始点からの各直線ルートと、前記始点と前記終点とを結ぶ直線である交差チェック基準線と、のなす角が最大角度となる直線ルートを、前記始点側ルート候補として設定するとともに、前記障害物の各頂点上を通過する前記終点からの各直線ルートと、前記交差チェック基準線と、のなす角が最大角度となる直線ルートを、前記終点側ルート候補として設定する請求項２３に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項２７】
基板上の配線のルートを、該基板上における少なくとも１つの障害物と交差しないよう、演算処理により自動的に決定する自動配線決定処理をコンピュータに実行させるためのコンピュータプログラムであって、
配線の始点および終点となるべき２点間を結ぶ直線上に存在する障害物を所定のクリアランス分だけ太らせた仮想障害物を設定する仮想障害物設定ステップと、
前記仮想障害物に接する、前記始点からの直線ルートを始点側ルート候補として設定するとともに、前記仮想障害物に接する前記終点からの直線ルートを終点側ルート候補として設定する第１のルート候補設定ステップと、
配線の始点および終点となるべき２点間を結ぶ直線上に障害物が複数存在する場合において、２つの仮想障害物間ごとに、当該２つの仮想障害物のみに接しかつ当該２つの仮想障害物以外の仮想障害物とは交差しない直線ルートを中間ルート候補として設定する第２のルート候補設定ステップと、
前記始点側ルート候補のいずれか１つと、前記終点側ルート候補のいずれか１つと、を少なくとも含み、前記障害物が複数存在する場合には、前記２つの仮想障害物間ごとに選択される、前記中間ルート候補のいずれか１つ、をさらに含む仮ルートを設定する仮ルート設定ステップと、
前記仮ルートのうち、前記始点から前記終点までの間の距離が最短となる仮ルートを、配線の最適なルートとして確定する最適ルート確定ステップと、
を備えることを特徴とする自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項２８】
前記最適ルート確定ステップにより確定した前記最適なルートが、該最適なルートが交差を回避した前記仮想障害物以外の仮想障害物と交差することになるとき、該最適なルートが交差を回避した前記仮想障害物近傍の該最適なルート上の点を、配線の新たなる始点に設定して、前記第１のルート候補設定ステップ、前記第２のルート候補設定ステップ、前記仮ルート設定ステップおよび前記最適ルート確定ステップによる前記の処理をさらに実行する請求項２７に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項２９】
前記配線の新たなる始点として設定される、前記最適なルートが交差を回避した前記仮想障害物近傍の該最適なルート上の点は、当該最適なルートと当該仮想障害物との接点である請求項２８に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項３０】
配線の始点および終点となるべき２点間を結ぶ直線上に障害物が存在するか否かを判定する判定ステップをさらに備える請求項２７に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項３１】
前記第１のルート候補設定ステップは、多角形状を有する前記仮想障害物の各頂点上を通過する前記始点からの直線ルートのうち、頂点上以外の位置では当該仮想障害物と交差することのない直線ルートを前記始点側ルート候補として設定するとともに、前記仮想障害物の各頂点上を通過する前記終点からの直線ルートのうち、頂点上以外の位置では当該仮想障害物と交差することのない直線ルートを前記終点側ルート候補として設定し、
前記第２のルート候補設定ステップは、２つの前記仮想障害物の各頂点上を通過する直線ルートのうち、頂点上以外の位置では当該２つの仮想障害物および当該２つの仮想障害物以外の仮想障害物とは交差することのない直線ルートを前記中間ルート候補として設定する請求項２７に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項３２】
前記第２のルート候補設定ステップは、
前記２つの前記仮想障害物のそれぞれについて、一方の前記仮想障害物の各頂点上を通過する他方の前記仮想障害物の各頂点からの直線ルートのうち、当該一方の仮想障害物の頂点上以外の位置では当該一方の仮想障害物と交差することのない直線ルートを仮中間ルート候補として設定する仮中間ルート候補設定ステップと、
前記仮中間ルート候補のうち、前記２つの仮想障害物の双方から引かれた仮中間ルート候補を前記中間ルート候補として設定する中間ルート候補設定ステップと、
を有する請求項３１に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項３３】
前記仮中間ルート候補設定ステップは、前記仮想障害物の頂点が凹頂点である頂点からの直線ルートを前記仮中間ルート候補には含めない請求項３２に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項３４】
前記第１のルート候補設定ステップは、前記仮想障害物の各頂点上を通過する前記始点からの各直線ルートと、前記始点と前記終点とを結ぶ直線である交差チェック基準線と、のなす角が最大角度となる直線ルートを、前記始点側ルート候補として設定するとともに、前記仮想障害物の各頂点上を通過する前記終点からの各直線ルートと、前記交差チェック基準線と、のなす角が最大角度となる直線ルートを、前記終点側ルート候補として設定する請求項３１に記載の自動配線決定処理をコンピュータに実行させるためのコンピュータプログラム。
【請求項３５】
基板上の配線のルートを、該基板上における少なくとも１つの障害物と交差しないよう、演算処理により自動的に決定する自動配線決定方法であって、
配線の始点および終点となるべき２点間とを結ぶ直線上に存在する障害物に接する、前記始点からの直線ルートと、前記障害物に接する、前記終点からの直線ルートと、を少なくとも含んで設定される仮ルートであって、前記障害物が複数存在する場合においては、２つの障害物間ごとに選択される、当該２つの障害物のみに接しかつ当該２つの障害物以外の障害物とは交差しない直線ルートをさらに含んで設定される仮ルート、のうち、前記始点から前記終点までの間の距離が最短となる仮ルートを、配線の最適なルートとして確定することを特徴とする自動配線決定方法。
【請求項３６】
確定した前記最適なルートが、該最適なルートが交差を回避した前記障害物以外の障害物と交差することになるとき、該最適なルートが交差を回避した前記障害物近傍の該最適なルート上の点を、配線の新たなる始点に設定して、前記の処理をさらに実行する請求項３５に記載の自動配線決定方法。
【請求項３７】
前記配線の新たなる始点として設定される、前記最適なルートが交差を回避した前記障害物近傍の該最適なルート上の点は、当該最適なルートと当該障害物との接点である請求項３６に記載の自動配線決定方法。
【請求項３８】
基板上の配線のルートを、該基板上における少なくとも１つの障害物と交差しないよう、演算処理により自動的に決定する自動配線決定方法であって、
配線の始点および終点となるべき２点間を結ぶ直線上に存在する障害物を所定のクリアランス分だけ太らせた仮想障害物を設定した上で、配線の始点および終点となるべき２点間とを結ぶ直線上に存在する仮想障害物に接する、前記始点からの直線ルートと、前記仮想障害物に接する、前記終点からの直線ルートと、を少なくとも含んで設定される仮ルートであって、障害物が複数存在する場合においては、２つの仮想障害物間ごとに選択される、当該２つの仮想障害物のみに接しかつ当該２つの仮想障害物以外の仮想障害物とは交差しない直線ルートをさらに含んで設定される仮ルート、のうち、前記始点から前記終点までの間の距離が最短となる仮ルートを、配線の最適なルートとして確定することを特徴とする自動配線決定方法。
【請求項３９】
確定した前記最適なルートが、該最適なルートが交差を回避した前記仮想障害物以外の仮想障害物と交差することになるとき、該最適なルートが交差を回避した前記仮想障害物近傍の該最適なルート上の点を、配線の新たなる始点に設定して、前記の処理をさらに実行する請求項３８に記載の自動配線決定方法。
【請求項４０】
前記配線の新たなる始点として設定される、前記最適なルートが交差を回避した前記仮想障害物近傍の該最適なルート上の点は、当該最適なルートと当該仮想障害物との接点である請求項３９に記載の自動配線決定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、基板上の配線のルートを、基板上における障害物と交差しないよう、演算処理により自動的に決定する自動配線決定装置および自動配線決定方法、ならびにこの自動配線決定処理をコンピュータに実行させるためのコンピュータプログラムに関する。
【背景技術】
【０００２】
例えばＬＳＩやＰＣＢなどの半導体集積回路について、基板上に存在する障害物と交差することなく自動的に配線する配線経路探索方法の代表的なものとして、迷路探索法と呼ばれる方法がある（例えば、特許文献１〜４参照）。迷路探索法では、基板上において、配線のルートを、他の配線もしくは障害物とのクリアランスを保つように、かつ、障害物に対しては９０度の方向に、場合によっては４５度の方向に迂回させることで当該障害物と交差しないように設定する。このような設定手法を実現できるのは、ＬＳＩやＰＣＢなどにおいては障害物の配置位置や形状がある程度の規則性を有しているという、ＬＳＩやＰＣＢに特有の配線的特徴に起因するものである。
【０００３】
【特許文献１】特開平１１−１６１６９４号公報
【特許文献２】特開２００１−３５０８１３号公報
【特許文献３】特開２００１−０４４２８８号公報
【特許文献４】特開平１０−２０９２８８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
ＰＢＧＡやＥＢＧＡなどの半導体パッケージの基板上には、プレーン（Ｐｌａｎｅ）、ゲート（Ｇａｔｅ）、マーク（Ｍａｒｋ）、パッケージ内部品もしくは他の配線などといったような、配線にとっては障害物となり得るものが多数存在し、その障害物の形状、配置位置あるいは配置角度も多種多様である。また、配線の始点もしくは終点となるべきビア（Ｖｉａ）、ボール（ｂａｌｌ）、ボンディングパッド（Ｂ／Ｐ）、あるいはフリップチップパッド（Ｆ／Ｃ）などの位置も様々である。このため、半導体パッケージの配線設計においては、基板上において、障害物を回避する際には９０度や４５度に限られない任意の角度方向に配線のルートを迂回させる必要がある。つまり、従来からＬＳＩやＰＣＢなどにおける自動配線に用いられてきた迷路探索法では、半導体パッケージの自動配線に対応できない。
【０００５】
このような事情から、半導体パッケージの配線設計においては、設計者自身が、例えばＣＡＤシステムを用いて仮想平面上で半導体パッケージの配線ルートを自らの技量や経験や勘を頼りに試行錯誤しながら設計するのが一般的である。試行錯誤しながらの手動による配線設計では、要求される配線の内容が複雑になるほど、最適な配線を実現するには多大なる労力および時間を要し、難易度も増す。さらに、完成品の品質のバラツキも大きくなる。実際のところ、試行錯誤しながらの手動による配線設計によれば、描画時間でいうと十数時間以上を要し、それ以上の時間を配線設計に割り当てることは非経済的であることから、ある程度の設計結果が得られれば「大体この程度で良いだろう」と妥協しているのが現状である。半導体パッケージの一層の小型化・高集積化が進む中で、半導体パッケージについての配線設計の自動化は今後の１つの重要課題であるといえる。
【０００６】
従って本発明の目的は、上記問題に鑑み、基板上の配線のルートを、基板上における障害物と交差しないよう、短時間で自動的に決定できる自動配線決定装置および自動配線決定方法、ならびにこの自動配線決定処理をコンピュータに実行させるためのコンピュータプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を実現するために、本発明においては、配線の始点および終点となるべき２点間を結ぶ直線上に障害物が存在するとき、この障害物に接する、始点からの直線ルートと、この障害物に接する、終点からの直線ルートと、を少なくとも含んだ仮ルートをまず設定する。特にこの仮ルートは、配線の始点および終点となるべき２点間を結ぶ直線上に障害物が複数存在する場合においては、２つの障害物のみに接しかつ当該２つの障害物以外の障害物とは交差しない直線ルートをさらに含んで設定される。なお、この２つの障害物に接する直線ルートは、２つの障害物間ごとに設定される。設定された複数の仮ルートのうち、配線の始点から終点までの間の距離が最短となる仮ルートを、配線の最適なルートとして確定する。
【０００８】
図１は、本発明による自動配線決定装置の原理ブロック図である。
【０００９】
基板上の配線のルートを、この基板上における少なくとも１つの障害物と交差しないよう、演算処理により自動的に決定する自動配線決定装置１は、
配線の始点および終点となるべき２点間を結ぶ直線上に存在する障害物に接する、始点からの直線ルートを始点側ルート候補として設定するとともに、障害物に接する終点からの直線ルートを終点側ルート候補として設定する第１のルート候補設定手段１１と、
配線の始点および終点となるべき２点間を結ぶ直線上に障害物が複数存在する場合において、２つの障害物間ごとに、当該２つの障害物のみに接しかつ当該２つの障害物以外の障害物とは交差しない直線ルートを中間ルート候補として設定する第２のルート候補設定手段１２と、
始点側ルート候補のいずれか１つと、終点側ルート候補のいずれか１つと、を少なくとも含み、配線の始点および終点となるべき２点間を結ぶ直線上に障害物が複数存在する場合には、上記２つの障害物間ごとに選択される、中間ルート候補のいずれか１つ、をさらに含み得る仮ルートを設定する仮ルート設定手段１３と、
仮ルート設定手段１３により設定された仮ルートのうち、始点から終点までの間の距離が最短となる仮ルートを、配線の最適なルートとして確定する最適ルート確定手段１４と、を備える。
【００１０】
本発明においては、基板上において配線の始点および終点となるべき２点間を結ぶ直線上に障害物が存在するか否かを判定する判定手段（図示せず）をさらに備えるのが好ましい。配線の始点および終点となるべき２点間を結ぶ直線上に障害物が存在する場合は、障害物情報が第１のルート候補設定手段１１に入力され、該障害物情報と配線設計データとに基づいて第１のルート候補設定手段１１は始点側ルート候補および終点側ルート候補を設定することになる。特に、配線の始点および終点となるべき２点間を結ぶ直線上に障害物が複数存在する場合は、第１のルート候補設定手段１１のみならず第２のルート候補設定手段１２にも障害物情報が入力され、該障害物情報と配線設計データとに基づいて、第１のルート候補設定手段１１は始点側ルート候補および終点側ルート候補を設定し、第２のルート候補設定手段１２は中間ルート候補を設定することになる。
【００１１】
また、最適ルート確定手段１４により最適なルートが確定したら、この最適なルートと障害物との間のクリアランスを確保するよう、最適なルートを補正するのが好ましい。なお、この変形例として、第１のルート候補設定手段１１、第２のルート候補設定手段１２、仮ルート設定手段１３および最適ルート確定手段１４が動作する前に、確保すべきクリアランスを予め考慮しておいて上記処理を実行するようにしてもよい。この場合、配線の始点および終点となるべき２点間を結ぶ直線上に存在する障害物を所定のクリアランス分だけ太らせた仮想障害物を設定するための仮想障害物設定手段（図示せず）を備えればよい。仮想障害物設定手段による仮想障害物に関する情報を、上述した障害物情報に代えて、第１のルート候補設定手段１１および第２のルート候補設定手段１２に入力する。仮障害物に関する情報と配線設計データとに基づいて、第１のルート候補設定手段１１は始点側ルート候補および終点側ルート候補を設定し、第２のルート候補設定手段１２は中間ルート候補を設定する。
【００１２】
また、最適ルート確定手段１４により確定した最適なルートが、該最適なルートが交差を回避した障害物以外の障害物と交差することになってしまうときは、該最適なルートが交差を回避した障害物近傍の該最適なルート上の点を、配線の新たなる始点に設定して、第１のルート候補設定手段１１、第２のルート候補設定手段１２、仮ルート設定手段１３および最適ルート確定手段１４による上記の処理をさらに実行する。配線の新たなる始点として設定される、上記の最適なルートが交差を回避した障害物近傍の該最適なルート上の点は、例えば、当該最適なルートと当該障害物との接点である。
【００１３】
なお、自動配線決定装置１における第１のルート候補設定手段１１、第２のルート候補設定手段１２、仮ルート設定手段１３、最適ルート確定手段１４、判定手段および仮想障害物設定手段は、コンピュータ等の演算処理装置が実行することができるソフトウェアプログラム形式で実現できる。以上の処理を実施する装置や、以上の処理をコンピュータに実行させるプログラムを作成することは、以下の説明を理解した当業者には容易に実施できる事項である。また、以上の処理をコンピュータにより実行させるプログラムを記録媒体に格納するという事項も当業者には自明である。
【発明の効果】
【００１４】
本発明によれば、基板上に存在する障害物と交差しない配線のルートの最適な位置を、コンピュータなどを用いた演算処理により、短時間で自動的に決定することができる。
【００１５】
特に本発明は、基板上に存在する障害物の形状、配置位置および配置角度などに制限されない、クリアランス要件を満足しつつ障害物を回避することができる配線設計を、コンピュータによる演算処理が可能となるようにルール化したものである。すなわち、本発明によれば、多種多様な障害物が存在する基板上において、障害物の形状、配置位置および配置角度に制限されず、また、配線したい方向、配線したい角度および配線の開始終了位置がどのようなものであっても、クリアランス要件を満足した配線の最適なルートを短時間で自動的に探し出すことができる。つまり本発明によれば、ＬＳＩやＰＣＢなどの半導体集積回路はもちろん、ＰＢＧＡやＥＢＧＡなどの半導体パッケージ、あるいはＭＣＭ／Ｓｉｐなどの配線基板において、基板上に存在する障害物と交差することなく自動的に配線のルートを決定することができる。
【００１６】
特に、半導体パッケージの配線設計に本発明を適用すれば、従来のように設計者自らの技量、経験、勘などに左右されることなく、なおかつ、基板上に存在する障害物の形状、配置位置および配置角度などに制限されずに、配線の最適なルートを短時間で容易に設計することができる。例えば、従来、試行錯誤しながらの手動による配線設計では描画時間でいうと十数時間以上を要していたところが、本発明によれば、４時間程度以下で配線の最適なルートを自動的に設計することができる。従来のような試行錯誤しながらの手動による設計を行わずに済むので、要求される配線の内容が複雑になったり、障害物の多かったり、あるいは障害物の形状が複雑であったとしても、配線の最適なルートを短時間で実現することができる。このような設計時間の短縮および設計者の負担の軽減の結果、製品の製造コストも低減できる。最適な配線ルートは、配線距離が短いので経済的であり、製造容易であり、そして製造時における製品エラーの発生率も低い。また、電気的にも安定した特性を示す。
【発明を実施するための最良の形態】
【００１７】
図２は、本発明の実施例による自動配線決定方法の動作フローを示すフローチャートである。
【００１８】
まず、ステップＳ１０１において、ある配線を基板上に設けようとしたときにおいて、この配線の始点および終点となるべき２点間を結ぶ直線を想定し、この直線上に障害物が存在するか否かを判定する。
【００１９】
ステップＳ１０１において配線の始点および終点となるべき２点間を結ぶ直線上に障害物が存在すると判定された場合、ステップＳ１０２において、当該障害物に接する、配線の上記始点からの直線ルートを、始点側ルート候補として設定する。始点側ルート候補は１つの点から１つの対象物に引かれる接線であるといえるので、少なくとも２本存在するものである。
【００２０】
次いで、ステップＳ１０３において、当該障害物に接する、配線の上記終点からの直線ルートを、終点側ルート候補として設定する。上記始点側ルート候補同様、終点側ルート候補も少なくとも２本存在する。なお、上記ステップＳ１０２およびステップＳ１０３については実行の順番を入れ替えてもよい。
【００２１】
次に、ステップＳ１０４において、配線の始点および終点となるべき２点間を結ぶ直線上に障害物が複数存在するか否かを判定する。配線の始点および終点となるべき２点間を結ぶ直線上に障害物が複数存在すると判定された場合には、ステップＳ１０５へ進み、障害物が１つしか存在しない場合にはステップＳ１０６へ進む。なお、ステップＳ１０４における障害物が複数存在するか否かを判定する処理を、ステップＳ１０１における障害物の存在の有無を判定する処理に含め、これらの処理を同時に実行するようにしてもよい。この場合は、障害物が存在すると判定されたときにこの障害物の個数に関する情報を保持しておき、ステップＳ１０２およびＳ１０３の実行後、障害物の個数に関する情報に基づいて、ステップＳ１０５を実行するか、あるいはステップＳ１０５を実行しないままステップＳ１０６を実行するかを決定すればよい。
【００２２】
ステップＳ１０５では、２つの障害物のみに接しかつ当該２つの障害物以外の障害物とは交差しない直線ルートを、中間ルート候補として設定する。なお、ステップＳ１０４で障害物が複数存在すると判定されていることから、「２つの障害物」の組は１組以上存在することは明らかである。ステップＳ１０５で設定される中間ルート候補は、複数の障害物の中から選んだ２つの障害物の組合せごとにそれぞれ生成される。
【００２３】
次に、ステップＳ１０６において、始点側ルート候補のいずれか１つと、終点側ルート候補のいずれか１つと、を少なくとも含む仮ルートを設定する。特にこの仮ルートは、配線の始点および終点となるべき２点間を結ぶ直線上に障害物が複数存在する場合においては、上記２つの障害物ごとに選択された「中間ルート候補のいずれか１つ」、をさらに含んで設定される。例えば障害物が２つ存在する場合には、隣接する２つの障害物の組が１組であるので、当該１組分の「中間ルート候補のいずれか１つ」が仮ルートに含められる。また例えば、障害物が３つ存在する場合には、隣接する２つの障害物の組が２組、および、１つの障害物の両側に位置する２つの障害物の組が１組、が存在する。この場合、隣接する２つの障害物の組ごとの中間ルート候補は必ず存在するが、１つの障害物の両側に位置する２つの障害物の組については、例えば２つの障害物の中間に位置する障害物が非常に大きいときなどのように、中間ルート候補が存在しない場合もある。つまり、障害物が３つ存在する場合には、少なくとも２組分の「中間ルート候補のいずれか１つ」が仮ルートに含められることになる。
【００２４】
以上、ステップＳ１０６における処理をまとめると次の通りである。すなわちステップＳ１０６では、配線の始点および終点となるべき２点間を結ぶ直線上に障害物が１つ存在する場合は、仮ルートは、始点側ルート候補のいずれか１つと、終点側ルート候補のいずれか１つと、の組み合わせで設定される。配線の始点および終点となるべき２点間を結ぶ直線上に障害物が複数存在する場合は、仮ルートは、始点側ルート候補のいずれか１つと、終点側ルート候補のいずれか１つと、２つの障害物間ごとに選択された中間ルート候補のいずれか１つと、の組み合わせで設定される。
【００２５】
次いで、ステップＳ１０７では、ステップＳ１０６で得られた複数の仮ルートのうち、配線の始点および終点となるべき２点間における仮ルートに沿った距離が最短となる仮ルートを、配線の最適なルートとして確定する。
【００２６】
ステップＳ１０７において確定した最適なルートが、該最適なルートが交差を回避した前記仮想障害物以外の仮想障害物と交差することになるとき、該最適なルートが交差を回避した仮想障害物近傍の該最適なルート上の点を、配線の新たなる始点に設定して、上記の処理をさらに実行する。配線の新たなる始点として設定される点である、上記の最適なルートが交差を回避した障害物近傍の該最適なルート上の点は、例えば、当該最適なルートと当該障害物との接点である。
【００２７】
本発明の実施例による自動配線決定処理におけるステップＳ１０１〜Ｓ１０７の各処理は、コンピュータ等の演算処理装置により実行される。なお、ステップＳ１０１の実行を開始する前に、プレーン（Ｐｌａｎｅ）、ゲート（Ｇａｔｅ）、マーク（Ｍａｒｋ）、パッケージ内部品もしくは他の配線などといったような配線にとっては障害物となり得るものに関する情報、すなわち障害物の形状、配置位置あるいは配置角度に関する情報や、配線の始点もしくは終点となるべきビア（Ｖｉａ）、ボール（ｂａｌｌ）、ボンディングパッド（Ｂ／Ｐ）、あるいはフリップチップパッド（Ｆ／Ｃ）や、設計データや、クリアランスに関するルールなど関する種々のデータを、演算処理装置に予め入力しておくのが好ましい。上記演算処理装置は、入力された上記データを用いてステップＳ１０１から処理を開始する。ステップＳ１０１〜Ｓ１０７を経て、基板上に存在する障害物と交差しない配線のルートの最適な位置が、演算処理により自動的に決定される。
【００２８】
以下に、いくつか具体例を挙げる。ここで挙げられる具体例では、障害物の形状は、一例として多角形状を有しているものとするが、障害物の形状に曲線部分が含まれていても、多角形状の場合と同様に適用可能である。
【００２９】
図３〜７は、本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第１の具体例を説明する図である。
【００３０】
第１の具体例では、図３に示すように、配線の始点となるべき点Ｓから終点となるべき点Ｅとの間に、１個の障害物Ｑが存在する場合を考える。
【００３１】
図３に示すように始点Ｓと終点Ｅとを結ぶ直線Ｌ上に障害物Ｑが１個存在する場合、まず図４に示すように、障害物Ｑに接する、配線の始点Ｓからの直線ルートを、始点側ルート候補として設定する。すなわち、多角形状を有する障害物Ｑに対しては、設定される始点側ルート候補Ａ１およびＡ２は、障害物Ｑの各頂点上を通過する始点Ｓからの直線ルートのうち、頂点ａ１およびａ２上以外の位置では障害物Ｑと交差することのない直線ルートである。
【００３２】
また、図５に示すように、障害物Ｑに接する、配線の終点Ｅからの直線ルートを、終点側ルート候補として設定する。すなわち、多角形状を有する障害物Ｑに対しては、設定される終点側ルート候補Ｂ１およびＢ２は、障害物Ｑの各頂点上を通過する終点Ｅからの直線ルートのうち、頂点ｂ１およびｂ２上以外の位置では障害物Ｑと交差することのない直線ルートである。
【００３３】
第１の具体例では、配線の始点Ｓと終点Ｅとを結ぶ直線Ｌ上に１個の障害物Ｑが存在するのみであるので、中間ルート候補は生成されない。以上ここまでの処理で、１個の障害物Ｑについて、得られたルート候補は、図６に示すように、始点側ルート候補Ａ１およびＡ２ならびに終点側ルート候補Ｂ１およびＢ２である。
【００３４】
次に、始点側ルート候補Ａ１およびＡ２のうちのいずれか１つと、終点側ルート候補Ｂ１およびＢ２のうちのいずれか１つと、を含んだ仮ルートを設定する。図６に示す例では、始点側ルート候補Ａ１と終点側ルート候補Ｂ１とこれらを障害物Ｑに沿うようにして結ぶルート候補Ｘ１とからなる仮ルートＫ１と、始点側ルート候補Ａ２と終点側ルート候補Ｂ２となる仮ルートＫ１とからなる仮ルートＫ２と、が設定される。なお、例えば終点側ルート候補Ｂ１と始点側ルート候補Ａ２とを含むような仮ルートは、該仮ルート上の始点Ｓから終点Ｅまでの距離が仮ルートＫ２上の始点Ｓから終点Ｅまでの距離よりも長くなるので、設定しない。
【００３５】
このように、１個の障害物Ｑについて、得られた仮ルートはＫ１およびＫ２である。そこで次に、配線の始点Ｓおよび終点Ｅとなるべき２点間における仮ルートＫ１およびＫ２の長さを比較する。図示の例では、仮ルートＫ２の方が仮ルートＫ１よりも短いので、これを配線の最適なルートとして確定する。なお、この時点まで、配線と障害物とのクリアランス要件を考慮していない。そこで、上記のようにして得られた最適なルートと障害物との間のクリアランスを確保するよう該最適なルートを補正し、最終的には図７に示すような配線の最適なルートＫ’２を得る。
【００３６】
図４を参照して説明した始点側ルート候補および図５を参照して説明した終点側ルート候補の導出処理の一具体例を説明すると次の通りである。図８は本発明の実施例において、多角形状を有する障害物についての始点側ルート候補の導出処理の一具体例を説明する図であり、図９は本発明の実施例において、多角形状を有する障害物についての終点側ルート候補の導出処理の一具体例を説明する図である。
【００３７】
図８に示すように、まず、始点Ｓと終点Ｅとを結ぶ直線Ｌを交差チェック基準線として設定する。この交差チェック基準線Ｌは、多角形状を有する障害物Ｑを左右に分断する直線となる。この交差チェック基準線Ｌによって分けられた障害物Ｑの左右両側それぞれについて、障害物Ｑの各頂点上を通過する始点Ｓからの各直線ルートと交差チェック基準線Ｌとのなす角をチェックする。交差チェック基準線とのなす角が最大角度となる直線ルートは、図中、交差チェック基準線Ｌの左側にあるものについてはＡ１であり、交差チェック基準線Ｌの右側にあるものについてはＡ２であるので、これらを始点側ルート候補とする。
【００３８】
同様に、図９に示すように、まず、始点Ｓと終点Ｅとを結ぶ直線Ｌを交差チェック基準線として設定する。この交差チェック基準線Ｌは障害物Ｑを左右に分断する直線となるが、この交差チェック基準線Ｌによって分けられた障害物Ｑの左右両側それぞれについて、障害物Ｑの各頂点上を通過する終点Ｅからの各直線ルートと交差チェック基準線Ｌとのなす角をチェックする。交差チェック基準線とのなす角が最大角度となる直線ルートは、図中、交差チェック基準線Ｌの左側にあるものについてはＢ１であり、交差チェック基準線Ｌの右側にあるものについてはＢ２であるので、これらを終点側ルート候補とする。
【００３９】
従来から一般的に用いられる手法では、多角形状を有する障害物のラインセグメントごとにチェック用直線を引き、このチェック用直線が当該障害物と何回交差するかをラインセグメントごとに計算して障害物に対する回避ルートを導出していた。このときの演算処理量は、障害物のラインセグメント数の階乗とチェック用直線の本数の階乗との積に比例する。これに対し、本実施例では、図８および９を参照して説明したように、交差チェック基準線Ｌと最大角度をなす直線ルートを見つけ出すことにより、障害物に対する回避ルートとなり得る始点側ルート候補および終点側ルート候補を導出するものである。このときの演算処理量は、障害物のラインセグメント数に比例する。すなわち、本実施例で用いた手法の方が従来から一般的に用いられている手法に比べて演算処理量が少ないので有利である。
【００４０】
図１０〜１５は、本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第２の具体例を説明する図である。
【００４１】
第２の具体例では、図１０に示すように、配線の始点となるべき点Ｓから終点となるべき点Ｅとの間に、複数の（特にこの図では２個の）障害物Ｑ１およびＱ２が存在する場合を考える。なお、障害物Ｑ１およびＱ２は、多角形状を有しているものとする。
【００４２】
図１０に示すように始点Ｓと終点Ｅとを結ぶ直線Ｌ上に障害物Ｑ１およびＱ２が存在する場合、図１１に示すように、始点側ルート候補Ａ１およびＡ２、ならびに終点側ルート候補Ｂ１、Ｂ２およびＢ３が設定される。始点側ルート候補よび終点側ルート候補を導出するための具体的な処理は既に説明した通りである。
【００４３】
本具体例では、配線の始点Ｓおよび終点Ｅとなるべき２点間を結ぶ直線Ｌ上に障害物が複数（図示の例では２個）存在するので、図１２に示すように、２つの障害物Ｑ１およびＱ２のみに接しかつ当該２つの障害物Ｑ１およびＱ２以外の障害物とは交差しない直線ルートを、中間ルート候補として設定する。すなわち、多角形状を有する障害物Ｑ１およびＱ２は、設定される中間ルート候補Ｃ１、Ｃ２、Ｃ３およびＣ４は、２つの障害物Ｑ１およびＱ２の各頂点上を通過する直線ルートのうち、頂点ｄ１、ｄ２、ｄ３、ｄ４、ｄ５、ｄ６およびｄ７上以外の位置では当該２つの障害物Ｑ１およびＱ２、ならびに、当該２つの障害物Ｑ１およびＱ２以外の障害物、とは交差することのない直線ルートである。
【００４４】
ここまでの処理で、２個の障害物Ｑ１およびＱ２について、得られたルート候補は、図１２に示すように、始点側ルート候補Ａ１およびＡ２、中間ルート候補Ｃ１、Ｃ２、Ｃ３およびＣ４、ならびに終点側ルート候補Ｂ１およびＢ２である。
【００４５】
次に、始点側ルート候補Ａ１およびＡ２のうちのいずれか１つと、終点側ルート候補Ｂ１、Ｂ２およびＢ３のうちのいずれか１つと、を少なくとも含む仮ルートを設定する。特に、配線の始点Ｓおよび終点Ｅとなるべき２点間を結ぶ直線Ｌ上に２個の障害物Ｑ１およびＱ２が存在することから、この場合のこの仮ルートは、始点側ルート候補Ａ１およびＡ２のうちのいずれか１つと、終点側ルート候補Ｂ１、Ｂ２およびＢ３のうちのいずれか１つと、の他に、２つの障害物Ｑ１およびＱ２に関係する中間ルート候補Ｃ１、Ｃ２、Ｃ３およびＣ４のいずれか１つ、をさらに含んで設定されることになる。
【００４６】
ここで、図１２に示すように、終点Ｅからの終点側ルート候補Ｂ３は、障害物Ｑ２ではなく、障害物Ｑ１と頂点ｄ５において接している。頂点ｄ５を通る仮ルートとしては、始点側ルート候補Ａ２と中間ルート候補Ｃ３と終点側ルート候補Ｂ２とを含んでなる仮ルート、始点側ルート候補Ａ２と中間ルート候補Ｃ４と終点側ルート候補Ｂ１とを含んでなる仮ルート、および、始点側ルート候補Ａ２と終点側ルート候補Ｂ３とを含んでなる仮ルートがある。これら仮ルートはいずれも始点側ルート候補Ａ２を含んでいるが、障害物Ｑ１の頂点ｄ５から終点Ｅまでについては、中間ルート候補Ｃ３および終点側ルート候補Ｂ２を経由するルートあるいは中間ルート候補Ｃ４および終点側ルート候補Ｂ１を経由するルートで結ぶよりは、直接、終点側ルート候補Ｂ３で結んだ方が、距離的には短い。既に説明したように仮ルートは最短ものであるのが好ましいので、仮ルートを設定する際は、頂点ｄ５を通過する中間ルート候補Ｃ３およびＣ４を、仮ルートの構成要素から除外する。このようにこの時点で予め除外しておくことにより、仮ルート設定後に実行される予定の「仮ルートの中から最短のものを選択する処理」の演算処理量を予め低減しておくことができる。
【００４７】
以上、２つの障害物Ｑ１およびＱ２について、得られたルート候補は、図１３に示されるように、始点側ルート候補Ａ１およびＡ２、中間ルート候補Ｃ１およびＣ２、ならびに、終点ルート候補Ｂ１、Ｂ２およびＢ３である。
【００４８】
次に、これら始点側ルート候補、中間ルート候補および終点側ルート候補を用いて仮ルート候補を設定する。すなわち、図１４に示すように、「始点側ルート候補Ａ１と、中間ルート候補Ｃ１と、終点側ルート候補Ｂ１と、障害物Ｑ２に沿うようにして中間ルート候補Ｃ１と終点側ルート候補Ｂ１とを結ぶルート候補Ｘ１と、からなる仮ルートＫ１」と、「始点側ルート候補Ａ１と、中間ルート候補Ｃ３と、障害物Ｑ１に沿うようにして始点側ルート候補Ａ１と中間ルート候補Ｃ３とを結ぶルート候補Ｘ２と、終点側ルート候補Ｂ２と、障害物Ｑ２に沿うようにして中間ルート候補Ｃ３と終点側ルート候補Ｂ２とを結ぶルート候補Ｘ３と、からなる仮ルートＫ２」と、「始点側ルート候補Ａ２と、終点側ルート候補Ｂ３と、障害物Ｑ１に沿うようにして始点側ルート候補Ａ２と終点側ルート候補Ｂ３とを結ぶルート候補Ｘ４と、からなる仮ルートＫ３」と、が設定される。なお、中間ルート候補Ｃ３を含むような仮ルートおよび中間ルート候補Ｃ４を含むような仮ルートは、該仮ルート上の始点Ｓから終点Ｅまでの距離が仮ルートＫ３上の始点Ｓから終点Ｅまでの距離よりも明らかに長くなるので、設定しないとしたことは、既に説明した通りである。
【００４９】
以上、２個の障害物Ｑ１およびＱ２について、得られた仮ルートはＫ１、Ｋ２およびＫ３である。そこで次に、配線の始点Ｓおよび終点Ｅとなるべき２点間における仮ルートＫ１、Ｋ２およびＫ３の長さを比較する。図示の例では、仮ルートＫ２が最短であると判定され、これを配線の最適なルートとして確定する。なお、この時点まで、配線と障害物とのクリアランス要件を考慮していない。そこで、上記のようにして得られた最適なルートと障害物との間のクリアランスを確保するよう該最適なルートを補正し、最終的には図１５に示すような配線の最適なルートＫ’２を得る。
【００５０】
なお、図１２および１３を参照して説明したように、本具体例では、演算処理量をさらに低減するために、仮ルートを設定する際、頂点ｄ５を通過する中間ルート候補Ｃ３およびＣ４を、仮ルートの構成要素から予め除外している。この代替例として、中間ルート候補Ｃ３およびＣ４を含めた仮ルートを設定し、このときの仮ルートの中から最短のものを選択するようにしてもよい。
【００５１】
図１２を参照して説明した中間ルート候補の導出処理の一具体例を説明すると次の通りである。図１６〜１８は本発明の実施例において、多角形状を有する障害物についての中間ルート候補の導出処理の一具体例を説明する図である。
【００５２】
本実施例では、多角形状を有する障害物が複数存在する場合においては、２つの障害物の各頂点上を通過する直線ルートのうち、頂点上以外の位置では当該２つの障害物および当該２つの障害物以外の障害物とは交差することのない直線ルートを、中間ルート候補として設定する。
【００５３】
まず、２つの障害物のそれぞれについて、一方の障害物の各頂点上を通過する他方の障害物の各頂点からの直線ルートのうち、当該一方の障害物の頂点上以外の位置では当該一方の障害物と交差することのない直線ルートを、仮中間ルート候補として設定する。このとき、障害物の頂点が凹頂点である頂点からの直線ルートについては、仮中間ルート候補には含めない。なぜなら、障害物の凹頂点から引かれる直線ルートは、「障害物と接する直線ルート」の要件を満足することはあり得ないからである。
【００５４】
例えば障害物Ｑ１については、図１６に示すように、障害物Ｑ１の各頂点上を通過する障害物Ｑ２の各頂点ｑ１、ｑ３およびｑ４からの直線ルートのうち、障害物Ｑ１の頂点上以外の位置（図１６の場合、頂点ｐ１、ｐ２、ｐ３およびｐ５）では障害物Ｑ１と交差することのない直線ルートＤ１、Ｄ２、Ｄ３、Ｄ４、Ｄ５およびＤ６を、仮中間ルート候補として設定する。
【００５５】
同様に障害物Ｑ２については、図１７に示すように、障害物Ｑ２の各頂点上を通過する障害物Ｑ１の各頂点ｐ１、ｐ２、ｐ３およびｑ５からの直線ルートのうち、障害物Ｑ２の頂点上以外の位置（図１７の場合、頂点ｑ１、ｑ３およびｑ４）では障害物Ｑ２と交差することのない直線ルートＦ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６、Ｆ７およびＦ８を、仮中間ルート候補として設定する。
【００５６】
なお、障害物Ｑ１の凹頂点ｐ４および障害物Ｑ２の凹頂点ｑ２からの直線ルートは、「障害物と接する直線ルート」の要件を満足することはあり得ないので、仮中間ルート候補として設定されることはない。
【００５７】
そして、図１８に示すように、仮中間ルート候補Ｄ１、Ｄ２、Ｄ３、Ｄ４、Ｄ５、Ｄ６、Ｆ１、Ｆ２、Ｆ３、Ｆ４、Ｆ５、Ｆ６、Ｆ７およびＦ８のうち、２つの障害物Ｑ１およびＱ２の双方から引かれた（換言すれば、２つの障害物Ｑ１およびＱ２から引かれた仮中間ルート候補が互いに一致する）仮中間ルート候補Ｄ１およびＦ１、Ｄ３およびＦ４、Ｄ６およびＦ８、ならびに、Ｄ２およびＦ７、を、それぞれ、中間ルート候補Ｃ１、Ｃ２、Ｃ３、および、Ｃ４として設定する。
【００５８】
図１９〜２３は、本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第３の具体例を説明する図である。
【００５９】
第３の具体例では、図１９に示すように、配線の始点となるべき点Ｓから終点となるべき点Ｅとを結ぶ直線Ｌ上に障害物Ｑ１が存在し、この直線Ｌの近傍に障害物Ｑ２が存在する場合を考える。なお、障害物Ｑ１およびＱ２は、上述の各具体例と同様、多角形状を有しているものとする。配線の始点および終点となるべき２点間を結ぶ直線上に障害物が存在し、さらにこの直線の近傍に他の障害物が存在する場合は、１つの障害物との交差を回避した最適なルートを確定できたとしても、この確定した最適なルートが、今度は別の障害物と交差してしまう可能性がある。確定した最適なルートが別の障害物と新たに交差してしまう場合は、最適なルートが交差を回避した障害物近傍の該最適なルート上の点を「配線の新たなる始点」に設定して、上述したルート候補設定処理、仮ルート設定処理および最適ルート確定処理を再度実行する。配線の新たなる始点として設定される、上記の最適なルートが交差を回避した障害物近傍の該最適なルート上の点は、例えば、当該最適なルートと当該障害物との接点である。得られた最適なルートが基板上のどの障害物とも交差しなくなるまで、上記の処理を繰り返す。
【００６０】
例えば、図１９に示すような具体例では、既に説明したようなやり方で、図２０に示すような、障害物Ｑ１との交差を回避した最適なルートＫ４を確定したとしても、この確定した最適なルートＫ４が、今度は障害物Ｑ２と頂点ｂ１において交差してしまう。最適なルートＫ４が交差を回避した障害物Ｑ１の頂点ａ１と終点Ｅとを結ぶ直線上には、障害物Ｑ２が存在する。そこで、図２１に示すように、障害物Ｑ１の頂点ａ１を配線の新たなる始点Ｓ’として設定し、始点Ｓ’と終点Ｅとを結ぶ直線Ｌ’上に存在する障害物Ｑ２との交差を回避する最適なルートを、上述したルート候補設定処理、仮ルート設定処理および最適ルート確定処理を再度実行することで、確定する。新たに確定した最適なルートは、図２１に示すＫ’４である。
【００６１】
最適なルートＫ’４は、始点Ｓと終点Ｅとの間を、障害物Ｑ１およびＱ２と交差することなく結ぶものである。しかし、始点Ｓと終点Ｅとの間を障害物Ｑ１およびＱ２と交差することなく結ぶルートは、他にも存在する可能性があり、例えば図２２に示すようなルートＫ５もその１つとして考えられる。このように、障害物との交差を回避したルートが複数存在しうる場合は、これらルートのうち、始点から終点までの間の距離が最短となるルートを、再度、最適なルートとして確定し直すのが好ましい。例えば図２２に示す具体例では、ルートＫ’４とルートＫ５とについて、始点から終点までの間の距離がどちらが短いかを判定する。この具体例では、ルートＫ’４の方がルートＫ５よりも短いので、これを配線の最適なルートとして確定する。なお、この時点まででは配線と障害物とのクリアランス要件を考慮していない。そこで、上記のようにして得られた最適なルートＫ’４と障害物Ｑ１およびＱ２との間のクリアランスを確保するよう最適なルートＫ’４を補正し、最終的には図２３に示すような配線の最適なルートＫ”４が得られる。
【００６２】
以上、いくつかの具体例を挙げて説明した本発明の実施例では、最適なルートが確定したら、この最適なルートと障害物との間のクリアランスを確保するよう、最適なルートを補正する。この変形例として、ルート候補設定処理、仮ルート設定処理および最適ルート確定処理を実行する前に、確保すべきクリアランスを予め考慮してから、上記処理を実行するようにしてもよい。この場合は、配線の始点および終点となるべき２点間を結ぶ直線上に存在する障害物を所定のクリアランス分だけ太らせた仮想障害物を設定し、上述したルート候補設定処理、仮ルート設定処理および最適ルート確定処理における障害物に関するデータを、設定した上記仮想障害物に関するデータに置き換えて、各処理を実行すればよい。
【００６３】
また、本発明により得られた最適なルートは、複数の線分が連なるものであるが、実際に当該最適なルートに基づいて配線する際は、線分が直線的に折れ曲がる部分を、曲線的に滑らかに折れ曲がるようにする方が、電気的特性および配線の耐久性の観点から好ましいといえる。
【００６４】
上述した本実施例による自動配線決定装置は、コンピュータを用いて実現される。図２４は、記録媒体に格納されたプログラムにより動作する本発明の実施例の自動配線決定装置の構成を示すブロック図である。
【００６５】
本発明による自動配線決定をコンピュータに実行させるプログラムは、図２４に示すように、記憶媒体（フレキシブルディスク、ＣＤ−ＲＯＭ等の外部記憶媒体）１１０に格納されており、例えば、次に説明するような構成によるコンピュータにインストールされて自動配線決定装置として動作する。
【００６６】
ＣＰＵ１１１は、自動配線決定装置全体を制御する。このＣＰＵ１１１に、バス１１２を介してＲＯＭ１１３、ＲＡＭ１１４、ＨＤ（ハードディスク装置）１１５、マウスやキーボード等の入力装置１１６、外部記憶媒体ドライブ装置１１７およびＬＣＤ、ＣＲＴ等の表示装置１１８が接続されている。ＣＰＵ１１１の制御プログラムはＲＯＭ１１３に格納されている。
【００６７】
本発明による自動配線決定処理を実行するプログラム（自動配線決定処理プログラム）は、記憶媒体１１０からＨＤ１１５にインストール（記憶）される。また、ＲＡＭ１１４には、自動配線決定処理をＣＰＵ１１１が実行する際の作業領域や、自動配線決定処理を実行するプログラムの一部が記憶される領域が確保されている。また、ＨＤ１１５には、入力データ、最終データ、さらにＯＳ（オペレーティングシステム）等が予め記憶される。
【００６８】
まず、コンピュータの電源を投入すると、ＣＰＵ１１１がＲＯＭ１１０から制御プログラムを読み出し、さらにＨＤ１１５からＯＳを読み込み、ＯＳを起動させる。これによりコンピュータは自動配線決定処理プログラムを記憶媒体１１０からインストール可能な状態となる。
【００６９】
次に、記憶媒体１１０を外部記憶媒体ドライブ装置１１７に装着し、入力装置１１６から制御コマンドをＣＰＵ１１１に入力し、記憶媒体１１０に格納された自動配線決定処理プログラムを読み取ってＨＤ１１５等に記憶する。つまり自動配線決定処理プログラムがコンピュータにインストールされる。
【００７０】
その後は、自動配線決定処理プログラムを起動させると、コンピュータは自動配線決定装置として動作する。オペレータは、表示装置１１８に表示される対話形式による作業内容と手順に従って、入力装置１１６を操作することで、上述した自動配線決定処理を実行することができる。処理の結果得られた「配線の最適なルートに関するデータ」は、例えば、ＨＤ１１５に記憶しておいて後日利用できるようにしたり、あるいは、処理結果を表示装置１１８に視覚的に表示してもよい。
【００７１】
なお、図２４のコンピュータでは、記憶媒体１１０に記憶されたプログラムをＨＤ１１５にインストールするようにしたが、これに限らず、ＬＡＮ等の情報伝送媒体を介して、コンピュータにインストールされてもよいし、コンピュータに内蔵のＨＤ１１５に予めインストールされておいてもよい。
【産業上の利用可能性】
【００７２】
本発明によれば、基板上に存在する障害物と交差しない配線のルートの最適な位置を、コンピュータなどを用いた演算処理により、短時間で自動的に決定することができる。
【００７３】
特に本発明は、基板上に存在する障害物の形状、配置位置および配置角度などに制限されない、クリアランス要件を満足しつつ障害物を回避することができる配線設計を、コンピュータによる演算処理が可能となるようにルール化したものである。すなわち、本発明によれば、多種多様な障害物が存在する基板上において、障害物の形状、配置位置および配置角度に制限されず、また、配線したい方向、配線したい角度および配線の開始終了位置がどのようなものであっても、クリアランス要件を満足した配線の最適なルートを短時間で自動的に探し出すことができる。したがって、本発明は、ＬＳＩやＰＣＢなどの半導体集積回路はもちろん、ＰＢＧＡやＥＢＧＡなどの半導体パッケージ、あるいはＭＣＭ、ＳＩＰなど、様々な種類の配線基板において、基板上に存在する障害物と交差することなく自動的に配線のルートを決定することができる。
【図面の簡単な説明】
【００７４】
【図１】本発明による自動配線決定装置の原理ブロック図である。
【図２】本発明の実施例による自動配線決定方法の動作フローを示すフローチャートである。
【図３】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第１の具体例を説明する図（その１）である。
【図４】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第１の具体例を説明する図（その２）である。
【図５】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第１の具体例を説明する図（その３）である。
【図６】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第１の具体例を説明する図（その４）である。
【図７】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第１の具体例を説明する図（その５）である。
【図８】本発明の実施例において、多角形状を有する障害物についての始点側ルート候補の導出処理の一具体例を説明する図である。
【図９】本発明の実施例において、多角形状を有する障害物についての終点側ルート候補の導出処理の一具体例を説明する図である。
【図１０】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第２の具体例を説明する図（その１）である。
【図１１】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第２の具体例を説明する図（その２）である。
【図１２】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第２の具体例を説明する図（その３）である。
【図１３】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第２の具体例を説明する図（その４）である。
【図１４】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第２の具体例を説明する図（その５）である。
【図１５】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第２の具体例を説明する図（その６）である。
【図１６】本発明の実施例において、多角形状を有する障害物についての中間ルート候補の導出処理の一具体例を説明する図（その１）である。
【図１７】本発明の実施例において、多角形状を有する障害物についての中間ルート候補の導出処理の一具体例を説明する図（その２）である。
【図１８】本発明の実施例において、多角形状を有する障害物についての中間ルート候補の導出処理の一具体例を説明する図（その３）である。
【図１９】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第３の具体例を説明する図（その１）である。
【図２０】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第３の具体例を説明する図（その２）である。
【図２１】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第３の具体例を説明する図（その３）である。
【図２２】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第３の具体例を説明する図（その４）である。
【図２３】本発明の実施例における自動配線決定装置による配線の最適なルートの確定の第３の具体例を説明する図（その５）である。
【図２４】記録媒体に格納されたプログラムにより動作する本発明の実施例の自動配線決定装置の構成を示すブロック図である。
【符号の説明】
【００７５】
１    自動配線決定装置
１１    第１のルート候補設定手段
１２    第２のルート候補設定手段
１３    仮ルート設定手段
１４    最適ルート設定手段
【図１】
2006331017.tif 000003
【図２】
2006331017.tif 000004
【図３】
2006331017.tif 000005
【図４】
2006331017.tif 000006
【図５】
2006331017.tif 000007
【図６】
2006331017.tif 000008
【図７】
2006331017.tif 000009
【図８】
2006331017.tif 000010
【図９】
2006331017.tif 000011
【図１０】
2006331017.tif 000012
【図１１】
2006331017.tif 000013
【図１２】
2006331017.tif 000014
【図１３】
2006331017.tif 000015
【図１４】
2006331017.tif 000016
【図１５】
2006331017.tif 000017
【図１６】
2006331017.tif 000018
【図１７】
2006331017.tif 000019
【図１８】
2006331017.tif 000020
【図１９】
2006331017.tif 000021
【図２０】
2006331017.tif 000022
【図２１】
2006331017.tif 000023
【図２２】
2006331017.tif 000024
【図２３】
2006331017.tif 000025
【図２４】
2006331017.tif 000026