無限期間動的計画法のGPU実装における収束判定の処理時間削減に向けた検討

• Item type: SIG Technical Reports(1)
• 公開日: 2016-02-23
• タイトル: 無限期間動的計画法のGPU実装における収束判定の処理時間削減に向けた検討
• タイトル / 言語: en
• タイトル: Consideration to Decrease Computational Times in Verifying Convergence in GPU Implementation of Infinite-stage Dynamic Programming
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: GPU/メニーコア
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 愛媛大学大学院理工学研究科
• 著者所属: 愛媛大学大学院理工学研究科
• 著者所属: 愛媛大学大学院理工学研究科
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Ehime University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Ehime University
• 著者所属(英): en
• 著者所属(英): Graduate School of Science and Engineering, Ehime University
• 著者名: 稲元, 勉; 樋上, 喜信; 小林, 真也
• 著者名(英): Tsutomu, Inamoto; Yoshinobu, Higami; Shin-ya, Kobayashi
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では，無限期間マルコフ決定過程のための動的計画法を GPU 上で実行する際の計算時間を削減するため，動的計画法が収束したか否かを判定する処理を効率化する技法を提案し，小規模な問題に対する評価結果を示すことを目的とする．提案技法は，GPGPU の枠組みとして NVIDIA 社の CUDA を用いることを前提とし，状態価値の変化量の最大値が閾値以下であるか否かとして収束判定を行う際に，GPU 側で部分状態空間に対応するスレッドブロック単位で変化量の最大値を算出しておき，この値の全部分状態空間にわたる最大値をホスト側で算出するという素朴なものである．計算結果では，animat 問題，mountain-car 問題を対象とし，提案技法を用いた場合の計算時間を示す．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose a technique to decrease the computational time of the value iteration program which is implemented on a GPU to solve infinite-stage Markov decision process. In order to judge whether the value iteration has been converged or not, the difference between state values before and after a sweep, which represents the computation to update all state values, is calculated for each state, then the the maximum of such differences over the whole state space is calculated. Here, it is obvious that taking such maximum over whole state space is equal to taking the maximum over values each of which is the maximum difference of state values over a sub state space. The proposed technique premises to use the CUDA to implement the value iteration for NVIDIA's GPU, and considers a thread block in the CUDA as a sub state space, then conducts computations to take the maximum difference of a sub state space in a corresponding thread block on a GPU. The effectiveness of the proposed technique is examined in terms of computational times through its applications to the animat problem and the mountain-car problem.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2016-HPC-153, 号 29, p. 1-6, 発行日 2016-02-23
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8841
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会