AMD Multicore Threadfest

地道にしょぼしょぼやってたけど、なんか最後に失敗したみたいで悲しい。のですがまぁ考えた記録を書いてみます。

なんか問題は、こなすべき色んなサイズの job が10万とかあって、それを数十個の性能の異なる machine で適当に全部こなすための scheduling を考えるというもの。 それぞれの job は他の job に依存してて、依存関係のある job は同じ machine で動かせば何の問題もないけど、他の machine で動かす時は一定の時間がかかる。あと job は一旦停止してまた別のタイミングで途中からやることもできるけど、その pause と resume はそれぞれ少し時間がかかる。

基本的にはこう、複数の job を同じマシンで動かせば移動のコストが無いけど、並列性が減ってしまう、というそういうトレードオフみたいだった。

まぁ最初はこう、 job に適当な評価関数を与えて priority queue につっこんで順番にその時最速で終わる場所に schedule 、とかでやってみて、なんか全然だめだった。

でなんか example 1 が妙に細かい job が多い設定で、それをまともに分散して schedule することに注力しよう…とか考えて、大きい job を適当に洗い出してきて、その大きい job が依存している job を優先的に一つのマシンでこなして、その間に依存の解決できた大きな job を別のマシンで走らせる、とかやった。 example 1 はそれでうまくこなせたっぽいんだけど、よく見ると他の example では壊滅的だった。 example 2 とか 3 とかは結構適当にやってもたくさんのマシンを同時に使えるので、大きな job 以外は一つのマシンでやるとかは愚の骨頂なのであった。

で今度は example 1 とか忘れて、なんか適当に1個 schedule したら、それに依存してる job のうち依存が解決できてるものを同じマシンで一定数 schedule する、って感じでやってみた。そしたら example 1 はあんまり良くなかったけど全体的に割と良かった。

細かい job が多い設定だと、どうしても一つの一番速いマシンだけで全部ぶん回すのが一番速かったりするなーと、一番速いマシンでぶん回すよりも時間がかかりそうだったらそっちの結果をかえすようにした。

大きな job がひっかかってる感じだったので、最初の方の精神を思い出して、大きな job とその依存 job 群を前方に stable_partition で持ってきておいて、それに対して処理をしていくようにした。ら結構よくなった。

とても大きい job とその依存 job を前方に stable_partition で持ってきて、その持ってきたものの中で比較的大きいものとその依存 job を前方に…と再帰的にやってみたあたりで、 job の子供を同時に schedule するコードはむしろ害悪になってた。まぁ似たような目的のコードではある。

あとは順序決めた後に、適当な回数大きな job は依存関係が許す限り前に持ってくるとか ad-hoc に入れたり、 machine にアサインする時に既に schedule した job の前に schedule できる時はするようにしたり job の分割を試みるようにしたり、まぁ色々。そのへんでこう点数が飽和してきてこれはダメだなーという感じでした。

なにかあれば下記メールアドレスへ。
shinichiro.hamaji _at_ gmail.com
shinichiro.h