GPGPUできるBrainfuckをCUDAで実装してみました。
このBrainfuckを使用すると、SIMDな並列演算を行うことができます。
並列演算用の命令を2つ追加してるので純粋なBrainf*ckではないですね、はい。
拡張命令
記号を2つ追加しました。
| 記号 | 説明 |
|---|---|
| { | 並列演算の開始.ポインタの指す要素分だけスレッドを用意 |
| } | 並列演算の終了 |
大雑把な説明
基本的に中括弧で囲まれた命令が並列実行されます。
＋＋＋｛＋ー＋｝＞． # 「+-+」が並列に実行されます
「｛」命令が実行されると、ポインタが指している要素の値分だけスレッドが用意されます。
↓ ＋＋＋｛＋ー＋｝＞． |→0|0|0|0| ↓ ＋＋＋｛＋ー＋｝＞． |→1|0|0|0| ↓ ＋＋＋｛＋ー＋｝＞． |→2|0|0|0| ↓ ＋＋＋｛＋ー＋｝＞． |→3|0|0|0| この場合3個のスレッドで実行するよ！
並列演算の実行時にスレッドが作られ、スレッドごとにメモリが用意されます。
このメモリはGPU上のメモリで、メインメモリからは独立してます（デバイスメモリ）。
メモリの先頭にはスレッドIDが格納されます。
スレッドIDとは「0〜スレッド数-1」の通し番号でスレッドを識別するものです。
↓ スレッドID=0 |→0|0| スレッドごとにメモリが用意される ↓ スレッドID=1 |→1|0| 先頭にはスレッドIDが格納 ↓ スレッドID=2 |→2|0| ＋ー＋｝
スレッドは並列に実行されます。
「｝」は終了マークです。
↓ スレッドID=0 |→0|0| ↓ スレッドID=1 |→1|0| ↓ スレッドID=2 |→2|0| ＋ー＋｝ ↓ スレッドID=0 |→1|0| ↓ スレッドID=1 |→2|0| ↓ スレッドID=2 |→3|0| ＋ー＋｝ ↓ スレッドID=0 |→0|0| ↓ スレッドID=1 |→1|0| ↓ スレッドID=2 |→2|0| ＋ー＋｝ ↓ スレッドID=0 |→1|0| ↓ スレッドID=1 |→2|0| ↓ スレッドID=2 |→3|0| ＋ー＋｝
命令は共通の領域に保存されていますが、スレッドごとに違う命令も実行できます。
↓ スレッドID=0 |4|7| こんな状況でもOK ↓ スレッドID=1 |5|8| ↓ スレッドID=2 |6|9| ＋＋＋
最終的にポインタが指している値をメインメモリにスレッドID順でコピーします。
↓ スレッドID=0 |→1|0| ↓ スレッドID=1 |→2|0| ↓ スレッドID=2 |→3|0| ＋ー＋｝ # 並列演算の終了後 ＋＋＋｛＋ー＋｝＞． |→3|1|2|3| スレッド数の後ろに結果(1,2,3)がコピーされる.
あとはよしなに結果を使います。
実行例
一応簡単なサンプルコードだけ。
CUDAを使っているので、実行するにはNVIDIAのグラフィックボードが必要になります。
1. abcと出力するプログラム。
3個のスレッド(ID=0, 1, 2)に対して、中括弧内で97(10*10-3, つまり'a')を足してます。
+++{>++++++++++[<++++++++++>-]<---}.>.>.>.
abc
2. 'a'〜'z'を表示するプログラム。
スレッドを26個用意→スレッドIDに'a'(97)を足す→出力。
>>+++[<+++++++++>-]<-{>>+++++++++[<++++++++++>-]<+++++++<[>+<-]>}[>.[-]<[->+<]>-]
内部、CUDA的なお話
疲れてきたので簡単な説明だけで許してくださいごめんなさい（ｵｲ。
というか途中でいろいろ面倒になって実装自体がアレな事になってます（ｵｲｵｲ。
スレッドブロックは1つしか使ってません。
スレッド数は(n, 1, 1)で実行されます。
// CUDAで例えるとこういうこと dim3 grid(1,1); dim3 block(n, 1, 1);
並列演算時のメモリはシェアードメモリです。
1次元配列ですが、2次元配列的に使ってます。
「スレッド数×スレッドあたりの最大メモリ(とりあえず32にしてある)」です。
メモリは縦に使っていきます。
0 1 2 … n-1 ←スレッドID ↓↓↓ 下向きに進んでいく |0|1|2|…|n-1| memory[threadId][0] |0|0|0|…| 0 | memory[threadId][1]
メモリを縦に使うことにした理由は、（繰り返しの命令（[ ]）がなければ）アクセスする要素が連続した場所になるため高速になるだろうと考えたからです。
（シェアードメモリでは関係ないかも）
ソースコード
githubに置いておきました。
もうギブハラ（Github・ハラスメント）も怖くない！
https://github.com/rubellum/cuda-brainfuck
