間違ってる点があったらすまそ。自分用メモでもある。
AmazonEC2とか、クラウドサービスって、お金さえ払えば好きにノード数増やせてうれしいよね。
だったら、それで並列計算できると嬉しいよね。
でもお金かかるよね。
じゃあ、どういう戦略を使えば払うお金を最小化出来るか?
こういうことを考えた論文。
問題設定:
探索・最適化問題には、超並列計算でないと物理的に解けない問題がある。
計算量(空間・時間)が指数爆発して解けなくなる。
NP以上の困難な問題。3-SAT,IP,プランニング、多重整列(Multiple Sequence Alignment)
時間なら好きに増やせるが、問題はメモリ量が爆発する場合。
時間なら少ないCPUでも多少待てばどうにかなるが(それでも爆発したら終わらないが)、
メモリの場合には、一つのクラスタのマザボに物理的に挿せるメモリ量に限度があるので、
こちらはそうおいそれと増やせない。スワップアウトなんかしたらおしまいで、解けないのと同じ。
これは 京みたいにいくらコア単位/通信速度を上げても変わらない問題。
まあ、数値計算には向いてるだろうけど。
クラスタで解く
- HDA*や将棋AIのような ハッシュベース分散探索(ほぼ完全なロードバランシング) と 非同期通信(データ送信の際に相手を待たない) を多用したアルゴリズムを使えば、探索問題で並列度を高めても同期コスト・探索コストをほぼ無視できるようになったらしい。
- しかし、大規模なクラスタは、ふつうtorqueなどのジョブスケジューラを用いて仕事を管理している。
- ジョブスケジューラは、一つのクラスタを複数人が効率的に使えるように、計算タスクをキューに入れ、必要資源を指定し、それに応じて適切にジョブをCPU/ノードに割り振るプログラム。
- クラスタの場合、途中で使用ノード数を増やすことは簡単ではない。途中で追加分のタスクを要求しても、それが実行されるのは他のタスクが終わってからだからである。
クラウドで解く
- AmazonEC2とかは、動的に必要な資源量を変えられるので、自分でサーバーをメンテナンスするコストや、上にあるようなバッチスケジューラの問題を考えれば利点が大きい。
- ただし、一般的な研究期間にあるみたいなクラスタとは違い、使ったマイクロ秒でお金がかかるのではなく、1HAUという単位をもとに課金される(離散的料金体系)。
- 最適化の研究者としてはアマゾンにくれてやる金を最小化したいのは当然。どうする?
Trivial な解法 : 反復増加 (itarative allocation)
こういう場合に普通に考えれば、iterative allocation というのを考えればいいことがわかる。
つまり、メモリ量、時間量を少しずつ増やしていく方法である。
「メモリ100MBでパンクした、だからつぎは150MBでやり直そう」
「150MBでもパンクした、だから200MBでやり直そう」
なお、並列計算なので、一度パンクしたら初期化のために全て計算を一度リセットする必要がある。
(動的にノードを増やすのは無理ということ)。
ハッシュベース探索であるということも影響しているかも。
このやり方を使えば、低い料金のうちに問題を解ける可能性はある。
さて、この言い方で、では予算を出す上司がOKをだすだろうか?
いやさ、それ、繰り返して無駄に計算する分、金増えるかもしれないし、結局いつ終わるかわからないじゃん。
この指摘は2つの要素に分けることが出来る。つまり、
- かかる費用が増えるか減るか、いまいちわからない
- 増えたときにどれだけ増えるか(上限)がわからない
これは実用的な意味で問題だ。この戦略を用いる確固たる理由がないからだ。
b-幾何反復法
代わりにこの論文が提案するのは次のような方法である。「リスタートのたびに資源をb倍する。」
結論から言ってしまえば、この場合、最悪必要資源量 が、未知の、最低限必要な資源量 に対して下の比以下に抑えられる:
R*_wo <= b^2/(b-1) <= 4 (b=2)
そして、平均必要資源量 も、以下に抑えられる:
R*_ave <= 2b^2/(b^2-1) (= 8/3 when b=2)
これはつまり、この戦略を用いれば、「たまたま一回目に指定した資源がバッチシ必要ギリギリの資源量だった」ときにAmazonに支払うお金に比べて、たとえ最低の資源がどれだけかわかっていなくても、最悪でもその4倍(b=2)、平均的には 2.6倍程度のお金を払うだけで済むよ、ということである。
一般に、探索問題がどれだけメモリを食うかは実際に解いてみるまでわからないので、この保証は大変ありがたい。そして、変に人間が手チューニングした、最悪コストの不明な方法 をつかうよりは、理論的に最悪の場合がわかっている戦略を使うべきだという結論になる。
実験
理論だけでなく実際の探索問題を用いて上記の減少が実際に観察されることも示している。
詳細は割愛
で、なに?
ジョブが失敗したら、時間・メモリ資源を2倍にしてジョブを投げ直す、
そういうtorqueクラスタ向けのスクリプトを作ったよ。
requirements: cgroup-bin