SWoPPの方針

メモリ・アーキテクチャ・
ベンチマーキング手法の提案
○小野貴継†
井上弘士‡
村上和彰‡
九州大学大学院システム情報科学府†
九州大学大学院システム情報科学研究院‡
発表手順



現状のシステム開発が抱える問題点
従来のメモリ・アーキテクチャ評価方法と
その課題
メモリ・アーキテクチャ・ベンチマーキング
手法の提案




メモリ・アクセスの特徴抽出
ベンチマーク・トレースの生成
シミュレーション時間と精度に関する評価
まとめと今後の課題
2
現状のシステム開発が抱える問題点
アプリケーション・プログラム
アプリケーション・プログラムに適した
システム構成を選択
・・・
シミュレーションに基づく評価
・・・
アプリケーション・プログラムや
設計選択肢が増加
シミュレーションに
膨大な時間が必要
システム開発期間が長期化
設計選択肢
MPEG2デコード（10秒間の動画像）
シミュレーション時間
⇒14,250秒@Intel Xeon 3.4GHz
キャッシュサイズ
16KB
32KB
64KB
128KB
連想度
1
2
4
ラインサイズ
32B
64B
14,250（秒）×24（通り）= 95（時間）3
従来のメモリアーキテクチャ
シミュレーション方法とその課題
アプリケーション・
プログラム
メモリ・アクセス・トレース
クロック・メモリ・アクセス・
サイクル
アドレス
XXXXXXXX
1
XXXXXXXX
2
XXXXXXXX
3
XXXXXXXX
4
・
・
・
・
N
XXXXXXXX
プロセッサ
読み出し
書き込み
メモリ
メモリ・アーキテクチャ
評価シミュレータ
メモリ・アクセス
time ∝ Tsize × Nprogram × Ndesign
time
Tsize
Nprogram
Ndesign
：
：
：
：
総シミュレーション時間
メモリ・アクセス・トレースサイズ
アプリケーション・プログラムの数
設計選択肢の数
4
シミュレーション時間を短縮するには？
アプリケーション・
プログラム
プロセッサ
読み出し
書き込み
メモリ
メモリ・アクセス・トレース
クロック・メモリ・アクセス・
サイクル
アドレス
XXXXXXXX
1
XXXXXXXX
2
XXXXXXXX
3
XXXXXXXX
4
・
・
・
・
N
XXXXXXXX
＜シミュレーション時間の短縮＞
シミュレータの高速化
メモリ・アクセス・トレースの削減
メモリ・アーキテクチャ
評価シミュレータ
ベンチマーク・
トレース
しかし・・・
シミュレーション精度が低下
メモリ・アーキテクチャ・
精度を維持しつつトレースサイズを削減ベンチマーキング手法
5
メモリ・アーキテクチャ・
ベンチマーキング手法の概要
メモリ・アクセス・アドレス
サブ・トレース
サブ・トレースに
同じ特徴をもつサブ・トレース
分割
⇒シミュレーション結果も同じ
時間（クロック・サイクル）
⇒それら全てをシミュレーションする必要はない
特徴抽出
クラスタリング
ベンチマーク・トレース
選出
6
メモリ・アクセスの特徴抽出
サブ・トレースの分割
サブ・トレース
アドレス
アドレス
インターバル
1
0
1
1
2
4
3
2
1
1
0
1
0
1
1
0
0
0
0
0
3
2
0
3
時間
時間インターバル

ブロック


メモリ・アクセス・トレースを一定間隔
で分割（サブ・トレース）
時間軸及びアドレス軸方向に等間
隔で区切る
ブロック数に対応する配列を用意し，
ブロック内のメモリ・アクセスの数を
7
入力
メモリ・アクセスの特徴抽出
平均値，標準偏差値，アドレス間距離の追加

特徴抽出精度の向上



平均値
標準偏差値
アドレス間距離
ブロック
平均値
標準偏差値
アドレス間距離
1
0
1
1
2
4
3
2
1
1
0
1
0
1
1
0
0
0
0
0
3
2
0
3
4.5
4.8
6.2
4.5
1.1
2.3
2.3
1.1
25
55.5
55.5 33.5
8
平均値と標準偏差値（1/2）
時間インターバル
アドレス
0
4
各ブロックにおける
メモリ・アクセス数は同じ
0
アドレス
インターバル
0
0
4
アドレス
時間
0
4
時間的バラツキが
反映されていない
0
0
0
平均値，標準偏差値を追加
4
時間
9
平均値と標準偏差値（2/2）
時間インターバル

アドレス
平均値
x

x
i
N

0
x0 x1 x2 x3 ・・・ xN
標準偏差値
時間

2


x

x
 i
N
10
アドレス間距離（1/2）
1100
1100
1000
1000
900
900
メモリアクセス
800
700
アドレス
700
アドレス
メモリアクセス
800
600
500
600
500
400
400
300
300
200
200
100
100
0
0
0
ブロック
10
20
30
40
50
時間
1000-1100
900-1000
800-900
700-800
600-700
500-600
400-500
300-400
200-300
100-200
0-100
平均値
標準偏差値
60
70
80
26
7
0
0
0
0
34
0
0
0
33
50.5
28.9
90
100
0
ブロック
10
20
30
40
50
時間
1000-1100
900-1000
800-900
700-800
600-700
500-600
400-500
300-400
200-300
100-200
0-100
平均値
標準偏差値
60
70
80
26
7
0
0
0
0
34
0
0
0
33
50.5
28.9
90
100
11
アドレス間距離（2/2）
時間インターバル

アドレス
アドレス間距離
y
y5 y
4
i
y3
y2
y1
アドレス間距離
y0
1,196
0
時間
1100
1100
1000
1000
900
900
メモリアクセス
800
メモリアクセス
800
700
アドレス
700
アドレス
アドレス間距離
59,918
600
500
600
500
400
400
300
300
200
200
100
100
0
0
0
10
20
30
40
50
時間
60
70
80
90
100
0
10
20
30
40
50
時間
60
70
80
90
100
12
メモリ・アクセスの特徴抽出
特徴ベクトルの生成
1
0
1
1
2
4
3
2
1
1
0
1
0
1
1
0
0
0
0
0
3
2
0
3
4.5
4.8
6.2
4.5
1.1
2.3
2.3
1.1
25
55.5
③
①
55.5 33.5
①
②
作業用テーブル
①
1
2
1
0
0
3
4.5
1.1
55.5
②
0
4
1
1
0
2
4.8
2.3
33.5
③
1
3
0
1
0
1
6.2
2.3
25
2次元配列を1次元配列に置き換え
 列とテーブルを比較し，一
致すればテーブルの番号に
置き換える
 どれにも一致しなければ
テーブルに追加
特徴ベクトル
13
代表サブ・トレースの選出
クラスタA
クラスタB
クラスタC
クラスタリング
選出
クラスタAの代表


クラスタBの代表クラスタCの代表
サブ・トレースをクラスタリング
各クラスタに属するメモリ・アク
セス・パタンに基づいて代表サ
ブ・トレースを選出
14
シミュレーション時間と精度に
関する評価

測定項目


比較対象



ベンチマーク・トレースによるシミュレーション
フル・トレースによるシミュレーション
評価指標



キャッシュヒット率
メモリ・アクセス・トレース削減率
キャッシュヒット率予測誤差
評価環境

アプリケーション・プログラム

mpeg2decode*


入力データ：missa,mei16v2
missa
mei16v2
クラスタリング（Ｋ-平均法）

Cluster3.0**
*http://www.mpeg.org/MPEG/MSSG/
**http://bonsai.ims.u-tokyo.ac.jp/~mdehoon/software/cluster/
15
パラメータ
サブ・トレース

アドレスインターバル


時間インターバル


アドレスインターバル
= 1,000
1,000クロックサイクル
・・・・
サブ・トレース


1,000
アドレス
時間インターバル×10
K-平均法

時間
時間インターバル = 1,000クロックサイクル
K = 500，1000，2000
メモリ・アクセス・サブトレース
= 時間インターバル×10
16
評価における代表サブ・トレースの
選出と重み付け
クラスタA

クラスタC
代表サブ・トレースの選出


クラスタB
クラスタに属するサブ・ト
レースのヒット率の平均に
最も近いヒット率のサブ・ト
レース
重み付け

代表を用いたシミュレーショ
ン結果にクラスタに属する
サブ・トレースの数の割合
をかける
ヒット率を基に選出
クラスタAの代表
クラスタBの代表クラスタCの代表
代表Bの
代表Cの
代表Aの
×2/10 ヒット率 ×4/10 ヒット率 ×4/10
17
ヒット率
キャッシュヒット率のメモリ・アクセス・トレース
サイズ削減率
予測誤差
評価結果－命令キャッシュー
100%
96%
80%
K = 500
60%
K = 1,000
40%
K = 2,000
K：クラスタ数
20%
0%
m ei16v2
8%
入力データ
m issa
トレースサイズを96%削減
精度の低下はわずか2%
6%
4%
2%
2%
0%
m ei16v2
入力データ
m issa
18
キャッシュヒット率のメモリ・アクセス・トレース
予測誤差
サイズ削減率
評価結果 ―データキャッシュ―
100%
80%
K = 500
60%
K = 1,000
40%
K = 2,000
K：クラスタ数
20%
0%
mei16v2
入力データ
missa
10%
8%
6%
4%
2%
0%
mei16v2
入力データ
missa
19
予測誤差の内訳
データキャッシュ mei16v2
キャッシュヒット率予測誤差の
絶対値
本来のヒット率より高く予測
本来のヒット率より低く予測
14%
12%
10%
8%
6%
4%
2%
0%
K=500

K=2,000
本来のヒット率より高く予測


K=1,000
クラスタ数
代表サブ・トレースのヒット率＞クラスタの平均ヒット率
本来のヒット率より低く予測

代表サブ・トレースのヒット率＜クラスタの平均ヒット率
20
まとめと今後の課題

まとめ

シミュレーション時間短縮を目的としたメモリ・
アーキテクチャ・ベンチマーキング手法


ベンチマーク・トレースの生成
キャッシュ性能予測を前提とした適用評価



従来の評価法と比較して平均81.6%の時間短縮
キャッシュヒット率予測誤差は平均5.8%
今後の課題


異なるアプリケーション・プログラムでの評価
関連研究との比較
21

Download Report