Tim Schmielau and Jacques du Toit, Numerical Algorithms Group Ltd
概要
nAGは、NVIDIA GPU上で効率的に動作するバッチ最小二乗法ソルバを作成しました。このコードは、tall skinny行列に対して最適化されています。これらは、ファイナンスにおけるXVAなどのデータフィッティングの問題で頻繁に発生し、通常は並列化が容易ではありません。このコードは、NVIDIAライブラリ(cuBLAS、cuSolver)を使用したバッチ処理GPU最小二乗ソルバよりも20倍から40倍高速です。これは、行列が既にGPUメモリにあるアプリケーションにおいて大幅に加速します。
CPUのみ使用するアプリケーションから見れば、CPUメモリからGPUに行列を転送するコストが支配的になります。我々は、問題サイズが十分に大きい場合に、1.5倍から12倍の間のすべての転送コストを含む時間のスピードアップを観察しました。したがって、CPUのみのアプリケーションでは、GPUを追加し、nAGのソフトウェアを使用することでスピードアップすることが可能です。nAGは、利便性と最小バッチサイズを判断するための、ユーザーシステムのベンチマークコードを提供できます。
行列が構造(例えば、多項式基底関数)を有する場合、転送データはずっと少なくて済みます。GPU上で基底関数を評価することで、現在のCPUのみのアプリケーションは十分に大きな問題に対して10倍から20倍スピードアップすることを意味します。nAGは、これを行うために必要な少量の追加GPUコードの作成に対するサービスが可能です。
バッチ線形最小二乗法
線形最小二乗法はデータフィッティングを行う多くのアプリケーションで見ることが出来ます:
minβ∈Rn=‖y−Xβ‖2
ここで、y∈Rm,X∈Rm×nです。多くの場合、設計行列Xは「縦型、tall and skinny」$m≫n$です。つまり、変数より多くの観測値があります。通常、これは、XのQR分解とそれに続く三角行列RのSVD分解で処理されます。Rは$n×n$で非常に小さいので、SVDは実行時間にほとんど影響を与えません。よってQR分解の時間が支配的です。
残念ながら、tall skinny行列の通常のQRアルゴリズムは並列化されないため、独立した最小二乗問題をより大きな問題にまとめるとより良い性能が期待できます。
ファイナンス領域では、アメリカンモンテカルロ(または条件付き期待値が近似されるときは常に)においてtall skinny最小二乗問題が生じます。ネッティングセットに独立した資産を持つXVAなどのアプリケーションでは、最小二乗計算を一括してバッチ処理することが可能です。
CPUおよびNVIDIA GPUを用いたバッチ処理オプション
1CPU上でバッチ処理される最小二乗法を実行するためには、複数の最小二乗問題上で並列化し、各問題に対してLAPACKルーチンdgelssまたはsgelssを呼び出します。LAPACKルーチンが効率的である場合、例えばMKLを用いる場合は、これは良いパフォーマンスを提供します。
NVIDIA GPUでは、cuBLASにバッチQR分解が有りますが、SVD用のルーチンはなく、Qをyに適用するために必要なバッチ処理dormqr、sormqrがありません。SVDはホスト上で(例えばMKLを呼び出すことによって)行われ、QはcuSolver内の単一行列のdormqrまたはsormqrのストリーミングコールを介して適用されます。
nAGは、500≤m≤100000,3≤n≤40に最適化された専用のバッチ最小二乗法ソルバを開発しました。列の数が多くなるにつれて、パフォーマンスは徐々に低下します。SVDはホスト上のLAPACK(MKL)によって実行されます。このソルバーは、バッチ内で行列のサイズを変更することができます。
PCI Express3.0
良好なPCIe 3接続を備えたマザーボードは、通常、約12GB/sの転送速度でホストからGPUにデータをコピーすることができます。これは、倍精度データの場合は1秒あたり1.5 x 109行列要素、単精度データの場合は1秒あたり3 x 109行列要素と言い換えることが出来ます。4.2GHzで動作するインテルCore i7-7700K上の8スレッドのテストシステムでは、上記のCPUアプローチは、少なくとも小規模な行列やバッチサイズではPCIe 3転送速度に匹敵する性能を示しました。つまり、小さな問題では、CPU実行時間はPCI Expressバス上で全行列を転送するのに匹敵する時間になります。
そこで議論を2つに分割します。次のセクションでは、行列が既にGPUに常駐しているアプリケーションについて検討します。これは、すでにGPUで部分的または完全に実行されているアプリケーションになります。
次に、行列がCPUに常駐するアプリケーションについて検討します。通常、これはGPUコンポーネントをまったく持たないアプリケーションです。ここでもバッチ処理された最小二乗法コードは利益をもたらします。
行列がGPUに常駐するアプリケーション
ここで、我々のGPU実装と、セクション3に示したNVIDIAライブラリを用いたアプローチを比較します。小さなバッチサイズ(50以下)では、我々のコードは大きな改善の余地があります。ここで、実行時間で割ったバッチ内の全行列要素数をthroughputという用語として性能を表現することとします。
図1:m×n, nは3から9とした場合の単精度と倍精度の性能。我々のコードはP100 GPU、CPUコードはIntel Core i7-7700K上での8スレッドを用いた性能。
図1は、様々なサイズの行列(行数は同じですが、列は[3-9]の範囲で均一に分散されています)のバッチ処理によるコード性能を示しています。NVIDIAライブラリは、異なるサイズの行列を持つバッチを処理できないことに注意してください。CPU実行時間は、動作の違いを示すために含めています。
図2:30m×3行列のバッチ処理における列に対する単精度と倍精度の性能。我々のコードとNVIDIAライブラリを用いたコードは共にP100上で実行した。他の問題サイズでも同じ傾向である。
図2は、均一なサイズの行列のバッチ処理で、NVIDIAライブラリを使用して構築されたバッチ最小二乗法と比較した我々のコードの性能を示しています。ここに示されたスピードアップは極めて典型的なものです。バッチサイズが大きく、行列が大きい場合も同様の結果が得られます。
行列がCPUに常駐するアプリケーション
セクション4で述べたように、PCIe3バスは1秒あたり1.5×109行列要素で倍精度データを転送し、1秒あたり3×109行列要素で単精度データを転送できます。これを図1と比較すると、バッチサイズが小さい場合、並列CPUコードは問題をGPUに転送するよりも速く解くことが解ります。しかし、バッチと行列のサイズが大きくなると、CPUのパフォーマンスが低下します。その結果、我々のテストシステムは、データをGPUにコピーして、GPU上で問題を解く方が有利になります(SVDはホスト上で実行する)。以下の数値は、以前と同様にthroughputで性能を測定しています。
図3:CPU(8 threads + MKL, Intel Core i7-7700K、PCIe転送を含む)からP100への速度向上。十分大きなバッチや行列サイズではGPUの方が高速。
図3は、PCIe転送を含む、様々なバッチや行列サイズに対する高速化を示しています。十分大きなバッチや行列サイズでは、データをGPUへコピーしてその場で解く方が高速です。倍精度計算ではその分岐点がかなり低くなっています。図4と5では均一なバッチサイズとしていますが、結果は同様です。
図4:6列と9列の行列の場合のCPU(8 threads + MKL, Intel Core i7-7700K、PCIe転送を含む)からP100への速度向上。十分大きな問題ではGPUの方が高速。
図5:15列の行列の場合のCPU(8 threads + MKL, Intel Core i7-7700K、PCIe転送を含む)からP100への速度向上。十分大きな問題ではGPUの方が高速。
性能要因
PCIe転送速度、CPU処理速度、転送データ量は、問題をGPU(具体的なGPUはそれほど重要ではありません。なぜなら、ほとんどのGPUはPCIeバスを介してデータを移動できるよりもはるかに高速に問題を解決するからです)上に移行することでスピードアップが可能かどうかを判断する重要な要素です。私たちのテストシステムにはかなりモダンなCPU(2017年1月リリース)があり、CPUがPCIeバスを介してデータを転送するよりも多くの問題をより素早く解決できるため、GPUにとっては相対的に不利です。古いCPUを搭載したシステムでは、GPU上で問題を解くことで大きなメリットが得られる可能性があります。nAGは、ユーザーシステムをベンチマークするためのソフトウェアを用意し、スピードアップの可能性を判断することができます。ここで12GB/秒の速度を達成するには、ホストにpage lockedメモリが必要です。これをGPUを使用しないホストアプリケーションに組み込むのは容易です。
入力行列が構造(例えば、多項式基底関数)を有する場合、実質的な改善が可能です。基本的なファクターのみを転送し、GPU上で基底関数を評価することで、十分に大きな問題サイズに対して10倍以上の全体的なスピードアップが得られるはずです。nAGは、この実装に対してサポートすることができますが、これはかなり少量のGPUコードを追加するのみの作業です。
小規模バッチの最適化
我々の実装は、小規模バッチサイズ(50行列以下)では改善の余地があります。行列をCPUあるいはGPU上のどちらに置くかや問題サイズによって、これらの最適化が有効かどうかが決まります。
コードへのアクセス
このコードはトライアル利用が可能です。GPUあるいはCPU上のどちらでもデータを入力できます。CPUの場合はすべてのデータ転送は透過的に扱われるため、ユーザーの視点からは通常のCPUライブラリルーチンのように振舞います。特に、ユーザはGPUプログラミングに関する知識を必要としません。
ご興味がある方は、担当窓口までお問い合わせください。