ある在庫管理問題の動的計画法による解法とCUDAを用いた高速化

• Item type: Trans(1)
• 公開日: 2008-08-21
• タイトル: ある在庫管理問題の動的計画法による解法とCUDAを用いた高速化
• タイトル / 言語: en
• タイトル: Solution of a Stock Management Problem by Dynamic Programming and Its Acceleration Using CUDA
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: GPU応用
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 名古屋大学大学院工学研究科計算理工学専攻
• 著者所属: 名古屋大学大学院工学研究科計算理工学専攻
• 著者所属: 名古屋大学大学院工学研究科計算理工学専攻
• 著者所属: 京都大学大学院理学研究科物理学・宇宙物理学専攻
• 著者所属: 名古屋大学大学院工学研究科計算理工学専攻
• 著者所属(英): en
• 著者所属(英): Department of Computational Science and Engineering, Graduate School of Engineering, Nagoya University
• 著者所属(英): en
• 著者所属(英): Department of Computational Science and Engineering, Graduate School of Engineering, Nagoya University
• 著者所属(英): en
• 著者所属(英): Department of Computational Science and Engineering, Graduate School of Engineering, Nagoya University
• 著者所属(英): en
• 著者所属(英): Department of Physics, Graduate School of Science, Kyoto University
• 著者所属(英): en
• 著者所属(英): Department of Computational Science and Engineering, Graduate School of Engineering, Nagoya University
• 著者名: 李, 天; 河畠, 工; 山本, 有作; 畝山多加志; 張紹良
• 著者名(英): Tian, Li; Takumi, Kawahata; Yusaku, Yamamoto; Takashi, Uneyama; Shao-Liang, Zhang
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，ある在庫管理計画問題のGPUによる高速化について報告する．この問題は組合せ最適化問題であり，動的計画法を用いて解けるが，状態空間は連続かつ高次元であり，多大な計算量が必要である．本問題の解法を分析したところ，計算の並列性がきわめて高いこと，単精度で十分であること，メモリバンド幅への要求が高いことなどから，GPU向きであることが分かった．そこで，この解法をGPUによる汎用計算のための統合環境CUDAを用いてGPUに移植した．NVIDIA社GeForce8800GTX上で評価した結果，CPU（Intel Core2 Duo，1.86 GHz，2コア使用）で1.5時間を要する最大規模の問題を約6分で解くことができ，15倍の高速化が達成できた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We report the result of speeding up the solution of a certain stock management problem using GPU. Our problem is a combinatorial optimization problem and can be solved by dynamic programming. However, the state space is continuous and high dimensional, hence the solution requires much computational work. We analyzed the solution algorithm and found that it is suited for GPU computing, since it has enormous parallelism, requires only single precision, and requires high memory bandwidth. We therefore ported the algorithm to NVIDIA's GeForce8800GTX using CUDA, an integrated environment for GPU computing. Numerical experiments show that for the largest problem that requires 1.5 hours on a CPU (Intel Core2 Duo, 1.86 GHz, using 2 cores), the GPU can find the solution in 6 minutes, achieving 15 times speedup.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 1, 号 2, p. 221-230, 発行日 2008-08-21
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会