数理解析研究所講究録
第 1568 巻 2007 年 14-19

14

数式処理を用いた LSI 設計に関する研究

A study of Symbolic Analysis for LSI design

中林太美世

加古富志雄

奈良女子大学

Tamiyo NAKABAYASHI

Fujio KAKO
Nara Women’s University

概要
本稿では、数式処理の応用として、数式処理ソフト $Mathematica[7]$ を用いた論理回路股計について議論する。

CMOS 非線形遅延モデルによる論理回路の遅延計算を数式処理を用いて行う方法を提案する。 まず、基本セルの遅延特性を近似多項式の数式表現によりモデル化する。 さらに、本手法を用いて 1 ビット全加算回路を設計し、配線長の最適化を行った。 これらにより、 本手法の有用性を確認した。
1 はじめに数式処理の LSI 設計分野への適用について提案する。 具体的なアプリケーションとして、 LSI の信号遅延計算ッールの開発を目指す。

#I 設計において回路が正常動作することを保証するためには、 回路遅延の見積もりと最適化が必須である.
LSI の高遠化高集積化を図るために製造工程の微細化と多層配線構造化が進み、信号配線の寄生容量/抵抗が信号遅延に及ぼす影響が大きくなっている $[2][3][4]$ ,般的に、信号遅延を計算するための方法として、 回踏のカテゴリに応じて回路方程式を数値的に解くシミュレーション手法や解析式を用いる方法、 あるいは予めCharacterize しておいた特性テープルを用いる方法がある。 本研究の趣旨は、 回路遅延の見積もりに数式処理を適用することにより、 信号遅延のモデル式による計算を通じて信号遅延の理論と過渡現象の概念を結び付けるこ-とである。

本報告では、 研究の初期段階として、 数式処理ソフト Mathematica を用いた CMOS 非線形遅延モデルによる論理回路の遅延計算手法を提案する。 まず基本セルの遅延特性についてモデル化を行い、 さらに実回賂への適用例として 1 ビット全加算回路の殻計を行った。 その結果、 回路動作や信号遅延のモデル式を使って敷式べースで最適な設計値を求めることができ、提案手法の有用性を確認した。

2 致式処理を用いた論理回路の遅延計算

CMOS 非線形遅延モデルを用いた論哩回賂の遅延計算を数式処理を用いて実現する方法を検討する。
21CMO8 弗餓膨遅延モデル-般的に、 論理回路の遅延計算は CMOS 非線形遅延モデルを用いて以下のように行われる【5L CMOS 非線形遅延モデルは、予め Characterize しておいた Look UP Table と楠間を使用してセル遅延を計算する。 ここで、セル遅延とは、入カピンの電匪が動作電源電圧の 50%になってから出力ビンの電圧が動作電源電圧の 50%になるまでの時間をいう 図
セル遅延を算出するには、 図 3 に示すような出力負荷容量と入力遷移時間をインデック$($$2)_{\text{。}}$スとして使用する 2 次元テーブル (以下、 セル遅延テーブル) を用いて以下のように求める :15$1$》セル Ul の遅延テーブルから前段セル UO の出力遷移時間と Ul の出力負荷容量をインデックスとして Ul の出力遷移時間とセル遅延時間を求める。
2) 1) で求めた Ul の出力遷移時間と U2 の出力負荷容量をインデックスとして U2 の出力遷移時間とセル遅延時間を求める。
3) 以降、 同様の操作を繰り返す。

このとき、 入力遍移時間と出力負荷容量をインデックスとしてセル遅延テーブルからセル遅延を求めるため、 インデックス値を含む 4 つの隣接するテーブル値を選択し、4 点で構成される面の近似値を求めるためにガウスの消去法を用いて 2 次元補間による係数決定が行われる。
22 着本セルの遅延特鮭のモデル化
上記の入力遷移時間と出力負荷容量をインデックスとするセル遅延テーブルに対して、最小 2 乗法による多項式近似を行うことにより係数を最適化し、 回路遅延特性を数式で衰現することを考える。
基本セルの遅延特性として、 ここではインバータセルの立下がり遅延について考える。 セルの立下がり遅延テーブルは図 3 に示す出力遷移時間テーブル、遅延時間テーブルとも入力遷移時間と出力負荷容量をインデックスとするのテーブルで与えられているとする。 このとき、該テーブルを最小 2 乗法を用いて係数の最適化を行い、1 次から 6 次までの近似多項式で表した場合の項数と元の 2 次元テーブル値に対する RMS 誤差を図 4 に示す。
また、 図 5 は 1 次、 3 次および 4 次の多項式で近似した場合の入力遷移時間と出力負荷容量に対するセルの立下がり遅延時間をプロットしたものである。 近似多項式による数式表現を用いてモデル化を行うためには、 より低$7\cross 7$次で高精度な多項式が必翼である。 しかし、 図$4$、

図 5 からわかるように、 高次になるとともに高精度になるが、4 次以上になると極が存在する。 これを避けるため、 3 次多項式での近似を採用することにする (図 6)。

81 ビツト全加算回路の設計
31 総遅延の算出実回賂への適用例として、 図 8 に示す 1 ビット全加算回路の設計を行う。 設計値は各セル閥を接続する配線長(図 8 の Ll,L2,L3,L4,L5)、設計制約は入力 A から出力 $S$ への遅延の上防下限および各セルの出力負荷容量の上限とする。 また、仕様値として、回路への入力信号の遷移時間 (Input\sim lew) 、および出力負荷容量 $(Output\lrcorner oad)$が与えられているとする。 ここでは、 与えられた $Input_{-}slew$$oad$ に対する各配線長の最適化を行う。
$Output$」
なお、 配線遅延モデルは図 7 に示す Elmore 遅延モデルを用いることにする、$[3][6]_{\text{。}}$

図 9 に Mathematica を用いて回路の入力 A から出力 $S$ までのトータル遅延を求める計算フローを示す。22 節で述べたように各セルの遅延特性を入力遷移時間と出力負荷容量をパラメータとする 3 次の近似多項式でモデル化する。ここで、出力負荷容量は負荷配線の容量と次段セルの入力ピン容量の合計である。図 9 で、Dcell 茜犠 ehは各々セル$x$の遅延, 出力遷移時間を、 DLYx, へ$Nx$ はそれらの関数、 RO, CO は各々製造工程から得られる単位長さあたりの配線抵抗値 (\Omega /um) と配線容量値 (F’um) を表す。 本計算フローで得られたトータル遅延を$Input_{-}\epsilon 1ew$、$Output\lrcorner oad$

、および各配線長 (Lengthl,...,Length5) をパラメータとする多項式により近似を行った結果、 27 次の近似多項式が得られた。

&2 配線長の最遼化
上記 31 で求めたトータル遅延は $Input_{-}slew$(Lengthl,...,Length5) をパラメータとする関数 (kUlDLY) で表される。 また、 各セル毎の出力負荷容量は、 配線負荷 (単位長さあたりの配線容量(CO(F’um)) $*$ 配線長) に次段セルの入カピン容量 (Cpin) を加えたものである。 制約条件として以下の不等式、$Output_{-}1oad$ と各配線長で表される条件が与えられている。
\langle 1) Dmin $\leq lbtal$ 遅延 $\leq D\max$(2)loadl

Cmaxl, load2 Cmax2, load3 $\leq C\max 3$ , load4 Cmax4, load5 Cmax5
ただし、 Dmin, Dmax は仕様値、 loadl, ..., load5 は Ceul から $Ce15$ の出力負荷、 Cmaxl. ..., Cmax6 は製$\leq$$\leq$$\leq$$\leq$16

造工程値から得られる制約条件である。
今、 (1)(2) の制約条件の下、 任意に与えた$n$個の Input-slew と Output-load の組み合わせに対して配線長(Lengthl,...,Length5) の最適化処理を実行する。 その結果、 図 10 に示すような $Input_{-}slew$ Output-load と、最適化された配線長のテーブルが得られる。 この配線長テーブルから、 Lkengthl,...LkengthS の各配線長を$Input\sim 1ew$ 、 $Output\lrcorner oad$の 2 つをパラメータとする近似多項式の数式表現によりモデル化を行うため、 3 次多項式で近似する (図 11)。得られた近似多項式を図 10 の配線長テーブル値と比較すると、 RMS 膜差はすべて 1%以内で近似できていることがわかる (図 12)。
4 まとめ

数式処理の応用として、数式処理ソフト Mathematica を用いて論理回路の遅延計算を行う方法を提案した。 まず、基本セルの遅延特性を 3 次の多項式の数式表現によリモデル化した。モデル化の族差は 4.2%である。さらに、本手法を用いて 1 ビット全加算回路を設計するため、当骸回路の遅延特性を 27 次の多項式で近似し、配線長の最適化を 3 次の近似多項式で行った (誤差 10%以内)。 これらにより、数式処理による遅延計算に対する提案手法の有用性を穂認することができた。

5 今後の課履

LSI 設計分野への数式処理の適用として、 本提案手法の多ビット加算器や乗算器など本格的な回賂設計への適用や、 半導体基本素子 (トランジスタ、 ダイオード、容量など) のモデル化、 さらに、 LSI レイアウトの配置配線の最適化へと発展させることが今後の課題である。
参考文賦[11 Sakurai, $*clo\epsilon ed\cdot formexpres\cdot ionl$ for $inter\infty nnection$ delay, $\infty uplinl$ , and.

$\alpha\infty\iota ta$]$k$ in $VISr\iota$ ,IEEElkans. Electron Devices, vol.40, no. 1, $pp.118\cdot 124$ Jan. 1983.
[2] H.B.Bakoglu, “Circuits, Interconnections, and Packging for VLSI,” $Addi\epsilon on\cdot Wesley$ Publishing Company,1990.
[3] $Chung\cdot Kuan$ Cheng, “Interconnect Analysis and Synthesis,“ Wley, 1999.

[4] N.DArora, “Modeling and Characterization of Copper interconnects for VLSI Design,“ Nanotech2003.
[51 Synopsys, Inc., LIBRARY COMPILER UoerGuide, Vo12, $V\cdot 1998.08.ed.$ , 1998.
[61 W.C.Elmore, “The transient response of damped linear networks with particular regard to Wideband

amplifien,“ $Jouma1atAppAedP\ovalbox{\tt\small REJECT} ias$ , vol. 19, pp. 55-63, Jan. 1948.
[71 Woliam research, MATHEMATICA 5.2.

17

セル逓猛 配線遅延$\frac{\text{◆}}{}-$

図 2 遅延の定義

図 1CMOS 非線形遅延モデルの構成要素

Numbw $d$ terms,$\backslash -|\backslash$$\downarrow.:_{l,-}|lt.$

’$0|$

$|$.
$\swarrow$$\mathcal{F}$$l$$\swarrow$$\swarrow$$\nearrow$

桶荻牡王寡’$\swarrow$

図 3 遅延テーブル$\nearrow$

$l$

$J$

$\nearrow$$f$

図 4 近似多項式の項数と RMS 眠差

図 5 インバータセル遅延の近似例$R_{-}f\cdot 11(x,y)\Rightarrow$$-0.\infty 0aeoe61+0.205682$ 禾 $-o.\infty 402\Re j_{+0.0008840933+5.7546y+}3$

1.17031 禾 y+0. 屋 9\infty 4-261y-u. $6\mathfrak{B}9\not\in-3.32541xi+25.7925j$$z:\lambda$$y$力逼移時間: 出力負蕎審量

図 6 インバータセル遅延の近似式算出例

18Dwire $=RwlCwl\prec\langle Rwl+Rw2$ ) $Cw2+\cdot\cdot\iota(Rwl+Rw2+\cdots+Rwn)Cwn$
特にすべての Rj\Rightarrow 丸 q\subset の時は$\ovalbox{\tt\small REJECT}=$果:議鐘工糎値.

$E\bullet S\aleph:1S*k_{-}V\Phi S(RW\bullet\bullet l$.‘\rightarrow 一鴬 [屑瑠輻.
は$uAtni$ 嚢による 1 寂曇モヂル.

. $rr-s$. 図 7 配線遅延モデル$P\bullet\bullet I:1lll\succ-\iota/\Phi\bullet 1(OP-\bullet l.\sigma$$k\vee W$

図8

1 ビット全加算回路$\ovalbox{\tt\small REJECT}_{}^{\vee}$

図 10

配線長テーブル19

Lengthl$=$Length2$=$

Length3

56.2706+14.0774 x-25. 6254 $1t^{2}*12.6111x^{3}*$ 352.036
46.557 $xy*31.8844x^{2}$ y-3466.32 +54.5149 $xf+5087.15y^{3}$$y_{-}$$\oint$$=$166.617+65.6652 x–152.015 $a\iota^{2}*93.03361t^{3}*180.61y*$706.275 y-344.757$x$$x^{2}$y-3095.31 $i-1044.05xy^{2}*6243.48y^{3}$$137.207*$ 67.3216 $x-204.595l\iota^{2}*135.224x^{3}-1230.47y*$.

424.636 y-205.38 $x^{2}y+4804.82\oint_{-}514$ 248 $2t \oint-S743.69\oint$$x$.

$Length4-32r_{i_{97xy*419.273x^{2}y-2882.1y^{2}*1261.5xy^{2}*2311.37y^{3}}^{457-84.2874x*223.271x^{2}-139.394x^{3}*735.468y-}}90$

Length5$119.946*78.9733$ x-240.862
152.843 $x^{3}-2839.19y$
1401.86 $xy-$ 638.947 $x^{2}y*$ 17538.3 $i-$ 1942.6 $xy^{2_{-}}24435.2y^{3}$$x^{2}*$

$=$

図 11

配線長最適化結果

図 12 配線長テーブル値 v.. 各近似式のRMS 娯差