図面 (/)

技術 論理セルの並列配置処理方法

出願人 株式会社東芝
発明者 上田俊晃河野香
出願日 1993年3月31日 (27年7ヶ月経過) 出願番号 1993-073930
公開日 1994年10月18日 (26年1ヶ月経過) 公開番号 1994-291186
状態 特許登録済
技術分野 CAD 半導体集積回路 ICの設計・製造(配線設計等)
主要キーワード 最適化効果 並列領域 収束判定条件 一般セル 見積値 カット数 移動候補 子プロセッサ
関連する未来課題
重要な関連分野

この項目の情報は公開日時点(1994年10月18日)のものです。
また、この項目は機械的に抽出しているため、正しく解析できていない場合があります

図面 (14)

構成

半導体集積回路レイアウト設計に於いて、セルの配置位置を計算機を用いて自動的に決定する際に、LSIのチップ領域を分割して複数の領域を構成する工程と、分割された領域間を通過するネット数が当該セルの移動或いは交換によって減少するセルを選択して配置位置を改善する工程と、分割された領域間を通過するネット数が当該セル集合の移動或いは交換によって減少するセル集合を選択して配置位置を改善する工程とを含み、分割された領域へのセル配置を最適化する。

効果

半導体集積回路のセル配置を計算機を用いて配置改善していく過程に於いて、単独のセル移動による高速改良効果とセル集合の移動による大局的な最適化効果ダイナミック切り替える事が可能となり、配置改良処理に於ける最適化の性能が向上する。

概要

背景

半導体集積回路装置は、所望の回路動作が得られる様に論理機能記憶機能を有するセル或いはブロックをチップ内に配置し、その入出力端子間をそれぞれ配線して構成されている。

図12は、一般的なゲートアレイ方式による半導体集積回路チップ概略構成を示したものである。チップ上は、セルが配置される領域51、セル間の配線が施される領域52、および周辺に設けられた入出力回路の配置される領域53により構成される。配線には複数の配線層が利用でき、水平・垂直方向の配線にそれぞれ別の層が割り当てられるのが一般的である。

この様な半導体集積回路レイアウト設計では、計算機を用いて自動的にセルの配置や端子間の配線を最適化するのが普通であり、配置処理に於いてセル配置を決定する際には、後の配線処理が容易となる様に配置処理を施す。例えば仮想配線長の最小化や配線混雑度の均一化といった事を目的として適当な評価関数を設定し、セルの配置位置を最適化する。また、計算機による配置処理では、通常、配置の初期状態を決定する初期配置フェーズと、その後の逐次配置改善フェーズにより、最終的な配置を決定する。

この配置改良過程に於いては様々な配置最適化手法が利用されているのが現状であるが、その中で比較的に良い性能が得られるものとして、K&Lの有名な分割アルゴリズム(B.W.Kernighan and S.Lin,"An Efficient Heuristic Procedure for Partitioning Graphs",Bell Sys. Tech. J.,Vol.49 pp.291-307, Feb. 1970)がある。これは、ミニカット配置に於ける論理セルの代表的な分割手法であり、セルのゲイン(当該セルを移動したときにカットラインを通過するネット数が幾つ減少するかという値)を次々と累積していく事によって一種の先読みが可能となり一般的に良い性能が得られるとされている。

ところが、図13の分割例でも判るように現実的には各セルの大きさのばらつきや、分割に於けるセル数不均衡の発生等考慮すべき課題も多い。そして最も重大な問題は、初期解に依存した局所的に最適な状態に陥ると、それ以降の改善が期待できない事である。以下でこの問題を図2,図3を使ってより具体的に説明する。

図2は初期状態から決定されるある配置状態表現しており、点線で示したものはチップ上に設定したカットライン、ローマ字の付いた丸印はセル、実線はそれらの接続関係を示しているものとする。この例では、大局的にみると図3の様な最適な配置結果を得ることが可能であり、カットラインを通過するネットの数を3本に最小化できるはずである。

ところが、ひとたび図2の様な局所的に最適な配置状態に陥ってしまうと、どのセルを動かしてもカット数が増加する傾向となり最小化が進まない。また、K&Lの分割アルゴリズムを使った場合でも、他のセルを全く動かさないで、セルJ,I,L,KとセルO,M,P,Nを立て続け交換する決定的な方策がないため、これ以上の最小化が進まない。

例えば図2の例では、セルF,H,U,V,C,D,S,Q等のどれか一つが先に移動候補となってしまうことが避けられず、こうなってしまうとこの後いくらゲインを累積して先読みしてもこれ以上の改良は進まずにこの配置状態で集束してしまう。即ち、同一ゲインのセルが複数存在した時に、どのセルから先に移動すべきかの選択基準がない為、これらの組み合わせで決まる次の配置状態を最適な方向へ導く事ができなかった。

また、この様な同一のゲンイを持つセルは大規模なLSIになればなる程増えていく為、それらの順列で決まる配置改良状態を全て虱潰しに調べる訳にはいかないという問題があった。

一方、上述した配置改良過程における最もシンプルな方法としては、あるセルの位置と他のセルの位置を交換して新配置状態を作り、元の配置状態よりも良くなれば新配置状態を採用し、悪くなれば元の配置状態へ戻す操作を繰り返して配置改良を図るという方法がある(M.hanan, P.K.Wolff Sr. ahd B.J.Agule, "Some experimental results on placement techniques", Proceedings of the 13thDesign Automation Conference,1976,pp.214-224.)。

この方法では、セル数の増加に従って、満足のいく配置解を得る為の配置改良に要する処理時間が急激に増大していく。この為、現実的な処理時間内で効果的に最適化を図るべく処理の高速化を達成しなければならないという問題があった。

この課題を解決するための並列配置改良方法としては、互いに直接的な接続関係がないセル同士並列に改良していく方法、或いは、この様な限定操作をせずにLSIのチップ領域を分割して並列配置改良を行う方法が既に提案されている(ICCAD'86, A parallel simulated annealing algorithm for the placemet ofmacro-cells, A Casotto and Alberto Aangiavanni-Vincentelli,UCB.、特開昭62−243071)。

ところが、前者は同時並列にセル交換処理が施された場合の改良誤差をなくす為に、直接接続関係がない互いに独立な交換セル対を選択する為のロック機構が必要となり、独立な交換セル対を計算機で収集し限定する操作の為のオーバヘッド改良対象となるセルを選択する度に毎回発生する。また、交換セル対は通常非常に多数存在するため、改良が収束するまでに多くの繰り返し操作が必要であるという問題が残り、大局的な最適化を高速に進める事は難しい。

一方、後者の様に単純に領域を分割して並列化する方法では分割された領域内の配置改良処理時間が不均一になり、チップ全体としての配置改良時間が最も処理時間のかかる領域に律則されて短縮化できない(並列度が上がらない)という問題点があった。

以上のように、セル数の増加に従って、満足のいく配置解を得る為の配置改良に要する処理時間が急激に増大していく。この為、現実的な処理時間内で効果的に最適化を図るべく処理時間を短縮化しなければならなかった。

この為、いくつかの並列配置方法が既に提案されているが、領域を分割して並列化する方法では分割された領域内の配置改良処理時間が不均一になり、チップ全体として配置改良時間が最も処理時間のかかる領域に律則されて並列度が上がらないという課題があった。

図13は、この課題をより具体的に説明するためのチップ領域上の領域分割例を示す概略図であり、点線で分割された4つの領域はそれぞれ別々の計算機により並列に配置改良処理が施される単位領域に対応している。ここで網がけの大きいい矩形はRAM/ROM等のマクロブロックを示しており、小さい矩形はその他の一般セルを示している。

この例の様に単純にチップを4分割して処理すると各領域内の実効改良対象セル数は異なってしまい。各領域内の配置改良に要する処理時間が著しく異なる事になる。チップ全体の配置改良処理時間は図13の矢印で示したように分割された各領域内の配置改良処理時間の最大値で決まってしまうので単純な分割では並列度が上がらない。

一般的な並列処理方式としては、動的に負荷の分散・均一化を図る方法、及び処理時間の掛かりそうな処理から先にプロセッサ割り付ける方法などが考えられる。確かに前者は利用するプロセッサ数が比較的少なく、対象とする処理単位が小さくて多い(粒度が小さい)時には確率的に負荷が均一化され、有効であるが、粒度が大きい場合にはやはり負荷の不均衡が残ってしまうという課題があった。

後者に於いては実行中に刻々と変化する負荷状況や利用する計算機の性能のばらつきなどを吸収する事はできず、負荷が均等になる保障がない。また、粒度が大きい時には前者と同様に負荷の不均衡が残ってしまい、問題は解決されない。

ところが、図6のように分割領域を調整してやれば、各領域内の配置改良処理時間は矢印で示したように均一化さてた揃い、チップ全体の配置改良処理に要する計算時間が短縮化される。つまり、この様な分割の前準備の手順を負めば利用できるプロセッサを有効に活用してレイアウト処理の高速化を実現する事が可能となる。

ところで、ULSI製造技術の進歩による集積度の向上により、ULSIに搭載されるトランジスタの数は毎年数倍の割合で増大してきており、数年内には。メガゲートクラスのLSIが実現可能となると予想される一方、短期間に制作されることが強く要求されている。このことより、レイアウトCADは大量のデータを高速に処理しなければならなくなっている。

これまで自動配置において種々の方法が提案されているが、これらのほとんどの場合、単一のCPUを用いてシーケンシャルに処理が行われてきたために計算速度には限度があり、計算時間の短縮は難しかった。計算速度をあげるにはCPUの速度をあげるか、マルチCPUにより並列処理を行い計算時間の大幅な短縮化をはかるかの方法が考えられる。このうちCPUの速度をあげる方法には自ずと限度がある。一方、並列処理により計算時間の短縮を図る配置方法も従来提案されてきている。

従来、並列配置処理においては並列用領域を設定したのち、各プロセッサーに対し任意に領域を割り当てていたため、プロセッサー数より並列領域数が多い場合、個々のプロセッサーが複数の領域を処理する事になり、それぞれのプロセッサーの全処理時間の差が大きなものとなるという問題があった。

この場合、一つの領域の処理を終えたプロセッサーに直ちに別の未処理の領域の処理を行わせるようにして並列度の向上を図ったとしても、最後に残った領域の処理に非常に時間がかかる場合には、一つのプロセッサーだけに処理の負荷がかかり、他のプロセッサーは処理が終了し、並列度が落ちるという問題があった。

概要

半導体集積回路のレイアウト設計に於いて、セルの配置位置を計算機を用いて自動的に決定する際に、LSIのチップ領域を分割して複数の領域を構成する工程と、分割された領域間を通過するネット数が当該セルの移動或いは交換によって減少するセルを選択して配置位置を改善する工程と、分割された領域間を通過するネット数が当該セル集合の移動或いは交換によって減少するセル集合を選択して配置位置を改善する工程とを含み、分割された領域へのセル配置を最適化する。

半導体集積回路のセル配置を計算機を用いて配置改善していく過程に於いて、単独のセル移動による高速な改良効果とセル集合の移動による大局的な最適化効果ダイナミック切り替える事が可能となり、配置改良処理に於ける最適化の性能が向上する。

目的

本発明はこの様な問題点を解決するために成されたものであり、第1の発明の目的は、まず貧欲な方法で改良を進めて高速に最適な状態に近づけ、その後はセルをダイナミックにグループ化して動かすことによって、さらに最適な配置状態を大局的に発見できる論理セルの並列配置処理方法を提供する事にある。

また、第2の発明の目的は、高速なセル配置改良方法を提供する事にある。さらに、第3の発明の目的は、並列に処理する際に並列領域の評価値を考慮した上、各領域をプロセッサーへ割り当てることによりレイアウト処理の並列度を上げ、高速でかつ効果的に配置結果を得ることができる論理セルの並列配置方法を提供する事にある。

効果

実績

技術文献被引用数
0件
牽制数
0件

この技術が所属する分野

(分野番号表示ON)※整理標準化データをもとに当社作成

ライセンス契約や譲渡などの可能性がある特許掲載中! 開放特許随時追加・更新中 詳しくはこちら

請求項1

半導体集積回路レイアウト設計に於いて、セルの配置位置を計算機を用いて自動的に決定する際に、LSIのチップ領域を分割して複数の領域を構成する工程と、分割された領域間を通過するネット数が当該セルの移動或いは交換によって減少するセルを選択して配置位置を改善する工程と、分割された領域間を通過するネット数が当該セル集合の移動或いは交換によって減少するセル集合を選択して配置位置を改善する工程とを含み、分割された領域へのセル配置を最適化する事を特徴とする論理セル並列配置処理方法

請求項2

前記セルを選択する工程は、分割された領域間を通過するネット数が当該セルの移動或いは交換によって最も減少するセルを選択して配置位置を改善する事を特徴とする請求項1記載の論理セルの並列配置処理方法。

請求項3

前記セル集合を選択する工程は、分割された領域間を通過するネット数が当該セル集合の移動或いは交換によって最も減少するセル集合を選択して配置位置を改善する事を特徴とする請求項1記載の論理セルの並列配置処理方法。

請求項4

移動或いは交換を施す前記セル集合を発見する際に、セルを選択する工程で選択されたセルからネットで接続しているセルを連鎖的に手操る事によってセル集合を決定する事を特徴とする請求項1あるいは2記載の論理セルの並列配置処理方法。

請求項5

半導体集積回路のレイアウト設計に於いて、セルの配置位置を計算機を用いて自動的に決定する際に、LSIのチップ領域を分割して複数の領域を構成する工程と、分割された領域間を通過するネット数が当該セルの移動或いは交換によって減少するセルを選択して配置位置を改善する工程と、この工程の後に分割された領域間を通過するネット数が当該セル集合の移動或いは交換によって減少するセル集合を選択して配置位置を改善する工程とを含み、分割された領域へのセル配置を最適化する事を特徴とする論理セルの並列配置処理方法。

請求項6

計算機を用いて半導体基板上に複数のセルを自動的に配置する方法に於いて、LSIのチップ領域を裁断して複数の領域に分割し、それぞれの領域内のセル配置改良処理を複数の計算機を利用して同時並列に実行させる際に、マクロブロック等の位置が固定されたセルを控除して領域内の実質的な改良対象セルを計算する工程と、領域内部で接続するネット及び領域外部へつながるネット数を計算する工程と、領域内の目標とする配置評価値と現在の配置評価値とのズレを計算する工程と、利用する計算機の性能及び負荷状況を計算する工程とを行なってチップ領域の分割方法を決定し、各領域内の配置改良処理時間を均一化させる事を特徴とする論理セルの並列配置処理方法。

請求項7

半導体集積回路の自動レイアウトシステムにおいて、対象領域を複数個の領域に分割し、並列にセルの配置改良を行うに際し、セルの集合が配置されている状態の良さを評価し、その評価値を基に並列処理用領域をプロセスに割り当てる事を特徴とする論理セルの並列配置処理方法。

技術分野

0001

本発明は、ゲートアレイ方式或いはスタンダードセル方式半導体集積回路自動レイアウト設計に於いて、セル或いはブロックを計算機を用いて自動的に配置する方法に関する。

背景技術

0002

半導体集積回路装置は、所望の回路動作が得られる様に論理機能記憶機能を有するセル或いはブロックをチップ内に配置し、その入出力端子間をそれぞれ配線して構成されている。

0003

図12は、一般的なゲートアレイ方式による半導体集積回路チップ概略構成を示したものである。チップ上は、セルが配置される領域51、セル間の配線が施される領域52、および周辺に設けられた入出力回路の配置される領域53により構成される。配線には複数の配線層が利用でき、水平・垂直方向の配線にそれぞれ別の層が割り当てられるのが一般的である。

0004

この様な半導体集積回路のレイアウト設計では、計算機を用いて自動的にセルの配置や端子間の配線を最適化するのが普通であり、配置処理に於いてセル配置を決定する際には、後の配線処理が容易となる様に配置処理を施す。例えば仮想配線長の最小化や配線混雑度の均一化といった事を目的として適当な評価関数を設定し、セルの配置位置を最適化する。また、計算機による配置処理では、通常、配置の初期状態を決定する初期配置フェーズと、その後の逐次配置改善フェーズにより、最終的な配置を決定する。

0005

この配置改良過程に於いては様々な配置最適化手法が利用されているのが現状であるが、その中で比較的に良い性能が得られるものとして、K&Lの有名な分割アルゴリズム(B.W.Kernighan and S.Lin,"An Efficient Heuristic Procedure for Partitioning Graphs",Bell Sys. Tech. J.,Vol.49 pp.291-307, Feb. 1970)がある。これは、ミニカット配置に於ける論理セルの代表的な分割手法であり、セルのゲイン(当該セルを移動したときにカットラインを通過するネット数が幾つ減少するかという値)を次々と累積していく事によって一種の先読みが可能となり一般的に良い性能が得られるとされている。

0006

ところが、図13の分割例でも判るように現実的には各セルの大きさのばらつきや、分割に於けるセル数不均衡の発生等考慮すべき課題も多い。そして最も重大な問題は、初期解に依存した局所的に最適な状態に陥ると、それ以降の改善が期待できない事である。以下でこの問題を図2図3を使ってより具体的に説明する。

0007

図2は初期状態から決定されるある配置状態表現しており、点線で示したものはチップ上に設定したカットライン、ローマ字の付いた丸印はセル、実線はそれらの接続関係を示しているものとする。この例では、大局的にみると図3の様な最適な配置結果を得ることが可能であり、カットラインを通過するネットの数を3本に最小化できるはずである。

0008

ところが、ひとたび図2の様な局所的に最適な配置状態に陥ってしまうと、どのセルを動かしてもカット数が増加する傾向となり最小化が進まない。また、K&Lの分割アルゴリズムを使った場合でも、他のセルを全く動かさないで、セルJ,I,L,KとセルO,M,P,Nを立て続け交換する決定的な方策がないため、これ以上の最小化が進まない。

0009

例えば図2の例では、セルF,H,U,V,C,D,S,Q等のどれか一つが先に移動候補となってしまうことが避けられず、こうなってしまうとこの後いくらゲインを累積して先読みしてもこれ以上の改良は進まずにこの配置状態で集束してしまう。即ち、同一ゲインのセルが複数存在した時に、どのセルから先に移動すべきかの選択基準がない為、これらの組み合わせで決まる次の配置状態を最適な方向へ導く事ができなかった。

0010

また、この様な同一のゲンイを持つセルは大規模なLSIになればなる程増えていく為、それらの順列で決まる配置改良状態を全て虱潰しに調べる訳にはいかないという問題があった。

0011

一方、上述した配置改良過程における最もシンプルな方法としては、あるセルの位置と他のセルの位置を交換して新配置状態を作り、元の配置状態よりも良くなれば新配置状態を採用し、悪くなれば元の配置状態へ戻す操作を繰り返して配置改良を図るという方法がある(M.hanan, P.K.Wolff Sr. ahd B.J.Agule, "Some experimental results on placement techniques", Proceedings of the 13thDesign Automation Conference,1976,pp.214-224.)。

0012

この方法では、セル数の増加に従って、満足のいく配置解を得る為の配置改良に要する処理時間が急激に増大していく。この為、現実的な処理時間内で効果的に最適化を図るべく処理の高速化を達成しなければならないという問題があった。

0013

この課題を解決するための並列配置改良方法としては、互いに直接的な接続関係がないセル同士並列に改良していく方法、或いは、この様な限定操作をせずにLSIのチップ領域を分割して並列配置改良を行う方法が既に提案されている(ICCAD'86, A parallel simulated annealing algorithm for the placemet ofmacro-cells, A Casotto and Alberto Aangiavanni-Vincentelli,UCB.、特開昭62−243071)。

0014

ところが、前者は同時並列にセル交換処理が施された場合の改良誤差をなくす為に、直接接続関係がない互いに独立な交換セル対を選択する為のロック機構が必要となり、独立な交換セル対を計算機で収集し限定する操作の為のオーバヘッド改良対象となるセルを選択する度に毎回発生する。また、交換セル対は通常非常に多数存在するため、改良が収束するまでに多くの繰り返し操作が必要であるという問題が残り、大局的な最適化を高速に進める事は難しい。

0015

一方、後者の様に単純に領域を分割して並列化する方法では分割された領域内の配置改良処理時間が不均一になり、チップ全体としての配置改良時間が最も処理時間のかかる領域に律則されて短縮化できない(並列度が上がらない)という問題点があった。

0016

以上のように、セル数の増加に従って、満足のいく配置解を得る為の配置改良に要する処理時間が急激に増大していく。この為、現実的な処理時間内で効果的に最適化を図るべく処理時間を短縮化しなければならなかった。

0017

この為、いくつかの並列配置方法が既に提案されているが、領域を分割して並列化する方法では分割された領域内の配置改良処理時間が不均一になり、チップ全体として配置改良時間が最も処理時間のかかる領域に律則されて並列度が上がらないという課題があった。

0018

図13は、この課題をより具体的に説明するためのチップ領域上の領域分割例を示す概略図であり、点線で分割された4つの領域はそれぞれ別々の計算機により並列に配置改良処理が施される単位領域に対応している。ここで網がけの大きいい矩形はRAM/ROM等のマクロブロックを示しており、小さい矩形はその他の一般セルを示している。

0019

この例の様に単純にチップを4分割して処理すると各領域内の実効改良対象セル数は異なってしまい。各領域内の配置改良に要する処理時間が著しく異なる事になる。チップ全体の配置改良処理時間は図13の矢印で示したように分割された各領域内の配置改良処理時間の最大値で決まってしまうので単純な分割では並列度が上がらない。

0020

一般的な並列処理方式としては、動的に負荷の分散・均一化を図る方法、及び処理時間の掛かりそうな処理から先にプロセッサ割り付ける方法などが考えられる。確かに前者は利用するプロセッサ数が比較的少なく、対象とする処理単位が小さくて多い(粒度が小さい)時には確率的に負荷が均一化され、有効であるが、粒度が大きい場合にはやはり負荷の不均衡が残ってしまうという課題があった。

0021

後者に於いては実行中に刻々と変化する負荷状況や利用する計算機の性能のばらつきなどを吸収する事はできず、負荷が均等になる保障がない。また、粒度が大きい時には前者と同様に負荷の不均衡が残ってしまい、問題は解決されない。

0022

ところが、図6のように分割領域を調整してやれば、各領域内の配置改良処理時間は矢印で示したように均一化さてた揃い、チップ全体の配置改良処理に要する計算時間が短縮化される。つまり、この様な分割の前準備の手順を負めば利用できるプロセッサを有効に活用してレイアウト処理の高速化を実現する事が可能となる。

0023

ところで、ULSI製造技術の進歩による集積度の向上により、ULSIに搭載されるトランジスタの数は毎年数倍の割合で増大してきており、数年内には。メガゲートクラスのLSIが実現可能となると予想される一方、短期間に制作されることが強く要求されている。このことより、レイアウトCADは大量のデータを高速に処理しなければならなくなっている。

0024

これまで自動配置において種々の方法が提案されているが、これらのほとんどの場合、単一のCPUを用いてシーケンシャルに処理が行われてきたために計算速度には限度があり、計算時間の短縮は難しかった。計算速度をあげるにはCPUの速度をあげるか、マルチCPUにより並列処理を行い計算時間の大幅な短縮化をはかるかの方法が考えられる。このうちCPUの速度をあげる方法には自ずと限度がある。一方、並列処理により計算時間の短縮を図る配置方法も従来提案されてきている。

0025

従来、並列配置処理においては並列用領域を設定したのち、各プロセッサーに対し任意に領域を割り当てていたため、プロセッサー数より並列領域数が多い場合、個々のプロセッサーが複数の領域を処理する事になり、それぞれのプロセッサーの全処理時間の差が大きなものとなるという問題があった。

0026

この場合、一つの領域の処理を終えたプロセッサーに直ちに別の未処理の領域の処理を行わせるようにして並列度の向上を図ったとしても、最後に残った領域の処理に非常に時間がかかる場合には、一つのプロセッサーだけに処理の負荷がかかり、他のプロセッサーは処理が終了し、並列度が落ちるという問題があった。

発明が解決しようとする課題

0027

以上述べてきたように、自動配置に於いては既に提案されている従来のグリーディな分割手法による改良アルゴリズムは一般的にアニーリングなどの最適化手法と比べてはるかに高速であるが、局所的な最適解に陥り改良が十分進まないという欠点があった。これは、一度図2の様な局所的な配置状態に陥ってしまうと、セルを単独で評価して移動を繰り返すだけでは十分な最適化が実現できない事に起因している。

0028

また、自動配置に於ける従来の配置改良方法では、LSIのチップ領域を分割して並列化を行う場合には、利用できるプロセッサ数と分割領域数の間に大差がない時、負荷の分散・均一化が難しく並列度が落ちてしまうという問題があった。

0029

さらに、従来のLSI設計におけるセルの並列配置方法においては、並列用領域を設定したのち、各プロセッサーに対し任意に領域を割り当てていたため、最後に残った領域の処理に非常に時間がかかる場合には、他のプロセッサーは処理が終了しているにも係わらず、一つのプロセッサーだけに処理の負荷がかかっている場合があり、レイアウトの並列効果も下がってしまうという問題があった。

0030

本発明はこの様な問題点を解決するために成されたものであり、第1の発明の目的は、まず貧欲な方法で改良を進めて高速に最適な状態に近づけ、その後はセルをダイナミックグループ化して動かすことによって、さらに最適な配置状態を大局的に発見できる論理セルの並列配置処理方法を提供する事にある。

0031

また、第2の発明の目的は、高速なセル配置改良方法を提供する事にある。さらに、第3の発明の目的は、並列に処理する際に並列領域の評価値を考慮した上、各領域をプロセッサーへ割り当てることによりレイアウト処理の並列度を上げ、高速でかつ効果的に配置結果を得ることができる論理セルの並列配置方法を提供する事にある。

課題を解決するための手段

0032

第1の発明は、半導体集積回路のレイアウト設計に於いて、セルの配置位置を計算機を用いて自動的に決定する際に、LSIのチップ領域を分割して複数の領域を構成する工程と、分割された領域間を通過するネット数が当該セルの移動或いは交換によって減少するセルを選択して配置位置を改善する工程と、分割された領域間を通過するネット数が当該セル集合の移動或いは交換によって減少するセル集合を選択して配置位置を改善する工程とを含み、分割された領域へのセル配置を最適化する事を特徴とする。

0033

また、第2の発明は、計算機を用いて半導体基板上に複数のセルを自動的に配置する方法に於いて、LSIのチップ領域を裁断して複数の領域に分割し、それぞれの領域内のセル配置改良処理を複数の計算機を利用して同時並列に実行させる際に、マクロブロック等の位置が固定されたセルを控除して領域内の実質的な改良対象セルを計算する工程と、領域内部で接続するネット及び領域外部へつながるネット数を計算する工程と、領域内の目標とする配置評価値と現在の配置評価値とのズレを計算する工程と、利用する計算機の性能及び負荷状況を計算する工程とを行なってチップ領域の分割方法を決定し、各領域内の配置改良処理時間を均一化させる事を特徴としている。

0034

さらに、第3の発明は、半導体集積回路の自動レイアウトシステムにおいて、対象領域を複数個の領域に分割し、並列にセルの配置改良を行うに際し、セルの集合が配置されている状態の良さを評価し、その評価値を基に並列処理用領域をプロセスに割り当てる事を特徴とする。

0035

第1の発明では、半導体基板上に複数のセルを計算機を用いて自動的に配置する方法に於いて、配置状態の改良手段として、単独のセル移動による改善手段とネットの接続関係から適当なセルグループを構成してセル集合毎に移動するという改善手段の2つの手段が設けられている。これにより、高速に改良を進めるという効果と局所的に最適な状態から抜け出してより最適な配置状態を大局的に発見するという効果を同時に満足させた最適化が実現できる。

0036

また、第2の発明は、計算機を用いて半導体基板上に複数のセルを自動的に配置する方法に於いて、LSIのチップ領域を複数の領域に分割し、それぞれの領域内のセル配置改良処理を複数の計算機を利用して同時並列に実行させる際に、各領域内の配置改良処理時間を均一化させる事が可能となり、チップ全体としての配置改良時間が最も処理時間のかかる領域に律則されて短縮化できない(並列度が上がらない)という問題が解決される。

0037

これにより、領域内の配置改良処理を別々のプロセッサによって同時並列に実行する事による高速化が有効に実現される。また、この方法に於いては当然ながら分割領域を決定するための見積時間(オーバヘッド)か必要であるが、この見積時間は実際に領域内の配置改良を繰り返す処理時間と比べれば非常に小く実現できる。従って、ひとたび不均一な負荷を割り当ててしまった後に複数のプロセッサが待ち状態になるよりははるかに効率的であり、並列度の低下を未然に回避できる。

0038

さらに、第3の発明によれば、レイアウト処理を並列化する際、並列領域の評価値を基に各領域をプロセッサーへ割り当てるため、プロセッサー数より並列用領域が多い場合、各プロセッサーの処理時間が均一化され並列効果を上げる事ができる。

0039

以下、本発明の一実施例について説明する。

0040

第1の発明
図1は第1の発明の概略処理手順を示すフローチャートであり、これを実現するための詳細な処理手順は実施例の最後に詳細処理手順step0〜step21の形で記述してある。以下、本発明の実施例を図2図3及び詳細処理手順step0〜step21を利用しながら、図1のフローチャートの流れに沿って説明する。

0041

START後、まずLSIのチップ領域をカットラインによって2分割し、分割領域を作成する。そして、それぞれの分割領域内のセルを仮決定し、初期の配置状態を決定する。この初期配置は例えばランダムなセル配置を採用しても良い(S1)。

0042

次に、(S1)で出来上がった初期分割に於いて改良度を初期化し(step0)、セルの混雑した分割領域を選択する(step1)。次に、カットラインを通過するネット数を最も減少させる効果の高いセルを混雑した領域内のセルから選択し(S2)、セルの移動を実行して(S3)、改良度を累積する(step2)。次に、以前の配置状態との比較を行って改良度があれば配置状態を更新する(step3)。

0043

次に、step4〜step6の改良収束判定条件によって、上記(S2からS3)のような単独のセル移動による配置改善処理を収束するまで行う。これによって、最大ゲインセル選択と当該セルの移動処理が繰り返される。(S2〜S4)。

0044

以上の様な単独のセル移動による配置改良過程により、最も改良効果の高いセルから配置状態が改善され急速に最適化が進む。これによって、ある局所的な配置最適解に収束する。これは、例えば図2の様な配置状態である。

0045

次に、この様な局所的に最適な配置状態から更に配置改善を進めるために、step7〜step14(S5〜S7)の手順に従ってダイナミックにセルのクラスタを形成し、クラスタ単位で移動を試みる。そして、この当該クラスタの移動によって移動先の領域内のセル充填率許容範囲を越えた場合は、同様の手順step15〜step21に従って動的に形成したクラスタと交換する。

0046

クラスタの形成方法としては、配置状態の改善効果が高いセル(ゲインの高いセル、通常、複数個ある)をひとたびキューに詰め込んで、これらのセルを各クラスタの核の候補とし(step9,step16)、次に、このキューからクラスタの核となる候補セルを一つ選び出して(step10,step17)、当該セルにネット接続するセルを連鎖的に手繰り寄せ、ゲインの高い順にソートされた状態のリストに追加する事によってクラスタ(セル集合)を作成する(step11,step13,step18,step20)。

0047

これにより、ある配置状態からネットの接続関係で決定されるゲイン最大のクラスタが動的に抽出できる。また、このクラスタの作成に於いては、分割された各領域内のセル充填率のバランスがクラスタの移動/交換によって崩れないようにクラスタのサイズを調整する(step12,step19)。

0048

以上のような処理手順によって、例えば図2の様な配置状態から、セルJ,I,L,Kで構成されたセル集合を一纏めにして反対側の領域に移動した場合の評価、及び、セルO,M,P,Nで構成されるセル集合と交換した場合の評価等が行える。従って、ひとたび図2の様な局所的に最適な配置解に陥っても、そこから脱出して更に最適化を進める事ができ、この例の場合では結果的に図3の様な大局的な最適配置状態へと改良が進む事になる。

0049

次に、上記処理手順によるゲイン最大のクラスタの生成(S5)、及びクラスタ化されたセル集合毎の移動(S6)による改良が成功したか否かを判定する(S7)。改良に成功した場合は(S2)に戻って、単独のセル移動による改良処理から上記クラスタ単位の改良処理までを手順通りに繰り返す。失敗した場合は配置最適化処理を止める。

0050

以上の様にして、本実施例ではある配置状態から動的にクラスタ化したセル集合の移動を他のセルの配置位置が変わらない状況下で評価する手段と単独のセル移動による改良評価手段を使い分けて配置改良を進める。これにより、高速に改良を進めるという効果と局所的に最適な状態から抜け出して、より最適な配置状態を大局的に発見するという効果を同時に満足させた最適化が実現できる。

0051

尚、本発明は上記した一実施例に限られるものではなく、その趣旨を逸脱しない範囲で変形して実施することができる。

0052

詳細処理手順
step0:登録されている配置状態のカット数減少累積値Gを0とする。
step1:セルの混雑している領域Rを選択する。
step2:Rの領域内から移動によって最もカット数が減少するセルをカットラインの反対側へ移動して仮の配置状態を作成し、カット数の減少値を累積Gする。
step3:累積値Gが現在までのGの値の最大値以上であれば登録されている配置状態を更新する。

0053

step4:全てのセルが移動済みか累積下限値を下回るまでstep1〜step3を繰り返す。
step5:累積値Gの最大値が正であればstep0へ。
step6:累積値Gの最大値が0で移動セルがあり、セルの混雑している領域内の全てのセルの中にゲイン正のセルがあればstep0へ。

0054

step7:登録されている配置状態のカット数減少累積値Tを0とする。
step8:セルの混雑している領域Rを選択する。
step9:Rの領域内から移動によって最もカット数が減少するセルをセルQUEQに挿入する。
step10:セルQUEQから一つセルを取り出しゲインソーテッドリストLを初期化する。QがNULLならEND。

0055

step11:ゲインソーテッドリストLから一つセルCを取り出しカットラインの反対側へ移動して仮の配置状態を作成し、カット数の減少値を累積Tする。
step12:セル総面積限界値を越えたらstep10へ。
step13:累積値Tが正でなければセルCにつながる同領域内の新規セルをLに追加し、step11へ。
step14:セル充填率の差が許容範囲以下であれば配置状態の登録を更新してstep10へ。

0056

step15:セルの混雑している領域Rを選択する。
step16:Rの領域内から移動によって最もカット数が減少するセルをセルQUEUに挿入する。
step17:セルQUEUから一つセルを取り出しゲインソーテッドリストLを初期化する。UがNULLならstep10へ。

0057

step18:ゲインソーテッドリストLから一つセルを取り出しカットラインの反対側へ移動して仮の配置状態を作成し、カット数の減少値を累積Tする。
step19:セル総面積限界値を越えたらstep17へ。
step20:累積値Tが正でなければセルCにつながる同領域内の新規セルをLに追加しstep18へ。
step21:step14へ。

0058

第2の発明
図5は、分割されたチップ上の領域をそれぞれ受け持つ各プロセッサ間の関係を示した概略構成図であり、Pが記入された4つの矩形は、チップ上の分割された各領域に割り当てられたそれぞれのプロセッサを示している。各プロセッサは、基本的な演算装置記憶装置を持ち、太線で示された様にコントロール側のプロセッサと通信チャネルにより結合されている。配置データの授受及び全体制御は、これらの通信手段を介して行われ、各プロセッサは同時並列に動作する。

0059

図6は、本発明の実施例を説明するためのチップ領域上の領域分割例を示す概略図であり、点線で分割された4つの領域はそれぞれ別々の計算機により同時並列に配置改良処理を施すため単位領域に対応している。この例では図13の様に単純にチップを4分割して処理すると各領域内の実効改良対象セル数が異なる為、各領域内の配置改良に要する処理時間が著しく異なる事になる。

0060

チップ全体の配置改良処理時間は分割された各領域内の配置改良処理時間の最大値で決まってしまうのでこの様な単純な分割では並列度が上がらない。ところが実施例の図6のように分割領域を調整してやれば、各領域内の配置改良処理時間が均一化されて揃い、チップ全体の配置改良処理時間が短縮化される。

0061

図4は、図6のような領域分割実現する為の処理手順を示す本発明ののフローチャートであり、この様な手順を踏めば利用できるプロセッサを有効に活用したレイアウト処理の高速化が実現できる。以下、第2の発明の並列配置処理方法を図4のフローチャートの流れに沿って説明する。

0062

スタート後、まずLSIチップ領域をカットラインで裁断して複数の矩形領域に仮分割する(S11)。これによって、チップ上は例えば図6の点線で示されたように縦方向に2つ、横方向に2つに分割され、合計4つの分割領域が構成される。

0063

次に、(S11)で出来上がった各分割領域内に於いてマクロブロック等の位置が固定されたセルを控除して領域内の実質的な改良対象セル数を計算し、ECとする(S12)。次に、仮分割で出来上がった各分割領域内に於いて領域内部で接続するネット及び領域外部へつながるネット数を計算し、それぞれIN,とする(S13)。次に、仮分割で出来上がった各分割領域内に於いて領域内の目標とする配置評価値と現在の配置評価値とのズレを計算し、DFとする(S14)。次に、利用する計算機の性能及び現在の稼動(負荷)状況を計算し、PW,LDとする(S15)。

0064

次に、(S12)〜(S15)によって求めた値から、例えば次の計算式により負荷見積値Eを計算して、この見積値が等しくなるように領域分割の修正を繰り返し、各プロセッサへの割り付け領域を決定する(S16)。尚、計算式に於けるa〜dは各項目重み係数である。これによって、LSIチップ上は例えば図6の点線で示されたように分割領域が修正され、新たな4つの分割か領域が決定される。

0065

ID=000003HE=015 WI=082 LX=0640 LY=1050
(S16)によってひとたび領域分割が決定した後は、それらの各領域それぞれに対して別々の計算機(プロセッサ)を割り付けて各領域内の配置改良処理を同時並列に実行する(S17)。ここでは、各プロセッサは自分の担当する部分領域内についてのみ配置改良を繰り返すため、チップ全面の配置処理に比べて高速に配置改良を図る事ができる。最後に、各プロセッサによる各領域内の配置改良結果を回収してチップ全体の配置結果を合成し。終了する。

0066

第2の発明では、以上の様にして分割領域毎の配置改良を並列化し、チップ全面の配置最適化を高速に行う。尚、本発明は上記した一実施例に限られるものではなく、その趣旨を逸脱しない範囲で種々変形して実施することができる。

0067

第3の発明
以下で、図7〜11を用い、第3の発明の具体的な実施例について説明する。本実施例においては、ゲートアレイレイアウト対象領域において初期配置が与えられている時において、並列領域を複数設定しプロセッサーに割当て、並列に配置改良処理を行い、セルの配置位置を決定する場合について説明する。ここでは、子プロセッサー数が5、並列用領域数が9の場合を考える。

0068

図7は本実施例に於ける処理フローを示す図である。まず、図8で示すように与えられたレイアウト対象領域1に対して並列用領域2〜10を設定する。次に図9に示すように各並列用領域2〜10ごとに、与えられた配置状態を基に現時点での評価値を求める。ここでは、現在の配置結果をもとにセル同士の重なり、カット数、ピン分散値総合した値(括弧内に示した数字)を各並列領域2〜10毎に求める。

0069

図10のように、当該評価値の悪い順に並列用領域6,9,3,5,4を各プロセッサー20〜24に割当て並列に配置改良処理を行う。各プロセッサー20〜24は各領域内での収束判定を当該評価値に基づき行い、収束が認められると領域内の配置改良を終了する。この場合、プロセッサー20〜24に領域を割り当てる時に使用する評価値と当該領域の収束判定に使用する評価値は同一であるから、処理前の評価値の悪いものほど処理に時間を要すると考えられる。

0070

プロセッサー20〜24は領域の配置改良を終了すると、そのつど未処理の領域の中から評価値の悪い7,10,8,2の順に次に処理する領域を割り当てられ、当該領域の配置改良処理が収束するまで行う。全ての並列用領域2〜10の配置改良が終了し、未処理の領域が無くなるまで前記処理を繰り返す。

0071

図11に従来例として、領域番号に従いチップの左下から順に領域の割当を行う場合のプロセッサー毎の処理時間及び割り当てられた領域の関係を示す。この場合、評価値を考慮していないため、一つの領域の処理を終えたプロセッサーに直ちに別の未処理の領域の処理を行わせるようにして並列度の向上を図っている。

0072

しかしながら、他のプロセッサーは処理が終了し、一つのプロセッサーだけに処理の負荷がかかる事があるため、並列度が落ちてしまう。これに対し、図10に示すように、本実施例では処理が速く終了したプロセッサーに評価値の悪い方から、即ち処理時間がよりかかると予想される領域から割り当てる為、各プロセッサーにより均一に負荷がかかり並列度向上につながる。

発明の効果

0073

以上述べた様に、第1の発明によれば、半導体集積回路のレイアウト設計に於いてセルの配置位置を計算機を用いて自動的に決定する際に、まず単独のセル移動や交換で改善が図れる場合には先にこれらのセルの配置改善を行って急速に最適な配置状態に近づける事ができる。また、この様な配置改善方法が収束した後には、ネットの接続関係からダイナミックに構成したグループ毎の移動或いは交換による大局的な配置改善が行える。この様に、配置状態の性質によって改良のレベルを動的に変更すれば、局所最適解から脱出しながら高速に最適化を進める事ができる。

0074

また、第2の発明によれば、計算機を用いてセルの配置位置を決定する自動配置処理に於いて、LSIチップ上の分割領域数と利用可能なプロセッサ数との間に大差がない場合であってもロスの少ない並列化を実現する事ができ、プロセッサを有効に利用して配置改良処理を高速化する事が可能となる。

0075

さらに、第3の発明によれば、レイアウト処理を並列化する際、並列領域の評価値を基に各領域をプロセッサーへ割り当てるため、プロセッサー数より並列用領域が多い場合、各プロセッサーの処理時間が均一化され並列効果を上げる事がてできる。

図面の簡単な説明

0076

図1第1の発明の一実施例の処理手順を示すフローチャート。
図2第1の発明に対する従来技術の問題点を説明するための概略図。
図3第1の発明の一実施例を説明するための概略図。
図4第2の発明における一実施例の処理手順を示すフローチャート。
図5第2の発明における各プロセッサ間の関係を示した概略構成図。
図6第2の発明における発明の実施例を説明する為の図。
図7第3の発明における一実施例に係わる配置処理手順を表わすフローチャート。
図8第3の発明における一実施例の並列用領域を示す図。
図9第3の発明における一実施例の並列用領域毎の評価値を示す図。
図10第3の発明における一実施例のプロセッサー毎の処理時間及び割り当てられた領域の関係を示す図。
図11第3の発明に対する従来のプロセッサー毎の処理時間及び割り当てられた領域の関係を示す図。
図12第1及び第2の発明に対する従来技術の問題点を説明するための概略図。
図13第1及び第2の発明に対する従来の半導体集積回路のチップ概略構成を示す図。

--

0077

A〜Xセル
1レイアウト対象領域
2〜10並列用に設定した領域
20〜24 プロセッサー

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

関連する挑戦したい社会課題

関連する公募課題

ページトップへ

技術視点だけで見ていませんか?

この技術の活用可能性がある分野

分野別動向を把握したい方- 事業化視点で見る -

(分野番号表示ON)※整理標準化データをもとに当社作成

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

新着 最近 公開された関連が強い技術

  • 東レ株式会社の「 集積回路およびその製造方法ならびにそれを用いた無線通信装置」が 公開されました。( 2020/09/24)

    【課題・解決手段】本発明は、簡便なプロセスで優れた集積回路を提供することを目的とする。本発明は、少なくとも、データを記憶するメモリアレイと、交流電流を整流して直流電圧を生成する整流回路と、前記メモリに... 詳細

  • 富士通株式会社の「 幾何公差寸法公差変換プログラム及び情報処理装置」が 公開されました。( 2020/09/24)

    【課題】幾何公差方式を用いて作成された図面データに対する利用者の解釈のばらつきを抑制する。【解決手段】処理部12は、幾何公差方式により物品15の形状または構造が定義された図面データ11aから、物品15... 詳細

  • 株式会社明電舎の「 変圧器コスト予測装置」が 公開されました。( 2020/09/24)

    【課題】変圧器のコスト予測を工数が少なく精度良く算出することができる変圧器コスト予測装置を提供する。【解決手段】過去に製造された変圧器の仕様、設計値、コストを含む過去データベース4を学習データとして予... 詳細

この 技術と関連性が強い人物

関連性が強い人物一覧

この 技術と関連する社会課題

関連する挑戦したい社会課題一覧

この 技術と関連する公募課題

関連する公募課題一覧

astavision 新着記事

サイト情報について

本サービスは、国が公開している情報(公開特許公報、特許整理標準化データ等)を元に構成されています。出典元のデータには一部間違いやノイズがあり、情報の正確さについては保証致しかねます。また一時的に、各データの収録範囲や更新周期によって、一部の情報が正しく表示されないことがございます。当サイトの情報を元にした諸問題、不利益等について当方は何ら責任を負いかねることを予めご承知おきのほど宜しくお願い申し上げます。

主たる情報の出典

特許情報…特許整理標準化データ(XML編)、公開特許公報、特許公報、審決公報、Patent Map Guidance System データ