階層的挟み撃ち探索を用いた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木の求解を情報家電組込用マルチコアプロセッサ上で高速に行うために、プロセッサコア数より多くの経路を並列・並行に深さ優先探索することで、メモリ量を小さく抑えつつプロセッサコア数にスケーラブルに速度向上する手法を提案し、評価した。本手法では、評価値の高い節点から探索する探索経路と評価値の低い節点を含む探索経路を並列探索し、さらに、少ないプロセッサコア数でより高速に求解するために、プロセッサコア数よりも多くの経路を並列・並行に探索する。また、各プロセッサコアの探索に深さ優先探索を用いることで、少ないメモリ環境での探索が可能となる。また、シングルプロセッサにおいても評価値の高い節点から探索する探索経路と評価値の低い節点を含む探索経路を複数同時に探索するために、並行処理を用いて探索する手法を提案し、評価した。本手法を用いることで、シングルプロセッサにおいても従来の評価値の高い節点からのみの探索よりも高速化が可能となる。シングルプロセッサ上で複数の経路を並行に探索するために、擬似的なスレッドを用いることでスレッド生成・切り替えにかかるオーバヘッドを削減でき、また、適切な箇所でスレッドを切り替えることができるため、並列処理には必須であるスレッド間の排他制御も削除できる。

探索问题被积极研究为人工智能的基础，并以多种方式使用，例如表达人类的思想和推理。但是，如果搜索范围很宽，则有必要长时间发现解决方案，因此需要快速解决方案。因此，在这项研究中，我们使用并行处理和并行处理来加快处理为和/或树的搜索，例如和/或树。通常，启发式搜索试图通过仅搜索具有高评估值的路由来提早找到解决方案，但是存在一个问题：当在评估值低的路线上找到解决方案时，解决方案需要很长时间才能解决它们。今年，我们提出并评估了一种方法，该方法允许在多核处理器上更快地解决和/或树，通过搜索平行且与处理器核心数量平行的路径的深度优先级，以嵌入信息设备，从而减少了可扩展的速度，从而减少了可扩展的速度，从而减少了可扩展的速度。在此方法中，并行搜索了来自具有较高评估值的节点和包括较低评估值的节点的搜索路径，并并行搜索，并且为了更快地找到少量的处理器核心，比并行且并行搜索的处理器芯的数量要多。此外，通过对每个处理器核心进行深度优先搜索，可以在小的内存环境中执行搜索。此外，在单个处理器中，提出了一种使用并行处理的搜索方法，并评估了一种搜索搜索路径，该搜索路径是从具有高评估值的节点搜索的搜索路径，以及包括评估值低的节点的搜索路径。通过使用此方法，即使是单个处理器也可以用来加快从具有高评估值的节点的搜索。通过使用伪线程在单个处理器上并行搜索多个路由，可以减少线程生成和切换所需的开销，并且可以在适当的位置切换线程，因此可以在线程之间进行独家控制，这对于并行处理至关重要。

项目成果

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

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

• 发表时间: 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