JP2736104B2 - 半導体集積回路の論理セルの配置方法 - Google Patents

Description

【発明の詳細な説明】 ［発明の目的］ （産業上の利用分野） 本発明は、半導体チップ内に論理セルを多数配列，集
積してなる半導体集積回路のコンピュータを用いた自動
レイアウトにおける、論理セルの配置方法に関する。

（従来の技術） ゲートアレイ方式（或いは、マスタースライス方式と
もいわれる）は、半導体集積回路装置の設計手法として
知られている。この方式は、マスターチップ上に一定数
のトランジスタからなるベーシックセル及び入出力セル
を規制正しく並べ、ユーザの仕様に合うようにこれらゲ
ート間を配線し、所望の機能を持つLSIを構成させるも
のである。

一般に、ベーシックセルが並べられているだけの配線
工程前のウェハをマスターウェハと呼び、これに配線を
施設し個々のLSIとしての機能を持たせることをパーソ
ナライズと呼んでいる。

ゲートアレイではベーシックセルを複数個使用し、配
線することによって、インバータ,NAND及びフリップフ
ロップ等をセルとして自由に実現できる。これら標準的
に使用するセルの配線パターン（これをマクロセルと呼
ぶ）は全てライブラリとして多数用意されていて、それ
を使うことによって効率の良い設計を行うことができ
る。

第８図は、マスターウェハのチップの例を示す。チッ
プ21の内部にはベーシックセル23が縦横両方向に隙間な
く並べられており、チップ周囲にはI/Oセル配置領域24
が設けられ、ここにI/Oセルが並べられている。ユーザ
は、実現すべきLSIの回路に合わせて必要な種類のマイ
クロセルを必要な数だけベーシックセルのアレー領域22
上に配置し、回路接続情報に従ってセル上の端子を配線
することによってパーソナライズを行うことができる。

ところで、高集積かつ大規模なゲートアレーの配置配
線処理では人手による設計はもはや困難であり、通常、
コンピュータを用いた自動配置配線処理の手法が採られ
ている。このうち、チップ上でのアクロセルの配置位置
を決定する自動配置処理は、大別して初期配置の段階と
配置改良の段階との２つに分けられる。後者の配置改良
処理の手法としては従来より幾つかの提案がなされてい
て、そのアルゴリズムの目的関数としては次の 配線長の最小化 貫通配線本数の最小化 配線混雑度の均一化 のいずれかをとるのが一般的である。

の例としては、FDR法（文献:Hanan,M.,Wolff,P.K.a
nd Anguli,B.J.,“Some Experimental Results on Plac
ement Techniques",Proc.13th Design Automation Conf
erence,PP.214−224,1976）がある。このFDR法は、セル
の接続関係をセル同士が引き合う張力で表現し、この張
力を緩和するようなセル交換又は移動を実施することに
より、全体の配線長を最小化をさせようとするものであ
る。

の例としては、MIN−CUT法（文献:M.A.Breuer,“MI
N−CUT Placement",Proc.Journal of Design Automatio
n and Fault−Tolerant Computing,October,PP.343−36
2,1977）がある。このMIN−CUT法は、仮想的に入れたチ
ップ領域の分割ラインを横切る信号線の数（これをカッ
ト数と呼ぶ）を少なくするようなセル交換を実施するこ
とにより、全体のカット数を最小化させようとするもの
である。

しかし、，いずれの方法を用いてもチップ上で局
所的な配線要求の集中を生じ配線実行が困難になる等、
ゲートアレーの配置としては不適当な場合が多々見られ
た。ゲートアレーの自動配置配線処理では、全てのセル
を未結線やショート等を生ずること無く配線することが
強く望まれる。この配線率100％を目指した手法がの
手法である。

の例の１つとして、MAX−CATMIN法（文献:H.Shirai
shi,F.Hirose,“Efficient Placement and Routing Tec
hniques for Master Slice LSI",Proc.17th Design Aut
omationConference,PP.458−464,1980）がある。このMA
X−CUT MIN法は、最もカット数の多いカットラインの
カット数を減少させる手法である。

しかし、この手法では各カットラインに対する配線要
求を許容値以下に抑えることはできても、更に細かいレ
ベルでの配線の容易化をはかることは難しく、十分な配
線率向上の効果が得られなかった。また、上記に示した
手法は仮想的な配線経路を見積るために特定の配線モデ
ル（ネットモデルという）を用いるため、使用するネッ
トモデルによって配線結果が大きく変わるという問題が
ある。このネットモデルの選択は自動配置の性能を大き
く左右するため重要であるが、厳密なモデルを用いるほ
ど処理時間が増大し、処理も複雑化する等の問題点があ
る。

これらの問題を回避する方法として、接続ピンをチッ
プ上で均一な密度に分布させるという手法がある（文
献:U.Schulz,Rainer Zuhlke,“A Study on Bipolar VLS
I Gate−Arrays Assuming Four Layers of Metal",Pro
c.IEEE JOURNAL OF SOLID−STATE CIRCUITS,VOL.SC−1
7,No.3,PP.472−480,1982）。配線の分布と接続ピンの
分布との間には強い相関関係があり、チップ上の配線要
求を均一化させることは接続ピンを均一化させることに
ほぼ等しい。しかし、単純に接続ピンを均一に分散させ
るだけでは配線の容易化の効果を十分に上げることはで
きない。これは、実際のセルには配線敷設に利用できな
い部分（以下これを禁止領域と呼ぶ）が含まれているこ
とやセルの大きさが種々である等、配線分布と接続ピン
分布との間の相関関係を弱める因子が存在することによ
る。

（発明が解決しようとする課題） このように従来、配線長又は貫通配線本数を最小化す
る手法は処理が複雑であるばかりでなく、配線の局所的
な集中を招き、結線率を思うように向上できなかった。
また、配線混雑度を均一化する手法は、処理時間の増大
及び処理の複雑化を招き、さらにチップ上の接続ピンの
分布を均一化させる手法においても配線混雑度緩和の効
果は不十分であった。

本発明は、上記事情を考慮してなされたもので、その
目的とするところは、局所的な配線の混雑度を効率良く
緩和し、結線率の向上をはかるための半導体集積回路の
論理セルの配置方法を提供することにある。

［発明の構成］ （課題を解決するための手段） 本発明では、チップ上に配置すべき全てのセルはセル
外形を取り払い、禁止領域と接続ピンに展開して取り扱
う。また、既配線等の配線領域として利用できない部分
についても禁止領域として扱う。ここで、禁止領域も接
続ピンもいずれも領域を占有するという観点から見る
と、同等に扱うことができる。このとき、禁止領域はそ
の面積の大きさに応じた等価的な接続ピン数で表現し、
接続ピンと等価に扱う。但し、接続ピンの占有面積は接
続するであろう配線の占有面積を考慮する必要があるの
で、配線処理と無関係に面積が決定される禁止領域とは
全く同等に取り扱うことはできない。このため、禁止領
域面積を接続ピンに変換する際には、重み付けを行い等
価ピンに置換する。次に、チップを格子状に分割し、各
格子間で配置可能領域に対する上記接続ピン数と等価ピ
ン数との和の比率を均一化させることによって、チップ
上の各所での配線混雑度の均一化をはかる。

これに加えて本発明では、格子状に分割されたチップ
に対し複数の格子からなるボックス領域を設定（ピンボ
ックスと呼ぶ）し、各ピンボックス内の格子間で配置可
能領域に対する接続ピンと禁止領域との和の分布を均一
化させる。各ピンボックス内の分布が均一化し、収束し
た後、次にピンボックスの設定を変えて再び各ピンボッ
クス内に関して前記処理を繰り返す。このピンボックス
の設定を変化させたピンボックス内の分布の均一化処理
は、チップ全体の接続ピンと配置禁止領域の分布が均一
化されるまで行われる。

即ち、本発明に関わる半導体集積回路の論理セルの配
置方法は、チップ上に配置すべきセル，既配置のセル及
び既配線を接続ピンと配線禁止領域とに展開したのち、
配線禁止領域を接続ピンと等価に扱うための変換処理を
施して該配線禁止領域を等価ピンに置換し、次いでチッ
プを格子状に分割すると共に、所定数の格子を含む複数
のボックス領域を指定し、次いで各ボックス領域内で格
子間における配置可能領域に対する接続ピン数と等価ピ
ン数との和の比率を均一化させることを特徴とする。

（作用） 本発明によれば、配置可能領域に対する接続ピンと禁
止領域をチップ上で均一に分布させるため、配線混雑度
の局所的な増大を避けることができ、結線率が向上す
る。また、ネットモデルを用いた仮想的な配線経路の見
積を行う必要がないため、レイアウトを行う回路の特性
に依存すること無く配置を実行することができる。さら
に配線分布を直接操作しないことで処理を簡略化でき、
処理の高速化が可能である。

これに加えて本発明では、接続ピンと禁止領域の分布
の均一化処理を限定した範囲内（ボックス領域内）で行
うため、カット数の増加を極力抑えつつ、局所的な配線
混雑度の緩和を行うことができる。また、一度に扱うデ
ータ量をボックス領域内の格子数に限ることができるの
で、処理をより高速化することが可能である。

（実施例） まず、実施例を説明する前に、本発明の基本となる論
理セルの配置方法（特願昭63−300905号）について、説
明する。

第４図はこの方法による自動配置処理の全体のフロー
チャートを示す。処理の開始後、初期配置処理について
は従来処理と同様であり、これによって使用するセルは
全てチップ上に置かれる（第４図f₀）。以下では、この
初期配置状態をもとに本発明が特徴とする配置改良処理
を行う。

まず、チップ上に配置された全てのセルを、そのセル
が持つ接続ピンと禁止領域に展開する。同様に、チップ
上の既配線等の新たに配線敷設に利用できない部分も、
禁止領域として表す（第４図f₁）。これら配線領域とし
て利用できない禁止領域を、それぞれの禁止領域の面積
に対応して仮想的な接続ピンの数で表現する（第４図
f₂）。この禁止領域を仮想的な接続ピン（等価ピン）に
変換する方法は後述するが、これにより配線混雑度に影
響を及ぼす因子である接続ピンと禁止領域を同時に取り
扱うことができる。次に、チップを格子状に分割し、各
格子毎の配置可能領域を見積ると共に、各格子内に含ま
れる接続ピン数と等価ピン数との和（以下、単に等価ピ
ン数と称す）を求める（第４図f₃）。

以上により、各格子毎の配置可能領域に対する等価ピ
ン数の分布を知ることができ（第４図f₄）、この等価ピ
ン分布マップをもとにそのバラツキからチップ上のセル
の配置状態を具体的に評価することができる。この各格
子毎の等価ピンのバラツキが予め設定しておく特定の許
容値以内に収まったとき配置改良処理を抜けて、個々の
セルの配置位置等を登録して処理を終了する（第４図
f₅,f₁₁）。各格子毎の等価ピン数のバラツキが設定した
許容値よりも大きいときは、以下の配置状態改良処理を
行う。

等価ピン数の最も多い格子内からセルをランダムに抽
出し、この格子に隣接する他の格子内へ移動させる。仮
に、抽出したセルが何らかの理由で移動不可能な場合に
は、同格子内よりそのセルを除いたものの中から再びラ
ンダムに抽出し、移動を試みる（第４図f₆〜f₉）。セル
の移動先の決定に関しては後述する。移動が実行されれ
ば、当該格子内の等価ピン等は減じられ、配線混雑度を
軽減させることができる。セルの移動が実行された場
合、移動に関係した格子に関して格子内の等価ピン数の
更新を行う（第４図f₁₀）。これは、セル移動によって
変化した等価ピン分布マップを、処理の次のサイクルに
反映させるためである。そして、第４図f₅における終了
判定条件を満たすまで、第４図f₆〜f₁₀の処理を繰り返
す。この一連の処理によって、格子毎に等価ピン分布を
均一化することができる。

なお、禁止領域の仮想的なピンへの変換は、第５図で
示すように行う。即ち、禁止領域10の面積を、垂直配線
格子７と水平配線格子８で決定される配線グリッド数単
位で評価し、この面積を等価的なピン数と考える。図中
のP_H,P_Vは、それぞれの配線方向の配線ピッチである。
このとき、各格子毎の配置可能領域に対する等価ピン分
布は、次式を用いて計算する。

EP_IJ ：配置可能領域に対する等価ピン数 G_PLACE :配置可能領域の面積 G_OBS ：禁止領域の面積（等価ピン数） G_PIN ：ピン数 Ｋ ：定数（０＜ｋ＜１） 添字ij ：格子番号 添字LAY :配線層 ここで、定数Ｋは禁止領域10を接続ピン９と等価に扱
うために用いる係数である。一般に、接続ピン９の占有
面積は禁止領域10のそれと比較して小さいが、接続ピン
９に配線がつながった場合を考えるとその占有面積は禁
止領域10と同等若しくはそれ以上となる。第６図の例で
は、接続ピン９が占める配線グリッド数は２であり、禁
止領域10が占める配線グリッド数は９である。ところ
が、図中のような配線11が敷設された場合、格子内で接
続ピン９とそれにつながる配線11とが占有する面積は配
線グリッドと数で10となる。セル12の移動先の決定は、
第７図で示すように隣接する８つの格子内とする。この
８つの格子の中から、第４図f₄で作成しした等価ピン分
布マップをもとに分布が最も疎である格子を探索し、こ
れを移動先の第１候補とする。以下、分布が疎である順
に隣接する格子を順位付けするわけであるが、第３〜４
候補程度までを実際の移動先の候補として決定しておけ
ばよい。セルの移動は、まず、移動先の第１候補となっ
た格子に対して試みられ、この移動が不可能な場合には
下位の候補となっている格子を順に試行する。

第７図の例では、格子（i,j）が等価ピン分布マップ
の最大値を持ち、その他（ｉ−1,j−１）〜（ｉ＋1,j＋
１）の８つの格子はそれに隣接する格子である。隣接す
る格子内の数字は、移動先候補としての順位を表してい
る。格子（i,j）から抽出されたセルは、最初に、格子
（ｉ＋1,j＋１）への移動が試みられ、これが受け入れ
られれば次の処理ステップへと進むがそうでない場合に
は、格子（i,j＋１）、更には、格子（ｉ＋1,j−１）へ
の移動が試みられる。

上記に用いた格子は、使用する最大のマクロセルを十
分に収容できる程度の大きさを設定する。また、この格
子サイズは、終始一定の大きさに設定する必要はなく、
処理の収束とともに微細化していってもよい。

ところで、上述した方法では、セル移動に伴いカット
数が大きく増加する場合があり、配線の容易化をはかる
上でその効果が十分ではない。また、常にチップ上の全
ての格子が評価，改良の対象となっており、内部データ
の更新等にかなりの時間を要し、処理時間を長くする虞
れがある。

そこで本実施例では、以下に説明する方法により、総
カット数の増加を極力抑え、効率良く局所的な配線の混
雑度を緩和している。

第１図は、本発明の一実施例による自動配置処理の全
体のフローチャートを示す。処理の開始後、全てのセル
及び既配線等を接続ピンと配線禁止領域とに展開し、チ
ップ上を格子状に分割する。さらに、各格子に関して配
線可能領域に対する等価ピンの分布状況を求める（第１
図P₀,P₁）。ここまでは、前記第４図の処理方法と同様
である。

このとき、各格子間の等価ピンのバラツキが許容値以
下であればこの時点で処理を終了するが（第１図P₂,
P₈）、そうでなければ以下の改良処理を行う。

本実施例は、格子状に分割されたチップを更に複数の
格子より構成される目の粗い格子であるピンボックス
（ボックス領域）で分割して、各ピンボックス毎に処理
を行うものである。設定するピンボックスの大きさとし
ては、例えば格子数で２×２〜５×５程度にとればよい
（第１図P₃）。第２図にはチップ左下点を基準として、
格子サイズで２×２のピンボックスを設定した例を示し
てあり、チップ上に設定されたピンボックスの数は16と
なっている。

このピンボックスに関して等価ピンの分布状況を評価
した後（第１図P₄）、等価ピンの分布状況が許容値を越
えているものに対して、ピンボックス内でセル移動を行
うことにより、ピンボックス内の格子間の等価ピンのバ
ラツキを緩和する（第１図P₅〜P₇）。このとき、移動候
補セルの選択と移動先の決定方法は前記第４図の処理方
法と同様でよい（第１図P₆）。各ピンボックスに関して
等価ピン分布の改善を行った後、チップ全体について格
子間のピンの分布状況を評価する。その結果、更に改良
の必要があると判断した場合には再び第１図P₅〜P₇の処
理を繰り返すわけであるが、セルの移動はピンボックス
をまたいで行われないので、全体の均一化をはかるため
にはピンボックス内に含まれる格子メンバーを何等かの
手法で変えてやる必要がある。

第３図の例は、ピンボックスの設定位置を格子単位で
移動させることによって最初の設定と違ったピンボック
スをチップ上に実現しようと試みたものである。同図
は、チップの左下点にピンボックスを置いたときにその
ピンボックス内に含まれる格子点（第３図中のａ〜ｉ）
のいずれかに、ピンボックスを形成するマクロ格子の格
子点が一致するようにランダムに変化させようとするも
のである。この例では、格子点ｅにマクロ格子の格子点
が一致するように設定されている。ここで、ピンボック
スは全てのチップ領域をカバーするように設定されなけ
ればならない。このようにピンボックスの設定を変えて
行くことにより、最初のピンボックスの設定では行われ
なかった格子間でセル移動を実行することができる。

以下、ピンボックスの設定を更新しつつ、上記ピンボ
ックス内の等価ピンのバラツキを小さくしていくことで
チップ全体の等価ピン分布の均一化をはかって行き、最
終的に各格子間のバラツキが許容値以内に収まるまで第
１図P₁〜P₇までの処理を繰り返す。

このとき、セル移動はピンボックスサイズ程度に限定
されるため、本処理によって著しくカット数が増加する
ことはない。更に、各ピンボックス内には高々数十個程
度の格子数しか含まれていないため、移動候補セルの選
択および移動先の決定等の作業を高速に行うことができ
る。１つのピンボックス内の処理時間は単にピンボック
ス内の格子数のみに依存し、また、全体の処理時間は設
定したピンボックスの数に比例して増大する。

かくして本実施例によれば、配置可能領域に対する接
続ピン数と等価ピン数との和をチップ上で均一に分布さ
せるため、配置混雑度の局所的な増大を避けることがで
き、結線率を大幅に向上させることができる。これに加
えて、接続ピンと等価ピンの分布の均一化処理をピンボ
ックス単位で行うため、カット数の増加を極力抑えつ
つ、局所的な配線混雑度の緩和を行うことができる。さ
らに、一度に扱うデータ量をボックス領域内の格子数に
限ることができるので、処理をより高速化し得る等のに
利点がある。

なお、本発明は上述した実施例に限定されるものでは
ない。例えば、前記ピンボックスの大きさは２×２に限
るものではなく、仕様に応じて適宜変更可能である。ま
た、チップ全体の等価ピン分布の均一化をはかるため
に、ピンボックスを移動する代わりにピンボックスの大
きさを可変するようにしてもよい。さらに、ピンボック
スの移動及び大きさ可変の双方を行って、より均一性を
高めることも可能である。その他、本発明の要旨を逸脱
しない範囲で、種々変形して実施することができる。

［発明の効果］ 本発明によれば、ゲートアレー方式等の半導体集積回
路の配置処理において、カット数を著しく増加させるこ
となく効率的に局所的な配線混雑度の緩和を行い、後処
理での配線を容易化し、もって大規模論理集積回路チッ
プの結線率を向上させることができる。

【図面の簡単な説明】

第１図乃至第３図はそれぞれ本発明の一実施例に係わる
論理セルの配置方法を説明するためのもので、第１図は
全体の処理手順を示すフローチャート、第２図はチップ
上のピンボックス設定例を示す図、第３図はピンボック
スの設定変更（移動）を示す図、第４図乃至第７図はそ
れぞれ本発明の基本となる論理セル配置方法を説明する
ためのもので、第４図は全体の処理手順を示すフローチ
ャート、第５図は禁止領域面積の等価的なピン数への変
換方法を示す図、第６図は禁止領域の等価ピンへの変換
を示す図、第７図はセル移動先を示す図、第８図はゲー
トアレイ方式のチップのセル配置例を示す概略図であ
る。 １……水平格子辺、２……垂直格子辺、３……格子、 ４……ピンボックス、７……垂直配線格子、 ８……水平配線格子、９……接続ピン、 10……禁止領域、11……配線、12……セル。

Claims (3)

(57)【特許請求の範囲】
1. 【請求項１】半導体チップ上に複数の論理セルを配置
   し、各論理セル間を配線することにより所望の回路を実
   現する半導体集積回路の論理セルの配置方法において、 前記チップ上に配置すべきセル，既配置のセル及び既配
   線を接続ピンと配線禁止領域とに展開する工程と、 前記配線禁止領域を前記接続ピンと等価に扱うための変
   換処理を施して、該配線禁止領域を等価ピンに置換する
   工程と、 前記チップを格子状に分割すると共に、所定数の格子を
   含む複数のボックス領域を指定する工程と、 前記各ボックス領域内で、格子内の配置可能領域に対す
   る前記接続ピン数と等価ピン数との和の比率を、各格子
   間で均一化させる工程とを含むことを特徴とする半導体
   集積回路の論理セルの配置方法。
2. 【請求項２】半導体チップ上に複数の論理セルを配置
   し、各論理セル間を配線することにより所望の回路を実
   現する半導体集積回路の論理セルの配置方法において、 前記チップ上に配置すべきセル，既配置のセル及び既配
   線を接続ピンと配線禁止領域とに展開する工程と、 前記配線禁止領域を前記接続ピンと等価に扱うための変
   換処理を施して、該配線禁止領域を等価ピンに置換する
   工程と、 前記チップを格子状に分割すると共に、所定数の格子を
   含む複数のボックス領域を指定する工程と、 前記各ボックス領域内で、格子内の配置可能領域に対す
   る前記接続ピン数と等価ピン数との和の比率を、各格子
   間で均一化させる工程と、 前記チップの全体について、各格子間での前記均一化の
   評価値が許容範囲内であるか否かを判定する工程と、 前記評価値が許容範囲内であるときは処理を終了し、前
   記評価値が許容範囲内でないときは前記ボックス領域を
   移動して前記均一化処理工程に戻る工程とを含むことを
   特徴とする半導体集積回路の論理セルの配置方法。
3. 【請求項３】半導体チップ上に複数の論理セルを配置
   し、各論理セル間を配線することにより所定の回路を実
   現する半導体集積回路の論理セルの配置方法において、 前記チップ上に配置すべきセル，既配置のセル及び既配
   線を接続ピンと配線禁止領域とに展開する工程と、 前記配線禁止領域を前記接続ピンと等価に扱うための変
   換処理を施して、該配線禁止領域を等価ピンに置換する
   工程と、 前記チップを格子状に分割すると共に、所定数の格子を
   含む複数のボックス領域を指定する工程と、 前記各ボックス領域内で、格子内の配置可能領域に対す
   る前記接続ピン数と等価ピン数との和の比率を、各格子
   間で均一化させる工程と、 前記チップの全体について、各格子間での前記均一化の
   評価値が許容範囲内であるか否かを判定する工程と、 前記評価値が許容範囲内であるときは処理を終了し、前
   記評価値が許容範囲内でないときは前記ボックス領域の
   大きさを変えて前記均一化処理工程に戻る工程とを含む
   ことを特徴とする半導体集積回路の論理セルの配置方
   法。