SoCS 2017 掲載論文の解説

SoCS 2017: The 10th Annual Symposium on Combinatorial Searchに、IDA* 探索を GPU を利用して高速化する手法に関する論文が採択された。

論文のタイトルは「Block-Parallel IDA* for GPUs」であり、以下のリンクから閲覧できる。

これは修士学生の頃の研究成果を、卒業後に投稿したものである。 採択は5月4日で、会議は6月16-17日に Pittsburgh で行われた。 自分は既に働いているので会議には参加せず、発表は共著者である元指導教官にお願いした。

概要

日本語で検索しても辿り着けるよう、概要を書いておく。 (かなり端折っているので、詳しくは論文を読んでいただきたい。)

IDA*

グラフ探索やIDA*の説明は、Wikipediaや元所属研究室の有志が2015年に書いてくれたAdvent Calendarに譲る。

掻い摘むと、IDA*とは問題についての知識をうまく利用しながら先読みをし、最適な行為の列を見つけるアルゴリズムであって、解の長さに対しメモリ使用量が指数的には大きくならないものである。 (余談だが、IDA*の提案者Richard E. Korf先生は、自分の元指導教官の元指導教官である。)

主な応用としては、色々なパズル、カーナビ、タンパク質の構造決定などがある。

先日少しバズっていた深層学習を超えた手法とは何かで書かれているように、巷で大流行の機械学習に、自動行動計画・先読み・探索・推論を組み合わせるのが一種のトレンドになるような予感がある。(もうなっている?) IDA*はこの探索における基礎的な技術のうちのひとつである。(ちなみに自動行動計画は自分の元所属研究室の主要なテーマであった。)

背景

本研究の主要な成果は、GPUでIDA*を効率的に実装する方法を提案したことだ。 GPUA*の並列化を行った先行研究としてChou, 2015があった。 しかしA*では、解の長さに対しメモリ使用量は一般に指数的に大きくなる。 例えばCPUでの直列A*でも、数GBのメモリをふつう1分以内程度で使い切る。 そのため、GPUの性能を使って本当に解きたい大規模な問題が解けないのである。 一方、IDA*では解の長さに対してメモリ使用量は線形程度に抑えられる。 そのため、メモリ使用量の制約からA*が解けない大規模な問題を解ける可能性がある。

GPUを使ってIDA*を並列化するとき、肝となるのは処理の分割方法である。 幅優先探索深さ優先探索などの単純な探索では、探索木の対称性が高く、素朴な方法で仕事を均等に分配できる。 一方IDA*では、探索木の形状の対称性は低く、実際に探索するまでこの形状はわからない。

IDA*の探索処理をどう分割し、並列化するかに関する研究は古くからある。 しかしその大部分は、CPUまたはSIMD計算機の並列化に関するものである。 GPUの実行モデル(NVIDIAはSIMTと呼んでいる)は、また違った特徴を有する。 過去の研究成果を元に、いくつかの手法を再実装してみたところ、GPUを前提に設計されていないため発生する種々の問題から、十分な性能が得られなかった。

Block-parallel IDA*

そのため本研究では、IDA*をGPUを利用して効率的に実装する手法としてBlock-parallel IDA*を提案した。

一般的なIDA*の並列化では、初期状態から少しだけ探索を行い、そうして得られる探索途中のノードを各スレッドに割り当てていた。各スレッドは割り当てられたノードを初期状態とし、探索の続きを行う。各々が探索する部分木の大きさは未知なので、処理の量にばらつきが出る。これを動的に調整するためのメカニズムにより処理が複雑化していた。

これに対して、提案手法Block-parallel IDA*では、各ノードはスレッドではなくブロックに割り当てられる。 これはオセロのゲーム木探索にGPUを利用する研究(Rocki and Suda, 2010)に着想を得たものである。 本論文ではIDA*の並列実行において、ブロック内のスレッドが明示的な同期を取らずに処理を行える方法を示した。 また、ブロック間のノードの分配はGPUのハードウェアスケジューラを利用できるため、ここでもやはり明示的な同期が不要である。 明示的な同期や処理の動的な再分配が不要なため、実装は非常にシンプルである。

実験

実験的に以下のことを確認した。

  • 1536コアのGPUにおいて、直列処理と比べて並列処理は約660倍高速である
  • 処理の均等な分割がほぼ完全に達成されている
  • CPUでの直列処理と比べて、1536コアのGPU1枚での並列処理は約5倍(ある補正をすると約7倍)高速である

所感とやり残し

GPUを使って5倍(あるいは7倍)高速化というのはさほどインパクトが大きくないかもしれない。しかし、一見GPUには向かない処理をうまく変換し、それなりの高速化を達成したという意味で価値のある成果だと思っている。

手法としては複数GPUの場合もほぼそのままでスケールするのではないかと思っている。しかし、これを実際に確認するまでは手が回らなかった。 また、もしGPU100枚や1000枚の規模になると、きっとまた一味違った困難が発生するのではないかとも考えている。

より多様な問題で性能評価を行うことも有意義だろう。 Block-parallel IDA*は問題にほぼ依存しないよう設計したつもりである。 しかし問題によっては、GPUの共有メモリに探索に必要な情報が収まらないなどの小さな困難は少なくとも発生するだろう。(この問題に関しては、教科書的にグローバルメモリから共有メモリに適当にprefetchすることで対処できるだろうと考えている。) 有効な問題の範囲を明らかにし、困難が発生する場合にはその対処方法を開発することは残された課題である。

Call for V100

GPUプログラミングわりと楽しかったので、探索技術に興味のある石油王の方が見ていたらV100(1699万円?)買ってください。