(57)【特許請求の範囲】
【請求項１】
回路図に含まれる素子列からなるブランチの並び順に従って素子を配置するＬＳＩ素子配置装置において、
前記回路図に含まれる所定数のブランチのデータを含む部分回路を、前記回路図の所定の端部側から順に抽出する部分回路データ抽出手段と、
部分回路データ抽出手段によって抽出された前記ブランチのデータに遺伝アルゴリズムを用いた素子配置操作を施して前記部分回路に含まれるブランチより少ない数のブランチの配置を演算により決定しながら、ブランチの配置座標データを順次記録していくことにより、前記ブランチのデータに含まれる全素子の配置座標データを含む素子配置結果を生成する素子配置手段と、を具備し、
前記部分回路データ抽出手段は、２回目以降の部分回路を読み出す場合には、前記素子配置手段で配置が未決定のブランチを含む部分回路を抽出することを特徴とするＬＳＩ素子配置装置。
【請求項２】
前記素子配置手段による前記素子配置結果に基づいて配置結果ファイルを作成する配置結果ファイル作成手段を更に具備することを特徴とする請求項１記載のＬＳＩ素子配置装置。
【請求項３】
所定の第１の正の整数ｍと、前記第１の正の整数より小さい第２の正の整数ｎとを予めセットするセット手段を更に具備し、
前記部分回路データ抽出手段は、前記ブランチのデータを最初に抽出する場合には、前記ブランチのデータを前記回路図の前記端部から連続してｍ個抽出する手段と、２回目以降は、１つ前に抽出されたブランチのデータのうち前記端部側からｎ個を除いたブランチのデータを含めて連続してｍ個のブランチのデータを抽出する手段と、最後の抽出において、ブランチのデータがｍ個未満である場合には、全てのデータを抽出する手段とを含み、
前記配置結果ファイル作成手段は、前記素子配置手段で生成された前記素子配置結果に含まれるブランチのデータのうちから前記端部に最も近く位置する連続するｎ個のブランチのデータに含まれる素子に関連する素子配置結果のみを記録する手段と、最後の回は、前記素子配置手段で生成された前記素子配置結果に含まれる全素子に関連する素子配置結果を記録する手段とを含むことを特徴とする請求項２記載のＬＳＩ素子配置装置。
【請求項４】
所定の第１の正の整数ｍと、前記第１の正の整数より小さい第２の正の整数ｎとを予めセットするセット手段を更に具備し、
前記部分回路データ抽出手段は、前記ブランチのデータを最初に抽出する場合には、前記ブランチのデータを前記回路図の前記端部から連続してｍ個抽出する手段と、２回目以降は、１つ前に抽出されたブランチのデータの前記端部側の次のｎ個のブランチのデータを抽出する手段と、最後の抽出において、ブランチのデータがｎ個未満である場合には、全てのデータを抽出する手段とを含み、
前記配置結果ファイル作成手段は、前記素子配置手段で生成された前記素子配置結果に含まれるブランチのデータのうちから前記端部に最も近く位置する連続するｎ個のブランチのデータに含まれる素子に関連する素子配置結果のみを記録する手段と、最後の回は、前記素子配置手段で生成された前記素子配置結果に含まれる全素子に関連する素子配置結果を記録する手段とを含むことを特徴とする請求項２記載のＬＳＩ素子配置装置。
【請求項５】
前記素子配置手段は、前記部分回路データ抽出手段で抽出された前記ブランチのデータを用いて、前記ブランチのデータに含まれる全素子の所定の第１座標の候補値からなる複数の解候補を含む解候補群を生成する解候補群生成手段と、前記解候補群に関連する全素子の前記第１座標に対応する第１座標軸に対して垂直な第２座標軸の第２座標を各解候補毎に決定する第２座標決定手段と、前記第２座標が決定された各解候補の解の適応度を評価する適応度評価手段と、解候補群の中から適応度の最も良い解候補を解として選定して、前記回路図に含まれるブランチに関連する素子配置結果を出力する近似最適解選定手段とを含むことを特徴とする請求項１乃至請求項４記載のＬＳＩ素子配置装置。
【請求項６】
前記解候補群生成手段は、前記適応度が評価された解候補群と関連する適応度とに基づいて、２つの解候補を選択する選択手段と、前記選択された２つの解候補間で、所定数の成分を互いに交換する交叉手段と、前記交換が施された解候補の所定数の成分に所定の算術的操作を施す突然変異手段とを含むことを特徴とする請求項５記載のＬＳＩ素子配置装置。
【請求項７】
前記解候補群生成手段は、前記部分回路データ抽出手段において抽出された前記ブランチのデータのうち、１つ前に行われた素子配置操作を行ったブランチのデータに関連する素子と重複するブランチのデータに関連する素子の前記第１座標の値をそのまま継承して当該解候補群を生成する手段を含むことを特徴とする請求項５記載のＬＳＩ素子配置装置。
【請求項８】
前記素子配置手段は、前記部分回路データ抽出手段で抽出された前記ブランチのデータを用いて、前記ブランチのデータに含まれる全素子の所定の第１座標の候補値からなる複数の解候補を含む解候補群を生成する解候補群生成手段と、前記解候補群に関連する全素子の前記第１座標に対応する第１座標軸に対して垂直な第２座標軸の第２座標を各解候補毎にコンパクション操作により決定する第２座標決定手段と、所定の確率に従い、前記解候補群の各解候補に対して、隣接する前記ブランチに含まれる素子のうち前記第１座標同士が近接する素子のペアを探索する探索手段と、前記近接する素子のペアが見つかった場合には、当該素子の第１座標値を同一値に調整する調整手段とを含むことを特徴とする請求項１乃至請求項４記載のＬＳＩ素子配置装置。
【請求項９】
前記調整手段は、調整後の第１座標値に対して、新たな解候補群に対する第１座標の調整を行うまで前記第１座標の値を保持する手段を含むことを特徴とする請求項８記載のＬＳＩ素子配置装置。
【請求項１０】
前記素子配置手段は、前記配置対象の部分回路に含まれる各素子に対応する第１座標の候補値を、前記１端からのブランチの並び順及びそのブランチ内の素子の並び順に従って並べてコーディングした数値列を前記解候補として設定する手段を含み、
前記選択手段は、前記解候補に関連する適応度に基づいて各解候補毎に決定された確率に従って行う手段を含み、
前記交叉手段は、ブランチ毎に、そのブランチが前記配置対象の部分回路データ抽出手段によって当該配置対象の部分回路に新たに加えられた順番に基づいて決定される交叉率に従って行う手段を含み、
前記突然変異手段は、ブランチ毎に、前記順番に基づいて決定される突然変異率に従って行う手段を含むことを特徴とする請求項１記載のＬＳＩ素子配置装置。
【請求項１１】
前記素子配置手段は、前記抽出手段で抽出された前記ブランチのデータを用いて、前記ブランチのデータに含まれる全素子の所定の第１座標の候補値からなる複数の第１解候補を含む第１解候補群を生成する初期解候補群生成手段と、前記各第１解候補毎に、少なくとも素子配置面積に関する第１コストと素子の位置関係に関する第２コストとを含む複数のコストをそれぞれ評価する評価手段と、前記第１解候補群から、前記各第１解候補毎に第１コストに基づいて所定の関数により選択確率を算出し、所定数より大きい複数の第２解候補の選択をして、前記第２解候補を含む第２解候補群を生成する第１生成手段と、前記第２解候補群から、前記各第２解候補毎に第２コストに基づいて所定の関数により選択確率を算出し、前記第１解候補の数より大きく前記第２解候補の数より小さい複数の第３解候補の選択をして、前記第３解候補を含む第３解候補群を生成する第２生成手段と、前記第２生成手段を、全てのコストについて最後の解候補群を生成するまで繰り返す手段とを含むことを特徴とする請求項１記載のＬＳＩ素子配置装置。
【請求項１２】
前記素子配置手段は、前記評価手段の実行前に前記第１解候補群に関連する全素子の第２座標を各第１解候補毎にコンパクション操作により決定する第２座標決定手段と、前記第３生成手段の実行後に、前記最後の解候補群に含まれる解候補の数の１／２組の解候補ペアを選択的に形成し、それぞれの前記解候補ペアをなす解候補間でいくつかの成分を互いに交換する交叉手段と、前記交換が施された前記各解候補の所定の成分に所定の算術的操作を施して、新しい解候補群を生成する突然変異手段と、前記突然変異手段で生成された新しい解候補群に対して、前記第２座標決定手段から突然変異手段を所定回数繰り返す手段とを更に含むことを特徴とする請求項１１記載のＬＳＩ素子配置装置。
【請求項１３】
前記評価手段は、素子の隣接性に関するコストと、素子面積に関するコストと、仮想配線長に関するコストとを更に含むコストを評価する手段を含むことを特徴とする請求項１１又は請求項１２記載のＬＳＩ素子配置装置。
【請求項１４】
前記第２座標決定手段は、コンパクション操作により、前記解候補に関連する各素子の第２座標を決定する手段を含むことを特徴とする請求項５記載のＬＳＩ素子配置装置。
【請求項１５】
前記セット手段でセットする前記第１の正の整数ｍ及び前記第２の正の整数ｎは、局所的に変動する値としてセットする手段を含むことを特徴とする請求項３又は請求項４記載のＬＳＩ素子配置装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、ＬＳＩ設計における素子の自動配置システムに関し、特に、回路図上の素子の位置関係が保存される素子配置方法及び素子配置装置に関する。
【０００２】
【従来の技術】
ＬＳＩ設計において、回路図（スケマティック）上の素子の位置関係をある程度保存した上で、全素子をいかに小さい面積の領域内に配置するかは非常に重要なポイントである。従来の手作業による素子配置はそのような高密度配置を実現するが、熟練と多くの作業時間が必要とされる。
【０００３】
そこで、近年、短時間で最適或いは近似最適な素子配置を実現すべく、自動素子配置装置の研究開発が活発化し、シミュレーテッド・アニーリング法等種々の自動素子配置方法が提案されている。例えば、佐々木、諏佐、“アナログ・セル生成における素子配置手法”、電子情報通信学会技術研究報告、ＶＬＤ９０−９４、１９９０年において、自動配置の手順が開示され、その他遺伝アルゴリズムを応用した多くの手法が提案されている。
【０００４】
遺伝アルゴリズムとは、生物の遺伝のメカニズムに着想を得て提案された確率的探索の１手法であり、初期解候補群の生成後、各解候補の適応度の評価、及び次期解候補群を生成するための選択・交叉・突然変異によって、新しい解候補群を逐次的に生成／評価して、より適応度の高い解候補を探索していくアルゴリズムとして知られている。
【０００５】
しかし、ＬＳＩにおける素子配置は回路に含まれる素子数が数千個〜数万個以上と膨大であるため、これらの自動配置システムでは全体的な回路構成を考慮した処理による素子配置の（近似）最適化は困難である。従って、従来では、回路全体を小さな配置対象の部分回路に分割し、その配置対象の部分回路毎に配置処理を行う方法を取っている。この方法は、例えば、回路全体を小さな配置対象の部分回路に分割し、回路図の左又は右から順に、配置対象の部分回路毎に配置処理を行うという方法である。回路全体をどのように配置対象の部分回路に分割するかは回路配置の最終結果に大きく影響するが、その分割方法は必ずしも確立されておらず、試行錯誤或いは経験的に把握したルールによっている。但し、回路図がそれぞれ独立の機能を持つ小さな部分回路からなっている場合は、分割方法が確立されている。更に、分割して得られる各々の配置対象の部分回路に対応する配置結果をいかに無駄なく接続し、回路全体に対する配置結果の性能を高めるかは、解決されていない。
【０００６】
従って、従来の自動配置システムが与える素子配置結果は、（近似）最適としては精度の低いレベルにあり、従来の手作業による設計に比較して必ずしも満足できるものではない。集積度の点で最終的には手作業による設計とほぼ同程度の結果が得られる手法もあるが、完全自動ではなく試行錯誤的操作を要し、解が得られるまでの処理に長時間を要する。
【０００７】
佐々木等は、素子の隣接性等の制約条件に関する評価値（以下、素子配置結果の評価値を「コスト」という）と、配置された素子が占める面積に関するコスト、或いは、素子間配線の配線長に関するコスト等を定義するための数種類の評価関数（以下、「コスト関数」という）とを導入し、コスト関数により算出されたコストをできるだけ最小化するような配置結果をシミュレーテッドアニーリング法を応用して求める手法を開示している。その際、佐々木等は、各コスト関数の重要度に応じた重み係数を乗じて総和を取り、１つのコスト関数として扱うという方法を採用している。
【０００８】
しかし、佐々木等は、各コスト関数に対して重要度に応じて順番を付けることは可能であっても、その重要度を重み係数として定量化する手法或いは指針は決して開示しておらず、もっぱら経験的に設定／修正しているのが実情である。
【０００９】
更に、遺伝アルゴリズムを適用した手法においては、１つの制約条件に関連するコスト関数に基づいて計算される適応度という評価値を用いるにとどまり、数種類の制約条件をいかに取り込むかが課題となっている。
【００１０】
上記のように、従来のＬＳＩの素子配置方法においては、各種制約条件に関連する数種類のコスト関数すべてに関して最適もしくは近似最適な配置結果を求めることができない。
【００１１】
配置結果の質を判断する１つの基準として、素子同士がなるべく横方向（すなわちｘ方向）に整列しているか否かがある。それは、素子が横方向に整列していた方が配線がしやすい、無駄な面積が少なくて済む、等の理由による。しかし、素子同士をなるべく横方向に整列する具体的な方法は開示されていない。
【００１２】
【発明が解決しようとする課題】
上記のように、従来のＬＳＩの素子配置方法においては、質の高い配置結果を得るには、多くの問題点を有する。
本発明の目的は、回路全体を考慮した高品質の素子配置結果を高速に与えるＬＳＩの素子配置方法及び装置を提供することである。
【００１３】
具体的には、
（ａ）  素子配置上の制約条件に関連するすべてのコスト関数に関して最適もしくは近似最適な配置結果を与えること、
（ｂ）  隣合う配置対象の部分回路の間の接続関係或いは位置関係等の相対的な関係を考慮しつつ、各配置対象の部分回路の素子配置に対して遺伝アルゴリズムを並列的に適用すること、
（ｃ）  横方向に隣合うことにより面積の縮小と配線のし易さに貢献するような素子のペアを、アルゴリズムの処理過程において、徐々に横方向に整列させ、横方向への整列性に優れた質の高い配置結果を効率よく求めること、
により、回路全体を考慮した高品質の素子配置結果を高速に与えるＬＳＩの素子配置方法及び装置を提供することを目的とする。
【００１４】
【課題を解決するための手段】
本発明は、上記の課題を解決するために次のような手段を講じた。
本発明の第１局面に係るＬＳＩの素子配置方法は、回路図に含まれる素子列からなるブランチの並び順に従って素子を配置するＬＳＩ素子配置方法において、前記回路図を入力し、記憶手段に記憶するステップと、前記記憶手段に記憶された前記回路図に含まれる所定数のブランチのデータを含む部分回路を、前記回路図の所定の端部側から順に前記記憶手段から読み出す第１のステップと、前記読み出された前記ブランチのデータに遺伝アルゴリズムを用いた素子配置操作を施して前記ブランチ内の素子配置を演算により求め、当該演算結果に基づいて前記部分回路に含まれるブランチ数より少ない数のブランチにおける素子配置座標データを決定する第２のステップと、前記第２のステップで素子配置が未決定のブランチと、前記記憶手段から読み出されて追加される素子配置が未決定のブランチとから次の部分回路を得る第３のステップとを含み、前記第２のステップと前記第３のステップとを繰り返してブランチの素子配置座標データを順次決定していくことを特徴とする。
【００１５】
本発明の第１局面に係るＬＳＩ素子配置装置は、回路図に含まれる素子列からなるブランチの並び順に従って素子を配置するＬＳＩ素子配置装置であって、前記回路図に含まれる所定数のブランチのデータを含む部分回路を、前記回路図の所定の端部側から順に抽出する部分回路データ抽出手段と、部分回路データ抽出手段によって抽出された前記ブランチのデータに遺伝アルゴリズムを用いた素子配置操作を施して前記部分回路に含まれるブランチより少ない数のブランチの配置を演算により決定しながら、ブランチの配置座標データを順次記録していくことにより、前記ブランチのデータに含まれる全素子の配置座標データを含む素子配置結果を生成する素子配置手段とを具備し、前記部分回路データ抽出手段は、２回目以降の部分回路を読み出す場合には、前記素子配置手段で配置が未決定のブランチを含む部分回路を抽出することを特徴とする
本発明の第１局面に係るＬＳＩの素子配置方法において、第２のステップは、前記第１のステップで抽出された前記ブランチのデータを用いて、前記ブランチのデータに含まれる全素子の所定の第１座標の候補値からなる複数の第１解候補を含む第１解候補群を生成する初期解候補群生成ステップと、前記各第１解候補毎に、少なくとも素子配置面積に関する第１コストと、素子の位置関係に関する第２コストと、を含む複数のコストをそれぞれ評価する評価ステップと、前記第１解候補群から、前記各第１解候補毎に第１コストに基づいて所定の関数により選択確率を算出し、所定数より大きい複数の第２解候補の選択をして、前記第２解候補を含む第２解候補群を生成する第１生成ステップと、前記第２解候補群から、前記各第２解候補毎に第２コストに基づいて所定の関数により選択確率を算出し、前記第１解候補の数より大きく前記第２解候補の数より小さい複数の第３解候補の選択をして、前記第３解候補を含む第３解候補群を生成する第２生成ステップと、前記第２生成ステップを、全てのコストについて最後の解候補群を生成するまで繰り返す第３生成ステップとを含むことを特徴とする。
【００１６】
本発明の第１局面に係るＬＳＩ素子配置装置において、前記素子配置手段は、前記抽出手段で抽出された前記ブランチのデータを用いて、前記ブランチのデータに含まれる全素子の所定の第１座標の候補値からなる複数の第１解候補を含む第１解候補群を生成する初期解候補群生成手段と、前記各第１解候補毎に、少なくとも素子配置面積に関する第１コストと素子の位置関係に関する第２コストとを含む複数のコストをそれぞれ評価する評価手段と、前記第１解候補群から、前記各第１解候補毎に第１コストに基づいて所定の関数により選択確率を算出し、所定数より大きい複数の第２解候補の選択をして、前記第２解候補を含む第２解候補群を生成する第１生成手段と、前記第２解候補群から、前記各第２解候補毎に第２コストに基づいて所定の関数により選択確率を算出し、前記第１解候補の数より大きく前記第２解候補の数より小さい複数の第３解候補の選択をして、前記第３解候補を含む第３解候補群を生成する第２生成手段と、前記第２生成手段を、全てのコストについて最後の解候補群を生成するまで繰り返す手段とを含むことを特徴とする。
【００１９】
本発明の第２局面に係るＬＳＩの素子配置方法は、第１局面に係る第２のステップが、前記第１のステップで抽出された前記ブランチのデータを用いて、前記ブランチのデータに含まれる全素子の所定の第１座標の候補値からなる複数の解候補を含む解候補群を生成する解候補群生成ステップと、前記解候補群に関連する全素子の前記第１座標に対応する第１座標軸に対して垂直な第２座標軸の第２座標を各解候補毎にコンパクション操作により決定する第２座標決定ステップと、所定の確率に従い、前記解候補群の各解候補に対して、隣接する前記ブランチに含まれる素子のうち前記第１座標同士が近接する素子のペアを探索する探索ステップと、前記近接する素子のペアが見つかった場合には、当該素子の第１座標値を同一値に調整する調整ステップとを含むことを特徴とする。
【００２０】
本発明の第２局面に係るＬＳＩの素子配置装置は、第１局面に係る素子配置手段が、前記部分回路データ抽出手段で抽出された前記ブランチのデータを用いて、前記ブランチのデータに含まれる全素子の所定の第１座標の候補値からなる複数の解候補を含む解候補群を生成する解候補群生成手段と、前記解候補群に関連する全素子の前記第１座標に対応する第１座標軸に対して垂直な第２座標軸の第２座標を各解候補毎にコンパクション操作により決定する第２座標決定手段と、所定の確率に従い、前記解候補群の各解候補に対して、隣接する前記ブランチに含まれる素子のうち前記第１座標同士が近接する素子のペアを探索する探索手段と、前記近接する素子のペアが見つかった場合には、当該素子の第１座標値を同一値に調整する調整手段とを含むことを特徴とする。
【００２１】
【作用】
上記手段を講じた結果、次のような作用が生じる。
本発明の第１局面に係るＬＳＩの素子配置方法及び装置によれば、回路全体を所定数（例えば、ｍ個）のブランチから構成される配置対象の部分回路に対して、ｍ個より少ない個数（例えば、（ｍ−ｎ）個）のブランチの重畳部分を持って素子を配置する。従って、本発明の第１局面に係るＬＳＩの素子配置方法及び装置によれば、局所的な最適化を連続して行うので、回路全体を考慮した素子配置が可能であり、更に、ブランチの特徴を生かした遺伝アルゴリズムを用いた素子配置方法と相俟って、例えば、配置された素子が占める面積をコスト関数に用いた場合は素子面積が高密度化された、質の高い素子配置結果を効率よく求めることができる。
【００２２】
上記のＬＳＩの素子配置方法及び装置によれば、最適化手法として遺伝アルゴリズムを採用し、各解候補毎のコストが評価された後の各世代における解候補の選択をする場合に、コスト関数をその重要度に応じた順番で適用することにより、解候補をふるいにかけて絞り込んでいくので、すべてのコスト関数に対して最適もしくは近似最適な解を効率よく求めることが可能となる。
【００２４】
本発明の第２局面に係るＬＳＩの素子配置方法及び装置によれば、ＬＳＩにおける素子の自動配置において、ブランチの特徴を生かした遺伝アルゴリズムを適用する際に、遺伝的操作の１つとして、各世代の各解候補のコード（染色体）に対して、予め指定された確率に従い、隣合うブランチ内でｙ座標が近接している素子のペアを探し、もしそのようなペアがあればその２素子のｙ座標を同一の値とするという操作を行う。この操作によって、横に隣合うことにより面積の縮小や配線のし易さ等に貢献するような素子のペアが徐々にｘ方向に整列していくので、最終的にｘ方向への整列性に優れた質の高い配置結果を効率良く求めることが可能となる。
【００２５】
【実施例】
図面参照して本発明の実施例を説明する。
図１は、本発明の第１実施例に係るＬＳＩ素子配置装置の概略構成を示すブロック図である。
【００２６】
概略的には、このＬＳＩ素子配置装置は、配置対象を入力し、入力した配置対象を記憶する図示しない記憶部を有する入力部１０と、記憶部にアクセスできる部分回路データ抽出部２０と、前記部分回路データ抽出部２０の後段に連結された素子配置部３０と、前記素子配置部３０の後段に連結された配置結果ファイル作成部４０と、前記配置結果ファイル作成部４０によって作成された配置結果ファイルの内容を出力する出力部５０とを具備する。
【００２７】
図１に示すＬＳＩ素子配置装置の動作を説明する。この場合において、素子配置対象として図２の回路図を例に用いる。
以下の説明において、「ブランチ」とは、回路図において、電源線とグランド線との間に連結されているいくつかの素子から形成される素子列のことをいう。このブランチが、自動素子配置において扱われる最小の単位となる。
【００２８】
例えば図２の回路図では、回路を曲線ｌ１〜ｌ６により分割して生成した第１ブランチＢ１〜第７ブランチＢ７が示されている。電源線６２とグランド線６４との間の電流路を形成する５個の素子Ｒ１−Ｑ１−Ｒ２−Ｑ２−Ｒ３からなる第１ブランチＢ１、グランドまで到達しないＲ４−Ｑ３−Ｒ５からなる第２ブランチＢ２、電源線−グランド線間パスにＲ１４が分岐接続されたＲ１３−Ｑ１０−Ｒ１４−Ｑ１１からなる第７ブランチＢ７等である。
【００２９】
図１のＬＳＩ素子配置装置の概略的な動作手順を説明する。図１に示すＬＳＩ素子配置装置は、回路図の左側の端のｍ個のブランチからなる配置対象の部分回路に基づいて詳細は後述する遺伝アルゴリズムを用いた手法により左側の端のｎ個（＜ｍ）のブランチに属する素子の配置座標を決定する。次に配置対象の部分回路をブランチｎ個分だけ右側にスライドして同様に次のｎ個のブランチに属する素子の配置座標を決定する。この動作を繰り返して、回路全体を配置対象の部分回路で走査することにより、全素子の配置を実施する。
【００３０】
具体的な動作手順を図３を参照して説明する。
素子のサイズや種類、ネットリスト、ブランチ情報等、配置の対象とする回路図に関するデータを入力部１０から読み込む（ステップＡ１）。この場合において、ブランチ情報は、予め設計者によって回路図にマニュアルで指定されても良いし、ステップＡ２以降において、部分回路データ抽出部２０で設定することもできる。
【００３１】
入力部１０を介してユーザは、本発明に係るＬＳＩの素子配置システムを用いて実施した図２の回路図の自動配置結果の一例を示す図４に外枠として示されている素子の配置可能領域６０の高さ（幅については特に指定しない）や詳細は後述するパラメータｍ、ｎ或いは素子配置部３０に関するパラメータ等を設定する（ステップＡ２）
次に、部分回路データ抽出部２０は、回路図の左側の端の所定数（この場合は、ｍ個）のブランチからなる回路を、配置対象の部分回路として決定する（ステップＡ３）。本実施例において、説明の便宜上、ｍ＝５とする。例えば、図２の回路では、第１ブランチＢ１〜第５ブランチＢ５からなる回路が配置対象の部分回路として決定される
前記部分回路データ抽出部２０は、ステップＡ３で決定された配置対象の部分回路に関連するデータを前記入力部１０から入力する（ステップＡ４）。
【００３２】
素子配置部３０は、ステップＡ４で抽出された配置対象の部分回路に関するデータに基づいて、詳述は後述する遺伝アルゴリズムを用いた素子配置方法により、配置対象の部分回路に含まれる全素子に対する自動配置を行う（ステップＡ５）。
【００３３】
配置結果ファイル作成部４０は、ステップＡ５により求められた解すなわち前記配置対象の部分回路に含まれる各素子の配置座標のうち、前記配置対象の部分回路の左側のｎ個のブランチに属する素子の配置座標のみが、最終的な配置座標として、配置結果ファイルに記録される（ステップＡ６）。
【００３４】
すなわち、本実施例において、ｎ＝２とすれば、図２の回路では、前記配置対象の部分回路を構成する第１ブランチＢ１〜第５ブランチＢ５のうちの第１ブランチＢ１に含まれる素子Ｒ１、Ｑ１、Ｒ２、Ｑ２、Ｒ３及び第２ブランチＢ２に含まれる素子Ｒ４、Ｑ３、Ｒ５の座標のみが、これらの素子の最終的な座標として決定される。第３ブランチＢ３〜第５ブランチＢ５に属する素子については、ここでは座標の決定はされない。
【００３５】
ステップＡ５の配置処理を一度も受けていない未処理ブランチが“０”でない場合はステップＡ４〜ステップＡ６が繰り返され、未処理ブランチ数が“０”である場合はステップＡ９に動作を移す（ステップＡ７）。
【００３６】
前記部分回路データ抽出部２０は、配置対象の部分回路からステップＡ６で座標が決定されたｎ個のブランチを除去し、残りの部分（すなわちステップＡ６で配置座標の決定がされずに保留された（ｍ−ｎ）個のブランチ）に、ステップＡ５の処理を未だ一度も受けていない未処理ブランチのうちの左からｎ個のブランチを付加して、これを新たなｍ個のブランチからなる配置対象の部分回路として決定する（ステップＡ８）。
【００３７】
ステップＡ８において、例えば、ステップＡ６で保留された第３ブランチＢ３〜第５ブランチＢ５に未処理ブランチである第６のブランチＢ６及び第７ブランチＢ７を付け加えて、第３ブランチＢ３〜第７ブランチＢ７の５個のブランチからなる新たな配置対象の部分回路を次の配置対象として決定する。
【００３８】
ステップＡ８の配置対象の部分回路更新からステップＡ６の素子の配置座標決定までのステップを繰り返し、この処理が一巡される毎に新たなｎ個分のブランチに属する素子の配置座標が決定されていく。
【００３９】
ステップＡ７において、未処理ブランチ数が“０”である場合、前記配置結果ファイル作成部４０は、直前でのステップＡ６で配置座標の決定がされずに保留された残りの全素子の配置座標を、最終的な配置座標として決定して、関連するデータを配置結果ファイルに記録する（ステップＡ９）。この手順により、配置対象の回路に含まれる全素子の配置座標が決定され、配置結果ファイルが完成される。
【００４０】
ステップＡ９において、例えば、図２では、２回目のステップＡ６において、このときの配置対象の部分回路に含まれる第３ブランチＢ３〜第７ブランチＢ７のうちの第３ブランチＢ３及び第４ブランチＢ４に含まれる素子の配置結果の座標が最終的な座標として決定され、第５ブランチＢ５〜第７ブランチＢ７の３個のブランチに含まれる素子の配置結果の座標は最終的な座標としての決定が保留されている。そして、その決定が保留された第５ブランチＢ５〜第７ブランチＢ７に含まれる素子の配置結果の座標が、このステップで最終的な配置座標として決定される。
【００４１】
出力部５０は、前記配置結果ファイルの内容を所定のデバイスに出力する（ステップＡ１０）。出力部５０は、モニター画面、プリンター、データ通信網或いは情報記憶媒体のいずれでもよい。
【００４２】
前記処理ループの所定数回目のループのステップＡ８すなわち最後のステップＡ８において、未処理ブランチの個数がｎでなく、新たな配置対象の部分回路に含まれるブランチ数がｍ個でないときは、以降の処理は当該個数をもって実施されるようにしてもよい。
【００４３】
ここで、入力部１０の記憶部に格納されているデータを用いて、ステップＡ２で設定するパラメータの一部或いは全部を変更して再実行させることも可能である。この場合、ステップＡ１は不要である。更に、前記パラメータｍ、ｎを、常に一定にするのではなく、回路図の特徴に応じて局所的に適宜変動させてもよい。
【００４４】
加えて、図３に示される第１実施例に関する動作は、一例であり適宜修正可能である。例えば、ステップＡ７をステップＡ６の前に持ってきて、条件が“Ｙｅｓ”の場合には、ステップＡ６とステップＡ９を合体した動作すなわちステップＡ５において与えられた全素子に関する配置結果の記録をするように構成しても同様の効果が得られる。
【００４５】
上記のように、本発明の第１実施例によれば、回路全体を配置対象の部分回路により重畳部分を持って走査しながら素子配置していくので、従来と異なり、局所的な最適化の連続という意味で回路全体を考慮して配置していくことができる。
【００４６】
図５は、素子配置部３０の概略構成を示す図である。
素子配置部３０は、配置対象の部分回路に関する初期解候補群生成部３１と、初期解候補群生成部３１の後段に連結されたＸ座標決定部３２と、前記Ｘ座標決定部３２に連結された適応度評価部３３と、前記適応度評価部３３に連結され前記Ｘ座標決定部３２にデータを与える解候補群更新部３４と、前記適応度評価部３３に連結され、最適解もしくは近似最適解を選定して出力する（近似）最適解選定部３５とを有する。前記解候補群更新部３４は、選択部３６と交叉部３７と突然変異部３８とを具備する。
【００４７】
素子配置部３０の動作説明に先立ち、以下の説明に用いる語句の定義を行う。「遺伝アルゴリズム」は、生物の遺伝のメカニズムに着想を得て提案された確率的探索の一手法であり、初期解候補群の生成後、各解候補の適応度の評価、及び次期解候補群を生成するための選択、交叉又は突然変異により、新しい解候補群を逐次的に生成／評価して、より適応度の高い解を探索していくアルゴリズムをいう。
【００４８】
「解候補」は、与えられた問題に対する解の候補であり、例えば、［１、０、０、０］或いは［Ａ、Ｂ、Ｃ、Ｄ］のような数列或いはデータ列からなる。第１実施例の場合は、配置すべき素子のｙ座標の候補値の数列である。具体的には、各解候補は、回路図に含まれる各素子の基準点（例えば素子の左下端の点）のｙ座標の候補値を、ブランチの回路図上での左側からの並び順、及びブランチ内での素子の回路図の下方からの並び順に従って並べてコーディングした数値列（解候補の染色体、又はコードと呼ぶ）で表される。ｙ座標には、配置可能領域の高さを複数等分（例えば５０等分）して得られる格子座標を用いる。以下では、素子の左下端の点を各素子の基準点とし、ｙ座標は０以上４９以下の整数を用いる。
【００４９】
「解候補群」は、解候補の集合である。
「初期解候補」は、解候補の初期値である。
「適応度」は、コスト等に基づいた所定の評価関数（以下、「適応度関数」という）により算出される解候補毎の解としての評価値である。適応度が大きいほど良い解候補である。適応度は各世代毎にその世代の解候補の間で相対的に定義しても良い。
【００５０】
「選択」は、適応度により決定される確率に基づいて、全解候補のうちから２つの解候補を選択することである。
「交叉」は、選択された２つの解候補の間で所定のルールに基づいて互いのいくつかの成分を交換することである。この交叉によって、新たな２つの解候補が生成される。
【００５１】
「突然変異」は、所定の確率に基づいてある解候補のある成分のみに所定の算術的操作を施すことである。この突然変異によって、初期解候補群により探索範囲が限定されてしまうことが回避される。
【００５２】
素子配置部３０の概略的な動作手順を説明する。
素子配置部３０は、複数個の解候補からなる初期世代の解候補群を後述の手法により生成し、その各々の解候補を評価し、この解候補群に基づいて、後述する手順により同数の新たな解候補群すなわち新世代の解候補群を生成し、その新世代の解候補群を評価し、それに基づいてさらなる新世代の解候補群を生成して、さらなる新世代の解候補群が評価されるというように、一定の条件が成立するまでそのような手順を繰り返し実行し、最終的に１つの解候補をこの素子配置問題の解として選定する。
【００５３】
素子配置部３０の遺伝アルゴリズムを用いた詳細な素子配置手順（すなわちステップＡ５）を、図６を参照して説明する。
初期解候補群生成部３１は、初期世代の解候補群を作成する（ステップＢ１）。但し、初期解候補群生成部３１は、初期世代の解候補群を作成する際に、初回と初回以外とでは異なる動作を実行するので、まず、初回の動作を説明する。
【００５４】
初回においては、部分回路データ抽出部２０は、抽出した前記配置対象の部分回路に関する素子のデータを初期解候補群生成部３１に初めて与える。初期解候補群生成部３１は、当該配置対象の部分回路に属するブランチの回路図上での左側からの並び順、更にはブランチ内での素子の回路図の下方からの並び順に従って、それら素子のｙ座標の候補値を並べて表現した解候補を所定数だけ生成する。このようにして生成された複数個の解候補からなる集合が初期世代の解候補群である。
【００５５】
図２を参照して上記の動作を具体的に説明する。
初期解候補群生成部３１は、最初に自動配置の対象となる第１ブランチＢ１〜第５ブランチＢ５からなる配置対象の部分回路の左に位置する第１ブランチＢ１内で下に位置する素子Ｒ１から上に位置する素子Ｒ３まで各々のｙ座標を昇順にランダムに発生させ（例えば１１、１４、２３、２８、３７）、以後第５ブランチＢ５まで同様の処理を行う。そして、初期解候補群生成部３１は、発生されたｙ座標の候補値を発生順にすべて連結して１つの解候補を生成する。
【００５６】
前述したように、発生させるｙ座標の値は、ここでは、０以上４９以下の整数を用いるが、予め配置可能領域をはみだすような場合を考慮して、例えば０以上４１以下の整数だけを用いることにしても良い（図２の例では、２以上のｙ座標値を持つ素子は配置可能領域をはみ出してしまう）。但し、このようにしても、例えば図２の素子Ｒ７のような高さの大きい素子の場合は、配置可能領域からはみ出してしまうことが有り得る。（実際、Ｒ７がとり得るｙ座標の値は０以上２８以下である）。そのような場合は、領域内にぎりぎりにおさまるように修正しても良い（例えば、Ｒ７に３５が割り当てられた場合は、２８に修正する）。
【００５７】
以下に初期解候補群生成部３１によって生成された解候補群の一例を示す。
0003556260.tif 000002
１つの解候補は、前記配置対象の部分回路に含まれる１９個の素子にそれぞれ対応する１９個のｙ座標の候補値を有し、この数列の左側からＲ１、Ｑ１、Ｒ２、Ｑ２、Ｒ３、Ｒ４、Ｑ３、Ｒ５、…というように対応している。セミコロンは、単にブランチの区切りを説明するために便宜上付した記号であり、解候補に含まれる文字データではない。
【００５８】
この場合において、ｙ座標の生成は、素子の配置可能領域６０の他に、各素子の種類、サイズ或いはデザインルール等を考慮した許容範囲以内で発生されたランダム値より実施されるようにしてもよい。
【００５９】
上記のようにして、初回における解候補群の生成が行われる。次に、初回以降の動作を説明する。
部分回路データ抽出部２０は、配置対象の部分回路をブランチｎ個分だけ右に移動して得られる新たな配置対象の部分回路に含まれる素子のデータを初期解候補群生成部３１に与える。初期解候補群生成部３１は、所定数の解候補からなる集合を初期世代の解候補群とする。
【００６０】
この場合において、初期解候補群生成部３１は、初回の動作のように関連するすべての素子に関してランダムに解候補群を生成するのではなく、現在対象としている配置対象の部分回路と前回対象とした配置対象の部分回路の間で重畳している（ｍ−ｎ）個のブランチに属する素子のｙ座標は、前回の自動素子配置ステップＡ５の最終回目で得られた解候補群におけるｙ座標の値をそのまま継承することによって解候補群を生成する。この値の継承は、同一番号を有する新旧の解候補の間で行われる。新しく追加されたｎ個のブランチの部分については、初回の動作と同様の手法でｙ座標の値を生成する。
【００６１】
以下、図２を用いて初期解候補群生成部３１の２回目以降の初期解候補群生成の動作を具体的に説明する。
２回目の配置対象の部分回路の初期解候補群を生成する場合、自動配置の対象となるのは第３ブランチＢ３〜第７ブランチＢ７からなる配置対象の部分回路であり、初回に自動配置の対象となったのは第１ブランチＢ１〜第５ブランチＢ５からなる配置対象の部分回路であるので、新旧の配置対象の部分回路間で重畳する３個のブランチは、第３ブランチＢ３〜第５ブランチＢ５である。従って、今回の解候補の第３ブランチＢ３〜第５ブランチＢ５の部分に含まれる素子のｙ座標の候補値については、初回の解候補の該当部分の値をそのまま継承し、新たに加えられた第６のブランチＢ６〜第７ブランチＢ７については、前述の初回の動作と同様の手法で生成する。
【００６２】
0003556260.tif 000003
となる。ここで、各解候補の上部の符号は該当するブランチを示す。
【００６３】
Ｘ座標決定部３２は、ステップＢ１では未定であった各素子のＸ座標をコンパクションによって決定する（ステップＢ２）。ここでは、コンパクション方法として、例えば、佐々木等の文献に記載されているような、いわゆる１次元コンパクションを用いて説明する。コンパクションは、当該配置対象の部分回路内の左側に位置するブランチから順次的に、ブランチ内で下に位置する素子から逐次的に、或いは左側の素子に接続を持つ素子を優先させて、素子を１つずつ−Ｘ方向すなわち水平に左の方向に移動して詰めるように配置する手法であり、コンパクトな配置面積を与えるＸ軸方向の配置手法である。なお、素子を左に平行移動した際に、上下に少しずらすだけで更に左に移動できる場合は、そのような移動を行うことによって、更にコンパクトな配置をすることが可能となる。
【００６４】
このコンパクションによって配置できる範囲は、前記配置結果ファイルに記憶されている配置済みの素子の座標、素子の配置可能領域及びデザインルール等により決定されてもよい。
【００６５】
コンパクションに関する制約として、移動中のブランチに属する素子は、１つ（又は２つ）前の既に配置されたブランチに属する最も左に位置する素子のＸ座標より左側にならない範囲で、左側に詰めるようにして配置するという条件を付加してもよい。この場合には、回路図上の素子の位置関係が良好に保存される。
【００６６】
適応度評価部３３により、所定の評価関数に従って、各解候補の適応度が算出される（ステップＢ３）。評価関数については、例えば、当該配置対象の部分回路に属する全素子のコンパクションの最右の素子（最も右側の領域を占めている素子）の右端の座標をコストとして考えると、この値は、各解候補の面積の大きさの１つの評価指標として評価関数に採用できる。そこで、例えば、解候補ｗの適応度ｆ（ｗ）を、
ｆ（ｗ）＝（現世代の全解候補の面積に関するコストの最大値）−（解放補ｗの面積に関するコスト）
のように定義してもよい。
【００６７】
面積に関するコストの他に、ブランチにおける素子の上下関係をなるべく保存するために用いるオーダーコスト等が必要であるが、それらについては第２実施例で詳述することにし、ここでは割愛する。
【００６８】
ステップＢ４において、処理ループ回数が図３のステップＡ２で設定された所定の回数以下であれば、ステップＢ５〜ステップＢ７を繰り返して新たな解候補群を生成する。
【００６９】
ステップＢ５において、選択部３６は、各解候補毎に適応度に基づいて決定される選択確率に従って、全解候補のうちから交叉すべき２つの解候補を選択し、選択された２つの解候補を、親１及び親２とする。
【００７０】
この場合において、例えば、解候補ｗの選択確率Ｐ（ｗ）を、
Ｐ（ｗ）＝ｆ（ｗ）／（全ｆの総和）
により与えてもよい。
【００７１】
選択の手法として実数区間［０，１）を、各解候補の選択確率に応じた数値範囲に分割し（例えば、［０，０．１）、［０．１，０．３）、…、［０．９７，１））、［０，１）間で一様に発生させた乱数が含まれる数値範囲に対応する解候補を選択するようにしても良い（例えば、乱数が０．１５ならば、第２番目の解候補を選択する）。
【００７２】
この場合には、所定の乱数により、まず解候補１が選択され、次に解候補４が選択されたとすると、次のように、解候補１が親１、解候補２が親２とされる。
0003556260.tif 000004
ステップＢ６において、交叉部３７は、選択された親１及び親２に対して互いの成分を交換する交叉を施し、新たな解候補である子１及び子２を生成する。
【００７３】
交叉は選択された２つの解候補に含まれる各ブランチ毎に以下のように実施される。
まず、ブランチ毎に予め設定された交叉率に従って、交叉が施されるか施されないかが決定される。ここで、各ブランチの交叉率は、例えば、０．２、０．２、０．５、０．５、０．８、のように、左に位置するブランチに対するものほど低い値であってもよい。
【００７４】
次に、交叉が施されることが決定したブランチ間でのみ交叉が実施される。
交叉には種々の方法があるが、一様交叉を施す場合を説明する。一様交叉は、“０”又は“１”を等しい確率で発生する手段を用いて、該当するブランチの素子数と等しい長さを有するマスクパターンを生成し、マスクパターン上の“１”を示す位置に対応する成分に関して、親１及び親２の間での交換を行う。
【００７５】
以下に、左から２番目のブランチ、４番目のブランチ、５番目のブランチに対して一様交叉が施される例を示す。このとき生成されたマスクパターンは、“０１０”、“１１０１”、“００１１”とする。
0003556260.tif 000005
突然変異部３８は、生成された子１及び子２に対してそれぞれ、突然変異操作すなわち算術的操作を施す（ステップＢ７）。
【００７６】
この突然変異は各解候補に含まれる各ブランチ毎に以下のように実施される。まず、ブランチ毎に予め設定された突然変異率に従って、突然変異が施されるか施されないかが決定される。各ブランチの突然変異は、交叉と同様に、０．１、０．１、０．３、０．３、０．５のように、左に位置するブランチに対するものほど低い値であってもよい。
【００７７】
次に、突然変異が施されることが決定したブランチにおいてのみ突然変異が実施される。
突然変異には種々の方法が考えられるが、ブランチ内からランダムに選んだ１つの成分の値に小さな値αを加えるという方法を用いても良い。ここではαは突然変異を行う都度、例えば｛＋３、＋２、＋１、−１、−２、−３｝の中からランダムに選択されるものとする。但し、この場合に、例えば＋３することによって配置可能領域をはみ出るような場合は、他の値の中から選択し直すことにする。
【００７８】
子１の左から３番目と５番目のブランチに対して突然変異が発生したときの例を示す（３番目のブランチに対しては、第１成分に−２を加え、５番目のブランチに対しては、第４成分に＋１を加えている）。
【００７９】
子１については、
0003556260.tif 000006
である。
【００８０】
突然変異率は初期値を与えて、世代を経る毎にその値を徐々に減少させ、最終世代では０に近い値となるように設定してもよい。
解候補の数と同数の子が生成されるまで、ステップＢ５〜ステップＢ７、すなわち選択、交叉及び突然変異を繰り返す。そして、子の集団を、新世代の解候補群とする（ステップＢ８）。
【００８１】
以上の新世代の解候補群の生成（所定回数のステップＢ５〜ステップＢ７のループ）、この解候補群に対するコンパクション（ステップＢ２）及びその適応度の評価（ステップＢ３）の処理ループが繰り返され、より良い解候補に収束されていく。
【００８２】
そして、処理ループ回数が図３のステップＡ２において設定された回数に達した場合、処理ループを脱出して、ステップＢ９に移る（ステップＢ４）。
ステップＢ９において、最適解選定部３５により、その最終世代の解候補のうちから適応度が最大すなわちコストが最小の解候補を最良の解として選定し、その解候補に関連するデータを出力する。
【００８３】
上記の動作において、図６のステップＢ４の後に、ステップＢ８からステップＢ５に制御が移る前に、適応度のスケーリングをしてもよい。スケーリングは決定された適応度を何らかの関数により拡大或いは縮小することである。スケーリングとして、
ｆ´＝ａｆ＋ｂ
とする線形スケーリングを用いてもよいし、
ｆ´＝ｆｋ
とするべき乗スケーリングを用いてもよい。
【００８４】
上記の第１実施例において、前記部分回路データ抽出部２０が、その都度、対象となる配置対象の部分回路に含まれる全ｍ個のブランチに関連するデータを抽出して前記素子配置部３０に与えているが、前記素子配置部３０が、その回に対象とする配置対象の部分回路に含まれるブランチに関連するデータのうち、次回に対象となる配置対象の部分回路との間で重畳する（ｍ−ｎ）個のブランチに関連する必要なデータを保持しておき、前記部分回路データ抽出部２０は、次回に対象となる配置対象の部分回路に新たに付け加えられるｎ個のブランチに関連するデータのみを抽出して前記素子配置部３０に与えても良い。
【００８５】
上記のように、第１実施例によれば、回路全体を配置対象の部分回路により重畳部分を持って走査しながら素子配置していくので、従来と異なり、局所的な最適化の連続という意味で回路全体を考慮した配置ができ、例えば、配置された素子が占める面積をコスト関数に用いた場合には、素子面積の高密度化を実現することができる。更に本発明によれば、配置対象の部分回路の自動素子配置にブランチの特徴を生かした遺伝アルゴリズムによる配置手法を用いているので、効率的な素子配置が可能となる。
【００８６】
以下、図面を参照しながら第２実施例を説明する。
第２実施例において、装置構成及び適用する回路例は第１実施例と同様であるので、図面と詳細な説明は省略する。
【００８７】
第２実施例の詳細な動作手順を、図７及び図８のフローチャートを用いて説明する。ここで、図３及び図６と同じ動作については同じ符号を付し、詳細な説明は省略する。
【００８８】
素子のサイズや種類、ネットリスト、ブランチ情報等、配置の対象とする回路図に関するデータを入力部１０から読み込む（ステップＡ１）。
入力部１０を介してユーザは、本発明に係るＬＳＩの素子配置システムを用いて実施した図２の回路図の自動配置結果の一例を示す図９に外枠として示されている素子の配置可能領域６０の高さや詳細は後述するパラメータａ、ｂ、ｎ或いは素子配置部３０に関するパラメータ等を設定する（ステップＡ２）
初期解候補群生成部３１は、初期世代の解候補群を作成する（ステップＢ１）。本第２実施例において生成された解候補群の例を以下に示す。
0003556260.tif 000007
１つの解候補は、第１実施例と同様に、前記配置対象の部分回路（本第２実施例では図２の回路全体を１つの部分回路とみなして説明する）に含まれる２５個の素子にそれぞれ対応する２５個のｙ座標の値を有し、この数列の左側からＲ１、Ｑ１、Ｒ２、Ｑ２、Ｒ３、Ｒ４、Ｑ３、Ｒ５、…というように対応している。ここで、各世代における解候補の個数ｎには、通常、３０〜１００の値を用いるのが効果的である。本第２実施例では、ｎ＝５０として説明する。
【００８９】
Ｘ座標決定部３２は、ステップＢ１では未定であった各素子のＸ座標を決定する（ステップＢ２）。
適応度評価部３３により、所定のコスト関数に従って、各解候補のコストが評価される（ステップＣ１）。コスト関数は、数種類のものを定義し、おのおのについて評価が実施される。
【００９０】
コストは各解候補の評価値であり、本第２実施例においては、値の小さい評価値を有するものほど良い解候補であるものと仮定して説明する。ここでは、コストの例として、素子の隣接性に関するコスト（以下、「ペアコスト」と称する）、配置面積に関するコスト、仮想配線長に関するコスト、及びブランチにおける素子の上下関係に関するコスト（以下、「オーダーコスト」と称する）の４種類のコストを用いて説明する。
【００９１】
ペアコストは、ステップＡ２において入力される素子の隣接性に関する制約条件によって計算される。素子の隣接性に関する制約条件とは、例えば、
１．素子Ｒ２と素子Ｒ４はなるべく隣接するように配置する
２．素子Ｑ８と素子Ｑ９はなるべく隣接するように配置する
というような条件であり、優先的に隣接させたい２素子に対して予め配置許容範囲を設定しておき、例えば、その許容範囲から外れた部分の面積を、その２素子に係わるコストとする。そして、すべての優先的に隣接させたい２素子に係わるコストを算出して総和を求め、その値をコストとする。
【００９２】
配置面積に関するコストは、第１実施例と同様である。
仮想配線長に関するコストは、例えば、ネット毎に、そのネットに関連する全端子を含む最小長方形の周囲の長さの１／２（但し、関連する全端子を含む最小図形が１線分の場合は、その長さ）と定義し、すべてのネットに対する総和をそのコストとする。
【００９３】
オーダーコストは、ブランチにおける素子の上下関係をなるべく保存するために用いられ、例えば、同じブランチ上で上下に隣合う２素子の基準点のｙ座標の大小関係が逆転している場合に、そのずれをコストとする。
【００９４】
コスト関数により算出されるコストには、それらの重要性に従って順位付けがされており、その順位は後述の選択操作において用いられる。ここでは、配置面積に関するコスト（コスト１とする）、仮想配線長に関するコスト（コスト２とする）、ペアコスト及びオーダーコスト（コスト３とする）の順に、重要性が高いものとする。ペアコストとオーダーコストの重要性は同程度と仮定する。
【００９５】
選択部３６により、解候補群に対して、各解候補の有するコストに基づいた確率を用いて選択操作が施される（ステップＣ２）。選択操作を図８を参照して説明する。
【００９６】
最も重要性の高いコスト１すなわち配置面積に関するコストを用いてａ個の解候補からなる集合Ａを生成する（ステップＤ１）。この場合において、ａ＞ｎとし、ここでは、ａ＝７０とする。
【００９７】
まず、各解候補毎に、その解候補のコスト１を用いて適応度を算出する。適応度については、例えば、解候補ｗの適応度ｆ（ｗ）を、
ｆ（ｗ）＝（現世代の全解候補のコスト１のうちのの最大値）−（解候補ｗのコスト１）
のように定義してもよい。
【００９８】
全ｎ個の解候補について適応度が算出されたら、この適応度に基づいて、各解候補が選択される確率を決定する。例えば、解候補ｗの選択確率Ｐ（ｗ）を、
Ｐ（ｗ）＝ｆ（ｗ）／（全ｆの総和）
により与えてもよい。
【００９９】
次に、解候補ｗの選択確率Ｐ（ｗ）を用いて、ｎ個の解候補のうちからａ個の解候補を選択する。この場合において、もとの解候補の集合の要素数ｎより、集合Ａの要素数ａの方が大きいので、集合Ａには必ず重複する解候補が存在する。
【０１００】
この選択の手法については、第１実施例の中で述べた選択の手法と同様の手法により、解候補を選択するようにしてもよい。そして、乱数をａ回発生させて、該当するａ個の解候補からなる集合Ａを生成する。
【０１０１】
２番目に重要性の高いコスト２すなわち仮想配線長に関するコストを用いて同様の操作を施して、ａ個の解候補からなる集合Ａから、ｂ個の解候補からなる集合Ｂを生成する（ステップＤ２）。ここで、ｂ＜ａ、かつ、ｂ＞ｎとし、この場合には、ｂ＝６０とする。
【０１０２】
コスト３すなわちペアコスト及びオーダーコストを用いて同様の操作を施す。このように重要度が同程度のコストが数種類ある場合は、それぞれのコストを、例えば、０以上１以下の実数値に換算して、その和をコスト３と考え、適応度を定義する。この適応度に基づく選択確率によって、ｂ個の解候補からなる集合Ｂから、ｎ個の解候補からなる集合Ｃを生成して、この選択操作を完了する（ステップＤ３）。そして、このｎ個の解候補を含む集合Ｃを、次の交叉操作のための親の集合Ｚとする。
【０１０３】
ここでは、前述のコスト１〜コスト３を用いて、交叉操作について説明したがコストが２種類の場合は、ステップＤ２を省けばよい。
重要性の異なるコストが４種類以上の場合は、ステップＤ２に該当するステップを適宜挿入すればよい。その際、前述の操作は高い重要性を有するコストから順に実施する。この場合、第ｓ番目に重要性の高いコストｓを用いて選択される解候補の数Ｕ（ｓ）は、
Ｕ（１）＞  …  Ｕ（ｓ−１）＞Ｕ（ｓ）＞Ｕ（ｓ＋１）  …  ＞ｎ
の関係を満たせばよい。
【０１０４】
また、予め相対的な重み付けが容易にできる複数のコストに対しては、それらを１つのコストとみなしても良い。例えば、ペアコストとオーダーコストの相対的な重み付けが４：３となるように与えることができる問題（配置対象）に対しては、まずそれぞれのコストを例えば０以上１以下の実数値に換算して、換算されたペアコストの４倍と、換算されたオーダーコストの３倍との和を１つのコストとみなしても良い。
【０１０５】
交叉部３７は、選択操作により生成された集合Ｚに含まれるｎ個の親すなわち解候補に対して互いの成分を交換する交叉を施し、新たな解候補であるｎ個の子を生成する（ステップＢ６）。
【０１０６】
まず、集合Ｚに含まれる親を２個ずつ組にして、ｎ／２組のペアを生成する。その際、どの親同士をペアにするかは任意或いはランダムとする。これら親のペアを、
（親１、親２）、（親３、親４）、…、（親ｎ−１、親ｎ）
で表す。第２実施例ではｎ＝５０としたので、２５組の親のペアすなわち
（親１、親２）…（親４９、親５０）
が生成される。
【０１０７】
次に、各親のペアに対して第１実施例と同様に、予め設定された交叉率に基づいて、交叉操作を行う。
上記のようにして、各親のペアから２個の子を生成し、合計ｎ個の子が生成される。第２実施例では、子１〜子５０が生成される。
【０１０８】
突然変異部３８は、交叉が施されて生成されたｎ個の子に対して、第１実施例と同様に、突然変異操作を施す（ステップＢ７）。
ステップＢ２からステップＢ７に至る一連の操作からなる処理ループの繰り返し回数が所定の回数に達したかを判断し、達しない場合はステップＢ２のコンパクションに移って処理ループを繰り返し、達した場合にはステップＣ３の終了処理に移る（ステップＢ４）。
【０１０９】
上記処理ループが一巡する毎に新しい解候補群が生成され、より良い解候補が探索されて、最適解もしくは近似最適解に収束していく。
終了処理を施す（ステップＣ３）。具体的には、ステップＢ２からステップＣ２までの操作と同一の操作を実施し、選択操作によって得られるｎ個の解候補の中から最小のコストを有する解候補を解として選定する。
【０１１０】
出力部５０は、前記配置結果ファイルの内容を所定のデバイスに出力する（ステップＡ１０）。
上記のように、本発明の第２実施例によれば、最適化手法として遺伝アルゴリズムを採用し、各世代における解候補の選択の際にコスト関数をその重要度に応じた順番で適用することにより、解候補をふるいにかけて絞り込む手法を用いるので、すべてのコスト関数に関し最適もしくは近似最適な解を効率よく求めることが可能となる。
【０１１１】
図９には、本発明に係るＬＳＩの素子配置システムを用いて実施した図２の回路図の自動配置結果の一例を示す。
以下、図面を参照しながら第３実施例を説明する。
【０１１２】
第３実施例において、装置構成及び適用する回路例は第１実施例と同様であるので、図面と詳細な説明は省略する。
図１０は本発明の第３実施例の概略動作を示すフローチャートであり、図１１は図１０のフローチャートの中の遺伝アルゴリズムの概略を示すフローチャートであり、基本的には、図６と同じ動作を示す。図１２は図１０のフローチャートを用いた図２の回路図に対する１つの配置結果を示す図である。
【０１１３】
以下、図１０及び図１１を参照して第３実施例の概略動作を説明する。
素子のサイズや種類、ネットリスト、ブランチ情報等、配置の対象とする回路図に関するデータ、素子配置部３０に関すパラメータ、及びステップＥ５で用いる終了条件等を入力する（ステップＥ１）。終了条件は、本実施例においては、ステップＥ３に示すように、任意の配置対象の部分回路に対する遺伝アルゴリズムの世代数の合計が総世代数ｋ以下か否かであるとする。
【０１１４】
全体の回路図を複数個のブランチから成る配置対象の部分回路に分割する（ステップＥ２）。以下の説明では、簡単のため配置対象の部分回路は全て３ブランチから成るとする。従って図２の回路では、（Ｒ１、Ｑ１、Ｒ２、Ｑ２、Ｒ３）、（Ｒ４、Ｑ３、Ｒ５）、（Ｒ６、Ｑ４、Ｒ７）の３ブランチ、（Ｒ８、Ｑ５、Ｒ９、Ｑ６）、（Ｒ１０、Ｑ７、Ｑ８、Ｒ１１）、（Ｑ９、Ｒ１２）の３ブランチ及び、（Ｒ１３、Ｑ１０、Ｒ１４、Ｑ１１）から始まる３ブランチ、の３つの配置対象の部分回路に分割する。３番目の配置対象の部分回路については一般性を失わずに、（Ｒ１３、Ｑ１０、Ｒ１４、Ｑ１１）の右側にも回路が続いているものとして、３ブランチから成るものと仮定する。最右端の配置対象の部分回路については１又は２ブランチから成ることがあるが、そのような例外的なケースについて述べることは本質的ではないのでここでは省略する。
【０１１５】
上記のようにして分割された各配置対象の部分回路に対して、それぞれ、遺伝アルゴリズムが起動され、図１１の概略フローチャートに従って配置改善を行う（ステップＥ３）。ステップＥ３における遺伝アルゴリズムは配置対象の部分回路の総数（ｑとする）だけあり、それぞれ別個のプロセッサで並列に実行される。尚、各遺伝アルゴリズムは予め指定された数ｊだけ世代交代を行う。ここではｊ＝１０とする。図１１に示す遺伝アルゴリズムの処理の具体的な説明は後述する。
【０１１６】
第３実施例は、各遺伝アルゴリズムをそれぞれ別個に実行する間に、例えば、ｊ＝１０世代毎に隣の部分回路の配置結果の情報を参照する実施例である。これによって、回路全体の配置の性能を考慮することを目的とする。すなわち、
（ｉ）各部分回路に対して、それぞれ遺伝アルゴリズムをｊ＝１０世代実行する（ステップＥ３）。
（ｉｉ）各部分回路に対する最後の世代（すなわち１０ｘｉ  世代目、但し、ｉ＝１、２、…）の最良の配置結果をそれぞれ共有メモリにコピーする（ステップＥ４）。ここで、コピーとは、以前のデータに新しいデータを上書きするという操作である。
上記のステップＥ３及びステップＥ４を最後の世代が総世代になるまで繰り返す（ステップＥ５）。すなわち、ステップＥ５では、最後の世代が総世代数ｋ以下か否かを判定し、もし総世代数ｋ以下ならばステップＥ３へ、さもなくば、ステップＥ６の出力へと進む（ステップＥ５）。ここではｋ＝ｊ×１００＝１０×１００＝１０００とする。つまりステップＥ３からステップＥ５に至るループは計１００回繰り返されることになる。
【０１１７】
ステップＥ３の遺伝アルゴリズムがステップＥ５に続く処理として実行される場合は、ｉ番目（２≦ｉ≦ｑ）の配置対象の部分回路に対する遺伝アルゴリズムは、共有メモリにコピーされている（ｉ−１）番目の配置対象の部分回路の配置結果の情報を参照する。
【０１１８】
ステップＥ５の判定がＮＯの場合は、その時点の各配置対象の部分回路に対する最良解、即ち、共有メモリに最後にコピーされた各配置対象の部分回路に対する配置結果の情報をそれぞれ出力する（ステップＥ６）。これによって回路の全ての素子に対する最終的な配置座標が決定される。
【０１１９】
ステップＥ３の遺伝アルゴリズムについて図１１の概略フローに従って説明する。以下の説明において、第１実施例と全く同じ動作内容については、詳細な説明は省略する。
【０１２０】
ステップＥ３は、ステップＥ２で決定される配置対象の部分回路の総数ｑだけあり、それぞれが図１１の概略フローに従って第３実施例では並列に実行されることを特徴とする。
【０１２１】
第１実施例と同様に、配置対象の部分回路に属す各ブランチ毎に素子の並び順に従い、そのｙ座標を並べて表現した複数個の解候補から成る初期世代を生成する（ステップＢ１）。
【０１２２】
ステップＢ１の初期世代生成は、ステップＥ３の処理が初めて適用されるときだけ必要となるものであり、２回目以降のステップＥ３〜Ｅ５の処理ループにおいては使用されない。
【０１２３】
各解候補に対してｘ座標を決定するために第１実施例と同様のコンパクションを行う（ステップＢ２）。この場合において、本第３実施例では、１番目の配置対象の部分回路に属するブランチのコンパクションに関しては、図１２のように配置領域の左縁を越えてはならないという条件を付加する。２番目以降の配置対象の部分回路のブランチのコンパクションについては、ステップＥ３の処理が初めて適用されるときは前記の１番目の配置対象の部分回路に対する場合と同様の条件を付加し、ステップＥ５の処理の後、再びステップＥ３の処理が適用される場合は、共有メモリにコピーされている左隣の配置対象の部分回路、すなわち（ｉ−１）番目の配置対象の部分回路の配置結果に対して素子をコンパクションで詰めていく。
【０１２４】
所定のコスト関数から定義される適応度関数に従って、第１実施例又は第２実施例と同様に、各解候補の適応度が算出される（ステップＢ３）。第３実施例においては、仮想配線長に関するコスト、配置面積に関するコスト、オーダーコスト、ペアコスト等を、例えば各コストに重みを付けて和をとり、その総和を解候補のコストとする。
【０１２５】
コストは小さいほど良いので例えば、解候補ｗの適応度ｆ（ｗ）を、
ｆ（ｗ）＝（現世代の全解候補のコストのうちの最大値）−（解候補ｗのコスト）
のように定義する。ｉ（ｉ≧２）番目の配置対象の部分回路に対するコスト計算の際に、ｉ番目と（ｉ−１）番目の配置対象の部分回路間の接続関係によるコストも考慮することとする。例えば、仮想配線長に関しては、ｉ番目と（ｉ−１）番目の配置対象の部分回路を接続しているネットの長さも加算することとする。ここで参照する（ｉ−１）番目の配置対象の部分回路の配置結果の情報は、共有メモリにコピーされているものを使用する。
【０１２６】
以下、ステップＢ５〜ステップＢ８を繰り返して新たな解候補群を生成する。ステップＢ３で算出された適応度に基づいて決定される選択確率に従って、全解候補の中から交叉すべき２つの解候補を選択する（ステップＢ５）。
【０１２７】
ステップＢ５で選択された親１、親２に対して予め設定された交叉率に基づいて交叉を施し、子を２つ生成する。それらの子を子１、子２とする（ステップＢ６）。
【０１２８】
ステップＢ６で生成された子１、子２に対してそれぞれ、予め設定された突然変異率に基づいて突然変異を施す（ステップＢ７）。
解候補の数と同数の子が生成されるまで、ステップＢ５〜ステップＢ７すなわち選択・交叉・突然変異を繰り返す（ステップＢ８）。子の集団を、新世代の解候補群とする。
【０１２９】
ステップＢ３、Ｂ５、Ｂ６及びＢ７を第２実施例のステップＣ１、Ｃ２、Ｂ６及びＢ７に置き換えて、ステップＢ４の判断操作を選択操作の後に位置させても良い。
【０１３０】
以上の新世代の解候補群の生成、この解候補群に対するコンパクション及びその適応度の評価の処理ループ（世代）がｊ回繰り返され、より良い解候補に収束されていく。そして、現在対象としているｉ番目の配置対象の部分回路に対する世代数の合計、すなわちステップＥ３の処理が初めてｉ番目の配置対象の部分回路に適用されてからの処理ループ回数の合計が前述の指定数ｊの倍数、即ちｊ、２ｊ、３ｊ、…、１００ｊの何れかに達した場合、処理ループを脱出して、ステップＢ９の処理に移る。ステップＢ４ではそのための判定を行う。
【０１３１】
ステップＢ９では、そこまでのｊ回の処理ループの最後の世代の適応度最大の、即ちコスト最小の解候補を最良解とし、その解候補に関するデータを出力する。
【０１３２】
上記のステップＥ３の遺伝アルゴリズムが全ての配置対象の部分回路に対して並列に実行される。
上記のように、第３実施例によれば、回路全体を複数個のブランチからなる配置対象の部分回路に分割し、それぞれの配置対象の部分回路の素子配置に対しては直前の配置対象の部分回路の、予め指定された世代数ｊ毎の最良解の配置結果の情報をも参照することによって、隣合う配置対象の部分回路の間の相対的な関係を考慮しつつ、各配置対象の部分回路の素子配置に対して遺伝アルゴリズムを並列的に適用するので、回路全体を考慮した質の高い配置結果を高速に求めることが可能となる。
【０１３３】
以下、図面を参照しながら第４実施例を説明する。
第４実施例において、装置構成及び適用する回路例は第１実施例と同様であるので、図面と詳細な説明は省略する。
【０１３４】
図１３は本発明の第４実施例の動作を示すフローチャートであり、図１４は図１３のフローチャートの中のｙ座標の調整の概略を示すフローチャートであり、図１５は図１３のフローチャートを用いた、図２の回路図に対する１つの配置結果の例を示す図である。
【０１３５】
第４実施例の動作を図１３及び図１４を参照して説明する。図１３において図３及び図６と同じ動作には同じ符号を付し、詳細な説明は省略する。
素子のサイズや種類、ネットリスト、ブランチ情報等、配置の対象とする回路図に関するデータや素子配置部３０に関するパラメータ及びステップＦで用いるパラメータ等を、第１実施例と同様に、入力部１０から読み込む（ステップＡ１）。
【０１３６】
第１実施例と同様に、配置対象の回路図に属する各ブランチ毎に、素子の並び順に従い、そのｙ座標を並べて表現した複数の解候補からなる初期世代を生成する（ステップＢ１）。
【０１３７】
第１実施例と同様に、各解候補に対してｘ座標を決定するためにコンパクションを行う（ステップＢ２）。
所定のコスト関数から定義される適応度関数に従って、第１実施例と同様に、各解候補に対する適応度が算出される（ステップＢ３）。コスト関数については、第１〜第３実施例と同様である。
【０１３８】
以下、ステップＢ５〜ステップＢ８を繰り返して新たな解候補群を生成する。ステップＢ５〜ステップＢ８（ステップＦを除く）は、第１実施例と同じであるので、詳細な説明は省略する。
【０１３９】
ステップＢ３で算出された適応度に基づいて決定される選択確率に従って、全解候補の中から交叉すべき２つの解候補（親１、親２）を選択する（ステップＢ５）。
【０１４０】
ステップＢ５で選択された親１、親２に対して予め設定された交叉率に従って交叉を施し、子１及び子２を生成する（ステップＢ６）。
ステップＢ６で生成された子１、子２に対してそれぞれ、予め指定された突然変異率によって突然変異が施され、子１’、子２’が生成される（ステップＢ７）。
【０１４１】
ステップＢ７で生成された子１’、子２’に対してそれぞれ、予め指定された確率δに従い、隣合うブランチ内でｙ座標が近接している素子のペアを探し、もしそのようなペアがあればその２素子のｙ座標を同一の値とする（ｙ座標調整する）、という操作を行う（ステップＦ）。
【０１４２】
解候補の数と同数の子が生成されるまで、ステップＢ５〜ステップＦすなわち選択・交叉・突然変異・ｙ座標調整を繰り返す（ステップＢ８）。子の集団を、新世代の解候補群とする。
【０１４３】
以上の新世代の解候補群の生成、この解候補群に対するコンパクション及びその適応度の計算の処理ループ（世代）が予め設定された世代数だけ繰り返され、より良い解候補に収束されていく。ここでこの処理ループの脱出条件として、「予め設定された世代数に達した場合」という条件の他に、「全ての個体が同じ適応度を持った場合」という条件を付加してもよい。
【０１４４】
最終世代における最良解の配置結果の情報、即ち各素子の配置座標を出力する（ステップＢ９）。
以下、図１４に従ってステップＦのｙ座標の調整につき具体的に説明する。
【０１４５】
ループ回数として用いるパラメータｉの値を１に設定する（ステップＦ１）。
０以上１以下の実数の一様乱数値ｒを発生させる（ステップＦ２）。
ｒが、予め指定されたｙ座標調整に関する確率δよりも小さい場合はステップＦ４へ、さもなくば、ステップＦ６へ進む（ステップＦ３）。この場合において、例えば、ｒ＝０．４、δ＝０．７ならばステップＦ４に進む。δの値は図１３の遺伝アルゴリズムの全世代に亙って定数としても良いし、或いは世代が進む毎に少しずつ増大させていく等、動的に変化させても良い。増大させると、一般に、後半の世代に行くほどｘ方向の整列度の度合いが高まることになる。
【０１４６】
ｉ番目と（ｉ＋１）番目のブランチのコードを比較してｙ座標の差の絶対値が１以上ｐ以下であるペアｙ（ｉ，ｋ）、ｙ（ｉ＋１，ｈ）を１組探す。複数組あるときはランダムに１組を選択する（ステップＦ４）。
【０１４７】
ここで、ｙ（ｊ，ｍ）はｊ番目のブランチのｍ番目の要素を意味する記号である。ｐの値はｙ座標の近接の度合いを反映し、本実施例では、ｐ＝２として説明する。即ち、
｜ｙ（ｉ，ｋ）−ｙ（ｉ＋１，ｈ）｜＝１又は＝２
であれば、ｉ番目のブランチのｋ番目の素子と、（ｉ＋１）番目のブランチのｈ番目の素子が近接していると判断する。
【０１４８】
例えば、ｉ＝１のとき、子１’において１番目のブランチのコードが、
０  １０  １５  ２７  ３７
であり、２番目のブランチのコードが
０  ２６  ３０
である場合に、１番目と２番目のブランチのコードを比較すると、｜ｙ（１，４）−ｙ（２，２）｜＝｜２７−２６｜＝１であるので、１番目のブランチの４番目の素子と、２番目のブランチの２番目の素子は近接していることが分かる。
【０１４９】
上記のような近接ペアｙ（ｉ、ｋ）、ｙ（ｉ＋１、ｈ）の探し方は、例えば、ｉ番目のブランチの要素ｙ（ｉ、ａ）と（ｉ＋１）番目のブランチの要素ｙ（ｉ＋１、ｂ）をランダムに選択し、それら２要素の差の絶対値が１以上ｐ以下であるか否かという条件をチェックする、という操作を例えば高々１０回繰り返し、その途中過程で１組でも条件を満たすものがあれば、そのペアを近接ペアとして採用する、という方法を採用しても良い。或いは、チェック時間は増えるが、考え得る全てのペアをチェックして、条件に合うペアを１つ選択するという方法を採用しても良い。
【０１５０】
ステップＦ４において近接しているペアｙ（ｉ，ｋ）、ｙ（ｉ＋１，ｈ）が探索された場合は、それらのうちの一方の値を他方にコピー（上書き）する（ステップＦ５）。即ち、
（ａ）ｙ（ｉ，ｋ）の値をｙ（ｉ＋１，ｈ）にコピーするか、又は
（ｂ）ｙ（ｉ＋１，ｈ）の値をｙ（ｉ，ｋ）にコピーする。
（ａ）、（ｂ）のどちらを実行するかはランダムとする。例えばステップＦ４の説明で用いたペアｙ（１，４）、ｙ（２，２）に対して、（ａ）を実行すると、子１’の２番目のブランチのコードは
０  ２７  ３０
となり、１番目のブランチの４番目の素子と、２番目のブランチの２番目の素子が、互いの基準点が同一の水平線（ｙ＝２７）上に位置しているという意味で、横に隣合うことになる。
【０１５１】
上記のようにして、ｙ座標調整の対象になった２個の素子のｙ座標の値は、ステップＦ２〜ステップＦ７のループを抜けでるまでは、再び変更されることはないものとする。従って、上記の（ａ）、（ｂ）の選択の例外として、もしｙ（ｉ、ｋ）が値の変更を許されていない場合は、（ａ）を選択することになる。
【０１５２】
このように、一旦ｙ座標調整の対象となった２素子のｙ座標は、ｉがブランチの総数未満の間は、再変更しないことにより、例えば隣合うブランチのコードが
０  ２５  ４０；    ０  ２６  ３６；    ５  ２６
の場合、まず「ｉ＝１の時」２番目のブランチの２番目の値が一旦２５に調整され、次に「ｉ＝２の時」再びその値が２６に戻るという無駄な操作は回避されることになる。例えば、次のようにブランチのコードが変化する。
０  ２５  ４０；    ０  ２６  ３６；    ５  ２６    （ｉ＝１；（ａ）を実行）
→  ０  ２５  ４０；    ０  ２５  ３６；    ５  ２６    （ｉ＝２；（ｂ）を実行）
→  ０  ２５  ４０；    ０  ２６  ３６；    ５  ２６
ステップＦ４において近接しているペアが探索されなかった場合は、ステップＦ５においては何も実行しない。
【０１５３】
パラメータｉの値に１を加える（ステップＦ６）。
以上のステップＦ２〜ステップＦ６の操作を、（ブランチの総数−１）回繰り返す（ステップＦ７）。図２の例では７−１＝６回繰り返す。
【０１５４】
図１４に記載の方法では、パラメータｉを初期値１から１ずつ増加させることにより、ブランチの左側から順次、ｙ座標調整を施しているが、それとは逆に、ｉの初期値を（ブランチの総数−１）として１ずつ減少させることによって、ブランチの右側から順次、ｙ座標調整を施すという方法を用いても良い。更には、１以上、（ブランチの総数−１）以下のｉの値をランダムに「ブランチの総数×δ」個選び、ステップＦ４、ステップＦ５の操作を行うという方法を用いても良い。
【０１５５】
上記のように、第４実施例によれば、ブランチの特徴を生かした遺伝アルゴリズムを適用する際に、遺伝的操作の１つとして、ｙ座標の調整を行うことにより、横に隣合うことによって面積の縮小と配線のし易さを増すような素子のペアが徐々にｘ方向に整列していくので、最終的にｘ方向への整列性に優れた質の高い配置結果を効率よく求めることが可能となる。
【０１５６】
本発明は上述した実施例に限定されない。
実施例においては、左側のブランチに属する素子から順に配置する場合について説明したが、もちろんその反対に右側から配置する場合でも、本発明は同様に適用でき、同様の効果が得られる。
【０１５７】
図７において、ステップＢ４の判断操作をステップＣ２の選択操作とステップＢ６の交叉操作との間に移動し、ステップＣ３の終了処理を最良解の選定処理とし、ステップＢ４の判断操作における所定回数を１増加しても、等価なフローチャートとなる。
【０１５８】
図６、図７、図１１及び図１３で用いた遺伝アルゴリズムの手法は非常に基本的なものであり、他の種々の遺伝アルゴリズムの手法が適用可能である。例えば前世代の最良解を無条件で次世代に残すというエリート戦略や、初期の世代で局所解に陥ることを防ぐためのスケーリングや期待値戦略などの各種の技法を盛り込めることは勿論のことである。第１〜第４実施例では新しい世代を生成する際に親の数（例えば５０）から、親と同数（５０）の子を生成し、そうして得られた子の集団を新世代の解候補群としているが、この方法の代わりに子を例えば２０個生成し、それらを親の集団に追加して得られる７０個の解候補からなる集団から適応度の高い順に５０個の個体を選出し、それらを新世代の解候補群としてもよいことは勿論のことである。
【０１５９】
また、上記実施例では、個別に説明したが、これに限らず、例えば、第１実施例と第２実施例、第１実施例及び第２実施例と第４実施例、第３実施例と第４実施例、或いは、第１実施例と第４実施例、と云ったように自由に組み合わせて適用することができる。他には、第２実施例と第３実施例、或いは、第２実施例及び第３実施例と第４実施例という組合せも可能である。
更に、本発明は上述した実施例に限定されるものではなく、その要旨を逸脱しない範囲で、種々変形して実施することができる。
【０１６０】
【発明の効果】
本発明によれば次のような効果が得られる。
本発明の第１局面に係るＬＳＩの素子配置方法及び装置によれば、回路全体を所定数（例えば、ｍ個）のブランチから構成される配置対象の部分回路に対して、ｍ個より少ない個数（例えば、（ｍ−ｎ）個）のブランチの重畳部分を持って素子を配置する。従って、本発明の第１局面に係るＬＳＩの素子配置方法及び装置によれば、局所的な最適化を連続して行うので、回路全体を考慮した素子配置が可能であり、更に、ブランチの特徴を生かした遺伝アルゴリズムを用いた素子配置方法と相俟って、例えば、配置された素子が占める面積をコスト関数に用いた場合は素子面積が高密度化された、質の高い素子配置結果を効率よく求めることができる。
【０１６１】
上記のＬＳＩの素子配置方法及び装置によれば、最適化手法として遺伝アルゴリズムを採用し、各解候補毎のコストが評価された後の各世代における解候補の選択をする場合に、コスト関数をその重要度に応じた順番で適用することにより、解候補をふるいにかけて絞り込んでいくので、すべてのコスト関数に対して最適もしくは近似最適な解を効率よく求めることが可能となる。
【０１６３】
本発明の第２局面に係るＬＳＩの素子配置方法及び装置によれば、ＬＳＩにおける素子の自動配置において、ブランチの特徴を生かした遺伝アルゴリズムを適用する際に、遺伝的操作の１つとして、各世代の各解候補のコード（染色体）に対して、予め指定された確率に従い、隣合うブランチ内でｙ座標が近接している素子のペアを探し、もしそのようなペアがあればその２素子のｙ座標を同一の値とするという操作を行う。この操作によって、横に隣合うことにより面積の縮小や配線のし易さ等に貢献するような素子のペアが徐々にｘ方向に整列していくので、最終的にｘ方向への整列性に優れた質の高い配置結果を効率良く求めることが可能となる。
【図面の簡単な説明】
【図１】本発明の第１実施例に係るＬＳＩ素子配置装置の構成を示すブロック図。
【図２】本発明に係るＬＳＩ素子配置装置を適用する回路図の一例。
【図３】図１に示す素子配置装置の動作を示すフローチャート。
【図４】本発明に係るＬＳＩ素子配置装置を用いて実施した図２の回路図の自動配置結果の一例。
【図５】素子配置部３０の概略構成を示す図。
【図６】図１に示すＬＳＩ素子配置装置の素子配置手段の動作を詳しく示すフローチャート。
【図７】本発明の第２実施例に係るＬＳＩ素子配置装置の動作を示すフローチャート。
【図８】第２実施例の選択手段の動作を示すフローチャート。
【図９】本発明に係るＬＳＩ素子配置装置を用いて実施した図２の回路図の自動配置結果の一例。
【図１０】本発明の第３実施例の処理工程を示すフローチャート。
【図１１】図１０のフローチャートの中の遺伝アルゴリズムの概略を示すフローチャート。
【図１２】図１０のフローチャートを用いた図２の回路図に対する１つの配置結果を示す図。
【図１３】本発明の第４実施例の処理工程を示すフローチャート。
【図１４】図１３のフローチャートの中のｙ座標の調整の概略を示すフローチャート。
【図１５】図１３のフローチャートを用いた図２の回路図に対する１つの配置結果。
【符号の説明】
１０…入力部、２０…部分回路データ抽出部、３０…素子配置部、
３１…初期解候補群生成部、３２…Ｘ座標決定部、３３…適応度評価部、
３４…解候補群更新部、３５…（近似）最適解選定部、３６…選択部、
３７…交叉部、３８…突然変異部、４０…配置結果ファイル作成部、
５０…出力部。
【図１】
0003556260.tif 000008
【図２】
0003556260.tif 000009
【図３】
0003556260.tif 000010
【図４】
0003556260.tif 000011
【図５】
0003556260.tif 000012
【図６】
0003556260.tif 000013
【図７】
0003556260.tif 000014
【図８】
0003556260.tif 000015
【図９】
0003556260.tif 000016
【図１０】
0003556260.tif 000017
【図１１】
0003556260.tif 000018
【図１２】
0003556260.tif 000019
【図１３】
0003556260.tif 000020
【図１４】
0003556260.tif 000021
【図１５】
0003556260.tif 000022