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