Timing Optimization Techniques

VLSI設計工学５
タイミング： DSM時代の最大関心事の１つ
（もう１つは消費電力）
•
回路における「配線の影響」が支
配的なくらい大きい
– 寄生容量
– 抵抗
– インダクタンス
•
100万ゲート以上
– システムLSI
1
論理素子の遅延と回路の遅延
• 論理素子の遅延時間
– 入力が決まってから出力が決まるまでの時間
• 回路の遅延時間
– 入力が決まってから出力が決まるまでの時間
– 回路は論理素子を結合したものなので、論理素子の遅延の積算
• 論理回路のタイミング
– 回路の二つの信号の間の時間的な関係
2
論理素子の遅延時間
• 素子の入力が決まってから出力が決まるまでの時間
– 情報を光よりも高速に伝えることはできない
– 10 ps (ピコ秒、10-12 秒) ~ 10 ns (ナノ秒、10-9 秒)
Ａ
Ａ
Ｙ
delay
delay
Ｙ
t（時間）
3
配線の遅延時間
• ゲートの出力 Y の変化が、Y に結合されているゲートの入力に伝
わるまでの時間
– 配線の容量に起因
Y
C
D
Y
C, D
delay
delay
t（時間）
4
配線遅延の問題点
• 素子の配置、配線の終了後でないと評価不能
– 設計段階で評価できない
– 設計変更で対処しずらい
• 大きなバッファ、太い配線
• 素子の遅延よりも大きくなりつつある
– LSI の製造プロセスの微細化による
5
ゲート遅延と配線遅延のモデル
• 遅延素子を用いたモデル化
– 遅延の積算時に考慮
配線の遅延
ゲートの遅延
C
Y
D
配線の遅延
6
配線遅延のモデル化
• 入出力対毎で遅延の異なる素子としてモデル化する
B→ Z: 8
C→ Z: 11
B
2
6
Z
C
5
Y
D
7
組合せ回路の最大遅延時間
• フィードバックループがないので素子の遅延時間を加算すれば良い
• 外部入力から外部出力へ向かって計算
– 素子をレベルソートする
– レベルの小さい順に素子の最大遅延を計算
レベル i の素子は
レベル i-1 以下の素子
の出力しか用いない
レベル 0 レベル 1
(外部入力)
レベル 2
8
素子のレベルの計算式
• level(v) = max i (level(v i)) + 1
– 外部入力のレベルは 0、vi は v の入力
•計算量は結線の数に比例
•素子数 n に対して n2
v1
v2
v3
v
9
素子の最大遅延の計算式
• maxd(v) = max i (maxd(v i)) + d(v)
– 外部入力の遅延は 0、vi は v の入力
– d(v) は素子 v の遅延時間
8
v1
計算量は結線の数に比例
８
v2
3
３
2
５
v
4
１２
v3
2
２
10
素子の最小遅延の計算式
• mind(v) = min i (mind(v i)) + d(v)
– 外部入力の遅延は 0、vi は v の入力
– d(v) は素子 v の遅延時間
8
v1
８
計算量は結線の数に比例
v2
3
３
2
2
v
4
6
v3
2
２
11
組合せ回路と順序回路
• 組合せ回路
– 記憶を持たない回路、フィードバックループのない回路、現在の
入力のみで出力が決る
• 順序回路
– 記憶を持つ回路、フィードバックループのある回路、出力は現在
および過去の入力に依存
• 同期式順序回路
– クロック信号に同期して動作する順序回路
12
同期式順序回路の概念図
• 組み合せ回路とエッジトリガフリップフロップ
外部入力
n
m
外部出力
組み合せ回路
状態変数
（現状態）
k
k
状態変数
（次状態）
クロック
エッジトリガフリップフロップ
13
エッジトリガ Flip Flop の動作
• クロックの変化時（立ち上りまたは立ち下がり）の入力を見て出力を
決める
– クロック変化の前(セットアップ）と後（ホールド）は入力が安定で
あること
入力
set-up
hold
クロック
delay
出力
14
同期回路のタイミング制約
• 組み合せ回路の最大遅延とクロック周期
組み合せ回路
状態変数
（現状態）
状態変数
（次状態）
クロック
状態変数
最大遅延の許容範囲
入力（次状態）
set-up
hold
クロック
delay
出力状態変数
（現状態）
15
同期回路のタイミング検証
• 最大遅延(tmax)について: tpd + tmax + tsu < tcy
• 最小遅延(tmin)について: tpd + tmin > th
入力
tsu
th
クロック
tcy
出力
tpd
16
同期回路の利点
• 最大遅延： tpd + tmax + tsu < tcy
– 組み合せ回路の出力は、最大遅延時間後は入力が変化しない限
り安定
– クロック周期（tcy）を十分大きくとれば必ず制約を満たせる
• 最小遅延： tpd + tmin > th
– エッジトリガフリップフロップの設計時に工夫可
• タイミング問題を組み合せ回路の最大･最小遅延の評価に帰着できる
17
同期回路の詳細なモデル
• レジスタ転送 (RT) レベル回路
組み合せ回路
組み合せ回路
組み合せ回路
組み合せ回路
クロック
18
同期回路の問題点
• 今のクロックで決ったレジスタの値に対し、次のクロックでレジスタに
記憶する値を計算
• クロックがすべてのレジスタに同時に到達することを仮定
• 本当に同時に到達するか
– クロックも配線を通してレジスタまで送られる
– 配線には遅延があるので、同時とは言えない
– ズレ（クロックスキュー）へ対処する必要がある
19
クロックスキューの問題点
• 組み合せ回路部の最大遅延時間を限定
• クロックを遅くしても問題が解決しない
クロック
クロック（A）
スキュー
クロック（B）
C１の計算時間
C2の計算時間？
組み合せ回路
C1
クロック
組み合せ回路
C2
A
B
20
クロックスキューへの対処
• スキューをなるべく小さくする
– 太い配線を用いる
– 配線長を合わせる
• クロックツリー合成
– スキューを合わせる
• 早く到達する部分に遅延をいれる
• スキューを仮定した回路設計
– ローカルには同期、グローバルには非同期
– スキューを制御して、積極的に利用
21
スキューの積極的な利用
• あるモジュールの許容遅延時間を長くとる
クロック
クロック（A）
C１の許容遅延時間
クロック（B）
d1
C2の許容遅延時間
組み合せ回路
C1
クロック
ただし minC2 > d1
組み合せ回路
C2
A
B
22
同期回路のタイミング設計と検証
• 組合せ回路部の最大遅延 tmax がクロックの１周期の時間より小さいか
どうかの判定
– tpd + tmax + tsu < tcy
– なるべく高速なクロックで動作させたい
• 設計側
– 最大遅延時間のなるべく小さい回路を設計する
• 検証側
– 最大遅延 tmaxの正確な評価が重要
– グラフ的な最大遅延 (topological delay)は本当に最大か
23
タイミング最適化設計の流れ
論理合成
レイアウト前、タイミング最適化
not ok
レイアウト前のタイ
ミング制約を満たす？
back annotation
問題点
– 最適化ルーチンでは、レイアウ
ト後の実際の配線容量や遅延
モデルとは異なるモデルで最
適化している
• タイミング最適化が収束し
にくい
RTL spec
フロントエンド
•
フロントエンドとバックエンドは別々
– レイアウト後の情報を戻して（
back annotation）、タイミング
最適化を繰り返す
バックエンド
•
ok
配置・配線
レイアウト後、タイミング最適化
実タイミング
制約を満たす？
not ok
ok
マスクパターン
24
タイミング最適化というのは、
なかなか収束しない！
タイミングエラー数
50
45
0.35 m
40
35
30
25
20
0.5 m
15
10
0.8 m
1.0 m
5
0
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18
繰り返し回数
25
基本事項・定義
•
•
信号cのarrival time
– 外部入力からの信号が c に到達するのに要する最大時間
信号cのrequired time
– タイミング制約を満たすために、信号 c の値が確定していなけばならな
い時刻
req
(6, 6)
2
c
1
(3,3)
1 e
(5, 4)
1
(4,3)
a b
•
•
•
arrc =
max(arra + delaya c,,
arrb + delayb  c)
逆方向の計算
(7, 6)d
順方向の計算
arr
reqc =
min(reqd - delayc d,
reqe - delayc  e)
reqa = reqc - delaya c
reqb = reqc - delayb c
信号cのスラック: （信号cのrequired time） - （信号cのarrival time）
クリティカルパス: 最小のスラックをもつ信号の集合
タイミング最適化の目標: スラックの最小値を最大化する
26
タイミング最適化の基本プロシージャ
基本ルーチン {
タイミング解析;
while ( 目標に到達していない) {
次のクリティカルな場所を選ぶ;
その場所を回路変換する;
タイミング解析;
critical region
if (スラックの最悪値が向上した)
回路変換を受け入れる;
else
回路を元に戻す;
}
}
critical path
•
レイアウト前、レイアウト中、レイアウト後に適用される
– それぞれ、異なるタイミングモデルの上に定義された、異なる回路変換
が適用される
27
静的タイミング解析
• 静的にクリティカルパル・最長パスを求める
– 回路を入力から出力へ順にarrival timeを計算していく
– そして、回路の出力から入力へrequired timeを計算する
• タイミング最適化の際のガイドとなる
• 信号経路が実際に活性化される（本当に信号を伝える）かどうかは
考えない
– フォールスパス問題が発生する
• あるパスは、決して信号を伝播しないかもしれない
• つまり、そのパスが信号を伝えるような入力値の組み合わせ
は存在しない
28
静的タイミング解析におけるフォールスパスの例
a 2-bit carry-bypass adder
c0
s0
a0
b0
p0
c1
s1
a1
b1
p1
1
0
sel
c2
(if 1, then c2 = c0, c0 - c1 - c2 not selected;
if 0, then p0 or p1 is 0, blocking c0 - c1 - c2)
– c0 - c1 - c2 がフォールスパス
• a0, a1, b0, b1 が時刻0、c0 が時刻2に到着、各ゲートの遅延は1
– フォールスパス c0 - c1 - c2 (遅延 7)
– 真の最長パス a0 - c1 - c2 (遅延 6)
29
逐次的タイミング解析によるスラックの更新
• 回路の部分的な変更に対して：
– 回路の順方向に arrival time を更新
• 変更部分の直前の入力からスタート
– 回路の逆方向に required time を更新
• 順方向に更新した際に、扱ったゲートからスタート
– ゲートの入力信号変化が変わるとそのゲートの遅延値は変化
逆方向に
required time を
更新
変更回路
部分
順方向に
arrival time を
更新
• 基本的に、遅延値の変化がなくなった時点で終了
30
論理関数の分割
• 論理関数 F を「うまく割る」関数 D をみつける
F=D•q+r
– 一般的に、論理関数を考慮して割り算をすると多数の候補が存在
し、計算時間もかかる
• 代数的な割り算に制限する
– D と q は同じ変数を共有しない
– D • q は代数的積と呼ばれる
– r はより少ない項数となる
• 例： F = x’z’ + yz + xz
– 論理関数的割り算: D = x’ + z
• F = (x’ + z)(x + z’) + x’y, または
• F = (x’ + z)(y + z’) + xz
（割り算の結果は一意ではない）
– 代数的割り算： D = x + y
• F = z(x + y) + x’z’
（割り算の結果は一意）
31
タイミングを考慮した論理関数の展開を分割
• f をクリティカルパスに沿って、部分的に展開し、新たな論理関数 k
で割り算する
– 基本戦略：クリティカルな信号をより出力側へもっていく
f
f
f
展開された
ノード
a
a
e
b
e
b
c d
k
divisor
a
e
c
d
b
c
d
クリティカルパス
32
テクノロジを考慮した関数分割
• まず、与えられた関数を NAND2/INV だけからなる回路に分割
– 小さいゲートの集合:
• セルライブラリを使って実現できることが保証されている
– ライブラリに４入力NANDはないかもしれない
• テクノロジマッピングしやすい
• タイミングへの影響大
– タイミングを考慮して分割
a
b
c
d
a
b
a
b
c
d
c
d
a, b, c, dが同じくらいクリティカル
Dが最もクリティカル
33
ゲートサイジング／ピン交換
• 等価セルで大きさのことなるものに変える
– ゲートのドライブ力、遅延、入力容量が変化する
size-down
late signal
a
2X
size-up
b
a
1X
b
1X
1X
2X
1X
critical path
• 入力ピンの交換
– 遅い信号を遅延の小さい入力ピンに接続する
longer pin-to-pin delay
late signal a
b
b
a
34
バッファ挿入
• ファンアウト負荷の削減する方法
– クリティカルパスを分離する
• クリティカルではないところにバッファを挿入する
critical path
– 負荷を合わせる
• すべての分岐の負荷を同じにする
35
リタイミング
• 元のクロック周期 = 4.5 ns
2.7 ns
4.5 ns
(1 ns)
組合せ回路
(2.7 ns)
組合せ回路
(3.5 ns)
• リタイミング後のクロック周期 = 3.7 ns
3.7 ns
組合せ回路
(2.7 ns)
3.5 ns
(1 ns)
組合せ回路
(3.5 ns)
36

Download Report