SuperCon 2016参加記
今年は幸運にも SuperCon 2016 の本選に参加してきたので、それの所感と経緯を書きたいと思います。
What is SuperCon
正しくは SuperComputingContest で、東工大と大阪大学が共同で開催している大会で、SuperConを使って規模のデカイ問題を解こうぜ！
みたいな大会のはずです。
結果
とりえあず結果だけ先に書いてしまえば、全20チーム中12位という結果に終わりました。
覚悟していたよりは良い結果だったのですが。色々悔しさが残っています(後述)
予選
予選開始前
まずはじめに、僕はプログラミングを4年間やっているのに競プロができないという致命的な問題がありました。
どのくらいかというと、初めてdijkstraを書いたのがこの記事を書く1週間前くらい、というレベルです。
というわけで、最初は割と「何かの間違いで本選出れたりしないかな」みたいな気分でいました。
予選開始
そんな中、 予選問題 が公開されました。
ここで一応簡単に予選問題について解説すると、
6x6の魔法陣に15個の虫食いがあるからできるだけ高速に埋めてね
という問題です。
問題公表から申し込み締め切りまでは17日間あり、その2週間ちょいでコードを書く必要があります。
こんなシンプルな問題ですが、僕は最初パっと解法が思いつかずに悩んでいて、数日は放置気味にしていました。
しかしパートナーの方が解法への糸口を掴んでくれていたらしく、そちらに最初の実装をお願いしました。
予選おわりまで
そこから1週間目の終わりくらいまではパートナーから実装の解説を聞いておかしいところを話し合いつつ、僕は何もせずにパートナーが頑張ってくれていました。
ちなみにこの時点で大体まとまった戦略は
魔法陣の各列に対してその列で使う可能性のある数をbit列で保持しておき、それの論理積を取って各マスの候補をさらに絞り込んでから再帰で全探索
というものでした。
しかし、2週間目に入った時にパートナーの方から「実装が詰まったから手伝ってくれ」というヘルプが飛んできました。
ところが、ソースをもらったところ、コードがグチャグチャでまず問題が発生しているコードの位置を特定できなかったので、基礎の考え方はそのままで僕の方でコードを1から書き直すことにしました。
そんなこんなで2週目の土日までにはコードが完成しました、が、重いテストケースで実行時間が1時間を突破してしまい、これはアカンということで最後数日で最適化を始めました。
そこで、速くなりそうな部分を探したところ、各マスの候補から全探索を行う際に色々と無駄なループが走っていることがわかり、割と気合でコードを書いて対策しました。
すると、実行時間が軽いテストケースでは200μs、重いテストケースでも2～7ms以内に収まるようになり、希望が見えてきました。
しかしこのソース、本来大会側で用意してあるヘッダーで入出力と時間計測を行わなければいけないのですが、それを完全に見落としており、最後の最後で慌てて修正しました。
あとは適当にコメントつけたりしてから提出しました。締め切り前日だったので結構危なかったです。
一応書いたソースは ここ に載せておきます。
別の出場チームの話を聞いたり、Twitterを見たりしたら皆実行時間が短くて大分ヒヤヒヤしたり、予選の結果発表が伸びたのをネタにしたりしていましたが、無事予選通過することができました。
しかし、実は今回の SuperCon はJOIの夏季ゼミと日程が丸かぶりしていたために、昨年の優勝校含む強豪学校が SuperCon に参加しておらず、当初の考え通り「何かの間違いで通過」に近かったかもしれません。
どちらにせよ通過出来たことは単純に嬉しかったです。
予選までの所感
今思うと最初半ば諦めていたとはいえとりかかり始めるのが遅く、完成したソースも最適化が微妙でまだ結構定数倍高速化できる部分がありました。
あとは、SuperConは基本的にC言語オンリー & 実行がUNIX環境のため、Windows & C++ ゆとりの僕には大分辛かったです。このために仮想マシン上にUbuntuでテスト環境を構築するはめになりました。
このC言語制限は本選でも共通だったため、色々と消耗しました。
本選
最初に
SuperCon の本選は東は東工大、西は阪大に予選を通過した20チームが集まり、5日間にわかって問題を解く形で行われます。
いつもは東と西で10チームづつ選出されるらしいのですが、今年は前述の夏季ゼミと被ったこともあってか東側の募集が少なかったらしく、東が8チーム、西が12チームという配分に別れました。
というわけで僕たちは東8チームのうち1チームとして5日間東工大に通いました。このうち、問題を解くのは4日間で、最後の日は表彰式と懇親会でした。
1日目
1日目は午前に集合したのちに、偉い方の挨拶、各チームの紹介などがあり、午後から東工大のコンテスト環境や回答提出方法の解説、問題の発表が行われました。
東工大では端末として iMac が用意されており、OS X と Windows がダブルブートできる環境だったのですが、本選では OS X の方を使用しました。
ここでマウスが Magic Trackpad で無かったり、OS X のバージョンがEl Capitan ではなく Mavericks だったりして高まっていたテンションが少し下がりました(これはむしろ良かったかもしれませんが)
本選問題は簡単にいえば
頂点がn個で次数がdの単純正則無向グラフの ASPL(総最短経路長) ができるだけ小さくなるように経路を求めよ
という問題です。
これを各チームに割り当てられたスパコンのノードを自由に使って解くのですが、今回のスパコンには東工大の TSUBAME が使用され、TSUBAME の特徴である GPU を CUDA C でいかに上手く動かすか、という感じになっていました。
一通りの説明が終わった後は、問題を解く時間となったのですが、まったく解法が思いつかなかったので補助用のシェルスクリプトを書いたりしてUNIXに慣れていました。
パートナーの方は何か解法を思いついたらしく、2人で相談しましたが、僕が上手く実装できる気がしなかったので、予選と同じく最初の実装をパートナーにお任せしました。
2日目
この日は朝の電車内で色々考えた結果、少し前に TSP について調べた時の手法が使えるのではないかという考えに至り、「ランダムでグラフを生成してから、更にグラフのランダムな2辺を取って入れ替える事を繰り返す」という手法を試して見ようと思いました。
2日目は15時から16時の強制休憩タイムを除き、9時から20時まで問題を解ける時間となっていましたが、この日でランダムなグラフの生成を書くことができました。
またランダムなグラフ生成における閉路判定に Uinon Find が必要だったのですが、僕はパッと書ける自信が無かったのでパートナーに書いてもらいました。
パートナーは競プロを比較的真面目にやっていて、データ構造に関する知識があったのでこういう場面ではありがたかったです。
この時点で、この手法に関して「これはイケる」という雰囲気を感じており、パートナー側と話し合って、2人で別の解法でプログラムを書こうという作戦にしました。
ちなみに、本番が終わった後に他のチームから指摘されて気づいたのですが、入力例に対するランダムなグラフの生成はサンプルプログラムとして大会側から配布されており、1日目にその説明もありました。
つまり、ランダムなグラフの生成は特に理由がなければ、手書きする必要がないようになっていたのです。
しかし、僕はそれを完全に失念しており、この2日目をグラフ生成に使ってしまいました。
これが最終日に時間が足りない直接の原因になり、今も凄まじく後悔している一番のミスです。
また、強制休憩タイムでは関西会場とつながったテレビ会議システム上でお絵かきしりとりをしていました。楽しかったです(小並感)
あとはGoogleの方からNougat入りのチョコレートの差し入れがあり、ありがたくいただいていました。
3日目
3日目も2日目と同じように、強制休憩タイム以外は進捗の時間として使えました。
この日は「2つのランダムな辺を選択して入れ替え、ASPLを計算した後に小さい方を取る」という部分の実装をしました。
ASPLを求める方法については事前に幾つか手法の紹介をされていたこともあり、この部分の実装は午前のうちに終わった…とおもいきや、ASPLの値が盛大におかしいことになり、昼ごはんを食べるまでずっと悩んでいました。
しかし昼ごはんを食べた後にすぐ、辺の入れ替え後に正しいグラフになっているかの判定でUnion Findを使っているのに、Uinon Find用のtreeが更新できていないことに気づき、修正が面倒くさそうなので手法を変えて実装しました。
食事は偉大です。
ちなみにこの「辺入れ替え後のグラフ判定」ですが、そもそも辺を入れ替えたあと閉路で無かった場合は ASPL が INF になるようになっているので、そもそも必要でないことに4日目で気が付きました。
食事は偉大でも、食べる側の人間の頭は偉大から程遠い場所にあったようです。
あとは、そもそも辺をswapする際の動作が間違っていたせいでinvalid graphになる問題なども発生して、午前に感じていた余裕は吹っ飛びました。
最後1時間位はASPLの計算に使用したフロイド・ワーシャル法の並列化方法が思いつかずに悶々としていました。
これに関しては家に帰ってからきちんと考えました。
4日目(午前)
4日目は、コーディングできるのは午前と本番である13時から15時の間のみでした。
朝になった時にパートナー側で試していたプログラムが結局ダメであった事を告げられ、僕のプログラム一本で行くことになりました。割とキレました。
しかし、前日の夜に足りない頭を絞った結果、フロイド・ワーシャル法の並列化がめちゃくちゃ楽な事に気づいたので、ぱっと実装…と言いたかったのですが、それまで全く CUDA に触れていなかったため、スレッドブロックの割り当てなどでちょっと手間取りました。
更に、これで完成…と思いきや、フロイド・ワーシャル法の後の配列の総和を求める部分をCPUでやると、メモリ転送コストで時間がCPU実装とそんなに変わらないという事になってしまっていました。
というわけでGPU側で配列の総和を求めるプログラムが必要になったのですが、これも大会側がCUDA向けのサンプルとして用意してくれていましたので、それを使おうとしました。
しかし、この総和の算出部分がなぜか上手くいかず、謎を抱えたまま昼になってしまいました。
本番
昼の後、本番がはじまりました。
本番は、入力が9個与えられ、それぞれの入力に対するできるだけASPLが小さい経路を2時間の間に求めて提出する形式で、その2時間の間はプログラムの修正が自由です。
CPUのみを使うプログラムではASPLの算出に時間がかかり、与えられた頂点数が大きい場合、辺の入れ替えを効果がでるまで繰り返す事ができないのがわかっていたので、パートナーにとりあえずの提出を任せ、僕はGPUでの総和計算でのバグを治すことに全力を注ぐことにしました。
しかし、結果だけ言ってしまえば、総和計算のバグを取ることは出来ませんでした。
このバグの原因は未だにわかっていません。
CPUの方でも超点数が少ない場合は試行回数を増やせるので、かなり手応えのある結果を出せる事が確認済みだったのですが、運の悪いことに、本選の問題の多くは頂点数が大きめに設定されており、最終的には全く良い結果が出せませんでした。
更にその後に2日目のミスに気づき、パートナーとともにただひたすらに後悔していました。
本番後は大会側から各チームへのインタビューがあり、チーム名の由来やメンバーの得意技を、問題を解いたアルゴリズムを聞かれました。
得意技に関しては、全く思いつかなかったので「OSデータ破損芸」と言ったらそのまま採用されてしまいました。
5日目
5日目は表彰式と懇親会でした。
表彰式ではまず主催者やスポンサーからの挨拶、再度各チームの紹介などがあり、そこから結果発表と入賞チームや奨励賞受賞チームへの賞状や副賞の授与がありました。
結果発表に本番2時間中の各入力での5位までの順位の変動がわかる動画が使われており、面白いなと思って見ていました。僕らのチームは一回も動画の中に出てきませんでした。
最終的に僕らの結果は上記の通り12位でした。
その後は懇親会があり、じゃんけん大会をしたりしました。
本番で使われなかった運をじゃんけん大会で使った気がする程度には勝ち、いくつか景品を戴きました。
あとは部屋でダベってから帰って爆睡しました。
全体を通しての感想
予選でも本選でもそうですが、配布されたものをしっかり確認しなかった結果、丸々1日損する事になったので、もっと気をつければよかったというのが一番の反省ポイントです。
あとは、慣れないシェルスクリプト、Vim、C言語 & CUDAについてチューターさんに質問を大量に投げてしまったのですが、毎回しっかり回答をいただけたのは非常にありがたかったです。
まああとはGPUの総和バグの原因が未だに分かっていないのが気がかりです。家にCUDAを実行できる環境がないのでもう直せないのがなおさらですね。
とりあえず、プロは強いということが実感できたので、来年も本選出場してもっと上を目指したいです(KONAMI)
