FPGA開発日記

FPGAというより、コンピュータアーキテクチャかもね！ カテゴリ別記事インデックス https://msyksphinz.github.io

Microsoftのデータフロープロセッサ EDGEの論文を読む

Twitterで知った、MicrosoftのFPGA向けのインオーダスカラプロセッサの論文が出ている。ターゲットとしてはデータフロー処理だ。 プロセッサの名前としてはEDGEという。ブラウザのEdgeではなくて、Explicit Data Graph Executionの略称である。 面白そうなので、読んでみることにした。

Now Microsoft ports Windows 10, Linux to homegrown CPU design • The Register

  • Towards an Area-Efficient Implementation of a High ILP EDGE Soft Processor

https://arxiv.org/pdf/1803.06617.pdf

EDGEの考え方

EDGEの考え方は、複雑なアウトオブオーダのプロセッサを設計するのではなく、なるべくシンプルに構成すること。これにより回路量が削減されFPGAにフィットしやすくなる。

f:id:msyksphinz:20180623230605p:plain
図1. EDGEの考え方を示す疑似コードとそれに相当する命令ブロック

下記の疑似コードとブロックダイアグラムが、EDGEの考え方を示している。下記のようなプログラムを実行する。

z = x + y
if (z <= 5)

疑似コードとして以下のように変換される。

I[0] ： READ  R0  T[2R]
I[1] ： READ  R7  T[2L]
I[2] ： ADD       T[3L]
I[3] ： TLEI  #5  B[1P]
I[4] ： BRO.T B1
I[5] ： BRO.F B1

最初のREAD R0 T[2R]は、グローバルレジスタファイルR0に格納されているxの値をI[2]の命令のRightオペランド(T[2R])に読み込んだデータを格納する。 次にREAD R7 T[2L] でグローバルレジスタファイルR7に格納されているyの値ををI[2]の命令のLeftオペランド(T[2L])に読み込んだデータを格納する。 そしてどちらのデータもオペランドに揃うと、ADD T[3L]を実行し、その結果をI[3]の命令のLeftオペランドに格納する。 さらにTLEI #5 B[1P]では、演算結果と#5を比較して、その比較結果をPredicate情報としてすべての命令にブロードキャストさせる。このときにブロードキャストに使用するチャネルとしては1(B[1P])を使用する。

上記を見てわかるとおり、命令列に対してデータを供給していくことで命令を活性化させていき、プログラムを先に進めていくという構造だ。

EDGEのマイクロアーキテクチャ

EDGEのマイクロアーキテクチャを図2.に示す。EDGEはシンプルなパイプライン構成をしており、大きくフロントエンドとバックエンドに分かれている。

f:id:msyksphinz:20180623230622p:plain
図2. EDGEのパイプラインアーキテクチャ
  • フロントエンド : Instruction Fetch(IF), Instruction Decode (DC)
  • バックエンド : Instruction Issue(IS), Operand Fetch, Execute(EX), Memory Data Cache Access(LS)

命令が発行できるかどうかは、各命令が必要なオペランドがすべてそろったか、つまり依存関係がすべて解消されたかどうかによって決められる。この命令のスケジューリングはInstruction Schedulerが行っており、発行を待っている命令はInstruction Windowに格納されている。 Instruction Schedulerは32エントリで、32命令を格納することができると思われる。それぞれのエントリはオペランドに対して状態を持っており、すべてのオペランドがReady状態になることで命令発行が可能になる。Instruction SchedulerはReady状態になった命令のうち最もIID(Instruction ID)の低いものを選んで発行する。

並列Instruction Scheduler

Instruction Schedulerは、毎サイクル2命令を発行することができる。2命令をよどみなく発行するためには、データの依存関係をなるべく早く解決してどんどんデータフローに流していくことが重要である。命令の発行を高速化させるために、演算が完了してレジスタで一度叩かれる間に、Instruction Schedulerにフォワーディングがされるようになっている。

命令発行可能かどうかを判定するために、Instruction Schedulerの32エントリにはそれぞれデコーダがおかれている。図3.にInstruction SchedulerのParallel Dataflow Schedulerの構造を示す。

f:id:msyksphinz:20180623230638p:plain
図. 並列Instruction Schedulerのアーキテクチャ
  • RT, RF: True Predicate / False Predicate ビットがReady状態か
  • R0, R1 : オペランド0 / オペランド1がReady状態か
  • INH : 命令が既に発行されているか
  • RDY : 命令が発行可能状態になっているか

RDYが有効になる条件は RT & RF & R0 & R1 & ~INH であり、これにより命令発行が可能になる。

Incremental Instruction Scheduler

一方で、並列Instruction Schedulerは32エントリ×6ビットのFFを消費してしまいリソースの使用量が大きい。 しかし、各サイクルで発行される命令によりReady状態に変化が現れるのは最大でも別の2つの命令である。そこで、デコードされた命令と現在のReady状態をLUT RAMに残しておき、Ready状態である先頭の2命令をキューに格納しておくという方法がある。 FFの配列による実装と比較して、LUT RAMの実装は高速であるが、1サイクル当たり1Writeしか実行できないという弱点がある。そこで、LUT RAMとFFをハイブリッドで使用する。

f:id:msyksphinz:20180623230655p:plain
図. Incremental Instruction Schedulerのアーキテクチャ

並列SchedulerとIncremental Schedulerの比較

以下に並列SchedulerとIncremental Schedulerの比較を示す。回路面積としてはIncremental Schedulerのほうが優れているが、並列Schedulerの方が命令のストールが発生する確率が少なく、性能的に有利である。

Metric Parallel Incremental Units
Area. 32 entries 288 78 LUTs
Area Total. 32 entries 340 150 LUTs
Period 5.0 4.3 ns
Period, pipelined 2.9 2.5 ns
Area, Total * period 1700 645 LUT*ns
Broadcast flash iterative
Event bank conflicts never sometimes
Area, 4 events/cycle 288 156 LUTs
Area, 64entries 576 130 LUTs