1 1
多分岐決定図に基く
多分岐決定図に基く
プロセッサとその応用
プロセッサとその応用
中原 啓貴
九州工業大学 情報工学部 電子情報工学系
2 2
研究テーマ
研究テーマ
• 論理関数のデータ構造
– 多値（多分岐）決定図
• 論理回路の設計検証
– 形式的検証
– 論理シミュレーション
• 再構成可能アーキテクチャ (FPGA)
– ネットワーク・セキュリティー・ハードウェア
• アクセス・コントローラ
• ウイルス検出器
• パケット・トラフィック・コントローラ
3
3
概要
概要
• 研究背景
• 二分岐決定図 (BDD: Binary Decision Diagram)
• 多分岐決定図 (MDD: Multi-valued DD)
• 決定グラフマシン
(DDM: Decision Diagram
Machine)
• 先読みMDDマシン
• 実験結果
• まとめと今後の課題
4
4
決定グラフマシン
決定グラフマシン
(
(
DDM
DDM
: Decision Diagram Machine)
: Decision Diagram Machine)
• 出力命令と分岐命令を持つ特定用途向けプロセッサ
• 決定グラフを評価
• 汎用の組込みプロセッサと比較して
– 高速
– コンパクト
– 低消費電力
• 応用分野
– 制御回路
– ネットワーク機器
(ルータ・侵入検知システム・ウイルスチェック等)
5
5
決定グラフマシンの歴史
決定グラフマシンの歴史
R. Boute, "The binary decision machine as programmable
controller". Euromicro Newsletter 2, 1, pp. 16-22 (Jan.
1976
).1971 1974 1976 1977 1979 1980 1981 Intel 4004 Intel 8008 TK-80(NEC) Cray-I Apple-II PC8001 PC9801 出展: IPSJ Computer Museum, NECパソコン博物館
6 6
ポスト
ポスト
Moore
Moore
時代
時代
1.E+03 1.E+04 1.E+05 1.E+06 1.E+07 1.E+08 1.E+09 1.E+10 1.E+11 1.E+121971
1974
1978
1982
1989
1997
2000
2006
2010
トランジスタ数
10-Core Xeon 8-Core Xeon Corei7(Quad) Core2Duo Itanium2 Pentium 4 Pentium III Pentium II Pentium 80486 80386 80286 8088 4004 8085 8008 8080 80862025
1.E+131μm
10μm
32nm
10nm
トランジスタの微細化によるプロセッサの高性能化に限界
7
7
電力効率
電力効率
• 熱（消費電力）がプロセッサの性能向上の障壁に
P. P. Gelsinger, “Microprocessors for the New Millennium:
Challenges, Opportunities, and New Frontiers,” ISSCC2001, pp. 22-25.
8 8
CMOS
CMOS
回路の消費電力
回路の消費電力
• 動的消費電力と静的消費電力の和
• 動的消費電力=N
a×C×V
2×f
N
a: 動作トランジスタ数
C: トランジスタ容量
V: 電源電圧
f: 動作周波数
• 静的消費電力=N
t×I
l×V
N
t: 全トランジスタ数
I
l: トランジスタ辺りのリーク電流
(90nm以降, 深刻化)
9 9
計算法の変更
計算法の変更
1+1?
3x4?
6÷7?
3-9?
従来の計算法
提案する計算法
多種の命令が必要
(算術演算, 論理演算,
メモリアクセス等)
単純な命令のみ
（「読む」命令）
3x4のページ
1+1のページ
3-9のページ
10 10
決定グラフ
決定グラフ
• 「読む」という動作を表現
分岐
と
出力
を行う命令で模擬
2 3
101
+
-
x
÷
1 2
1 2
1 2
1 2
1 2
100
演算子
オペランド
オペランド
出力
11 11
例題
例題
:
:
信号選択回路
信号選択回路
(MUX)
(MUX)
s
x
1x
2y
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
MUX
x
1
x
2
y
s
12 12
Binary Tree
Binary Tree
• 論理関数を表現する有向非環状木
• 非終端節点：
2つの分岐先のアドレスを保持
• 終端節点: 関数値を保持
s
x
1x
2y
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
0 0 1 1 0 1 0 11枝
0枝
x
1
x
2
s
y
13 13
簡約化
簡約化
規則
規則
1. 任意の同型な（isomorphic）サブグラフをマージ
2.
2つの子ノードが同型な節点を省略
f
f
f
14 14
簡約化
簡約化
の例
の例
s
x
1x
2y
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
0 1x
1
x
2
s
y
15
15
Binary Decision Diagram (BDD)
Binary Decision Diagram (BDD)
• 二分決定木に簡約化規則を適用
• 非終端節点：
2つの分岐先のアドレスを保持
• 終端節点: 関数値を保持
0 1x
1
x
2
s
y
0 0 1 1 0 1 0 1x
1
x
2
s
y
BT
BDD
16 16
BDD
BDD
の評価
の評価
• 入力値に応じて根節点から終端節点まで辿る
0 1x
1
x
2
s
y
BDD
s
x
1x
2y
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
0
1
1
1
1
17
17
決定グラフの尺度
決定グラフの尺度
メモリサイズ: # of nodes size of a node
平均評価時間:
APL (Average Path Length)
0
1
x
1
x
2
x
3
x
4
x
5
x
6
BDD
18 18
BDD
BDD
の節点数
の節点数
• 変数順序に影響
0 0 0 1 11 1x
1
x
2
s
y
1 0 1 0 1x
1
x
2
s
y
19 19
BDD
BDD
を模擬する命令セット
を模擬する命令セット
0 1x
1
x
2
s
y
２分岐命令
B_BRANCH (A0, A1), x
if( x == 0) then goto A0, else goto A1
出力＆ジャンプ命令
OUTPUT Data, A0
20 20
例
例
A1
A2
0 1A3
x
1
x
2
s
y
A4
A5
２分岐命令
B_BRANCH (A0, A1), x
if( x == 1) then goto A0, else goto A1
出力＆ジャンプ命令
OUTPUT Data, A0
Output <- Data, and goto A0
A1: B_BRANCH(A2,A3), s
A2: B_BRANCH(A4,A5), x1
A3: B_BRANCH(A4,A5), x2
A4: OUTPUT 0, A1
21 21
BDD
BDD
マシン
マシン
(BDDM)
(BDDM)
Memory
PC
Output Register
Inst. Register
Primary Inputsx
1x
2x
nx
iEnable signal
22 22
BDDM (2
BDDM (2
分岐命令
分岐命令
)
)
Memory
PC
Output Register
Primary Inputsx
1x
2x
nx
iEnable signal
23 23
BDDM (
BDDM (
出力命令
出力命令
)
)
Memory
PC
Output Register
Primary Inputsx
1x
2x
nx
iEnable signal
1 VALUE ADR24 24
マイクロプロセッサとの違い
マイクロプロセッサとの違い
--
アーキテクチャ
アーキテクチャ
-
-I ALU レジスタ PC メモリ レジスタ 選択回路 #レジスタ レジスタファイル 選択回路 選択回路 選択回路 +1 D 選択回路 I PC メモリ レジスタ A1 選択回路 レジスタ レジスタマイクロプロセッサ
(複雑)
決定グラフマシン
(単純)
A025 25
命令の比較
命令の比較
// C-code A_1: if( x[2] & 0x001) goto A_2; else goto A_10; A_2: if( x[1] & 0x002) goto A_4; else goto A_3; // ASM-code A_1: movl %eax, _x+8 testb %al, $1 je A_10 A_2: movl %eax, _x+4 testb %al, $2 jne A_4 // BM-code A_1: BRANCH (A_2,A_10), x[2] A_2: BRANCH (A_4,A_3), x[1]MPUは条件分岐を実行するのに
３命令必要
DDMは１命令で
条件分岐を実行可能
26 26
並列
並列
BDDM
BDDM
•
BDDMを128台並列に接続したプロセッサ
– 各プロセッサ毎にメモリを持つ
– 階層構造
– プロセッサ間接続回路を設計
•
FPGA上に実装
•
Intel社Core2Duoとの比較
– ピーク性能で約100倍高速
– 消費電力4分の1
• 欠点: 高コスト
H. Nakahara, T. Sasao, M. Matsuura, and Y. Kawamura, "A parallel branching program
machine for sequential circuits: Implementation and evaluation,"
27 27
要求項目
要求項目
• 電力効率
– 高速処理
– 低消費電力
• 低コスト
– 安価な既製品で構成
28 28
FPGA
FPGA
CLB: Configurable
Logic Block
Block RAM
29 29
FPGA
FPGA
のリソース数と価格
のリソース数と価格
1728 4320 8064 17280 29952 13824 24192 41472 59904 80640 110592 152064 200448 ¥900¥1,345 ¥2,406 ¥5,533 ¥10,781 ¥9,724¥18,818 ¥39,133¥54,315 ¥92,913 ¥169,789¥274,998 ¥517,600 1000 10000 100000 1000000 XC3S50 XC3S200 XC3S400 XC3S1000 XC3S1500 XC4VLX15 XC4VLX25 XC4VLX40 XC4VLX60 XC4VLX80 XC4VLX100 XC4VLX160 XC4VLX200Device
# Logic Cells
100 1000 10000 100000 1000000# Logic Cells (Spartan III)
Price (JP YEN)
Price (Japan YEN)
# Logic Cells (Virtex IV)
30
30
多値（多分岐）決定図
31
31
Multi
Multi
-
-
Valued Decision Diagram (MDD)
Valued Decision Diagram (MDD)
•
BDD: 2分岐(二値)決定図, MDD: 多分岐(多値)決定図
–
MDD(k): 2
k分岐
–
k ビットを同時に評価
0
1
x
1
x
2
x
3
x
4
x
5
x
6
BDD
0
1
X
3
X
2
X
1
{x
5
,x
6
}
{x
3
,x
4
}
{x
1
,x
2
}
MDD(2)
32 32
分岐数とメモリ量
分岐数とメモリ量
• 節点の入力数: k
• 分岐数: 2
k
index A0 A1 index A0 A1 A2 A3 index A0 A1 A2 A3 A4 A5 A6 A7k=1
k=2
k=3
A0 A1 A0 A1 A2 A3 A0A1A2 A733 33
ホモジニアス
ホモジニアス
MDD
MDD
とヘテロジニアス
とヘテロジニアス
MDD
MDD
• 各節点の入力数が等しい:
ホモジニアスMDD (MDD(k))
• 各節点の入力数は異なる:
ヘテロジニアスMDD (HMDD)
X
2
X
3
X
1
{x
1
,x
2
}
{x
4
,x
5
,x
6
}
{x
3
}
HMDD
0
1
0
1
X
3
X
2
X
1
{x
5
,x
6
}
{x
3
,x
4
}
{x
1
,x
2
}
QDD (MDD(2))
34
34
メモリ量と評価時間
メモリ量と評価時間
Small memory,
but slow evaluation
Fast evaluation,
but large memory
HMDDマシンはメモリ量を増加させることで,
高速に評価可能
35 35
HMDD
HMDD
に基くプロセッサ
に基くプロセッサ
従来プロセッサ
HMDDに基くプロセッサ
動的
消費電力
削減
静的
消費電力
削減
安価なFPGA+メモリ
36
36
先読みヘテロジニアス
37 37
ヘテロジニアス
ヘテロジニアス
MDD
MDD
マシン
マシン
• ヘテロジニアスMDDを模擬
– 間接分岐方式
– 直接分岐方式
• ２種類のヘテロジニアスMDDマシンを比較
– 先読みを行わない
間接分岐方式
– 先読みを行う
間接分岐方式
H. Nakahara, T. Sasao and M. Matsuura, "A comparison of architectures for various decision diagram machines," ISMVL2010, 2010, pp.229-234.
H. Nakahara, T. Sasao, and M. Matsuura "On a prefetching heterogeneous MDD machine," MWSCAS2011, Korea August 7-10, 2011.
38 38
直接分岐方式
直接分岐方式
0
1
x
1
x
2
x
3
x
4
x
5
x
6
BDD
X6 A0 A1 X5 A2 A3 X4 A2 A4 X3 A5 A6 X3 A7 A8 X2 A9 A10 X2 A5 A10 X1 A5 A10 0 A0 1 A039 39
直接分岐方式
直接分岐方式
(
(
ヘテロジニアス
ヘテロジニアス
MDD)
MDD)
X
2
X
3
X
1
{x
1,x
2}
{x
3
}
0
1
HMDD
{x
4
,x
5
,x
6
}
X2 A3 A4 X2 A5 A6 X1 A6 A7 A7 A6 X1 A7 A6 A7 A6 X3 A1 A2 A2 A2 A1 A2 A1 A2 0 A0 1 A040 40
間接分岐方式
間接分岐方式
• インデックスと各分岐先のアドレスを各ワードに格納
– 分岐先アドレス = ベースアドレス+入力値 – 評価に2ステップ必要 index A0 A1 index A0 A1 A2 A3 index A0 A1 A2 A3 A4 A5 A6 A7k=1
k=2
k=3
A0 A1 A0 A1 A2 A3 A0A1A2 A741 41
間接分岐方式
間接分岐方式
(
(
ヘテロジニアス
ヘテロジニアス
DD)
DD)
X
2
X
3
X
1
{x
1,x
2}
{x
3
}
0
1
HMDD
{x
4
,x
5
,x
6
}
X3 A1 A2 A2 A2 A1 A3 A2 A1 X2 A3 A4 X2 A5 A6 X1 A6 A7 A7 A6 X1 A7 A6 A6 A7 0 A0 1 A042 42
間接分岐方式
間接分岐方式
HMDD
HMDD
マシン
マシン
(HMDDM)
(HMDDM)
Memory
Primary
Inputs
0: Branch
1: Output
+
PC
+1
1 00: Fetch inputs
1: Jump
Control
0 1X
1
X
2
X
m
Output Register
Enable
Input Register
43 43
ヘテロジニアス
ヘテロジニアス
MDD
MDD
マシン
マシン
• ヘテロジニアスMDDを模擬
– 間接分岐方式
– 直接分岐方式
• ２種類のヘテロジニアスMDDマシンを比較
– 先読みを行わない
間接分岐方式
– 先読みを行う
間接分岐方式
H. Nakahara, T. Sasao and M. Matsuura, "A comparison of architectures for various decision diagram machines," ISMVL2010, 2010, pp.229-234.
H. Nakahara, T. Sasao, and M. Matsuura "On a prefetching heterogeneous MDD machine," MWSCAS2011, Korea August 7-10, 2011.
44 44
先読みを行わない間接分岐方式
先読みを行わない間接分岐方式
(
(
従来手法
従来手法
)
)
X
2
X
3
X
1
{x
1,x
2}
{x
3
}
0
1
HMDD
{x
4
,x
5
,x
6
}
{x
3
}
X
2
{x
1,x
2}
X
1
X
3
{x
4
,x
5
,x
6
}
{x
4
,x
5
,x
6
}
{x
4
,x
5
,x
6
}
{x
4
,x
5
,x
6
}
{x
4
,x
5
,x
6
}
{x
4
,x
5
,x
6
}
X
3
45 45
先読みを行う間接分岐方式
先読みを行う間接分岐方式
X
2
X
3
X
1
{x
1,x
2}
{x
3
}
0
1
HMDD
{x
4
,x
5
,x
6
}
X
3
{x
4
,x
5
,x
6
}
{x
4
,x
5
,x
6
}
{x
4
,x
5
,x
6
}
{x
4
,x
5
,x
6
}
{x
4
,x
5
,x
6
}
{x
4
,x
5
,x
6
}
X
3
{x
3
}
X
2
{x
1,x
2}
X
1
46 46
先読みを行う間接分岐方式
先読みを行う間接分岐方式
• 分岐先のアドレスを読込むときに, 分岐先のイン
デックスも同時に読み込み
– １ステップで評価可能
– ワード長が増加（一般的には２倍）
A0 A1 A4 A2 A3X0
X1
X2
A1 X1 A4 X2 A2 X1 A3 X1 節点A0に 割当てた メモリ空間 00 01 10 11分岐先の
インデックス
A0 A1 A0 A2 A1 A0 A3 A2 A1 A0 A4 A3 A2 A1 A047 47
命令セットの比較
命令セットの比較
先読みを行わない間接分岐方式
先読みを行う間接分岐方式
分岐命令
出力命令
分岐命令
出力命令
0 IDX A_0 A_1 A_2k-1 1 OUTPUT JUMP ADR0 A_0 IDX for A_0 0 A_1 IDX for A_1
0 A_2k-1 IDX for A_2k-1
1 OUTPUT JUMP ADR
48
48
実験結果
49
49
FPGA
FPGA
に実装した結果
に実装した結果
•
2種のHMDDマシンを実装
–
FPGA: Altera社 Cyclone III Starter Kit
• EP3C25 • LE数: 24,624 • M4K数: 66個 • 外付けSSRAM １個 – 16入力32出力(先読み無し方式) – 15入力64出力(先読み有り方式)
• 実装結果
方式 LE数 ピン数 動作周波数 先読み無し 348 202 93.1 MHz 先読み有り 239 234 110.1 MHz50 50
他のマシンとの比較
他のマシンとの比較
•
MCNCベンチマーク関数を使用
– 単一出力関数に分割
– 個々の関数に対して変数順序を最適化
•
MDD(2) マシン
–
200MHzで動作
•
Intel社 Core2Duo U7600
–
BDDマシンをCコードで模擬
– 動作周波数: 1.2GHz, コンパイラ: gcc, OS: Windows XP
• 先読みHMDDMマシン
–
100MHzで動作
51 51
実行時間の比較
実行時間の比較
12030 13450 17500 19170 3700 3468 6390 7039 5907 6493 8317 2971 2425 5299 1761 3528 2041 1561 281 88 361 1509 2831 1090 1253 249 88 337 1005 2567 830 1103 248 83 312 0 5000 10000 15000 20000 s5378 (in:35,out:49,ff:164) s9234 (in:36,out:39,ff:211) dsip (in:229,out:197,ff:224) bigkey (in:263,out:197,ff:224) apex6 (in:135,out:99) cps (in:24,out:102) frg2 (in:143,out:139)実行時間
[nsec]
HMDDM(4MB)@100MHz HMDDM(2MB)@100MHz HMDDM(1MB)@100MHz MDD(2)@200MHz Core2Duo@1.2GHz (低速) (高速)52 52
Intel Core2Duo@1.2GHz
Intel Core2Duo@1.2GHz
との
との
消費電力性能の比較
消費電力性能の比較
(
(
推定
推定
)
)
• 実行時間
–
16.22-20.08倍高速
• 消費電力
–
Core2Duo: 35W (TDP)
–
HMDDM: SRAM (0.5W)
+ FPGA (less than 1W)
53 53
