Fast Algorithm of Inventory Management using Dynamic Programming on GPU

Abstract

In this paper, we propose an efficient GPU implementation of computing the inventory manage- ment problems solved by dynamic programming. In existing GPU implementations, repeat synchronization is necessary, and the overhead of calling the kernel for this necessitates a delay in calculation time. In addition, another method with different calculation order was also implemented, and a hybrid implementation that combines two kinds was also implemented to speed up. Therefore, in the proposed GPU implementation, by preparing flags for managing calculation order for each element in the table, we calculated the problem with one kernel calling and speeded up. As an evaluation experiment, we implemented the proposed method in NVIDIA Tesla V100 and measured the execution time. As a result, the proposed method achieves up to 3.41 times as much as the existing GPU implementation, and up to 1094.57 times faster than the sequential CPU implementation.