Cache Organization for Memory Speculation メモリ投機を支援するキャッシュの構成法 東京大学工学部電子工学科 坂井研究室 ２０４２２　豊島　隆志 坂井研究室の豊島です。 今日は「～」と題して発表させて頂きます。 Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Outline Introduction Background ~Speculative Multi-threading~ Our Baseline Model – NEKO – Cache Coherency Protocols Overview Cache Directories Events Conditions State Diagrams Evaluation Environment Results Conclusions Future Works まず、イントロダクションです。 Cache Organization for Memory Speculation

Background ~Speculative Multi-threading~ A single threaded application Parallel execution !! Objectives Proposal of Cache Coherency Protocols Support Memory Speculation on Speculative Multi-threading Comparison between these protocols Invalidate-based vs. Update-based, etc… Dependencies (interrupting parallel executions) Control dependencies Data dependencies Register level dependencies Memory level dependencies Memory Speculation 研究背景としてSpMTについて説明します。 SpMTでは、プログラムを細かいスレッドに分割して、複数のプロセッサ上で並列実行します。 しかし、各スレッド間に存在する「依存」を解決しない限り、本来のプログラムの整合性が保たれません。 「依存」は大きく分けて、「コントロール依存」と「データ依存」に分類され、 さらに「データ依存」は「レジスターレベルの依存」と「メモリレベルの依存」の２種類に分かれます。 この「メモリレベルの依存」に対処する手法として「メモリ投機」があります。 そこで本研究の目的ですが、 まず第一に「メモリ投機」を支援する「キャッシュプロトコル」の典型的なモデルを複数提案します。 そして、それらの性能を比較し、一般的な「キャッシュプロトコル」に言える特徴がこれらに当てはまるのかを検討します。 Cache Organization for Memory Speculation

Our Baseline Model –NEKO– まず、もっとも特徴的な機構「スレッド・コントロール・ユニット」がコンパイラにより静的に分割されたスレッドを、動的にプロセッサに割り当てます。 プロセッサは４つ存在し、それぞれのレジスターは同期されています。 次が本研究の対象としているＬ１キャッシュになりますが、ここでメモリ投機を支援します。 最後に共有バスを通じて、これらはＬ２キャッシュと接続されます。 以上が「NEKO」の説明になります。 Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Outline Introduction Background ~Speculative Multi-threading~ Our Baseline Model – NEKO – Cache Coherency Protocols Overview Cache Directories Events Conditions State Diagrams Evaluation Environment Results Conclusions Future Works 次にキャッシュプロトコルについての説明をします。 Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Overview Two major types of cache coherency protocols Invalidate-based Update-based Cache Miss in multi-tasking ×　Bad ○　Good Traffic especially on data bus ○　Little ×　Heavy Design Complexity ○　Simple ×　Complex まず、一般的には大きく分けて２種類のプロトコルが存在します。 １つは「invalidate方式」、そしてもう１つは「update方式」です。 それぞれ、表のような特徴が見られます。 特に今回は「キャッシュミス」と「トラフィック」について注目してください。 Cache Organization for Memory Speculation

Cache Directories Invalidate-based Protocol -MONE- Containing conditions in addition to common information Violation Detection Version Management Line Tag State Condition Word 7 … Word 0 Data Conditions Obsolete Speculative Loaded Stored 2bit 1bit 64bit まず、「invalidate方式」を「メモリ投機」に対応させたプロトコル「MONE」の「キャッシュディレクトリ」の構成について説明します。 今回特徴的なのは「コンディションビット」と呼ばれる付随的な状態ビットです。 「メモリ投機」を支援するには大きく２つ、「Violationの検出」と「バージョン管理」が必要となります。 このうち、「Violationの検出」に利用されるのは青の部分の「コンディションビット」。 「バージョン管理」に利用されるのは赤の部分の「コンディションビット」です。 Cache Organization for Memory Speculation

Cache Directories Update-based protocol -NENEKO- Containing conditions in addition to common information Violation Detection Version Management Line Tag State Conditions Word 7 … Word 0 Data Invalid Shared Modified Obsolete Store Loaded 1bit 64bit 4bit 「update方式」を「メモリ投機」に対応させた「NENEKO」も同様になります。 Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Events Events PrRd Load operation from Processor PrWr Store operation from Processor BusRd Load operation via Bus BusInv Invalidate operation via Bus BusUpd Update (Store) operation via Bus PrSquash Processor is squashed PrCommit Processor is committed PrvCommit Just previous processor is committed BusCommit Other processors are committed Invalidate-based only Update-based only Thread-control Events Unique to Speculative Multi-threading イベントについても簡単に説明します。 この部分がSpMTに特徴的なイベントで、それぞれのプロセッサで実行されるスレッドの終了を通知します。 Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Conditions Conditions bus shared shared with other processors forwarded forwarded from another processor dynamic delayed sent from successor processors masked masked by prior events static loaded loaded by the processor stored modified by the processor obsolete be invalid when next thread is assigned speculative have been forwarded Invalidate-based only Update-based only 我々の提案するプロトコルでは、「イベント」と「コンディション」を入力情報として、状態遷移を行います。 「コンディション」は、先ほど説明した「コンディションビット」で構成される「スタティック・コンディション」 バスからの信号で通達される「バス・コンディション」、また「イベント情報」と「コンディションビット」、「投機レベル」を元に算出される「ダイナミック・コンディション」が存在します。 Cache Organization for Memory Speculation

Cache Organization for Memory Speculation State Diagrams Invalidate-based Protocol -MONE- Update-based Protocol -NENEKO- これらが、それぞれの状態遷移を表した図になります。 通常のプロトコルに比べて、特に複雑な印象はありません。 Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Outline Introduction Background ~Speculative Multi-threading~ Our Baseline Model – NEKO – Cache Coherency Protocols Overview Cache Directories Events Conditions State Diagrams Evaluation Environment Results Conclusions Future Works ここから評価の説明に入ります。 Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Environment Simulator CPON2: MONE/NENEKO Protocol Simulator Processors’ access patterns are gained from trace data of SPECint95 on NEKO Simulator Environment Processors: 4 Cache size: 256kBytes Line size: 64Bytes (=8Words) Associativity: 2 Protocols: MONE/NENEKO (with per-Word / per-Line basis violation detection) MONE/W, MONE/L, NENEKO/W, NENEKO/L まず、キャッシュプロトコルのシミュレータですが、今回開発したシミュレータ「CPON2」は、先ほど説明した２つのプロトコルをシミュレートします。 しかし、これらはプロセッサ部分のシミュレートは行いませんので、「NEKOシミュレータ」によって作成された「アクセス履歴」を入力データとして用います。 これらはSPECint95を走らせた履歴データとなっています。 構成としましては、 プロセッサが４つ。 キャッシュサイズが２５６キロバイト。 ラインサイズ、６４バイト。 アソシアティビティは２。 また、プロトコルについては「MONE」と「NENEKO」の２種類について、Violation検出機構をワード単位で構成した場合とライン単位で構成した場合の２種類。 計２×２の４種類を比較に用いています。Violation検出機構に関しては、ワード単位で構成しないと著しく性能が低下する、という先行研究があったため、NEKOモデルでこれを検証する事にしました。 Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Results Block time ratio Invalidate-based Protocol -MONE- Update-based Protocol -NENEKO- zero zero 2.4×10-4 The worst case of SPECint95 Average of SPECint95 The best case of SPECint95 Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Results Violation Frequency × ○ × ○ The worst case of SPECint95 Average of SPECint95 The best case of SPECint95 Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Results Cache miss ratio thread control missの説明 Capacity or Conflict Only 12.15% invalidations are effective and appear as cache miss reason in the left graph Thread Control Invalidation Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Results Bus event ratio Address Bus Data Bus Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Outline Introduction Background ~Speculative Multi-threading~ Our Baseline Model – NEKO – Cache Coherency Protocols Overview Cache Directories Events Conditions State Diagrams Evaluation Environment Results Conclusions Future Works Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Conclusions Proposal of Cache Coherency Protocols supporting Memory Speculation Evaluations of these Protocols MONE./W MONE/L NENEKO/W NENEKO/L block ○ violation × cache miss △ bus event - Result is different from expectation NENEKOは改善の余地がある Cache Organization for Memory Speculation

Cache Organization for Memory Speculation Future Works Mechanisms for avoiding effects of thread-control Comparison between these protocols and other approaches for Memory Speculation Cache Organization for Memory Speculation