PyTorchのメモリ計画、新しいナップサック解法でピークRAMを20分の1に削減
0/1 Knapsack Problem in PyTorch
PyTorchは計算グラフのメモリ計画で0/1ナップサック問題を解き、どの演算を保存しどれを再計算するかを決めている。従来のdp_knapsackはアイテム数×容量の巨大なDPテーブルを確保していたが、スライディングウィンドウとHirschberg法を組み合わせたdp_knapsack_sliding_hirschbergはテーブルを2行に圧縮。64GB環境で100アイテムで落ちていたのが2000アイテムまで扱えるようになり、実行速度も約37%改善した。
これらの最適化を組み合わせることで、DPテーブルを(アイテム数, 最大重量)から(2, 最大重量)へ縮小でき、ピークメモリを実質20分の1に削減できる。私の64GB RAMのマシンでは、dp_knapsackは100アイテムの問題でクラッシュするが、dp_knapsack_sliding_hirschbergは2000アイテムの問題をこのRAM予算内で処理できる。
- 7scan
実際には、0-1ナップサック問題を解く際にはほとんど常に「コンボ」アルゴリズムを使うべきです。少なくとも中〜大規模のインスタンスでは、これらのアプローチより桁違いに速いでしょう。コードと参考文献はこちらにあります: https://hjemmesider.diku.dk/~pisinger/codes.html
- TacticalCoder
0/1ナップサックは素晴らしい小さな問題で、特に動的計画法による解法がいいですね。
もしかしたら間違っているかもしれませんが、30年前に0/1ナップサックを学んだとき、すぐに思ったのは、多くの場合、動的計画法を使って近似版（より少ないメモリで済み、例えばメモリに収まる）を実行し、その解が「最適解から最大1%の誤差」であることを証明できるのではないかということでした。ただ、実際に調べたことはないので、間違っているかもしれません。
基本的に、量 1739, 2989, 3798, 4233 などを0/1ナップサックする必要がある場合、例えばそれらを10で割って切り上げると、174, 299, 380, 424 になり、動的計画法の解法を実行するのに必要なメモリがはるかに少なくなります。そして見つけた最良の解は、最適解から最大x%の誤差であることが保証されます。
そんな感じです。これはうまくいきますか？誰か似たようなことを聞いたことがありますか？
- shoo
著者が指摘したベースラインのナップサックアルゴリズムの問題、つまりメモリ不足になるという点に興味を持ちました。
pytorchの様々なナップサック実装（著者が貢献したものを含む）はここにあるようです:
https://github.com/pytorch/pytorch/blob/31ba9a56657bc887c957...
例えばここで使われているようです
https://github.com/pytorch/pytorch/blob/31ba9a56657bc887c957...
ベースラインのdp_knapsackコードをじっと見ていて目に飛び込んできたのは、メモリを測定する単位が何を意味するのかが非常にはっきりしないことです。dp_knapsackコードは、memoryとmax_memory（メモリ予算とも呼ばれる）が浮動小数点数であると仮定しています。dp_knapsackは内部的にこれらの浮動小数点のメモリ値を10,000倍し、整数に丸めてメモリ値を量子化します。量子化されたmax_memory値が動的計画法テーブルの1つの次元のサイズを定義します。もう1つの次元はアイテム数でサイズが決まります。
partitioners.pyのパッチを読む限り、メモリ予算は0.0から1.0の間の浮動小数点数であることを意図しており、おそらく各アイテムのメモリはそのメモリ予算に対して正規化されているのでしょう？
もしそうで、dp_knapsackがmax_memory=1.0で呼ばれると、nアイテム用の2次元配列が割り当てられ、m=10,000の量子化されたメモリ値が形状(n+1, m+1)として割り当てられます。つまり100アイテムの場合、形状(101, 10001)の配列になり、float32で埋められるので要素あたり4バイト、テーブルに必要なサイズは…約4MBになります。[…]