階層的挟み撃ち探索を用いたAND/OR木探索の並列処理による高速化

使用分层钳搜索的并行处理加速 AND/OR 树搜索

• 批准号: 06J06909
• 负责人: 鷹野 芙美代
• 金额: $ 1.79万
• 依托单位: Waseda University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06J06909/
• 关键词: 並列処理; 並行処理; 探索アルゴリズム; AND; OR木; 高速化手法; 人工知能; マルチコア; 並行探索; 探索問題

探索問題は人工知能の基礎として盛んに研究されており、人間の思考・推論の表現など様々に用いられている。しかし、探索範囲が広いと解の発見に長時間必要となるため求解の高速化が望まれている。そこで、本研究では、AND/OR木として表される問題の探索を例として、並列処理・並行処理を用いて処理の高速化を図る。一般にヒューリスティック探索では、評価値の高い経路のみ探索することで早期に解を発見しようとするが、評価値の低い経路上に解がある場合には求解に非常に長い時間を要するという問題がある。本年は、AND/OR木の求解を情報家電組込用マルチコアプロセッサ上で高速に行うために、プロセッサコア数より多くの経路を並列・並行に深さ優先探索することで、メモリ量を小さく抑えつつプロセッサコア数にスケーラブルに速度向上する手法を提案し、評価した。本手法では、評価値の高い節点から探索する探索経路と評価値の低い節点を含む探索経路を並列探索し、さらに、少ないプロセッサコア数でより高速に求解するために、プロセッサコア数よりも多くの経路を並列・並行に探索する。また、各プロセッサコアの探索に深さ優先探索を用いることで、少ないメモリ環境での探索が可能となる。また、シングルプロセッサにおいても評価値の高い節点から探索する探索経路と評価値の低い節点を含む探索経路を複数同時に探索するために、並行処理を用いて探索する手法を提案し、評価した。本手法を用いることで、シングルプロセッサにおいても従来の評価値の高い節点からのみの探索よりも高速化が可能となる。シングルプロセッサ上で複数の経路を並行に探索するために、擬似的なスレッドを用いることでスレッド生成・切り替えにかかるオーバヘッドを削減でき、また、適切な箇所でスレッドを切り替えることができるため、並列処理には必須であるスレッド間の排他制御も削除できる。

The exploration problem is the foundation of artificial knowledge, research, human thinking, inference and performance. Since it takes a long time to explore the broad scope and solve the problem, there is a high demand for high-speed solution. In this paper, we explore the problem of parallel processing and parallel processing and speed up the processing. Generally speaking, it is necessary to solve the problem of very long time in order to find out the solution in the early stage. This year, the AND/OR algorithm for solving the problem of information appliance group is proposed and evaluated. This method includes parallel exploration, parallel exploration. The exploration of the environment is possible. The method of parallel processing is proposed and evaluated. This method can be used to improve the speed of exploration. In addition, the number of parallel paths to explore, the number of parallel paths to explore

项目成果

証明数・反証数を用いた反復深化法における複数経路並行探索の並列化

使用证明数和证伪数的迭代深化方法中多路径并行搜索的并行化

• 发表时间: 2006
• 期刊: 情報処理学会研究報告 ハイパフォーマンスコンピューティング No.107
• 作者: A.Satou;V.Ryzhii;T.Otsuji;M.S.Shur;A. Satou;鷹野芙美代
• 通讯作者: 鷹野芙美代

Parallel and Concurrent Search for Fast AND/DR Tree Search on Multicore Processors

多核处理器上快速 AND/DR 树搜索的并行和并发搜索

• 发表时间: 2009
• 作者: A.Satou;V.Ryzhii;T.Otsuji;M.S.Shur;A. Satou;鷹野芙美代;Fumiyo Takano;Fumiyo Takano
• 通讯作者: Fumiyo Takano

Multiple-Paths Search with Concurrent Thread Scheduling for Fast AND/OR Tree Search

• DOI: 10.1109/cisis.2009.65
• 发表时间: 2009-03
• 期刊: 2009 International Conference on Complex, Intelligent and Software Intensive Systems
• 作者: Fumiyo Takano;Y. Maekawa;H. Kasahara