![実現コード
1入力 1出力の送るだけのノード
※ Verilog HDLで記述した試作段階のもの
module throughNode(
input clk, // クロック
input reset, // RESET信号
output inReceived, // READY信号
input [bitLen:0] inToken,
// トークンの入力信号
// MSBは制御信号（PROBE）
// receive token
always @(negedge clk or posedge reset) begin
if (reset)
inBuf <= 0;
else if (inToken[bitLen])
// if input is available, set inBuf
inBuf <= inToken;
15
// MSBは制御信号（PROBE）
input outReceived, // READY信号
output [bitLen:0] outToken
// トークンの出力信号
// MSBは制御信号（PROBE）
);
// parameter def
parameter bitLen = 16; // トークンのbit長
reg [bitLen:0] inBuf = 0; // 入力バッファ
assign inReceived = inBuf[bitLen];
reg [bitLen:0] outBuf = 0; // 出力バッファ
assign outToken = outBuf;
inBuf <= inToken;
else if (inBuf[bitLen] && outBuf[bitLen])
// inToken already copied to outBuf
inBuf[bitLen] <= 1'b0;
end
// send token
....
endmodule](https://image.slidesharecdn.com/130831fpgax3yos-130831131131-phpapp01/85/130831-fpgax3-yos-15-320.jpg)
![そして難題 “エラトステネスの篩”
当然、素数列を計算したくなる
Haskellで書くとこんな感じ
primes = sieve [2..]
sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
DFNで考えると、sieveの再帰呼び出しの分だけノ
ードが必要となり、動的にDFNを拡張できる仕組みードが必要となり、動的にDFNを拡張できる仕組み
が必要となる
? ここで、“データフローマシンっぽい” の限界にぶつかる
? DFNを動的に生成できる仕組みを作らねば...
次回のテーマ !!
19](https://image.slidesharecdn.com/130831fpgax3yos-130831131131-phpapp01/85/130831-fpgax3-yos-19-320.jpg)
130831 fpgax3 yos
- 1. FPGAでデータフローマシンっぽい もんを作ったで!! 2013/8/31 FPGAエクストリーム?コンピューティング第3回 今回は大阪だ！ 大阪大学大阪大学 吉田 幹（@kibayos） BBR / PIAX Inc.
- 2. 前回（第2回）は、FPGAはエアでしたが、今回は、 DE0（Cyclone III）で動く回路を書きました 前回、「異形の論理型言語」と難解な話をしてしまっ たので、今回はデータフローマシンという親しみあ る（?）テーマでトライしてみました 相変わらず、非ノイマンの前提です相変わらず、非ノイマンの前提です FPGAがソフトCPUコアやハードCPUコアを持っていたとし ても、CPUの助けは借りないぞ !! マシンを作るといっても、マイクロコードでエミュレートはし ない前提。どこまでも非ノイマンなマシンが前提だぁ !! （単なる意地です。いつまで続くかは本人も知りません） 2
- 4. 簡単な例 華氏->摂氏 摂氏=(5 / 9) * (華氏 - 32) - / * 5 9 32 華氏華氏華氏華氏 摂氏摂氏摂氏摂氏 4 32 +1 m 自然数の列自然数の列自然数の列自然数の列1 自然数の列 “m” (merge) は来たトークンを順次出力するノード 無限に自然数の列が生成される
- 5. 簡単な例 華氏->摂氏 摂氏=(5 / 9) * (華氏 - 32) - / * 5 9 32 華氏華氏華氏華氏 摂氏摂氏摂氏摂氏 5 32 +1 m 自然数の列自然数の列自然数の列自然数の列1 自然数の列 “m” (merge) は来たトークンを順次出力するノード 無限に自然数の列が生成される 1
- 6. 簡単な例 華氏->摂氏 摂氏=(5 / 9) * (華氏 - 32) - / * 5 9 32 華氏華氏華氏華氏 摂氏摂氏摂氏摂氏 6 32 +1 m 自然数の列自然数の列自然数の列自然数の列1 自然数の列 “m” (merge) は来たトークンを順次出力するノード 無限に自然数の列が生成される 1 1
- 7. 簡単な例 華氏->摂氏 摂氏=(5 / 9) * (華氏 - 32) - / * 5 9 32 華氏華氏華氏華氏 摂氏摂氏摂氏摂氏 7 32 +1 m 自然数の列自然数の列自然数の列自然数の列1 自然数の列 “m” (merge) は来たトークンを順次出力するノード 無限に自然数の列が生成される 1 2
- 8. 簡単な例 華氏->摂氏 摂氏=(5 / 9) * (華氏 - 32) - / * 5 9 32 華氏華氏華氏華氏 摂氏摂氏摂氏摂氏 8 32 +1 m 自然数の列自然数の列自然数の列自然数の列1 自然数の列 “m” (merge) は来たトークンを順次出力するノード 無限に自然数の列が生成される 2 1 2
- 9. ノードとその種類(1) ノード （一般形） n入力 m出力 n引数の関数（operation） 発火の条件はまちまち 同期型： n入力のトークンの すべてが揃った時点で発火 非同期型： n入力のどれか operation n input m output ??? ??? 非同期型： n入力のどれか のトークンが来た時点で発火 mix型： 発火の条件が個別に定義される 出力の仕方もいろいろ 同報型： 発火によって得た計算結果を m出力すべてに流す 選択型： 発火によって得た結果から、適切な出力を選んで流す ※ノードの定義方法は他にもたくさんあります。ここでは発火の段数が小さくなる方法を 選びました 9
- 10. ノードとその種類(2) 算術演算 論理演算、関係演算 - / mod+1 -1 + * 10 その他 <== <=not and or m sel T/F T F merge selector sw T/F T F switch in input out output sink sink dup duplicate
- 11. 今回対象としたデータフローマシン 任意のDFNをロードできるデータフローマシンでは なく、回路として与えたDFNだけが動く簡単なもの 試作目的 本当なら “データフローマシン” と言えるものではなく、 “データフローマシンっぽいもの” 扱えるデータ型はbooleanと整数に限定扱えるデータ型はbooleanと整数に限定 整数は任意のbit数（但し、固定長） リンクに乗るトークンの数は高々1つ 回路合成をやりやすくするため（ FIFOを使わなくて済む ので） ストリーム計算を主に考える 型は整数に限るので、無限の整数列を扱った計算 11
- 12. ストリーム計算を選んだ理由(1) データフロー言語との相性 Lucid（1976年に生まれたデータフロー言語）はストリー ム計算を得意とし、次のようなサンプルもある total where total = 0 fby total + x end x に数列（ストリーム）を与えると、その合計（total）をストリームと して出力する 与えるストリームを止めると、結果のストリームも止まり、 関数型言語の遅延評価のような振る舞いをする 関数型言語との関係性を調べたい 特に、リスト（無限でもよい）を扱うプログラムについて。 DFNに変換可能かどうか 12
- 13. ストリーム計算を選んだ理由(2) ストリーム版 Map/Reduce 連続的に入ってくるストリームをパイプライン的に処理す る Map/Reduce 連続的に結果を返してもよいし、EOS（end of stream）を 区切りのタイミングとして結果を返してもよい Reduceでよく使う以下の集約関数はストリーム処理が可Reduce 能 => 有効性は高い min, max, total, average, median（中央値）, variance（分散） 13
- 14. 回路をどう実現するか ノードはモジュール（Verilog HDLのmodule）として リンクは、モジュールのポート間をつなぐ信号線（wire） ノード間のトークンの移動は、モジュール間の信号のやりと りに。但し、ハンドシェークが必要 node A node B 14 READY STROBE DATA module A module B READY STROBE DATA 〈〈〈〈タイミングチャートタイミングチャートタイミングチャートタイミングチャート〉〉〉〉 node A node B token
- 15. 実現コード 1入力 1出力の送るだけのノード ※ Verilog HDLで記述した試作段階のもの module throughNode( input clk, // クロック input reset, // RESET信号 output inReceived, // READY信号 input [bitLen:0] inToken, // トークンの入力信号 // MSBは制御信号（PROBE） // receive token always @(negedge clk or posedge reset) begin if (reset) inBuf <= 0; else if (inToken[bitLen]) // if input is available, set inBuf inBuf <= inToken; 15 // MSBは制御信号（PROBE） input outReceived, // READY信号 output [bitLen:0] outToken // トークンの出力信号 // MSBは制御信号（PROBE） ); // parameter def parameter bitLen = 16; // トークンのbit長 reg [bitLen:0] inBuf = 0; // 入力バッファ assign inReceived = inBuf[bitLen]; reg [bitLen:0] outBuf = 0; // 出力バッファ assign outToken = outBuf; inBuf <= inToken; else if (inBuf[bitLen] && outBuf[bitLen]) // inToken already copied to outBuf inBuf[bitLen] <= 1'b0; end // send token .... endmodule
- 16. 早速、DFNの合成をやってみた 自然数の列を出力するDFNと、totalを実現する DFNを作って、両者をつなぐ Σ(i=1..n)i の列を計算するDFNになる 1,3,6,10,... と順に合計列が出力される（めでたし） +1 16 total where total = 0 fby total + x end m1 + m0 自然数の列を自然数の列を自然数の列を自然数の列を totalの入力の入力の入力の入力x に入れるに入れるに入れるに入れる total Σ(i=1..n)i の列
- 17. みんな大好きフィボナッチ数列 フィボナッチ数列 n項目のfib(n) はお馴染みの定義 fib(1) = fib(2) = 1 fib(n+2) = fib(n) + fib(n+1) 数列なので、1,1,2,3,5,8,... と無限に続く Haskellで書くとこんな感じHaskellで書くとこんな感じ fibs = 1 : 1 : zipWith (+) fibs (tail fibs) zipWith は2つのリストを貼りあわせて新しいリストを作る関数 fibs はフィボナッチ数列の無限リストを返す 遅延評価がうまく実装されていないと再帰呼び出しが爆 発する（データフローにとっては、よい例） これを定義そのままの意味を使って、DFNにする 17
- 19. そして難題 “エラトステネスの篩” 当然、素数列を計算したくなる Haskellで書くとこんな感じ primes = sieve [2..] sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] DFNで考えると、sieveの再帰呼び出しの分だけノ ードが必要となり、動的にDFNを拡張できる仕組みードが必要となり、動的にDFNを拡張できる仕組み が必要となる ? ここで、“データフローマシンっぽい” の限界にぶつかる ? DFNを動的に生成できる仕組みを作らねば... 次回のテーマ !! 19
- 20. “エラトステネスの篩”のDFN sieveに対応する モジュール#1 2以上の整数列 2, 3, 4, 5, ... 素数列素数列素数列素数列 2, 3, 5, 7, ... sieveに対応する モジュール#2 sieveに対応する モジュール#n <ストリーム処理ノード> 20 car/cdr cons del dup head tail head tail head car/cdr tail stream cons head tail stream del element stream stream <ストリーム処理ノード> element 指定されたelementを streamから削除する
- 21. ご清聴ありがとうございました