只見線日帰り旅行に行ってきた
あけましておめでとうございます。
僕は長期休暇にだいたい青春18きっぷを購入しているのですが、今回も例によって余らせてしまった（しかも3日分）ので、期間内にどこかに旅行しに行こうと思って日帰り旅行できそうな場所を調べていたところ、
このNaverまとめを見つけたので、只見線を乗りに学科の友人と二人で行くことにしました。
只見線とは
新潟県魚沼市の小出駅〜福島県会津若松市の会津若松駅間を結ぶ、ド級のローカル線。
どれくらいド級かというと
1日4本、無事乗車しました pic.twitter.com/IXUXgaxJAq
— Fukumu Tsutsumi (@levelfour_) 2016, 1月 7小出駅側からは1日にたったの4本。。。うち只見駅まで行けるのは3本です。
こんな路線の何がいいかと言うと、景色が非常に良い。
魚沼市も新潟の山奥、只見周辺も福島県の西端、奥会津と呼ばれる場所で、山奥の秘境です。
Wikipediaより引用
すごい。
さらに四季によって折々の景色を映すらしく、この時期は白銀の世界が広がっていると聞き、これは行くしかないということで行きました。
旅程
上のNaverまとめでは池袋発着で次の旅程が紹介されていました。
ただ、出発前夜に気づいたことなのですが、小出駅で乗る只見線は13:11しかないので、朝5時代に出る必要はありません。
今回は上野発着で乗ったので、実際の旅程は
- 6:26-8:16 高崎線 上野駅→高崎駅
- 8:24-9:31 上越線 高崎駅→水上駅
- 9:47-11:10 上越線 水上駅→小出駅
- 13:11-14:28 只見線 小出駅→只見駅
- 14:32-15:22 只見線(代行バス) 只見駅→会津川口駅
- 15:28-17:36 只見線 会津川口駅→会津若松駅
- 18:12-19:29 磐越西線 会津若松駅→郡山駅
- 19:42-20:45 東北本線 郡山駅→黒磯駅
- 20:52-21:44 宇都宮線 黒磯駅→宇都宮駅
- 21:47-23:38 宇都宮線 宇都宮駅→上野駅
となりました。これ、たぶん横浜住みの人だと一日で戻れないですね。
只見線特有の特徴としては、
見どころ
非雪国の出身にとっては、トンネルを抜けた瞬間に眼前に雪国が広がっているのには感動します。
この行程では
の2箇所で峠を越えます。
只見線は小出駅から始まります。大白川駅までは比較的人里がち。それでも白銀の景色を楽しむことはできます。
メインは只見線の大白川駅から。大白川駅から只見駅の間には駅はなく、営業距離約20km、運行時間約30分間止まることなく走り続けます。
前半は新潟の最も山奥の豪雪地帯で、スノージェット（道路・線路に設けられている防雪用の屋根）をたくさん見かけます。
雪をたたえた樹木や時折交差する渓流にかかる橋梁は非常に美しいです。
ちなみに冬期はここの道路は封鎖されるそうで、新潟-福島間の六十里越を越えられる交通手段は只見線が唯一となるそうです。
後半は峠越えなのでほとんどがトンネルになります。14:20頃にトンネルを一度抜けると、進行方向右手に田子倉湖が見えます。
雪の中の田子倉湖の景色も非常に良いです。これ以降、1〜2時間ほど田子倉ダムとその下流ダムと並走します。
食事
昼食を取る時間は、小出駅での約2時間の電車待ちの間が妥当です。
しかし、小出は非常に小さな町で、駅前にはほとんど何もありません。市街地は駅の反対側、魚野川の対岸です。
僕が訪れたのが1/7とまだ新年明けたばかりというのもあるかもしれませんが、小出の飲食店は夜のみ営業となっているところが多いように感じます。
そのため、昼間に飲食店を探すのはなかなか至難の業。30分ほど町中を練り歩いたところ非常にオススメのお店を見つけました。
上掲の地図にピンを打ってありますが、香秀（カシュウ）という懐石料理屋さんです。
お昼は海鮮料理や天ぷら定食をいただくことができ、小鉢にコーヒーもついてくる、とても美味しいお店です。
小出駅まで片道およそ15分程度です。小出の昼食はここがぜひおすすめです。
夕食はタイミング的には会津若松駅が妥当で、会津若松は喜多方ラーメンで有名な喜多方も近くにありますし、美味しいおそばも多く散見されたのでぜひ寄ってみたかったのですが、上述の通り只見線の冬期徐行で会津若松駅滞在時間が30分間になっているので、駅の外で食べるのは少々時間的に厳しいと感じました。
駅中に何軒かお食事処があるので、そこがよいのではないでしょうか。
CPU実験でTravis CIを使ってみた
この記事はCPU実験 Advent Calendar 2015の15日目の記事です。
CPU実験において、僕の班は（主に僕の独断で）Travis CIを導入しました。
もう一度CPU実験の概要について説明します。
CPU実験では主に
の4つの係があり、
という流れになります。FPUはコアに組み込みます。また、シミュレータの浮動小数点演算もx86組み込みのfadd命令ではなく、自班のFPUの動作を模倣するシミュレータを書きます（コア/シミュレータの差分を比較するため）。
ここで重要になってくるのは、いかにしてまずシミュレータをバグなく完成させるかということです。
コアやコンパイラは一般にバグなく書き上げるのは難しいので、シミュレータを正しく動作させるのが先決です。
また、コンパイラ→シミュレータのパスを正確につくり上げることでコア係のデバッグに役立ちます。
というか、コンパイラ→シミュレータのパスに信頼性がないと、コアのバグがコアの原因なのかコンパイラやシミュレータの原因なのかわからず、何からデバッグすればいいか手をつけにくいです。
（CPU実験においてはこういう状況は精神衛生によくない）
そのため、コンパイラ→シミュレータのパスの信頼性を担保するのは重要であり、ここにTravis CIを用いることを考えました。
テストの流れ
1. 必要パッケージのインストール
2. min-camlのビルド
3. シミュレータのビルド
4. テストケースの実行
この流れはMakefileに書きました(make testで実行できるようにした)。実際には.travis.ymlのscript属性にmake testと記述してあります。
【参考】.travis.yml
依存パッケージのインストール
テストケースの実行にはPythonのnoseというユニットテストモジュールを用いているので、pipで必要パッケージをインストールします。
pip install -r .install.txt
また、min-camlはOCamlで記述されているためOCamlが必要です。僕はBytesというモジュールを使っているのですが、これはOCaml 4.0.2から導入されたモジュールです。
しかし、travisで標準で用いられているOCamlはもっと古いので、新しいバージョンをインストールする必要があります。
これはTravis CIでOCamlを使うまでの道のり - Handwritingで紹介したので、参考にしてみてください。
min-caml、シミュレータのビルド
これは普通にビルドするスクリプトを書いただけです。
テストケースの実行
テストケースの実行には、上述の通りPythonのnoseというモジュールを用いました。
これはリポジトリ内にある、「test」と名前についているファイル中に含まれる「test」を冠するテストメソッドを実行します。
説明するより見るほうが早いので、僕が書いたテストスクリプトを置いておきます。
これが実際に走るとこのログのようになります。
各々のテストメソッドで行っているのはシミュレータの答えと期待される答えが一致しているかどうかのアサーションで、等しければOK、違っていればそこでテストが落ちます。
Slackへの通知
TravisはSlackへの通知をサポートしています。pushする度にテストが走り、Slackにテスト結果が通知されます。
所感
Travisを使うのは初めてでしたが、pushする度に100行超のログが流れてテストに通るのはなかなか快感でした（自己満足）。
ただ、実際CPU実験の役にたったのかどうかというのは少し疑問です。
というのも、どちらかというとTravisのテストに通すために非本質的なfixを強制されることがありました。
例えば、
などなど。まあ恐らくコンパイラやアセンブラ、シミュレータのデグレーションは防げていたのだろうけど、逆にデグレーションしなかったからあまりありがたみが感じられなかったのかもしれません。「失って初めて気づく幸せ」というやつですね。
あと、浮動小数点演算のテストを作るのはちょっと面倒です。結局僕は面倒だったのでサボりました。
FPUのレギュレーションはx87完全一致ではなく、数ulpの誤差が許されています。
逆にそのせいで浮動小数点演算の答えがx87と一致しないので、テストを書くのが難しいです。
例えば、僕は次のようなロジスティック写像を15回ほど回すlogisticというテストケースを作りました。
ところが、元々1回の浮動小数点演算（ここではfmul）がx87と一致しないので、15回回すと結構大きな誤差になりました。確か1万ulp程度はずれていたと記憶しています。これでも一応レギュレーションは満たしているのですが。
そのため、本当に厳密にテストを書くのならば、ちゃんと不等式で幅を持たせて期待される答えの範囲を記述する必要が出てくるので、非常に面倒くさいです。
CPU実験でコンパイラの改造でハマったところ
この記事はCPU実験 Advent Calendarの1日目の記事である。
1日目なので(?)、とりあえずCPU実験について説明する（とはいえどもこの記事を見ている人でCPU実験を知らない人がいるのかどうかという点については怪しいところだが）。
CPU実験というのは東京大学理学部情報科学科の学部3年の後期に半年間かけて行われる演習のことであり、この学期の授業コマ数11分の6を占めるという、まさに名物演習だ。
受講者（ほぼ情報科学科の3年生）は4人1班に分かれて、それぞれコア係、コンパイラ係、シミュレータ係、FPU係に分かれてレイトレーシングプログラムが動くように自作アーキテクチャを設計してFPGA上でレイトレーシングプログラムを動作させ、その実行速度を競う。
最終的に次のような画像が作られる。
僕はコンパイラ係になった。コンパイラ係は最近はMinCamlというOCamlのサブセットであるコンパイラを改造して、自作アーキテクチャに対応させる流れになっている（講義でもMinCamlが推奨、というかデフォルト）。
基本的にはMinCamlにPowerPC、SPARC、x86向けのアセンブラを吐くモジュールがあるので、それを流用してMinCamlの中間表現をうまく自作アーキテクチャのアセンブラに変換することがコンパイラ係のメインの仕事。
なのだが、思った以上にいろいろなところでつまづいたり、他の仕事もあったりで結局開発をはじめてから2ヶ月弱かかることになってしまった。
自作アーキテクチャへの対応
僕の班ではMIPS32を改造して（というよりもほとんど流用して）Carinaという1stアーキテクチャを設計した。
MinCamlにはアーキテクチャごとにx86、SPARC、PowerPCというディレクトリが切ってあり、それぞれにemit.mlというアセンブラを出力するファイルが入っている。
基本的にはどれか一つを選んでコピーして、emit.mlを書き換えていくことになる。
ここでまず一つ。x86を選ぶべきではない。
なぜかというと、x86はアドレッシングモードが煩雑であり、自作アーキテクチャへの対応が面倒だから。
他の2つはRISCなので比較的改造が楽だが、x86にはdisplacementとbase registerに加えてindex registerがアドレッシングモードで使える。
index registerは一般的にはアセンブラで配列アクセスする際に配列の要素サイズを指定しておくことによってループごとに簡単にアクセスできるというシロモノだが、CPU実験ではまずindex registerが必要になる場面はない（よっぽどの物好きでない限り）。
その理由は、実験で使うFPGA基盤(Virtex-5)に乗っているSRAM(メインメモリ)のアドレス幅が32bit（1つのアドレス番地と32bitの記憶領域が対応している）になっているため、浮動小数点数をすべて単精度で実装するため。
MinCamlでは浮動小数点は倍精度で扱う実装になっているが、CPU実験では単精度で十分だ。
SRAMのサイズも2^20なのでアドレス変数も32bitで十分。
さらにこれらのデータがSRAMの1cellにちょうど入るので、データにしろ命令にしろ32bit単位にしてセルに1つずつ詰めるのが最も単純。
そのため、配列アクセスする際もindex=1が基本となるので、x86ほどの複雑なアドレッシングモードを必要としない。
レイトレ用ライブラリを用意する
レイトレを動かすために必要なライブラリは
- sin
- cos
- atan
- abs
- float_of_int (intからfloatへの変換)
- int_of_float (floatからintへの変換)
- floor
- sqrt
- print_int
- read_int
- read_float
- その他雑多な関数群
主にクリティカルになるのが実数算術系のはじめの8つ。sinやcosなど、このあたりは実験のレギュレーションでどの程度まで誤差を抑えないといけないかが決まっている。
この誤差がちゃんと抑えられていないと
こんな悲しい画像になる。
（「床がバグるときはfloor関数を見なおせ」という格言があるくらいこれはCPU実験では有名なバグの一つのようだ。ちなみにこの時点ではfloorが切り捨てではなく四捨五入になっていた）
実装するときはアセンブラで実装するかOCamlで実装するかというオプションがある。
OCamlの方がインライン展開がきくので後々最適化をゴリゴリかけられたり、human-friendlyといったメリットがある。
アセンブラだとコンパイラのバグの影響を受けないとか、意図しないコンパイル結果にならないというメリットがあるのかもしれない。なんでアセンブラで実装したんだろう・・・
実装した後はこんな感じでx87のFPUで計算した結果と自分たちのシミュレーション結果との誤差検証を行う。
ulpというのはunit in last placeの略で、最下位ビットを単位としていくらずれているか、という誤差指標だ。
例えば正しい計算結果が1.53(単精度で0x3fc3d70a)なのに得られた計算結果が1.5300009(単精度で0x3fc3d712)だった場合、誤差は
0x3fc3d712-0x3fc3d70a=0x8 ulp
となる。
だいたいの誤差はアセンブラの書き間違いとか、些細な計算式の間違い（符号違いとか多かった）とか、係数間違い（アセンブラだと浮動小数点数を16進数で書かないといけないのでそこの変換ミス）だったりした。
あとは、10年ほどまえに誕生したFPU神資料というやつが代々受け継がれて浮動小数点回りの計算でよく参照されるが、それに微妙な間違いがあって、そこに引っかかることもある（ex. レギュレーションの解釈が間違っていて実装が若干間違っている、逆数の参照テーブルの計算式が微妙に間違っている等）。
レイトレをコンパイルする
ここまできたらあとはレイトレをコンパイルするだけなのだが、意外とすんなりといかせてくれない。
そもそも、配布されたレイトレプログラムはデフォルトのMinCamlの文法では以下の理由により受理できない。
- 整数乗算/除算演算子が使われている
- create_arrayという未定義関数が使われている（Array.createにエイリアスすればよい）
- 継続演算子（名称合ってるのか？）; (セミコロン)が文の最後についている
- 評価部(let x = C1 in C2のC2)が存在しないlet文
- プログラムの最後に評価される値がunitではない
ざっとこんなところだろうか。以上の記法はすべてMinCamlの文法では違法である。
（他にもあるかもしれないが、先生が今年度中に直すと仰っているので、直っていなかったら文句を言っていいと思う）
さらに、文法的には違法ではないが、「クロージャレジスタがSave/Restoreされていない」というバグ(?)がある。
簡単に説明すると、コンパイルの過程で変数のレジスタ割り当てをしなければならないが、"生きている変数"が割り当てられているレジスタに他の変数を割り当てるときは元の値を破壊しないようにスタック上に退避(Save)する必要があるし、一度退避した変数を使うにはスタックから復元(Restore)する必要がある。
クロージャレジスタの方が一般的な用語ではないので説明すると、MinCamlは（一応）関数型言語なので高階関数や関数のネストができる（部分適用はできない）。
nested functionを実際に機械語で実現するためには、呼び出し前に通常の引数に加えてヒープ上にnested functionで使われる自由変数をわたしたり、nested function自体のアドレスを確保しておく（クロージャ変換という操作だ）。
このときnested functionのアドレスを入れておくレジスタがクロージャレジスタなのだが、なぜかこのレジスタのSave/Restoreが行われない。
この点も直す必要がある（レイトレでは大量のクロージャが生成される）。
つまらないハマリポイント
個人的にハマってしまったポイントを挙げる。
OCamlの比較演算子を勘違いする
OCamlのnot equal演算子には<>と!=がある。<>は値の比較、!=はオブジェクトアドレスの比較だ。
ここでうっかり!=を使っていたがために全くバグの原因がわからず1週間溶かしてしまうという悲劇を引き起こした。
そもそもOCamlでアドレス比較をしたいということはまずないと思って良いので、OCamlのnot equalは<>演算子という点を強調しておきたい。
デバッグ用の存在しない命令を吐いていた
上述のとおり、レイトレでは整数乗算と整数除算が使われる。僕は当初、コンパイラ/アセンブラ/シミュレータすべてで面倒だったので整数乗算/除算命令を実装していた。
しかし、FPGA上では乗算回路はかなり配線量を消費する。除算回路はなおさらだ。
配線遅延は起きるわ、回路規模は圧迫するわで非常に大変。おまけに乗算は×4、除算は÷2しか登場しない（除算はスクリーンサイズの計算に2回使われるだけだ）。
そのため、これらはシフト演算命令を使って実装されるのが定番だ。
ところが、僕は面倒だったので普通に乗算/除算命令を吐いていた。これをコア係に伝え忘れていたため、コア係の時間を3日ほど潰してしまった（本当にごめんなさい…）
まとめ
CPU実験で素早く完動するにはいかにバグの起こらなそうな方法で素早く実装するかにかかっていると思う。
ISA(Instruction Set Architecture)をいかに簡単なものに設計するかも重要なポイントだと思う。シンプル・イズ・ベストというやつだ。
また、いかに早くバグの原因を特定するか、というのも重要だと思う。僕は特に11月、2つの原因がわかりづらい大きなバグに悩まされて、それぞれ1週間ずつくらい溶かしてしまっている。
まずは班員の役割分担がコア・コンパイラ・シミュレータ・FPUと分かれているのだから、どのセクションにバグがあるのかを明確にすること。また、明確になるように目的意識を持ってデバッグすること。
コンパイラ係はコア係の次に原因不明のバグに悩まされることが多いポジションだと思うので、精神衛生を保つことも大切です。
あまり深く考え過ぎないように、別の課題やったり散歩したりご飯食べにいって気分転換してる間にふっと解決することもあります。
これから
1st完動ということで2ndで何をやりたいかなのだけれども、我々の班はとりあえずコア・FPUがパイプライン非対応なので、まずは1stをパイプライン化することから恐らく始まる。
そのため、コンパイラ係の僕は暫くは最適化以外やることのない暇な時間が訪れる（と期待される）。
その間にコンパイラ基盤をフルスクラッチしたいと考えている。MinCamlだとどうにも自分のやりたいことがうまくできない感じがある。これからやっていきたいのは
- MLコンパイラのフルスクラッチ(MinCamlより広範な、独自拡張文法も含めた文法を扱う)
- lambda liftingなど、クロージャ変換よりも実行効率のよいクロージャの実現
- その他有名な最適化の実装(レジスタ割り付けの整数最適問題への帰着など)
- LLVM
あたりかな。あと、これは余興という形で班員とも相談になるけれど、独自拡張構文を導入して行列演算をはじめとした数値計算構文を導入して、バックエンドではSIMD命令を吐いて独自アーキテクチャ上で楽々Machine Learningみたいなことができたら面白いかなあと思う。面白いだけで性能は期待できないけど。
