(57)【要約】【課題】本発明は、計算機処理により必要最小限の数のリピータを適切な位置に挿入する方法を提供することを目的とする。【解決手段】リピータ挿入方法は、半導体チップのレイアウトにおける複数のセルの物理的配置情報に基づいて、セル間の距離の近さに応じて複数のセルをグループ化し１つ又は複数のグループを生成するグループ化段階と、物理的配置情報に基づいて、１つ又は複数のグループ毎に必要なリピータ数及びリピータの物理的配置位置を決定するリピータ挿入段階を含むことを特徴とする。【選択図】　　　　図１
2004126904.tif 000002
【特許請求の範囲】
【請求項１】
半導体チップのレイアウトにおける複数のセルの物理的配置情報に基づいて、セル間の距離の近さに応じて該複数のセルをグループ化し１つ又は複数のグループを生成するグループ化段階と、
該物理的配置情報に基づいて、該１つ又は複数のグループ毎に必要なリピータ数及びリピータの物理的配置位置を決定するリピータ挿入段階
を含むことを特徴とするリピータ挿入方法。
【請求項２】
該複数のセルはソースセルと複数のシンクセルを含み、該グループ化段階は、該ソースセルから各シンクセルまでの距離と該ソースセル周りの各シンクセルの角度とに基づいて該距離及び該角度が互いに近いセル同士をグループ化することにより、該１つ又は複数のグループを生成することを特徴とする請求項１記載のリピータ挿入方法。
【請求項３】
該リピータ挿入段階は、該ソースセルから各シンクセルまでの距離に関わらず該角度が近い複数のグループを纏めることで、該纏められた複数のグループ間で少なくとも一つのリピータを共有させる段階を更に含むことを特徴とする請求項２記載のリピータ挿入方法。
【請求項４】
該リピータ挿入段階は、該１つ又は複数のグループ毎に該ソースセルからの距離に応じて挿入するリピータ数を決定することを特徴とする請求項２記載のリピータ挿入方法。
【請求項５】
半導体チップのレイアウトにおける複数のセルの物理的配置情報に基づいて、セル間の距離の近さに応じて該複数のセルをグループ化し１つ又は複数のグループを生成するグループ化ユニットと、
該物理的配置情報に基づいて、該１つ又は複数のグループ毎に必要なリピータ数及びリピータの物理的配置位置を決定するリピータ挿入ユニット
を含むことを特徴とするリピータ挿入装置。
【請求項６】
該複数のセルはソースセルと複数のシンクセルを含み、該グループ化ユニットは、該ソースセルから各シンクセルまでの距離と該ソースセル周りの各シンクセルの角度とに基づいて該距離及び該角度が互いに近いセル同士をグループ化することにより、該１つ又は複数のグループを生成することを特徴とする請求項５記載のリピータ挿入装置。
【請求項７】
該リピータ挿入ユニットは、該ソースセルから各シンクセルまでの距離に関わらず該角度が近い複数のグループを纏めることで、該纏められた複数のグループ間で少なくとも一つのリピータを共有させるグループ結合ユニットを更に含むことを特徴とする請求項６記載のリピータ挿入装置。
【請求項８】
該リピータ挿入ユニットは、該１つ又は複数のグループ毎に該ソースセルからの距離に応じて挿入するリピータ数を決定することを特徴とする請求項６記載のリピータ挿入装置。
【請求項９】
半導体チップのレイアウトにおける複数のセルの物理的配置情報に基づいて、セル間の距離の近さに応じて該複数のセルをグループ化し１つ又は複数のグループを生成するグループ化段階と、
該物理的配置情報に基づいて、該１つ又は複数のグループ毎に必要なリピータ数及びリピータの物理的配置位置を決定するリピータ挿入段階
を実行するためのプログラム。
【請求項１０】
該複数のセルはソースセルと複数のシンクセルを含み、該グループ化段階は、該ソースセルから各シンクセルまでの距離と該ソースセル周りの各シンクセルの角度とに基づいて該距離及び該角度が互いに近いセル同士をグループ化することにより、該１つ又は複数のグループを生成することを特徴とする請求項９記載のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に半導体チップレイアウトのタイミング設計方法に関し、詳しくは半導体チップレイアウトのタイミング設計において遅延を解消するためにリピータを挿入する方法に関する。
【従来の技術】
半導体チップの回路設計においては、回路を伝播する信号の必要なタイミング条件を満足させるために、タイミング検証を繰り返し行いながらタイミングエラー情報をフィードバックすることで、論理設計及びレイアウトを調整していく。接続するセル間の距離が長い回路レイアウトの場合やファンアウトが多い回路レイアウトの場合、配線負荷により遅延が生じ、タイミングエラーが発生してしまう。このようなタイミングエラーを解消するためには、リピータ（バッファ）を挿入して配線を分割し、配線負荷を軽くすればよい。
【０００２】
リピータを挿入する際に、既にレイアウトされている配線経路はそのまま変更せずに使用し、その経路上にリピータを配置することで配線を分割する方法がある。しかしこの方法でリピータを挿入しても、配線経路が迂回している場合等には、遅延を改善する最適な対策とはならない。そこで現状では、レイアウト上でエラーに関連するセルの位置関係を確認し、マニュアル作業で配線経路を変更し且つリピータを挿入している。
【０００３】
また特許文献１には、配線上に有する各ノード毎に配線抵抗と配線容量との関係を表したｒ−ｃグラフを作成し、作図的にリピータの挿入数および挿入位置を計算する技術が開示されている。これにより、複雑な構成を有する集積回路においても、実際の配線に沿ったリピータ挿入の最適解を正確かつ短時間で得ることができるようにしている。
【０００４】
【特許文献１】
特開２００１−２６５８４３号公報
【発明が解決しようとする課題】
このように従来のタイミング調整はマニュアル作業で行われるために、処理の精度が悪く、またレイアウト及びタイミング検証の工程を繰り返し実行するために処理時間がかかってしまう。半導体チップの回路規模が増大し、また動作速度が高速になるに従い、レイアウト後のタイミング調整が更に困難になり、タイミングエラーを収束させるまでの処理時間増大が問題となっている。
【０００５】
以上を鑑みて、本発明は、計算機処理により必要最小限の数のリピータを適切な位置に挿入する方法を提供することを目的とする。
【課題を解決するための手段】
本発明によるリピータ挿入方法は、半導体チップのレイアウトにおける複数のセルの物理的配置情報に基づいて、セル間の距離の近さに応じて該複数のセルをグループ化し１つ又は複数のグループを生成するグループ化段階と、該物理的配置情報に基づいて、該１つ又は複数のグループ毎に必要なリピータ数及びリピータの物理的配置位置を決定するリピータ挿入段階を含むことを特徴とする。
【０００６】
上記方法によれば、セルの物理的配置情報に基づいて距離が近いセル同士を纏めるようにグループ化し、グループ毎にリピータを挿入するので、必要最小限な程度にまでリピータの個数を少なくし且つ適切な位置に挿入することが可能である。また物理的配置情報に基づいてリピータ数及びリピータの物理的配置位置を自動的な計算処理により決定することが出来るので、レイアウト設計とタイミング検証のイタレーション数を少なくしてタイミング調整処理を短時間で効率的に実行することが可能となる。
【発明の実施の形態】
以下に、本発明の実施例を添付の図面を用いて詳細に説明する。
【０００７】
本発明によるリピータ挿入方法においては、挿入するリピータ数を最小限に抑えるために、物理的な配置位置が互いに近いシンクセル（信号受信側の回路素子）を１つのグループに纏め、同一グループに属するシンクセルを同一のリピータに接続する。グループ化をする際のパラメータとしては、ソースセル（信号送信側の回路素子）からシンクセルまでの距離、及びソースセル周りの回転角として与えられるシンクセルの角度を用いる。
【０００８】
ここで距離パラメータとしては、実際の配線が縦横のグリッドに沿ってレイアウトされることを考慮して、マンハッタン距離を用いる。物理的な配置位置が互いに近いシンクセルを１つのグループに纏めるために、複数のシンクセルを同一グループとするための１つの条件として、所定の距離範囲の内部にそれらのシンクセルが存在することとする。また角度パラメータについては、複数のシンクセルを同一グループとするための１つの条件として、所定の角度範囲の内部にそれらのシンクセルが存在することとする。
【０００９】
ソースセルを基点として、所定距離Ｌ以内に存在するシンクセルを距離グループ１、所定距離Ｌ以遠で２Ｌより近い位置に存在するシンクセルを距離グループ２、２Ｌ以遠で３Ｌより近い位置に存在するシンクセルを距離グループ３といったように、所定距離Ｌ毎に領域を分割していくことにより距離グループを設定する。同一の距離グループ内にあるシンクセルは、所定の角度範囲内に存在する互いに近いシンクセルが同一の角度グループに属するようにグループ化される。この際、上記所定の角度範囲を距離グループに応じて変化させ、距離グループ１に対しては所定角度／１、距離グループ２に対しては所定角度／２、距離グループ３に対しては所定角度／３とする等してよい。このように距離が遠くなるほど角度を小さくすることで、異なる距離グループ間でもグループ面積が略一定となるように構成することが出来る。
【００１０】
図１は、本発明によるリピータ挿入処理を示すフローチャートである。
【００１１】
図１のステップ１−１で、リピータ挿入対象となる回路レイアウトのソースセルとシンクセルの配置座標をレイアウト情報より抽出する。
【００１２】
ステップ１−２で、ステップ１−１で抽出した各セルの配置座標を基に、基点となるソースセルからのマンハッタン距離と角度を各シンクセルについて算出する。
【００１３】
ステップ１−３で、ステップ１−２で算出したソースセルからのマンハッタン距離に基づいて所定距離Ｌ毎に区切り、シンクセルを距離グループにグループ化する。
【００１４】
ステップ１−４で、未処理の距離グループがあるか否かを判定する。未処理の距離グループがある場合には、ステップ１−５に進む。以降のステップ１−５乃至１−１３は、ステップ１−３で画定した複数の距離グループから１つの距離グループを選択し、選択された距離グループに対して実行する。この処理を、複数の距離グループ全てに対して終了するまで繰り返して実行する。
【００１５】
ステップ１−５で、各シンクセルについて、当該シンクセルから所定角度範囲内でプラス方向（反時計回り）とマイナス方向（時計回り）との両方向にサーチし、その範囲内に含まれるシンクセルの数を計数する。即ち、各シンクセルを基準としたときに、プラス方向とマイナス方向とのそれぞれに対して、基準シンクセルと同一グループにグルーピング可能なシンクセルの数を計数する。
【００１６】
ステップ１−６で、プラス方向で同一グループにグルーピング可能なセル数とマイナス方向で同一グループにグルーピング可能なセル数との合計を、各シンクセル間で比較し、その数が最小のセルを基準シンクセルと定義する。
【００１７】
ステップ１−７で、ステップ１−６で決定した基準シンクセルを用い、基準シンクセルの角度に一番近い角度を有するシンクセルを特定する。
【００１８】
ステップ１−８で、ステップ１−７で特定したシンクセルが、基準シンクセルと同一グループとなり得る所定角度範囲内にあるか否かについて判定を行う。所定角度範囲内に存在する場合には、ステップ１−９に進み、当該シンクセルを基準シンクセルと同一グループと定義する。
【００１９】
ステップ１−１０で、現在処理中の距離グループ内において、未処理のシンクセルがあるか否かを判断する。未処理のシンクセルがある場合には、ステップ１−１１に進む。
【００２０】
ステップ１−１１で、次に角度が近いセルを特定する。その際、基準シンクセルからステップ１−７で特定したシンクセルに進むのと同一方向（プラス方向又はマイナス方向）へサーチして特定する。その後ステップ１−８に戻り、ステップ１−８乃至１−１１の処理を、基準シンクセルと同一グループに属する新たなシンクセルが無くなるまで繰り返し実行する。特定したシンクセルが所定角度範囲内にはないとステップ１−８で判断され、同一グループに属する新たなシンクセルが無くなった時点で、そのグループのシンクセルが分布する角度の範囲をグループの分布角度範囲として記憶しておく。
【００２１】
ステップ１−１２において、ステップ１−１１で特定したシンクセル（或いはステップ１−７で特定したシンクセル）を新しい基準シンクセルとして設定する。
【００２２】
ステップ１−１３で、基準シンクセルに角度が最も近いシンクセルを特定する。その際、基準シンクセルからステップ１−７で特定したシンクセルに進むのと同一方向（プラス方向又はマイナス方向）へサーチして特定する。その後、ステップ１−８乃至１−１１の処理を繰り返し実行する。
【００２３】
上記ステップ１−４乃至１−１３の処理を全ての距離グループについて完了すると、ステップ１−４での判断結果がＮＯとなり、ステップ１−１４に進む。
【００２４】
ステップ１−１４で、異なる距離グループ間で分布角度範囲が重なっているグループをサーチし、範囲が重なっているグループが存在する場合には、それらのグループを結合して１つのグループとする。このようにして決定された各グループにおいて、同一のグループに属するシンクセルは、１本の基幹配線を介してソースセルと接続される。
【００２５】
ステップ１−１５で、グループ毎に挿入するリピータの個数とその構成を決定する。ソースセルからの各所定距離Ｌについて１個のリピータを設ける。このようにして設けられる複数個のリピータは、基幹配線上に直列に挿入される。ステップ１−１４で複数のグループを纏めた場合、ソースセルに距離が近いグループについては、基幹配線の途中からこのグループ内のシンクセルに配線を分岐する構成とし、複数のグループ間で少なくとも１つのリピータを共有することになる。
【００２６】
ステップ１−１６で、各リピータを配置する座標を算出する。配置座標の算出にあたっては、まずグループ内にある全てのシンクセルの配置座標からそれらシンクセルの重心の座標を求める。複数の距離グループを纏めてある場合には、ソースセルから一番距離が遠い距離グループに関して、そのグループに属するシンクセルの重心を求める。ソースセルの配置座標とグループの重心座標とを直線で結び、その線上に間隔が均等になるようにリピータを配置し、リピータの配置座標を求める。
【００２７】
以上の処理をタイミング調整対象となる全てのネットに対して実行することで、リピータ挿入の箇所についての論理情報と配置座標を出力し、処理を終了する。
【００２８】
以下に、具体的な例を用いて、本発明によるリピータ挿入処理を説明する。
【００２９】
図２は、タイミング調整対象となるネットの一例を示す図である。
【００３０】
図２のネットは、ソースセル１０及びシンクセル１１乃至１７を含む。ソースセル１０から１つの出力が供給され、この出力が分岐されて各シンクセル１１乃至１７に供給される。
【００３１】
図３は、図２のネットにおける各セルの物理的配置位置を示す図である。縦軸及び横軸のディメンジョンは任意であり、例えばマイクロメータである。なおソースセル１０周りの角度を考えた場合に、シンクセルが９０°範囲に収まっている必要は無く、必要であれば縦軸及び／又は横軸の正側だけでなく負側も使用してよい。
【００３２】
各シンクセルのグループ分けするために、例えば、距離パラメータについては所定の距離範囲Ｄｓｔｅｐを１００とし、角度パラメータについては所定の角度範囲Ａｓｔｅｐを４５°とする。まずレイアウトデータより各セルの配置座標を抽出し（図１のステップ１−１）、各シンクセルとソースセル１０との距離Ｄｓｉｎｋを以下の式（１）により求めると共に、ソースセル１０周りの角度Ａｓｉｎｋを以下の式（２）により求める（図１のステップ１−２）。
【００３３】
Ｄｓｉｎｋ　＝　（Ｘｓｉｎｋ　−　Ｘｓｏ）　＋　（Ｙｓｉｎｋ　−　Ｙｓｏ）　　　　　　　（１）
Ａｓｉｎｋ　＝　ｔａｎ−１　｛（Ｙｓｉｎｋ　−　Ｙｓｏ）　／　（Ｘｓｉｎｋ　−　Ｘｓｏ）｝　　　　（２）
Ｘｓｉｎｋ：シンクセルのＸ座標
Ｙｓｉｎｋ：シンクセルのＹ座標
Ｘｓｏ　　：ソースセルのＹ座標
Ｙｓｏ　　：ソースセルのＹ座標
これにより図４に示すように各セルの物理的配置に関する各パラメータの値が求められる。
【００３４】
次に、ソースセル１０からの距離に応じてグループ分けを行う（図１のステップ１−３）。即ち、距離範囲Ｄｓｔｅｐを用い以下の式（３）に従ってグループ分けを行う。
【００３５】
Ｄｓｔｅｐ×（ｙ−１）　≦　Ｄｓｉｎｋ　＜　Ｄｓｔｅｐ×ｙ　　　　　　　　　（３）
ｙ：距離グループ
例えば、距離グループ２については、距離Ｄｓｉｎｋが２Ｄｓｉｎｋから３Ｄｓｉｎｋの間にあるシンクセルがこのグループに属するものとする。
【００３６】
図５は、シンクセルのグループ化及びリピータ挿入を説明するための図である。
【００３７】
上記のようにして距離グループを決定すると、図５に示されるライン２０乃至２２が距離グループの区切りとなる。ここで距離の計算はマンハッタン長を用いているので、等距離線はユークリッド距離の場合のように円弧とはならず、図５に示されるように直線となる。
【００３８】
これより各シンクセルは、以下のような距離グループに分類される。
距離グループ１：なし
距離グループ２：シンクセル１１、シンクセル１２
距離グループ３：シンクセル１３、シンクセル１４、シンクセル１５、シンクセル１６、シンクセル１７
これ以降の処理は、各距離グループ単位で実行される。以下では、説明の便宜上距離グループ３の処理ついてのみ説明する。
【００３９】
まずあるシンクセルを基準としたときに、そのシンクセルと同一の角度グループに幾つのシンクセルが属するかを、各々のシンクセルについて算出する（図１のステップ１−５）。その際、前述のようにソースセル１０からの距離に係らずグループ面積が略一定になるように、グルーピング可能な角度範囲を距離グループの距離に応じて以下のように補正する。
【００４０】
Ａｒａｎｇｅ　＝　Ａｓｔｅｐ　／Ｄｇｒｏｕｐ　　　　　　　　　　　　　　　（４）
ここでＤｇｒｏｕｐは距離グループの番号であり、距離グループ３の場合には３である。従って、距離グループ３において、同一グループにグルーピング可能な角度範囲Ａｒａｎｇｅは、
Ａｒａｎｇｅ　＝　４５／３　＝　１５°　　　　　　　　　　　　　　　　（５）
となる。図４に示される角度データを用いて、プラス方向（反時計回り）に角度１５°の範囲にあるシンクセルの個数と、マイナス側（時計回り）に角度１５°の範囲にあるシンクセルの個数を求めると、図６に示される結果が得られる。
【００４１】
プラス方向で同一グループにグルーピング可能なセル数とマイナス方向で同一グループにグルーピング可能なセル数との合計に着目し、その合計が最も小さいセルを基準シンクセルとする（図１のステップ１−６）。この場合には、シンクセル１３が基準シンクセルとして選択される。
【００４２】
基準シンクセルが決定されると、その基準シンクセル１３と角度が一番近いシンクセルを抽出する（図１のステップ１−７）。この例の場合、シンクセル１３から角度が一番近いセルはシンクセル１４である。次に、この特定されたシンクセル１４が基準シンクセル１３から所定の角度範囲１５°以内にあるか否かを判定する（図１のステップ１−８）。シンクセル１４の角度は図４に示されるように４８°であり、シンクセル１３との差が８°となるので、この差は角度範囲１５°以内である。従って、シンクセル１４は基準シンクセル１３と同一グループに設定される（図１のステップ１−９）。
【００４３】
シンクセル１４は基準シンクセル１３から見てプラス方向にあるので、同じプラス方向で次に距離が近いシンクセルをサーチしシンクセル１５を特定する（図１のステップ１−１１）。このシンクセル１５は角度が６０°であり、基準シンクセル１３との角度差が角度範囲１５°より大きいので、同一のグループにはグルーピングされない（図１のステップ１−８でＮＯ）。従って、シンクセル１３とシンクセル１４とで１つのグループ（図５のグループ３２）が確定し、シンクセル１５が新たな基準シンクセルとして設定される（図１のステップ１−１２）。
【００４４】
この際、確定したグループについて、属するシンクセルが分布する角度範囲（この例では４０°〜４８°）を記憶しておく。
【００４５】
その後、前回と同一の方向であるプラス方向において、次に距離が近いシンクセルをサーチしシンクセル１６を特定する（図１のステップ１−１３）。以降は上記のグループ化処理と同様にして、シンクセル１５を基準として、プラス側１５°以内にあるシンクセル１６及びシンクセル１７が同一のグループに属するものとして選択される。これにより図５のグループ３１が確定する。
【００４６】
１つの距離グループ内にある全てのシンクセルのグルーピング処理が終了すると、次の距離グループに移り、全ての距離グループについての処理が完了するまで同様の処理を繰り返す。その結果、図５に示されるように以下の４つのグループが生成される。
グループ３１：シンクセル１５、シンクセル１６、シンクセル１７
グループ３２：シンクセル１３、シンクセル１４
グループ３３：シンクセル１１
グループ３４：シンクセル１２
各距離グループ内において角度に基づくグループ分けが終了した時点で、異なる距離グループ間で分布角度範囲が重なっているグループ同士を纏めて１つのグループとする（図１のステップ１−１４）。上記４グループでは、グループ３１の分布角度範囲が６０°〜７０°でありグループ３３の分布角度範囲が６５°であるので、グループ３１とグループ３３とを結合する。この例では、他にグループ結合されるものはない。この結果、リピータを挿入する基幹配線（ソースセル１０から直接に延びる配線）は３本となる。
【００４７】
次に、グループ毎に挿入するリピータの個数とその構成を決定する（図１のステップ１−１５）。この際、挿入するリピータの個数は距離グループの値と等しい数とする。即ち、結合グループ３１＆３３は再遠の距離グループ値が３であるので３個、グループ３２は距離グループ値が３であるので３個、グループ３４は距離グループ値が２であるので２個となる。グループ３２とグループ３４については、単一の距離グループから形成されているので（グループ結合がなされていないので）、そのグループに属するシンクセルに対して信号を伝達する基幹配線上に、リピータを直列に挿入するよう配置する。結合グループ３１＆３３については、最遠のグループ３１のシンクセルに信号を伝達する基幹配線上に３個のリピータを直列に挿入し、距離グループ２に属するグループ３３のシンクセル１１については、当該基幹配線から２番目のリピータの出力部分を分岐して接続する。従って、グループ３１とグループ３３とで、ソースセル１０との接続経路において２つのリピータを共有することになる。
【００４８】
図７は、リピータ挿入処理により決定された論理構成を示す図である。
【００４９】
図７に示すように、シンクセル１２（グループ３４）については、単一の距離グループから形成されているので、シンクセル１２に対して信号を伝達する基幹配線上に、リピータ４７及び４８を直列に挿入する。シンクセル１３及び１４（グループ３２）については、単一の距離グループから形成されているので、シンクセル１３及び１４に対して信号を伝達する基幹配線上に、リピータ４１乃至４３を直列に挿入する。シンクセル１１のグループ３３とシンクセル１５乃至１７のグループ３１とは結合されているので、最遠のグループ３１のシンクセル１５乃至１７に信号を伝達する基幹配線上に３個のリピータ４４乃至４６を直列に挿入し、距離グループ２に属するグループ３３のシンクセル１１については、当該基幹配線から２個目のリピータ４５の出力部分を分岐して接続する。
【００５０】
最後に、挿入したリピータの配置座標を求める（図１のステップ１−１６）。グループに複数のシンクセルが含まれている場合は、それらのシンクセルの重心座標を求め、重心座標とソースセルとを結ぶ直線上にリピータを等間隔で配置する。
【００５１】
例えばグループ３２に対しては、２つの所属シンクセル１３及び１４の重心（Ｘｃｅｎｔｅｒ，　Ｙｃｅｎｔｅｒ）は、
Ｘｃｅｎｔｅｒ　＝　（Ｘｓｉ３＋Ｘｓｉ４）／２　＝　（１１５＋１３４）／２　＝　１２４．５
Ｙｃｅｎｔｅｒ　＝　（Ｙｓｉ３＋Ｙｓｉ４）／２　＝　（９６＋１４８）／２　　＝　１２２
となる。従ってリピータ４１乃至４３の配置座標は、重心座標とソースセル座標とを４分割して、
Ｘｒｅｐ１　＝　（Ｘｃｅｎｔｅｒ−Ｘｓｏ）×（１／４）　＝　（１２４．５−０）　×（１／４）　＝　３１．１３
Ｙｒｅｐ１　＝　（Ｘｃｅｎｔｅｒ−Ｘｓｏ）×（１／４）　＝　（１２２−０）　　　×（１／４）　＝　３０．５０
Ｘｒｅｐ２　＝　（Ｘｃｅｎｔｅｒ−Ｘｓｏ）×（２／４）　＝　（１２４．５−０）　×（２／４）　＝　６２．２５
Ｙｒｅｐ２　＝　（Ｘｃｅｎｔｅｒ−Ｘｓｏ）×（２／４）　＝　（１２２−０）　　　×（２／４）　＝　６１．００
Ｘｒｅｐ３　＝　（Ｘｃｅｎｔｅｒ−Ｘｓｏ）×（３／４）　＝　（１２４．５−０）　×（３／４）　＝　９３．３８
Ｙｒｅｐ３　＝　（Ｘｃｅｎｔｅｒ−Ｘｓｏ）×（３／４）　＝　（１２２−０）　　　×（３／４）　＝　９１．５０
として求められる。従って、シンクセル１３及びシンクセル１４用のリピータ４１乃至４３の座標は以下の通りとなる。
【００５２】
リピータ４１：（３１．１３，３０．５０）
リピータ４２：（６２．２５，６１．００）
リピータ４３：（９３．３８，９１．５０）
リピータ配置後のレイアウトイメージは図５に示される通りである。
【００５３】
図２に示されるようにソースセル１０から各シンクセル１１乃至１７に直接に配線を引き回している構成では、配線距離が長くなりタイミングエラーが発生する場合がある。このような場合であっても、本発明によるリピータ挿入方法によって図７のようにリピータを挿入すれば、必要最低限に近い個数のリピータを最適に近い位置に配置して、効率的で手間がかからず処理の早いタイミング調整を実現することが可能となる。
【００５４】
図８は、本発明によるリピータ挿入方法を実行する装置の構成を示す図である。
【００５５】
図８に示されるように、本発明によるリピータ挿入方法を実行する装置は、例えばパーソナルコンピュータやエンジニアリングワークステーション等のコンピュータにより実現される。図８の装置は、コンピュータ５１０と、コンピュータ５１０に接続されるディスプレイ装置５２０、通信装置５２３、及び入力装置よりなる。入力装置は、例えばキーボード５２１及びマウス５２２を含む。コンピュータ５１０は、ＣＰＵ５１１、ＲＡＭ５１２、ＲＯＭ５１３、ハードディスク等の二次記憶装置５１４、可換媒体記憶装置５１５、及びインターフェース５１６を含む。
【００５６】
キーボード５２１及びマウス５２２は、ユーザとのインターフェースを提供するものであり、コンピュータ５１０を操作するための各種コマンドや要求されたデータに対するユーザ応答等が入力される。ディスプレイ装置５２０は、コンピュータ５１０で処理された結果等を表示すると共に、コンピュータ５１０を操作する際にユーザとの対話を可能にするために様々なデータ表示を行う。通信装置５２３は、遠隔地との通信を行なうためのものであり、例えばモデムやネットワークインターフェース等よりなる。
【００５７】
本発明によるリピータ挿入方法は、コンピュータ５１０が実行可能なコンピュータプログラムとして提供される。このコンピュータプログラムは、可換媒体記憶装置５１５に装着可能な記憶媒体Ｍに記憶されており、記憶媒体Ｍから可換媒体記憶装置５１５を介して、ＲＡＭ５１２或いは二次記憶装置５１４にロードされる。或いは、このコンピュータプログラムは、遠隔地にある記憶媒体（図示せず）に記憶されており、この記憶媒体から通信装置５２３及びインターフェース５１６を介して、ＲＡＭ５１２或いは二次記憶装置５１４にロードされる。
【００５８】
キーボード５２１及び／又はマウス５２２を介してユーザからプログラム実行指示があると、ＣＰＵ５１１は、記憶媒体Ｍ、遠隔地記憶媒体、或いは二次記憶装置５１４からプログラムをＲＡＭ５１２にロードする。ＣＰＵ５１１は、ＲＡＭ５１２の空き記憶空間をワークエリアとして使用して、ＲＡＭ５１２にロードされたプログラムを実行し、適宜ユーザと対話しながら処理を進める。ＲＡＭ５１２或いは二次記憶装置５１４には、ソースセル及びシンクセルの配置座標を抽出するレイアウト情報が格納されている。なおＲＯＭ５１３には、コンピュータ５１０の基本動作を制御するための制御プログラムが格納されている。
【００５９】
上記コンピュータプログラムを実行することで、上記各実施例で説明されたように、リピータ挿入方法を実行する。
【００６０】
図９は、リピータ挿入方法を実行するプログラムの構成を示す図である。
【００６１】
図９に示されるように、リピータ挿入方法を実行するプログラムは、グループ化ユニット６０１とリピータ挿入ユニット６０２を含む。グループ化ユニット６０１は、図１のステップ１−１から１−１３に対応し、半導体チップのレイアウトにおける複数のセルの物理的配置情報に基づいて、セル間の距離の近さに応じて複数のセルをグループ化し１つ又は複数のグループを生成する。リピータ挿入ユニット６０２は、図１のステップ１−１４から１−１５に対応し、物理的配置情報に基づいて１つ又は複数のグループ毎に必要なリピータ数及びリピータの物理的配置位置を決定する。リピータ挿入ユニット６０２は、図１のステップ１−１４に対応するグループ間の結合を行うグループ結合ユニット６０３を含む。
【００６２】
以上、本発明を実施例に基づいて説明したが、本発明は上記実施例に限定されるものではなく、特許請求の範囲に記載の範囲内で様々な変形が可能である。
【発明の効果】
本発明によるリピータ処理方法によれば、セルの物理的配置情報に基づいて距離が近いセル同士を纏めるようにグループ化し、グループ毎にリピータを挿入するので、必要最小限な程度にまでリピータの個数を少なくし且つ適切な位置に挿入することが可能である。また物理的配置情報に基づいてリピータ数及びリピータの物理的配置位置を自動的な計算処理により決定することが出来るので、レイアウト設計とタイミング検証のイタレーション数を少なくしてタイミング調整処理を短時間で効率的に実行することが可能となる。
【図面の簡単な説明】
【図１】本発明によるリピータ挿入処理を示すフローチャートである。
【図２】タイミング調整対象となるネットの一例を示す図である。
【図３】図２のネットにおける各セルの物理的配置位置を示す図である。
【図４】各セルの物理的配置に関する各パラメータの値を示す図である。
【図５】シンクセルのグループ化及びリピータ挿入を説明するための図である。
【図６】各セルごとにグループ化可能なシンクセルの個数を示す図である。
【図７】リピータ挿入処理により決定された論理構成を示す図である。
【図８】本発明によるリピータ挿入方法を実行する装置の構成を示す図である。
【図９】リピータ挿入方法を実行するプログラムの構成を示す図である。
【符号の説明】
１０　ソースセル
１１、１２、１３、１４、１５、１６、１７　シンクセル
５１０　コンピュータ
５２０　ディスプレイ装置
５２１　キーボード
５２２　マウス
５２３　通信装置
【図１】
2004126904.tif 000003
【図２】
2004126904.tif 000004
【図３】
2004126904.tif 000005
【図４】
2004126904.tif 000006
【図５】
2004126904.tif 000007
【図６】
2004126904.tif 000008
【図７】
2004126904.tif 000009
【図８】
2004126904.tif 000010
【図９】
2004126904.tif 000011