FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

RISC-V 5th Workshopの発表紹介 (Time Traveling Coherence Algorithm)

RISC-V

この記事は ハードウェア開発、CPUアーキテクチャ Advent Calendar 2016 - Qiita の6日目の記事です。

Advent-Calendarを埋めてくれるかた、今からでも募集中です！是非参加してください！ 僕一人では、クオリティのある記事を続けられそうにありません。。。(弱音)

Memory Model in RISC-V

ちょうど先月の終わり頃、5th RISC-V WorkshopがGoogle @ Mountain Viewで開催され、大盛況で終了したという記事が上がっていた。

そこで、本Advent Calendarのエントリでは、RISC-V Workshopのアップロードされた資料の中で、面白そうなものをピックアップしようと考えていたのだが、以外と資料のアップロードが遅い。。。 現時点で数本しか発表資料がアップロードされておらず、過去のWorkshopでYoutubeへ投稿されていた発表動画も未だに投稿されていない。

せっかくネタにしようとしていた情報源がこれでは少なすぎるのだが、これと言って他に情報源も無いので、とりあえず現状でアップロードされているものから、いろいろ調べてまとめてみる。

ちなみに当日の様子は、eetimesにて記事になっている。私は参加したかって？日本に住んでいるし、仕事もあるので不参加でした。

www.eetimes.com

発表資料の紹介

いくつかカテゴリがあるのだが、現時点でアップロードされている資料の中では、メモリモデルに関する発表が多いように感じている。

メモリモデル、特にマルチコア、メニーコアになった場合のコンシステンシの取り方の問題について、多くのアプローチが提案されている。 また、IoTのが普及し、非常に多くのデバイスが存在するようになると、それだけでメモリそのものの考え方や、セキュリティ、アドレッシングをどのようにすれば良いかということに繋がってくる。

Towards Thousand-Core RISC-V Shared Memory Systems

https://riscv.org/wp-content/uploads/2016/11/Wed1000-Thousand-core-RISC-V-Nguyen-MIT.pdf

"Tardis"という新しいコヒーレントプロトコルの紹介。これまでのコヒーレントプロトコルと違い、「タイムスタンプ」を導入し、データを「リース」することによりデータのコヒーレントを保とうとする方式。

ちなみに、このTardisについて検索すると以下の論文が見つかる。あとでしっかり読む必要があるかもしれない。

  • Tardis: Time Traveling Coherence Algorithm for Distributed Shared Memory

https://people.csail.mit.edu/devadas/pubs/tardis.pdf

各コアには、データに対する現在の状態(MESIモデル)を保持しているのだが、それに加えて、集中管理(？)するためのManagerを用意する。こちらでは、データをリースしたタイムスタンプを保持している。これにはwts,rtsという値を利用し、wtsはリースの開始時間、rtsはリースの終了時間を記録する、としている。また、各プロセッサはptsというレジスタにタイムスタンプを保持している。

f:id:msyksphinz:20161205225333p:plain

まず、コアが2つある状態で、Core-0がアドレスAに対してストアを実行すると、

  • ManagerがアドレスAの所有者をCore-0に設定することでリース開始。
  • Core-0はアドレスAを所持し、タイムスタンプを複写
  • Core-0はアドレスAに書き込みを実施し、タイムスタンプwts=1, rts=1と設定する。またpts=1に更新する。

f:id:msyksphinz:20161205225623p:plain:w300

次に、Core-0がアドレスBをロードすると、

  • Core-0はptsをManagerに送り、ManagerはアドレスBのタイムスタンプを設定する。wts=1,rts=1
  • 現在のptsをベースに、タイムスタンプを設定する。wts=1, rts=11 とする。(注: ここでrts=11とするのは何故なのか良く分からない。長い時間保持しておく、ということだろうか？11にあまり意味はない？)

f:id:msyksphinz:20161205230101p:plain:w300

次に、Core-1がBをストアする。ここでは、まだCore-0との競合は発生しないが、タイムスタンプの更新が行われる。

  • Managerは、現在のアドレスBのリース終了時間を+1する。これにより、アドレスBはShared状態からModified状態になり、wts=12,rts=12からは、Core-1が所有し、Modified状態になる、ということになる。

この状態で、Core-0とCore-1で異なる値がアドレスBに対して共存しているという状態が発生する。(Core-1がアドレスBに書き込みを行ったとしても、直ぐ様全体にInvalidateを出さないということか)

f:id:msyksphinz:20161205230151p:plain:w300

次にCore-1がアドレスAをロードしようとすると、

  • ManagerはCore-0に対してアドレスAのライトバックを要求する。これは、ManagerのアドレスAの状態がModifiedで、所有者がCore-0であることから判明する。
  • Core-1がアドレスAのロードを行い、タイムスタンプを設定する。wts=11, rts=22に設定する(つまりリース期間はこの場合は10ということか)

f:id:msyksphinz:20161205230558p:plain:w300

最後にCore-0がアドレスBのロードを行うと、Invalidateを行わないため、シンプルにCacheにヒットしてしまい、ここで最新のデータが取得できないという状態になっている(？)

これ、それを許容するというプロトコルなのかなあ？けど、リース期間は過ぎている訳だから、単純にもう一度取りに行けば良いのじゃないの？

f:id:msyksphinz:20161205231125p:plain:w300

そもそもこのプロトコルの目的は

という訳で、いまいちOrderの守られないプロトコルではあるが、どうやら本来のこのプロトコルの目的は、命令オーダー通りにデータをやりとりすることではなく、通信負荷を削減することらしい。

IoTのように大量のデータを結びつけることになると、そこまで厳密にプロトコルを守る必要は無い、という考えに基いているのかもしれない。

という訳で、少し難しいが RISC-V Workshopで発表されたコヒーレントプロトコルについての紹介をした。まあぶっちゃけRISC-Vには関係無いが、IoTの時代、このようなプロトコルをサポートする必要も生じてくるのかもね。

明日はもう一本、Fast Instruction Simulatorについて紹介しようかと思う。どちらかというと、こっちの方が内容としては簡単め。