Timing Optimization Techniques

ＶＬＳＩ設計工学２
論理合成技術
•
•
•
•
•
•
論理合成の流れ
ルールによる論理回路簡単化
論理式の多段化：論理式の割り算
回路の解析による簡単化
テクノロジマッピング
多段論理式簡単化
1
設計の流れ（基本）とハードウェア記述言語
(Hardware Description Language, HDL)
module WaitState(load,lo
input load;
input [1:0] loadValue
always @(positive Clk)
if (load)
仕様（RTL)
動作合成
論理合成
より詳細な設計レベルほど：
・面積・遅延見積もりはより正確
・回路変換の余地はより小さい
LSIの大規模化により、計算機
設計支援技術(CAD: Computer
Aided Design)なしでは設計で
きない！
配置
配線
2
ハードウェア記述言語（HDL)による仕様の記述
論理式への変換（HDLのコンパイル）
含む：状態割り当て
論理式簡単化
テクノロジマッピング
配置・配線へ
図２
3
a
a
x
b
x
b
(a) x=a’b+ab’
a
x
b
(b) x=a+a’b
a
x
b
(c) x=a+b
図１
4
(a) 簡単化対象回路
(c) ルールによる回路変換例
(b) 回路変換のルールの例
図３
5
c’d’
c’d
cd
c’d
cd
cd’
a’b’
a’b’
1
a’b
1
ab
ab’
c’d’
cd’
1
1
1
1
1
ab
ab’c’ + ac’d + bcd + a’bc
c’d
cd
cd’
1
1
a’b’
a’b
ab’
c’d’
1
1
1
1
1
a’b
ab
ab’
1
1
1
1
ab’c’ + abd + a’bc ab’c’ + abc’d + abcd + a’bc
(a)
(b)
(c)
図４
6
２段論理式（積和形論理式)簡単化
•
•
•
主項（prime implicant）をすべて生成して、最小数で与えられた論理をカバ
ーするものを見つける
– 従来は、１２変数くらいまで（1980年代まで）。後で述べるBDDを使うと２
０変数くらいまでは可能（1990年代から）
発見的手法（heuristic methods）
– 繰り返し改善
– 繰り返しの単位
• 項の縮小（reduce）
• 項の拡大（expand）
– 否定を利用する／しない
» 否定の式が爆発してしまう場合がある
• 冗長項の除去（irredundant）
– 数百変数での扱える（1980年代から）
– 最適解との差は項の数で数％程度以下
最近の動向
– 後で説明するBDDの利用
– 後で説明するSAT手法の利用
7
多段論理回路の合成
•
処理ステップ
1. 積和形論理式簡単化
2. 多段化（論理式の割り算）
3. 多段論理式簡単化
4. テクノロジマッピング
5. 多段論理回路簡単化
•
タイミング最適化は、随時挿入される
– 最大、最小遅延の最適化
8
積和形論理式と多段論理式
•
•
•
•
•
積和形論理式＝ AND-ORの２段
多段論理式＝３段以上の任意の形
一般的には、多段論理式の方がコンパクトな表現になる
– ace + ade + bce + bde + cf + df = (c + d)(e(a + b) + f)
回路面積の目安＝リテラル数
– １６ → ６
回路遅延の目安＝２入力基本ゲートで表現した時の段数
– ５段 → ４段
9
a
b
a+b+c
t1
t1t2
c
y
d
t2
e
f
g
d’+ef+gh
t1=a+b+c
t2=d’+ef+gh
y=t1t2
h
図５
10
a
b
ace+bce+de+g
f1
ad+bd+cde+eg
f2
c
d
e
abc
g
f3
a
b
a+b
t1
t1ce+de+g
f1
t1d+cde+eg
f2
c
d
e
abc
g
図６
f3
11
論理式の割り算
•
•
•
f = gh + r
– fをｇで割った商がhで、あまりがr
– 一般的には、hとrはユニークには決まらない
hとrに制限をつけない＝論理的割り算
– 無限通りの割り方がある
– １回の割り算に積和形論理式の簡単化と同じ手間がかかる
ghを代数的積に制限する＝代数的割り算
– 結果がユニークにできる
– O(n log n)の手間で計算できる
– そんなに悪くないことが多い
12
論理式の代数的処理
•
•
代数的論理式とは、論理関数の積和形論理式表現で、他の１つのキューブ
に含まれるキューブ（single cube containmentと呼ぶ）のないもの
– ab + abc + cdは代数的論理式ではない
– ab + cdは代数的論理式
代数式fとgの代数的積fgとは、fgを展開し、single cube containmentに
ついて冗長性を取ったもの
– fとgに共通な変数がないとfgは必ず代数的積
– (a + b)(c + d) = ac + ad + bc + bdは代数的積
– (a + b)(a + c) = aa + ac + ab + bc = a + bcは代数的積ではない
13
論理式の割り算の例
f= ad + ae + bcd + j
g1 = a + bc
g2 = a + b
• fをg1で代数的に割ると、商はd、あまりはae + j
• fをg2で代数的に割ると、商は(a + bc)d、あまりはae + j （代数的
には割れない）
14
Weak division
•
•
•
代数的割り算であまりのキューブ数最小のもの
定理： weak divisionの結果はユニーク
割り算の手間はO(n log n) nは積項数
15
c
b
d
e
c
d
a
b
f
4
1
5
2
6
e
c
a
b
f
7
8
9
o2
3
(a)
c
b
d
o1
4
1
2
5
o1
8
9
o2
3
(b)
図７
16
a
b
c
１
(b)
(a)
a
c
0
d１
b
２
c
a
b
２
c
(d)
( c)
図８
17
c
4
b
d
1
5
e
c
d
a
b
f
2
6
8
7
9
o2
3
(a)
c
1
0
o1
b
d
e
c
0 d
1a
1b
1 f
1
2
0
0
4
0
5
0
矛盾
0 1
6
3
o1
1
7
1
8
1
9
o2
(b)
図９
18
c
4
b
d
e
c
d
a
b
f
1
5
2
6
e
c
a
b
f
7
8
9
o2
3
(c)
c
b
d
o1
4
1
2
5
o1
8
9
o2
3
(d)
図９
19
f
g
d
e
out
h
b
a
c
(a)
図１０
20
not(1)
nand2(2)
or(3)
nand3 (3)
and2(3)
oai21 (3)
aoi22 (4)
(b)
図１１
21
f
g
d
out
e
h
b
面積合計２３
a
(c )
c
図１２
22
f
and2(3)
g
d
aoi22(4)
or2(3)
out
e
h
b
or2(3)
nand2(2)
a
面積合計１８
nand2(2)
c
not(1)
図１３
(d)
23
f
g
d
nand3(3)
and2(3)
oai21(3)
F
e
h
b
面積合計１５
a
oai21 (3)
(e)
nand2(2)
c
not(1)
図１４
24
(a)
nand2 (3)
not (2)
nand3 (4)
nand4 (5)
and2 (4)
aio21 (4)
oai21 (4)
library
(b)
図６
25
5
nand2(3)
6
not(6) nand2(12)
not(5)
and2(8) nand3(11)
nand2(3) and2(4)
nand2(7) 4
nand4(8)
1
2
nand3(4)
3
not(10)
aoi21(8)
7
8
nand2(11)
nand3(13)
nand4(12)
（c）
図１５
26
aoi21
5
6
7
8
nand3
1
4
2
nand2
3
（d）
図１６
27
０
28
29
30
31
32
33
34

Download Report