CMPにおけるキャッシュ・データを考慮したスレッド・スケジューリング手法の初期検討

全文

(1)Vol.2012-ARC-200 No.14 Vol.2012-OS-121 No.14 2012/5/8. 情報処理学会研究報告

(2) . におけるキャッシュ・データを考慮した. スレッド・スケジューリング手法の初期検討三輪忍. . 角崎宏一 . 佐々木広. 中村宏. 概要：多数のコアを有するでは，チップ上に分散して配置されたをラスト・レベル・キャッシュとして利用する．そのため，ラスト・レベル・キャッシュのアクセス・レイテンシは，コアとそれがア. クセスするとの物理的な位置関係によって異なる．これまで，データをキャッシュする位置を工夫することによって，キャッシュの容量効率を高めつつ平均アクセス・レイテンシの短縮を図る研究が行われてきた．しかし，そのようにデータの配置のみを考えていたのでは十分とは言えない．本稿では，データの配置だけでなくスレッドの配置も工夫することで，プロセッサの性能が向上する可能性があることを. 示す．また，データの配置を工夫する手法のつである

(3) を用いて予備評価を行った結果，ディレクトリ参照が性能上のボトルネックとなることがわかった．キーワード：. ，スレッド・スケジューリング，

(4) . 肢がある．. はじめにの微細化にともない，つのチップに搭載されるコア程度のコアからなるが主流となっている．中には十数コアをつのチップ上に搭載したものもあり，の. 方式各を全てのコアで共有し，つの巨大なラスト・レベル・キャッシュとして利用する方式．. 数は年々増加している．近年の商用プロセッサでは，. 各. . は共有キャッシュのバンクに相当する．バ. ンクはアドレスによってインタリーブされる．各コアは全ての. を利用できるため，の大きさを. コア数は，今後，微細化が進むにつれてさらに増加すると. 超えるデータを参照するスレッドが実行された場合で. 期待されている．そのため，現在，数十コア，あるいは，. もデータをすべてキャッシュすることができる．した. 百個を超えるコアを搭載したに関する研究が盛んに. がって，後述する. 行われている

(5) .

(6)

(7) ．. 方式と比べ，高いヒット率. を実現できる．しかし，近傍のバンクに比べて遠方の. 多数のコアを有するでは，ラスト・レベル・キャッ. バンクへのアクセスは時間がかかる（アーキ. シュの構成が通常とは異なる．キャッシュは，通常の . テクチャ

(8) ）ため，キャッシュの平均アクセス・レイ. のように，チップ上のどこかに集中的に配置されるのでは. テンシは大きくなってしまう．. ない．多コアのでは，コアと少量のをつの. 方式各をそれぞれのコアが専用のキャッ. つのし. ノード（タイル）とし，それらを敷きつめることによって. シュとして利用する方式．各コアは. プロセッサ全体を構成する場合が多い（図）

(9) . か利用できないため，の大きさを超えるデータ.

(10)

(11) ．. それぞれのノード間はによって接続される．このよ. を参照するスレッドは，すべてのデータをキャッシュすることはできない．したがって，方式のヒッ. うな構成をとるのは，製造プロセスを簡略化し，コア数を. ト率は方式のそれと比べて低くなる．しかし，. スケールしやすくするためである．このようにして分散配置されたをキャッシュとして利用する．. ラスト・レベル・キャッシュへのアクセスは常にノー. 各の利用方法は，大きく分けて以下のつの選択. ド内のに対するアクセスとなるため，レイテンシは方式と比べて短い．. 東京大学 .

(12)

(13)

(14). 九州大学. .

(15)

(16) 現在，九州電力株式会社所属. .

(17)

(18)

(19) .

(20). におけるデータ配置手法一般に，データはそれを参照するスレッドを実行してい. るノードの近傍にキャッシュするのがよい．各ノードは，.

(21) Vol.2012-ARC-200 No.14 Vol.2012-OS-121 No.14 2012/5/8. 情報処理学会研究報告

(22) . られる．. Node. 我々は，$ のスレッド・スケジューラを改良し，スレッ. Core L1I L1D. Core L1I L1D. Core L1I L1D. Core L1I L1D. LLC 0. LLC 1. LLC2. LLC 3. Core L1I L1D. Core L1I L1D. Core L1I L1D. Core L1I L1D. LLC4. LLC5. LLC6. LLC7. Core L1I L1D. Core L1I L1D. Core L1I L1D. Core L1I L1D. " の効果がどの程度変化するかを測定した．その結果，のキャッシュの利用効率を向上する. LLC8. LLC9. LLC10. LLC11. には，ディレクトリ参照による性能オーバヘッドを削減し. Core L1I L1D. Core L1I L1D. Core L1I L1D. Core L1I L1D. LLC12. LLC13. LLC14. LLC15. 図. タイル型. . ドの配置を最適化することによって，におけるキャッ. シュの利用効率を最大限高めることを考えている．そのための予備評価として，今回，スレッドの配置によって. なければならないことがわかったので報告する．以下まず次章では，. " を中心に，デー. タ配置の最適化を目指した既存研究について詳しく述べる．続く章では，我々が着目している，タイル型 . におけるスレッドの配置問題について説明する．章で評. 価を行い，! 章で関連研究について述べ，章でまとめとそこで実行するスレッドが参照したデータをローカルな. にキャッシュする．ローカルなの容量を超えた場合は，容量に余裕のある近傍のにキャッシュする．そうすれば，方式と同じくの総容量を有効に利用しつつ，方式に匹敵するレイテンシを実現できる．このような理想的なデータ配置を目指した研究がいくつか行われている

(23) .

(24)

(25)

(26) ．例えば，

(27) !

(28)

(29) は，他ノードのを自身のノードの "# キャッシュとして利用する．各ノードが参照したデータは，基本的には，方式と同様，ローカルなへとキャッシュする．そして，リプレースの際，一定確率で，ローカルから追い出されたデータを隣接するノードへと転送し，そのノードのにキャッシュ. 今後の課題について述べる．. キャッシュの利用効率向上のためのデータ配置手法本章では，本稿で評価の対象とした . ". についてまず説明する．次いで，その他のデータ配置手法についてまとめる．.

(30). . " は，方式において容量に余裕のある他ノードのを "# キャッシュとして使用. することにより，チップ全体のキャッシュの利用効率を高める手法である．詳しくは次章で述べるが，スレッドにはそれが使用するキャッシュ容量を増やすほどヒット率が向. する．再びそのデータが参照された場合は，メイン・メモ. 上し性能が向上するものとそうでないものとがある．その. リにアクセスしなくても，隣接ノードのを参照すれ. ため，後者のスレッドを実行するノードのを前者の. ばデータを取得できる．. スレッドの. タイル型においては，オフチップに位置するメイン・メモリへのアクセスが性能上のボトルネックとなる．. "# キャッシュとして使用すれば，全体の. ヒット率は向上する．. " の基本的な動作は以下の通りである．. また，オンチップ・メモリのアクセス・レイテンシは，コア. 各コアは，方式と同様，それがアクセスしたライン. とそれがアクセスするメモリとの物理的な位置関係によっ. をローカルな. て異なる．そのため，キャッシュのヒット率を高めつつ，. シュからラインが追い出される際，必要に応じてラインを. 平均アクセス・レイテンシを短縮することが重要である．. 他のノードへと転送し，そのノードのキャッシュに格納す. にキャッシュする．ローカル・キャッ. る．再びそのラインが参照された際は，ラインを格納した.

(31) スレッドの配置問題. リモート・キャッシュにアクセスすることでラインを取得. 上述のように，従来ののキャッシュに関する研究. する．このように，他ノードのキャッシュを "# キャッ. は，データをキャッシュする位置を工夫することで，キャッ. シュとして使用することにより，オフチップ・メモリへの. シュの容量効率を高めつつ平均アクセス・レイテンシの短. アクセスを削減する．. 縮を図っていた．しかし，そのようにデータの配置だけを. 図に . て，これらの手法の効果は変化し得るからである．スレッ. " の構成を示す． " の構成はいくつか存在する

(32) !

(33)

(34) が，本稿では分散ディレクトリ方式を採用した %&' " !

(35) を対象とする．これは，多コアのでは集中. ドの配置も含めて考えることでキャッシュをより有効に利. ディレクトリの参照は性能上のボトルネックとなりやすい. 用でき，プロセッサ全体の性能をさらに改善できると考え. ためである．. 考えていたのでは十分とは言えない．章で詳しく述べるように，どのノードでどのスレッドを実行するかによっ. .

(36)

(37)

(38) . .


(40) . Directoryy 0 Directory Memory. ii) Searching directory Directory yN Directory Memory ix) Updating directory. Spilling Buffer. Spilling Buffer. Spilling Engine. Spilling Engine. i) Sending request ii) Registration. i) Forwarding. iii) Deciding where to spill. iii) Sending request. Interconnection ix) Forwarding Core L1I L1D. ix) Forwarding. Core L1I L1D. Core L1I L1D. LLC1. LLC15. Miss LLC0. Evicted data. Node 0. Node 15. Node 1. Spilling process Remote hit process 図. .

(41)

(42) の構成と動作. %&' " では，各々のディレクトリを拡張し，(()* +', と (()* -)*) を追加する．(()* +', は，他ノードのキャッシュへ転送するラインを一時的に保持するバッファである．各ラインの転送先は. (()* -)*) が決定する．ディレクトリはアド. レスによってインタリーブされる．なお，ラインを他ノードのキャッシュへ格納する一連の処理をと呼ぶ．. (( は以下のようにして行われる．ローカル・キャッ. シュでリプレースメントが発生すると，まず，そのライン. (( 対象のラインか否か判断される．複製が他に存在しなければ，基本的には，そのラインは (( の対象となる．対象だった場合は以下のようにして (( を行う． . / まず，キャッシュから追い出されたラインを該当するが. ディレクトリへ転送する．. . / 当該ディレクトリ（図では）では，受け取ったデータを (()* +', に格納する． . / 各ディレクトリの (()* -)*) は，(()* +', の先頭からラインを取り出し，(( 先を決定する． (( 先を決めるポリシーはいくつか存在し，例えば，ある一定の確率で隣接ノードのキャッシュに (( する

(43) ，(( 先のキャッシュのヒット率が向上する場合に (( する

(44) などがある． . / (( 先が決定したら，該当するノードへラインを転送し，キャッシュに書き込む．また，そのラインのアドレスと転送先のノード. %. を用いて %"0. #0. を更新する．. (( したデータへのアクセスは，通常のコヒーレンス制御のプロセスと何ら変わりはない．すなわち，あるノード. .

(45)

(46)

(47) . （図ではノード 1）でローカルのキャッシュにミスすると，. . / 該当するディレクトリに問い合わせを行う． . / 問い合わせのあったディレクトリでは，%"0 #2 0 を参照し，当該ラインが他ノードにキャッシュされているか調べる．図では，ノード ! にキャッシュされていることがわかる．. . / ラインをキャッシュしているノード ! に対し，ラインを要求元のノード 1 へ転送するように要求する． . / リクエストを受け取ったノード ! は，ラインを要求元のノード 1 へと転送する． " では，一度 (( されたラインが再び (( されることのないよう，(( される回数に制限を設けている（234 ポリシー）．これは，再利用されないラインが (( され続けることによって，キャッシュの容量を圧迫することを防ぐためである．このために，各キャッシュ・ラインに対し，そのラインが (( によってキャッシュされたラインか否かを判別するためのビットを追加する．このビットがセットされている場合は，ラインがキャッシュから追い出された場合でも. (( しない．. 各キャッシュ上では，そのノードで実行中のスレッドが割り当てたラインと，他ノードから. (( されたラインと. の間で競合が発生する．(( の発生頻度はスレッド毎のキャッシュ・ミス頻度に依存する．そのため，あるキャッシュでは，頻繁にミスするスレッドのデータを受け取ったことによって，そのノードで実行しているスレッドが参照する予定だったラインを追い出してしまうことがある．この競合の影響を緩和するため，キャッシュ・パーティショニングを利用することが提案されている

(48) ．. .


(50) . 40. CPI. 15. CPI. 30. MPKI. 10. MPKI. 20. 5. 10. 0. 0 0. 4. 8 12 16 20 24 Cache Size (Number of Ways) 図. . 高. 28. 32. 0. 4. スレッド（）. 8 12 16 20 24 Cache Size (Number of Ways) 図.

(51) その他の手法. . 低. 28. 32. スレッド（）. シュ状のネットワークによって接続されている．以下，. のオンチップ・メモリを有効利用する方法は， " 以外にもいくつか提案されている． %2

(52)

(53) は，方式において，最近参照したラインに対するアクセスを高速化する．通常の方式は，各がアドレスでインタリーブされているた. スレッドによって異なる．利用可能な容量が増えるにつれ. め，参照するデータのアドレスによっては，要求元のノー. て性能が漸次向上するスレッドもあれば，そうではないス. にアクセスしなければならない．それに対し，%2 では，各 40 を各バンクに対応させる．例えば，図の例では，¼ を 401，½ を 40，のように対応づける．このようにすれば，最近. " (0

(54) が高いスレッド（以下，高スレッド），後者を (0 が低いスレッ. ドから遠く離れた. 参照したラインを参照元のノードのバンクに移動させることができる．ただし，この方法はヒット5ミスの判定のために複数のバンクを検索する必要がある．そのため，検索に通常よりも多くのエネルギを消費するという問題を抱えている．また，ラインを格納する可能性のあるすべてのバンクにミスしなければキャッシュ・ミスか否かは判明しないため，ミスが判明するまでの時間が遅くなるという問題もある．. 2

(55) は，各のインデクスを工夫すること. で，ラインが格納されるを，それを参照したコアから. 数ホップ以内のに限定する．この方法を. )(. )()* と呼ぶ．ラインを配する領域の大きさは，ノードごとだけでなく，アドレス空間ごとにも変更する．$ のページ割り当てを利用して，なデータが多いアドレス空間を 1 ホップの領域，すなわち，ローカルなにマッピングし，データが多いアドレス空間はリモートのにマッピングする．. におけるスレッドの配置問題前章で述べた手法はいずれも，キャッシュするデータとその位置を工夫することによって，キャッシュの容量効率. " が適用されたとする．

(56). と一般に，キャッシュ容量を増減した場合の性能向上率は. レッドもある．前者を. ド（以下，低スレッド）と呼ぶことにする．それぞれの例を図，および，図に示す．グラフは，. - 111 ベンチマークのつのプログラム（）について，キャッシュのセット数を固定した状態で 40 数を増加させた時の，，および， 6 の変化を表している．横軸は 40 数，縦軸は，または， 6 である．グラフより，はキャッシュ・サイズの増加にともなって漸次が減少するのに対し， . は 40 以上に増やしてもがほとんど変わらない．このようにスレッドによって (0 は異なる．したがって，全体を効率良く利用するためには，高 (0 スレッドを実行中のノードから低 (0 スレッドを実行中のノードへデータを (( した方がよい．

(57) スレッドの配置との効果. 図のにおいて，ノード 1 で高 (0 スレッドが，. ! で低 (0 スレッドが実行されたする．そ. ノード . の様子を表したのが図 ./ である．図において，各キャッシュは. つの領域に分割されており，分割された各領域は. 保持中のラインを表している．各ライン中の文字列は，そのラインがどのスレッドによって参照されたかを表す．各ラインは，それを参照したスレッドの. (0 が高いほど. 濃色で，(0 が低いほど淡色で表現してある．ノード. しかし，さらなる性能向上を考えた場合，データの配置だ. 1 ! で，それぞれ，スレッド 1 ! が実行されているものとする．各スレッドが表に示す 40 数を利用で. けを考えていたのでは十分とは言いがたい．. きた場合に，全体のヒット率は最も高くなるものとする．. を高めつつ平均アクセス・レイテンシの短縮を図っていた．. 例として，図. . に示した . ノードからなるタイル型. の各コアにおいて，異なる個のスレッドを実行. する場合を考える．各ノードは，図に示すように，メッ. .

(58)

(59)

(60) . (( は，高 (0 スレッドを実行中のノードから低 (0 スレッドを実行中のノードへ行った方がよい．そのため，図 !./ のような配置でス前述のように，データの. .


(62) . LLC 0 thread 0 thread 0 thread 0 thread 0. LLC 1 thread 1 Evicting thread 1 useful data thread 0 thread 0 thread 1. LLC 0 thread 0 thread 0 thread 0 thread 0. LLC 1 thread 1 thread 1 thread 1 thread 0. LLC 4 thread 4 thread 4 thread 4. LLC 5 thread 5 thread 5 thread 6 thread 6. LLC 4 thread 4 thread 4 thread 4. LLC 5 thread 5 thread 5 thread 0 thread 6. thread 0. thread 0. (a) Data migration to adjacent busy cache. Long Access Latency. (b) Data migration to remote free cache 図. . LLC 4 thread 4 thread 4 thread 4. LLC 5 thread 1 thread 1 thread 1. thread 0. thread 6. (c) Thread migration with data migration to adjacent free cache. におけるスレッドの配置問題. レッドが実行された場合，高 (0 スレッドを実行する. ノード 1 は，ラインを低 (0 スレッドを実行するノードに. Not evicting useful data & short access latency LLC 0 LLC 1 thread 5 Thread thread 0 Migration thread 5 thread 0 thread 0 thread 0 thread 0 thread 0. (( しようとする．その時の選択肢としてまず考え. られるのは，低 (0 スレッドを実行中の隣接ノードへ. ワップし，ノードでスレッド ! を，ノード ! でスレッド. を実行する．そうすれば，ノード 1 がノードにラインをつ (( したとしても，スレッド ! は 40 分の容量を利用できれば十分なため，容量不足に陥らない．. (( することである．図では，スレッドを実行しているノードは 40 あれば十分（表）なことから，ノード 1 からノードにライン (( している．このように (( 先を低 (0 スレッドを実行中の隣接. (0 のスレッドをどこで実行するかによって " の効果は異なる．2 " の効果を十分に引き出すためには，(0. ノードに限定してしまうと，十分なヒット率を達成できな. ことがわかる．. いことがある．例えば，図. !./ では，スレッド 1 は 40. を使用したい（表）がために，ノードにつのライン，ノードにつのラインを. レッドは. このように，どのような. を考慮してスレッドを実行するノードを変更した方がよい. 評価. (( している．その結果，ス. 40 分の容量を利用できた方がよいにも関わらず，ローカル・キャッシュを 40 分しか利用できない，という状況が生まれてしまう．このような容量不足を避けるために，図. !.&/ のように，. 我々は，(0 に応じてスレッドを実行するノードを変更するスレッド・スケジューラの開発を考えている．そのための予備評価として，今回，スレッドの配置によって. " の効果がどの程度変化するかを測定した．本章ではその結果を述べる．. 離れた場所に位置する容量に余裕のあるノード（図ではノード !）に. (( するという選択肢も考えられる．しかし，離れたノードに (( した場合は，近くのノードに ((.

(63). 評価環境および評価条件. 加してしまう．また，パケットがより長い距離を伝搬する. *#!

(64) に %&' 2 " を実装し，評価を行った．評価したは個のコアを持ち，それらが 7 のメッシュ状に並ん. ことで，ネットワークが輻輳する可能性が増加する．. でいる．各コアはインオーダで，ディレクトリは各ノード. !."/ のようにスレッドを配置すれば回避できる．すなわち，スレッドとスレッド ! をス. に分散されている．表にその他のパラメタをまとめる．. した場合と比べて，それにヒットした時のレイテンシが増. このような状況は，図. 表. 各スレッドに割り当てるキャッシュ容量スレッド割り当てる容量（）. ! # % & . " $ $ '. .

(65)

(66)

(67) . プロセッサ・シミュレータ. ベンチマーク・プログラムとして， -. 111 の. 中から表に示す 1 本のプログラムを選び，それらを組. み合わせて使用する．1 本のプログラムを表. に示すよ. うに高 (0 スレッド，低 (0 スレッドに分類する．. 実行の際は，高 (0 スレッド5低 (0 スレッドそれぞ. 8 8 ）. れからプログラムを選択する比率（例えば 8 . をまず決定し，次いで，その比率にもとづいてそれぞれの. .


(69) . (

(70) #

(71) '

(72) $

(73) %

(74) &

(75) /

(76) "

(77) 0

(78) 1. 表. . 評価に用いたプログラム群.

(79) . )* + ), -'

(80)

(81) ##! ##! .. #+$ .. ##! -' .

(82) .. ##! ##! ##! ##! ##!

(83) ..

(84) ##! #+# -'

(85)

(86) -' .. ..

(87)

(88) .. ##! ##!

(89) -' -' ##! -' .. .. ##!

(90) ..

(91) ##! .. -' ##! $+# -' .. -'

(92) .. .. .. . グループから実行するプログラムをランダムに選択する．. SHARED Total Throughput (normalized to SHARED). このようにして得られた，表に示す種類のプログラム群を用いて評価した．評価は以下のつのモデルについて行う．. 方式 ! 方式 " " " とキャッシュ・パーティ. PRIVATE. CC (worst). CC (best). CCwCP (worst). CCwCP (best). 1.3 1.2 1.1 1 0.9 0.8 com1. com2. 図. ショニングを組み合わせた方式. . com3. com4 com5 com6 Executed Programs. com7. com8. com9. トータル・スループット. " を用いるモデルでは，高 (0 スレッドを実行するノードから低 (0 スレッドを実行するノードへとキャッシュ・データを (( する．(( の際， (( 先のノードの選び方，および，(( する量（リプレースメント何回に対し回 (( するか）にはいくつかの選. お，9-%，および， :;- については，上述の試. 択肢がある．我々は，この問題を最小費用流問題に見立て，. による実行時間の変化がほとんど見られなかったためであ. 6()&* のアルゴリズム 1

(93) にもとづき，総メモリ・アクセス時間が最小となる (( 先と (( 量を静的に決定し. 続く 11 サイクルを実行した．. た．この方法の詳細は紙面の都合により省略する．. で示す結果は，回の試行を繰り返した結果である．な行を行わず，あるスレッドの配置パターン回についての. み評価する．これは，これらのモデルではスレッドの配置る¶½ ．いずれの試行も，最初の < サイクルをスキップし，. べるため，スレッドの配置パターンをランダムに決定して.

(94) 評価結果図 # に各モデルの性能を示す．グラフの横軸はプログ. 実行時間を測定する，という実験を複数回繰り返す．次節. ラム群，縦軸はトータル・スループットである．プログ. 表評価したの構成 2 )

(95) #/ , 3- /%4 ,# (5 #/46 % 6 # 7

(96) 8 ,' #46 #/ 6 #! 7

(97) 8

(98) , #' , , % , 4 9 #'0 2

(99) % .

(100) $:46 &!

(101)

(102)

(103)

(104) ;<3(. :;-，（全回の試行におけるワースト・ケース），（同ベスト・ケース），4 （ワースト・ケース），4 （ベスト・ケース）である．なお，各モデルの結果は 9-% のそれで正規化してある．グラフより，まず，タイル型においてはラスト・. スレッドの配置が . 表. . " に与える影響を調. レベル・キャッシュのアクセス・レイテンシが性能を左右する非常に重要な要素であることがわかる．各モデルの平均メモリ・アクセス・レイテンシを図 $ に示す．ただし，グラフの結果は.

(105)

(106)

(107) . キャッシュにヒットするアクセスを除. いたものとなっている．グラフより，9-% の平均ア. クセス・レイテンシは他の ! つのそれと比べて極端に大き . 評価に用いたベンチマーク. .

(108) . *. .. -'

(109) ,

(110) . ラム群ごとのつの棒グラフは，左から順に，9-%，. 簡単のため，本実験では各ルータにメモリ・コントローラが付随していると仮定した．実際には，メモリ・コントローラの数は限られているため，メモリ・アクセスを行うスレッドが実行されているノードの位置とメモリ・コントローラの位置とよって，方式や方式でも性能が変化すると予想される．この影響については今後評価する．. . . .


(112) . PRIVATE. CC (best). CCwCP (worst). CCwCP (best). 6. packet_injection. requestor_to_directory. directory_to_owner. owner_to_requestor. 150. 5 4 3 2 1. 100 50. 0 com1. com2. 図. PRIVATE Last Level Cache Miss Ratio. CC (worst). Latency. Average Memory Access Latency. SHARED 7. . com3. com4 com5 com6 Executed Programs. com7. com8. com9. com1. 図. 平均メモリ・アクセス・レイテンシ. CC (worst). CC (best). 0. CCwCP (worst). CCwCP (best). 0.9% 0.8% 0.7% 0.6% 0.5% 0.4% 0.3% 0.2% 0.1% 0.0%. com2. com3. com4. com5. com6. com7. com8. com9. リモート・キャッシュの平均アクセス・レイテンシの内訳. のトータルのミス率は改善する．改善率は実行するプログラムの組み合わせによって異なるが，最も効果が大き. "#! では，.&/ の場合で 11=，4 .4/ の場合で = の改善が見られた．ただし，ミス率の値そ. い. のものはあまり大きいとは言えず，その結果，ミス率の改善がトータル・スループットの改善に繋がっていない． com1. 図. . com2. com3. com4. com5. com6. com7. com8. com9. ラスト・レベル・キャッシュ全体のミス率. 4 におけるリモート・キャッシュの平均アクセス・レイテンシの内訳を図 & に示す．横軸はプログラム群，縦. 軸はレイテンシである．プログラム群ごとの本の棒グラ. い．その結果，トータル・スループットでは，最も小さい. フは，左がワースト・ケース，右がベスト・ケースである．. 場合（.4/ の. 棒グラフは色に塗り分けられており，それぞれの意味は. "#!）でも 1=，最も大きい場合（.&/ の "#）では = の性能差を示す．一方，残念ながら今回の実験では， " を用いたモデルと :;- との間に大きな性能差は見られなかった．この原因はいくつか考えられるが，つには. 以下の通りである．. ' () ( 命令が発行されてからパケットがネットワークに送出されるまでのレイテンシ. *+ データを要求したノードから. 後述するディレクトリ参照のオーバヘッドが挙げられる．. そのデータを管理するディレクトリにパケットが到達. このオーバヘッドが大きいために，リモート・キャッシュ. するまでのレイテンシ. にヒットした場合でもあまりレイテンシを短縮できず，先. "( ディレクトリから要求データを保. 行研究のような性能改善が達成できなかったと考えられ. 持するノードにパケットが到達するまでのレイテンシ. る．また，今回の試行は実行サイクル数が 11 サイクル. "( *+ 要求データを保持するノードから. と短かったため，+ のプライベート・キャッシュで容量は十分足りてしまい，ラスト・レベル・キャッシュ・ミス. 要求元へデータを転送するレイテンシグラフより，スレッドの配置を変えることによってリ. があまり発生しなかったことも原因のつである．. モート・キャッシュの平均アクセス・レイテンシは短縮さ. ，および，4 においてスレッドの配置を変更. れることがわかる．その差は，最も大きい "# で ! サ. した場合も，トータル・スループットではほとんど差が見. イクルであった．このように，スレッドの配置を変えるこ. られなかった．ただし，後述するように，データをリモー. とにより，. ト・キャッシュからそれを要求したノードへ転送する時間. シュの平均アクセス・レイテンシは短縮できる．. . " におけるリモート・キャッ. は改善されている．リモート・キャッシュ・ヒット時に必. 短縮はされたものの，依然として平均アクセス・レイテ. 要とされるその他の処理に要する時間が大きいため，この. ンシは大きい．ローカル・キャッシュのヒット・レイテン. 改善がトータル・スループットの改善に繋がっていない．. シは 1 サイクル（表）であるのに対し，リモート・キャッ. 図 %は. キャッシュにミスしたアクセスがメイン・メ. . シュの平均アクセス・レイテンシは ! . サイク. モリ・アクセスを行った割合，すなわち，ラスト・レベル・. ルと非常に大きい．これはメイン・メモリ・アクセスの平. キャッシュ全体のミス率を表したグラフである．グラフの. 均レイテンシの半分ほどの大きさである．このように，リ. 横軸はプログラム群，縦軸はメイン・メモリ・アクセスの. モート・キャッシュの平均アクセス・レイテンシが大きい. 割合を表す．*#! の仕様の問題から 9-% のメイン・. ため，や 4 のトータル・スループットの改善幅. メモリ・アクセス数を取得できなかったため，グラフには. が小さいものと思われる．. 9-% 以外のつのモデルの結果のみ示してある．グラフより， " を用いることによって. .

(113)

(114)

(115) . 平均アクセス・レイテンシの内訳を見てみると，ディレクトリ参照のオーバヘッドが非常に大きいことがわかる． .


(117) . 要求元のノードからディレクトリ，および，ディレクトリ. よび，(( されていた場合はその. (( 先をチェックする． (( されていれば，このディレクトリから (( 先のノー. 4) のノードへと要求を転送するのに要する時間は，平均で ! サイクルにも達する．率にして，リモート・キャッシュ・アクセス・レイテンシの 1= がディレクトリ参照のために費されている． " そのものの性能，および，スケジューラによってス. イベートであるため，ディレクトリもプライベートでよい．. レッドの配置を変えた場合の性能を向上させるためには，. ディレクトリ参照のオーバヘッドの問題を解決した上. から. このオーバヘッドを削減することが重要である．. ドへ，データ転送要求を直接送るようにする．このようにすれば，リモートのディレクトリを参照しなくても， (( したデータを取得できる．(( されるデータはすべてプラ. で，スレッドの配置が . " に与える影響を. 改めて評価したいと考えている．スレッドの配置を変える. 関連研究. ことの効果を確認した上で，スレッド・スケジューラの開. "' は，方式のキャッシュの容量を効果的に. 発を行う予定である．謝辞本研究の一部は半導体理工学センター（;）. 利用するため，スレッドをマイグレーションする手法を提案している

(118) ．上でシングル・スレッドを実行し. ているノードがつしかない状況では，他ノードのキャッ. 共同研究経費（課題名「型メニーコアのアーキテクチャレベル設計最適化」）による．. シュは何ら機能していない．そこで，"' の方法では，プログラムのワーキング・セットを等分し，プログラ. 参考文献. ムの実行状態があるワーキング・セットから別のワーキン. . グ・セットに移った時にスレッドをマイグレーションすることで，シングル・スレッド実行時においても他ノードの. . "' の方法. (. 定しており，我々が想定している複数のシングル・スレッ. . キャッシュを有効利用する．このように. はシングル・スレッドがつだけ実行されている状況を想ドが実行される場合とは状況が異なる．. 方式におけるスレッド・マイグレーション手法もある．# らの方法では，リモート・キャッシュ・アクセスを減らすため，リモート・キャッシュ・アクセスが発生. ! '. した際に，そのデータを要求したスレッドとそのデータをキャッシュしているノードで実行中のスレッドとをスワップする !

(119) ．ただし，スレッドのスワップはハードウェア・レベルで行うことを想定しており，我々が考える，$ レ. ベルでスレッドとノードのマッピングを変更するアプロー. $ . /. チとは異なる．. まとめと今後の課題本稿では， " を適用したタイル型 . # . を対象に，スレッドの配置がプロセッサ性能に与える影響について調査した．スレッドの配置によって利用可能な近傍のキャッシュの量，および，リモート・キャッシュのアクセス・レイテンシが変わるため，スレッド配置を変えることによって . " を用いるプロセッサの性. (. 能は向上すると考えられた．ところが実際には性能はほとんど変わらず，その原因はディレクトリ参照のオーバヘッ. . ドにあることがわかった．ディレクトリ参照のオーバヘッドを削減する方法として，例えば，(( したデータ用のプライベートなディレク. !. トリをノード内に設けることが考えられる．各ノードは，. '. ローカル・キャッシュにミスした場合はまずこのディレクトリを参照し，要求したデータが (( されていないか，お. .

(120)

(121)

(122) .

(123)

(124)

(125)

(126)

(127) ! "##$%

(128)

(129)

(130) & ' $' "##'% ) *+ ,

(131) ) . &

(132) -

(133) ) &

(134) $ (. "##/% 0 ) *

(135)

(136) *+ &

(137) 12

(138) )

(139) )

(140) 1

(141) ) . /! "##/% 0. 3

(142) 4

(143) 1

(144) )

(145) ( ( "##.% 05 )

(146) .& 6&( & & 5

(147) 478, ! 9, #. #/ "##% 0

(148) *+ 1

(149)

(150) : ; 1 ( # "##!% 6

(151) 8 8 5

(152) - < &

(153) 5 =

(154) )

(155) *&+ &

(156)

(157) > &4 - 4

(158) ) 9& "##% = 1

(159) 3)

(160) 6& ) "##'%

(161) =

(162)

(163)

(164) ? ;

(165) &)

(166)

(167) "@3,%

(168)

(169)

(170) 7 (( * / // "##!% ) 3;

(171)

(172)

(173) - , &

(174) & 5

(175) 3;

(176)

(177) .' /! "#% A = )

(178) , & 1

(179) 0 & ! ! "##/% A =

(180) +

(181)

(182) -&B )

(183)

(184) C5&9 ) 0 &

(185) &

(186)

(187)

(188) , ) ( ( "##'% , = ,

(189) ) < )

(190) > 4

(191) 1

(192) ) , ) "#% <

(193)

(194) DD555

(195) D )

(196) D D<6C3&@; 8 -. .

(197)