Android + OpenGLでMMD そのさん

Lat式ミク様を表示させるために，なにより目がないと怖いのでｗ　テクスチャマッピングを実装しました．さらに，マルチテクスチャでトゥーンレンダリングもなんとなくそれっぽくなるように実装しました．どうもレンダリング結果が一部微妙なので今後デバッグしますが，まずはソレっぽい出来なのでひと段落させます．

テクスチャ関連に関しては，完全に教科書どおりのコーディングになっています．

• glTexParameterxで，TEXTURE_WRAP_S/TをGL_REPEATに，GL_TEXTURE_MAG_FILTER/MIN_FILTERをGL_LINEARに設定
• glPixelStoreiでGL_UNPACK_ALIGNMENTに1を指定
• glGenTextures, glBindTexture, glTexImage2Dで用意したbitmapにtextureをbind
• glTexCoordPointerでテクスチャ座標バッファを指定．テクスチャ座標はPMDファイル中に記載されている
• GL_TEXTURE_2DをGL_ENABLEしてglTexEnvfでGL_REPLACEを指定，glBindTextureで貼り付けるtextureを選択
• glDrawElementsで描画

はまりポイントは以下の通り．

• MAG_FILTERにGL_LINEAR(多分バイリニア補完で拡大)を指定したつもりだが，どうもバイリニアになっていない気がする．ニアレストネイバーっぽい．まだ解決していない．
• glTexImage2Dで指定したGL_RGBのフォーマットは，RGB各8bitで順番はアドレスの若い方からR->G->Bの順．まぁ普通．
• GL_REPLACEしているのでライティングを無視している
• glGenTexturesは複数回呼び出しても良いっぽい

で，実はOpenGLの方ではあんましはまっていなくて，主にテクスチャファイルの読み出しではまっていました．

• BitmapFactoryで普通にファイル読み出すと，RGB556に変換されてしまう．前述のglTexImage2Dのフォーマットではない．BitmapFactory.Optionsで，inPreferredConfigにBitmap.Config.ARGB_8888を指定して読み込む．さらに，このままだと変な場所にアルファがあるので，適当にアルファ除いてバッファに書き込み．今考えると，アライメント指定するだけでも良かったかもしれぬ．
• 1回のnewで2M以上，全部で16M～32Mくらいのどこかで，メモリアロケーションが行えなくなる．android的な仕様？Lat式ミク様のテクスチャは余裕で1024x1024とかあってメモリから溢れたので，BitmapFactory.OptionsでinSampleSizeを2に指定し，画像サイズを1/4に縮小してテクスチャとして扱った

てな感じで，テクスチャマップした結果を以下に．トゥーンレンダリングも実装した結果もあるんだけど，そっちはまた明日にでも書きます．ようやくスタートラインに立てた感じです．ふぅ．

Android + OpenGLでMMD そのに

流石初心者だぜ！初っ端からとんでもない間違いをしていたぜ！

というわけで，ライティングをしてみたところ，色の扱いがまーーーったく違うことがわかってびびりましたｗｗ　昨日のは忘れてくださいｗ

間違っていたのは，「OpenGLでは頂点に色をつける」という箇所です．いや，この字面はあっているのかもしれませんが，どうやら，ライティングをする場合は，ColorBuffer使わずに，glMaterialでポリゴンごとに色を指定するようです．いやいや，やっぱり何か言葉が違う気がする．もうちょっと勉強しまふ．．．

で，とりあえず今日やった修正は以下のとおり．

1. 各vertexに対してNormal Vectorを定義し，glNormalPointerでそのバッファを指定．Normal Vector自体はPMDファイル内に記載されている
2. glColorPointerは削除
3. GL_LIGHTING, GL_LIGHT0をglEnableして，LIGHT0を光源として利用
4. glLightfv, glLightModelfvで白色光源を定義
5. PMDファイルの各MaterialごとにglMaterial*で色・材質を定義し，glDrawElementsでindex bufferに記述したポリゴンを描画．色・材質はPMDファイルの定義どおりに指定する．

DIFFUSE以外はアルファは無視られる，か，DIFFUSEのアルファが使われるっぽいので，とりあえずDIFFUSEのアルファを突っ込んでおきました．あと，ひっかかるポイントとしては，androidでは，どうやらglMaterial*でGL_FRONTやGL_BACKは使えないようです．GL_FRONT_AND_BACKの指定が必要なもより．このへん参照のこと． https://code.google.com/p/android/issues/detail?id=1962

で，以下今日の進捗です．昨日よりさらに怖くなりましたｗ

Android + OpenGLでMMD そのいち

お久しぶりです．色々あってほぼ死亡していました．まだ死亡中なのですが，ちょっとネタが出来たので，メモ書き代わりに更新します．やる気と時間があれば続きをやるかも．．．

そのネタというのは，AndroidでOpenGLです．最近ブラウザ(WebGL)やAndroidやXNAなどへのMMD（というかPMD形式のモデル等）のポーティングが盛んなのを見るにつけ，「ひょっとしてこれは簡単なのではないか？」と勘違いしてしまったのが始まりです．「もし簡単なら俺にも出来るかも！」的な根拠のない全能感に満たされた結果，勢いでOpenGLの本を購入してとりあえずコーディングに入りましたｗ

で，その結果，わかったこと2つ．ひとつは，ポリゴンを単に描くだけならば，OpenGLは非常に簡単であること．もうひとつは，その先に行こうとした時点で急に大変になること．ですｗ

OpenGLは，とりあえず頂点を3次元(X,Y,Z)の配列として，その色を4次元(R,G,B,A)の配列として突っ込んでやり，ポリゴンを形成する頂点をindexであたえてやれば，後はカメラ座標を指定するだけでさらっとシェーディングとかしてくれて描けてしまいます．原理さえわかれば凄く簡単です．PMDとOpenGLの座標系ではまりましたが，その辺事前にわかっていれば，瞬間でかけます．

ただ，その先に進むのがなかなか大変そうです．テクスチャ貼り付けたり，ライティングしたりは，まぁなんとかなりそうな雰囲気をかもしだしていますが（法線ベクトルの指定ははまるかも），その先，特にアニメーションさせようとした場合に急に難易度があがるような気がします．アニメーションに関してはOpenGLのサポート範囲外だからです．ボーンとかFK/IKとか，一体何事？レベルで何にも記述がありません．これは，普通にCGの本を買わないといけないということか．．．FKは行列の乗算ですみそうですが，IKは特に大変そうに感じますな．ソルバが必要って一体なんだよｗ

この辺の詳細をちくちく勧めながら，またブログを更新しようと思います．まぁ今度の夏コミか冬コミのネタになるかな．とりあえず，現状はまったことを列挙．

• PMDは左手系ですが，OpenGLは右手系，くさい．ので，PMDのvertexをparseした際には，zを-zと符号反転することにより右手系に変更します
• 同様にポリゴン（PMDは3角形だけです）のカリングに関しては，glFrontFace(GL10.GL_CW)指定が正しいように見受けられます
• モデルを読み込んだままだと，ほぼ原点を中心としてモデルが存在します．カメラも原点にある？ので，glMatrixMode(GL10.GL_MODELVIEW)で，glTranslatef(0, -10f, -9.0f)くらいしてやって，一方で，glMatrixMode(GL10.GL_PROJECTION)でglOrthof(-7f, 7f, -11.6f, 11.6f, 5f, 20f)してやると，全身がそれっぽく描写できます．
• glFrustumfだと，z軸の距離に依存して物体が小さく見えるので，ちゃんとレンダリングする際にはそっちのが良いと思います．ただ，現時点ではモデルがちゃんと描画されているか確認したいので，zに依存しない，glOrthofを使っています．
• PMDファイルでは，各三角形ごとに色の指定があります．一方で，OpenGLでは，各頂点ごとに色を指定する必要があります．そのため，PMDをparseした後で，各三角形の対応する色を，各頂点に指定しています．うそでした．ライティングする場合はglMaterial*で色を指定します．
• ボーンはとりあえず無視っても(=vertexとmaterialとfaceだけでも)それなりにちゃんとレンダリングできます．アニメーションの際のみに必要みたいです
• PMDの形式に関しては，ぐぐれｗ　PMDはlittle endianですが，javaはbig endianなのでendianの変換が必要です．ByteBufferを利用しました．ただ，OpenGLへ与えるバッファはマシンエンディアンで指定する必要があり，ARMでは多分little endianなので，ファイルからそのままの順で突っ込めばよかったかもしれません．ま，安全のために念のため両方変換しています．

このくらいかな．とりあえず，現在の進捗として，完全に化け物としか見えないミクさんを貼り付けますｗ　これでも，最初の頃の正体不明のクリーチャーより は随分マシになったのだよｗ　ライティングもしてなければ，テクスチャも張っていないので，特に目が白目で怖いですｗ　口から血吐いているしｗ　 vertexの色指定も所々なんか辺な感じなので，後でもうすこし考えてみます．

しかし，見れば見るほどキモイなｗｗｗ　大丈夫かこれｗｗｗｗ

コミケ76終了

C76で我々「空理空論学会」のスペースに来ていただいた皆様，本当にありがとうございました．おかげさまで，無事終了することができました．本は50冊準備していったのですが，14時頃には売り切れてしまい，その後に来た方々に申し訳ないことをしてしまいました．次はもう少し余裕をもって準備していきます．

というか，予想以上の売れ行きにびっくり，というのが正直なところです．ネタがネタだし，キャッチーでもないし，私の担当分はFPGA関連であるにも関わらずデモすらしていないしｗ　その割にちゃんと見て頂けて，ひじょーに嬉しく思いました．コミケという場所の凄さを思い知りましたｗ

見に来て頂いた方々も皆様，こゆい雰囲気をお持ちで，色々凄い感じでした．明らかに本職系の人や，そのスジの人，CafeOBJ方面ですとか，Brainfuckでshell作ってるぜとか，scheme処理系作ってるぜとか，ひじょーに極まった人たちがたくさん見に来てくれまして，いつもは出来ないような濃い話もできて嬉しい限りでした．セイバースキーさんの素粒子物理学方面も結構な人が来てくれまして，そっちはそっちでソッチ系の濃い話が展開されていましたｗ　ありがたやありがたや

で，次回に関してですが，残念ながら仕事の関係上，冬は参加できそうにありません．次は早くてもC78あたりになります．私の方はPuzzleBoxをもっと最適化＆出来れば並列化もして，何かデモれるところまでもっていきたいナ，と思っております．セイバースキーさんの方も今回の続きを計画していますのでお楽しみに．さ，死ぬほどたまったアニメを消費しないとｗ

コミケ76に参加します

あと1週間ない時点での告知でひじょーにアレですが，コミケ当選してました．2日目(8月15日)の東Q-29b「空理空論学会」です．「Journal of Everything」といういタイトルで文字ばっかりの本を売りますので，皆様たまたまコミケ2日目に参加される方は是非お立ち寄りをｗ

執筆者は，私，及び，このブログにもコメント頂いているセイバースキーさんの二人です．私が計算機科学でLazyKのFPGA実装的な話をしており，セイバースキーさんは素粒子物理学で量子電磁力学的な話をしております．結果としてカオスな本になりましたが，まぁそこはそれｗ

私の書いた記事は，計算モデルから始まり，lambda calculus, combinator calculus, LazyK, そしてFPGA実装，と，一通り記述してあります．blogの記事を一部流用はしておりますが，基本新規書き下ろしです．blogの記事では，色々とわかっている人だけを対象にしていましたが，今回の本では，一応最初から全てがわかるように解説したはず，です．はず，なのですが，何せ本を書く時間が，日常業務的に激しく厳しい時期だったので，あんまし推敲されていません^^;;; わかりづらいかも．というか，図がほぼありませんｗｗｗｗｗ　本当は，graph reductionのくだりとか，left ancestor stackのくだりは図を使って解説した方が良いのですが，そんな時間はありませんでした^^;;;　じ，次回は必ず．．．

NEEK上で動作するLCDコントローラを作る

いままでずーっと，Verilog RTLでほげふが，というタイトル付けていたのですが，つい先ほど，これは間違いで，Verilog HDLと記述するのが正しい，ということに気づきましたｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ　いや，勿論後者が正しいことは昔から知っていましたし，なんか変だなーと思ってはいたのですが，あんまし気にせずタイトルコピペしていましたｗｗｗｗｗｗｗｗｗ　なんかもう色々と失格な感じで穴があったら入りたいとはまさにこのことですｗｗｗｗｗｗｗｗｗ　ええと，いいわけすると，RTLレベルで書いているんだぜ，ビヘイビアじゃなくてよ，ということを主張したかったのですが，まず単語からちゃんと確認しようぜ俺ｗ

こんだけ超弩級の失敗をやらかした後だと，色々説得力が皆無になってもうほんとどうしようか，と思い悩んでしまいますが，過去は忘れて未来をみることとします．皆も過去は忘れてねｗ

さて，やっぱりLCDに絵をだしたい，ということで，LCDコントローラを作ることにしました．まずは，LCDの仕様の確認です．Nios II Embedded Evaluation Kit, Cyclone III Edition (NEEK) の仕様書の中，LCD Multimedia HSMC Reference Manualを確認したところ，NEEKに載ってあるLCDは，TD043MTEA1とやらであることが判明しました．このLCDの仕様は前述のリファレンスマニュアルには一切掲載されていないので，ぐぐって仕様書をゲットしました．ただ，ゲットしたのは良いのですが，どうも仕様書に書かれていないことが多いように見受けられます．HSYNCとかVSYNCとかの信号のタイミングチャートは記述されているので，最低限の信号は出せるのですが，なにやら存在するシリアルインタフェースの仕様やコマンドの類が一切ないのは一体どういうことよｗ　とりあえずはシリアルインタフェースは放置しておき，必要に応じて付属のサンプル回路を覗いて確認することにします．

さて，このLCDですが，800x480の解像度があり，仕様書通りだとリフレッシュレートは約60Hzに見受けられます．RGB入力で，それぞれ8bitが割り当てられるため，1ピクセルを表現するためには24bitのデータが必要です．HSYNCとVSYNC的な信号により同期させる，まぁどっかでみたよーな信号体系なので，それほど制御は難しくはなさそうです．

LCDのざっくりした仕様がわかったので，各種バジェットを考えてみましょう．データ転送量は，1秒あたり800 x 480 x 3byte x 60fpsです．すなわち，69.1MByteの転送量が必要です．また，1フレームあたりのデータサイズは，1.15MByteです．一方，NEEKには，合計約70KByte程度のM9Kと，1MByteの外付けSRAM @ 32bitがあります．DDR-SDRAMはコントローラを作る能力が私にはないので存在自体を除外しますｗ

上記より，全ピクセルデータを無圧縮RGB形式で持つことは，そもそもリソース上不可能であることがわかります．また，SRAMの帯域は，SRAMコントローラを50MHzで合成させた場合には200MByte/secとなります．フレームへの書き出しと読み込みが発生することを考えると，最低でも69.1MByte/secの2倍，約140MByte/secのデータ転送が必要です．上限に対し7割はなかなか厳しい値ですので，やっぱり無圧縮RGB形式で持つことは無理です．

というわけで，フレームデータのサイズを小さく，データ転送帯域を狭くしなければなりません．そのために，以下のパラメータを少なくすることにしました．

1. フレームサイズ
2. 1ピクセルあたりのデータ量
3. フレームレート

3番はデータ転送帯域だけに効いてくるのに対し，1番と2番は両方に効いてきます．ので，まずは1番と2番の対処を行うことにします．

まず，2番．YUV420フォーマットによる間引きが有効です．これは，人間の眼球の構成に依存した間引き手法です．人間の眼球には，明るさを感知する細胞は多く，色を感知する細胞は少なく存在しています．ので，ピクセルデータを明るさと色の情報に分け，色の情報は明るさの情報の半分で済ませましょう，という考え方に基づく間引きです．YUV420においては，明るさを示すYは1pixelあたり1byteの情報を与えるのに対し，色の情報（色差）を示すCbとCrはそれぞれ4pixelで1byteの情報を共有します．ので，1pixelあたりの色の情報は0.5byteです．これに対応することにより，RGB3byteに比べ情報量は半分になります．

2番だけではデータ量が半減しただけなので，まだ容量的に，ダブルバッファを持つには足りません．ので，フレームサイズもへらしましょう．ここはわかりやすく，縦半分，横半分の，合計1/4のピクセル数にします．

これらにより，データ転送量は，1秒あたり400 x 240 x 1.5byte x 60fpsになりました．すなわち，8.64MByteの転送量が必要です．また，1フレームあたりのデータサイズは，144kByteです．ダブルバッファで2フレーム分の領域を確保しても，288kByteで，SRAMの1/3しか使いません．また，データ転送帯域も10%程度と，まぁそれなりに現実的な感じとなります．

で，間引いたからには，表示するときに補完しなければいけません．YUVからRGBは，固定係数をかけて足せば良いだけなので，特に問題ないでしょう．固定小数点演算をする必要があるので，精度が問題ですが，それはまぁ適当にトライアンドエラーでざっくり決めちゃいます．フレームサイズは，てきとうにバイリニアで拡大してやれば良いかな．

また，フレームレートですが，LCDに送るクロック周波数を落とせば自然とフレームレートが落ちる気がするのですが，それでLCD自体がちゃんと動作するかは謎です．後で試してみよう．15fpsとかでもそれなりに見えるはず．これくらいなら，SDから直接データ読んで表示する，とかでも動きそうな予感．

一方で，15fpsの時の画像1バイトあたりの処理サイクルバジェットは，80MHzでPuzzleBoxコアを動かしたとしても，40cycle程度です．つまり，最大でも1バイトあたり40回しかリダクションできません．結論として，全然処理性能が足りない，ということになりますｗｗｗｗｗ church数をmachine integerに変換するだけでも最大255cycleかかってしまうので，もう論外ですｗ　やはり，machine integerの計算を組み込まないとダメだな．．．

Verilog RTLでGC そのよん

まだバグがありそうな感もありますが，とりあえずGCの実装（最適化前）を完了しました．rev62でcommit済みです．おかげさまで，add7が普通に動作するようになりましたが，相変わらず(fact 4)が計算できません．どどど，どうしよう．．．GCでダメだとすると，真面目にmachine integerと四則演算等の実装をしないとならんなぁ．むぅ．．．

なんとなーく，ですが，fact 4メモリ不足で実行できないよ問題は，GCでは解決しないよーな気はしていました．ゴミ自体が少ないと思われたからです．再帰中は未評価のCAFがたんまりたまっていって，参照が切れていない状況だと思われます．そんな状況でメモリ不足が発生したとしても，回収できるゴミが少ないんではなかろうか，と．まぁ，ちょっとGCの挙動がおかしい気もするので，GCにバグがあるかも的な視点でデバッグしてみますが，あんまし根本的な解決にはならなそうだなぁ．

で，他の解決策として，再帰時に消費するCAFの量を減らしましょう，という話があります．そこで登場するのがmachine integerと四則演算の実装です．church numberは，lambda calculus的なモデル上でうまく整数を表す手法ではあったのですが，なにせモノが再帰構造なため，CAFを大量に使ってしまいます．メモリ的にひじょーに優しくない．こいつらを組み込みの演算で実現すること自体は難しくはないので，まずはここから対処しましょう．

とはいえ，やっぱり評価順がapplicative orderじゃないとマズいのでどうしましょうね問題が発生します．むー．例のreduceronのようにひっくり返せば良いのですが，どう実装したもんかなぁ．もう少し考えてみます．

で，アプリの話ですが，やっぱりSDからデータ読んでLCDに絵を表示したくなったので，そっちのコントローラを作ろうかなぁという気がしてきました．激しく今更ですがｗ　頑張って2ヶ月で作成して，7月に本を書く方向で．むむむ，本を書く時間が激しく短くなってきました．これは，アレですね．死亡フラグって奴かなｗｗｗｗｗ

．．．ええと，LCDに絵を表示するためには，LCDコントローラに加え，フレームバッファ用のメモリが必要ですね．で，このメモリは多分外付けのSRAMを使わないと実現できない感じですね．そうすると，SRAMコントローラを作らなければなりませんね．ぎゃーｗｗｗｗｗ　ムリダナ．うん．無理無理．無理だけど，やってみようｗｗｗｗｗ　まぁどーせこの辺のペリフェラルはどっかで必要となるだろーし．SRAMくらいならそんなに難しくないでしょ．夏の本は，出来たとこまでの解説をする方向でお茶をにごそうそうしようｗ　

Verilog RTLでGC そのさん

GCめんどくせえええええええｗｗｗｗ　昼間の業務が忙しくなったこととあわせて，全然進捗がありません．とりあえず，markのためのbitmapを作成し，bitmapのゼロクリアとマークされていない領域（未使用領域）の探索，及びアロケーションまではサポートしました．コミット済みです．過去のPuzzleBoxとほぼ互換で作成しているので，今のところ問題なく動作します．ただ，肝心のGCがまだサポートされていません．これから，evaluation stackとcar reg.をなめてbitmapのマーク&外部メモリのsearchを行うシーケンサを作る必要があります．なんとか，ゴールデンウィーク前には作ってしまいたいなぁ．ゴールデンウィーク中はアプリケーション作成に打ち込みたいところです．

アプリは，結局たいしたものができないような感じがします．入出力が119200bpsのシリアルだけなので，そもそものデータ転送量がしょぼいですし．ええと，転送効率が半分で，read/writeでさらに半分とすると，119200/4で約30,000bps，3.7k byte/secですか，ああ，これはなんも転送できんなぁ．．．．どうしよう．てけとーにLOGフィルタでも実装してちんたら絵出して満足させるかなぁ．しょぼいなぁ．ううむ．

SDIF，LCD Controller及びSRAM Controllerを実装してしまえば，それなりの性能で絵をだしながらほげほげ出来て色々嬉しいのですが，それらを実装すると，本書く時間がなくなりそうなんだよね．んー．悩む．夏に落選したらこの辺実装するかな．

Verilog RTLでGC そのに

1日たって冷静に考えた結果色々間違っていたので謝罪しようのコーナー（えー

ええと，まず，CopyingGCでは読み出したオブジェクトの内容で処理を分岐させるのでレイテンシまるみえ，という話をしましたが，このレイテンシまるみえ困っちゃったな事態はmark-and-sweepでも同様に発生します．ふつうにCAFなデータ構造を辿っていく際には，読み出したオブジェクトの内容がポインタになっているのでそのアドレスを読み出す，的な動作が必要だからです．なので，結局こっちでも性能あげるためにはレイテンシ隠蔽する手法が必要です．

次に，tree辿るにはstackが必要，的な話をしましたが，まぁ普通はそうなんですが，今回のHWの実装では，stackではなくFIFOを使うと良いような気がしてきました．FIFOだとアクセスポートが読み書きで分かれているため，スループットで動かしやすいからです．多分．stackでもアドレスのmark順がleafから始まるのか，rootから始まるのかの違いだけで，FIFOと同様のことはできるのですが，なんせstackへのアクセスポートは1個のため，RTL的に読み書きが同時に行えません．読む側の処理と書く側の処理がdecoupleできなく，simulteniousな処理が困難になります．FIFOはアクセスポートが2portあるので，その辺の問題はないかなぁと．

あと，FIFOなりstackなりのサイズに関して．おそらくですが，MAXでメモリサイズの半分くらいの容量が必要となりそうです．幅優先の場合だとバランスのとれたtreeが一番メモリを使いそうで，その場合のMAXのleafの数はtreeのnodeの約半分ってところだからです．FIFOだと，幅優先と深さ優先の折衷案みたいな辿り方をするような気がするのでよくわからないのですが，まぁ似たようなものでしょう．ただ，これもまたおそらくですが，実用上はそれほど容量は必要ないはずなので，小容量でFIFO作って，まぁFIFO溢れフラグでも持っておけば良いかな程度に考えています．

そんな感じで，現状想定しているmark手順は以下の通りです．

1. FIFOからアドレスを読み出す
2. アドレスの値を元にbitmapを読み出す
3. 読み出したbitmapの値が1の場合，すなわち既にmark済みの場合は1に戻る
4. bitmapを1に書き換える
5. アドレスの指し示すconsを外部メモリから読み出す
6. 読み出したconsのcar部分とcdr部分それぞれに対し，アドレスであった場合にはFIFOへそのアドレスを書き込む

で，最初にevaluation stackの中に保持されているアドレスをFIFOに書き込めば，上記手順でmarkを開始します．

さて，この手順をじーっと見ると，実はmark-and-sweepでもCopyingGCと同じ回数だけメモリにアクセスしていることがわかります．FIFOの読み書き，bitmapの読み書き，そして外部メモリの読み出しで，読み出し3回，書き込み2回が行われています．CopyingGCと比べ，回数は全然減っていません．今回は，bitmap使ったり，途中で評価が止まる危険性を認識しつつ小容量のFIFOを使ったりすることで，なんとなく外部メモリへのアクセスを減らしましたが，こう考えるとあんましmark-and-sweepは良いものじゃないなぁ．CopyingGCの方がよかったかなぁ．むーん．

ちなみに，先達であるところのreduceronはstop-and-copyでした．この辺の用語は全然知らないというか，CopyingGCも正式名称かどうかすらも知らんのですがｗ stop-and-copyはCopyingGCみたいな感じでやるGCっぽいです．ただ一点，flipせずにcopy backします．別にGCの研究やっているわけじゃないから，一番簡単なのにしたよアハハ，これだとstackいらんしね，ということらしいです．でも，stackはいらなくてもGC用のメモリを必要としているじゃんｗｗｗ

Verilog RTLでGC

いつまでもメモリ足りない足りないと連呼しているだけだとしょーがないので，PuzzleBox CoreにGarbage Collection(GC)を導入することにしました．当初は，コンパクションも行うCopyingGC的なものを使用する予定でしたが，その外部メモリへのアクセスの多さに絶望して別の手法に逃げました．基本はmark-and-sweepで，mark bitだけをbitmapとして別メモリでFree Pointer管理モジュール内にローカルに実装します．bitmapをリニアサーチすることで次のFreePointerを見つけます．外部メモリへのアクセスはmark時のread 1回/cellのみなので，GCにかかる外部メモリ読み書きコストはCopyingGCに比べかなり減ります．また，bitmapは外部メモリが64kの場合はたかだか2k byteですむため，M9K2個のみでコンパクトに実装できます．他のモジュールとbitmapを共有する必要がないため，レイテンシも短くでき，良いことずくめです．markする時のstackどう実装するよ問題とか，色々ありますし，そもそも一切実装していませんが，まぁそれはおいおい．

CopyingGCのアルゴリズムは，the architecture of symbolic computersのmemory management for s-expressionsに記載されています．CopyingGCという名前は一切でていないのですが，memory compactionの節(8.4, p195)から解説されているBaker's algorithmが多分ソレでしょう．しかしこの本本当になんでも載ってるなｗ　良い本です．

CopyingGCのざっくりした内容は，以下の通り．

• ヒープ領域を同じサイズの2個の領域(FromspaceとTospace)に分ける
• プログラムから使用できるのは片方の領域のみ
• GC+コンパクションは，片方の領域で使用されているオブジェクトのみを，もう片方の領域に，隙間を詰めながらコピーすることで行う

もう少し詳細な動作は以下のような感じかな．

1. Reduction Coreが保持するオブジェクトをFromspaceからTospaceにコピーする
2. コピー元のFromspaceのオブジェクトに，コピー先のアドレスを上書きする
3. Tospaceにコピーしたオブジェクトを読み出す（読み出したオブジェクトをaとおく)
4. オブジェクトの内容がFromspaceを指し示すアドレスであれば，そのアドレスのオブジェクトを読み出す
5. 読み出したオブジェクトが既にコピー済みで，内容がコピー先のアドレスに上書きされている場合，Tospaceのオブジェクトaにコピー先のアドレスを上書きする
6. 読み出したオブジェクトがコピーされていない場合，そのオブジェクトをTospaceにコピーし，Tospaceのオブジェクトaにコピー先のアドレスを上書きする
7. Tospaceから読み出すオブジェクトがなくなるまで，3..6を繰り返す

．．．わかりづらいですね^^;;;コミケ用の本書く際にはもうちょっと推敲します^^;;;

で，まぁ，ここでのポイントは，生きているオブジェクト1個あたりの読み書き回数です．step 1で読み出し1回書き込み1回，step2で書き込み1回，step 3で読み出し1回，step 5 or 6で書き込み1回が最低行われます．step4の読み出しは，step1の読み出しと同意義の場合が多いのでとりあえず省略．で，生きているオブジェクト1個あたり，合計読み出し2回，書き込み3回行われます．

FPGAというか，HWの世界だと，メモリアクセスのコストはひじょーに高い（レイテンシが大きく，スループットが小さい）ので，全てのオブジェクトに計5回もアクセスする，しかもプロセッシングとは全く関係ないことはできるだけやりたくありません．さらに，step4から5,6にかけて，読み出したデータの内容で処理を分岐させています．これは，メモリレイテンシがもろに見えてしまいます．並列動作によりある程度は隠蔽できますが，ぶっちゃけ面倒でノーフューチャーな香りがします．

そこで，やはりポインタを書き換えるのはコストがでかいだろう，ということで，ポインタを書き換えない手法としてmark-and-sweepに戻りました．ただ，この手法でも，mark & unmarkのためにメモリアクセスが頻発します．メモリアクセスが生じることは仕方ないのですが，できるだけその影響を減らす必要があります．そこで，アクセスの頻発するmark bitをオブジェクトから分離し，bitmapとして管理します．全メモリ空間に対するbitmapのサイズは非常に小さい(1/32～1/64)のため，ローカルにかかえた小さいメモリで実装可能です．メモリはサイズが小さく，接続相手が少ないほどにアクセスにかかわるコストは減っていきます．今回のPuzzleBoxでは，2k byte程度で済むため，まぁ問題ないかなぁと．

また，mark-and-sweepはポインタの書き換えを行わないため，simulteniousにGCを実行できます．PuzzleBoxからの外部メモリへのアクセスがない時のみメモリアクセスを生じさせることにより，コアの実行性能に一切影響を与えずにGCが可能です．

FreePointerの空き領域探索も，同様にsimulteniousに行えます．FreePointerのリクエスト間隔より少ない時間で空き領域探索が完了すれば，こちらもコアの実効性能に一切影響をあたえません．多分，サーチは1cycleに64領域を探索できるように作成するので，まぁ多分そんなにサーチに時間がかかるということはないでしょう．こちらも問題なし．

そんな感じで方針は決まったのでさて実装するか，という段になって，そういえばtreeのサーチはstackなしでは出来ないなぁということに気づいて目下悩み中ですｗｗｗｗ　tree書き換えながらstackなしで行う，というアルゴリズムもあるにはあるのですが，GCで頑張って減らした外部メモリへのアクセスが激増しますｗｗｗｗ　まぁ，おとなしく内部にもう一個スタックつくるか．やれやれ．．．