• このエントリーをはてなブックマークに追加

今なら、継続入会で月額会員費が1ヶ月分無料!

記事 2件
  • 【週末Hack】30分で作る自作1024コアCPU千里1号 / shi3z

    2014-06-15 10:05  
    100pt
     おはよう。shi3zだ。 昨夜はヨネちゃんこと関西大学米澤ゼミの合宿に顔を出して、午後からは五反田のゲンロンカフェでノンプログラマー・プログラミング講座があるのでとんぼがえりするわけなんだけど、昨日はBrainf**k専用CPU、64コアのウルフラムルール90専用CPUとふたつのCPUを作ったわけなんだけど、もうここまで来たら、 64コアとかセコいこと言ってる場合じゃないでしょ! というわけで、一気に1024コアのCPUを作ってみることにした。 今回からせっかく作るCPUには名前を付けようと思い、いろいろ考えた結果、千里1号
     と名付けることにした。チサトだよ。センリじゃないよ。格好わるいフラれかたではなく、千の里(コア)を持つマシン、ということでこの名前にしてみた。 しかし一度慣れてしまうと Velirog HDLは実に簡単だ。 こんなに簡単でいいのか?ほんとに?と思ってしまう。 JavaとかSwiftのように、フレームワークに頼らない(頼れない)言語なので、ロジックを書くことだけに集中できる。 さて、今回作る1024コアCPUのお題は、なんといってもセル・オートマトンだ。 ただし今度は1次元ではなく、2次元のセル・オートマトンにしよう。しかも、30分以内につくる。 そう。コンウェイのゲーム・オブ・ライフ、通称「ライフゲーム」である。 これを実装することにより、チューリング完全なCPUをものにできるということになる。やったぜ、バンザイ! 念のために説明すると、チューリング完全とは、数学的には完全な計算能力を持ったコンピュータであることを意味する。まあ厳密にはBrainf**kもチューリング完全ではあるんだけど、プログラムが面倒だし地味だ。その点、ライフゲームはなにより見た目が面白いという特典がついている。こいつはでかいぜ。 というわけでさっそく秒速でライフゲーム専用CPUを作ろう! つうても、作り方はウルフラムルール90のセルオートマトンと基本的には同じだ。 繋ぎかたが複雑になるだけ いつものように、全てはenchantMOONでスケッチするところから始まる。
     他の人はどうだか知らないが、僕は新しいものをつくるとき、こういうスケッチを少しでも書かないと頭のなかでイメージを固められない。 つってもこれは簡単だ。アホみたいに簡単だ。 ライフゲームなので、あるセルの周囲8近傍からの情報を入力し、入力された情報をもとに次の状態を決定する。 ひとつひとつのコアは相変わらず1ビットCPUそのものだ。 ltとかrtとかは、それぞれLeft、Right、Top、Center、Middle、Bottomの頭文字で、二文字の組み合わせでどちら側の近傍なのか決めている。 この回路が正しいのかどうか検証するため、いきなり1024コア書くのは疲れそうなので、とりあえず3x3の9コアで試してみる。 ここは地道な手作業だ。 これで実際にシミュレーションしてみると・・・ ほほう。 これはブリンカーパターンといって、縦と横に点滅を繰り返す。 これが動くということは、ライフゲームが正常に動作しているということだ。YES! あとはこれを32x32=1024コアに拡張するだけなのだが、こんなの手作業でやっていたら頭がおかしくなる。 そこで、@duxcaが作ってくれたaltjsdo.itを使って1024コアを生成する部分を自動的にコーディングすることにする。 このaltjsdo.it、悔しいがプロトタイピング環境としてはcode.9leapよりも良く出来てる。オフラインで動くし。 こいつのソースはここ→http://goo.gl/Nb6CbO URLだけというのが実にニクい。 これによって自動的に生成された可愛いCPUコアちゃんたち、その数1024個 さあこれを実行だ!果たしてちゃんと動くのか・・・ うごいてる!当然のようにグライダーパターンが右上から左下へダーッと移動しとる! OMG!これぞチューリング完全マシン! ここまでのプログラミングにかかった時間は28分ジャスト。 可愛いよ!可愛いよ!千里ちゃん! というわけで例によって完全なソースコードは以下 
  • 【週末Hack】経験ゼロからVerilog HDLでBrainf**k専用CPUを自作してみた / shi3z

    2014-06-14 13:49  
    100pt
     気がつくと嵐のようなウィークデーが終わり、週末になった。 前々から週末に試してみようと思っていたのは、FPGAによるオリジナルCPU作り。 FPGAって敷居が高そう・・・と思っていたのだが、トグサ秋月によると、べつにへーちゃらだということで、せっかくなので週末を利用して挑戦してみた。 今回使ったのはAltera DE0というFPGA評価キットで、入門のための一通りの機能が揃って1万5千円と安い。しかし、最終的に、VerilogHDLでCPUを作ってみるというだけなら、フリーソフトのエミュレータだけでも気分は存分に味わうことが出来る。 そもそも僕はトグサ秋月と違ってFPGA歴0秒なので、まず基本からしてよくわからん。大学は二回入学したが二回とも中退したしな。  FPGAとはなんなのかと言うと、Field Pragramable Gate Arrayの略で、これだけ読んでもよくわからんが、要はあとから書き換え可能な電子回路のこと。 ひらたくいえば、プログラムを書くような感覚で、電子回路の中身をガシガシ変更したり出来ちゃうというわけだ。こないだハワイのプロセッサ学会に行った時に、「これからのCPUはFPGAを内蔵してアルゴリズムに最適化した回路を動的に生成するようになる」という話を聞いてキョーミを持ったのよ。 このFPGAへの回路の焼き込みは拍子抜けするくらい簡単で、HDLというモノを使ってプログラムのようなものを書くと、USBでホゲッと転送できてしまう。 んで、HDLってなんぞや、というと、Hardware Description Language(ハードウェア記述言語)のことのよう。 そう聞くとなにやら難しいんじゃないの?という気がするが、いざやってみるとなんのこたぁない。ちよっと癖のある並列プログラミング言語のようなものだ。 論理回路だのフリップフロップだの、ちょいとプログラミング用語にはあまり出てこないような言葉も出ては来るが、論理回路は単なる論理演算(AND, OR ,XOR, NOT)に過ぎないし、フリップフロップは論理回路を組み合わせた記憶装置に過ぎない。 簡単に言えば、これを組み合わせるとコンピュータができあがるわけだが、まずとっかかりがないと全く、ぜんぜん、見当もつかない。 HDLにはいくつかあるらしいが、メジャーなのはVerilog HDLとVHDLというやつらしい。 僕は入門書に従ってVerilog HDLを勉強してみることにした。 そこでとりあえずCQ出版の入門書を読んでみた。本そのものは高価だが、読みやすく解りやすい。秒速で7セグメントLEDを使ったタイマーまで作れるようになった。所要時間は2時間くらい。ラクショーだ。 さて、まあタイマーくらいまで作れたら次はCPUに挑戦しよう。VGAもちょっと遊んでみたいが、またの機会でいいや。 とりあえずハードで動くのは解ったので、シミュレータでCPU作ればいいや。ということで、新幹線に飛び乗る直前まで家でIcalus-Verilogをインストールした。フリーソフトでこんな楽しいことができるとはねー とはいえ・・・とはいえですよ。 いきなりCPUを作ろうとしても、時計を作るのとはワケが違う。 どうすれば作れるんだ??? とりあえず、教科書にROMとRAMのプログラムが載っていた・・・が・・・ ROMがCASE文!? こういうのでいいのか?・・・・こういうので RAMが配列!?(のようなそうでもないような) always文は、続く括弧内のシグナルを検出したときに動作する順序回路を記述する。 この場合、clk(クロック)に同期して、かつ、続くif文でweが1(1'b1は1ビットの2進数で1という意味)のとき、mem[adr]にwdataを書き込むということになる。あくまで動くタイミングはmodule RAMのところではなくて、clkが変化したとき、というのがポイント。 プログラムではなく回路なのだ。 assign文は、組み合わせ回路を定義する。adr(アドレス)に応じたmemの内容をただrdataに返すだけだ。とてもシンプル。 しかしこれ、なまじのプログラミング言語よりも簡単なんじゃないか? 本当にこれで回路になるのか!? 一応このモジュールを解説すると 入力はCLK(クロック)、ADR(アドレス/8ビット)、WDATA(書き込むデータ/8ビット)、WE(書込みON/1ビット)があり、出力はRDATA(読込みデータ/8ビット)のみ。 使い方としては、書き込む時にはWEをオンにしてADRとWDATAを設定する。 読み込む時にはWEをオフにしてADRを設定すると、RDATAにデータが返ってくる・・・ハズだ。 しかしこんなに簡単でいいのか・・・?? 一抹の不安を感じつつテストプログラムを書いてみる。 さてさて・・・ こんな簡単なモジュールで本当にRAMとして機能するのだろうか・・・ こ、こいつ・・・動くぞ。 解り辛いと思うが、@monitorというマクロを使うと信号に変化があったときだけprintf的なことをしてくれるという超絶便利な関数だ。 一番左は経過時間だ。10から35で書込みを行い、40から60で読込みを行っている。 書込まれるタイミングがズレるのは、書き込むタイミングがクロックに同期しているからだ。 ちなみにgtkというツールを使うともっとグラフィカルに確認することもできる。 xxは不定。 メモリを初期化せずにいきなり使っているので最初はxxが一杯でてくる ちなみにクロックに同期しない非同期なRAMの場合は、以下のようになる ポイントはalways文の中でposedgeをclk(クロック)に同期させるのではなくwe(書込みフラグ)に同期させている点。これでも正しく動く。 さて、RAMが実装できたら次はCPUだ。 今回は命令セットを考えるのが嫌だったのでBrainf**kを使うことにした。 なにしろ6命令だけ実装すればいいから簡単だ。 しかもHello Worldを出力するのに入力はいらないから5命令の実装でいい。 まずはマシン語を設計する。 通常のBrainf**Kでは<>+-.,という記号を使うが、これらの命令を数値化しなくてはならない。頭から0,1,2,3・・・と割り振っても良かったんだけど、一応可読性も意識してこんな感じにしてみた。 AF・・・アドレス・フォワード、AB・・・アドレス・バックワード、AC・・・Add Count、DC・・・Decliment Count、0C・・・アウトプット(0だけどオーとも読める)カウント、C0・・・適当(今回使わない)、F0・・・フォワード、0F・・・F0に対応するモノ みたいなイメージだ。 ところで、Brainf**kのHelloWorldが以下のような感じなのはあまりにも有名 これをハンドアセンブルしてもいいんだけど、馬鹿馬鹿しいので自動化したい。 単なるテキスト処理だから何で書いてもいいんだけど、JavaScriptに毒されているのでcode.9leap.netでサクッと作ってみた。 まあこの処理は舐めきってる。アセンブラに謝れ、という気がしないでもないが ただしここで問題が起きた。 Brainf**kの二つしかないジャンプ命令である[と]、つまり今回のCPUではF0と0Fに割り当てられている命令が、意外と高度なのだ。意外と高度というのは、「対応する括弧にジャンプ」というところで、「対応する括弧」というのがなんなのか、プログラムの時点ではわからない。 これをalwaysで直接記述しようとすると、まあ無理ゲーなのだ。 実際にやろうと思えば、かなり回りくどい方法になるが、次の括弧を検索するモードに変更して、クロックを消費して次の括弧を検索するのだと思うが、そんな馬鹿馬鹿しいことをやるCPUなんて聞いたことがない。 むしろそんなことをやらされるCPUが可哀想である。 普通のマシン語では、ジャンプ命令はジャンプ先が直接アドレスで書かれている。かなりマヌケなコードであっても、ジャンプ先は1命令サイクル内でわかるようになっている。そうでなければおかしいのだ。しかしBrainf**kを直接実行させようとすると、本来CPUがやらないようなことまでやらされてしまうのだ。そうだ。思い出した。よく考えたらBrainf**kは立派な高級言語なのだ。 そのとき、僕の脳裏を某教授の言葉がよぎった。手抜きと妥協は真摯の嗜み! いろいろ考えたが、新幹線が名古屋を通過してしまったのでこのままでは京都までに完成しない! しかたないので、アセンブル時にF0と0Fのジャンプ先アドレスを先計算して入れてしまうことにした。 命令がF0と0Fの場合だけ、直後の1バイトにはジャンプ先が入っているという感じにしたのである。 そもそもBrainf**kにはオペランドがないので命令の長さがそこだけ変わってしまうが、ここは目をつむる! さて、CPUだ。 なんとびっくり。CPUの回路構造は、ROMとそれと少し似ている。 つまり、クロックに同期して命令を読込み、読み込んだ命令に応じて別々の処理が走るだけだ。 とはいえ、ROMよりは若干複雑だ。 とりあえずモジュールの冒頭部分だけ書き出す  おお、どこが簡単なんだ責任者でてこい、と思ってしまうかもしれないが、単に入力と出力が多いから必然的にこうなってしまうだけである。 このCPUの回路図はこんな感じ clkはクロック、rstはリセット、で、romDataとromData2はROMからのデータ読み出しをしてる。今回、手抜き迅速な開発を行うため、F0と0Fの後ろにジャンプ先アドレスを付けたはいいが、途中まで作っていたのが完全に8ビットでデータをやりとりするコードのため、もう面倒だから手早く開発するために、通常のアドレスから読み込むromDataと、その次のデータが入って来るromData2をromに接続している。図には書き忘れた省略されているが、romAdrでromの何番地から読むのか決めている。 今回はプログラム内蔵方式であるものの、プログラムの本体はROMに書き込まれるタイプのCPUにしてみた。まあそのほうが簡単だから。 そしてメインはalways文による順列回路だ。といっても、これはJavaScriptのコードなの?と思ってしまうくらい簡単だ。 RAMがクロック同期なので、書込みに1クロック待たないとならない。そこで冒頭のc_clkで全体を実クロックの半分のクロック周波数で動くようにしている。 次に、romDataには実行すべき命令が入っているはずなので、これをcase文で処理する。 AF(>)、AB(<)、AC(+),DC(-0)は拍子抜けするくらい簡単だ。 問題のF0([)、0F(])も、romData2にひとつ先のデータが入って来ているのでcnt(プログラムカウンタ)にジャンプ先を代入するだけだ。-1してるのは、直後にcntがインクリメントされているからで、これもまあ手抜き手早く実装するための工夫だ。 今回つくったBrainf**k専用コンピュータの全体像は下図のような感じ 唯一の出力命令である0C(.)はffOUTに出力するようになっている。 データを出力するタイミングでoutSignalもオンにしてる。  こんな感じでテストしてみると・・・ やったぜ! Hello World! 僕の予定では二日から1週間くらいかかりそうだったんだけど、数時間で作れてしまった。 ということでVerilog HDLとFGPA、たまの週末に遊ぶにはなかなかいいオモチャでした。 完全なソースコードは以下から ※ただし、短時間で結果を出すため相当汚いコードになってるので上記記事を参考に自分で作ってみるのもいいよ!