JP3215215B2 - 論理セルの並列配置処理方法 - Google Patents

Description

【発明の詳細な説明】

【０００１】

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

【０００２】

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

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

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

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

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

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

【０００８】ところが、ひとたび図２の様な局所的に最
適な配置状態に陥ってしまうと、どのセルを動かしても
カット数が増加する傾向となり最小化が進まない。ま
た、Ｋ＆Ｌの分割アルゴリズムを使った場合でも、他の
セルを全く動かさないで、セルＪ，Ｉ，Ｌ，Ｋとセル
Ｏ，Ｍ，Ｐ，Ｎを立て続けに交換する決定的な方策がな
いため、これ以上の最小化が進まない。

【０００９】例えば図２の例では、セルＦ，Ｈ，Ｕ，
Ｖ，Ｃ，Ｄ，Ｓ，Ｑ等のどれか一つが先に移動候補とな
ってしまうことが避けられず、こうなってしまうとこの
後いくらゲインを累積して先読みしてもこれ以上の改良
は進まずにこの配置状態で集束してしまう。即ち、同一
ゲインのセルが複数存在した時に、どのセルから先に移
動すべきかの選択基準がない為、これらの組み合わせで
決まる次の配置状態を最適な方向へ導く事ができなかっ
た。

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

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

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

【００１３】この課題を解決するための並列配置改良方
法としては、互いに直接的な接続関係がないセル同士を
並列に改良していく方法、或いは、この様な限定操作を
せずにＬＳＩのチップ領域を分割して並列配置改良を行
う方法が既に提案されている（ICCAD'86, A parallel s
imulated annealing algorithm for the placemet ofma
cro-cells, A Casotto and Alberto Aangiavanni-Vince
ntelli,UCB.、特開昭６２−２４３０７１）。

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

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

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

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

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

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

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

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

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

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

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

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

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

【００２７】

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

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

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

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

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

【００３２】

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

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

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

【００３５】

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

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

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

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

【００３９】

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

【００４０】第１の発明 図１は第１の発明の概略処理手順を示すフローチャート
であり、これを実現するための詳細な処理手順は実施例
の最後に詳細処理手順ｓｔｅｐ０〜ｓｔｅｐ２１の形で
記述してある。以下、本発明の実施例を図２，図３及び
詳細処理手順ｓｔｅｐ０〜ｓｔｅｐ２１を利用しなが
ら、図１のフローチャートの流れに沿って説明する。

【００４１】ＳＴＡＲＴ後、まずＬＳＩのチップ領域を
カットラインによって２分割し、分割領域を作成する。
そして、それぞれの分割領域内のセルを仮決定し、初期
の配置状態を決定する。この初期配置は例えばランダム
なセル配置を採用しても良い（Ｓ１）。

【００４２】次に、（Ｓ１）で出来上がった初期分割に
於いて改良度を初期化し（ｓｔｅｐ０）、セルの混雑し
た分割領域を選択する（ｓｔｅｐ１）。次に、カットラ
インを通過するネット数を最も減少させる効果の高いセ
ルを混雑した領域内のセルから選択し（Ｓ２）、セルの
移動を実行して（Ｓ３）、改良度を累積する（ｓｔｅｐ
２）。次に、以前の配置状態との比較を行って改良度が
あれば配置状態を更新する（ｓｔｅｐ３）。

【００４３】次に、ｓｔｅｐ４〜ｓｔｅｐ６の改良収束
判定条件によって、上記（Ｓ２からＳ３）のような単独
のセル移動による配置改善処理を収束するまで行う。こ
れによって、最大ゲインのセル選択と当該セルの移動処
理が繰り返される。（Ｓ２〜Ｓ４）。

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

【００４５】次に、この様な局所的に最適な配置状態か
ら更に配置改善を進めるために、ｓｔｅｐ７〜ｓｔｅｐ
１４（Ｓ５〜Ｓ７）の手順に従ってダイナミックにセル
のクラスタを形成し、クラスタ単位で移動を試みる。そ
して、この当該クラスタの移動によって移動先の領域内
のセル充填率が許容範囲を越えた場合は、同様の手順ｓ
ｔｅｐ１５〜ｓｔｅｐ２１に従って動的に形成したクラ
スタと交換する。

【００４６】クラスタの形成方法としては、配置状態の
改善効果が高いセル（ゲインの高いセル、通常、複数個
ある）をひとたびキューに詰め込んで、これらのセルを
各クラスタの核の候補とし（ｓｔｅｐ９，ｓｔｅｐ１
６）、次に、このキューからクラスタの核となる候補セ
ルを一つ選び出して（ｓｔｅｐ１０，ｓｔｅｐ１７）、
当該セルにネット接続するセルを連鎖的に手繰り寄せ、
ゲインの高い順にソートされた状態のリストに追加する
事によってクラスタ（セル集合）を作成する（ｓｔｅｐ
１１，ｓｔｅｐ１３，ｓｔｅｐ１８，ｓｔｅｐ２０）。

【００４７】これにより、ある配置状態からネットの接
続関係で決定されるゲイン最大のクラスタが動的に抽出
できる。また、このクラスタの作成に於いては、分割さ
れた各領域内のセル充填率のバランスがクラスタの移動
／交換によって崩れないようにクラスタのサイズを調整
する（ｓｔｅｐ１２，ｓｔｅｐ１９）。

【００４８】以上のような処理手順によって、例えば図
２の様な配置状態から、セルＪ，Ｉ，Ｌ，Ｋで構成され
たセル集合を一纏めにして反対側の領域に移動した場合
の評価、及び、セルＯ，Ｍ，Ｐ，Ｎで構成されるセル集
合と交換した場合の評価等が行える。従って、ひとたび
図２の様な局所的に最適な配置解に陥っても、そこから
脱出して更に最適化を進める事ができ、この例の場合で
は結果的に図３の様な大局的な最適配置状態へと改良が
進む事になる。

【００４９】次に、上記処理手順によるゲイン最大のク
ラスタの生成（Ｓ５）、及びクラスタ化されたセル集合
毎の移動（Ｓ６）による改良が成功したか否かを判定す
る（Ｓ７）。改良に成功した場合は（Ｓ２）に戻って、
単独のセル移動による改良処理から上記クラスタ単位の
改良処理までを手順通りに繰り返す。失敗した場合は配
置最適化処理を止める。

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

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

【００５２】詳細処理手順 ｓｔｅｐ０：登録されている配置状態のカット数減少累
積値Ｇを０とする。 ｓｔｅｐ１：セルの混雑している領域Ｒを選択する。 ｓｔｅｐ２：Ｒの領域内から移動によって最もカット数
が減少するセルをカットラインの反対側へ移動して仮の
配置状態を作成し、カット数の減少値を累積Ｇする。 ｓｔｅｐ３：累積値Ｇが現在までのＧの値の最大値以上
であれば登録されている配置状態を更新する。

【００５３】ｓｔｅｐ４：全てのセルが移動済みか累積
下限値を下回るまでｓｔｅｐ１〜ｓｔｅｐ３を繰り返
す。 ｓｔｅｐ５：累積値Ｇの最大値が正であればｓｔｅｐ０
へ。 ｓｔｅｐ６：累積値Ｇの最大値が０で移動セルがあり、
セルの混雑している領域内の全てのセルの中にゲイン正
のセルがあればｓｔｅｐ０へ。

【００５４】ｓｔｅｐ７：登録されている配置状態のカ
ット数減少累積値Ｔを０とする。 ｓｔｅｐ８：セルの混雑している領域Ｒを選択する。 ｓｔｅｐ９：Ｒの領域内から移動によって最もカット数
が減少するセルをセルＱＵＥＱに挿入する。 ｓｔｅｐ１０：セルＱＵＥＱから一つセルを取り出しゲ
インソーテッドリストＬを初期化する。ＱがＮＵＬＬな
らＥＮＤ。

【００５５】ｓｔｅｐ１１：ゲインソーテッドリストＬ
から一つセルＣを取り出しカットラインの反対側へ移動
して仮の配置状態を作成し、カット数の減少値を累積Ｔ
する。 ｓｔｅｐ１２：セル総面積限界値を越えたらｓｔｅｐ１
０へ。 ｓｔｅｐ１３：累積値Ｔが正でなければセルＣにつなが
る同領域内の新規セルをＬに追加し、ｓｔｅｐ１１へ。 ｓｔｅｐ１４：セル充填率の差が許容範囲以下であれば
配置状態の登録を更新してｓｔｅｐ１０へ。

【００５６】ｓｔｅｐ１５：セルの混雑している領域Ｒ
を選択する。 ｓｔｅｐ１６：Ｒの領域内から移動によって最もカット
数が減少するセルをセルＱＵＥＵに挿入する。 ｓｔｅｐ１７：セルＱＵＥＵから一つセルを取り出しゲ
インソーテッドリストＬを初期化する。ＵがＮＵＬＬな
らｓｔｅｐ１０へ。

【００５７】ｓｔｅｐ１８：ゲインソーテッドリストＬ
から一つセルを取り出しカットラインの反対側へ移動し
て仮の配置状態を作成し、カット数の減少値を累積Ｔす
る。 ｓｔｅｐ１９：セル総面積限界値を越えたらｓｔｅｐ１
７へ。 ｓｔｅｐ２０：累積値Ｔが正でなければセルＣにつなが
る同領域内の新規セルをＬに追加しｓｔｅｐ１８へ。 ｓｔｅｐ２１：ｓｔｅｐ１４へ。

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

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

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

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

【００６２】スタート後、まずＬＳＩチップ領域をカッ
トラインで裁断して複数の矩形領域に仮分割する（Ｓ１
１）。これによって、チップ上は例えば図６の点線で示
されたように縦方向に２つ、横方向に２つに分割され、
合計４つの分割領域が構成される。

【００６３】次に、（Ｓ１１）で出来上がった各分割領
域内に於いてマクロブロック等の位置が固定されたセル
を控除して領域内の実質的な改良対象セル数を計算し、
ＥＣとする（Ｓ１２）。次に、仮分割で出来上がった各
分割領域内に於いて領域内部で接続するネット及び領域
外部へつながるネット数を計算し、それぞれＩＮ，とす
る（Ｓ１３）。次に、仮分割で出来上がった各分割領域
内に於いて領域内の目標とする配置評価値と現在の配置
評価値とのズレを計算し、ＤＦとする（Ｓ１４）。次
に、利用する計算機の性能及び現在の稼動（負荷）状況
を計算し、ＰＷ，ＬＤとする（Ｓ１５）。

【００６４】次に、（Ｓ１２）〜（Ｓ１５）によって求
めた値から、例えば次の計算式により負荷見積値Ｅを計
算して、この見積値が等しくなるように領域分割の修正
を繰り返し、各プロセッサへの割り付け領域を決定する
（Ｓ１６）。尚、計算式に於けるａ〜ｄは各項目の重み
係数である。これによって、ＬＳＩチップ上は例えば図
６の点線で示されたように分割領域が修正され、新たな
４つの分割か領域が決定される。

【００６５】

【数１】 （Ｓ１６）によってひとたび領域分割が決定した後は、
それらの各領域それぞれに対して別々の計算機（プロセ
ッサ）を割り付けて各領域内の配置改良処理を同時並列
に実行する（Ｓ１７）。ここでは、各プロセッサは自分
の担当する部分領域内についてのみ配置改良を繰り返す
ため、チップ全面の配置処理に比べて高速に配置改良を
図る事ができる。最後に、各プロセッサによる各領域内
の配置改良結果を回収してチップ全体の配置結果を合成
し。終了する。

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

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

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

【００６９】図１０のように、当該評価値の悪い順に並
列用領域６，９，３，５，４を各プロセッサー２０〜２
４に割当て並列に配置改良処理を行う。各プロセッサー
２０〜２４は各領域内での収束判定を当該評価値に基づ
き行い、収束が認められると領域内の配置改良を終了す
る。この場合、プロセッサー２０〜２４に領域を割り当
てる時に使用する評価値と当該領域の収束判定に使用す
る評価値は同一であるから、処理前の評価値の悪いもの
ほど処理に時間を要すると考えられる。

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

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

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

【００７３】

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

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

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

【図面の簡単な説明】

【図１】第１の発明の一実施例の処理手順を示すフロー
チャート。

【図２】第１の発明に対する従来技術の問題点を説明す
るための概略図。

【図３】第１の発明の一実施例を説明するための概略
図。

【図４】第２の発明における一実施例の処理手順を示す
フローチャート。

【図５】第２の発明における各プロセッサ間の関係を示
した概略構成図。

【図６】第２の発明における発明の実施例を説明する為
の図。

【図７】第３の発明における一実施例に係わる配置処理
手順を表わすフローチャート。

【図８】第３の発明における一実施例の並列用領域を示
す図。

【図９】第３の発明における一実施例の並列用領域毎の
評価値を示す図。

【図１０】第３の発明における一実施例のプロセッサー
毎の処理時間及び割り当てられた領域の関係を示す図。

【図１１】第３の発明に対する従来のプロセッサー毎の
処理時間及び割り当てられた領域の関係を示す図。

【図１２】第１及び第２の発明に対する従来技術の問題
点を説明するための概略図。

【図１３】第１及び第２の発明に対する従来の半導体集
積回路のチップ概略構成を示す図。

【符号の説明】

Ａ〜Ｘ セル １ レイアウト対象領域 ２〜１０ 並列用に設定した領域 ２０〜２４ プロセッサー

───────────────────────────────────────────────────── フロントページの続き (58)調査した分野(Int.Cl.⁷，ＤＢ名) H01L 21/82 G06F 17/50 H01L 21/822 H01L 27/04

Claims (7)

(57)【特許請求の範囲】
1. 【請求項１】 半導体集積回路のレイアウト設計に於い
   て、セルの配置位置を計算機を用いて自動的に決定する
   際に、ＬＳＩのチップ領域を分割して複数の領域を構成
   する工程と、分割された領域間を通過するネット数が当
   該セルの移動或いは交換によって減少するセルを選択し
   て配置位置を改善する工程と、分割された領域間を通過
   するネット数が当該セル集合の移動或いは交換によって
   減少するセル集合を選択して配置位置を改善する工程と
   を含み、分割された領域へのセル配置を最適化する事を
   特徴とする論理セルの並列配置処理方法。
2. 【請求項２】 前記セルを選択する工程は、分割された
   領域間を通過するネット数が当該セルの移動或いは交換
   によって最も減少するセルを選択して配置位置を改善す
   る事を特徴とする請求項１記載の論理セルの並列配置処
   理方法。
3. 【請求項３】 前記セル集合を選択する工程は、分割さ
   れた領域間を通過するネット数が当該セル集合の移動或
   いは交換によって最も減少するセル集合を選択して配置
   位置を改善する事を特徴とする請求項１記載の論理セル
   の並列配置処理方法。
4. 【請求項４】 移動或いは交換を施す前記セル集合を発
   見する際に、セルを選択する工程で選択されたセルから
   ネットで接続しているセルを連鎖的に手操る事によって
   セル集合を決定する事を特徴とする請求項１あるいは２
   記載の論理セルの並列配置処理方法。
5. 【請求項５】 半導体集積回路のレイアウト設計に於い
   て、セルの配置位置を計算機を用いて自動的に決定する
   際に、ＬＳＩのチップ領域を分割して複数の領域を構成
   する工程と、分割された領域間を通過するネット数が当
   該セルの移動或いは交換によって減少するセルを選択し
   て配置位置を改善する工程と、この工程の後に分割され
   た領域間を通過するネット数が当該セル集合の移動或い
   は交換によって減少するセル集合を選択して配置位置を
   改善する工程とを含み、分割された領域へのセル配置を
   最適化する事を特徴とする論理セルの並列配置処理方
   法。
6. 【請求項６】 計算機を用いて半導体基板上に複数のセ
   ルを自動的に配置する方法に於いて、ＬＳＩのチップ領
   域を裁断して複数の領域に分割し、それぞれの領域内の
   セル配置改良処理を複数の計算機を利用して同時並列に
   実行させる際に、前記分割領域内においてマクロブロッ
   ク等の位置が固定されたセルを控除して領域内の実質的
   な改良対象セルを計算する工程と、前記分割領域内部で
   接続するネット及び分割領域外部へつながるネット数を
   計算する工程と、前記分割領域内の目標とする配置評価
   値と現在の配置評価値とのズレを計算する工程と、利用
   する計算機の性能及び負荷状況を計算する工程とを行な
   ってチップ領域の分割方法を決定し、前記各分割領域内
   の配置改良処理時間を均一化させる事を特徴とする論理
   セルの並列配置処理方法。
7. 【請求項７】 半導体集積回路の自動レイアウトシステ
   ムにおいて、対象領域を複数個の領域に分割し、並列に
   セルの配置改良を行うに際し、前記各領域のセルの集合
   が配置されている状態に基づいて評価値を算出し、その
   評価値を基に並列処理用領域をプロセッサーに割り当て
   る事を特徴とする論理セルの並列配置処理方法。