なつたん

最近schemeを勉強していて思ったこと。
「関数型言語をそのまま論理合成できたらおもしろくない？」

ASIC/FPGAの信号処理の開発は、
①処理のアルゴリムを数式で書く
②アルゴリズムをC言語に書き直す。（C言語でテストを行う）
③RTLへ変換する。

の3段階が主流です。RTLの後もいろいろあるのですが、VerilogなりVHDLまで行ってしまえば、あとは枯れた技術なので何も手を入れる必要がない。SystemCとかは②と③の間全体を受け持ち、高位合成ツールというのは②から自動的に③を作る。ざっくりいうとそんな感じ。

①から②の本質は、逐次処理の追加である。
16個のある値を足す処理を考えると、①の段階では、y = Σni (1 <= i <= 16)　のような表現になり、ここに時間の概念はない。一般的なプロセッサは同時に処理ができないので、C言語でこの数式を表すと、このようになる。

int i;

int sum;

sum = 0;

for(i = 0:i < 16; i++) {

	sum += n[i];

}

同時に1からNまで足せないので、順番を与えて一回ずつ足している。

②から③の本質は、並列性の追加である。ループになっているところを、パイプライン化する、もしくは依存関係の無い演算を展開して一気に処理をする。Verilogだと、

always @ (posedge clk) begin
	sum1 <= n1 + n2 + n3 + n4;
	sum2 <= n5 + n6 + n7 + n8;
	sum3 <= n9 + n10 + n11 + n12;
	sum4 <= n13 + n14 + n15 + n16;
	sum_all <= sum1 + sum2 + sum3 + sum4
end

こんな感じで記述すれば、加算器5個で、レイテンシ2clkで、1clk毎に計算結果が出せる。加算器を1個にして、16CLKかけて計算することも可能だ。このあたりは、bit幅と加算器のコストのトレードオフで選択できるようになっている。 もちろん

always @ (posedge clk) begin
	sum_all <= n1 + n2 + n3 + n4 + ・・・・　 + n16;
end

と書けば、1clkで計算可能だ。RTLレベルまで落とすことで、逐次処理を取り除いて、結果的に高速化を図る。RTLレベルになれば、一度に好きなだけの演算ができる。

もう一回整理。
①→②で逐次性を追加して、②→③で逐次処理を取り除く。②の処理ってもしかして無駄？

図で書くとこんな感じ。

話を関数型言語で考えてみる。関数型言語というのは、いわいるy=f(x)のような写像を元にプログラムを組み立てる。ある入力に対して一意の出力があるような、そんなシステムだ。実際には、写像だけでは処理しにくいので、状態を表せるような仕組みも持っている。
もし、①のアルゴリズムが関数型言語で表現できるなら、ASIC/FPGA化は簡単にできる気がする。本質的に、y=f(x)というのは単なる組み合わせ回路だ。そして、状態を表すのにフリップフロップが使える。再帰関数が、末尾最適化されているなら、計算の結果を特定のフリップフロップに上書きし続ければ、そのまま計算できる。

で、僕が思いついたフローはこれ。
①処理のアルゴリムを数式で書く
②'アルゴリズムを関数型言語で書き下ろす。
③RTLへ変換する。

図で書くとこんな感じ。

いったんC言語にするより、もっと直感的にRTLへ変換できると思う。

最上の日々の方に、もっとわかりやすく書いてあります。CPUに命令を追加するのではなく、CPUに相当するものを毎回作るところが違うけど。