この記事は、The Parallel Universe Magazine 48 号に掲載されている「The MAXLOC Reduction in oneAPI」の日本語参考訳です。原文は更新される可能性があります。原文と翻訳文の内容が異なる場合は原文を優先してください。
maxloc 操作とは
最大値の場所 (maxloc) を見つけることは、配列で実行される一般的な検索操作です。多くのプログラミング言語とライブラリーが、組込みの maxloc 関数を提供しています (NumPy* argmax (英語)、Fortran maxloc (英語)、BLAS amax (英語)、C++ max_element (英語) 関数など)。最近の記事、「インテル® AVX-512 命令を使用した Maxloc 操作の最適化」 (The Parallel Universe 46 号) では、maxloc 検索をベクトル化してパフォーマンスを向上する方法を説明しました。相互相関を含む、多くのアルゴリズムで重要な操作であることは明白です (図 1)。
図 1. (2 進数の配列として表された) 2 つの離散信号の重なりが最大になる変位を見つける。
ここで、α は sig1 に対してシフトされる sig2 の要素の数。
相関を計算するとき、2 番目の信号は循環シフトされることに注意。
以前の記事、「oneAPI によるフーリエ相関アルゴリズムの実装」 (The Parallel Universe 44 号) では、SYCL* とインテル® oneMKL 関数の組み合わせを使用して 2 つの信号の 1 次元相互相関を計算する方法を紹介しましたが、最後の maxloc ステップは省略されていました (図 2)。ステップ 1 から 3 はアクセラレーター・デバイスにオフロードされていましたが、ステップ 4 はホスト CPU で計算されていました。つまり、最終的な相関配列をホストに転送する必要があることを意味します。理想的には、信号がデバイスのメモリーにロードされた後に、すべての計算がデバイスで実行されるべきです。ホストで必要なのは、最終的な変位 (1 次元相関の 1 つのスカラー) のみです。その他のホストとデバイス間のデータ転送は不要であり、パフォーマンスの低下につながります。そのため、この記事の主題である、デバイス上で maxloc を実行するさまざまな方法を実験しました。
図 2. maxloc リダクションはフーリエ相関アルゴリズムの最後のステップ。
DFT は離散フーリエ変換、IDFT は逆 DFT、CONJG は複素共役、MAXLOC は最大相関スコアの場所。
SYCL* のリダクション演算子
リダクションは、複数の値を 1 つの値に減らす一般的な並列パターンです。例えば、総和リダクションは、配列内の値を加算して 1 つの総和を得ます。配列内の最小値や最大値、それらの値の場所を見つけることも、リダクション操作です。SYCL* は、並列カーネルで使用できる組込みのリダクション演算子を提供しています (図 3)。
図 3. SYCL* の総和リダクションの例。
SYCL* のリダクション・クラスを使用して maxloc のようなほかの演算子を実装することもできます (図 4)。このコードは、『Data Parallel C++: Mastering DPC++ for Programming of Heterogeneous Systems Using C++ and SYCL (データ並列 C++: C++ と SYCL* を使用したヘテロジニアス・システムのプログラミングで DPC++ を使いこなす)』 (英語) の第 14 章「Common Reduction Patterns (一般的なリダクション・パターン)」 (英語) (334～339 ページ) の minloc の例から引用したものです。SYCL* キューは非同期であるため、wait 文を使用して続行する前に計算が完了することを保証しています。
製品とパフォーマンス情報
1実際の性能は利用法、構成、その他の要因によって異なります。詳細については、www.Intel.com/PerformanceIndex (英語) を参照してください。
