FPGAはどのようにして書き換えられるのか？〜SRAM型FPGAからNBFPGAへ〜

# 1. はじめに
本記事は，[東京大学航空宇宙工学科／専攻 Advent Calendar 2018](https://t.co/nqDlxGUCIV)の12日目のものです．

# 2. 自己紹介
現在，航空宇宙工学科の学部4年です．宇宙工学系の研究室に所属しており，研究室プロジェクトでFPGA（を利用した画像処理）のプログラミングを担当しています．といっても電気系専攻のガチプロの方々と比べると底辺です．

# 3. FPGAとは
## ロジックICとしてのFPGAの立ち位置
FPGAとはField Progammable Gate Arrayと呼ばれる，PLD（Programmable Logic Device）の一つです．以下の分類表のようなものを用いて説明されることも多いですが，結構文献によって言葉の定義・分類法が違うのであくまで一例として参考にしていただけると幸いです．

<img width="525" alt="スクリーンショット 2018-12-12 4.06.33.png" src="https://qiita-image-store.s3.amazonaws.com/0/320962/795d8646-4bac-c7af-1176-16bddc2cc1bc.png">

一般に論理演算を行う集積回路をロジックICなどと呼びますが，それは完全にある用途に特化したカスタムIC，色々な目的に共通して使える汎用ICの2つに分けられます．カスタムICの一番わかりやすい最近の例としては，仮想通貨のマイニングのためにASICを設計するというやつでしょうか．その汎用ICの中には汎用ロジックICとしてFFやALUなどがある一方で，ユーザー側が論理回路の動作を変更できるPLDというものがあるというわけです．そのPLDの中でも回路の規模の大きさに応じて分類があり，SPLD，CPLD，FPGAの順に規模が大きくなっています．言い方を変えれば，FPGAが最も設計の自由度が大きいということになります．

余談ですが，「---はマイコンでできないからFPGAでやればいいんじゃない？」みたいな話をよく聞きます．間違った言い方ではないと思いますが，個人的にはマイコンとFPGAは同じ次元で語るべきものではないと思っています．Raspberry Piのようなマイコンはもちろんハードウェアの変更は不可で，ソフトウェアを変えることで様々な動作をしています．この既存のハードウェア+ソフトウェアでできることに限界がある場合に，もうハードウェアも自分オリジナルにしてしまえばいい，という意味では間違った言い方ではないとは思います．しかし，既存のハードをFPGAで担当して思い通りの回路にしたからといって，それはマイコンに変わりないはずです．そういう意味で，「---はALUやRAMなどの既存の汎用ロジックICを用いて作成した汎用マイコン（Raspberry Piとか）でできないから，FPGAでハードもアレンジした自作マイコンでやればいいんじゃない？」というイメージだと思います．現に，最近のFPGAは内部にCPUを内蔵しているものも多く，HDLによってハードウェアを作成し，C言語などを用いてソフトウェアを書いて，それらをあわせて１つのデバイスとして動かすということもできます（研究室プロジェクトで利用しているFPGAもそうです）．もっと端的に言えば，FPGAはアクセラレータであるとも言えます．

## FPGAの内部構造
話が逸れましたが，FPGAの内部構造について簡単にまとめます．以下の図[^1]はアイランドスタイルと呼ばれる，一般的なFPGAの構造を表しています．

<img width="395" alt="スクリーンショット 2018-12-12 3.21.40.png" src="https://qiita-image-store.s3.amazonaws.com/0/320962/899e05e6-a663-b0ae-f48f-fce560668b22.png">

<dl>
  <dt>IOB（Input Output Block）</dt>
  <dd>その名の通り，外部のデバイス（LED，加速度センサー，カメラセンサー，etc．）とのインターフェイスとなる部分．</dd>
  <dt>LB（Logic Block）</dt>
  <dd>FPGAのメインとなる部分．このLBの中身を変更することで，あるときにはただの組み合わせ回路になったり，RAMになったりする．</dd>
  <dt>CB（Connection Block）</dt>
  <dd>LBからのアウトプットの配線を他のLBなどにつなげるときにLBの入り口・出口の橋渡し役となる部分．</dd>
  <dt>SB（Switch Block）</dt>
  <dd>スイッチのように，LB→CBと通ってきた信号をどこのLBへ送るか切り替える部分．</dd>  
  <dt>その他</dt>
  <dd>上記以外に，クロックを各ブロックに張り巡らせるためのクロックネットワーク，コンフィグレーションデータ（回路を書き換えるための情報，後述）をLBやSBなどに送るためのコンフィグレーションチェーン，乗算などのように通常のLBでは面倒な計算に特化したDSPブロック，など多くの要素がある．
</dl>

# 4. FPGAを書き換えるとはどういうことか
本題です．FPGAの内部構造を見れば分かるように，LBの中身を自分の思い通りに書き換えて，さらに思い通りに書き換えたLB同士を思い通りに作ったスイッチング回路でつなげてあげれば，思い通りの回路ができそうです．
ここで，回路を書き換えるためには，以下の手順が必要になります．

1. 回路情報のデータ（コンフィグレーションデータ）を作成する（拡張子.bitのファイル）
1. 作成したデータをFPGAに書き込む
1. FPGAがコンフィグレーションデータを読み込んでそのデータをLB，SBなどに送る
1. 送られてきた情報を元に，LBやSBなどを書き換える

2については大きく分けて2通りあり，最初からFPGAに直接（.bitファイルのまま）書き込むか，一度FPGA外部の不揮発性メモリに（拡張子.mcsファイルとして）コンフィグレーションデータを書き込んでからそれをFPGAが読み出すかとなります．直接書き込む場合，後述のSRAM型FPGAならば，SRAMが揮発性なので，FPGA電源ONするたびにわざわざFPGAに書き込みをしなくていいように，通常は外部ROMにコンフィグレーションデータを書き込みます．

1については，FPGAの統合開発環境として有名なVivadoやQuartusなどを用いて作成し，2についてもFPGA本体とセットで販売されている専用の書き込み用ケーブルで書き込みます．
3について，基本的にはFPGAには外部に保存されたコンフィグレーションデータを自分から読み出す機能がついており，この仕組はコンフィグレーションチェーンと呼ばれています．
最後に，4が最も想像し難いと思うのでより詳細を見ていきたいと思います．

# 5. SRAM型FPGA
FPGAが読み出したコンフィグレーションデータを元にLB内部で組み合わせ回路を表現する際に，以下の代表的な手法が用いられます．

1. プロダクトターム方式
2. LUT（Look Up Table）方式

また，読み出したコンフィグレーションデータを（少なくともFPGA電源ONの間）LBやSB自身が保持している必要がありますが，そのためにも以下のような方式が用いられます．

1. フラッシュメモリ
2. アンチヒューズ
3. SRAM（Static RAM）

特に，現在のFPGAではLUT方式とSRAMを組み合わせたものが多く，本記事ではこれに焦点を当てていきます．

## LUT（Look Up Table）
LUTという言葉自体はFPGA特有というわけではないので，言葉だけで大体どういうものかイメージできると思いますが，FPGAにおけるLUTとはどういうものかというと，例えば下の図のように，X，Y，Zという3bitの信号があったときに，X，Y，ZがそれぞれこうなっていたらOutputはこうする，というものを達成するための組み合わせ回路です．要するに真理値表をそのまま組み合わせ回路で体現したものをLUTと呼んでいるだけです．
<img width="155" alt="スクリーンショット 2018-12-12 6.43.58.png" src="https://qiita-image-store.s3.amazonaws.com/0/320962/b870a261-e090-e0c4-1d46-6e7ad1851de5.png">

## SRAM（Static RAM）
SRAMについては，ご存知の方も多いと思うので，適当に[wikipedia](https://ja.wikipedia.org/wiki/Static_Random_Access_Memory)などを参照してください．よくある揮発性メモリです（写真はwikipediaから）．Qが保持されているデータで，それがBLを通して外に読み出されるというイメージでしょうか．
<img width="250" alt="スクリーンショット 2018-12-12 6.31.40.png" src="https://qiita-image-store.s3.amazonaws.com/0/320962/1a9fa29a-b044-ad9c-c7de-73daa74a75e9.png">

## SRAM+LUTのLBへの利用
ではLUTとSRAMを用いてどうやって任意の組み合わせ回路が作れるのかについての本題です．SRAMに任意のデータを保存すれば，それによって原理上任意の組み合わせ回路が作れることになります．
具体的に，例えば以下の真理値表を持つような組み合わせ回路をLB内に作りたいとします．

|X  |Y  |Z  |Out |
|---|---|---|----|
|0  |0  |0  |0   |
|0  |0  |1  |0   |
|0  |1  |0  |0   |
|0  |1  |1  |1   |
|1  |0  |0  |0   |
|1  |0  |1  |1   |
|1  |1  |0  |1   |
|1  |1  |1  |1   |

ちなみにこれを積和形に書き直して，HDLの１つであるverilogで書くと以下のように簡単な形でかけます．

```Javascript:hoge.v
Out = (X & Y) | (Y & Z) | (Z & X);
```

このとき，SRAMとMUX（マルチプレクサ，これがNANDゲートから作れるのはおなじみですよね）を用いて以下のような図の回路を構成すると，実はこれが所望のLUTにそのままなっていることがわかります．
<img width="500" alt="スクリーンショット 2018-12-12 7.32.28.png" src="https://qiita-image-store.s3.amazonaws.com/0/320962/b4b186d7-8008-9a85-8c8b-0b6aecea0755.png">
例えば，X=1，Y=0，Z=1のときを考えます．Z=1なので，最初の4つのMuxのSelectorは1となり，SRAMのうち上から数えて2，4，6，8番目がMUXからOutputされます．そのOutputに対し，Y=0が次の2個のMuxのSelectorとなるのでSRAMのうち上から数えて2番目，6番目がMUXからOutputされます．最後にX=1なので，結局SRAMの上から数えて6番目が最終的なこのLUTのOutputとなります．MUXはNANDゲートから簡単に作れるので，SRAMをこういうふうに使えば，SRAMの中身を書き換えるだけで任意の組み合わせ回路が原理的に作れることになります．ただ，積和形などを用いるともっと回路を簡略化できるのに，こういう$2^n$オーダーで増えていくような回路を予めFPGA内に用意することはその分無駄が増えるということにもなります．そのかわり任意の回路が再構成できるのがFPGAの強みです．これとトレードオフ関係にあるのはASICで，ASICはこういった汎用的な回路を持たずに専用の特化した回路を持ち，書き換え不可能です．

まとめると，上記においてverilogで書いたコードを統合開発環境で論理合成してマッピングすると前述した.bitファイルが生成され，.bitファイルをFPGAに直接書き込むと，結局LB内部のSRAMの値をいじることでverilogで記述した論理回路がLB内で表現されることになります．

さらに，ここでLBの中身についてより詳しく説明しておきます．
１つのLBは基本的にはいくつかのSliceというものが集まってできています．さらにSliceというものは，いくつかのLUTやFF，SRAMなどが集まってできています．LUTだけであれば，組み合わせ回路しか表現できませんが，そこにFFなどが絡むことによって値を保持する順序回路なども作ることができます．以下のようなイメージです．各Slice内で，SRAMの値をどう保持させるかによってLUTの内容を変えたり，FFを使うか決めたり（これは厳密に言えば次に出てくるSBへの応用のスイッチ的な側面ですが）することによってSliceの中身を自在に変更することができます．
<img width="300" alt="スクリーンショット 2018-12-12 16.36.56.png" src="https://qiita-image-store.s3.amazonaws.com/0/320962/86c37b2c-a4fc-bcdb-2470-9c7aff3bef93.png">

## SRAMのSBへの利用
すでに述べたようにSliceの中身を自在に変更できますが，１つのSliceの中に入っているLUTやFFの数には限りがあるので，実際にはこのSlice間（or LB・IOB間）での配線も自在に変更できなければいけません．
このために，どうやったらできるだけ簡潔な方法で複雑な配線のスイッチングができるかという研究がなされているようで（グラフ理論的な？），以下の図[^2]のようにSBのトポロジーとして良いものがいくつかあるようです．色々難しそうに見えますが，結局の所は拡大図にあるようなトランジスタ（パストランジスタといいます）のコントロールゲートに電圧をかけてONにするかどうかを，SRAM内の値の0 or 1で決めることで任意のスイッチングを達成できることになっています．これによってSlice間（or LB・IOB間）でも配線の変更が可能となり，こういったことが可能なのでFPGAは書き換えられると言っているわけです．
<img width="319" alt="スクリーンショット 2018-12-12 8.16.42.png" src="https://qiita-image-store.s3.amazonaws.com/0/320962/d53e1ca1-6bad-37ec-5853-ee4553923130.png">

# 6. SRAM型FPGAの例（Virtex-5）
今まで，FPGAのコンフィギュレーションに関する一般論（ちゃんとした本FPGAの本には書いてある内容）を述べましたが，ここで具体的にVirtex-5というFPGAを例にして具体的にFPGAの構成はどういう感じなのか簡単に紹介します．以下の画像はFPGAの統合開発環境であるISEにおいて，FPGA設計を行い.bitファイルを生成した結果です．FPGA内に内蔵されているリソースのうち，何がどれだけ消費されているかをDesign Summaryの形で見ることができます．

![キャプチャ.PNG](https://qiita-image-store.s3.amazonaws.com/0/320962/2980e507-79d0-3ce7-9012-9c1dd3af247c.png)
![キャプチャ1.PNG](https://qiita-image-store.s3.amazonaws.com/0/320962/1cca4ba0-3f66-dbc4-3073-2ec44651259a.png)

まず，`Number of Occupied Slices`というものがあります．これはさきほど，各LBの中にいくつかSliceがあるといった通り，FPGA内に存在する全てのLB内のSliceの総数が7200であることを表しています．そして１つのSliceの中にはLUTやFFがいくつか含まれていると述べましたが，このVirtex-5では，公式ドキュメント[^5]によれば

> Virtex-5 FPGAのスライス構造はこれまでのFPGAファミリと異なり，各Virtex-5 FPGAスライスに LUTおよびフリップフロップが4個ずつ含まれています（従来は，各2個）．

となっています．つまり．Sliceの数に対してLUTやFFは4倍の数があるということです．実際に表を見ても．
`Number of Slice Registers`と`Number of Slice LUTs`は28800個となっています．実際にはここでいうRegistersはFFだけでなくラッチ回路（FFとは違い，クロック同期せずにデータを保持する回路のようなもの）も含んでいます．さらに，`Number of Slice LUTs`を深く見ると`O6 output only`などとあります．公式ドキュメント[^6]によれば

> Virtex-5 FPGAのファンクションジェネレータは，6入力のルックアップテーブル(LUT)としてインプリメントされています（厳密に言えばすべてが6入力ではないのですがあまりにも細かい話なので省略します）．各スライス （A，B，C，およびD）の4つのファンクションジェネレータには，6つの独立入力（A入力‐A1～A6と2つの独立出力(O5およびO6)があります．

となっています．つまりVirtex-5のSlice内のLUTは6入力で（先程の例は3入力），Outputの仕方などはO5，O6を利用した複数のやり方があるようです．今回の設計結果では，O6がほとんどとなっています．つまり，Virtex-5の全てのLUTを使えば，原理的には6入力の任意の組み合わせ回路を28800個使えるということになります．

また，Design Summaryの下の方を見ていくと，`Number of bonded IOBs`とあります．これがさきほど出てきたInput Output Blockってやつです．220個中168個使われています．

さらにその下を見ていくと，Block RAM，BUFGなどとあり，先程アイランドスタイルのFPGAを紹介する際にちらっと出てきたDSPもあります．これらはLB，SBなどとは違いその他に分類されるものです．Block RAMについて，FPGA開発をする上で，RAMは絶対に必要なので元からBlock RAMとしてある程度パッケージ化されてFPGA内に存在しています．ちなみに，`Number of Slice LUTs`において，よく見ると`Number used as logic`と`Number used as memory`とあります．`Number used as logic`は先程説明したように，論理回路として使われているLUTである一方で，LUTはSRAMを内蔵しているので，ただのRAMとして使うこともできます．もとからFPGA内に用意されているBlock RAMが足りなくなったり，Block単位でしか使えないBlock RAMを節約したりするために，LUTをRAMのように扱うという手段が用意されているというわけです．このようにLUTを用いたRAMを分散RAMと呼び，FPGA設計においてRAMを使うとなればBlock RAMと分散RAMを使い分けることになります．

# 7. NBFPGAとは
NBFPGAとはNano Bridge FPGAの略であり，SRAM型FPGAに変わる次世代のFPGAとして今注目を集めています．このNBFPGAについて，人工流れ星の技術実証もあるのでご存知の方もいるかもしれませんがJAXAの革新的衛星技術実証プログラム[^3]の1号機に搭載される衛星の一部となっています．このNBFPGAはNECが開発した最先端のスイッチング技術のようで，ここまでSRAMが担ってきた役割を，金属原子で代用するというものです．サイト[^4]から直接とってきたのであれですが，以下の図のように金属原子間に金属の架橋を作るか否かで，0 or 1を作り出せるようです．このメリットとして挙げられるのはSRAMと比べて圧倒的に放射線耐性が強いということがあります．宇宙空間では普通のRAM等は放射線によるシングルイベント的なやつですぐだめになってしまう一方で，NBFPGAは金属原子を用いているので放射線エラーに非常に強いとのことです．また，素子の小型化にも向いているそうです．

<img width="302" alt="スクリーンショット 2018-12-12 8.34.23.png" src="https://qiita-image-store.s3.amazonaws.com/0/320962/b3453b8a-7dce-3f80-3a77-88282b88993b.png">

2018年12月12日現在，打ち上げ予定日は2019年1月17日となっています．果たしてこのNBFPGAは従来のSRAM型FPGAに取って代わる存在になるのでしょうか？

# おわりに
ここまで稚拙な文章を読んでいただきありがとうございました．
まだまだ誤植・至らない点など多々あるかと思います．何かありましたら，コメントなどで教えていただけると幸いです．
時間があればコンフィグレーションチェーンの仕組みなどについても書いてみたいです．

[^1]: https://www.slideshare.net/shtaxxx/2015-10-11-pycon-pycoram
[^2]: https://www.amazon.co.jp/dp/B073TS4XFC/ref=dp-kindle-redirect?_encoding=UTF8&btkr=1
[^3]: http://www.kenkai.jaxa.jp/kakushin/index.html#about
[^4]: http://www.kenkai.jaxa.jp/kakushin/interview/01/interview03.html
[^5]: https://japan.xilinx.com/support/documentation/data_sheets/j_ds100.pdf
[^6]: https://japan.xilinx.com/support/documentation/user_guides/j_ug190.pdf