IPSC 2010
今年は個人で参加した。
8問半解いて、全体で15位、個人の部では1位だった。
A
数列が与えられるので、ソートされてないように並び替える問題
やるだけ
B
平面上に一本直線があり、この直線上と上下左右への移動のみによる二点間の最短距離を求める問題
二点から水平・垂直な直線引いて交点求めてそれらからなるグラフの最短距離求めるだけ
C
「変数=数式」っていう形の入力を受け取って、各変数の値を求める問題
ただしループはしない
頑張ってパースするだけ
D
N個の頭を持つドラゴンを倒したい
二種類の剣があって、剣iはドラゴンの頭をci減らすがその後gi本の新しい頭が生えてくる
ドラゴンの頭を全て切ることができればあなたの勝ち
ドラゴンの頭がci未満だとその剣は使えない
しかし、自分も頭があるので、ドラゴンの頭がci-1個の時は自分の頭も一緒に切ることで引き分けにできる
勝敗判定せよって言う問題
拡張ユークリッドして場合分けしまくったら通ったが怪しい
E
ちゃんと読んでないが、たぶんインタラクティブ問題
時間かかるので放置
F
N個のサイズが異なる立方体があるので、それらを積み上げて二つの等しい高さの山を作るとき、最大の高さを求める問題(全部使い切らなくても良い)
に対する嘘解法が４つ与えられるのでそれらを全て同時に撃墜できる入力を作る問題
ランダムに入力生成すればそのうち落ちるかと思ったが全然落ちなかったのでちゃんと考えて作ったら落とせた
G
読んでない
H
指定されたMD5値になるようにファイルを生成する問題
無理ゲー
I
多角形(凸とは限らない)が与えられて、その内部の点から各辺の延長線上におろした垂線の長さの和の期待値を求める問題
頑張って積分するだけ
J
N個の机があり、各机に青と赤で数字を書く
最初、N人の男女が各机に一人ずつ居て、一定時間ごとに男は青の数字の机に移動し、女は赤の数字の机に移動する
N回の移動で、各男女が全ての机に移動し、各男が全ての女と同じ机になることがあるような番号付けを求めよっていう問題
サンプルからてきとーに類推して出したら通った
K
二人プレーのゲーム
3次元中に点がN個あって、各点は原点からのユークリッド距離が真に小さくなる格子点上へ移動させれる
各ターンに最大K個の点を動かすことが出来、全部原点に移動させたプレーヤーの勝ち
勝敗を判定せよっていう問題
同時に1〜K個のゲームを進められるNimは山のサイズを二進表記の各桁毎に和を取って全部mod(K+1)で0なら負け、そうでなければ勝ち
座標が超でかくて山のサイズがナイーブに求まらないのでちょっと大変
位置(x,y,z)に対応する山のサイズは|(x,y,z)|^2=Mとすると、|(x',y',z')|^2=K＜Mとなる点(x',y',z')が存在するようなKの個数に等しい
つまり３つの平方数の和で表せるような数の個数を求めればよい
google先生に聞いたところ、表せない数は4^n(8k+7)であることが分かったため、サイズがO(log M)で求まって解けた
L
1円の切手がN種類と、2円の切手がM種類あるから、これらからK円分買うような方法の総数を求める問題
smallはKが小さいので2円の切手を何円分買うかが全通り試せる
largeはKが超でかいが、行列累乗で解けると思う
最後１０分くらいで気づいたが組み終わらなかった
Marathon Match 59
TCOのシードを得るために一年ぶりに参戦
結果は11位orz
まぁ、久しぶり過ぎた上に時間がなさすぎたのでしょうがない…
方針はまず、何段にするかと、それぞれの段の高さを決めるために、次のように制約をきつくした問題を考え、それを解くことにした。
- i段目に入っている本はi+1段目に入っているどの本よりも高さが低い
こういう制約を付けると次のような二段階のDPにより最適解を求めることができる。
- まず、本を高さでソートする
- dp1[i][j] := [i,j]から幅Wで選ぶときの最大価値
- dp1[i][j]の計算はiを固定しておいて、ナップサックするだけ
- サイズが大きいと計算量がやばいので、ナップサックDPは諦めて貪欲法を使用
- dp2[h][i] := i番目までで高さがhとなるときの最大スコア
- dp2[h][i]=max{dp2[h-book[j].height-10]+dp1[j][i]}みたいな感じ
- こっちも計算量がやばいので、嘘DPを使用
何段にするかと、高さが決まったら、次は高さの低い段から貪欲的にナップサックDPを行って本を入れる
これだけだと、空きスペースができてもったいなかったので、本を別の段に移動させることにより、新たに別の本が入れれるようになるっていうのを探して頑張って詰め込む
時間が余るので、高さをランダムにちょっとだけ変更して繰り返しー
CPU実験
CPU実験が終了しました。
我々の超ksk班はスーパースカラ+動的スケジューリング(OutOfOrder実行)で100MHzというのを作成し、17.3sという記録でした。
なんとか過去の記録は抜けたものの、基板の変更があったので単純には比較出来ない上、実は150MHz(もしくは133MHz)用に作成していたものの間に合わなかったり、分岐予測がうまく機能していないようだったりともう少し時間があれば…という感じでした。
以下、大体の流れ
第一期アーキテクチャ
昨年10月に班が決まり、第一期アーキテクチャの作成が開始しました。
とりあえず過去の班の資料を参考に、絶対必要そうな命令だけからなる単純な命令セットを作成して、50MHzのマルチサイクルで動かすことになりました。
今年から新基板になるハズだったのですが、このときまだ基板が届いておらず、ひとまずは旧基板で作成することになりました。
自分はシミュレータ係となり、暇になったらコンパイラの最適化を手伝うという感じになりました。
MinCamlを読みながらのんびりシミュレータ&アセンブラを作っていたところ、HW係の方々が神すぎてあっという間にHWの方が完成してしまったため、自分も急いでコンパイラからレイトレのコードを吐けるように、最後のアセンブラを吐く部分を手伝ったりしました。
結果、10/16にシミュレータで初画像(真っ白)、17日にそれっぽい画像が、18日についに正しい画像を出すことが出来ました。
さらに翌日には実機でレイトレが動作し、作業開始からわずか２週間でレイトレ完動を果たしました。
この時の記録が34億命令338.985sで次の日にはkskさんによりキャッシュが搭載されたり(こんなにすぐに付けれるものだったのか…)、コンパイラがちょっとはましなコードを吐けるようになったりして、10/22には26.6億命令141.234sとなり、ここで第一期アーキテクチャの開発が終了しました。
ここまでに行った最適化は、ライブラリを書き換えてクロージャが作られないようにしたり、零レジスタの活用、定数テーブルやグローバル配列の読み込みをラベルから直接行うように、といった単純なのくらい。
第二期アーキテクチャ
予想外にスムーズに第一期アーキテクチャが完成してしまったため、まだ新基板が届いておらず、次のアーキテクチャも旧基板で作成することになりました。
第二期アーキテクチャは、命令種を少し増やし、100MHzのパイプラインで動かすことになりました。
主な特徴としては、レジスタが整数・浮動小数共有で64本、比較と分岐がcmpとjmpの２命令、ディレイスロットなし、HW側でストールといった感じです。
kskさんが神なおかげでソフトウェア側でnopを挟んだりディレイスロットを埋める必要がなく、仕事が減って楽になりました。
ソフトウェアの方は一度作ってしまえば、命令セットが変わってもちょっといじるだけで終わるので、自分はコンパイラの最適化とレイトレソースの理解に努めることにしました。
まず、命令セットの変更により命令数が23億くらいに減りました。(即値比較やレジスタ+レジスタのロードができるようになったり、sqrtがライブラリからFPUへ変更になったり、レジスタの本数が増えたりした)
このころ、Javaで書いたGUI付きシミュレータが遅すぎて(１レイトレで３分くらいかかる)我慢ならなかったので、Cで総命令数のカウント以外何も機能のない高速シミュレータを書いたりしました。
こっちだと30sもあれば画像を出せて、コンパイラをいじる上でとても役に立ちました。(高機能の方は統計とったり、デバッグしたりするときのみ使用)
あとはflessとかをコンパイラの組み込み命令化したり、よく使いそうなグローバル配列を直接レジスタに割付けたりして11月初めには20億切りを達成しました。
その後、コンパイラ係のhotaさんにより共通部分式除去(GVNとかいう手法があるらしい)の実装とレジスタ割付の改良(呼び出す関数内で使用されないレジスタは退避しない)が行われたり、自分がスタックアクセスの挿入位置を改良したりして(最終的にはスタックアクセスはほぼなくなるのでこれは不要だった)、12月初めには15.5億命令くらいまで削減出来ました。
HWの方は100MHzで安定動作させるのがとても大変らしく、制約を満たしていて単体テストだと正常動作するのに、全体で動かすと正しく動作しないみたいな状況でした。
また、ようやく新基板が届いたものの、なにやら色々と問題があるようで、新基板担当となったxyxさんが大変苦労していました。
12月は、自分が別の仕事で忙しくて、無駄なジャンプ除去や、不要引数除去くらいしか最適化を行えませんでした。
それでもこの時点で14.6億命令くらいで、比較命令が2.1億くらいあることを考えると過去の人達とあまり変わらないような気がして、実はコンパイラコードじゃこれ以上そんなに減らないんじゃないか、とか思っていました。
1月に入り、自分は完全にICPCモード。
1月の終わりに、ついに実機でレイトレが正常動作(87.5MHz)し、またGShare分岐予測とCallStackが搭載されました。
2月中旬、ついに旧基板100MHzでレイトレを動かすことに成功し、ここで第二期アーキテクチャの開発が完了しました。
この時点でリンクレジスタが不要になった分が減っただけで14.5億命令くらい
第三期アーキテクチャ
これはただ単に第二期アーキテクチャを新基板へ移行するだけでした。
新基板用のモジュールなどはすでに作成してあり、移行はスムーズに進んで３日くらいで完了しました。
その後、新基板で150MHzまでクロックを上げることに成功したものの、それでもまだ過去の記録を抜けないという状況でした。
自分は、HW側でストールしてくれるおかげでサボっていたパイプラインシミュレーションをようやく行いました。
その結果、ものすごくストールしまくることが発覚…
特に浮動小数演算の依存関係がひどく、どうしようもない感じに…
急いでスケジューラを作成してみたものの、それでもどうしようもないストールが大量にあり、分岐先からも命令を移動させる投機的スケジューラの作成を行いました。
ところが投機的スケジューラを用いてもまだ埋まらないストールが存在し、また、このスケジューラを用いたコードはなぜか実機動作しませんでした。
また、シミュレータでの予想時間と実機での動作時間に3.5sくらいのズレ(実機の方が遅い)があり、結局これも解決しませんでした。
第四期アーキテクチャ
３月になり、最終アーキテクチャの仕様を決めることになりました。
まず、ボトルネックとなる部分が大体、loadしまくったもの同士をFPUで演算しまくり、その結果を比較して分岐するという感じで、第三期アーキテクチャではFPU間に４つ命令を挟まないといけないため、分岐先から命令を移動させても全然埋まらない、という問題点がありました。
また、分岐予測が付いているのに、比較命令が別にあるため、効果が薄れているという問題もありました。
そこで、FPUのうち、3clkで動作可能なfaddとfmulについては3clkにし、また比較と分岐は1命令にすることになりました。
また、fabsやfnegはフラグを用いて他のFPU命令と同時に行うことになりました。
あとは新基板となったことを生かすために何かできないかということになり、命令を全てブロックRAM上に載せることが可能であったため、命令キャッシュが不要となりました。
また、これにより1clkで複数命令を発行でき、スーパースカラ化が可能となりました。
しかし、ただ単にスーパースカラ化したところで、依存関係によるストールがある限り大して性能向上が得られないため、分岐予測を生かすために動的スケジューリングでOutOfOrder実行を行うことになりました。
これに伴ない、レジスタが整数・浮動小数別で64本ずつ、CallStackは廃止されることになりました。
この時点で残り２週間、ここから怒涛の最適化タイム開始。
まず、命令セットの変更により、一気に命令数が12.2億に。
次にグローバルレジスタ割付を実装し、スタックアクセスをほとんど撲滅し、11.5億。
また、IO周りをインライン展開しないよう制御することで、総命令実行数をほとんど増やすことなく、命令サイズ2^13制約を満たすことに成功。
hotaさんにより、タプルの共通部分式除去が強化され、ついに11億切りを達成。
条件式の中のif文(要するに&&)の部分のアセンブリがとてもひどかったので、基本ブロック分割を実装して無駄な比較の除去を行い、ついでに同一ブロックのマージ、If文の二重化、ブロックの順番の変更などなどを行って10.1億命令に。
引数レジスタを関数内で保存することで関数呼び出しによるmovを削減し、ついに10億切り達成。
ここからついにハンドアセンブルの神nuさんの行ったタプルの中身を展開するという最適化にコンパイラで挑む。
てきとーに配列長推論を組んだところ、３次元ベクトルのサイズが６になってしまい失敗…
それをてきとーに修正したところ、なんかうまく配列長が推論できた(とても怪しい…というかたぶん嘘ｗ)
あとは中身の展開をとりあえず手抜きで嘘実装し、9.5億命令切りを達成(結局修正する時間がなくて、嘘のままになってしまった)。
各種パラメータをいじって9.3億命令まで削減し、最終日、徹夜で引数のタプル・配列を展開して渡すのを組んで8.8億命令に。
結局、12.2億から8.8億まで命令数を削減出来ました。
がんばればコンパイラコードでも8億切りくらいはいけそうな感じなので、ぜひ来年以降の人達には頑張ってもらいたいです。
また、HWの方は終了２日前についに実機でレイトレを動かすことに成功し、そこからDキャッシュの搭載、同種命令間でのフォーワーディングによるレイテンシの軽減、などが実装されていきました。
しかし、どうやら分岐予測が正常動作していないことが発覚、頑張って原因を探りましたが結局このバグは終了までとることが出来ませんでした(分岐予測ミスのペナルティが最低8clkはあるらしいです)。
また、新基板は非常に合成に時間がかかるため、66.6MHzでデバッグしていたところ、終了までに本来の予定だった150MHzや133.3MHzでの合成に成功することができず、結局100MHzで動かすことになり、17.3sという結果になりました。
本来であれば、シミュレータ係の自分が動的スケジューリングのシミュレーションを行い、このアーキテクチャでどのくらいの性能が出そうなのかちゃんと計算するべきだったとは思いますが、時間がなくて行えなかったので、うまく動作していたらどのくらいの時間になったのかは分かりません。
ともあれ、最後の２週間という僅かな時間でスーパースカラ+動的スケジューリングを一人で動かしてしまったkskさんは本当に神です。
班のみんなお疲れ様でした。
SRM 464
hos先生のセット
250
全通り調べるだけ
n=1の場合を忘れて再提出orz
しかも、再提出ミスって再々提出orzorz
147.68
550
見た瞬間、二分探索＋2SAT
492.89
1000
現在位置*安全だと分かっている色の集合*危険だと分かっている色で状態数が50^2*2^7*8
これをDPしていけばいいが、そのままだとDAGでないので、安全だと分かっている色の集合が変化しない部分についてUnionFindとかでマージすればよい
時間内に組み終わらずorz
Challenge
250でn=1の場合を忘れている人いっぱいいるだろーと思ったのに全然いなかった
1成功1ミス
+25.00
合計665.57の9位
2848 → 2902
SRM 463
またしてもりんごさんのセット…
250
ソートして、Π(a_i-i)計算するだけ
すぐに気づけなくて時間かかったorz
239.85
500
よくわかんなかったのでとりあえず小さいの二つ取り出して足すのと掛けるので大きい方にして、一つになるまで繰り返すーをやってみたらサンプルが通らなかったorz
ちょっと考えたら、1.5〜3.0のやつらを二つずつのペアにして足して、あとは全部掛けるでいいことが分かったが、どういうペアにすればいいのか分からない…
小さいから順にペアにするとサンプルが通らないので小さいのと大きいのでペアかなーとか思って組んでみたらサンプルは通ったけどなんか怪しい…
全探索も組んでランダムであってるか調べたら落ちたorz
ここらで諦めて1000開いてわかんなくて戻ってきて、どこまで足し算するかの部分を全部試せばいいんじゃねということにようやく気づき、やってみたら小さいサイズでは正しい解が出てそうだったので提出
231.39
1000
さっぱり分からなかったorz
Challenge
500が撃墜祭りになりそうだったので、パッと見で怪しかったら先越されないように即撃墜
５回成功３回ミス
+175.00
ルーム内で11/16が落ちてたので、全員に対してブラインド撃墜してれば50*11-25*4で450点も稼げた計算に…
今度からはPetrが再提出してたらブラインド撃墜してみよう
合計646.24の32位
2841 → 2848
SRM 462
やっぱりSRMは11:00なんていう早朝にやるもんじゃないねｗ
250
1,"11"で0返してて再提出orz
落とし穴いっぱいで撃墜しまくりだーと思ったら自分のも落ちたorzorz
1,"110"とかどう見ても解あるじゃん…
Failed System Test
450
全てのやつを独立に考えて良くて、i回スワップ後にもとの位置にいる確率をp_iとすると、
p_{i+1}=hoge*p+piyo*(1-p)
みたいに書けて、これ計算してから全部まとめるだけ
O(log S + n)まではいける
が、コンビネーションnCrでr<0の場合を考慮してなくて死んだorz
Failed System Test
1000
最悪ケース最小化→二分探索！！！
というわけで二分探索で解けないか考えたところ、
minD[v]=max_u{辺(v,u)を削除したときのv-t間最短距離}
とし、解の上限をubとすると、
(s-v間最短距離)+minD[v]<=ub であるような点だけを使ってtに到達できるかを判定すれば良い
…のはずだが何故か落ちたorz
他の人みんなベルマンフォード的なことをしてたので解法違うのかなーと思ったが、ただバグっていただけだったorz
なぜかダイクストラの初期化する場所をミスり、さらに終点について上の判定をしていなかったorzorz
Failed System Test
