日本ユニシスの加藤氏が登壇したセッションは「You Might Also Like: A Multi-GPU Recommendation System」というタイトルが付けられている。その名のとおり、マルチGPUで動作するリコメンドシステムを紹介するセッションだ。

　加藤氏は「同僚がリコメンドシステムの処理の遅さで悩んでいたので、こういう方法もあるという提案のために作った。CUDAには理工学向けアプリケーションが多いが、CUDAのビジネス利用の1つとして、新しいフィールドを開ければ面白いと思った」と、動機を語る。

　リコメンドシステムとは、Eコマースサイトなどで使われるもので、利用者の購入履歴からお勧めの製品をピックアップしてくれるシステムだ。Amazonなどでそのシステムに触れたことがある人も多いはずだ。

　ここで紹介されたリコメンドシステムは協調フィルタリングと呼ばれるもの。その手法は、利用者と製品をマトリクスに配置し、そこに利用者の購入履歴から特定のパラメータをはめ込む。そのパラメータから傾向(嗜好)が近い利用者を計算で割り出し、その嗜好が近い利用者が購入した製品をお勧め製品としてピックアップする仕組みだ。

　しかしながら、1つのEコマースサイトが扱う製品は膨大な量になるし、ユーザー数によってもどんどんマトリクスは膨れあがる。つまり、そのマトリックスは膨大な大きさとなる。例えば1,000人の利用者、1,000個の取り扱い製品であれば、1,000×1,000のマトリクスが生成される。その計算量は膨大なものとなる。

　そのため、まず「Singular Value Decomposition(SVD、特異値分解)」というプロセスを踏む。これは製品と利用者からなるデータマトリクスの行列を分解し、小さなマトリクスへと圧縮する処理。データの精度は下がるが、行や列同士の相関関係が維持された状態で分解することになる。

　次いで、分解された各行列データを利用して、嗜好が近いことを求める計算が行なわれる。それには「k-Nearest Neighbor(k近傍法)」と呼ばれる手法を使う。距離が近い順にk個のオブジェクトを選び出すというのもので、これにより似た嗜好のユーザーが購入したお勧めの製品が浮かび上がるということになる。リコメンドシステムにおいては、kの値はそれほど大きくないのが特徴で、例えば、1万番目にお勧めする製品といったものは不要なわけで、大きくても数百程度の値であるという。

リコメンドシステムの基本的な考え方。スライドは、A～Eの利用者、W～Zの各製品をマトリクスにし、Aさんが”X”という映画を購入し、近いベクトルを持つBさんが高い評価をしている”W”という製品がリコメンドされるという内容になっている	一般的なリコメンドシステムのプロセスとして、マトリクスをSVDで圧縮し、分解された行列を使ってk-Nearest Neighborを使って上位k個の近似データを割り出す、という処理が行なわれる

●SVDとk-Nearest NeighborをCUDAで実装

　では、この2つのステップをどのようにCUDAへ対応させたか、という話である。まずSVDであるが、先述のデータマトリクスはある利用者がある製品を購入したところでデータをはめ込んでいくことになるため、そのほとんどはデータがない。しかし、やりたいことはデータがある部分をマッチングしていく作業である。そうした処理を行なうアルゴリズムとして、B.Webb氏が作成した広く知られるシリアルなアルゴリズムがあるという。

　日本ユニシスの加藤氏は、このアルゴリズムを基に、行と列を別々に処理させる方法を発案。元々のアルゴリズムとは分解後のデータが異なる結果になるものの、同じ方向で収束するという。そして、各行、各列の間は完全に独立しているので、この手法ならばパラレルに処理できるというアイデアだ。

広く知られるSVDのアルゴリズムでは、行・列をまとめてループに割り当てて処理する。加藤氏のアイデアは、各行列は完全に独立しているので、これを行と列に分けてループ処理をさせても問題ない。だからパラレル処理が可能になるというもの	このアイデアを図式したしたスライド。行方向をU^T、列方向をVに分割する際、まず行方向を複数のスレッドでパラレル処理し、次に列方向の値を同様に処理していく

　次にk-Nearest Neighborであるが、この基本的なアルゴリズムは、与えられた数値を比較して距離の近似性を割り出し、ソートするという流れになる。

　まずベクトルの近似性を割り出す部分は、いわゆるN-Bodyに非常に近いアルゴリズムになるという。複数のオブジェクトの相互作用を扱うプログラムであるN-Bodyも各オブジェクトの距離を知る必要があるわけで、k-Nearest Neighborもそれに近いというわけだ。しかし、N-Bodyの場合、各オブジェクトは最大でも6次元程度の値が付いているが、k-Nearest Neighborでは数百次元の値を扱う必要がある。そのため、各スレッドが利用するデータをGPU内の各SMが持つシェアードメモリ上に展開する際に、容量が不足するという。

　この対処として考案されたのが、次元方向に配列をスライスし、各ブロックを順次実行するという方法だ。ユークリッド空間の法則に基づけば距離は2乗の和になるので、シェアードメモリを活用できる範囲で一定数のブロックを読み込んで2乗の和を取る、ということを繰り返せば、距離が求められるという。

　次にソートのアルゴリズムであるが、ここでヒープソートは複数の配列をパラレルに処理し、上位k個を割り出すのが重要となる。ソートを複数のスレッドで処理する際、最終的な結果は統合して整合性を取るアトミック処理を行なう必要があるが、加藤氏のアルゴリズムでは、格納されたデータのうち何番目以下のものはすべて切り捨て、という処理を各配列の処理に加える。

　最終的にはかなりのデータが切り捨てられて上位k個だけのデータを持つヒープを集めてアトミックな処理を行なっている。このような、ソートして上位k個のデータを抽出するというアルゴリズムについては、さまざまなアプリケーションへの応用が考えられる分野であり、加藤氏は今後もフォーカスしていきたい分野であるとした。

近似性を求める処理において、膨大なデータ量となるリコメンドシステムではシェアードシステムが不足する問題が発生する。これを避けるため配列をスライスしてシェアードメモリの容量が許す範囲で生成されたブロック単位でパラレル処理を行なう	ヒープを使って上位k個のデータを割り出す処理を行なう際、下位のデータをどんどん切り捨てて処理を進めていく。先述のとおリコメンドシステムではkの値がそれほど大きくないため、最終的なアトミック処理を行なう際に残っているデータはそれほど多くないので処理の高速化につながる

　さて、次にマルチGPUにおけるk-Nerest Neighborへの適用について言及があった。1つは、近似性(距離)計算においては、各GPUが同じ数のブロックを持つように割り当てることが重要であるとし、マトリクスが対称性を持つことが多いこと考えれば、プレゼンで示されるような順序で配置するのが妥当であるとしている。

　また、ソートにおいては、行単位、列単位で処理を実行したいが、上述の手法では別々のGPUが同じ行列にあるデータを分散して持つことになってしまうので、最終的にそれを統合するアトミック処理が必要になる。ここは先の応用で、各GPUが持つデータをヒープソートして上位k個のデータを抽出。それを最終的にCPU側でアトミック処理するという手法が採られる。kの値がそれほど大きくないので、CPUで処理させてもそれほど大きなパフォーマンスロスにはならないという判断だ。

マルチGPUにおけるk-Nearest Neighborの適用。各GPUに割り当てるブロックが同じ数になるように割り当てる	その割り当て方をすると、一連のデータを別のGPUで持つ事態が発生するが、先の手法と同じで、各GPUで処理して残る上位k個のデータはそれほど多くないので、各GPUから上げられたデータをCPU側でアトミック処理をさせる。ここをGPUで処理させることも可能だが、全体の計算量に比べればわずかなので、CPU側で処理させても問題ないという判断である

　最後にベンチマークの結果であるが、GeForce GTX 280とCore i7の比較が示された。ただし、ここでいうCore i7(つまりCPU)の処理はマルチスレッド化されておらず、シングルスレッドのプログラムとなる点には注意が必要だ。この結果を比較すると、SVD処理でおおむね25倍以上。k-Nearest Neighborにおいては、2つの距離関数でのデータが紹介されており、計算量が多くなるHellinger Distanceに基づいた処理の方で、Core i7と2つのGeForce GTX 280×2個の環境で300倍以上の高速化が見られる結果となっている。

　例えばSVDにおいて、マトリクス数が増えるとCPUに対するアドバンテージが小さくなるなど、パフォーマンスの細かい研究はまだなされていないそう。例えば、k-Nearest Neighborにおける距離計算については、加藤氏はブロックをスライスする手法を用いているが、別の手法を用いたGPUでの高速化も他の人によって提案されている。しかし、どちらが高速かなどのテストは未だ行なわれてないという。今後さらなるパフォーマンスの調査が行なわれ、チューニングも深まっていくのではないだろうか。

SVDにおけるパフォーマンス比較。CPUはシングルスレッド処理ではあるが、GPUに処理させることでCPUに対して最大30倍を超える性能向上を得られている。ただし、マトリクスが大きくなるほど、向上の度合いは小さくなっている	k-Nearest Neighborのパフォーマンス比較は、距離関数を変えた2パターンのテスト結果が示された。ここではマルチGPUにおける性能向上もしめされている。より計算量が増えるHellinger Distanceを用いた場合で、とくに大きな性能向上が見られることが分かる

　ちなみに、加藤氏が今回紹介した内容は、アルゴリズムを開発したという研究レベルの話であり、実際のアプリケーションへの適用はこれから提案していく話になる。「現在動いているシステムに対して性能的な不満がリプレースの動機になることは少ないようだ」と加藤氏は述べており、ビジネス展開においては、今後、さまざまな角度からのコスト計算など別のアプローチも求められるところだ。

　もっとも、マトリクスに当てはめるパラメータは実際のアプリケーション次第であり、CUDAによるリコメンドシステムという視点で開発されたものではあるものの、他の分野での応用も可能だ。日本発のビジネス向け提案として期待したいアイデアである。