Skip to content

Changes

Page history
Create FPGAMultiportRAM authored by Toru Koizumi's avatar Toru Koizumi
Hide whitespace changes
Inline Side-by-side
FPGAMultiportRAM.md 0 → 100644
View page @ 921ce2ed
マルチポートメモリの作り方
==========================
スーパスカラプロセッサを作る場合、1 cycleに二要素以上を書き換えられるメモリが欲しくなることがあるかと思います。例えばレジスタファイルなどがそれに該当するはずです。1 cycleに二命令処理するためには、レジスタファイルにwrite portが2つ必要です（そのような場合はストールするという戦略も可能ですが、性能が大きく低下します）。
このような時、以下のようにレジスタファイルを記述すると、分散RAMに推論されずフリップフロップ（とツリー状の選択回路）に合成されてしまいます。これに必要なフリップフロップは1000個程度（32bit×31要素）です。この規模の論理回路の合成は十分可能であり、またそれなりの速度で動作します。
```verilog
module regfile(raddr1, rdata1, raddr2, rdata2, raddr3, rdata3, raddr4, rdata4,
we1, waddr1, wdata1, we2, waddr2, wdata2, clk);
input wire [4:0] raddr1;
output wire[31:0] rdata1;
input wire [4:0] raddr2;
output wire[31:0] rdata2;
input wire [4:0] raddr3;
output wire[31:0] rdata3;
input wire [4:0] raddr4;
output wire[31:0] rdata4;
input wire we1;
input wire [4:0] waddr1;
input wire[31:0] wdata1;
input wire we2;
input wire [4:0] waddr2;
input wire[31:0] wdata2;
input wire clk;
reg [31:0] mem [0:31];
initial mem[0] = 0;
always @(posedge clk) begin
if(we1) mem[w_addr1] <= w_data1;
if(we2) mem[w_addr2] <= w_data2;
end
assign r_data1 = mem[r_addr1];
assign r_data2 = mem[r_addr2];
assign r_data3 = mem[r_addr3];
assign r_data4 = mem[r_addr4];
endmodule
```
ここからさらに高速化＆省資源化するため、分散RAMをうまく活用してレジスタファイルを作ることを考えます。
そのためには、どういう制約を満たしている場合に分散RAMに推論されるかを正確に理解する必要があります。
FPGAに内蔵されている分散RAMの**ハードウェア仕様**（何ができて何ができないのか）は、以下の通りです。
* クロック同期でしか書き込めない
* 読み出しはクロックと非同期でできる
* write port数は1
* read port数は1
一方、Vivadoが分散RAMに**推論する条件**は、以下の通りです。
* 書き込みがクロック同期になっている
* 読み出しはクロック同期でもクロック同期でなくてもよい
* ただし、読み出しがクロック同期の場合、BlockRAMでも実現可能な可能性があります。BlockRAMで実現可能かつ大容量な場合、BlockRAMが優先されることがあります
* write port数が1
* write port数が0の場合、つまりROMの場合はLUTに推論されます
* read port数はいくつであってもよい
* 実際、read port数が2つあるレジスタファイルを作ってみれば、確かに分散RAMに合成されることが分かります
ここで「分散RAMの read port数は1のはずなのに、read port数が2以上の場合でも分散RAMに推論できるのはなぜか？」という疑問が生じるかと思います。この疑問に答えるためには、どのようにしたらread port数を増やすことができるかを知っておく必要があります。
## Read port数を増やす技術：レプリケーション
Read port数を増やすためには、レプリケーションという方法が使われます。
レプリケーションとは、単純にメモリをread port数分だけ複製する方法です。
書き込むときは、全てのメモリに書き込みます。
読み出すときは、`r_addr1`、`r_addr2`、`r_addr3`……をそれぞれのメモリに入力します。
このようにすることで、1 read + 1 writeのメモリだけを使用してread port数が2以上のメモリ（と同じインタフェースを持つメモリ）を作ることができます。
Vivadoは、このレプリケーションを自動で適用することで、read port数が2以上のメモリを自動で分散RAMに合成してくれます。
## Write port数を増やす技術
一方、write port数を増やすのはこのような単純な方法ではうまくいきません。
実際、FPGA上にある資源をうまく組み合わせてwrite port数を増やす技術に関してはそれだけで論文が書けるようなテーマであり、自動で推論できる類のものではありません。
以下では、write port数を増やす技術の一つである、XOR-based multiport memoryというものを紹介したいと思います。
まずは前提知識として、メモリのバンク化という技術を紹介し、つづいて Live Value Tableと呼ばれる技術を軽く紹介します（論文：https://dl.acm.org/doi/10.1145/1723112.1723122 ）。
その後、本題のXOR-based multiport memoryという技術を紹介します（論文：https://www.eecg.utoronto.ca/~steffan/papers/laforest_xor_fpga12.pdf ）。
### メモリのバンク化
「`w_addr1`でしか書き込めないメモリ領域」と「`w_addr2`でしか書き込めないメモリ領域」のように分割することを考えます。
このようにすることで、write port数が1のメモリしか使えない場合でも1 cycleに二か所書き込むことは可能になります。
このような、特定のアドレス範囲しか使えないメモリを複数用意する方法を**バンク化**と言います。
もしかしたら、データメモリを構成するために、アドレスの下位2ビットが`2'b00`であるデータを保存するメモリ、`2'b01`用のメモリ、`2'b10`用のメモリ、`2'b11`用のメモリ、のようにメモリアドレス全体を4分割するような方法を使った人がいるかもしれません。
このようなものもバンク化の一種です。
バンク化で問題を解決できるのは、「`2'b00`用のメモリ、`2'b01`用のメモリ、`2'b10`用のメモリ、`2'b11`用のメモリのそれぞれに高々一エントリ書き込む」といった場合です。
レジスタファイルの問題は、このようなバンク化により解決することはできません。
二命令のデスティネーションレジスタ番号が4と8であれば、どちらも`2'b00`用のメモリに書き込まなければいけません（バンク衝突と言います。そのような場合にストールするという戦略もあります）。
二命令のデスティネーションレジスタの組み合わせは任意の組み合わせが来うるため、どのようにメモリを分割しても実現が不可能な点に注意してください。
なお、31分割すればできますが、それはフリップフロップと選択回路で実現しているのと同じことになります。
一般に、バンク化を適用する場合、多バンクになればなるほど、(1)一バンク当たりの要素数が少なくなりRAMの効率性が失われ、また(2)選択回路のオーバーヘッドも増大します。
### Live Value Table
メモリ領域を分割する**のではなく**、メモリ領域全体をwrite port数個だけ複製したRAMを持つことを考えます。
それぞれのRAMは、「`w_addr1`でしか書き込まない」「`w_addr2`でしか書き込まない」……といった運用にすることにします。
これも一種のバンク化なのですが、メモリ領域を分割するタイプのバンク化と異なり、バンク衝突が起こりません。
つまり、任意の書き込みアドレスの組み合わせを取り扱えるということです。
一方、このような運用にすると、「どのバンクに最新のデータが入っているか」というのが問題になります。
他のバンクには古いデータが入っているので、これを読み出してしまってはいけません。
「どのバンクに最新のデータが入っているか」を管理する表（“生きている”値がどれかを記録する表、Live Value Table (LVT)）を作る必要があるということです。
残念ながら、このLVTもまた、元のメモリと同じwrite port 数を要求するので、LVTを使う方法は本質的に問題を解決したことにはなりません。
ただし、LVTは非常に幅が狭い（レジスタファイルは32bit×31エントリ、LVTは1bit×31エントリ（write port数が2の時））なので、これをフリップフロップで作ることを妥協してしまえば、のこりは分散RAMで作ることができます。
LVTを使った場合、write port数をw、read port数をrとして、wr倍のメモリ容量が必要になります。
なぜなら、本体のデータを保存するためには、（write port数個だけバンクを用意）×（read port数個だけレプリケーション）が必要だからです。
### XOR-based multiport memory
XOR-based multiport memoryは、Live Value Table の時と同様、メモリ領域全体をwrite port数個だけ複製したRAMを持ち、それぞれのRAMは「`w_addr1`でしか書き込まない」「`w_addr2`でしか書き込まない」……といった運用にします。
XOR-based multiport memoryの核となるアイデアは、『`wdata`をそのまま担当メモリバンクに書き込むのではなく、「すべてのメモリバンクの値のビット毎排他的論理和を取った値が最新の値」になるように、**適切な値**を担当メモリバンクに書き込む』というものです。
このようになっていれば自明に、「どれが最新データであるか」みたいな面倒な問題はないことが分かります。
そのような書き込みがいつでも可能か（担当メモリバンクに書き込むだけで「最新の値」を任意の値に書き換えられるか）という点が気になりますが、これは排他的論理和の性質から、そのような条件を満たす値が常にちょうど一つ存在することが分かります。
具体的な実装（4 read + 2 writeをサポートするレジスタファイル）は以下のようになります。
この実装（というか一般にマルチポートメモリのほとんど）は、論理的に同じインデックスの位置に同時に書き込むと値が壊れてしまいます。必要であれば「`waddr1 == waddr2`であるかを確認して、そうであれば`we1`を落とす」のようなロジックを追加してください。
```verilog
module regfile(raddr1, rdata1, raddr2, rdata2, raddr3, rdata3, raddr4, rdata4,
we1, waddr1, wdata1, we2, waddr2, wdata2, clk);
input wire [4:0] raddr1;
output wire[31:0] rdata1;
input wire [4:0] raddr2;
output wire[31:0] rdata2;
input wire [4:0] raddr3;
output wire[31:0] rdata3;
input wire [4:0] raddr4;
output wire[31:0] rdata4;
input wire we1;
input wire [4:0] waddr1;
input wire[31:0] wdata1;
input wire we2;
input wire [4:0] waddr2;
input wire[31:0] wdata2;
input wire clk;
reg[31:0] mem_b1[0:31];
reg[31:0] mem_b2[0:31];
initial mem_b1[0] = 0;
initial mem_b2[0] = 0;
always @(posedge clk) begin
if(we1) mem_b1[waddr1] <= wdata1 ^ mem_b2[waddr1];
if(we2) mem_b2[waddr2] <= wdata2 ^ mem_b1[waddr2];
end
assign rdata1 = mem_b1[raddr1] ^ mem_b2[raddr1];
assign rdata2 = mem_b1[raddr2] ^ mem_b2[raddr2];
assign rdata3 = mem_b1[raddr3] ^ mem_b2[raddr3];
assign rdata4 = mem_b1[raddr4] ^ mem_b2[raddr4];
endmodule
```
XOR-based multiport memoryで実現する場合、write port数をw、read port数をrとして、w(r+w-1)倍のメモリ容量が必要になります。
R=r+w-1というのは、内部的なread port数です。
外部につながっているread port数に加えて、「適切な値」を計算する際に担当バンク以外を読み出す必要があるため(w-1)バンクの読み出しが必要になるためです。
したがって、データを保存するためには（write port数個だけバンクを用意）×（R個だけレプリケーション）倍のメモリ容量が必要になります。
XOR-based multiport memoryはフリップフロップが完全に不要という利点がありますが、容量がw(r+w-1)倍に増えてしまいます。
LVTを使った場合は容量がwr倍にしか増えないため、これよりオーダーが悪いということになります。
この特徴を組み合わせ、データの保存はLVT方式で行い、LVT自体をXOR-based multiport memoryで作るという方法がほとんどの場合に有効であることが知られています（論文：https://www.ece.ubc.ca/~lemieux/publications/abdelhadi-fpga2014.pdf ）。
なお、レジスタファイルを実現する際はこのオーダーの違いは大きく効いてこないので気にする必要はありません（LVT方式の欠点である遅延の増大の方が効いてきます）。
## True dual port BlockRAM
もしかすると、データメモリも1 cycleに二要素以上を書き換えたくなるかもしれません。
クロック同期かつread portとwrite portの合計が2までであればBlockRAMに推論されるのですが、write portを二つにしてしまうとreadができなくなってしまいます。
実は、メモリのポート（アドレス線入力）はreadとwriteで共用にできます（むしろ、これが普通です）。
以下では、read/write共用ポートを使ってBlockRAMのwrite port数を増やす方法を紹介します。
Read/write共用ポートが二つのメモリのことを、true dual port memoryと呼びます。
True dual port memoryは、1 cycleに「2 read」「1 read + 1 write」「2 write」のいずれかができます。
対称的に、1 cycleに「1 read + 1 write」しかできない1 read + 1 writeのメモリのことを、simple dual port memoryと呼びます。
True dual port memoryはsimple dual port memoryの上位互換です。
True dual port memoryの機能を制限すればsimple dual port memoryを作れますが、その逆はできません。
FPGAに存在するBlockRAMは、true dual port memoryですが、[FPGA 内蔵 RAM の使用方法](FPGARAM#ブロックram)で紹介した方法で記述してしまうとsimple dual port memoryになってしまいます。
BlockRAMの機能をフルに使うには、以下のように記述します。
```verilog
module databram(addr1, rdata1, we1, wdata1, addr2, rdata2, we2, wdata2, clk);
input wire[13:0] addr1;
output wire[31:0] rdata1;
input wire [3:0] we1;
input wire[31:0] wdata1;
input wire[13:0] addr2;
output wire[31:0] rdata2;
input wire [3:0] we2;
input wire[31:0] wdata2;
input wire clk;
reg[31:0] mem[0:16383];
// Vivadoに推論させるためには、alwaysを二個に分離しないといけない
// また、バイトイネーブル付きだと推論してくれない（自前でバンク化するなどで対処する必要がある）
// 第一ポート：Read-first（書き込む前の値がrdata1として得られる）
always @(posedge clk) begin
if (we1) mem[addr1] <= wdata1;
rdata1 <= mem[addr1];
end
// 第二ポート：Read-first（書き込む前の値がrdata2として得られる）
always @(posedge clk) begin
if (we2) mem[addr2] <= wdata2;
rdata2 <= mem[addr2];
end
endmodule
```
また、以下のように書くことでもBlockRAMに推論されます。
こちらの書き方をしたほうが高速に動作するとされています。
ただし、書き込みアドレスと同じアドレスを読み出した時の挙動は、**Verilogでの記述に反して、何が読みだされるか保証されない**ので要注意です。
また、当たり前ですが、同じアドレスに二つの値を同一サイクルに書き込んだ場合、どんな値が書き込まれるかは保証されないので注意してください。
```verilog
module databram(addr1, rdata1, we1, wdata1, addr2, rdata2, we2, wdata2, clk);
input wire[13:0] addr1;
output wire[31:0] rdata1;
input wire [3:0] we1;
input wire[31:0] wdata1;
input wire[13:0] addr2;
output wire[31:0] rdata2;
input wire [3:0] we2;
input wire[31:0] wdata2;
input wire clk;
reg[31:0] mem[0:16383];
// Vivadoに推論させるためには、alwaysを二個に分離しないといけない
// また、バイトイネーブル付きだと推論してくれない（自前でバンク化するなどで対処する必要がある）
// 第一ポート：Write-first（書いた場合、その値がそのままrdata1として得られる）
// ただし、第二ポートに書き込んだアドレスと同じアドレスを読み出した時、記述に反して値は不定
if (we1) begin
mem[addr1] <= wdata1;
rdata1 <= wdata1;
end else begin
rdata1 <= mem[addr1];
end
// 第二ポート：Write-first（書いた場合、その値がそのままrdata2として得られる）
// ただし、第二ポートに書き込んだアドレスと同じアドレスを読み出した時、記述に反して値は不定
if (we2) begin
mem[addr2] <= wdata2;
rdata2 <= wdata2;
end else begin
rdata2 <= mem[addr2];
end
endmodule
```
なお二ポートのうち片方をread-firstに、もう片方をwrite-firstにすることも可能です。
その場合、両ポートで同じアドレスを指定した場合しread-firstなポートに書き込んだ場合、もう一方の側では**Verilogの記述にかかわらず**古い値が読み出せます。一方、両ポートで同じアドレスを指定しwrite-firstなポートに書き込んだ場合、もう一方の側で読み出される値は不定です。
```verilog
module databram(addr1, rdata1, we1, wdata1, addr2, rdata2, we2, wdata2, clk);
input wire[13:0] addr1;
output wire[31:0] rdata1;
input wire [3:0] we1;
input wire[31:0] wdata1;
input wire[13:0] addr2;
output wire[31:0] rdata2;
input wire [3:0] we2;
input wire[31:0] wdata2;
input wire clk;
reg[31:0] mem[0:16383];
// Vivadoに推論させるためには、alwaysを二個に分離しないといけない
// また、バイトイネーブル付きだと推論してくれない（自前でバンク化するなどで対処する必要がある）
// 第一ポート：Write-first（書いた場合、その値がそのままrdata1として得られる）
// ただし、第二ポートに書き込んだアドレスと同じアドレスを読み出した時、記述に反して古い値が得られる
if (we2) begin
mem[addr1] <= wdata1;
rdata1 <= wdata1;
end else begin
rdata1 <= mem[addr1];
end
// 第二ポート：Read-first（書き込む前の値がrdata2として得られる）
// ただし、第一ポートに書き込んだアドレスと同じアドレスを読み出した時、記述に反して値は不定
always @(posedge clk) begin
if (we2) mem[addr2] <= wdata2;
rdata2 <= mem[addr2];
end
endmodule
```
\ No newline at end of file