Intel® Optimized MP LINPACK Benchmark の詳細

Intel® Optimized MP LINPACK Benchmark は、行ピボットによるガウスの消去法で行列の LU 分解を計算します。P が行ピボットを表す置換行列の場合、PA = LU となります。L は下三角行列、U は上三角行列です。アルゴリズムは、データのキャッシュ再利用を向上させるためブロック化されています。Intel® Optimized MP LINPACK Benchmark に最も近いシーケンシャルなアルゴリズムは、LAPACK の DGETRF または ScaLAPACK の PDGETRF です。これらは *GETRF という総称で呼ばれます。*GETRF は L を保持しますが、Intel® Optimized MP LINPACK Benchmark では、その必要はありません。次の手順を実行して、*GETRF で連立方程式 Ax = b を解くことができます。

1. PA = LU を計算します。

2. y について Ly=Pb を解きます。

3. x について Ux = y を解きます。

問題を解く過程で b が上記の y で置換される場合、左の L は破棄できます。これにより (あまり重要ではない) 最後の順方向の算出を省略できます。つまり、列が拡張された方程式 [A|b] の LU 分解を行う限り、right-looking アルゴリズムでピボットを行う際に左辺のピボットを省略できます。

*GETRF は、いくつかの BLAS 呼び出しを行います。N を問題サイズ、NB をブロック化で使用される列ブロックのサイズと仮定すると、N が NB より十分に大きい場合、ほとんどの浮動小数点演算 (FLOP) は *GEMM で行うことができます。一部の FLOP は *TRSM でも行われます。ほかの BLAS 呼び出しも必要となる場合がありますが、これらの関数はパフォーマンス・クリティカルです。*GETRF は、3 カ所 (*GEMM、*TRSM、およびローカルの LU 分解) で計算を行います。

*GEMM は、C を

α * op(A) * op(B) + β* C で上書きします。

α と β はともにスカラーで、A、B、C は行列です。op(A) は A または A の転置を表します。op(B) も同様です。op(A) は m x k 行列、op(B) は k x n 行列、C は m x n 行列です。

N をグローバルな問題サイズと仮定し、行列はブロックサイズ NB の P x Q プロセッサー・グリッドに循環的にマッピングされる 2 次元 (2D) ブロックに分配されており、最初のいくつかの *GEMM 呼び出しで m、n、k の初期値は m ≈ N/P、n ≈ N/Q、k = NB であると仮定します。

各ブロックの反復において *GEMM で実行される FLOP の数は、約 2*N*N*NB/(P*Q) で始まります。対象ノードが以前のブロック行やブロック列を所有しているかどうかに応じて、各 *GEMM のサイズは小さくなることがあります。

*TRSM は、NB x NB の三角連立方程式を解きます。通常、N/Q ソリューション・ベクトルを計算します。計算には、約 NB*NB*(N/Q) FLOP が含まれます。N >> P*NB である限り、*TRSM よりも *GEMM のほうが計算量は多くなります。

さらに、各反復は、サイズ N/P x NB で始まるローカルの LU 分解を行います。列全体の行ピボットを行う必要がありますが、計算量は NBxNB 行列を分解するのと同じ (約 2*NB*NB*NB/3 FLOP) です。N >> P*NB の場合、計算に含まれる FLOP の数は *TRSM よりも少なくなります。

HPL では行ピボットが必要です。行ピボットには、FLOP はかかりませんが、時間がかかります。HPL のランダム行列ジェネレーターを、より少ないピボットで済む行列 (例えば、対角優位行列) に置換することはできません。

また、各ノードで行のピボットを行うのに必要になるため、2 次元の PxQ グリッドの周りのデータも取得する必要があります。PxQ グリッドの各ノードは、ペア (i, j) として表現できます (0≤i<P、0≤j<Q)。

このアルゴリズムには、グリッド全体にわたる横方向ブロードキャストと縦方向ブロードキャストが含まれています。

横方向ブロードキャスト (上記の *GEMM のピボット情報と A 行列を含む) は通常、Q ノードに沿ったリング・ブロードキャストです。例えば、ノード (2,3) は、ブロック行 (2, j) のほかのすべてのノードにデータをブロードキャストしなければなりません。ツリー・ブロードキャストではなく、リング・ブロードキャストを使用する理由は、グリッドの縦方向の移動はほかの操作とオーバーラップできるためです。ブロードキャストには時間がかかりますが、入力パラメーターによっては一部を隠すことができます。

縦方向ブロードキャスト (上記の *GEMM の B 行列を含む) は通常、プロセッサー列を同期しなければならないため、P ノードに沿ったツリー・ブロードキャストです。多くの HPL 設定では P≤ 2Q が選択されます。

HPL におけるブロードキャストの詳細は、www.netlib.org/benchmark/hpl/algorithm.html#bcast (英語) を参照してください。

その他のコミュニケーションとして、ピボットが挙げられます。

通常、*GEMM または *TRSM の一部がオフロードされます。これは、FLOP のデータに対する比率が最も高く、PCIe バスを介してデータを移動する必要があるためです。

DGEMM をオフロードする最も簡単な方法は、A と B の一部をコプロセッサーに送り、インテル® Xeon Phi™ コプロセッサーのネイティブ DGEMM 呼び出しで C (β はゼロと仮定) を返すことです。

NB は、インテル® Xeon® プロセッサー単独で必要なサイズよりも大きくなければなりません。NB が 400 では、オフロードによる速度向上は得られません。NB を 960 よりも大きな値にすると、大幅な速度向上が得られます。

ただし、NB を大きな値にするには、ホスト・プロセッサーとコプロセッサーで追加のメモリーが必要になります。メモリーが小さい場合、問題サイズ N は N >> NB を満たしません。その場合、Intel® Optimized MP LINPACK Benchmark のオフロードバージョンは使用しないほうが良いでしょう。