大規模化、分散化

現在のPICSY実装は1万人までしか想定されていない。

ひとつのPCサーバでもつ行列の大きさとしては、1万×1万×sizeof(double)=8億バイト=800MBくらいが限界だろうということだ。オンメモリだとこれくらいだが、ディスクだと10万×10万×sizeof(double)=800億B=80GBくらいだろう。がんばれば10万人まではいく。

そこで、もっと大規模化するために、分散化する必要がある。ためしに、太田くんが作った原案1というGRIDを用いた案で、さまざまなリソースの計算をしてみた。彼のアイデアは、既存のSCALAPACK(並列という言葉しかないのが気になる。たぶん無理だろう)やGlobus等のGRIDツールを使って分散メモリ型の行列計算をやろうというものだ。

固有値ベクトルを管理ノードにおき、行列を分散して分散ノードに置き、固有値ベクトルを管理ノードと分散ノードの間を行き来させるというモデルだ。

この場合、通信量は、n行n列行列で分散ノード数がkだとすると、

sizeof(double) × n × k

となる。このkが曲者で、nが増えるとnに漸近する。

たとえば、n=1億だとすると、1台あたりのディスク容量は

sizeof(double)×1億×100=800億バイト=80GB

ということで、k=100万台のクラスタが必要になる。

すると、通信量は、

sizeof(double)×1億×100万=800兆バイト

となり、1Gbpsですべてのノードが接続されていたとしても、転送に

1800時間=75日

ほどかかる計算になる。鬼だ。

n=1億ではなく、n=100万とすると、

1台あたりのディスク容量は

sizeof(double)×100万×1万=800億バイト=80GB

ということで、k=100台のクラスタが必要になり、

通信量は、

sizeof(double)×100万×100=8億バイト

1Gbpsですべてのノードが接続されていたとすると、

6.4秒

しかかからない。

さらに各ノードでの計算時間を考えてみると、

100万×1万×2=200億回

浮動小数点演算が必要となる。

ためしにぼくのノートPCのjavaで計算したところ、

240秒=4分

しかかからない。

現実的には80GBのディスク読み出しの時間のほうが圧倒的に時間がかかるだろう。一般のHDDだと、30MBpsくらいらしいので、45分くらいといったところか。

つまり、原案1による方法の

【結論】

100万人くらいまでなら、マシンを100台そろえれば可能。

1000万人くらいまでなら、マシンを1万台そろえれば可能。(転送時間18時間)

1億人くらいまでなら、マシンを100万台そろえれば可能。(転送時間1800時間)

ちなみにgoogleは5万4千台くらいあって、1日に400台ずつ増やしているらしい。

【考察】

・行列分割方式を変えてかわりに各ノード間でコミュニケーションさせたりして管理ノードの通信量をかわりに下げたりできる。

・管理ノードという考え方を捨て、WEBのような完全分散を考えてみる。

アルゴリズムを根本的に考え直す。

・カンパニーの解体についてはまったく考慮されていない。

・管理ノード自体を分散化することも考えられる。つーか、完全に同じデータを100万ノードに配信するという話は、ブロードバンド放送のときに出た話で、やれP2Pで解決するとか散々議論されているはずなので、実は問題はそんなに深刻じゃないかもしれない