FPGAの原理と構成を読んだ - xiangze's sparse blog

FPGAブームが来ています*1 。

最近年を追うごとにFPGAに関する書籍やネット上の情報が多くなり、またC言語ベースでの高位合成技術の進展やLinuxベースのシステムが作られ、FPGAはソフトウェア開発者にとっての敷居が低く使いやすくなってきています。しかし入手できる情報は特定のベンダーの製品、ツールの使用を想定した実践的なものが多く、中立的立場からFPGAの内部構成や動作する原理について解説した日本語の本はほとんど見当たりませんでした。
「FPGAの原理と構成」はそのような意味で他にはない、この本にしか載っていない事柄の多い本になっています。

FPGAの原理と構成

shop.ohmsha.co.jp

1章 FPGAを理解するための基本事項
2章 FPGAの概要
3章 FPGAの構成
4章設計フローとツール
5章設計技術
6章ハードウェアアルゴリズム
7章 PLD/FPGAの応用事例
8章新しいデバイス，アーキテクチャ
その他の本
Link

1章 FPGAを理解するための基本事項

最初にデジタル回路の非常に基本的なこと(重要)が書かれたあとFPGAブーム？が来ている理由とそれに至る歴史に多くのページが割かれています。集積度、消費電力、動作速度の3つのお得が享受できるムーアの法則の減速に伴って、何度でも書き込みが出来かつノイマン型アーキテクチャにとらわれないFPGAが注目されています。
FPGA業界の歴史は寡占化の歴史でもありました。大手2社の成長と他社の参入断念の歴史のようです。1980年代の今で言うファンダリの観点からの日本企業の参入と2000年代前半の特許切れに伴う新しいアーキテクチャを提唱したベンチャー企業の参入が興味深かったです*2。ここ数年ではFPGAの枠を超えた買収、提携が進んでいるそうです。

2章 FPGAの概要

主要な構成要素として

論理要素
入出力要素
配線要素
その他(回路情報書き込み用回路:コンフィギュレーションチェーン、クロックネットワーク、テスト用回路、メモリ、ハードマクロ)

の説明がされています。

このうち配線要素はツールによって自動で配線がされ、使用者は直接意識することはありません。

CPU,GPUと同じく計算はCMOS FETによるデジタル回路で行われることに変わりはなく、計算の部分はもはや半導体の物理的特性に直接依存しないのですが、記憶部分と演算部分が混在しているFPGAの特長から記憶素子とSRAM(揮発性),Flash(不揮発性)、ヒューズ(一回だけ書き込み可能なRAM)を回路情報の記録に使っていてその特徴がFPGAデバイスとしての特徴にもなります。

色々な情報がコピーされうる現代においてヒューズで書かれた情報は外部から読み取ることが非常に困難になるというのは興味深いです。

組み合わせ回路だけが並んだデバイス(PLA)であれば回路情報を作成するのは真理値表をAND,OR回路で実現するだけなので比較的簡単ですが、現代のFPGAでは論理要素はLUT(Look Up Table)とレジスタを使って実現されており、これにプログラマーが回路情報を割り当てるのは複雑な行程で5章で解説されています。

Xilinxのデバイスでは論理要素用のLUTがメモリにも転用出来るようになっているという特許(1994年 US5343406)、シフトレジスタも構成できるという特許(US5889413)といった本質的な情報が回路図で紹介されていてためになります。

3章 FPGAの構成

テーマ的には論理要素, 入出力要素, 配線要素, その他(ハードマクロ)と2章とよく似たことについて書かれているのですが、
論理要素の実現手段であるLUTはデバイスによって違いがあること、配線要素部分の回路構成が図を交えて非常に細かく説明されています。

素朴に論理要素を建物、配線要素を道路と考えると都市に高速道路、一般道、路地があるように配線要素も階層的になっていた方が効率的な情報の移動が実現できそうです。実際昔のFPGAはそうなっていたそうなのですが、製造プロセスの進展に伴い配線の遅延とばらつきの影響が増大してきた現代においてはあまり使われないそうです。

CPU,GPUと同じく集積化による周辺回路の取り込み(ハードマクロ化)が進んでいます。数値計算的な回路をHDLで記述した場合FPGA内部のDSPが自動で割り当てられることが多いです。

ハードマクロの中でもPLL(Phase Locked Loop),DLL(Delay Locked Loop)について少し詳しく説明されています。PLLは基本的構成は単純ですがそれだけで本が書けるほど奥深く、プロセスに応じた設計が難しいそうです。FPGAでは既にある回路に合成ソフトウェアでパラメータを設定するだけになっていて使う人にとっては簡単ですが中の人の多大な努力があるはずです。PLL,DLLを他のIPとは別扱いで取り上げた理由はクロックを生成することは動作に不可欠で歴史的に最初にFPGAに搭載されたからではないか思います。

4章設計フローとツール

FPGAを使ってプログラミングする手順としては

HDLの記述によるプログラミング
シミュレーションによる動作検証
論理合成: HDLで書かれたコードを論理回路に変換する。
配置配線: 論理回路を特定のFPGAデバイス内のどの位置の論理要素を使用し、どのように配線要素でつなぐかの情報を作成する。
タイミング解析: 作成された回路の位置情報から要請される周波数で動作するかを解析する。動作しない場合には問題個所を表示する。
FPGAでの実機検証

となり、論理合成、配置配線、タイミング解析はベンダー提供のツールによって自動化されています。これの前にsystemCなどの言語によるHLS設計とそれをHDLに変換する高位合成、動作合成とその検証が入ることがあります。またソフトコア、ハードコアCPUにソフトウェアを書き込んで協調動作させる手順もあります。それが分かりやすくまとめられています(図4.1)

4章はこの本でもっとも実務的な部分でした。仕事でFPGAを使うことになった人はまずここに書かれているフローにしたがって作業することになると思います。手を動かしているだけでは面白くないので、なぜFPGAはうまく動くのか(うまく動かないときがあるのか)を知りたいと思ったらこの本の他の章を読むことになるのだと思います。

5章設計技術

4章で挙げられた自動化された配置配線がどのように行われているのかを解説しています。ASICと比べた場合のFPGA配置配線特有の処理としてデバイスに応じたLUTに回路情報をマッピングするテクノロジーマッピングとクラスタリングという行程が独立してあるそうです。

配置処理は最適化問題の例としても興味深く、シミュレーテッドアニーリングなどの方法が使われているそうです。コスト関数には配線の混雑さとタイミングが使われるそうです。配線処理も競合する部分がなくなるまで組み合わせを探索し続ける方法のようです*3。オープンソースの配置配線ツールVTRが紹介されています(https://github.com/verilog-to-routing/vtr-verilog-to-routing)。

FPGAにも消費電力を考慮したツールがあるそうです。

6章ハードウェアアルゴリズム

FPGAでは論理要素を自由に使えるようにする為に回路に冗長な部分があり、配置も最適化できません。
そのため動作周波数が専用のCPU,GPU回路に比べ遅くなってしまいます。普通にCPUを実装しただけでは製品としての優位性はありません(動作検証や個人的学習には意味があります)。
FPGAを使う理由、優位性を持つような計算は何かという疑問に対する答えがこの章に書かれています。

一般的なCPUではプログラムに従って計算を行うためにその読み出し回路、処理の分岐の判定、演算回路の処理の選択回路が必要になります。
またデータをランダムにメモリから読み出す為の回路(メモリ管理ユニット)とレーテンシーが存在します、
条件分岐がないか単純な動作に限定すればプログラムをロードする必要がなく、使うデータに規則性、局所性があれば複雑なメモリ管理ユニットは必要なくなります。同じような計算をたくさん行うのであれば並列性、パイプライン化による計算効率の向上も比較的単純な構造が並んでいるFPGAにとっては有利です。
そのような計算を実現するものとして本章ではまず計算機の色々なアーキテクチャが挙げられています。

SIMD,MIMDのような分類をFlynnの分類と言うそうで、その他に計算要素(PE)を2次元的に並べたシストリックアレーや必要なデータが届き次第計算を行うというデータフローマシン、そしてストリーム処理といったものが挙げられています。そして特に構造が簡単で計算効率を高めやすいストリーム処理の例が紹介されています。
まずpoission方程式
$\Delta \phi=f$
を逆行列として逐次的に解くような問題が挙げられています。poission方程式は流体や電磁場の計算の他に画像処理でも使われ応用範囲が広いです。
セルオートマトンはsaliency(顕著性)の検出で使われることがあるそうです*4。
ソーティングネットワークについても紹介されています*5。
その他BING(Binarized Normed Gradients)のような画像特徴量の計算は得意そうです*6
stencil computingのようなアーキテクチャで何かやる場合にはSystemCによる高位合成よりも HDLで直接書くかHalideやDarkroom *7のようなDSLを使うのが良さそうだと思いました(HalideはOpenCL->AlteraのFPGAというフローになると思います)。

ゲノムの相同性解析、配列の断片をつなぎ合わせて復元する処理(アセンブル)はデータ全体のサイズはギガバイト単位で巨大ですが、各時点で必要なデータの相対的位置は固定で局所性が高いのでストリーミング処理に向いています。簡単な編集距離の計算例が紹介されています。またゲノムは塩基の種類が4~5種類しかない為文字列として考えると簡潔データ構造の形式を使うと効率よく処理できます。FPGAでの実装も考えられているようです*8。7章でもゲノムシーケンサの紹介がされています。

7章 PLD/FPGAの応用事例

HPC(High Performance Computing)、科学技術計算の分野の事例が多く挙げられています。
多数のGPUを接続したスパコンでNvidiaのGPU同士のデータ通信の方法であるNVlinkが使えるようになる前にはGPU間のデータ転送でいったんCPUのメモリ領域にコピーしなければ行けなかったのですが、それを回避するようなデータ転送を行う為にFPGAを使ったそうです*9。
ルーターやスイッチなどのネットワークデバイスは高性能なFPGAの用途としてよく挙げられます。
パケットの解析に必要な情報をFPGA単体で保持し処理するのは難しいようで連想メモリ(CAM)やCPUと組み合わせた構成が一般的なようです。
金融業界では取引において低レーテンシーの処理の必要性が高くFPGAがよく使われているということ、また複雑な条件の金融商品の価格を計算するのに使われることもあるらしいのですが、計算に使う電気代とのトレードオフでデバイスを選択していてビットコインの採掘と共通するところがあります。
参考文献が非常に豊富に挙げられていて中でも機械学習関係、データベース関係の実装(memchached)

が個人的に興味深かったです。

本にはほとんど書かれていなかったのですが組み込み系、IoT、家電製品のような計算力はさほど必要とされないが電力効率などの面でシビアな分野でもFPGAは広まりつつあります。Zynqボードはそういった分野をターゲットにしているのだと思います。Xilinx,Alteraともに主にHPC向け(Vertex,Stratix)、組み込み向け(Spartan,Cyclone)と中間(Kintex,Arria)の製品ラインナップがあります。

8章新しいデバイス，アーキテクチャ

編者の方が提唱された疎粒度リコンフィギャブルアーキテクチャ(CGRA)が説明されています。動的再構成アーキテクチャ(DRP)は既に実用化され、家電製品に搭載されているそうです。

電子回路では消費電力低減のため回路の一部の電源供給やクロック供給を止める動作(ゲーティング)を行うことがあります。しかしFPGAでは回路の使い方を自由に変えられるという構成上、あるいは回路追加の負担が大きいという理由でゲーティングを行うのが困難な場合が多いです。
そこでモジュール間でクロックに同期したデータのやり取りをしないような回路構成(非同期FPGA)が紹介されています。その他しきい値電圧の違うトランジスタを用途のに応じて配置配線で割り当てる方法やフラッシュメモリなどの不揮発性メモリを回路に組み込んで省電力化を図る方法はFPGAらしいと思いました。

光ファイバーでの通信はボード単位では実用化されつつあるらしいのですが、FPGAに直接光インターフェースを取り入れる試みもあるらしいです。
ホログラムによる記録は現代のFPGAとはかけ離れていますが、メモリに近いところで計算を行うというコンセプトはFPGAに近いと思いました。

その他の本

CPUの基本的な構造については
パターソン、ヘネシー「コンピュータの構造と設計」

コンピュータの構成と設計第5版上

作者: ジョン・L.ヘネシー,デイビッド・A.パターソン,成田光彰
出版社/メーカー: 日経BP社
発売日: 2014/12/06
メディア: 単行本
この商品を含むブログ (1件) を見る

を読んで知りましたが、最近はより実践的にARMのアーキテクチャを解説した本が翻訳されたそうです。
mag.switch-science.com

system verilogのコードがすごい豊富です。
ヘネシー＆パターソンコンピュータアーキテクチャ第5版翻訳版ホームページ | Amano Lab
ヘネシー,パターソン「コンピュータアーキテクチャ」はパターソン、ヘネシーとは違う本だということをだいぶたってから気づき、またその内容の難しさからちゃんと読めてないです。"4章は特殊な業界用語とNVIDIAによるアーキテクチャの隠蔽作戦のために、ベールに包まれたＧＰＵのアーキテクチャを今までのアーキテクチャの中に位置づけている。"というのが気になります。

最内ループからはじめる深層学習(waifu2xの高速化)
こちらを読んでNvidiaのGPUもSIMD的な(正確にはSIMTらしい*10 )アーキテクチャなのだということを認識しました。

FPGAプログラミング大全 Xilinx編

http://www.shuwasystem.co.jp/products/7980html/4753.html
著者の方はXilinx, AlteraのFPGAプログラミングに関する本を多数出版されています。従来の本であったシミュレーションと波形ビューア、ロジックアナライザ(chipscope, signaltap)を用いたデバッグ、ソフトコアCPU(MicroBlaze, NIOS)の使用の他にといった定番開発主要に加え、XilinxのFPGAの新機能としてVivado HLSでの高位合成、ZYNQでのソフト、ハード協調開発について書かれているそうです。ZYNQではLinuxが動き、LinuxのデバイスとしてFPGA部分の回路を動かすことができ、よりソフトウェアエンジニアには親しみやすそうです。