計算機アーキテクチャ特論 2016 年 10 17 枝廣 前半 ( 並列アーキテクチャの基本 枝廣 ) 10/3, 10/17, 10/24, 10/31, 11/7, 11/14( 程は予定 ) 内容 ( 変更の可能性あり ) 序論 ( マルチコア= 並列アーキテクチャ概論 ) キャッシュ コヒーレンシ メモリ コンシステンシ 並列アーキテクチャモデル OSモデル スケーラビリティに関する法則 並列プログラミングモデル 語 資料置場 : http://www.pdsl.jp/class/ 後半 ( 先端トピックス 本 ) 11/21 内容 ( 変更の可能性あり ) 組込みアーキテクチャ 再構成可能アーキテクチャ Page 1
メモリ アーキテクチャ CPU CPU CPU CPU メモリ メモリ メモリ 集中メモリ方式 分散メモリ方式 CPU SoC メモリ階層 キャッシュ CPU 内蔵メモリ SoC 内蔵メモリ ボード上メモリ 別ボード上メモリ ストレージシステム 高速小容量 ボード 低速大容量
次 キャッシュ コヒーレンシ ( キャッシュの 貫性 ) メモリ コンシステンシ ( メモリの整合性 ) Page 3
キャッシュの 貫性 (coherency) シングルプロセッサ SW1 CPU1 SW2 3 4 キャッシュ メモリバス AMP 型 ( ハードウェアサポートなし ) CPU1 3 4 キャッシュ CPU2 3? メモリバス SMP 型 ( キャッシュの Snoop( 盗み見 ) 機構 ) SW1 SW2 SW1 SW2 CPU1 3 4 キャッシュ CPU2 4 3 共有メモリ 3 共有メモリ 3 AMP 型の場合 SW2でメモ SMP 型では隣のCPUの シングルプロセッサの場 リ上の同じデータを使いたい キャッシュの内容を盗み見 合 SW1もSW2も同じ 場合 SW1はキャッシュの内 る (Snoop) ハードウェア機 キャッシュから読むので 容を一度共有メモリに戻す必 構を持つ ソフトでは気に オーバーヘッドなく正しい 要がある せずにSW1とSW2のデー 値が読める SW1からSW2への 通信 を タ共有ができる プログラムに明示的に書く ( オーバーヘッドが小さい ) Page 4
キャッシュの役割 ( 復習 ) キャッシュは高速だが容量が小さい ( 入替がある ) Page 5
Page 6 キャッシュの構造 ( 復習 )
Page 7 ダイレクトマップ 式 ( 復習 )
ライトスルーとライトバック ライトスルー 新しいデータを常にメモリに書き戻す 書き込みデータをキャッシュに残す 式と残さない 式がある いずれにしてもメモリとキャッシュはいつも同じ値 書き込みの時に時間がかかる 後述のストアバッファ ( ライトバッファ ) を使うことによって改善できるが それでも多くの書き込みが発 すると CP U が まる ライトバック 新しいデータをキャッシュに書き メモリにはその時には書き戻さない 3つの状態 インバリッド : 初期値 無効な値 クリーン : メモリと同じ値を保持 ダーティ : メモリと異なる新しい値を保持 Page 8
ライトバックキャッシュの状態遷移 ライトのキャッシュミス Page 9
例 SW1 SW2 CPU1 3 4 キャッシュ 初期状態 インバリッド値 3を読む クリーン 3 値 4に書き換える ダーティ Page 10
マルチコアのキャッシュ ( スヌープ 式 ) Configurable number of hardware interrupt lines Interrupt Distributor Private lines Per CPU Peripher als Timer CPU Wdog interface IR Q Timer CPU Wdog interface Timer CPU Wdog interface Timer CPU Wdog interface Configurabl e SMP (1 and 4 PEs) CPU/VFP L1 Cache CPU/VFP L1 Cache CPU/VFP L1 Cache CPU/VFP L1 Cache ARM11 MPCore I & D Snoop Control Unit (SCU) 64bit Primary AXI R/W 64bit bus bus Optional 2 nd AXI R/W 64bit bus Coherence Control Bus Page 11
ライトアップデートとライトインバリデート ライトアップデート 書き込みがあった場合 同じデータをもつすべてのコアのキャッシュの該当データを書き換える Page 12 ライトインバリデート 書き込みがあった場合 同じデータをもつすべてのコアのキャッシュの該当データを無効化 ( インバリデート ) する データ書き換えよりも無効化の が簡単なので 組込みプロセッサでは主流
スヌープキャッシュの状態遷移 いろいろな 式がある MESI MOESI など M(Exclusive Modified: モディファイド ) データが書き変わっている状態 ( 主記憶と 致せず 分だけがデータを持っている ) O(Owned: オウンド ) 主記憶と 致していないが 他のコアも同じデータを持っている E(Exclusive Clean: イクスクルーシブ ) 主記憶と 致し 分だけが持っている S(Shared Clean: シェアード ) 主記憶と 致し 他のコアも同じデータを持っている I(Invalid: インバリッド ) 無効状態 Page 13
Page 14 例 (MESI)
Page 15
Page 16
Page 17 キャッシュ間コピーができるアーキテクチャもある
Page 18 キャッシュ間コピーができるアーキテクチャもある
ミス I Invalid ミス Page 19
Page 20
Page 21
ディレクトリ型 スヌープ型は集中メモリ型に多く使われるが メモリが分散している場合には実装が難しい その場合にはディレクトリ型が使われる 今後 つのLSIに多くのプロセッサが搭載される時代に有 になると思われる Page 22
Page 23
Page 24 I
Page 25 フォールスシェアリング問題
キャッシュ スラッシング問題 同じキャッシュラインになってしまった セットアソシアティブ キャッシュなら回避 それでもダメなら配列参照がずれるようにする Page 26
メモリ整合性 AMP 型 ( ハードウェアサポートなし ) SW1 CPU1 SW2 CPU2 キャッシュ 同時に書き込みがあったときの順番は? キャッシュなどの影響は? Page 27
メモリ整合性 ( メモリコンシステンシ ) プロセッサP1とP2でそれぞれのプログラムが動く 変数 A Bは共有メモリ上にあるとする 両 のIF が同時に真になることはないはず ある種のスイッチ / 排他制御になっているつもり 例えば P1 で IF が真になったとすると P2 は L2 の前を実 しているはずだから P2 の IF の評価のときには既に A=1 になっているはず しかしながら 実際にはうまく動かない場合が多い なんらかの順序関係の記述が必要 Page 28
順序関係 順序関係の保証をハードでやるのか ソフトでやるのか ハードですべて保証しようと思えばできないことはないが オーバーヘッドが きい ( プログラムのごく 部の話で全体が遅くなっていいのか ) 部ソフトで保証することにしてハードを簡単化 緩和する順序関係の候補 Read Write Write Read Write Write (Read Read) Page 29
順序関係 スレッド 1 スレッド 1 Load M[x] スレッド 1 Store M[x] Load M[x] Store M[x] W R スレッド 2 Store M[x] Load M[x] 同期 スレッド 2 スレッド 2 スレッド 1 スレッド 1 Store M[x] Store M[x] Store M[x] Store M[x] W W スレッド 2 スレッド 2 スレッド 1 スレッド 1 Store M[x] Load M[x] Store M[x] Load M[x] R W スレッド 2 スレッド 2 Page 30
メモリ整合性モデル W R W R, W W ソフトウェアでの対応 : 同期をとって ( 例えば ) ライトバッファをはきだす命令を出す sync() や flush() など Page 31
ライトバッファ ライトマージ ノンブロッキングキャッシュ Page 32 ライトバッファ 書き込み終了を待つことなく バッファにためる ライトバッファがあると リードがライトを追い越すことがある ライトマージ 近く ( 同時にメモリに書きこめる ) の書き込み命令をまとめる ライトマージすると ライトがライトを追い越すことがある ノンブロッキングキャッシュ 前データ到着前にCPUはキャッシュアクセスが可能 あらゆるメモリアクセス処理の追い越しがあり得る