ヘテロジニアス計算機環境における並列探索アルゴリズムの研究
【研究分野】知能情報学
【研究キーワード】
探索 / 並列アルゴリズム / Heuristic search / artificial intelligence / 探索アルゴリズム / 人工知能 / 並列探索アルゴリズム
【研究成果の概要】
最適解（最小コスト解）を保証するヘテロジニアス並列探索アルゴリズムBlock-Parallel IDA*を開発した。Block-Parallel IDA*はGPUのBlock毎に探索木の部分木を割り当てることにより、従来のスレッド並列GPU探索アルゴリズムより優れた性能を得られることを実証した。一方、最適解を求めるのは難しい問題において充足解を求めるヘテロジニアス並列探索アルゴリズムBatch Monte Carlo Random Walk(BMRW)を開発して、従来のRandom Walkより優れた結果を得られることを実証した。
【研究の社会的意義】
近年、従来型の演算コアを数十個搭載する主演算装置（CPU）に加えて、数千個の演算コアを搭載するGPUを両方搭載しているヘテロジニアスな計算機が普及している。人工知能においてエージェントやロボットの自動行動計画問題及び、経営工学における生産スケジューリング問題や施設配置問題等、多くの難解な探索・最適化問題に対して並列処理能力を十分に発揮できるグラフ探索アルゴリズムを設計することが必要である。本研究においてCPUとGPUを同時に有効に使う探索アルゴリズムを提案・解析した。
【研究代表者】
【研究種目】基盤研究(C)
【研究期間】2017-04-01 - 2021-03-31
【配分額】4,680千円 (直接経費: 3,600千円、間接経費: 1,080千円)