ふるつき

私は素直に思ったことを書いてるけど、上から目線だって言われる

SuperCon(スーパーコンピューティングコンテスト)2016の本選に出た

SuperCon本選でチームワークを発揮したので、kingyo(は3位だった。すごいな。

SuperConについて

よくわからなかったが、SuperComputerのすっごい資源をつかって計算させてくれるプログラミングコンテストだと思う。今年は東工大TSUBAMEというスパコンを使った。

予選

私は予選の問題はさっぱりわからなかったので。チームメイトが去年JOIの本選にでるなど健闘していたのでJavaで解コードを書いてもらい、C言語に移すなどしていた。要項にはANSI Cに準拠すること、とあったが、ANSI CがどんなCか全然わからず、不安のなか移植をした。

枝刈り全探索みたいなコードだったと思う。C言語のよくわからない型挙動に苦戦しつつなんとか動くコードにして、提出した。このときは予選突破があるとは思ってなかった。

それからn日くらいたって予選突破報告がTLに流れ始めたが、我らのチームにはメールが来ず、やはりだめか……と言っていた。しかし本戦出場の意思がないチームがあったのか、なんか一番お尻につっこまれて本選にでられることになった。かなり嬉しかった。

本選

本選では5日間阪大に通った。家からだと2.5時間くらいかかるので移動が長かった。 それはそれとして、とりあえず本選で問題の説明がされたりした。できるだけ良いスコアを出す系の問題だった。

私はそういう問題の対策は山登り法と焼きなまし法しか知らなかったので、焼きなましっぽいのの実装を始めた。チームメイトはランダムではない方法を模索したり、GPUで評価値を求めるプログラムを書いたりしていた。

二日目の終わりくらいにはほとんど焼きなまし完成みたいな感じで、動くコードができていた。手法としては、グラフ中の四点(二点同士が辺で結ばれている、などグラフの正則性を保つような制約つきでランダムに選択したもの)の辺をつなぎ替えるみたいな感じだった。これをtsunaginao_c関数と名づけて、ファイル名をtsunaginao.cとしてうまいじゃんと笑っていたが、後にcudaを導入してtsunaginao.cuになったりした。

あとは重み付けとか、評価関数とかを書いていた。評価関数のワーシャルフロイドをバグらせていたのは笑える。

三日目くらいにはちゃんと動くようになっていた。サンプルの小さいケースを食べて値が出る! などと無邪気に遊んでいた。この時点では初期グラフの良さがそのまま出力に直結する感じだったので、初期グラフをn回つくれるように改良したりしていた。

提出練習でもそれなりに動いたので手応えを感じていた。チームメイトの一人が行列積のGPU高速化番を作ってくれていたのでそれを使ったら最大ケースで2.5s程度で評価関数が動作していい感じ。本当はもっと早く、10倍くらいにはなるらしい。

4日目は初期グラフをランダムではなく規則的に並べる方針を採用した。初期値は悪いが、焼きなましと相性が良かった。初期グラフが綺麗なのでプログラム名はkireiとなった。

さらに辺の交換ではなくて色の交換を行った。これ自体はあんまり機能しなかったがこれとtsunaginao_cを組み合わせるといい結果がでるケースがあり採用となった。これを用いたプログラムがchimeraとkirei_swapvと名付けられた。

さらに、競技直前に、「ある程度結果を出した後のグラフからもう一回やりたくない?」という話が出てこれの爆速実装を行った。これは初期グラフ生成のかわりにグラフを読み込む処理を加えるだけなのでそんなに難しくはない。しかしここまでで、gpu(これが最初のプログラム)、kirei、chimera、kirei_swapvと四つのプログラムを作ってしまい(それぞれコピーしてディレクトリごとに管理していた)、それらのすべてに手を加えなければならないので大変だった。実際、gpu以外のプログラムでのrestore機能の実装は競技開始してからだった。

四日目なのでお昼すぎから競技だった。だいたい、一つの問題ケースにたいして5minずつ割り当てて、chimeraとkireiをつかって頑張っていた。最初はGPU利用の競合を懸念して一つしかSolverを走らせなかったが、とちゅうから並列で走らせた。ちゃんとプログラムが遅くなって面白かった。

最初は全然振るわなかったkingyoだが、なんか次数がでっかいケースなどつよいのでは?とか適当に考えて6問目を回したところ、1位かそれに準ずる順位を取れて俄然士気が上がった。それぞれの問題で10~6位程度を取れたので、restoreプログラムを活躍させて一回submitしたファイルから計算を再開させるなどしてちょっとずつスコアを改善するちくちく作戦をやっていた。ここでrestoreでは焼きなましが走ってしまいなんかせっかく山に登っていたのに降りやすくなってしまっておもしろかった。kireiに関しては完全に山登りにしたnouseというプログラムをforkして走らせたりしていた。どちらでも結果はそんなに変わらない感じだった。

そんなことをしていると1位を取れる問題がいっこでたので、それのSolverは競技中ずっと走らせていた。

競技終了前の平均得点は4位相当だった。最後の5分も計算させてsubmitし四日目を終えた。

最終日は表彰式があった。なんか最後の5分で4位くらい浮上している問題があり3位だった。

表彰後は懇親会みたいなのがあったのでたこ焼きとフライドポテトを食べながら優勝チームやそうでないチームと話をした。

他のチームのひとの話をきいていると考察がなされていて頭がいいとおもったり、うちの評価関数はめちゃおそいということがわかったりしてもっと戦えたのではと思った。

その他

何かもっと書きたかったかもしれないが忘れたのでいいや。