« AVM3.0 | Main | 関数型言語で高位合成を その2 »

2007.05.20

関数型言語で高位合成を

最近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に相当するものを毎回作るところが違うけど。

|

« AVM3.0 | Main | 関数型言語で高位合成を その2 »

Comments

ううむ...いにしえの sfl を思い出すのは
私だけでしょうか...
http://easter.kuee.kyoto-u.ac.jp/parthenon/NTT/index_j.htm
ああっ...黙っとくことにしてたのでした...

Posted by: noboshemon | 2007.05.20 at 07:50 PM

noboshemonさん、こんにちは。

おおっ、こんな言語があったなんて。

http://easter.kuee.kyoto-u.ac.jp/parthenon/NTT/sfl/cpu.sfl
このファイルを見ると、全体的にはVHDLっぽいかな。

else : par {
relay if.ift() ;
any {
op1 == LDAI : a := op2 ;
op1 == LDAX : a := memory_read(x).dti ;
op1 == STAX : memory_write(x,a) ;

こういう記述を見ていると、イメージは近いです。

Posted by: なつたん | 2007.05.22 at 11:19 PM

Post a comment



(Not displayed with comment.)




TrackBack

TrackBack URL for this entry:
http://app.cocolog-nifty.com/t/trackback/18154/15138062

Listed below are links to weblogs that reference 関数型言語で高位合成を:

« AVM3.0 | Main | 関数型言語で高位合成を その2 »