(57)【特許請求の範囲】
【請求項１】
部品の配置配線を行う部品配置配線装置であって、
ユーザにより入力される設計条件を受け付ける条件入力手段と、
前記部品を無作為に配置すると共に、前記条件入力手段により受け付けられた設計条件に基づいて、当該部品を配線する無作為配置配線手段と、
部品間の仮想的な力の釣り合い位置を、配線長を短くする引力と発熱量を平滑化する斥力との釣り合い位置に基づいて計算し、前記無作為配置手段によって無作為に配置された前記部品を、計算された前記釣り合い位置に基づいて、当該部品の配置を決定する位置計算配置手段と、
前記位置計算配置手段によって配置が決定された前記部品に対し、所定の回数以内で配線の交差の解消を行うと共に、当該部品をクラスター化する交差解消部品クラスター化手段と、
前記交差解消部品クラスター化手段により、全ての部品がクラスター化されたか否かを判定する部品判定手段と、を備え、
前記部品判定手段は、
まだクラスター化されていない部品が残っている場合には、当該まだクラスター化されていない部品に対し、前記位置計算配置手段と前記交差解消部品クラスター化手段とによって配置配線とクラスター化を行い、一方、全ての部品がクラスター化された場合には、配置配線を終了することを特徴とする部品配置配線装置。
【請求項２】
前記交差解消部品クラスター化手段は、
前記配線に対して優先順位が配線クラスとして割り当てられ、優先順位の最も高い配線クラスから、配線する順序を決定する配線順序決定手段と、
順序が決定された前記配線クラスに対し、前記交差の解消を行うと共に、再配線を行う交差解消再配線手段と、
前記交差解消再配線手段により、配線が収束したか否かを判定する収束判定手段と、
前記収束判定手段により、当該配線クラスの配線が収束した場合には、配線クラスを優先順位が次に低い配線クラスに変更し、配線順序を変更する順位変更手段と、
前記収束判定手段により、当該配線クラスの配線が収束しない場合には、交差解消が終了した配線クラスの配線で結ばれた部品を、１つのクラスター部品として登録する部品クラスター化手段と、
前記部品クラスター化手段により登録された前記クラスター部品内の部品同士を、配線が交わらない範囲であって、かつ部品の発熱量で決定される限界距離内で近づけていき、クラスター部品の大きさを縮小するクラスター縮約手段と、
を更に備えることを特徴とする請求項１記載の部品配置配線装置。
【請求項３】
部品の配置配線を行う部品配置配線装置であって、
ユーザにより入力される設計条件を受け付ける条件入力手段と、
前記部品を無作為に配置すると共に、前記条件入力手段により受け付けられた設計条件に基づいて、当該部品を配線する無作為配置配線手段と、
部品間の仮想的な力の釣り合い位置を計算し、前記無作為配置手段によって無作為に配置された前記部品を、計算された前記釣り合い位置に基づいて、当該部品の配置を決定する位置計算配置手段と、
前記位置計算配置手段によって配置が決定された前記部品に対し、所定の回数以内で配線の交差の解消を行うと共に、当該部品をクラスター化する交差解消部品クラスター化手段と、
前記交差解消部品クラスター化手段により、全ての部品がクラスター化されたか否かを判定する部品判定手段と、を備え、
前記部品判定手段は、まだクラスター化されていない部品が残っている場合には、当該まだクラスター化されていない部品に対し、前記位置計算配置手段と前記交差解消部品クラスター化手段とによって配置配線とクラスター化を行い、一方、全ての部品がクラスター化された場合には、配置配線を終了し、
前記交差解消部品クラスター化手段は、
前記配線に対して優先順位が配線クラスとして割り当てられ、優先順位の最も高い配線クラスから、配線する順序を決定する配線順序決定手段と、
順序が決定された前記配線クラスに対し、前記交差の解消を行うと共に、再配線を行う交差解消再配線手段と、
前記交差解消再配線手段により、配線が収束したか否かを判定する収束判定手段と、
前記収束判定手段により、当該配線クラスの配線が収束した場合には、配線クラスを優先順位が次に低い配線クラスに変更し、配線順序を変更する順位変更手段と、
前記収束判定手段により、当該配線クラスの配線が収束しない場合には、交差解消が終了した配線クラスの配線で結ばれた部品を、１つのクラスター部品として登録する部品クラスター化手段と、
前記部品クラスター化手段により登録された前記クラスター部品内の部品同士を、配線が交わらない範囲であって、かつ部品の発熱量で決定される限界距離内で近づけていき、クラスター部品の大きさを縮小するクラスター縮約手段と、
を更に備えることを特徴とする部品配置配線装置。
【請求項４】
部品の配置配線を行う部品配置配線装置における部品配置配線方法であって、
ユーザにより入力される設計条件を受け付ける条件入力ステップと、
前記部品を無作為に配置すると共に、前記条件入力ステップにより受け付けられた設計条件に基づいて、当該部品を配線する無作為配置配線ステップと、
部品間の仮想的な力の釣り合い位置を、配線長を短くする引力と発熱量を平滑化する斥力との釣り合い位置に基づいて計算し、前記無作為配置ステップによって無作為に配置された前記部品を、計算された前記釣り合い位置に基づいて、当該部品の配置を決定する位置計算配置ステップと、
前記位置計算配置ステップによって配置が決定された前記部品に対し、所定の回数以内で配線の交差の解消を行うと共に、当該部品をクラスター化する交差解消部品クラスター化ステップと、
前記交差解消部品クラスター化ステップにより、全ての部品がクラスター化されたか否かを判定する部品判定ステップと、を備え、
前記部品判定ステップは、
まだクラスター化されていない部品が残っている場合には、当該まだクラスター化されていない部品に対し、前記位置計算配置ステップと前記交差解消部品クラスター化ステップとによって配置配線とクラスター化を行い、一方、全ての部品がクラスター化された場合には、配置配線を終了することを特徴とする部品配置配線方法。
【請求項５】
前記交差解消部品クラスター化ステップは、
前記配線に対して優先順位が配線クラスとして割り当てられ、優先順位の最も高い配線クラスから、配線する順序を決定する配線順序決定ステップと、
順序が決定された前記配線クラスに対し、前記交差の解消を行うと共に、再配線を行う交差解消再配線ステップと、
前記交差解消再配線ステップにより、配線が収束したか否かを判定する収束判定ステップと、
前記収束判定ステップにより、当該配線クラスの配線が収束した場合には、配線クラスを優先順位が次に低い配線クラスに変更し、配線順序を変更する順位変更ステップと、
前記収束判定ステップにより、当該配線クラスの配線が収束しない場合には、交差解消が終了した配線クラスの配線で結ばれた部品を、１つのクラスター部品として登録する部品クラスター化ステップと、
前記部品クラスター化ステップにより登録された前記クラスター部品内の部品同士を、配線が交わらない範囲であって、かつ部品の発熱量で決定される限界距離内で近づけていき、クラスター部品の大きさを縮小するクラスター縮約ステップと、
を更に備えることを特徴とする請求項４記載の部品配置配線方法。
【請求項６】
部品の配置配線を行う部品配置配線装置における部品配置配線方法であって、
ユーザにより入力される設計条件を受け付ける条件入力ステップと、
前記部品を無作為に配置すると共に、前記条件入力ステップにより受け付けられた設計条件に基づいて、当該部品を配線する無作為配置配線ステップと、
部品間の仮想的な力の釣り合い位置を計算し、前記無作為配置ステップによって無作為に配置された前記部品を、計算された前記釣り合い位置に基づいて、当該部品の配置を決定する位置計算配置ステップと、
前記位置計算配置ステップによって配置が決定された前記部品に対し、所定の回数以内で配線の交差の解消を行うと共に、当該部品をクラスター化する交差解消部品クラスター化ステップと、
前記交差解消部品クラスター化ステップにより、全ての部品がクラスター化されたか否かを判定する部品判定ステップと、を備え、
前記部品判定ステップは、まだクラスター化されていない部品が残っている場合には、当該まだクラスター化されていない部品に対し、前記位置計算配置ステップと前記交差解消部品クラスター化ステップとによって配置配線とクラスター化を行い、一方、全ての部品がクラスター化された場合には、配置配線を終了し、
前記交差解消部品クラスター化ステップは、
前記配線に対して優先順位が配線クラスとして割り当てられ、優先順位の最も高い配線クラスから、配線する順序を決定する配線順序決定ステップと、
順序が決定された前記配線クラスに対し、前記交差の解消を行うと共に、再配線を行う交差解消再配線ステップと、
前記交差解消再配線ステップにより、配線が収束したか否かを判定する収束判定ステップと、
前記収束判定ステップにより、当該配線クラスの配線が収束した場合には、配線クラスを優先順位が次に低い配線クラスに変更し、配線順序を変更する順位変更ステップと、
前記収束判定ステップにより、当該配線クラスの配線が収束しない場合には、交差解消が終了した配線クラスの配線で結ばれた部品を、１つのクラスター部品として登録する部品クラスター化ステップと、
前記部品クラスター化ステップにより登録された前記クラスター部品内の部品同士を、配線が交わらない範囲であって、かつ部品の発熱量で決定される限界距離内で近づけていき、クラスター部品の大きさを縮小するクラスター縮約ステップと、
を更に備えることを特徴とする部品配置配線方法。
【請求項７】
部品の配置配線を行う部品配置配線装置における部品配置配線プログラムであって、
ユーザにより入力される設計条件を受け付ける条件入力手順と、
前記部品を無作為に配置すると共に、前記条件入力手順により受け付けられた設計条件に基づいて、当該部品を配線する無作為配置配線手順と、
部品間の仮想的な力の釣り合い位置を、配線長を短くする引力と発熱量を平滑化する斥力との釣り合い位置に基づいて計算し、前記無作為配置手順によって無作為に配置された前記部品を、計算された前記釣り合い位置に基づいて、当該部品の配置を決定する位置計算配置手順と、
前記位置計算配置手順によって配置が決定された前記部品に対し、所定の回数以内で配線の交差の解消を行うと共に、当該部品をクラスター化する交差解消部品クラスター化手順と、
前記交差解消部品クラスター化手順により、全ての部品がクラスター化されたか否かを判定する部品判定手順と、を備え、
前記部品判定手順は、
まだクラスター化されていない部品が残っている場合には、当該まだクラスター化されていない部品に対し、前記位置計算配置手順と前記交差解消部品クラスター化手順とによって配置配線とクラスター化を行い、一方、全ての部品がクラスター化された場合には、配置配線を終了することをコンピュータに実行させることを特徴とする部品配置配線プログラム。
【請求項８】
前記交差解消部品クラスター化手順は、
前記配線に対して優先順位が配線クラスとして割り当てられ、優先順位の最も高い配線クラスから、配線する順序を決定する配線順序決定手順と、
順序が決定された前記配線クラスに対し、前記交差の解消を行うと共に、再配線を行う交差解消再配線手順と、
前記交差解消再配線手順により、配線が収束したか否かを判定する収束判定手順と、
前記収束判定手順により、当該配線クラスの配線が収束した場合には、配線クラスを優先順位が次に低い配線クラスに変更し、配線順序を変更する順位変更手順と、
前記収束判定手順により、当該配線クラスの配線が収束しない場合には、交差解消が終了した配線クラスの配線で結ばれた部品を、１つのクラスター部品として登録する部品クラスター化手順と、
前記部品クラスター化手順により登録された前記クラスター部品内の部品同士を、配線が交わらない範囲であって、かつ部品の発熱量で決定される限界距離内で近づけていき、クラスター部品の大きさを縮小するクラスター縮約手順と、
を更にコンピュータに実行させることを特徴とする請求項７記載の部品配置配線プログラム。
【請求項９】
部品の配置配線を行う部品配置配線装置における部品配置配線プログラムであって、
ユーザにより入力される設計条件を受け付ける条件入力手順と、
前記部品を無作為に配置すると共に、前記条件入力手順により受け付けられた設計条件に基づいて、当該部品を配線する無作為配置配線手順と、
部品間の仮想的な力の釣り合い位置を計算し、前記無作為配置手順によって無作為に配置された前記部品を、計算された前記釣り合い位置に基づいて、当該部品の配置を決定する位置計算配置手順と、
前記位置計算配置手順によって配置が決定された前記部品に対し、所定の回数以内で配線の交差の解消を行うと共に、当該部品をクラスター化する交差解消部品クラスター化手順と、
前記交差解消部品クラスター化手順により、全ての部品がクラスター化されたか否かを判定する部品判定手順と、を備え、
前記部品判定手順は、まだクラスター化されていない部品が残っている場合には、当該まだクラスター化されていない部品に対し、前記位置計算配置手順と前記交差解消部品クラスター化手順とによって配置配線とクラスター化を行い、一方、全ての部品がクラスター化された場合には、配置配線を終了することをコンピュータに実行させ、
前記交差解消部品クラスター化手順では、
前記配線に対して優先順位が配線クラスとして割り当てられ、優先順位の最も高い配線クラスから、配線する順序を決定する配線順序決定手順と、
順序が決定された前記配線クラスに対し、前記交差の解消を行うと共に、再配線を行う交差解消再配線手順と、
前記交差解消再配線手順により、配線が収束したか否かを判定する収束判定手順と、
前記収束判定手順により、当該配線クラスの配線が収束した場合には、配線クラスを優先順位が次に低い配線クラスに変更し、配線順序を変更する順位変更手順と、
前記収束判定手順により、当該配線クラスの配線が収束しない場合には、交差解消が終了した配線クラスの配線で結ばれた部品を、１つのクラスター部品として登録する部品クラスター化手順と、
前記部品クラスター化手順により登録された前記クラスター部品内の部品同士を、配線が交わらない範囲であって、かつ部品の発熱量で決定される限界距離内で近づけていき、クラスター部品の大きさを縮小するクラスター縮約手順と、
を更にコンピュータに実行させることを特徴とする部品配置配線プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、部品配置配線装置、部品配置配線方法及び部品配置配線プログラムに関し、特に、回路基板やＬＳＩ（large scale integrated circuit）に適用可能な部品配置配線装置、部品配置配線方法及び部品配置配線プログラムに関する。
【背景技術】
【０００２】
近年、電子機器の回路基板の設計において、部品の増大と、その部品の増大に伴う配線の複雑化により、手動での設計では限界が見えてきている。
【０００３】
また最近は、様々な配置配線の要求や条件が多くなり、その要求を満たすと共に、非常に多くの部品を配置配線する処理が求められ、配置配線の処理が複雑化している。
【０００４】
そのため、最適もしくは最適に近いような配置配線の設計を現実的な時間内で行う設計システムは、確立されていない。
【０００５】
実際には、後戻り行程を繰り返しながら、試行錯誤による全手動の配置配線か、又は、大まかな配置配線を自動で設計した後、手動でチューニングを行っているのが現状である。
【０００６】
ところが、技術競争が進み、回路基板の納期の短縮、製造の効率化などにより、これらの後戻り過程をなるべく少なくする要求が非常に高まっている。
【０００７】
このような状況の中で、配線長の低減を目的とした部品配置配線方法については、次の方法論が提案されている。
【０００８】
まず、第１の方法は、配線長や発熱量の平滑化、部品の重なりの除外、ＥＭＩ（electromagnetic interference）低減等の目的で仮想的力を導入して、その釣り合い位置として最適配置を求める方法である。
【０００９】
この方法は、特許文献１、非特許文献１、非特許文献２等に記載されている。
【００１０】
具体的に特許文献１には、配線の長さに応じた弾性引力と、部品の重なりに応じた斥力を導入し、つりあいの位置を求める方法を提案している。
【００１１】
また、非特許文献１には、基板上の発熱の均等化を目的として、部品の発熱量に比例し距離の逆２乗則に従う斥力と、配線長に比例した弾性引力とに従い、つりあいの位置として最適配置を求める方法が提案されている。
【００１２】
また、非特許文献２には、ＥＭＩを配線の長さと電流の関数として表し、これを仮想的力として釣り合いの問題を解き、ＥＭＩを低減する配置を探索する方法が提案されている。
【００１３】
次に、第２の方法は、遺伝的アルゴリズムを用いて、配線長低減や複数の目的関数の下で、最適配置を求めるものである（例えば、特許文献２参照）。
【００１４】
このような試みとして、非特許文献３には、部品の温度と、配線長を目的関数として最適な配置を探索する遺伝的アルゴリズムが提案されている。
【００１５】
そして、第３の方法は、目的関数を参照しながら、部品を一つずつ最適の場所に配置する方法である。
【００１６】
具体的に非特許文献４には、部品の温度と、配線長を目的関数とした配置方法が提案されている。
【００１７】
もう一方で、配線長をなるべく短くしながら配線同士の交差を取り除くということも、非常に重要な設計項目であり、多くの方法が提案されている。
【００１８】
この配線長を短くしながら配線同士の交差を取り除く方法は、非常に大規模化したＬＳＩの配線では、もはや人の手では配線が行えないので、アルゴリズムを用いることによって、ＬＳＩ設計の分野でも大きく進歩してきた。
【００１９】
例えば、特許文献３には、古典的な配線法である迷路法などでは見つけられなかった良い配線を、現実的な時間で発見できるアルゴリズムが提案されている。
【００２０】
しかしながら、このような配線方法は、配線単独の設計手法であることと、解析時間の長さがネックとなっている。
【００２１】
これまで提案された回路設計方法は、これらのように配置方法と配線方法のいずれかに力点を置くものであり、或いは配置配線方法として提案されながらも、両者を順次に独立して行う単純な組み合わせというものであった。
【特許文献１】特開平３−１２４０４６号公報
【特許文献２】特開２０００−２５９６８２号公報
【特許文献３】特公平０６−０４２２５６号公報
【非特許文献１】Lee, “Thermal Placement Algorithm Based on Heat Conduction Analogy”, IEEE Transactions on Components and Packaging Technologies, (2003), Vol.26, No.2, pp. 473-482
【非特許文献２】谷本、中山、池田、福本、植村、「信号線からのＥＭＩを考慮したプリント回路板の自動部品配置アルゴリズム」、エレクトロニクス実装学会誌、４巻３号２００１年、pp.231-236
【非特許文献３】Deb, Jain, Gupta, Maji, “Multiobjective Placement of Electronic Components Using Evolutionary Algorithms”, IEEE Transactions on Components and Packaging Technologies, (2004), Vol.27, No.3, pp.480-492
【非特許文献４】林、岩田、藤本、佐藤、「モジュール間境界条件に基づく解析・設計による熱・回路協調設計」、電子情報通信学会論文誌ＣVol.J88-C No.11 pp.972-980
【発明の開示】
【発明が解決しようとする課題】
【００２２】
ところで、配置問題と配線問題は、信号の遅延や電磁放射の低減の上で重要となる配線長の低減という目的を経由して互いに関連し合っているので、配置の最適化は配線の最適化を崩してしまい、また配線の最適化は配置の最適化を崩してしまう。
【００２３】
このため、最適配置、最適配線を順次独立に行っても、真の最適解を達成できるとは限らない。
【００２４】
従って、最適な配置配線の設計を行うためには、配線と配置を独立に行うのではなく、両方を協調させた設計を行わなければならない、という問題があった。
【００２５】
また、全ての配置配線の場合を調べ尽くす全幅探索を行うことにより、最適な配置配線を探すことは原理的には可能である。
【００２６】
しかしながら、配置配線の場合の数は、部品の数に対して指数関数的に増大するため、この方法では現実的とは言えない。
【００２７】
そこで、代替案として、遺伝的アルゴリズムやシミュレーティッドアニーリングなどの最適化アルゴリズムを適用することにより、指数関数から巾関数程度の場合の数に低減し、効率的に探索する方法論が考えられる。
【００２８】
ところが、巾関数程度の場合の数に低減しても、多くの計算リソースと時間を要するため、限られた設計期間の中で様々な設計を試みるような要求には応えることができない、という問題があった。
【００２９】
このように、これらの理由から、現実的な時間で配置配線を達成しようと試みても、より最適に近い解を探索する方法を構築することができなかった。
【００３０】
そこで、本発明は上記問題点を鑑みてなされたものであり、最適な配置と配線設計を協調的に行い、現実的な時間で最適解を探索する部品配置配線装置、部品配置配線方法及び部品配置配線プログラムを実現することを目的とする。
【課題を解決するための手段】
【００３１】
本発明に係る部品配置配線装置は、部品の配置配線を行う部品配置配線装置であって、ユーザにより入力される設計条件を受け付ける条件入力手段と、前記部品を無作為に配置すると共に、前記条件入力手段により受け付けられた設計条件に基づいて、当該部品を配線する無作為配置配線手段と、部品間の仮想的な力の釣り合い位置を、配線長を短くする引力と発熱量を平滑化する斥力との釣り合い位置に基づいて計算し、前記無作為配置手段によって無作為に配置された前記部品を、計算された前記釣り合い位置に基づいて、当該部品の配置を決定する位置計算配置手段と、前記位置計算配置手段によって配置が決定された前記部品に対し、所定の回数以内で配線の交差の解消を行うと共に、当該部品をクラスター化する交差解消部品クラスター化手段と、前記交差解消部品クラスター化手段により、全ての部品がクラスター化されたか否かを判定する部品判定手段と、を備え、前記部品判定手段は、まだクラスター化されていない部品が残っている場合には、当該まだクラスター化されていない部品に対し、前記位置計算配置手段と前記交差解消部品クラスター化手段とによって配置配線とクラスター化を行い、一方、全ての部品がクラスター化された場合には、配置配線を終了することを特徴とする。
また、本発明に係る部品配置配線装置は、部品の配置配線を行う部品配置配線装置であって、ユーザにより入力される設計条件を受け付ける条件入力手段と、前記部品を無作為に配置すると共に、前記条件入力手段により受け付けられた設計条件に基づいて、当該部品を配線する無作為配置配線手段と、部品間の仮想的な力の釣り合い位置を計算し、前記無作為配置手段によって無作為に配置された前記部品を、計算された前記釣り合い位置に基づいて、当該部品の配置を決定する位置計算配置手段と、前記位置計算配置手段によって配置が決定された前記部品に対し、所定の回数以内で配線の交差の解消を行うと共に、当該部品をクラスター化する交差解消部品クラスター化手段と、前記交差解消部品クラスター化手段により、全ての部品がクラスター化されたか否かを判定する部品判定手段と、を備え、前記部品判定手段は、まだクラスター化されていない部品が残っている場合には、当該まだクラスター化されていない部品に対し、前記位置計算配置手段と前記交差解消部品クラスター化手段とによって配置配線とクラスター化を行い、一方、全ての部品がクラスター化された場合には、配置配線を終了し、前記交差解消部品クラスター化手段は、前記配線に対して優先順位が配線クラスとして割り当てられ、優先順位の最も高い配線クラスから、配線する順序を決定する配線順序決定手段と、順序が決定された前記配線クラスに対し、前記交差の解消を行うと共に、再配線を行う交差解消再配線手段と、前記交差解消再配線手段により、配線が収束したか否かを判定する収束判定手段と、前記収束判定手段により、当該配線クラスの配線が収束した場合には、配線クラスを優先順位が次に低い配線クラスに変更し、配線順序を変更する順位変更手段と、前記収束判定手段により、当該配線クラスの配線が収束しない場合には、交差解消が終了した配線クラスの配線で結ばれた部品を、１つのクラスター部品として登録する部品クラスター化手段と、前記部品クラスター化手段により登録された前記クラスター部品内の部品同士を、配線が交わらない範囲であって、かつ部品の発熱量で決定される限界距離内で近づけていき、クラスター部品の大きさを縮小するクラスター縮約手段と、を更に備えることを特徴とする。
【００３２】
本発明に係る部品配置配線方法は、部品の配置配線を行う部品配置配線装置における部品配置配線方法であって、ユーザにより入力される設計条件を受け付ける条件入力ステップと、前記部品を無作為に配置すると共に、前記条件入力ステップにより受け付けられた設計条件に基づいて、当該部品を配線する無作為配置配線ステップと、部品間の仮想的な力の釣り合い位置を、配線長を短くする引力と発熱量を平滑化する斥力との釣り合い位置に基づいて計算し、前記無作為配置ステップによって無作為に配置された前記部品を、計算された前記釣り合い位置に基づいて、当該部品の配置を決定する位置計算配置ステップと、前記位置計算配置ステップによって配置が決定された前記部品に対し、所定の回数以内で配線の交差の解消を行うと共に、当該部品をクラスター化する交差解消部品クラスター化ステップと、前記交差解消部品クラスター化ステップにより、全ての部品がクラスター化されたか否かを判定する部品判定ステップと、を備え、前記部品判定ステップは、まだクラスター化されていない部品が残っている場合には、当該まだクラスター化されていない部品に対し、前記位置計算配置ステップと前記交差解消部品クラスター化ステップとによって配置配線とクラスター化を行い、一方、全ての部品がクラスター化された場合には、配置配線を終了することを特徴とする。
また、本発明に係る部品配置配線方法は、部品の配置配線を行う部品配置配線装置における部品配置配線方法であって、ユーザにより入力される設計条件を受け付ける条件入力ステップと、前記部品を無作為に配置すると共に、前記条件入力ステップにより受け付けられた設計条件に基づいて、当該部品を配線する無作為配置配線ステップと、部品間の仮想的な力の釣り合い位置を計算し、前記無作為配置ステップによって無作為に配置された前記部品を、計算された前記釣り合い位置に基づいて、当該部品の配置を決定する位置計算配置ステップと、前記位置計算配置ステップによって配置が決定された前記部品に対し、所定の回数以内で配線の交差の解消を行うと共に、当該部品をクラスター化する交差解消部品クラスター化ステップと、前記交差解消部品クラスター化ステップにより、全ての部品がクラスター化されたか否かを判定する部品判定ステップと、を備え、前記部品判定ステップは、まだクラスター化されていない部品が残っている場合には、当該まだクラスター化されていない部品に対し、前記位置計算配置ステップと前記交差解消部品クラスター化ステップとによって配置配線とクラスター化を行い、一方、全ての部品がクラスター化された場合には、配置配線を終了し、前記交差解消部品クラスター化ステップは、前記配線に対して優先順位が配線クラスとして割り当てられ、優先順位の最も高い配線クラスから、配線する順序を決定する配線順序決定ステップと、順序が決定された前記配線クラスに対し、前記交差の解消を行うと共に、再配線を行う交差解消再配線ステップと、前記交差解消再配線ステップにより、配線が収束したか否かを判定する収束判定ステップと、前記収束判定ステップにより、当該配線クラスの配線が収束した場合には、配線クラスを優先順位が次に低い配線クラスに変更し、配線順序を変更する順位変更ステップと、前記収束判定ステップにより、当該配線クラスの配線が収束しない場合には、交差解消が終了した配線クラスの配線で結ばれた部品を、１つのクラスター部品として登録する部品クラスター化ステップと、前記部品クラスター化ステップにより登録された前記クラスター部品内の部品同士を、配線が交わらない範囲であって、かつ部品の発熱量で決定される限界距離内で近づけていき、クラスター部品の大きさを縮小するクラスター縮約ステップと、を更に備えることを特徴とする。
【００３３】
本発明に係る部品配置配線プログラムは、部品の配置配線を行う部品配置配線装置における部品配置配線プログラムであって、ユーザにより入力される設計条件を受け付ける条件入力手順と、前記部品を無作為に配置すると共に、前記条件入力手順により受け付けられた設計条件に基づいて、当該部品を配線する無作為配置配線手順と、部品間の仮想的な力の釣り合い位置を、配線長を短くする引力と発熱量を平滑化する斥力との釣り合い位置に基づいて計算し、前記無作為配置手順によって無作為に配置された前記部品を、計算された前記釣り合い位置に基づいて、当該部品の配置を決定する位置計算配置手順と、前記位置計算配置手順によって配置が決定された前記部品に対し、所定の回数以内で配線の交差の解消を行うと共に、当該部品をクラスター化する交差解消部品クラスター化手順と、前記交差解消部品クラスター化手順により、全ての部品がクラスター化されたか否かを判定する部品判定手順と、を備え、前記部品判定手順は、まだクラスター化されていない部品が残っている場合には、当該まだクラスター化されていない部品に対し、前記位置計算配置手順と前記交差解消部品クラスター化手順とによって配置配線とクラスター化を行い、一方、全ての部品がクラスター化された場合には、配置配線を終了することをコンピュータに実行させることを特徴とする。
また、本発明に係る部品配置配線プログラムは、部品の配置配線を行う部品配置配線装置における部品配置配線プログラムであって、ユーザにより入力される設計条件を受け付ける条件入力手順と、前記部品を無作為に配置すると共に、前記条件入力手順により受け付けられた設計条件に基づいて、当該部品を配線する無作為配置配線手順と、部品間の仮想的な力の釣り合い位置を計算し、前記無作為配置手順によって無作為に配置された前記部品を、計算された前記釣り合い位置に基づいて、当該部品の配置を決定する位置計算配置手順と、前記位置計算配置手順によって配置が決定された前記部品に対し、所定の回数以内で配線の交差の解消を行うと共に、当該部品をクラスター化する交差解消部品クラスター化手順と、前記交差解消部品クラスター化手順により、全ての部品がクラスター化されたか否かを判定する部品判定手順と、を備え、前記部品判定手順は、まだクラスター化されていない部品が残っている場合には、当該まだクラスター化されていない部品に対し、前記位置計算配置手順と前記交差解消部品クラスター化手順とによって配置配線とクラスター化を行い、一方、全ての部品がクラスター化された場合には、配置配線を終了することをコンピュータに実行させ、前記交差解消部品クラスター化手順では、前記配線に対して優先順位が配線クラスとして割り当てられ、優先順位の最も高い配線クラスから、配線する順序を決定する配線順序決定手順と、順序が決定された前記配線クラスに対し、前記交差の解消を行うと共に、再配線を行う交差解消再配線手順と、前記交差解消再配線手順により、配線が収束したか否かを判定する収束判定手順と、前記収束判定手順により、当該配線クラスの配線が収束した場合には、配線クラスを優先順位が次に低い配線クラスに変更し、配線順序を変更する順位変更手順と、前記収束判定手順により、当該配線クラスの配線が収束しない場合には、交差解消が終了した配線クラスの配線で結ばれた部品を、１つのクラスター部品として登録する部品クラスター化手順と、前記部品クラスター化手順により登録された前記クラスター部品内の部品同士を、配線が交わらない範囲であって、かつ部品の発熱量で決定される限界距離内で近づけていき、クラスター部品の大きさを縮小するクラスター縮約手順と、を更にコンピュータに実行させることを特徴とする。
【発明の効果】
【００３４】
本発明によれば、部品配置配線装置は、配置と配線を別個独立に行うのではなく、協調的に連動させて行っているので、効率的に解探索ができ、探索の速度を上げられると同時に、独立に探索した場合では見つからない配置配線を見つけることができる。
【００３５】
これにより、最適な配置と配線設計を協調的に行い、現実的な時間で最適解を探索する部品配置配線装置、部品配置配線方法及び部品配置配線プログラムを実現することができる。
【発明を実施するための最良の形態】
【００３６】
次に、本発明を実施するための実施形態１について、図面を参照して詳細に説明する。
【００３７】
（実施形態１）
（１）部品配置配線装置の構成
図１を参照すると、本発明に係る部品配置配線装置は、条件入力部１と、記憶部２と、位置計算決定部３と、部品間配線部４と、クラスター化部５と、配線クラス管理部６と、クラスター部品管理部７とを備えている。
【００３８】
条件入力部１は、部品の種類、数、接続関係、配線のランク、発熱量等の設計条件を入力する機能を有している。
【００３９】
記憶部２は、条件入力部１において入力された設計条件を記憶し、格納する機能を有している。
【００４０】
位置計算決定部３は、部品間の仮想的力を計算し、その釣り合いの位置を決める機能を有している。
【００４１】
部品間配線部４は、部品間の配線を行う機能を有している。
【００４２】
クラスター化部５は、部品の縮約を計り、クラスター化する機能を有している。
【００４３】
配線クラス管理部６は、部品間配線部４が交差する配線を解消するように配線を行う、配線クラスを管理する機能を有している。
【００４４】
クラスター部品管理部７は、クラスター化されたクラスター部品を管理する機能を有している。
【００４５】
次に、これらの各部は、それぞれ概略以下のように動作する。
【００４６】
条件入力部１は、設計に必要な条件を、システムに取り込む。
【００４７】
記憶部２は、条件入力部１からの設計条件を記憶している。
【００４８】
位置計算決定部３は、設計条件を参照して、部品間の仮想的力を計算すると共に、その釣り合いの位置を求め、部品の配置を行う。
【００４９】
部品間配線部４は、配線クラス管理部６で管理され指定されるクラスの配線に関して、全体の配線長を短くしながら配線の交差解消を行う。
【００５０】
クラスター化部５は、指定されたクラスの配線で結ばれた部品群を、配線のトポロジーを変えずにじわじわと接近させ、クラスター化させる。
【００５１】
配線クラス管理部６は、部品間配線部４が行う配線処理のクラスを指定すると同時に収束判定を行う。
【００５２】
クラスター部品管理部７は、どの部品がクラスター化されるかを判断し、クラスター部品を管理する。
【００５３】
（２）部品配置配線装置における配置配線処理の動作
次に、本発明に係る部品配置配線装置における配置配線処理の動作について、図２のフローチャートと、図面を参照しながら、詳細に説明する。
【００５４】
まず、図２のフローチャートを参照すると、ステップＳ１１において、ユーザが各種の条件を入力するようになっている。
【００５５】
ここで、この入力される各種の条件の内容は、図３に示すフローチャートに従って、ユーザが各種の項目を入力し、条件を決定する。
【００５６】
ステップＳ１１−１では、ユーザは、部品の種類や数を指定する。
【００５７】
ステップＳ１１−２では、ユーザは、部品同士の接続関係を指定する。
【００５８】
ステップＳ１１−３では、ユーザは、図４に示すように、配線に流れる信号の重要度により配線のランク分けを行い、優先順位を設定する。
【００５９】
次に、ステップＳ１１−４では、単位面積あたりの許容発熱量を決定する。
【００６０】
この許容発熱量は、部品間の許容最近接距離の決定に用いる。
【００６１】
また、この許容発熱量は、基板と雰囲気からの熱拡散の量と、部品の平均的な許容発熱量に基づいて、単位面積あたりどれだけの発熱が許されるかを見積もることにより、決定される。
【００６２】
ステップＳ１１−５では、配線長や熱分布を反映させた仮想的力の釣り合いにより部品の配置を決定する方法を取るため、以下の各処理ステップで使用する仮想的力を決定するためのパラメータを指定し、配線の弾性定数を決定する。
【００６３】
まず「引力」を決定する。
【００６４】
以下に、引力を決定する具体例を説明する。
【００６５】
配線長の短い配置を求めるための仮想的「引力」は、ｌｉｊを部品ｉ，ｊ間の配線長としたとき、弾性力を模擬して、次式のようなものとして決定することができる。
【００６６】
【数１】
0005018501.tif 000002
ステップＳ１１−５では、「弾性係数」ｋｉｊを決定することにより、弾性定数を決定する。
【００６７】
この場合、ｋｉｊは、部品を結ぶ配線の重要度を考慮して、例えば、重要配線はより短くなるように配線することによって、より強い「引力」となるようにする、というようなバイアスをかけることができるので、設計の品位を上げることができる。
【００６８】
次に「斥力」を決定する。
【００６９】
以下に、斥力を決定する具体例を説明する。
【００７０】
発熱量を分散させる効果を表す「斥力」は、例えば、電荷同士のクーロン力を参考にして、次式のように決定することができる。
【００７１】
【数２】
0005018501.tif 000003
ここで、ｒｉｊは部品ｉ，ｊ間の距離であり、Ｑｉは部品iの発熱量であり、ｈｉｊ，αは後述する予め決定される係数である。
【００７２】
但し、ｆ（ｒｉｊ，Ｑｊ×Ｑｊ）は、発熱量Ｑｊ，Ｑｊを持つ二つの部品がこれ以上近づけてはいけない最短距離ｒｉｊ＝α×Ｑｊ×Ｑｊを規定する力である。
【００７３】
ここで、ｒｉｊ＝α×Ｑｊ×Ｑｊによって力が無限大になるということは、ここに無限のエネルギーでも越えられない壁があることを意味している。
【００７４】
この力が存在しないと、部品が規定より小さい距離で近接するという結果が生じる可能性がある。
【００７５】
また、この最近接距離は、クラスター部品の縮約の操作で必要となる。
【００７６】
「斥力」の形状は、図５のように与えられる。
【００７７】
次に、ステップＳ１１−６では、発熱分布の平滑化のための「斥力」であるＦｈｅａｔを規定する係数ｈｉｊ，αを指定する。
【００７８】
具体的には、単位面積あたりの許容発熱量や、シミュレーションにより、最適な値を決定することで、より品位の高い設計を行うことができる。
【００７９】
ステップＳ１１−７では、配線処理を行う際の収束ステップの上限値を、収束条件として設定する。
【００８０】
ステップＳ１１−８では、基板面積と形状を指定する。
【００８１】
この値は、配置を決めるときの境界条件として用いられる。
【００８２】
以上により、指定された設計に必要な情報を記憶部２に入力することによって保存され、図３のフローチャートを終了し、図２のフローチャートのステップＳ１２に進む。
【００８３】
ステップＳ１２では、部品を基板上にランダムに配置し、それらを予め指定された接続関係に基づいて接続する。
【００８４】
ステップＳ１３では、位置計算決定部３が、発熱量と配線長に応じた部品間の力の計算を行う。
【００８５】
ステップＳ１４では、図６に示すように、二つの力ＦｈｅａｔとＦｌｅｎｇｔｈと力の釣り合いの計算し、配置を決める。
【００８６】
なお、この場合、部品の移動は９０度の回転も許すこととする。
【００８７】
すなわち、向きによって配線長が長くなっている場合があるので、その場合には向きを変えることにより、配線長の長さを低減させることができる。
【００８８】
次に、図７に示すフローチャートに基づいて、図２のステップＳ１５における配線の交差解消と部品のクラスター化処理について説明する。
【００８９】
図７に示す交差解消・部品クラスター化処理は、まずステップＳ１５−１において、配線クラス設定をｎ＝１とし、配線のクラス分けにおける最も重要な配線を含むクラスを指定する。
【００９０】
図７のステップＳ１５−２では、部品間配線部４が、そのクラスについて配線長を短くしながら、交差することのない配線を段階的に探索する。
【００９１】
ここで、配線長を目的関数としながら、交差をしない配線を見つける段階的アルゴリズムとしては、例えばタッチアンドクロス法が挙げられる。
【００９２】
次に、図７のステップＳ１５−３では、配線クラス管理部６が収束判定を行う。
【００９３】
すなわち、所定ステップ内で交差のない配線が収束した場合は、ｎ＝ｎ＋１として（ステップＳ１５−４）、配線クラスの優先順位が次に高い配線を加えて、ステップＳ１５−２に戻る。
【００９４】
そして、ステップＳ１５−２では、優先順位が次に高いそのクラス内で、配線について交差解消最短配線探索を行う。
【００９５】
そして、所定ステップ内で交差を解消できなかった場合や、もう収束することが無くなった場合には（ステップＳ１５−３）、次のステップＳ１５−５に進む。
【００９６】
ステップＳ１５−５では、交差を解消できなかった部品や、交差がなく配線が収束してしまった部品を１つのコアとして、部品のクラスター化を行う。
【００９７】
また、ステップＳ１５−６では、図８に示すように、交差が終了した現クラスｎの配線で結ばれた部品の集団を、交差を解消した配線が再び交わらないように、すなわちトポロジーを変えずに、熱的仮想的力で規定される最短距離ｒｉｊ＝α×Ｑｉ×Ｑｊまで接近させる。
【００９８】
このステップＳ１５−６の処理を、クラスターの縮約と呼ぶ。
【００９９】
そして、現クラスｎの配線で結ばれた部品の集団を、１つの部品と見なす。
【０１００】
この部品集団を、１つのクラスター部品と呼ぶ。
【０１０１】
このように、クラスター化したら、図２のステップＳ１６に進む。
【０１０２】
なお、上述のステップＳ１５−４において、ｎ＝ｎ＋１とした場合には、その都度、指定した配線クラスで再び配線を行う。
【０１０３】
以下、同様にして、配線が所定ステップで終わった場合には、配線クラスをｎ＝ｎ＋１として、次に高い優先順位の配線を加えて交差解消を行う。
【０１０４】
このように所定のステップ数で交差が解消できるまで、順次配線を加えながら、交差解消を行う。
【０１０５】
そして、所定ステップで交差解消が終わらない事態が起こったら、ステップＳ１５−３で収束判定をＮＯとして計算をやめ、クラスター化を行う次のステップＳ１５−５に進む。
【０１０６】
このように、図２のステップＳ１５において、交差解消・部品クラスター化処理が繰り返し行われ、終了すると、図２のステップＳ１６へ進む。
【０１０７】
図２のステップ１６では、部品が全てクラスター化されたか否かをチェックする。
【０１０８】
部品が全てクラスター化された場合には、ステップ１７に進み、配置配線を終了する。
【０１０９】
これに対し、部品にまだクラスター化されていない部分がある場合は、ステップ１４に戻る。
【０１１０】
なお、ステップＳ１６からステップＳ１４に戻ってきた場合には、ステップ１４では、クラスター部品と残りの部品で仮想的力の釣り合いを計算し、配置を調整する。
【０１１１】
ここで、クラスター部品の熱量は、構成部品の熱量の和とする。
【０１１２】
再び配線の交差が発生するので、再びステップ１５に進む。
【０１１３】
その後は、ステップＳ１５における交差解消・部品クラスター化処理のループを実行し、新たな部品クラスターを構成する。
【０１１４】
（３）実施形態１における部品配置配線装置の効果
本実施形態によれば、部品配置配線装置は、配置と配線を独立に行うのではなく、連動させて行っているので、効率的に解探索ができ、探索の速度を上げられると同時に、独立に探索した場合では見つからない配置配線を見つけることができる。
【０１１５】
また、部品配置配線装置は、発熱を規定以下に抑えながら、なるべく短い配線長と、小さな基板面積を持つような部品配置配線を、現実的な時間内で行うことができる。
【０１１６】
また、部品配置配線装置は、時間のかかる交差解消配線処理に対して、処理ステップに収束判定の上限値を設けているので、設計の時間を現実的なものに抑えることができると同時に、必要に応じて精度をあげることもできる。
【０１１７】
また、部品配置配線装置は、配線の上限ステップを時間短縮と同時にクラスター化のためにも利用しているので、作業を簡略化することができる。
【０１１８】
また、予め設定された何らかの視点でクラスター化を行うのではなく、配線を行いながらクラスター部品を決めるので、クラスター化のための恣意的な視点を必要としないため、作業が簡素化されている。
【０１１９】
また、部品配置配線装置は、配線をクラス分けし、それに応じて配線の重視の度合いを決めているので、クラス分けをＥＭＩ特性で分けることにより、低ＥＭＩの設計を行うことができる。
（４）実施形態１による部品配置配線装置の実施例
次に、図９から図１６の図面を用いて、本発明に係る部品配置配線装置における部品配置配線処理について、実施例を述べる。
【０１２０】
まず、図４（ａ）に示したように、配線クラスは、３クラスに分かれているとする。
【０１２１】
図４（ａ）では、重要な配線の優先順位により、重要なものから、極太、太、細の線で表している。
【０１２２】
このとき、クラス分けは、図４（ｂ）に示すように、下位のクラスがそれまでの上位の配線クラスの配線を全て含むように作る。
【０１２３】
次に、図９に示すように、部品をランダムに配置する。
【０１２４】
そして、図１０に示すように、予め指定された結合関係に従い、部品を任意につなぎ配線を施す。
【０１２５】
そして、図１１に示すように、部品の発熱量、配線の長さから、仮想的力の計算をし、釣り合いの位置を求める。
【０１２６】
そして、図１２に示すように、図４でＲａｎｋ１にクラス分けされた最重要配線について交差解消を行う。
【０１２７】
続いて、図４でＲａｎｋ２にクラス分けされた配線の交差解消を行い、所定ステップ内で終了しなかったとする。
【０１２８】
この場合、図１３に示すように、Ｒａｎｋ１の配線で結ばれた部品を縮約し、クラスター化する。
【０１２９】
そして、図１４に示すように、図１３でクラスター化されたクラスター部品と残りの部品とで釣り合いを計算し、配置を決める。
【０１３０】
そして、図１５に示すように、Ｒａｎｋ２の配線について交差の解消する配線を行う。
【０１３１】
続いて、図４でＲａｎｋ３にクラス分けされた配線の交差の解消を行い、所定ステップ内で終了しなかったとする。
【０１３２】
この場合、図１６に示すように、Ｒａｎｋ２の配線でつながれた部品を縮約し、クラスター化する。
【０１３３】
なお、実施形態１では、部品配置配線装置に係る条件入力部１が、本発明に係る条件入力手段を形成し、記憶部２と位置計算決定部３が、無作為配置配線手段を形成し、位置計算決定部３が、位置計算配置手段を形成している。
【０１３４】
また、実施形態１では、部品配置配線装置に係る部品間配線部４が、本発明に係る交差解消部品クラスター化手段を形成し、配線クラス管理部６が、部品判定手段を形成している。
【０１３５】
しかしながら、実施形態１は、これに限定されるものではなく、その他の構成によって本発明に係る部品配置配線装置、部品配置配線方法及び部品配置配線プログラムを形成するようにしても良い。
【産業上の利用可能性】
【０１３６】
本発明によれば、プリント配線板の設計やＬＳＩのレイアウト設計における部品・モジュール配置と配線を現実的な時間で行うという用途に適用できる。
【図面の簡単な説明】
【０１３７】
【図１】本発明に係る部品配置配線装置の構成を示す図である。
【図２】本発明に係る部品配置配線装置の部品配置配線処理の動作を示すフローチャートである。
【図３】本発明に係る部品配置配線装置の条件入力処理の動作を示すフローチャートである。
【図４】本発明に係る部品配置配線装置の配線のランク分け例を示した平面図である。
【図５】本発明に係る部品配置配線装置の発熱分布の均一な配置を得るために導入した仮想的斥力の距離依存性を表した図である。
【図６】本発明に係る部品配置配線装置の発熱分布の均一化を計る斥力と、配線長の短縮を計る引力との釣り合いの問題を示す図である。
【図７】本発明に係る部品配置配線装置の交差解消・部品クラスター化処理の動作を示すフローチャートである。
【図８】本発明に係る部品配置配線装置のクラスターの縮約例を示した図である。
【図９】本発明に係る部品配置配線装置のランダム配置を示した図である。
【図１０】本発明に係る部品配置配線装置の任意配線を示した図である。
【図１１】本発明に係る部品配置配線装置の釣り合い位置を計算して配置した場合を示した図である。
【図１２】本発明に係る部品配置配線装置の交差解消再配線を示した図である。
【図１３】本発明に係る部品配置配線装置のクラスター化と縮約を示した図である。
【図１４】本発明に係る部品配置配線装置の釣り合い位置を再計算して配置した場合を示した図である。
【図１５】本発明に係る部品配置配線装置の交差解消再配線を示した図である。
【図１６】本発明に係る部品配置配線装置のクラスター化と縮約を示した図である。
【符号の説明】
【０１３８】
１  条件入力部
２  記憶部
３  位置計算決定部
４  部品間配線部
５  クラスター化部
６  配線クラス管理部
７  クラスター部品管理部
【図１】
0005018501.tif 000004
【図２】
0005018501.tif 000005
【図３】
0005018501.tif 000006
【図４】
0005018501.tif 000007
【図５】
0005018501.tif 000008
【図６】
0005018501.tif 000009
【図７】
0005018501.tif 000010
【図８】
0005018501.tif 000011
【図９】
0005018501.tif 000012
【図１０】
0005018501.tif 000013
【図１１】
0005018501.tif 000014
【図１２】
0005018501.tif 000015
【図１３】
0005018501.tif 000016
【図１４】
0005018501.tif 000017
【図１５】
0005018501.tif 000018
【図１６】
0005018501.tif 000019