設計仕様解析によるハード／ソフト最適分割システムの構築と評価立命館大学理工学研究科梅原直人，○和田智行，山崎勝弘 2007/9/5 研究背景 • 高速化、低消費電力化などにコデザインは必要 • 大規模化によるシステムの複雑化 • システムにはハードとソフトのバランスが必要目的 • ハード/ソフト最適分割システムの構築 • システムの設計仕様解析ツールの作成 • 実際にアプリケーション（暗号アルゴリズム）に適用し、システムの有効性を検証 2 ハード／ソフト分割探索 • モジュール数により分割領域が指数関数的に増加 • 人間の判断で行うには限界がある • シミュレーションによる数値解析にも限界 • ハード/ソフトの最適な分割を支援すること • 早期の予測による手戻り損失の減少 3 ハード/ソフト最適分割システム • C言語リファレンス・プロトタイプ作成段階から分割領域（境界）の特定 – 関数をハードウェアモジュールに対応システムの最終出力 Cソースコード int a(); char b(); void c(); Analysis & Answer Hardware Software int a(); char b(); void c(); • ユーザの要求から分割 – 速さ優先、消費電力優先、コスト優先、etc… 4 ソースコードと要求仕様を併せて、設計仕様と呼称設計仕様解析手法モジュール外部要素プリプロセッサ・関数抽出 C言語ソースコードモジュール（ファンクション）ファイルコード解析 CDFG 合成演算式評価データトレース FSM 合成設計仕様解析器モジュール毎の各要素の内部表現（CDFG・演算強度など）性能解析回路規模個別・相互評価速度メモリ量消費電力工数 5 設計仕様解析器 • • • • • 各関数はハードウェア・モジュールに1対1対応実装環境を考慮ユーザの要求を考慮（速度重視、メモリ重視、……など） goto文・malloc文・ポインタ・文字列操作はサポートしない実装言語はRuby Ｃ言語ファイルモジュールインスタンス(CDFG) int func(int B,int C){ } 処理の流れ int A,I,j; for(i=0;i<4;i++){ for(j=0;j<4;j++){ A=B+C; } } return A; rtm,true,[“int”.”int”] farg,”int”,[“B”,”C”] decl,””,[“A”,”i”,”j”] loop,”for”,0,”i”,0,”<4”,”++” loop,”for”,1,”i”,0,”<4”,”++” assign,2,[“A”],[“B”,”+”,”C”] ctrl,”return”,0,no_assign,”A” 構造の深度 6 Misty1暗号アルゴリズム • 64ビットブロック・128ビット秘密鍵暗号 • 条件分岐の一切ない構造 FL 平文（64bit） 32 16 16 64 bit KLi FL KLi+1 KLi1 FL KLi, Loop N times KOi KLi2 FO （ KLi+1, FO KOi+1 FO ） 16 9 32 16 S9 KOij FI KLn+1 FL KLn+2 暗号文（64bit） FL 7 16 KIij KIi2 S7 KIi1 S9 7 モジュール連結による実験 • MISTY1を最適分割実験に使用 – MISTY1は軽く、簡単な制御 e.g.モジュール連結による実験結果の計測 • ループ回数は100固定暗号化ブロック数は可変平文 MISTY1 BLOCK[0] インライン展開（連結） MISTY1 BLOCK[1] 大きな MISTY1 BLOCK[N] 暗号文ハードウェアモジュール • 連結によって意図的に巨大モジュールを作成 • 解析によってどのような変化が結果に出るのかを考察 8 実験環境 OPB SW処理 Block RAM DLL Clock ＋制御 UART RS232C Connector SDRAM control SDRAM MicroBlaze FSL FSL User Peripheral • • • • FSL FSL User Peripheral HW処理 Clock counter Xilinx社のソフトコアMicroBlazeを軸に構築 FSLでユーザペリフェラルと通信ツールと専用コンパイラが付属結果はUART-RS２３２Cからデスクトップへ FPGA 9 MISTY1単一ループモジュール性能項目動作周波数レイテンシ数値 • • • • 397[MHz] 4[cycle] 回路規模 SWメモリ量 4932[slices] 4843[Bytes] 1ブロック（64bit）をN=8で暗号化する場合最高性能で4Gbps程度のスループット MB検証システムの動作周波数は100MHｚ固定ソフトウェアのみで同じ動作を行う場合2892サイクルこのハードウェア・ソフトウェアの結果を本システムにフィードバックして設計仕様解析器を実現 10 モジュール性能評価式 StdValitem   StdMin  Eval   Wu item   StdMax  StdMin   pattern Eval：各モジュール評価総和、Wu item：ユーザ要求の係数 Std()：偏差値導出関数、Val：CDFGなどの性能値 • • • • 偏差値は価値を画一するため（Bytes,Cycles…）分数計算は偏差値の揺れ幅を揃えるためユーザ要求の係数は比率 Evalが最も大きい時にそのパターンを使用 11 実験結果と評価 MISTY1暗号の解析結果 HWループ回数 0回 8回 32回 64回 100回実行サイクル数 92330 85120 63056 24406 525 回路規模 0 13265 13270 13276 13282 メモリ量 38048 37668 25885 13728 64 MISTY1暗号の評価結果 HWループ回数 0回 8回 32回 64回 100回処理速度重視 A 8:1:1 0.10 0.06 0.29 0.66 0.90 回路規模重視 B 1:8:1 0.80 0.06 0.14 0.20 0.00 メモリ使用量重視 C 1:1:8 0.10 0.02 0.29 0.59 0.90 D 6:2:2 0.20 0.05 0.26 0.57 0.80 E 2:6:2 0.60 0.02 0.13 0.28 0.40 F 2:2:6 0.20 0.0. 0.53 0.80 重み付け（速度：回路規模：メモリ量） 0.26 12 11 Evaluation MISTY1暗号解析結果の評価と考察 1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0.0 A C B A：速度重視 B：回路規模重視 C：メモリ使用量重視 0 8 32 64 100 • 処理速度とメモリ量はハードの化による評価の向上が高い • 回路規模はあまり変化なし • [6,2,2]の比率でも大差はない 13 • MISTY1はハードウェア化で高性能になる AES暗号での実験 • 全く異なるモジュールからなる • 負荷の高いモジュールを優先的にハードウェア化 SubBytes, 40% 分類ハードウェア処理部ア MixColumns, 36% ShiftRows, 14% Add Round Key, 10% ソフトウェア処理部 SubBytes,MixColumns,ShiftRows, AddRoundKey イ MixColumns SubBytes,ShiftRows,AddRoundKey ウ SubBytes MixColumns,AddRoundKey,ShiftRows エ SbuBytes,MixColumns ShiftRows,AddRoundKey オ SubBytes,MixColumns,ShiftRows AddRoundKey カ SubBytes,MixColumns,AddRoundKey ShiftRows キ SubBytes,MixColumns,ShiftRows, AddRoundKey S W 大 H W 14 14 大 AES暗号による解析結果評価実測評価結果 1 A Evaluation 0.9 B D C E F A 速度重視（8:1:1） B 回路規模重視 (1:8:1) C メモリ使用量重視 (1:1:8) D 速度優先 (6:2:2) E 回路規模優先 (2:6:2) F メモリ使用量優先 (2:2:6) 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 アイウエオカキ解析評価結果 1 A 0.9 B D C E F Evaluation 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 15 0 アイウエオカキピアソンの積率相関係数による類似性証明 1 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0 0. 953 0. 949 0. 858 0. 835 0. 751 A B C 0. 737 D E F • • • • １に近いほど相関関係が強く、0に近いほど無関係平均値は0.85 概ね解析が正しいといえる “A”と“D”が高いことから処理速度（クロックサイクル数）の見積もり精度は高いといえる • “C”と“F”から、メモリ量解析でまだ見積もり精度に問題 16 まとめ • ハード/ソフト最適分割システム • 分割方法の探査のための実験・考察 – MISTY1暗号のハード/ソフト分割 • ツールの有効性判断 – AES暗号の実測値と解析値の類似性証明課題 • 設計仕様解析器の完成 • 解析器の精度向上 • 他のアルゴリズム実装による実験 17