■ソフトウェアによる最適化
・ループアンローリング
ループを部分的に展開
条件分岐のオーバーヘッドを削減
・ソフトウェア・パイプラインニング
異なるイテレーションに属する命令をループ内に混在
・トレース・スケジューリング
■ソフトウェア・パイプラインニング
重複する領域:ソフトウェアパイプライン化する区間
複数のイテレーションの枠に含まれる命令を、ひとつの命令にする
■動的スケジューリングの基本方式
・集中制御方式
・分散制御方式
・スーパースカラ方式
■スーパースカラ方式
分岐命令で、基本ブロックを区切る。
基本ブロック単位で同時実行
基本ブロック内依存関係はハードウェアで吸収
ILPの直接利用
複数の独立した命令を、1クロックに発行・完了
cf. Core i7はスーパースカラ
■スーパースカラ方式の前提
・マルチポート・レジスタファイル or リザベーションステーション
- 1クロックに複数命令が結果を生成
- 1クロックに複数命令がレジスタファイルを読み出し
- 4 wayでは、整数10ポート 程度
・分岐予測機構
- way数が増加すると、基本ブロックを同時実行
・十分なレジスタ数
- 命令上のレジスタアドレスが狭い場合にはレジスタ・リネーミング
・メモリ依存関係の解析機構
・大きい命令ウィンドウ
■利用可能なILP
並列度の限界を考えて見ると、
かなり高い。低い場合でも17.9
これから、並列度を上げていくことが重要
-----
これから、キャッシュメモリの話
■メモリの階層化
・アクセス・ギャップ
CPUの命令実効速度とメモリのアクセス時間のギャップの増大
チップ内 1GHz
チップ外 133MHz
DDR3は8個並列でアクセスできる
DDR3-nnnn (PC-xxxx)
レイテンシ 7-7-7-24
DRAMは2回アドレスを与える
tRAS 間は使いつづける
tRCD 行方向, tCL
tRP 終わったら行う
tRCD : 7 , tCL : 7
clk: 800MHz
9-9-9-24ならば
アクセス時間 22.5ns, サイクル時間41ns
■アクセスギャップの克服
・チップ内メモリだけを使用する
・超高速メモリを外部メモリとする
:自明、高価、困難
・メモリアクセスの局所性の利用
- 高速小規模メモリと低速大規模メモリ
- 頻繁にアクセスするデータを高速小規模メモリに置く
:これが現在使われている
・メモリアクセスのパイプライン化、並列化
■メモリアクセスの局所性
・あるアドレスを中心とした確率分布ではない
正規分布にはならない
・メモリアクセスの基本パターン
- 命令アクセス
ループ構造、再帰構造
入れ子構造
例外的処理
- データアクセス
ベクトル、マトリクス
リスト構造
スタック、ローカル変数
・データ
・ループ
ベクトルな処理
・ローカルな処理
今どのパターンを実行しているかが分かる
■時間的局所性と空間的局所性
・時間的局所性(Temporal Locality)
- 一度アクセスしたアドレスに、近い将来アクセスすること
- ループ内のスカラ変数、大域変数など
- ループ構造、再帰構造の命令アクセス
・空間的局所性(Special Locality)
- ある場所にアクセスすると、近い将来その近傍にアクセスすること
- ベクトル、マトリクスのアドレス
- 逐次実行中の命令アドレス
- 入れ子構造のローカルデータ
・一般のプログラムではこの両者が金剛して出現
・全アドレス空間中に、局所性を持つ場所がn個出現
■局所性の利用法式
・高速、小規模メモリ中に存在することの検索・アクセス
・局所性を持つデータの高速・小規模メモリへの移動・コピー
・基本方式
ソフトウェアによるLarge, Smallメモリの利用
- CDC6600
- メモリ間データ移動を実現する命令オーバーヘッド
■キャッシュメモリ
・ハードウェアによるLarge, Smallメモリの利用
・基本方式
メモリ空間を固定サイズのブロックに分割
ブロック単位で、小規模メモリにコピー作成
読み出しは小規模メモリから
■基本方式
ダイレクトマップ方式
フルアソシアティブ
セットアソシアティブ
n個ダイレクトマップをならべる
(n-way set associative)
n: way数
キャッシュメモリ中でのブロックの検索
・ダイレクトマップ方式、セットアソシアティブ方式
インデクスでキャッシュメモリのティレクとりを呼び出す
・フルアソシアティブ
でぃレクとりの全要素を同時に検索
キャッシュミス時に、どのブロックを置き換えるか
・キャッシュミス、該当ブロックがキャッシュメモリ上にない
・ダイレクトマップ方式
置き換えるブロックは一意的に決定
・セットアソシアティブ方式
n個の候補から選択
random or lru
・フルアソシアティブ方式
■LRU方式の実現
4つの順序関係を、6つのバイナリで判断する
:4wayがよく使われる。
32wayだと、LRU tableのサイズがおおきくなりすぎる
・書き込み時の動作
- メインメモリに書き込みを反映させるか?
-- Write Through キャッシュメモリの書き込みは、同時にメインメモリへ
-- Write Back 書き込みはキャッシュメモリだけに反映
- キャッシュ上にないブロックへの書き込み
-- Write allocate 該当ブロックをキャッシュメモリにコピーしてっ脚shす仁鶴
-- No Write Allocate メインメモリ抱けに書き込み、キャッシュは不変
通常の組み合わせ
Write Through, No Write Allocate
Write Back, Write Allocate
これらはメモリアクセスのパタンで優劣
■キャッシュメモリの性能
ミス率:キャッシュメモリ上にアクセスするブロックがない
平均アクセス時間 =
(1 - ミス率) キャッシュアクセス時間
+ ミス率 * メインメモリアクセス時間
+ ミス率 * 転送時間
ミス率を小さくする
メインメモリアクセス時間
転送時間
を小さくする
- 初期ミス クリアなキャッシュにデータを埋めていく
- 容量ミス ワーキングセットがデータに入らない
- 競合ミス 同じ部分をアクセスしようとして、スラッシングが起きる
-----
来週はキャッシュメモリの高速化