PyTorch의 새로운 knapsack solver로 피크 RAM을 20배 줄이다
0/1 Knapsack Problem in PyTorch
PyTorch의 activation memory budget solver인 dp_knapsack_sliding_hirschberg를 소개한다. 기존 dp_knapsack은 전체 DP 테이블을 할당해 메모리를 많이 사용했지만, 슬라이딩 윈도우와 Hirschberg 기법을 결합해 테이블 크기를 (2, max_weight)로 줄여 피크 RAM을 20배 절감한다. 64GB RAM에서 기존 solver는 100개 아이템에서도 크래시가 발생하지만, 새 solver는 2000개 아이템까지 처리 가능하다. SciPy를 사용할 수 있다면 ilp_knapsack이 더 빠르다.
64GB RAM 환경에서 dp_knapsack은 100개 아이템 문제에서 크래시가 발생하지만, dp_knapsack_sliding_hirschberg는 같은 RAM 예산 내에서 2000개 아이템 문제를 처리할 수 있다.