ソフトエラーを回避する LUTカスケード・エミュレータについて

Transcription

1 多 分 岐 決 定 図 に 基 く プロセッサとその 応 用 中 原 啓 貴 九 州 工 業 大 学 情 報 工 学 部 電 子 情 報 工 学 系 1

2 研 究 テーマ 論 理 関 数 のデータ 構 造 多 値 ( 多 分 岐 ) 決 定 図 論 理 回 路 の 設 計 検 証 形 式 的 検 証 論 理 シミュレーション 再 構 成 可 能 アーキテクチャ (FPGA) ネットワーク セキュリティー ハードウェア アクセス コントローラ ウイルス 検 出 器 パケット トラフィック コントローラ 2

3 概 要 研 究 背 景 二 分 岐 決 定 図 (BDD: Binary Decision Diagram) 多 分 岐 決 定 図 (MDD: Multi-valued DD) 決 定 グラフマシン (DDM: Decision Diagram Machine) 先 読 みMDDマシン 実 験 結 果 まとめと 今 後 の 課 題 3

4 決 定 グラフマシン (DDM:: Decision Diagram Machine) 出 力 命 令 と 分 岐 命 令 を 持 つ 特 定 用 途 向 けプロセッサ 決 定 グラフを 評 価 汎 用 の 組 込 みプロセッサと 比 較 して 高 速 コンパクト 低 消 費 電 力 応 用 分 野 制 御 回 路 ネットワーク 機 器 (ルータ 侵 入 検 知 システム ウイルスチェック 等 ) 4

5 決 定 グラフマシンの 歴 史 R. Boute, "The binary decision machine as programmable controller". Euromicro Newsletter 2, 1, pp (Jan. 1976). Intel 4004 TK-80(NEC) Apple-II Intel 8008 Cray-I PC8001 PC9801 出 展 : IPSJ Computer Museum, NECパソコン 博 物 館 5

6 トランジスタ 数 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 ポストMoore 時 代 10μm 1μm 32nm 10nm Pentium Pentium II 10-Core Xeon 8-Core Xeon Corei7(Quad) Core2Duo Itanium2 Pentium Pentium III トランジスタの 微 細 化 によるプロセッサの 高 性 能 化 に 限 界 6

7 電 力 効 率 熱 ( 消 費 電 力 )がプロセッサの 性 能 向 上 の 障 壁 に P. P. Gelsinger, Microprocessors for the New Millennium: Challenges, Opportunities, and New Frontiers, ISSCC2001, pp 消 費 電 力 当 りの 性 能 が 重 要 に 7

8 CMOS 回 路 の 消 費 電 力 動 的 消 費 電 力 と 静 的 消 費 電 力 の 和 動 的 消 費 電 力 =N a C V 2 f N a : 動 作 トランジスタ 数 C: トランジスタ 容 量 V: 電 源 電 圧 f: 動 作 周 波 数 静 的 消 費 電 力 =N t I l V N t : 全 トランジスタ 数 I l : トランジスタ 辺 りのリーク 電 流 (90nm 以 降, 深 刻 化 ) 8

9 計 算 法 の 変 更 従 来 の 計 算 法 提 案 する 計 算 法 3x4? 1+1? 3x4のページ 1+1のページ 6 7? 3-9? 3-9のページ 多 種 の 命 令 が 必 要 ( 算 術 演 算, 論 理 演 算, メモリアクセス 等 ) 単 純 な 命 令 のみ ( 読 む 命 令 ) 9

10 読 む という 動 作 を 表 現 決 定 グラフ 分 岐 と 出 力 を 行 う 命 令 で 模 擬 演 算 子 + - x オペランド オペランド 出 力

11 例 題 : 信 号 選 択 回 路 (MUX) s x 1 x 2 y x 1 x 2 MUX s y

12 Binary Tree 論 理 関 数 を 表 現 する 有 向 非 環 状 木 非 終 端 節 点 : 2つの 分 岐 先 のアドレスを 保 持 終 端 節 点 : 関 数 値 を 保 持 1 枝 s x 1 x 2 y y x 2 x 1 s 0 枝

13 簡 約 化 規 則 1. 任 意 の 同 型 な(isomorphic)サブグラフをマージ f f f 2. 2つの 子 ノードが 同 型 な 節 点 を 省 略 13

14 簡 約 化 の 例 s x 1 x 2 y x 1 x 2 y s

15 Binary Decision Diagram (BDD) 二 分 決 定 木 に 簡 約 化 規 則 を 適 用 非 終 端 節 点 : 2つの 分 岐 先 のアドレスを 保 持 終 端 節 点 : 関 数 値 を 保 持 s s x 1 x 1 x 2 x 2 y y 0 1 BT BDD 15

16 BDDの の 評 価 入 力 値 に 応 じて 根 節 点 から 終 端 節 点 まで 辿 る s x 1 x 2 y s x 1 x 2 y 0 1 BDD 16

17 決 定 グラフの 尺 度 x 6 x 5 x 4 x 3 x 2 x BDD メモリサイズ: # of nodes size of a node 平 均 評 価 時 間 : APL (Average Path Length) 17

18 変 数 順 序 に 影 響 BDDの の 節 点 数 x 1 s x 2 x 1 s x 2 y y

19 BDDを を 模 擬 する 命 令 セット s x 1 x 2 y 分 岐 命 令 B_BRANCH (A0, A1), x if( x == 0) then goto A0, else goto A1 出 力 &ジャンプ 命 令 OUTPUT Data, A0 Output <- Data, and goto A0 19

20 例 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

21 BDDマシン (BDDM) PC Memory Inst. Register Primary Inputs x 1 x 2 x x i n Enable signal Output Register 21

22 BDDM (2 分 岐 命 令 ) PC Memory 0 IDX ADR0 ADR1 Primary Inputs x 1 x 2 x x i n Enable signal Output Register 22

23 BDDM ( 出 力 命 令 ) PC Memory 1 VALUE ADR Primary Inputs x 1 x 2 x x i n Enable signal Output Register 23

24 マイクロプロセッサとの 違 い -アーキテクチャ- 選 択 回 路 PC PC レジスタファイル 選 択 回 路 選 択 回 路 #レジスタ レジスタ メモリ レジスタ I D I メモリ レジスタ A1 A0 +1 選 択 回 路 選 択 回 路 選 択 回 路 ALU レジスタ マイクロプロセッサ ( 複 雑 ) レジスタ 決 定 グラフマシン ( 単 純 ) 24

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は 条 件 分 岐 を 実 行 するのに 3 命 令 必 要 DDMは1 命 令 で 条 件 分 岐 を 実 行 可 能 25

26 並 列 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

27 要 求 項 目 電 力 効 率 高 速 処 理 低 消 費 電 力 低 コスト 安 価 な 既 製 品 で 構 成 27

28 FPGA CLB: Configurable Logic Block Block RAM 28

29 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, ,406 1, ,533 XC3S50 XC3S200 XC3S400 XC3S1000 XC3S1500 XC4VLX15 XC4VLX25 XC4VLX40 XC4VLX60 XC4VLX80 XC4VLX100 XC4VLX160 XC4VLX200 # Logic Cells Device Price (Japan YEN) 注 : デバイス1 個 で 購 入 時 の 価 格 (2010 年 12 月, Digikey)

30 多 値 ( 多 分 岐 ) 決 定 図 30

31 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

32 節 点 の 入 力 数 : 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

33 ホモジニアス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

34 メモリ 量 と 評 価 時 間 Small memory, but slow evaluation Fast evaluation, but large memory HMDDマシンはメモリ 量 を 増 加 させることで, 高 速 に 評 価 可 能 34

35 HMDDに に 基 くプロセッサ 動 的 消 費 電 力 削 減 静 的 消 費 電 力 削 減 従 来 プロセッサ HMDDに 基 くプロセッサ 安 価 なFPGA+メモリ 35

36 先 読 みヘテロジニアスMDD MDDマシン 36

37 ヘテロジニアスMDD MDDマシン ヘテロジニアスMDDを 模 擬 間 接 分 岐 方 式 直 接 分 岐 方 式 H. Nakahara, T. Sasao and M. Matsuura, "A comparison of architectures for various decision diagram machines," ISMVL2010, 2010, pp 種 類 のヘテロジニアスMDDマシンを 比 較 先 読 みを 行 わない 間 接 分 岐 方 式 先 読 みを 行 う 間 接 分 岐 方 式 H. Nakahara, T. Sasao, and M. Matsuura "On a prefetching heterogeneous MDD machine," MWSCAS2011, Korea August 7-10,

38 直 接 分 岐 方 式 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

39 直 接 分 岐 方 式 (ヘテロジニアス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

40 間 接 分 岐 方 式 インデックスと 各 分 岐 先 のアドレスを 各 ワードに 格 納 分 岐 先 アドレス = ベースアドレス+ 入 力 値 評 価 に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

41 間 接 分 岐 方 式 (ヘテロジニアス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

42 間 接 分 岐 方 式 HMDDマシン (HMDDM) Primary Inputs X 1 X 2 X m +1 + PC : Branch 1: Output Memory Input Register 0: Fetch inputs 1: Jump Control Enable Output Register 42

43 ヘテロジニアスMDD MDDマシン ヘテロジニアスMDDを 模 擬 間 接 分 岐 方 式 直 接 分 岐 方 式 H. Nakahara, T. Sasao and M. Matsuura, "A comparison of architectures for various decision diagram machines," ISMVL2010, 2010, pp 種 類 のヘテロジニアスMDDマシンを 比 較 先 読 みを 行 わない 間 接 分 岐 方 式 先 読 みを 行 う 間 接 分 岐 方 式 H. Nakahara, T. Sasao, and M. Matsuura "On a prefetching heterogeneous MDD machine," MWSCAS2011, Korea August 7-10,

44 先 読 みを 行 わない 間 接 分 岐 方 式 ( 従 来 手 法 ) X 3 {x 4,x 5,x 6 } X 2 {x 3 } X 2 X 1 {x 1,x 2 } 0 1 HMDD 44

45 先 読 みを 行 う 間 接 分 岐 方 式 X 3 {x 4,x 5,x 6 } X 2 {x 3 } X 2 X 1 {x 1,x 2 } 0 1 HMDD 45

46 先 読 みを 行 う 間 接 分 岐 方 式 分 岐 先 のアドレスを 読 込 むときに, 分 岐 先 のイン デックスも 同 時 に 読 み 込 み 1ステップで 評 価 可 能 ワード 長 が 増 加 ( 一 般 的 には2 倍 ) 分 岐 先 の インデックス X1 X2 X0 00 A1 A A2 A4 A3 節 点 A0に 割 当 てた メモリ 空 間 A1 A4 A2 A3 X1 X2 X1 X1 46

47 命 令 セットの 比 較 先 読 みを 行 わない 間 接 分 岐 方 式 分 岐 命 令 出 力 命 令 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 実 験 結 果 48

49 FPGAに に 実 装 した 結 果 2 種 のHMDDマシンを 実 装 FPGA: Altera 社 Cyclone III Starter Kit EP3C25 実 装 結 果 LE 数 : 24,624 M4K 数 : 66 個 外 付 けSSRAM 1 個 16 入 力 32 出 力 ( 先 読 み 無 し 方 式 ) 15 入 力 64 出 力 ( 先 読 み 有 り 方 式 ) 方 式 LE 数 ピン 数 動 作 周 波 数 先 読 み 無 し MHz 先 読 み 有 り MHz 49

50 他 のマシンとの 比 較 MCNCベンチマーク 関 数 を 使 用 単 一 出 力 関 数 に 分 割 個 々の 関 数 に 対 して 変 数 順 序 を 最 適 化 MDD(2) マシン 200MHzで 動 作 Intel 社 Core2Duo U7600 BDDマシンをCコードで 模 擬 動 作 周 波 数 : 1.2GHz, コンパイラ: gcc, OS: Windows XP 先 読 みHMDDMマシン 100MHzで 動 作 メモリ 量 制 限 : 1MB, 2MB, 4MB 50

51 実 行 時 間 の 比 較 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) ( 高 速 ) 実 行 時 間 [nsec] ( 低 速 )

52 Intel 消 費 電 力 性 能 の 比 較 ( 推 定 ) 実 行 時 間 倍 高 速 消 費 電 力 Core2Duo: 35W (TDP) HMDDM: SRAM (0.5W) + FPGA (less than 1W) HMDDMは 消 費 電 力 効 率 で2 桁 優 れている 52

53 まとめ 多 分 岐 決 定 図 に 基 くプロセッサ メモリ 量 を 増 加 させることで, 性 能 向 上 コンパクトなプロセッサ( 制 御 回 路 ) メモリアクセス 回 数 の 削 減 : 低 クロック 先 読 みHMDDマシン 多 分 岐 決 定 図 を 模 擬 プリフェッチ( 先 読 み)を 行 う 安 価 な 既 製 品 で 構 成 可 プロトタイプをFPGA+SRAM 上 に 実 装 消 費 電 力 効 率 で 汎 用 MPUよりも2 桁 優 れる 53