アンチパターンてんこ盛りの案件でGPUは生かせるのか

　積極的なAWS活用で、多くの効果を得たナビタイムジャパン。既存サービスの移行だけではなく、AWSならではのメリットを得ることができないかと、最新テクノロジー活用の研究も進めている。

　ナビタイムジャパンが取り組む最新テクノロジー活用の研究、その一つがGPUを使った経路探索だ。クラウドサービスのGPU機能は、近年多方面から注目を集め事例も多数発表されているが、その多くが機械学習関連だ。これらの事例により、単純な演算を並列化して超高速化することにおいて、GPUが高い効果を示すことは広く知られることとなった。ナビタイムジャパンが取り組むGPU活用は、それらの事例とは一線を画す。同社が目指す経路探索は、これまで「GPUには向かない」といわれてきた、いわゆるアンチパターン（不適切な解決策）だらけの要件なのだ。

　ナビタイムジャパンのシニアエンジニア吉濱 誠氏（開発部ACTS）は、GPU活用を模索する理由を2点述べた。1つ目は、経路探索処理の高速化が必要になっていることだ。「全サービスにおける利用規模は、2017年6月には月間3700万UU（ユニークユーザー）でしたが、同年12月には月間4100万UUにまで増加しています。1件当たりの処理を高速化しなければサービス品質を維持できません」（吉濱氏）。2つ目の理由は経路品質の向上だ。

ナビタイムジャパン　吉濱 誠氏

　経路品質の向上とは具体的にどのようなことを指すのか。それを説明するために吉濱氏はまず、現状の経路探索エンジンの検索アルゴリズムについて紹介した。ナビタイムジャパンは全国2700万リンクのネットワークデータを持っている。リンクとは、交差点や乗り換えポイントのことだ。CPUで全リンクを使って検索すると多大な時間がかかるため、ごく近距離の場合のみ全リンクを参照するレベル1探索をする。ある程度遠い目的地が指定された場合には、幅の狭い道を切り捨ててリンク数を減らしたレベル2探索をする。さらに長距離の場合は、国道や高速道路のみに絞り込んだレベル3探索をする。切り捨てられるリンクがあるとはいえ、長距離移動の際は国道もしくは高速道路を中心に走行することが多いため、探索時間と結果のバランスは取れている。

　とはいえ、見えないリンクがあることは確かだ。「全リンクを探索できれば、よりよい経路を提示できる可能性があります。それが経路品質の向上です」（吉濱氏）

　ところでGPU利用の効果を高めるプログラミングでは、条件分岐をできるだけ避けて連続したメモリ領域にアクセスさせることで、キャッシュのヒット率を上げることがお約束とされている。対して全リンクを参照する経路探索は条件分岐の連続、ネットワークデータへのランダムアクセスが多数発生するという正反対の条件を抱えている。処理粒度も大きく、小さい処理を膨大にこなすことを得意とするGPUには向いていない。GPUの強みに沿っているのは要素数が多く並列化して高速化するという1点のみ。

　「処理粒度が大きくてもGPUの効果は出るのか。そもそもGPUで経路探索はできるのか。そのレベルからの実証実験でした」（吉濱氏）。作成したプロトタイプでは、GPUインスタンスの「p2.xlarge」を利用し、2700万リンク、2.6GBのネットワークデータを全てGPUのメモリに載せて動かした。

プロトタイプを作成し、全2700万リンクを使った経路探索をGPUインスタンスで実行

　探索時間を比較するため、CPUでも2通りの探索を実施。1つ目は距離に合わせてネットワークデータを省略する従来手法、2つ目はGPUと同等条件で全ネットワークを考慮して探索する手法だ。

　全ネットワークデータを参照した場合は、圧倒的にGPUが優位だった。探索距離が伸びるほど優劣の差は広がり、しかもCPUでは50キロ程度の経路までしか検索できなかった。

　続いて、GPUでは全ネットワークデータを参照し、CPUではネットワークデータを省略して探索するという比較をした。今度はネットワークデータを省略した分、CPUが優位だった。GPUはCPUと比べて2.7倍ほどの探索時間を要した。

　参照しているネットワーク数が違い、高品質な探索ができるとしても、現状サービスの3倍近い時間を要するとなると現実的ではなくなる。探索アルゴリズムの改善やGPUに合わせたプログラミングの改善など最適化を施した結果、CPUの2倍程度までに探索時間を短縮できたという。そこまで最適化してから、インスタンスタイプをp2.xlargeからよりスペックの高い「p3.2xlarge」に変更したら、「あっさりとCPU同等の処理時間を実現しました」と吉濱氏は語る。2.7倍から2倍にまで最適化するのにかけた時間は約1カ月、インスタンスタイプを変えて2倍からCPU同等に高速化するのに要した時間は1時間ほどだったという。

NVIDIAの「Volta」アーキテクチャに基づくGPU（p3.2xlargeインスタンスのGPU）を使うだけで2倍以上の高速化を達成

汎用的な処理に生かせるほど進化したGPUをAWSでどんどん試そう

　吉濱氏らは、全ネットワークデータを参照しながらも、ネットワークデータを省略したCPUでの経路探索と同等の探索時間をGPUで実現した。最終的な決め手は圧倒的なGPUパワーだった。しかしp3.2xlargeをはじめとするP3インスタンスは高コストなので、全探索に利用するのは現実的ではないことも分かった。

　アルゴリズムをさらに最適化して、ある程度の距離まではp2.xlargeなどのP2インスタンスでもネットワークデータ省略版のCPUと同じくらいの時間で探索できるようになった。「その上で1000キロを超えるような長距離に探索のみをP3インスタンスに割り当てるようにして、コストと経路品質のバランスを取れる仕組みを考えています」（吉濱氏）

実証実験の最新状況では、P2インスタンスとP3インスタンスを使い分け

　こうした取り組みを紹介した吉濱氏は、最後にGPU活用について幾つかの提言をした。GPUに不向きといわれる粒度の高い処理でも、並列度が高ければ効果は出る。P2インスタンスでも12GBのデバイスメモリを割り当てられるので、ある程度大きなデータを必要とする汎用（はんよう）的な処理でも手軽に高速化できる。さらに、パーツを調達してオンプレミスで実験するには100万円単位のコストがかかる最新GPUを使った実証実験が、AWSなら1時間数ドルで試せるので、もっといろいろなことに活用してみるべきだという。

吉濱氏は、もっといろいろなことにGPUを使おうと訴えた

　「GPUインスタンスを“機械学習以外”でもどんどん使いましょう。お勧めは、まずP2インスタンスで試すことです。GPUでも処理できることをP2インスタンスで示した上で、インスタンスタイプをP3インスタンスに変更するだけで高速化を実現できます」（吉濱氏）

　クラウドだからこそできる、GPUの可能性を探る手軽な実証実験。同様の取り組みが多方面に広がれば、GPUの活用範囲は広がっていくかもしれない。