ジョイジョイジョイ

ジョイジョイジョイジョイジョイ

計算機科学実験及演習3ハードウェア(CPU製作)記

先日、長いようで短かった実験がついに終わったので記録を残しておきます。

はじめに

京都大学情報学科の計算機科学コースでは計算機科学実験及演習(以下、実験)という必修科目が 2 回生前期 / 後期、 3 回生前期 / 後期の計 4 つあります。

実験 1 はプログラミングの入門みたいな内容
実験 2 はマリオ AI の作成と電子回路
実験 3 は CPU 製作とインタプリタ製作
実験 4 はいくつかの分野から選択

という感じです。

僕たち 2015 年入学の学生から実験の内容が少し変わったのですが、実験 3 の CPU 製作は昔からあるみたいです。

CPU を製作する学生実験といえば某大学某学科の CPU 実験が有名で知っている人も多いと思います。

CPU 実験でググるとすごい人の製作記がたくさん出てきて面白いのですが、いまググるとこの記事が霞んで見えるので読み終わってから調べてください(参考文献にいくつか並べてあります)

あちらの実験は有名なのに、実験 3 の記事は(調べ方が悪いのか)調べてもあまり出てきません。

これではあまりにも寂しいし、僕自身実験をはじめる前に製作記みたいなのを読みたかったので後輩のためにも少しがんばって書くことにしました。

実験について

実験 3 (ハードウェア)では二人がかりで FPGA を使って CPU を製作します。

期限は二ヶ月弱。今年は初回授業が 4/13 で、デモが 6/2 でした。

実験の時間は毎週木曜 3 限から 5 限と金曜 1 限から 5 限までの 8 コマ(毎週 12 時間)です。めちゃくちゃ長い。

しかも 4 分の 1 以上休むと単位がもらえないというスパルタぶりです。

作るアーキテクチャについては SIMPLE という 16 ビットアーキテクチャが提示されて、これに準拠したものを作ります。

準拠するといっても改良するのはアリで、どこまで変えていいのか聞いてみたところ面白ければなんでもいいらしいのでほぼ自由です。

ただし、レジスタ幅/データバス幅は 16 ビットでないとダメです。この制約が割と辛いので注意してください。32 ビットアーキテクチャにするくらいなら許してほしいところです。

この制約はソートコンテストで SIMD の幅増やす勝負とかにならないようにするためだそうです(それはそれで面白そうですが)

ソートコンテストというのは、製作した CPU 上で 1024 個の 16bit の符号付き整数をソートする速度を競うコンテストのことです。

必須参加ではありませんが、だいたいこのコンテストに参加して上位を狙うのを目標にする班が多いようです。


とりあえず一通り説明したので、これからは日記形式でやったことを説明していきます。

日記

4/13

実験初日です。

ハードウェアにはめちゃくちゃ苦手意識があるので気が重かったです。

初週はまだ CPU を作らないようで、HDL の説明を軽くされたあと、導入課題として個人で 10 進カウンタを作って 7 セグ LED に表示するというものが出ました。

カウンタ自体はそう難しくないんですが、 LED への出力の仕様がよく分からずハマりました。

こういうハードウェア部分でハマって、マニュアルを見ても分からないときは早めに TA に相談するのが良いと思います。

▲ハードウェア難しすぎて絶望する joisino 氏

4/14

まだカウンタが終わらないので作り続けます。


昼になった時点で CPU 製作の班分けが発表されました。

僕のペアは kmcyuma くんでした。

KMC の競技プログラミング勢ということで、気心が知れて、プログラミングがとてもできる人なので助かりました。

ペアはたいへん重要なのですが、自分たちで選べる訳ではなく、指定されます。

これから実験 3 に挑む人は良い人と当たるために春休みのうちに徳を積んでおきましょう。


午後は、SIMPLE アーキテクチャの説明と git の使い方説明会がありました。

今年は全員 HDL(Verilog HDL か VHDL) で CPU を作ることになったのですが、去年までは HDL で作る班と CAD でポチポチ配線する班があったそうです。

CAD で CPU 配線するの激ヤバだと思うんですが、今年は全員 HDL ということで良かったです。

僕は Verilog HDL よりも System Verilog の方が良かったのでそれでもいいかと聞いたら OK が来たので System Verilog で作ることにしました。


なんとかこの日のうちにカウンタを作り終えて、レポートを書き終わるところまでたどり着きました。

レポート部分が意外と重いので注意してください。


最後の 1 時間くらいは相方と今後の CPU 製作について打ち合わせしました。

だいたい次のようなことを相談しました。

  • 相方はシミュレータとアセンブラとソートプログラムを作る。
  • 僕は CPU を作る。
  • とりあえず来週くらいには単位コアを作って精神を安定させる。
  • 単位コアはすぐに捨てていい感じのコアをつくりはじめる。
  • さすがにパイプライン化はしたい。
  • OoO とかスーパースカラ化もできればやりたい。
  • ソートコンテストで 1 位になるのを目標にする。
4/18

CPU が完成しました

製作パートどこいったんだよ製作記じゃなかったのかよという感じですが僕自身もビックリするくらいすぐ完成してしまいました。

マイクロアーキテクチャの図を見ながら、ひとつずつ部品を作って配線していくと出来上がります(それはそう)

コアを作る上でオススメなのは

  • SIMPLE/B というマイクロアーキテクチャが参考に上がっていますが、あれよりもパタヘネに載ってるやつのほうが慣れてて書きやすいです(これは人によりそう)
  • コンパイルに 2 分くらいかかってつらいですが、Modelsim での RTL レベルのシミュレーションなら 1 秒くらいでコンパイル終わるのでこちらでバリバリデバッグして、最後にタイミングの確認とかの段階になって論理合成するのが良いです。
  • 機能を増やすにつれてどこに何があるのか混乱してくるので、コアの全体図を描いておくとわかりやすいです。
  • テスト用にいろいろな難易度のプログラムを書いておくと良いです。僕たちの班は入力をそのまま出力に返す、演算して出力する、1 から 10 までの和をループで求める、フィボナッチ数列の 10 番目を再帰で求める、バブルソートをするなどをテスト用に書いて、ハードがバグったら簡単なものからどこまで通るかを確認してバグ箇所を特定したりしていました。

特にふたつ目は生産性爆上がりなので、ぜひ実行してみてください。

ちなみにアセンブラとソートプログラムも相方がまだ作っていなかったので僕が作ってしまいました。

愚直なクイックソートで 4.96ms でした。

▲完動を喜ぶ joisino 氏

4/20

5 段パイプライン化しました。

パタヘネに有名な文言「誤信: パイプライン化は容易である」というのがありますが、意外とすんなりパイプライン化できました。

ここで特にパタヘネのマイクロアーキテクチャを参考にしたのが効いてきたのだと思います。

SIMPLE/B ベースでパイプライン化しようとするとハザード検出を自分で考えることになるのでバグらせやすいですが、パタヘネのマイクロアーキテクチャは本に書いてある上に講義でもパイプライン化の手順をやったはずなので、手際よくできるはずです。

フォワーディングを実装して、この日にソートコンテストに一度目の提出をしました。1.451ms でした。

4/21

そろそろ単位コアを捨てて新しいコアを作り始めてもよかったのですが、相方と話し合った結果、このままでも歴代最速を更新できるんじゃないかという気がしてきたのでもう少し作り続けようという結論になりました。

ちなみに歴代最速は 2012 年度の 4 コアプロセッサで 0.3680ms です。

4/23

分岐予測を実装、クロックを上げる、Jump And Link 命令すらなかったので追加するなどなどを行って歴代最速を更新しました

小さい時は挿入ソートにする & ピボット選択をがんばるクイックソートで 0.3650ms です。(これは提出していません)

もうこれ以上の高速化は限界っぽかったのでマルチコアにしようかということになってきました。

そういえば、このあたりは他の講義中もずっと CPU 作っていて、そのせいか週 3 くらいで CPU を作る夢を見ていた記憶があります。

特に CPU の配線を全て手作業で行わされる悪夢にうなされたのが印象に残っています。

4/27

基数ソート + 挿入ソートを書いて 0.1916 ms で提出しました。

アルゴリズムの変更でここまで速くなるのはアルゴリズムの勝利という感じがして嬉しかったですね。

twitter で自慢する joisino 氏

4/28

8 コアプロセッサが動いて 0.05040ms で提出しました。

▲記録の更新に浮かれる joisino 氏

結果的にこれがソートコンテストの最終提出になりました。

正直 4 月中にマルチコアが動くと思ってなかったので動いた時はめっちゃ嬉しかったです。

俺は 2 週間でマルチコアプロセッサを作ったぞってあと 10 年くらいは自慢するかもしれませんが聞き流してもらって構いません。

ちなみにメモリとかタイミング制約を限界まで取って 8 コアでコンパイルすると論理合成に 1 時間くらいかかって絶望するのでそこそこで我慢しましょう。6 割にするだけで 5 分くらいになります。

マルチコアですが、ソートコンテストが動く最低限の同期だけ実装したものならそこまでヤバくはありません。

僕の班でも、8 つのコアはほとんど独立で、メモリだけ共有しています。

動作するために特別やったことといえば、メモリの排他制御が必要なのでセマフォ入れたぐらいです。

あとは高速化のためにメモリアクセス権のプライオリティをクロックごとにコアに順番に割り当てていくことと、メモリの 2 ポート化(読み込み 1 / 書き込み 1)をしました。

ソートコンテストでは要素数 1024 個の配列をソートするのですが、ハードウェアの制約上メモリは 2 ポートまでしか実現できず、クロック数も 250 MHz が上限(といっても CPU を 250 MHz で動かすのは至難の業ですが)なので、仮に値の収納先がわかって毎クロック値を読み込み / 書き込みを行ったとしても 1024 / 250 MHz = 0.0041 ms くらいはかかります。

相当無理をした仮定でも 13 分の 1 くらいにしかならないことを考えるとこれ以上の本質的な高速化は厳しいという結論になり、これからはソートコンテスト以外の道を模索することになりました。(後から思うと、僕たちの CPU は 90MHz なので、パイプライン段数を増やしてクロックを上げればまだ高速化はできたと思います。)


ところで少し話は変わりますが、この実験では中間レポートというものがあり、我が班は非常に焦っていました。

というも、実験の評価項目では分担がうまくできているかが重視されているのですが、ここまで CPU は全て僕が作ってしまっていました。

ということで、この日に急遽相方に CPU の仕組みと System Verilog を教えて、細かい部品を作ってもらうことにしました。

4/29

ゴールデンウィークですが、コンパイラを作れたらなぁと思って LLVM のドキュメントを眺めたりしつつ遊んでいました。

あとゴールデンウィーク中にちょくちょくレポートを書きましたがかなり分量が多いので気をつけてください。

5/6

LLVM バックエンド難しすぎて挫折する。

5/7

とりあえず flex + bison で温かみのある昔ながらのコンパイラを作ることにしました。

ソースは C サブセットにするつもりだったのですが厳密にサブセットにするのは面倒だったので C サブセットっぽい何かになってしまいました。

この日は演算命令をコンパイルするくらいを実装しました。

5/8

コンパイラに比較、if、else、whileあたりを実装しました。

このあたりで気づいたのですが、16 ビットということもありアーキテクチャが弱すぎでコンパイラを作るのが相当大変です。

たとえば、分岐命令は上下 128 命令くらいまでしか飛べないので if 文などでそれ以上飛ぼうと思うと一旦別の場所に飛んでから遠くの場所に飛ぶ必要があります。

ここまではよくあるテクなのですが SIMPLE は即値分岐や即値代入も絶対値 128 くらいまでしか指定できないので困り果てました。

調べてみると MIPS は即値分岐で飛べない場所に行かないように配置するらしいのですが流石に 128 しか飛べないように配置するのでは制限が大きすぎます。

ラベルの x ビット目から y ビット目を表すラベルみたいなのを作って無理やり処理したのですがこういうのはどのように処理するのが正解だったのでしょうか。


あと、この日にようやく相方が作っていたシミュレータがまともに動くようになりました

もう既に完動してしまっていますが、いちいち波形シミュレータを使うのは面倒すぎるので、このシミュレータはこれからのコンパイラ製作に大いに役立ちました。

5/9

コンパイラに関数呼び出しを実装しました。

5/10

コンパイラに関数の引数や配列を実装しました。

このあたりで以下のフィボナッチ数を求めるプログラム程度ならコンパイルできるようになりました。

gist.github.com

5/11

中間レポートを提出しました。

相方もいい感じにパーツを作ってそれらを CPU に組み込んでなんとか協力した感じを醸し出しました。

5/12

この日は中間デモでした。

完成品を見せるというよりは進捗確認の意味合いが強い感じで、とりあえず 1 命令以上実機で動くことを見せるというものでした。

張り切った僕たちの班はすでにコンパイラの原型までできていたので、ちょっと C プログラムを書いてマンデルブロー集合を出力するデモをしました。

f:id:joisino:20170604175836p:plain
▲誤差がすごいマンデルブロー集合

FPU とかはないので固定小数の掛け算のライブラリを書いて動かしました。


とりあえず山場の中間デモまで終わったので最終デモでやる余興を何にするかという話になりました。

いろいろ考えてはみたのですがハードウェアの制約がかなり厳しいです。

FPGA からなにか使える端子が伸びていてディスプレイでも繋げられたらいろいろやりようがあると思うのですが、残念ながら出力は LED とブザーしかありません。

OS っぽいものを作る案もあったのですが、ハーバードアーキテクチャで作ってしまったのでプログラムの展開をどうするんだという話になって流れてしまいました(後から思うとハーバードでも何かしらは作れたと思うのですが)

とりあえずボードに乗っているハードウェアを最大限使ってテトリスを作ることにしました。

テトリスのプログラムは相方が作って、ハードウェアとコンパイラ方面を僕が作ることにしました。

とりあえず僕は LED の出力周りをいい感じにアーキテクチャから見えるようにしたりしました。

f:id:joisino:20170604175957j:plain
▲実験で使うボード

5/15

コンパイラに for や continue や break などを追加したりしていました。

5/19

ブザーで音楽を鳴らせるようにしました。

音楽部分はプロセッサから独立させてひたすらメモリからデータを読みだして BGM を鳴らし続けるようになっています。

アーキテクチャから見えるようにしたかったのですが、BGM を鳴らすとなるとタイマ割り込みとかが必要になってきそうなので諦めました(これも後から思うと色々やりようはあったと思います)

だいたいテトリスが動くようになりました。

割と大変だったのが、メモリの容量不足です。

実験で使うボードでは 16 キロワードくらいまでしかメモリが入らなくて、データ 8k 命令 8k にしているのですが、コンパイラが最適化をしてないこともあり、普通にテトリスを書くと溢れてしまいました。

なんとか相方に手で命令数を最適化したりしてもらっていました。

5/25

この時点になってもまだソートコンテストの参加者が僕たちだけだったので、まだ完成していない KMC 部員の席に行っては煽ったりしてました(ごめんね)

5/26

タイマーを追加して、リセットからの時間を取得できるようにしました。

他にもいろいろと微調整をしてデモ用のプログラムが完成しました。


さて、このあたりでまたまたレポート問題です。

最終レポートはこれまでのレポートよりも分量が多く、班で提出するレポートが 4 種類と個人で提出するのが 1 種類あります。

なかでもユーザーズマニュアルというのが大変で、「IPコア(ソフトコアプロセッサ)として提供することを想定し、プロセッサを使用するうえで必要十分な情報を記載すること」といういかにも大変そうな注意書きが書かれています。

特に僕たちの班はごちゃごちゃと機能を付け足してしまったので書くことが山盛りです。

そんなわけでこのあたりから実験中はずっとリファクタリングをしながらレポートを書き続ける回になりました。

6/1

デモ前日です。

デモはペアがそれぞれ絶対に喋らないといけないのに、相方はハードウェアの中身については知らないらしいのでいろいろとレクチャーして発表の分担を考えたりしました。

6/2

いよいよデモ当日です。

デモといってもスライドを作ってみんなの前で発表するわけではなく、TA と教員が班席まで回ってきて 10 分くらいプロセッサやプログラムの説明をする感じです。

知り合いの発表は聞きにいったりしていましたが。

テトリスはこんな感じに仕上がりました。

youtu.be

声が入っているので音は入れていませんが、プレイ中はコロブチカが流れます。

あと相方がプレイして僕が撮ってるのですがミスするたびに笑ってカメラを揺らしています。ごめんなさい。

これだけ色々言ったわりには大したことないようなという感じかもしれませんが、とにかくデモが終わった後はようやく終わったという開放感でいっぱいでした。

レポートもこの日のうちになんとか書き終えて提出することができました。

6/4

この記事を書いています。

感想

2 ヶ月弱、つらいことも多かったですが、振り返ってみると全体的に楽しかったと思います。もうやりたくはありませんが。

期間も短く班員も 2 人なのであまり大層なことはできませんが、こんな短期間で CPU 製作を一通り学べるのはものすごく良い経験だと思います。

僕たちの班も最後の方は若干だれてしまったので、全力疾走するにはこの位の期間が限度なのかもしれません。

色々やりたいことの中から、無理だと諦めたものもありましたが、最終的に作れたものには満足しています。

来年以降実験を受ける人たちは僕たちが諦めたものたちも含めて、僕たちの成果物なんかよりもっとすごいものを作ってください。(半分そのために記事を書いているので期待してますよ!)

的を射ているかは分かりませんが若干アドバイスです

  • OoO とスーパースカラ

- ソートコンテストをやるうちにいつの間にか目標から外れていました。というのは、通常実験ではアセンブリコードを手書きするので、相当のハザードを手で解消できてしまい OoO の恩恵をあまり受けられないというのと、そもそも 8 コア化するとすごい量のメモリアクセスがあってアクセスキュー待ちがボトルネックになるのでこのあたりの高速化テクの意味が無くなってしまったからです。ですが、正直このあたりの技術を実装するのを目標にしている人たちならソートコンテストは無視してもっと大規模なプログラムを目標に据えて、OoO とかスーパースカラを実装していくのがいいと思います。

  • second architecture

- 僕たちの班も最初は単位コアを作って新しいアーキテクチャに移ろうと考えていたのですが、結局最後まで first を建て増しし続けて終わりました。これについてはどちらが良いとも言えないと思います。もうちょっと実験期間が長ければ有用だと思うのですがなにしろ実験期間が短いので second を作る余裕はあまりありません。second を作ることにするならちゃんとペースを考えたほうが良いと思います。

  • OS

- OS を作りたいなら最初の設計の段階から決めてかかったほうが良いです。ハーバードで作るよりノイマン型で作ったほうがいろいろやりやすいと思うし、割り込みとかもあんまりすぐに建て増しできる感じではないので最初の設計で考えたほうがよいはずです。たぶんハードウェアに詳しくない人は最初からこのへん考えるのは難しい(少なくとも僕はそうだった)ので、OS 作ったりする場合は second 作るのが有用なのかもしれません。

  • 出力

- ボードに出力が全然ないと言いましたが、唯一出てるリッチな出力がコンフィギュレーション用の USB Blaster です。全く知りませんが、これを使っていい感じにシリアル通信したりできるかもしれません。最後の方になって気づいたのですが結局調べる時間もないまま終わりました。これが使えるならできることが一気に広がると思うので調べてみると良いかもしれません。


レポジトリを置いておきます(剽窃があるといけないので公開しないようにと先生が言っていましたが、頼んだら許可してくれました。来年以降受講する人は絶対に剽窃しないでくださいね。)

github.com

一息つく間もなく来週からはソフトウェア実験がはじまるのでがんばります。

参考文献

ためになった本たちを紹介しておきます。

CPUの創りかた

CPUの創りかた

めっちゃいい本。あと絵がかわいい。

今回の実験で使ったわけではなく昔読んだものですが、この本のおかげで CPU がどんな風にできているのか理解できた記憶があります。

フリップフロップのイメージはまだこの本に書いてあるカメラのページを思い出します。

パタヘネとか読んだことあるならもう読む必要があるかは分かりませんが、ハードウェアがめちゃくちゃ苦手な意識のある人は読んでみるといいかもしれません。

コンピュータの構成と設計 第5版 上

コンピュータの構成と設計 第5版 上

コンピュータの構成と設計 第5版 下

コンピュータの構成と設計 第5版 下

いわゆるパタヘネ。

講義とかで使ったことがあるはずです。相方はなぜか持ってませんでした。

これがないとさすがに実験 3 を乗り越えるのは難しいのでちゃんと買って読みましょう。実験 3 では特に上巻が重要です。


ディジタル回路設計とコンピュータアーキテクチャ[ARM版]

ディジタル回路設計とコンピュータアーキテクチャ[ARM版]

ディジタル回路設計とコンピュータアーキテクチャ (IT Architects' Archiveクラシックモダン・コンピューティング)

ディジタル回路設計とコンピュータアーキテクチャ (IT Architects' Archiveクラシックモダン・コンピューティング)

パタヘネに比べるとあまり有名ではないかもしれません。

僕は上の ARM 版を読みました。

概念自体はパタヘネを読んだことがあるならあまり新しいことは無いですが、この本の良いところは System VerilogVHDL (通常版は Verilog HDL と VHDL らしい?)のサンプルコードが載ってあることです。

最後にはシンプルなシングルサイクルの ARM プロセッサのコードまで載っています。

僕は System Verilog をだいたいこの本で学びました。

HDL を学べる資料は貴重なので、実験初期に HDL がよく分からなかったら読んでみると良いかもしれません。

コンピュータ設計の基礎

コンピュータ設計の基礎

高性能コンピュータ技術の基礎

高性能コンピュータ技術の基礎

kindle でセールしてたので買いました。

上のコンピュータ設計の基礎については、パタヘネに書いてあることがほとんどです。

下の高性能コンピュータ技術の基礎は、OoO とかスーパースカラがかなり丁寧に解説してあります。

OoO とかスーパースカラを実装しようかと思っていて、ヘネパタは高い/重いと思う人は読んでみるとよいと思います。

ヘネシー&パターソン コンピュータアーキテクチャ 定量的アプローチ 第5版

ヘネシー&パターソン コンピュータアーキテクチャ 定量的アプローチ 第5版

いわゆるヘネパタ。

OoO とかスーパースカラあたりの部分だけ読みました。

実験で使うとしたらそのあたりだと思います。

僕もちゃんと読めてないのでまた時間があるときに挑戦したいです。


nullpo-head.hateblo.jp
kw-udon.hatenablog.com
sueki743.hatenablog.jp
github.com

某大学某学科の CPU 実験のすごい人たちの記事(一部)です。

ほかにも「CPU実験」とかで調べるとたくさん出てきます。

この実験がはじまる前〜初期くらいはいろんな製作記を読みまくっていました。

読み物としても楽しいし、モチベも上がるのでオススメです。



とても長い記事になってしまいましたが、最後まで読んでいただきありがとうございました。

最小全域有向木(m log n)

明日、KMC の組合せ最適化読書会でやる予定なのですが、少し調べた限りでは日本語の解説が見つからなかったので書いてみます。(注:組合せ最適化本体には O(nm) のアルゴリズムしか載っていません。)

 

こういうアルゴリズムに慣れていない人向けに書いたつもりなのでプロ各位にはまどろっこくて分かりづらい表現になったかもしれません。ゆるして。

最小全域有向木について

辺にコストのついた有向グラフが与えられて一つの頂点が指定されたとき、その頂点を根とする全域有向木でコスト最小のものを求める問題です。

 

根用の頂点を追加して、各点にコスト INF の辺を張れば頂点を指定しない最小全域有向木が解けます。コスト 0 で張ると最小有向森です。

 

有名な解法に Edmonds / Chu-Liu のアルゴリズムがあります。この計算量は O( nm ) で、組合せ最適化や Spaghetti Source - 最小全域有向木(Chu-Liu/Edmonds) に載っています。今から説明する O( m log n ) の解法は Tarjan [1977] によるもので、このアルゴリズムの亜種(というか高速化しただけ)です。

アルゴリズム

  1. 根以外の頂点を適当に選びます
  2. 今いる頂点 v に入ってくる(自己ループでない)辺のうちコストが一番小さい辺 ( u -> v ) を取ります。今いる頂点が圧縮された頂点なら、もとのサイクルで v に入ってくる辺を使う辺から除きます。u に移り、( u -> v ) を使う辺に追加します。
  3. 使う辺でサイクルができたら、サイクルを一点に圧縮します。このとき、サイクル外からサイクル上の頂点 w に入ってくる辺のコストを、w に入ってくるサイクル辺のコストだけ減らします。
  4. まだ根と繋がらなかったら 2 に戻ります。繋がったときは、他に頂点が無いなら終了。まだあるなら適当に頂点を選んで 2 に戻ります。

やることはすごく簡単です。少し下で解説をしているのでこれを読んで分からなければそっちを読んでみてください。(むしろこれだけで分かったらすごい)

解説

有向木では、根以外の入次数は 1 です。(もちろん根は 0 です。)なので、各頂点について入ってくる辺をちょうど一つ選ぶわけです。このアルゴリズムでは、手順 2 で貪欲に一番コストが小さい辺を選んでいっています。サイクルができなければこれが一番良いことはすぐに分かると思います。

 

厄介なのはサイクルができたときです。サイクルができた時は、そこで詰んでしまうので、サイクルを「開いて」やらなければいけませんf:id:joisino:20170111142108p:plain

サイクルに繋がる辺を選ぶ訳ですが、上の図のように開くと総コストが d - c だけ増えます。(コスト c の辺を使うのをやめてコスト d の辺を使うため。)このアルゴリズムではこのコストについて貪欲に小さいものを選びます。アルゴリズムの手順 3 で「このとき、サイクル外からサイクル上の頂点 w に入ってくる辺のコストを、w に入ってくるサイクル辺のコストだけ減らします。」と言っているのはそういうことです。(「サイクル外からサイクル上の頂点 w に入ってくる辺のコスト」は図の d に対応し、「w に入ってくるサイクル辺のコスト」は図の c に対応します。)

 

サイクルができるたびに上のように対応して、サイクル(だったもの)はそれ以降変更しないように一点に圧縮してしまいます。(これは、正当性の証明のところで示すようにサイクルの一辺以外を全て含むような最小全域有向木があるので OK です。)

 

入ってくる辺を貪欲に選んで、サイクルを貪欲に切って圧縮するというのは Edmonds のアルゴリズムも同じです。違うところは、Edmonds では全部の頂点について入ってくる辺を選んでから圧縮するのを繰り返しているのに対し、このアルゴリズムでは DFS の要領で一つずつ頂点を処理していくことです。

 

現在の頂点から辺を逆に辿ってパスが伸びるか、サイクルができても圧縮してしまうので、現在の処理している辺たちは常にパスのように見えることになります。

 

こうすると、辺を辿るたびに、パスが 1 つ伸びるか、サイクルができて、サイクルの大きさくらいの頂点が消えるので、 2n ステップくらいで止まることが分かります。

正当性の証明

Edmonds のアルゴリズムの正当性の証明とほとんど同じです。そっちを知っている人はこれも証明できると思うので自力でやってみてもいいかもしれません。

 

証明は圧縮する回数についての帰納法で行います。

 

圧縮する回数が 0 回(圧縮しない)とき

これは、解説のところでも言及しましたが、ほとんど明らかだと思います。

このアルゴリズムで得られた有向木 T と、任意の有向木 S を比べたとき、各頂点に入ってくる辺同士についてコストを比べると、T の辺は入ってくる辺の中で一番コストが小さいものを選んでいるので、もちろん T の辺のコストが S の辺のコスト以下になります。ということは、総和をとっても T 全体のコストは S 全体のコスト以下です。

 

圧縮する回数が k + 1 回のとき

まず、最初に圧縮することになるサイクルを C とします。 C は L 本の辺からなるとします。

 

ここで、なんとサイクル C の辺のうち、L - 1 本の辺を使う最小全域有向木が存在することがいえます。(この証明は組合せ最適化にも載っています。慣れない人には少し難しいかもしれないので分からなかったら認めてしまって次に進んでも良いかもしれません。飛ばす場合は「補題の証明終わり」というところまで進んでください。)

 

背理法により補題を証明します。

最小全域有向木のうち、サイクル C の辺を使う本数が最も多いものを A とします。C の辺のうち K ( >= 2 ) 本使わないがあると仮定します。

C の辺のうち、A で使われていない辺を、一周回る順番に ( a_1, b_1 ), ..., ( a_K, b_K ) とします。ここで、i = 1, 2, ..., K について A には b_i から b_{i-1} にパスがあることを示します。( i = 1 のときには i-1 は K を表していると思ってください。)

( a_i, b_i ) が使われていないのだから、A には b_i  に入ってくる他の辺 e があるはずです。

e を使うのやめて ( a_i, b_i ) を使うことにしてみます。

( a_i, b_i ) のコストは b_i に入ってくる辺の中で一番小さいのでコストの総和は変更前以下になります。変更後もちゃんと有向木だったとすると、コストが真に小さくなっても A が最小であることに反するし、同じでも C のうち使う辺の本数が 1 本多いので、 A のとり方に違反します。

考えられるのは使う辺を変えたことでサイクルができてしまったということです。

これは、A において、b_i から a_i にパスがあったということです。a_i からそのパスを逆向きにたどって行くと以下の図から分かるように b_{i-1} にたどり着きます。(入次数が 1 なので一意にたどれます。また、(a_{i-1}, b_{i-1}) は使わない C の辺のうち一つ前の辺なので、間の辺は全て A でも使われています。)

f:id:joisino:20170111211948p:plain

つまり、A 上には b_i から b_{i-1} にパスがあるということです。(b_i から a_{i-1} へのパスの一部分。)

これでパスの存在は示せました。

しかし、これは b_K からb_{K-1} にパスがあり、b_{K-1} から b_{K-2} にパスがあり、...、b_1 から b_K にパスがあるということになり、A にサイクルがあるということになります。

これは A が有向木であるという仮定に反します。

よって、最小全域有向木のうち、サイクル C の辺を使う本数が最も多いものは L - 1 本の辺を使うということになります。

補題の証明終わり

 

もとの証明に戻ります。圧縮する回数が k+1 回のときにアルゴリズムで得られた有向木が最小全域有向木であることを示すのが目的でした。

 

このアルゴリズムで得られた有向木を T とし、サイクル C を圧縮したときにできるグラフ(以下圧縮グラフと呼びます)で T に相当する有向木を T' とします。帰納法の仮定より、 T' は圧縮グラフでの最小全域有向木です。

補題により存在が示された、C の辺のうち L - 1 本を使う最小有向木を T* とし、圧縮グラフで T* に相当する有向木を T*' とします。

ここで、 T のコストは T' のコストにサイクル C に含まれる全ての辺のコストの和を足したものとなります。T* についても同様に T*' のコストに C のコストを足したものになります。

これは、 T' で C に相当する部分以外のコストは同じで、 C は、1 本以外全て使うことになりますが、使わない辺については C に入ってくる辺のコストの変更によって調整されているので、このようになります。

よって、( T のコスト ) = ( T' のコスト ) + ( C のコスト ) <= ( T*' のコスト ) + ( C のコスト ) = ( T* のコスト )

となり、 T が最小全域有向木であることが分かります。真ん中の不等号は T' が圧縮グラフ上での最小全域有向木であることからです。

f:id:joisino:20170111225913p:plain

 以上、帰納法によって正当性が示されました。

 

計算量

計算量を調べます。

解説のところで言及したように、1 ステップ ごとにパスが伸びるか、頂点がマージされて減るのでアルゴリズムの手順 2, 3 を実行する回数は O(n) 回です。

 

各頂点について入ってくる辺を隣接行列でもって愚直に管理するとします。手順 2 で最小値を求めるのは毎回 O(n) で、これは O(n) 回行われます。手順 3 で圧縮するのも、1 つの点につき O(n) でマージできて、合計高々 n 頂点しかマージされないので、結局全体の計算量は O(n^2) になります。

密グラフでこのアルゴリズムを走らせたいときはこれ以上速くなりようがないのでこれで終了です。

 

次に疎グラフで O( m log n ) を達成するやり方を考えます。

dijkstra 法などを学んだ人ならなんとなく分かると思いますが、辺をヒープ(prioirty queue)で管理します。

こうすると手順 2 で最小値を求めるのは毎回 O(1) になります。

 

問題は圧縮です。ヒープをうまくマージしたりコストを一様に減らしたりする方法なんてあるのかと思いますがあります。

一つには、マージテクを使うとできます。これで O( m log n + n log^2 n ) とかになります。

もう一つには、meldable heap というものを使います。これはマージが効率よくできるヒープのことで、leftist heap や skew heap などがあります。blog - Leftist Heap & Skew Heap に詳しいのでそちらを参照してみてください。これで O( log n ) でマージできます。また、コストを一様に減らす方法ですが、ヒープのノードに一様に足された数を持っておいてマージするときに遅延伝播すればうまくいきます。(segtree の遅延伝播と全く同じです。)これで全体で O( m log n ) になります。おめでとうございます。

 

具体的な実装例は使い道のところを参照してみてください。

 

ちなみに、fibonacci heap を使うとマージが O(1) でできます。コストを一様に減らす解析は読んでないので良く分かっていませんが Gabow et al. [1986] によると全体で O( m + n log n ) になるらしいです。誰か読んで分かりやすく教えて。

使い道

競技プログラミングでは今のところあまり実用性はないかもしれませんが、とりあえず首都(The Capital | Aizu Online Judge)をアルゴリズムパンチで殴り倒せます。

 

実装例です。多めにコメントを書きました。MSA という関数が、 r を根とする最小全域有向木のコストを求める関数です。「ここが本質です。」と書いてあるループ部分が最小全域有向木のメインの部分です。

The Capital ( AOJ 2647 )

 

終わりに

この記事を書くまでは最小全域有向木は無向の最小全域木よりも(少なくとも競技プログラミングで使うようなアルゴリズムでは)有意に計算量が大きいものだと思っていたんですが、割と簡単なアルゴリズムで似たような計算量が達成できるのにビックリしました。

最小全域有向木を使う問題はあんまり見ないですが、n = 10^5 とかで割と簡単に書けるので使いようがあるんじゃないかと思いました。(浸透しないとただの知識ゲーだけど)

 

 

ここが分からないとかここ間違ってるよとかあれば気軽に言ってください。

最後まで読んでいただきありがとうございました。

 

(1/11 23:33 マージテクでも少しいい感じにできるよということなど少し追記しました)

参考文献

[1] B.コルテ, J.フィーゲン [2012]: 組合せ最適化 第二版. 丸善, 2012, 第 6 章.

[2] Gabow, H.N., Galil, Z., Spencer, T., and Tarjan, R.E. [1986]: Efficient algorithm for finding minimum spanning trees in undirected and directed graphs. Combinatorica 6 (1986), 109-122

[3] Tarjan, R.E. [1977]: Fining optimum branchings, Networks (1977), 25-35

2015ふりかえりと2016めも


昨日振り返りするの忘れていたので元日に振り返りと目標どっちも書こう

 

2015年の振り返り
こんなことを買いていたのでその振り返り

 

大学に入る
はい

 

赤くなる
TC 1584 -> 1827 (+243)
CF 1876 -> 2150 (+274)
うーんダメ
一瞬だけCF赤くなったけど色基準変更されてレートも落ちてしまった
来年はちゃんと精進して赤くなるぞ

 

ゆゆ式二期が決まる
ダメですね......

 

良い一年だったけど目標は全然達成できてないですね
2015年は全然競プロできなかったので今年は精進するぞ

 

2016年めも
TC,CF赤くなる
ゆゆ式二期が決まる 

櫟井唯ちゃんの画像を無限に生成する話

いくら待てどゆゆ式二期の発表がないのでそろそろ僕の櫟井唯ちゃん資源が枯渇してしまいそうです

そこで今話題のニューラルネットワークに唯ちゃんの画像を無限に生成してもらうことにしました

 

とりあえずこちらがデモです(設定の読み込みにかなり時間がかかります)

Mugen Yuichan

 

ランダムに生成したサンプルです

一応はっきりと唯ちゃんだと分かる

f:id:joisino:20150909230636p:plainf:id:joisino:20150909230646p:plainf:id:joisino:20150909230652p:plainf:id:joisino:20150909230656p:plainf:id:joisino:20150909230700p:plain

 

使ったのはDenoising Autoencoder(DAE)

ふつうのAutoencoderの入力にノイズを加えて学習させるだけです(今回はガウス分布のノイズを加えました)

ノイズ除去に使えたり生成モデルを作れたりします

DAEについては深層学習 (機械学習プロフェッショナルシリーズ)を参考にしました

 

作り方

まずはゆゆ式の本編から唯ちゃんの顔部分だけ切り抜きます

この作業はこのページを参考にさせていただきました

ご注文はDeep Learningですか? - kivantium活動日記

ゆゆ式1話と2話でだいたい1000枚の唯ちゃんの画像が手に入りました

 

次にニューラルネットワークの構成ですが、夏季セミのときに作ったのを流用しました

JOI夏季セミナー2015チューター記 - ジョイジョイジョイ

 

ネットワークは3層で、入力画像が96*96*3、中間層が128、出力画像が96*96*3です。

本当はもう少し中間層を増やしたかったのですが公開のときのサイズの都合上128にしました(これでも重い)

 

あとは普通に学習させるだけ

学習方法はSGD+Momentum(0.9)

学習係数は0.01

デモのネットワークはだいたい100epochくらいのもので、学習は1時間くらいで終わりました

 

やりたいこと

多層にすると精度上がるかなぁ

変分自己符号化器(VAE)を使ってみたい

自前のライブラリだと速度や実装コスト面でつらいのでそろそろライブラリの使い方を覚えたい

 

 

最後にリポジトリです

github.com

JOI夏季セミナー2015チューター記

 

JOIの夏季セミナーにチューターとして参加してきました。

本が6冊なのになぜかチューターは5人だったので僕は『プログラミング言語の基礎概念』と『深層学習』の2冊を担当することになりました。

 

1日目

catupperと共にヌエックに到着

自己紹介する(チューター→生徒の順)

ぼく「最近興味があるのは深層学習です」(伏線)

本決めとかする

セミナーはじまる(プログラミング言語の基礎概念』を担当)

生徒優秀すぎるでしょ...(何もできずただ座っている)

ヌエックのご飯おいしい

1日目は談話室なかったのでちょっと集まってすぐ寝る

 

2日目

セミナーと講義

師匠に私は熟女好きですされる

わたあめ大人気

今日からは談話室が使える

がっこうぐらしをつけながら枯山水をやる

枯山水たのしい

hogloidの徳の高さには勝てなかったよ...

ここでめぐねえが死ぬ

寝る

 

3日目

catupperの班(関数プログラミング)と相部屋になる

絵しりとりなどする

catupperにHaskellを教わる

ABCの問題をHaskellで解く

Haskell楽しい('ω' )三('ω')三( 'ω')

夕食時、わたあめ機が壊れていた(けっきょく食べられなかった)

シンデレラ見たかったけど談話室は24時に閉まるので見られず死

この日は談話室では特になにもしなかった

 

4日目

深層学習と相部屋になる

potetisenseiがkaggleの犬と猫を見分けるのをやるらしい

面白そうなので勝負を申し込む

画像読み込む段階で挫折しそうになる

potetiにライブラリを教えてもらってなんとか読み込む(これをつかった)

とりあえず昔書いた単純なパーセプトロンに学習させてみる

49.1%

ランダムにラベルつけた期待値の方が高いじゃん...

MNIST(手書き数字認識)を学習させたら9割超えるんだけどなぁ...

Deeplearningの必要性を感じたので畳み込みニューラルネットワーク(CNN)をpotetiから一通り教わる

協力プレイしない?という話になる

基礎はpotetiが既に作っていたのでぼくは畳み込み層の逆伝播とプーリング層を実装することに

セミナーが終わったので談話室で実装することに

hogloidとdegwerがウェイについて話している

hogloidはウェイ

catupperはウェイ

人類皆ウェイ

全然終わらないのでぼくの部屋で実装することに

開発の都合上gitを入れることに

パソコン弱いのでgitインストールできない(結局potetiとcatupperにめっちゃ手伝ってもらった)

アイマス曲を流して歌いながらぐだぐだ実装する

いつのまにか部屋にめっちゃ人が集まっていた

そしてだんだん外が明るくなりはじめる

potetiがスライド一通り作り終えたようなので一緒に考えながら実装する

一応完成した

20分くらい学習させてみる

50.0%

 

5日目

結局寝ないまま5日目の朝を迎える

potetisensei「深層学習で死にそう」

そのあとの紆余曲折はだいたいここに書いてあります

www.slideshare.net

(ここでの正解率は全てMNISTの正解率で結局犬と猫のにはチャレンジできなかった)

 

ア、皆の発表ちゃんと聞いてたからね?

ここでdegwerに私は熟女好きですされる

 

まぁ一からCNN書いて理解も深まったし、なにより動いてくれたのでめでたしめでたし

 

 

...?

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

K理事長「分からなかったことに納得するまでが夏季セミナーです。」

 

6日目

基本的にレイヤーの実装が良くないというはなしになる

また設計やり直すか?とか話す

 

7日目

 

ConvNetJSと比べてパフォーマンスが悪いなぁという話になる

ConvNetJSでは活性化関数にReLUを使ってるけどこちらでReLUを使うと重みが発散して死ぬ

ConvNetJSのコードを見て学ぶ

重み制限を実装する

このおかげでReLU使って重み発散しなくなる(ただしパフォーマンスは悪い)

6層のCNNでReLU使って79.66%が出る

逆伝播のデルタを初期化していないという深刻なバグを見つける(これのせいで変な方向に重みが動いていた)

直したけどパフォーマンス全然変わらない

これもう分かんねぇな

potetiがレイヤーの設計改めて実装する(プロ)

 

8日目

新しい設計でテストする

4層だと学習するんだけど6層だと学習しない

ConvNetJSの設定みて初期値とか学習率を変えるとめっちゃパフォーマンスよくなる(ただし依然6層では学習しない)

でもまだConvNetJSの方がパフォーマンス良い

向こうはAdadelta使ってるからだろうなという結論になる

とりあえずmomentum実装する

まぁいい感じ

momentumの符号逆であることに気付く

直したけど精度変わらず

これもう分かんねぇな

momentum有りだと6層で学習するようになる

 

9日目

momentum有りの6層で94.20パーセントが出る(大勝利)

そろそろ犬と猫に挑戦してもいいんじゃない?

犬猫は80パーセントを目標にして、達成したらやめると宣言する(この時点で全く手を付けていなかったので80パーセントという数字は適当)

この見切り発車を後で後悔することになる

 

biasの更新に学習率をかけていないというバグをみつける

バグを直すを学習が遅くなる

これもう分かんねぇな

 

10日目

Adagradを実装する

Adagrad最強(めっちゃ学習が速くなった)(しかもReLUでもいい感じに学習する)

Pythonインストールしてpotetiのスクリプトいじって犬と猫の画像をリサイズする

画像のサイズ128*128にすると計算遅すぎてまともに学習しないので32*32に

とりあえず4層(input->conv->pool->fully->output)で学習させてみる

53.89パーセント(死)

一応統計的に有意に学習してます(白目)

8層(input->conv->pool->conv->pool->conv->pool->fully->output)で学習させる

59.9パーセント

厳しすぎる

8層に3時間くらい学習させて64.057パーセント

とりあえず学習させながら寝る

 

11日目

朝起きて確認

68.960パーセント

うーん

フィルタ増やしたいけど増やすと計算が遅くなる

計算資源の重要性を思い知る

amazonEC2と自宅のパソコンを使っていろいろパラメータをチューニングする

9層のCNN(input->conv->pool->conv->pool->conv->pool->fully->fuully->output)で71.794パーセントが出る

このあたりで80パーセントにしたことを後悔しはじめる

72パーセントとか言っとけばよかった(くっ)

 

12日目

画像の大きさを36*36にして、そのうちランダムで32*32を切り取るようにする

チューニングしながら学習させまくる

 

13日目

なかなか記録伸びず

9層CNNに40時間くらい学習させて75.874パーセントがこの時点で最高

dropout実装するか~という話になる

dropout実装する(二人で分担した)

とりあえず明日まで昔のCNNに学習させて、無理そうだったらdropout付きのに切り替えることにする

 

14日目

8epoch(50時間くらい)終わって77.794パーセント

つらい

というか8epochに50時間かかるの遅すぎませんかねぇ(1epochで2万画像)

ちょっと(3割くらい)プログラム高速化してdropout付きのに切り替える

一応昔のも走らせ続ける

 

 

15日目~18日目

ひたすら学習させる(放置)

6epoch 74.686パーセント

8epoch 77.394パーセント

9epoch 77.909パーセント

10epoch 79.268パーセント

12epoch 78.869パーセント

13epoch 79.806パーセント

 f:id:joisino:20150829201021p:plain

 

 \パンッ/ヨッシャアアアアアアアアアアアアwwwwwwwwwwwwww(高い声で)キタァwwwwwwwwwwウワァヤッタアアアwwwwwwwwwwwwwwwww

 

くぅ~疲れましたw これにて完結です!
実は、potetiに競争申し込んだら協力を持ちかけられたのが始まりでした

云々

 

最後にまとめ

 

まとめ

Deeplearningの闇

  • バグってなくてもパラメータ次第では学習してくれないのでバグのせいかパラメータのせいかの見分けがつかない
  • 下のようなCNNの構成とパラメータを探してもあまりない(実験系の論文や強いライブラリを使ったものはあるけど計算資源の都合上真似できない)
  • バグってても学習するのでバグってることに気付かない
  • 計算資源を無限に欲してしまう
  • 深層学習のアルゴリズムの解説に「理屈はないけど経験上うまくいく」というのが多くて結果の予測がむずかしい

 

最終的なCNNの構成

  • input 32*32 channel 3
  • conv size:5*5 channel 16
  • pool size 2*2 stride 2
  • dropout 0.25
  • conv size 5*5 channel 32
  • pool size 2*2 stride 2
  • dropout 0.25
  • conv size 5*5 channel 64
  • pool size 2*2 stride 2
  • droput 0.25
  • fully channel 64
  • dropout 0.5
  • fully channel 2

活性化関数は全てReLUで最後だけsoftmax

学習係数は0.01

学習方法はAdagrad

画像を全て36*36にリサイズして、うち32*32をランダムで選んで学習させた(推測時は16通り全て試して多数決)

 

ちなみにdropoutなしの同じ構成は20epoch学習させても77.886パーセントでした

 

構成はnagadomi/kaggle-cifar10-torch7 · GitHubを多く参考にしました。

 

僕たちのリポジトリ

github.com

 

 

誘ってくれたアンド最後まで付き合ってくれたpotetisenseiへの感謝の言葉で終わりにします

サンキューポテチ!

PCK2014本選参加記

1日目

  • 起床成功
  • 伊丹空港到着
  • 飛行機でウキウキ
  • 会津
  • @DEGwer3456と@namonakiaccountに会う
  • 優勝おめでとうございますと伝える
  • 実際優勝した(完全にプロ)
  • バスで大学へ
  • 受付
  • 開会式
  • 競技
  • 7完3WAだった(5位)
  • バスでホテルへ
  • @potetisenseiと初めて会う
  • 神秘的だった
  • 交流会ではJOIerとばかり交流する
  • 部屋へ
  • @HIR180と@yokozuna_57の部屋に風船が集まっているらしい
  • 持っていく
  • そのままIs部屋に居つく
  • @satashunから高槻駅やよい軒閉店の知らせを聞いて驚愕する(後で調べたらリニューアルらしい)
  • 雑談していたら皆倒れていったので部屋に戻って寝ることにする

 

2日目

  • 起床成功
  • 朝食
  • 朝食解いた人は意外と少なかった
  • バスで大学へ
  • 自由時間
  • 鶴ヶ城
  • ラーメン食べる
  • おいしい
  • 大学に戻る
  • @potetisensei「Is、三上和馬、DEDwerの7名が写真撮影に間に合わない」
  • 写真撮影開始
  • 予選の成績順で並んだので前の方スッカスカ
  • JOIerは闇
  • 並び調整してる間に7名到着
  • 撮影
  • 大学見学
  • 表彰式
  • 5位(再掲)
  • 三上和馬のミドルネームの一部と化す
  • 会津若松駅
  • 高槻
  • 帰宅

 

感想

  • たいしたミスも無かったのに5位なのはつらい
  • 求められる速解き力、実装力
  • 受験終わったら競プロ精進します