2025年10月4日土曜日

グラフコンパイルーメモリ問題

 メモリ問題から、全基数制約をコンパイルするのを諦めて、TIME制約とWEEKEND制約のみコンパイルします。

そうしたときに要するRoster1個あたりのメモリ所要量です。

                       コンパイルメモリ所要  コンパイル時間 グラフメモリ所要量

instance23  48GB          45分       0.7GB

instance24  140GB                                       2-3時間      1.5GB


このために、メモリを32GB⇒48GB⇒96GB⇒192GBまでDDR5を増量しました。instance23で、グラフコンパイルだけで、丸2日、instance24で2週間程度かかります。

<コンパイル時間問題>

こんなに時間がかかるなら、別な方法を検討したくなりますが、実は、この問題は、クラウドを使えば現在でも解決できます。というのは、スタッフ毎に独立してコンパイルが可能だからです。リソース無尽蔵のクラウド資源を使えば、並列にコンパイル可能です。つまり、リソースさえ気にしなければ、全スタッフを2時間でコンパイルは出来ます。

<コンパイルメモリ問題>

グラフのコンパイルに192GBメモリが必要です。AIに10年後の予測をしてもらったところ、AI需要等により64-256GBになるとのことでした。



よって、10年後では、標準的なPCで十分に対処可能になると予測します。

<グラフメモリ問題>

instance24は、150staffなので、平均1.5GBだとすると1.5*150=225GB > 192GB で足りません。

Diskに退避した場合、現在の高速SSD+対応ボードを使うと14GB/secの転送レートで、メモリ転送レートと比べて、そんなに遅くはありません。以前のHDDを使った転送レートと比べれば雲泥の差です。それでもGraph処理レートよりもDisk転送レートの方が遅い可能性が高いので、できるだけメモリ上で圧縮処理した方が得策とみます。

<グラフ縮約>

一度LBが算出されれば、後は、厳密解に拘る必要はありません。つまりLB算出までは、Fine、それ以降は、Coarseで制御します。グラフ処理速度は、グラフ規模で一意に決まるので、グラフを極小化することで、処理速度を向上させます。

まとめると、

LB算出までは、厳密解を得るために、多少時間がかかってもグラフの縮約は用いません。

LB算出以降は、実用的なBranch&Bound速度とするために、グラフの縮約を用いて高速化を図ります。

以上の検討により,

■instance24のコンパイルに192GBメモリ48x4

■必要ならば、メモリ上でグラフ圧縮処理

■LB算出後のグラフ縮約


を行うこととします。

さすれば、グラフメモリ問題は解決できる、と結論します。

とりあえず、instance24のグラフメモリをDISKに保存中です。この予備処理に2週間程度かかる予定です。一旦グラフメモリを保存することが出来たならば、後はそれを用いてさらにアルゴリズムの検討を行うことが出来ます。HIGHSの新IPMは、GITHUBを見るとかなり期待出来る速度となるようです。これにより、課題要素は、それぞれクリアできるのではないか?と期待されます。




0 件のコメント:

コメントを投稿