Cソースコード解析による

Cソースコード解析による
ハード／ソフト最適分割システムの構築
高性能計算研究室
Ｍ２和田智行
2009/02/20
研究背景と目的
• 背景
– 高速化、低消費電力化などにコデザインは必要
– 大規模化によるシステムの複雑化
– システムにはハードとソフトのバランスが必要
• 目的
– Ｃソースコード解析による最適なハード／ソフト分
割案を提案するシステムの構築
– ソフトマクロＣＰＵによるハード／ソフトの分割実験
– ハード／ソフト最適分割システムの適用と検証
• Ｍｉｓｔｙ１暗号、ＡＥＳ暗号、ＳＨＡ-1
2
ハード／ソフト最適分割システム
Ｃ言語ソースコード
システムの特徴
関数・モジュール分割
分割パターン生成
分割パターン
性能・コスト・並列性解析
性能・コスト・並列性
分割パターン評価
最適分割パターン出力
ユーザ要求
• 目的
– 設計の早期段階で分割領
域の特定
– ハード／ソフトの最適な分
割を支援
– Cソースコード解析
• 条件・制約
– ハードウェアのリファレンス
となるソースコード
– 関数がハードウェアモ
ジュールに対応
– ポインタ・構造体・標準関数
は対象外
– 各関数の制御はmain文に
まとめる
最適な分割パターン
3
ハード／ソフト最適分割システムの構成
制御（インタフェース）
―
―
性能・コスト解析部
演算式評価データ
DFG・FSM
変数リスト
実装環境記述ファイル
クロック数
回路規模
メモリ量
動作周波数
ＳＷ負荷割合
分割パターン生成部
ソースコード
全分割パターン生成
前処理部
ソースコード
字句解析
関数・モジュール分割＆抽出
プリプロセッサ抽出
CDFG・FSM抽出
制御文・変数抽出
並列性解析部
CDFG・FSM
演算式評価データ
ループ文
実装環境記述ファイル
並列効果算出
出力部
分割パターン
モジュール並列効果
モジュール性能
ユーザ要求
最適な分割パターン出力
並列可能性出力
• 実装言語はRuby
• 独自の内部表現を使用
4
実験方法
• Misty1暗号、AES暗号、SHA-1に適用
• 各関数の解析値を算出
– SW実行サイクル数、SW負荷割合、HW実行サイクル数、回路規
模、メモリ量、最高動作周波数、並列性
• 全分割パターンの評価値を算出
最高偏差値 偏差値 

評価値   重みitem 

最高偏差値

最低偏差値

 pattern
– 実行サイクル数と回路規模のみで全パターン評価
– 速度（1：0）・回路規模（0:1）・バランス重視（0.5:0.5）
• ユーザ要求を満たす、最適な分割パターンを算
出
• ソフトマクロCPUで実測値を求め、解析値と比較
5
Misty1暗号アルゴリズム
• 64ビットブロック・128ビット秘密鍵暗号
• FL・FO・FI・KSの4つの機能ブロックモジュールに分割
• 8ループの場合を対象
FL
平文（64bit）
KLi
FL
KLi+1
32
16
16
KLi1
FL
KLi,
Loop N times
KLi2
KOi
FO
（
KLi+1,
FO
KOi+1
32
FO
）
16
9
16
S9
KOij
FI
KLn+1
FL
KLn+2
暗号文（64bit）
FL
7
16
KIij
KIi2
S7
KIi1
S9
6
Misty1暗号で各モジュールの性能解析
FI
FO
FL
KS
解析値
実測値
解析値
実測値
解析値
実測値
解析値
実測値
SW実行サイクル数[Cycles]
47
36
247
199
48
41
576
551
SW負荷割合[%]
45
46
47
52
10
5
12
17
HW実行サイクル数[Cycles]
1
1
4
3
1
1
12
8
回路規模[Slices]
256
232
784
1026
16
16
2064
2489
メモリ量[Bytes]
28
39
140
43
24
36
232
228
最高動作周波数[MHz]
88
63
20
34
108
155
35
59.6
並列性
なし
―
なし
―
なし
―
なし
―
• 全体の誤差の平均は0.1
• FI・FLのハードウェア化が効果的
• 各性能により分割パターンの評価
7
Misty1暗号での全分割パターン評価
1.000
0.900
0.800
0.700
速度
0.600
回路規模
0.500
バランス
0.400
0.300
0.200
0.100
0.000
FI
S
S
S
S
S
S
S
S
H
H
H
H
H
H
H
H
FO
S
S
S
S
H
H
H
H
S
S
S
S
H
H
H
H
FL
S
S
H
H
S
S
H
H
S
S
H
H
S
S
H
H
KS
S
H
S
H
S
H
S
H
S
H
S
H
S
H
S
H
• 全ての重視項目で、KS以外がハードウェアのパターンが優秀
8
ユーザ要求を考慮した分割案の評価
1
◎要求
– 回路規模：実行サイクル数＝
0.1：0.9
– 回路規模・・・3000slice以下
– 実行サイクル数・・・4500clock
以下
– 動作周波数・・・30MHz以上
– メモリ使用量・・・10KByte以下
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
FI
S
S
S
S
S
S
S
S
H
H
H
H
H
H
H
H
速度
FO
S
S
S
S
H
H
H
H
S
S
S
S
H
H
H
H
回路規模
FL
S
S
H
H
S
S
H
H
S
S
H
H
S
S
H
H
バランス
KS
S
H
S
H
S
H
S
H
S
H
S
H
S
H
S
H
ユーザ要求
• 要求を満たさないものは0
• FO以外をハードウェア化したものが優秀
9
ＡＥＳ暗号アルゴリズム
• 128ビットブロック秘密鍵暗号（鍵は可変）
• 5つの機能ブロックモジュールに分割
• 鍵長が128ビットの場合を対象
平文（128bit）
秘密鍵
（128 or 192 or 256bit）
AddRoundKey
KeyExpansion
SubBytes
拡大鍵
（128 or 192 or 256 bit）
ShiftRows
AddRoundKey
MixColumns
暗号文（128bit）
Loop（N times）
10
AES暗号での実験
重視項目 KE Add Shift Mix Sub
回路規模
実行サイク
[Slices]
ル数[Cycles]
解析値実測値解析値実測値
評価値
速度
H
H
H
H
H
2314
1600
1775
1397
速度
1
回路規模
S
S
S
S
S
0
0
25269
31246
0
1
0.5
バランス
S
H
H
H
S
512
1266
7285
5618
0.765
0.779
0.770
Sub KE
7% 7%
KE
21%
Add
7%
Add
1%
Sub
58%
Mix
20%
回路規模比率
Mix
41%
Shift
0%
Shift
38%
回路規模バランス
0
0.5
• AddRoundKey、
ShiftRows、MixColumns
のハードウェア化が効
果的
• 全体的に妥当な最適
パターンを選出
ＳＷ負荷割合
11
ハッシュ生成アルゴリズムＳＨＡ-1
 組込み機器向けベンチマークMiBenchより選出
 5つの機能ブロックモジュールに分割
 MessagePaddingはソフトウェアで固定
メッセージ
Loop（Block数）
Message Padding
512bit
Block生成
32bitシーケンス
を80個生成
Sequence Generate
Culculate Hash
Add Hash
ハッシュ化データ
ハッシュ値
の更新
•ハッシュ計算を行う
•GetF・GetK・Rotateの3つの
モジュールを使用
Loop 80times｛
Temp＝Rotate+f(b,c,d)+e+K+input
e=d
d=c
c= Rotate
b=a
a=Temp
}
Ｒｏｔａｔｅ
ＧｅｔＦ
ＧｅｔＫ
12
ＳＨＡ-1での実験
• 実測値と解析値によるバランス重視の評価値で比較
評価値
1
実測値
0.9
解析値
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
SG
Add
GetF
GetK
Rotate
1
S
S
S
S
S
2
S
S
S
S
H
3
S
S
S
H
S
4
S
S
S
H
H
5
S
S
H
S
S
6
S
S
H
S
H
7
S
S
H
H
S
8
S
S
H
H
H
9
S
H
S
S
S
10
S 11
S 12
S 13
S 14
S 15
S 16
S 17
H 18
H 19
H 20
H 21
H 22
H 23
H 24
H 25
H 26
H 27
H 28
H 29
H 30
H 31
H 32
H
H
S
S
H
H
S
H
S
H
S
H
H
H
H
S
S
H
H
S
H
H
H
H
S
H
H
H
H
S
S
S
S
S
S
S
H
S
S
H
S
S
S
H
H
S
H
S
S
S
H
S
H
S
H
H
S
S
H
H
H
H
S
S
S
H
S
S
H
H
S
H
S
H
S
H
H
H
H
S
S
• 2つの評価値の整合性が高い
• ハードウェア化の優先度の高いモジュールの割り出し
H
H
S
H
H
H
H
S
H
H
H
H
13
考察
• Misty1暗号、AES暗号
– 性能値の解析精度が高い
– 分割パターンの選出は妥当
– ユーザ要求を満たした最適な分割パターンの選出
• SHA-1
– 全パターンの評価値を参照することで、分割パター
ンの傾向探索
– ハードウェア化の優先度の決定
ハード／ソフト最適分割システムは有効
14
まとめ
– ハード／ソフト最適分割システムによるMisty1暗
号、AES暗号の分割パターンの妥当性検討
– ユーザ要求を考慮したハード／ソフト最適分割に
よる分割パターン検討
– SHA-1における分割パターンの傾向探索と分割パ
ターンの妥当性検討
今後の課題
– ハードウェアのコスト・性能見積もりの向上
– 様々なアプリケーションへのシステムの適用
– マルチコア実験による並列性解析の妥当性検証
15

Download Report