図面 (/)

技術 RC遅延最適化配置方法

出願人 株式会社東芝
発明者 五十嵐睦典
出願日 1993年9月24日 (27年3ヶ月経過) 出願番号 1993-237043
公開日 1995年4月7日 (25年8ヶ月経過) 公開番号 1995-093383
状態 拒絶査定
技術分野 CAD
主要キーワード 配線径路 遅延予測 配線抵抗成分 配線単位 改善後 移動候補 遅延係数 解空間
関連する未来課題
重要な関連分野

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

図面 (3)

構成

次配置改善等で多くの遅延予測計算を必要とする処理において、高速ネットの遅延予測を行ない、RC遅延を効率よく最適化する手法を提供することにある。

効果

配線径路が決定していないレイアウト配線以前の段階において、高速にネットのRC遅延予測を行なうことができる。このため、配線抵抗の影響が無視できないサブミクロンオーダゲート長デザインルールの下でも、膨大な遅延予測計算量が必要な配置改善処理において、遅延予測計算の負荷を著しく軽減することができ、有限時間でより多くの解空間の探索が可能となる。従って、配線抵抗を考慮したタイミング最適化問題に関するレイアウトの質を向上させることができる。

概要

背景

半導体集積回路微細化は、チップ当たりの搭載可能な回路規模の増大による製造コスト低減や、動作速度の向上による性能アップなどの利点が期待できる反面、サブミクロンオーダ回路では配線抵抗成分遅延時間への影響が無視できなくなり、レイアウト設計において回路の動作性能保証を困難にするといった問題を発生させている。

論理ゲート物理的な配置位置情報からネット配線抵抗を考慮して遅延時間を予測する場合、配線径路情報を何らかの手法で予測する必要がある。そのための手法として、従来、唯一幹線に各端子から垂線を下ろすSingle Trunk Steiner Tree法(以下STST法と呼ぶ)、文献:M.A.Breuer,"Design Automation of Degital Systems", vol.1, Theory andTechniques, Prentice-Hall Inc.,1972 )や、端子のグループ化を行なって、各グループ毎の部分的なSTSTの配線予測径路を組み上げて全体ネットの予測径路とする手法(以下MTSTと呼ぶ)、文献:特開平5−18657号等が提案されている。前者については、木構造で予測される予測径路からネットのRC遅延を算出するために多くの計算量を必要とし、また、多端子ネットの遅延時間の予測精度は非常に低いといった問題がある。一方、後者の手法に基づく遅延時間の予測精度は、配線後の実遅延と比較して高いが、多端子ネットでは径路予測に時間が掛かるのみならず、ネットのRC遅延計算に関しては前者のSTST法と同様の問題を含んでいる。このため、両者の手法とも、配置位置情報から高速にネットのRC遅延を予測するには不十分な点がある。このため、これら予測手段をそなえた従来の配置手法では、処理時間上で困難な問題を抱えていた。

概要

次配置改善等で多くの遅延予測計算を必要とする処理において、高速にネットの遅延予測を行ない、RC遅延を効率よく最適化する手法を提供することにある。

配線径路が決定していないレイアウトの配線以前の段階において、高速にネットのRC遅延予測を行なうことができる。このため、配線抵抗の影響が無視できないサブミクロンオーダのゲート長デザインルールの下でも、膨大な遅延予測計算量が必要な配置改善処理において、遅延予測計算の負荷を著しく軽減することができ、有限時間でより多くの解空間の探索が可能となる。従って、配線抵抗を考慮したタイミング最適化問題に関するレイアウトの質を向上させることができる。

目的

この発明は、上述の問題点に鑑みなされたものであり、その目的としていることは、逐次配置改善等で多くの遅延予測計算を必要とする処理において、高速にネットの遅延予測を行ない、RC遅延を効率よく最適化する手法を提供することにある。

効果

実績

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

この技術が所属する分野

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

請求項1

論理ゲートの配置位置を決定する論理ゲート配置処理において、回路動作クリティカルであるクリティカルネットからなるパス上の遅延時間を改善し配置する際に、パスを構成するネット配線径路を信号の入り口となる端子と信号の出口となる端子をとする木構造からなる径路予測し、上記予測配線径路を基に、ネットのRC遅延時間を算出して、端子のx,y座標からなるRC遅延関数を定義し、上記RC遅延関数を座標x,yでそれぞれ偏微分して、遅延を減少させるセルの移動方向をセルの移動方向とし、上記方向へのセル移動を行なうことで該ネットの遅延時間最小化を行ない、全ての違反パスに関して、上記ネット遅延の最小化を繰り返し施して、違反パスの遅延時間を最小化することを特徴とするRC遅延最適化配置方法

請求項2

前記RC遅延関数を定義するに際して、ソースからシンクに至るマンハッタン径路を幹として、幹線から各ファンアウト端子に至るまでの支線分岐点をシンクの位置に置き、分岐点から各ファンアウト端子までの支線の長さをソースからファンアウト端子までのマンハッタン長で定義し、上記配線径路に従って、ソースからシンクまでのElmoreの遅延を算出することを特徴とするRC遅延最適化配置方法。

技術分野

0001

この発明は、計算機を用いたLSI設計に係わり、論理セルの配置の段階に際して、高速RC遅延最適化する方法に関するものである。

背景技術

0002

半導体集積回路微細化は、チップ当たりの搭載可能な回路規模の増大による製造コスト低減や、動作速度の向上による性能アップなどの利点が期待できる反面、サブミクロンオーダ回路では配線抵抗成分遅延時間への影響が無視できなくなり、レイアウト設計において回路の動作性能保証を困難にするといった問題を発生させている。

0003

論理ゲート物理的な配置位置情報からネット配線抵抗を考慮して遅延時間を予測する場合、配線径路情報を何らかの手法で予測する必要がある。そのための手法として、従来、唯一幹線に各端子から垂線を下ろすSingle Trunk Steiner Tree法(以下STST法と呼ぶ)、文献:M.A.Breuer,"Design Automation of Degital Systems", vol.1, Theory andTechniques, Prentice-Hall Inc.,1972 )や、端子のグループ化を行なって、各グループ毎の部分的なSTSTの配線予測径路を組み上げて全体ネットの予測径路とする手法(以下MTSTと呼ぶ)、文献:特開平5−18657号等が提案されている。前者については、木構造で予測される予測径路からネットのRC遅延を算出するために多くの計算量を必要とし、また、多端子ネットの遅延時間の予測精度は非常に低いといった問題がある。一方、後者の手法に基づく遅延時間の予測精度は、配線後の実遅延と比較して高いが、多端子ネットでは径路予測に時間が掛かるのみならず、ネットのRC遅延計算に関しては前者のSTST法と同様の問題を含んでいる。このため、両者の手法とも、配置位置情報から高速にネットのRC遅延を予測するには不十分な点がある。このため、これら予測手段をそなえた従来の配置手法では、処理時間上で困難な問題を抱えていた。

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

0004

上述のように従来のレイアウト設計の配置後の未配線状態におけるネットのRC遅延最適化の方法にあっては、遅延時間予測の計算量が多いことから、高速な最適化には不十分な点があった。

0005

この発明は、上述の問題点に鑑みなされたものであり、その目的としていることは、逐次配置改善等で多くの遅延予測計算を必要とする処理において、高速にネットの遅延予測を行ない、RC遅延を効率よく最適化する手法を提供することにある。

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

0006

この発明は、高速動作を要求されるLSIのレイアウト設計に係わり、論理ゲートの配置位置を決定する論理ゲート配置処理において、回路動作クリティカルであるクリティカルネット(クリティカルである1つまたは複数のネット)からなるパス信号伝播径路)上の遅延時間を改善する配置手法であって、パスを構成するネットのソース(信号の入口となる端子)とシンク(信号の出口となる端子)をとする木構造からなる径路で予測し、上記予測配線径路を基に、ネットのRC遅延時間をElmoreの手法を用いて算出して、端子のx,y座標からなるRC遅延関数を定義し、上記RC遅延関数を座標x,yでそれぞれ偏微分して、遅延を減少させるセルの移動方向をセルの移動方向とし、上記方向へのセル移動を行なうことで該ネットの遅延時間最小化を行ない、全ての違反パスに関して、上記ネット遅延の最小化を繰り返し施して、違反パスの遅延時間を最小化することを特徴とするものであって、前記RC遅延関数を定義するに際して、ソースからシンクに至るマンハッタン径路を幹として、幹線から各ファンアウト端子に至るまでの支線分岐点をシンクの位置に置き、分岐点から各ファンアウト端子までの支線の長さをソースからファンアウト端子までのマンハッタン長で定義し、上記配線径路に従って、ソースからシンクまでのElmoreの遅延を算出することを特徴とするRC遅延最適化配置手法である。

0007

更に、この発明は、高速動作を要求されるLSIのレイアウト設計に係わり、論理ゲートの配置位置を決定する論理ゲート配置処理において、回路動作上クリティカルであるパス上の遅延時間を改善する配置手法であって、パスを構成するネットのソースとシンクを幹とする木構造からなる径路で予測し、上記予測配線径路を基に、ネットのRC遅延時間をElmoreの手法を用いて算出して、端子のx,y座標からなるRC遅延関数を定義し、上記RC遅延関数を座標x,yでそれぞれ偏微分して、偏微係数の値がマイナスとなる方向を各セル毎に求め、上記方向へのセル移動を行なうことで該ネットの遅延時間最小化を行ない、全ての違反パスに関して、上記ネット遅延の最小化を繰り返し施して、違反パスの遅延時間を最小化するもので、前記RC遅延関数を定義するに際して、ソースからシンクおよびその他のファンアウト端子までの2端子間マンハッタン長さを端子座標x,yの関数として求め、ソースからシンクに至る径路を幹とする木構造からなる配線径路を想定した場合の、Elmoreの遅延時間の上限値を上記端子座標x,yの関数である2端子間マンハッタン長で定義することを特徴とするものである。

0008

上記構成によれば、配線径路が決定していないレイアウトの配線以前の段階において、高速にネットのRC遅延予測を行なうことができる。このため、配線抵抗の影響が無視できないサブミクロンオーダのゲート長デザインルールの下でも、膨大な遅延予測計算量が必要な配置改善処理において、遅延予測計算の負荷を著しく軽減することができ、有限時間でより多くの解空間の探索が可能となる。従って、配線抵抗を考慮したタイミング最適化問題に関するレイアウトの質を向上させることができる。

0009

本発明のディレイモデル構築仕方を、図1に示した簡単な3端子ネットの配置例を用いて説明する。同図で信号が端子A(ソース)から端子B(シンク)へ至るまでの遅延時間を計算する。ソースからシンクに至る径路を幹とする木構造の配線径路を仮定すると、Elmoreの手法を用いた遅延時間は次のようになる。

0010

Delay AB= KUPDN{c(11 +12 +13 +14 )+CB +CC }
+1/2r c11 2 +r11 (c(12 +13 +14 )+CB +CC )
+1/2r c(13 +14 )2 +r(13 +14 )CB (1)
KUPDN:セルのドライブ力から決まる遅延係数
r:配線単位長さ当たりの抵抗
c:配線単位長さ当たりの容量、
CB ,CC :端子B,Cの入力容量
11 〜14 :予想配線セグメント長さ
ただし、ここでは説明を簡略化するために配線層の違いによる物理定数の違い、および、立ち上がり立ち下がりによる遅延係数違いは省略した。例えば、第1式で配線径路をSingle trunk Steiner tree法で予測し、配線セグメント(11 〜14 に相当)を決定した場合、遅延時間の算出に際しては、各線分が駆動する下流側の容量を探索する必要がある。これには非常に多くの計算量を必要とし、配置改善でのセル移動数回程度、このような計算を行った場合には、遅延時間の見積に多くの時間を費やすことになる。そこで、高速にRC遅延を見積もる手法が必要である。本発明の遅延モデルは、上記の計算式を以下のように再構成する事で与えられる。まず、第1式をまとめ直すと、

0011

Delay AB= KUPDN{c(11 +12 +13 +14 )+CB +CC }
+1/2r c{11 2 +(13 +14 )2 }
+r{(11 +13 +14 )CB +11 CC }
+rc11 (12 +13 +14 ) (2)
である。ここで、距離11 〜14 を端子座標から簡単に近似するために、ソース端子Aからの端子B,Cまでのマンハッタン長を求めると、

0012

1B =(XB −XA )+(yB −yA )=11 +13 +14

1C =(XC −XA )+(yC −yA )=11 +12 (3)
である。ここで、

0013

11 ≦1B ,12 ≦1c ,
13 +14 ≦1B ,
11 +12 +13 +14 ≦1B +1C ,
11 (12 +13 +14 )≦1B 1C (4)
の関係を利用すれば、端子B,Cの位置関係によらず、

0014

Delay AB,= KUPDN{c(1B +1C )+CB +CC }
+1/2r c1B 2

+r{1B CB +1C CC }
+rc1B 1C (5)
が成り立つ。そこで、本発明の遅延モデルを以下のように定める。

0015

Delay AB= KUPDN{c(1B +1C )+CB +CC }
+1/2r c1B 2

+r{1B CB +1C CC }
+rc1B 1C (6)
1B ,1C は、端子位置(x,y)から簡単に計算する事ができ、従って、DelayAB´も端子の座標を使って簡単に求めることができる。第6式を任意の端子数のネットに対して適用して、本発明の遅延モデルを以下のよう定める。

0016

ID=000003HE=015 WI=067 LX=1165 LY=0950
ID=000004 HE=020 WI=111 LX=0495 LY=1200
Cj (j=1,2,…):ファンアウトセルの入力容量、
1i :ソース〜シンク間のマンハッタン長、
1j (j=1,2 …j=i):ソース〜ファンアウトセル間のマンハッタン長、
次に、本発明の遅延モデルを使ってネットの遅延時間を削減するためのセルの移動方向の決め方について説明する。処理対象となったネットに関して、第7式で定義したモデルを作る。移動候補セルを端子Bが接続するセルとし、該セル以外のセルの位置を固定した条件下では、第3式より、

0017

d1B /dX =d(XB −XA )/dX

=d(13 +14 )/dX ,
d1B /dy =d(yB −yA )/dy

=d(13 +14 )/dy (8)
である。同様にして、端子Cが接続するセルを移動候補として選択し、その他のセルを固定した条件下では、

0018

d1C /dX =d(XC −XA )/dX ,
=d(11 +12 )/dX ,
d1C /dy =d(yC −yA )/dy

=d(11 +12 )/dy (8')
が成り立つことから、第7式のコストを順次最小化していけば、第2式で示したElmoreの遅延も最小化されていくことが分かる。そこで、第7式の座標x,yに関する偏微分係数を求める。

0019

dDelay´/dX , dDelay´/dy (9)
この微係数が負となる方向が、選択セルを動かして該ネットの遅延時間が削減される方向である。このように、逐次セルを選択し、移動を試みることで該ネットの遅延時間を削減していくことができる。制約違反している全てのネットに対して、同様の処理を試みることで、クリティカルパス全体の遅延を徐々に削減していくことが可能である。

0020

実際に、本発明をタイミングを改善する逐次配置改善処理に組み込んで実験を行った結果を説明する。実験に使用したデータは、129KG規模ゲートアレイのデータで、セル数12000、ネット数12000で、このうち制約を付加したネット数は1563である。これに対して本発明の遅延予測処理を組み込んで、遅延時間の最適化を行った結果、初期状態に302あった違反パスが、約1/6の52本に減少し、要求時間に対する実遅延時間の差であるスラック最小値も50%改善された。

0021

図2は、初期状態の違反パス(a)と改善後の違反パス(b)、および、それらに関係するセルのみを抜き出して描いたものである。全体のはチップを表していて、周辺にI/Oセルが置かれている。矩形は、各ネットの最小矩形を表し、セル間を結ぶ斜めの直線は制約が付加されているソースとシンクを結んだものである。図2に示した結果は、28.5MIPSマシンで約1時間で得ることができた。

発明の効果

0022

上記の説明で明らかなように、この出願の発明を用いれば、配線径路が決定していないレイアウトの配線以前の段階において、高速にネットのRC遅延予測を行なうことができる。このため、配線抵抗の影響が無視できないサブミクロンオーダのゲート長デザインルールの下でも、膨大な遅延予測計算量が必要な配置改善処理において、遅延予測計算の負荷を著しく軽減することができ、有限時間でより多くの解空間の探索が可能となる。従って、配線抵抗を考慮したタイミング最適化問題に関するレイアウトの質を向上させることができる。

図面の簡単な説明

0023

図1本発明の遅延予測モデル構築方法を説明するための図。
図2本発明の適用した実験結果を説明した違反パスの変化の様子を示した図。

--

0024

1…ソース
2…シンク
3…ファンアウトセル
4…幹線
5…支線

ページトップへ

この技術を出願した法人

この技術を発明した人物

ページトップへ

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

関連する公募課題

ページトップへ

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

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

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

ページトップへ

おススメ サービス

おススメ astavisionコンテンツ

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

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

関連性が強い人物一覧

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

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

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

関連する公募課題一覧

astavision 新着記事

サイト情報について

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

主たる情報の出典

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