Timing Optimization Techniques

VLSI設計工学６
•
•
•
•
タイミング解析・最適化
順序回路合成の基本
順序回路マクロ
６月１４，２１日は石原先生による代講
– 設計の上位レベルの設計手法とその支援法
– ソフトウェアを書くようにハードウェアを書く（設計する）
1
タイミング最適化設計の流れ
論理合成
レイアウト前、タイミング最適化
not ok
レイアウト前のタイ
ミング制約を満たす？
back annotation
問題点
– 最適化ルーチンでは、レイアウ
ト後の実際の配線容量や遅延
モデルとは異なるモデルで最
適化している
• タイミング最適化が収束し
にくい
RTL spec
フロントエンド
•
フロントエンドとバックエンドは別々
– レイアウト後の情報を戻して（
back annotation）、タイミング
最適化を繰り返す
バックエンド
•
ok
配置・配線
レイアウト後、タイミング最適化
実タイミング
制約を満たす？
not ok
ok
マスクパターン
2
タイミング最適化というのは、
なかなか収束しない！
タイミングエラー数
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
繰り返し回数
3
基本事項・定義
•
•
信号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）
クリティカルパス: 最小のスラックをもつ信号の集合
タイミング最適化の目標: スラックの最小値を最大化する
4
タイミング最適化の基本プロシージャ
基本ルーチン {
タイミング解析;
while ( 目標に到達していない) {
次のクリティカルな場所を選ぶ;
その場所を回路変換する;
タイミング解析;
critical region
if (スラックの最悪値が向上した)
回路変換を受け入れる;
else
回路を元に戻す;
}
}
critical path
•
レイアウト前、レイアウト中、レイアウト後に適用される
– それぞれ、異なるタイミングモデルの上に定義された、異なる回路変換
が適用される
5
逐次的タイミング解析によるスラックの更新
• 回路の部分的な変更に対して：
– 回路の順方向に arrival time を更新
• 変更部分の直前の入力からスタート
– 回路の逆方向に required time を更新
• 順方向に更新した際に、扱ったゲートからスタート
– ゲートの入力信号変化が変わるとそのゲートの遅延値は変化
逆方向に
required time を
更新
変更回路
部分
順方向に
arrival time を
更新
• 基本的に、遅延値の変化がなくなった時点で終了
6
論理関数の展開
• 関数 G を F の中に展開する（ a がクリティカルと仮定）
F = cG
G=a+b
a
b
a+b
F = ac + bc
G
cG
c
2 levels
F
a
b
c
ac+bc
F
1 level
– 論理段数が減少
• 面積増大を考慮する必要（面積はリテラル数で数える）
– クリティカルパス上で部分的に展開する
– 必要なら積和形論理簡単化プログラムを実行する (espresso)
• 論理関数の分割処理をこの後行う
7
論理関数の分割
• 論理関数 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’
（割り算の結果は一意）
8
タイミングを考慮した論理関数の展開を分割
• f をクリティカルパスに沿って、部分的に展開し、新たな論理関数 k
で割り算する
– 基本戦略：クリティカルな信号をより出力側へもっていく
f
f
f
展開された
ノード
a
a
e
b
e
b
c d
k
divisor
a
e
c
d
b
c
d
クリティカルパス
9
テクノロジを考慮した関数分割
• まず、与えられた関数を NAND2/INV だけからなる回路に分割
– 小さいゲートの集合:
• セルライブラリを使って実現できることが保証されている
– ライブラリに４入力NANDはないかもしれない
• テクノロジマッピングしやすい
• タイミングへの影響大
– タイミングを考慮して分割
a
b
c
d
a
b
a
b
c
d
c
d
a, b, c, dが同じくらいクリティカル
Dが最もクリティカル
10
ゲートサイジング／ピン交換
• 等価セルで大きさのことなるものに変える
– ゲートのドライブ力、遅延、入力容量が変化する
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
11
バッファ挿入
• ファンアウト負荷の削減する方法
– クリティカルパスを分離する
• クリティカルではないところにバッファを挿入する
critical path
– 負荷を合わせる
• すべての分岐の負荷を同じにする
12
リタイミング
• 元のクロック周期 = 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)
13
同期式順序回路の概念図
• 組み合せ回路とエッジトリガフリップフロップ
外部入力
n
m
外部出力
組み合せ回路
状態変数
（現状態）
k
k
状態変数
（次状態）
クロック
エッジトリガフリップフロップ
14
順序回路の表現
in 4
Present State
Latch
Primary Output
out 1
in 3
(1010, 0110)/1
in 1
in 2
(--00, 11-0)/0
Primary inputst
0
----/1
• 回路
• STG (Signal
Transition Graph)
• 状態遷移関係
(Transition Relation)
---1/1
1
Next State
Gates and Latches
(Netlist)
State Transition Graph
(STG)
ns1
pi
ps
ns'
1 ns
2
ns'
2 ns
3
ns'
3
ns
n
ns'n
Transition Relation
15
Verilogによる設計例：交通信号制御回路
module hwy_control(clk, car_present, enable_hwy,
short_timer, long_timer, hwy_light,
hwy_start_timer, enable_farm);
input clk,car_present,enable_hwy,short_timer,
long_timer;
output hwy_light,hwy_start_timer,enable_farm;
boolean wire car_present;
wire short_timer, long_timer, hwy_start_timer,
enable_farm, enable_hwy;
color reg hwy_light;
initial hwy_light = GREEN;
assign hwy_start_timer = (((hwy_light == GREEN)
&& ((car_present == YES) && long_timer))
||
(hwy_light == RED) && enable_hwy);
assign enable_farm=((hwy_light==YELLOW)&&short_timer);
always @(posedge clk) begin
case (hwy_light)
GREEN: if ((car_present == YES) &&
long_timer) hwy_light = YELLOW;
YELLOW: if (short_timer) hwy_light = RED;
RED: if (enable_hwy) hwy_light = GREEN;
endcase
end
endmodule
16
状態遷移グラフと状態遷移表
(Signal Transition Graph, Signal Transition Table)
• 交通信号制御回路のmealy machineによる記述
not(c and t1)/
hl = GREEN; fl = RED; st = 0
ts/
HG
hl = RED; fl = YELLOW; st = 0
not(ts)/
hl = RED; fl = YELLOW; st = 0
FY
c and t1/
hl = GREEN; fl = RED; st = 1
HY
not(c) or t1/
hl = RED; fl = GREEN, st = 1
FG
not(ts)/
hl = YELLOW; fl = RED; st = 0
ts/
hl = YELLOW; fl = RED; st = 1
not(not(c) or t1)/
hl = RED; fl = GREEN; st = 0
State Transition Graph: Example
PS
HG
HG
HY
HY
FG
FG
FY
FY
IN
not(c and t1)
c and t1
not(ts)
ts
not(not(c) or t1)
not(c) or t1
not(ts)
ts
NS
HG
HY
HY
FG
FG
FY
FY
HG
OUT
hl = GREEN; fl = RED; st = 0
hl = GREEN; fl = RED; st = 1
hl = YELLOW; fl = RED; st = 0
hl = YELLOW; fl = RED; st = 1
hl = RED; fl = GREEN; st = 0
hl = RED; fl = GREEN; st = 1
hl = RED; fl = YELLOW; st = 0
hl = RED; fl = YELLOW; st = 1
State Transition Table: Example
17
順序回路論理合成、最適化
• 有限状態ステートマシン（Finite State Machine）を操作
• 分割（decomposition）と展開（collapse）
decompose
FSM
FSM
FSM
FSM
collapse
• FSMをFSMで論理的に割る（FSMの割り算）
x
x
M
Q
z
z
M1
M
• 組合せ回路論理合成、最適化に比べ、アルゴリズムとして改良の余
地は大きい
18

Download Report