一次元配列に含まれる最小値か最大値を見つけるプログラムを紹介します。以降に処理の概要図を示します。
64ビット整数型
呼び出し側・符号付
以降に、呼び出し側のC++コードを示します。common.hをincludeしていますがSIMDで記述したアセンブリ言語の関数と等価な機能を持つC++言語で記述した共通関数のヘッダです。最下部にソースコードを示します。条件は関数名に含まれます。
#include "..\common.h" // TEMPLATES #define T long long extern "C" { T aminsq(const T*, const size_t); T amaxsq(const T*, const size_t); } // main int main(void) { const size_t ArrLen = 4096; static_assert(ArrLen % 16 == 0, "number of elements must be an integral multiple of 16."); T a[ArrLen]; init(a, ArrLen); T cmin = cMin (a, ArrLen); T amin = aminsq(a, ArrLen); T cmax = cMax (a, ArrLen); T amax = amaxsq(a, ArrLen); cout << fixed << setprecision(2); cout << "cpp min = " << cmin << endl; cout << "asm min = " << amin << endl; cout << "cpp max = " << cmax << endl; cout << "asm max = " << amax << endl; return 0; }
一次元配列にランダムな値を与え、先ほどの関数を呼び出し、配列内の最小値や最大値を表示します。
呼び出され側
64ビット整数型一次元配列に含まれる要素の、最小値や最大値を探します。見つけ以降に、マクロを使って開発したアセンブラーのコードを示します。最小値や最大値、そして符号ごとに関数を記述するのは面倒なのでマクロを使って記述します。本関数へ渡されるレジスターとデータの関係を以降の表に示します。
レジスタ | 内容 |
---|---|
rcx | 入力配列の先頭アドレス |
rdx | 配列の要素数 |
mymacro macro MNAME, MINST public MNAME align 16 MNAME proc vpbroadcastq zmm0, qword ptr [rcx] ; zmm0 = initial value xor rax, rax ; clear index loop_f: MINST zmm0, zmm0, zmmword ptr [rcx+rax*8] add rax, 8 cmp rax, rdx jb short loop_f vextracti64x4 ymm1, zmm0, 1 ; reduce zmm0 MINST ymm1, ymm0, ymm1 vextracti64x2 xmm0, ymm1, 1 MINST xmm2, xmm0, xmm1 vpsrldq xmm0, xmm2, 8 MINST xmm1, xmm0, xmm2 vmovq rax, xmm1 ret MNAME endp endm ;------------------------------------------------------------------- ; code _TEXT segment mymacro aminsq, vpminsq mymacro aminuq, vpminuq mymacro amaxsq, vpmaxsq mymacro amaxuq, vpmaxuq _TEXT ends end
mymacro マクロを定義し、これを使ってaminsq、aminuq、amaxsq、amaxuq関数を作ります。各関数の機能を表で示します。
関数名 | 機能 |
---|---|
aminsq | 一次元符号付64ビット整数配列から最小値を取り出す。 |
aminuq | 一次元符号なし64ビット整数配列から最小値を取り出す。 |
amaxsq | 一次元符号付64ビット整数配列から最大値を取り出す。 |
amaxuq | 一次元符号なし64ビット整数配列から最大値を取り出す。 |
関数の内容を先頭から説明します。vpbroadcastq命令で、zmm0に配列の先頭の値をブロードキャストします。これは、最小値や最大値を探すための初期値です。次にraxレジスターをクリアします。このraxレジスターは配列を参照するインデックスを保持します。次に、マクロの引数MINST を指定します。これは、vpminsq命令、vpminuq命令、vpmaxsq命令、そしてvpmaxuq命令のいずれかに置き換えられます。MINSTの第三引数は配列のアドレスを示します。配列のインデックスを保持するraxレジスターへ8を乗じ、それを先頭アドレスを保持しているrcxレジスターへ加算することによってアドレスを求めます。
これにより8要素単位の小さな値か大きな値がzmm0レジスターへ格納されます。これを全要素が終わるまで繰り返します。全要素の完了検査は、lengthが格納されているrdxレジスターと配列のインデックスを保持するraxレジスターを比較して判断します。全配列の処理が完了するとzmm0レジスターへ8要素単位の最小値か最大値が格納されます。
zmm0レジスターの8要素をreduceし、最小値あるいは最大値を求めることにより、配列全体の最小値か最大値が求まります。言葉で説明すると分かりづらいため、zmm0レジスターに格納された8要素単位の最小値から、全体の最小値を求める方法を図で示します。
ここでは詳細な説明は行いませんが、図を参照し処理の流れを追ってください。なお、32ビット整数をreduceする方法を詳しく後述します。
vpbroadcastq命令で、zmm1に下限値、zmm2に上限値をブロードキャストします。次に、r8レジスターへ要素数を設定します。基本的なループの構造は、これまでのプログラムと同様です。vmovdqu64 命令で、符号付、あるいは符号なし64ビット整数型配列から8個の要素を読み込みます。そして、vpmaxsq命令あるいはvpmaxuq命令で下限値へ飽和させます。次に、その結果を使って、vpminsq命令あるいはvpminuq命令で上限値へ飽和させます。これによって入力の値を、下限値と上限値の範囲へ飽和させ、vmovdqu64 命令で8個の要素を書き込みます。
一回の処理で8要素を処理するため、raxレジスターに8を加算し要素数に達するまで上記処理を繰り返します。なお、先に示したvpmaxsq命令あるいはvpmaxuq命令は、マクロの引数MMAXINST で置き換えられ、vpminsq命令あるいはvpminuq命令はMMININST で置き換えられます。
common.h、共通関数
ヘッダーファイルの一部を示します。簡単な内容なので、説明は省きします。
: // min template <typename T> T cMin(const T* a, const size_t length) { T r = a[0]; for (size_t i = 0; i < length; i++) { if (r > a[i]) { r = a[i]; } } return r; } // max template <typename T> T cMax(const T* a, const size_t length) { T r = a[0]; for (size_t i = 0; i < length; i++) { if (r < a[i]) { r = a[i]; } } return r; } :
すべての型に対応させるため、テンプレート関数とします。cMin関数は一次元配列から最小値を探し、cMax 関数は最大値を探します。
このプログラムのビルドと実行の例を示します。
実行結果(signed)
C:\>ml64 /c minmaxAsm.asm
…
C:\>cl /O2 /EHsc minmaxQ.cpp minmaxAsm.obj
…
C:\>minmaxQ
cpp min = -16383
asm min = -16383
cpp max = 16382
asm max = 16382
reduceのまとめ
zmmレジスターに格納されている64ビット整数をreduceする方法は簡単に示しました。ここで、32ビット整数、16ビット整数、8ビット整数、64ビット浮動小数点、そして32ビット浮動小数点について詳しく説明します。特に、32ビット整数のreduceについて詳しく説明します。
32ビット整数をreduce
以降に、32ビット整数をreduceするコードと、それを図で示します。まず、マクロで記述したコードを示します。
vextracti32x8 ymm1, zmm0, 1 ; reduce zmm0 MINST ymm1, ymm0, ymm1 vextracti128 xmm0, ymm1, 1 MINST xmm2, xmm0, xmm1 vpsrldq xmm0, xmm2, 8 MINST xmm1, xmm0, xmm2 vpsrldq xmm0, xmm1, 4 MINST xmm1, xmm0, xmm1 vmovd eax, xmm1
zmm0レジスターに格納されている16個の符号付32ビット整数から、最小値を取り出します。示したコードのMINST はマクロ展開時に実際の命令へ置き換えられます。データ型が符号付32ビット整数で最小値を探す場合は、vpminsd命令へ置き換えられます。そのように置き換えられたソースコードを示します。
vextracti32x8 ymm1, zmm0, 1 ; reduce zmm0 vpminsd ymm1, ymm0, ymm1 vextracti128 xmm0, ymm1, 1 vpminsd xmm2, xmm0, xmm1 vpsrldq xmm0, xmm2, 8 vpminsd xmm1, xmm0, xmm2 vpsrldq xmm0, xmm1, 4 vpminsd xmm1, xmm0, xmm1 vmovd eax, xmm1
これから、上記のコードを順次説明します。基本的にレジスターを半分に畳みながら、順次結果を得る方法を採用します。
まず、zmmレジスターに格納されている16個の要素を8個の要素にreduceしymmレジスターへreduceします。
zmm0レジスターに格納されている上位8要素をymm1レジスターへ抽出します。下位8要素はzmm0レジスターの下位であるymm0レジスターへ残されます。この二つのレジスターをvpminsd命令へ与え、ymm1レジスターへ集約します。ここでは、最小値を抽出しますが、最大値を抽出したければvpmaxsd命令へ置き換え、さらには符号なし32ビット整数を処理したければ、vpminud命令やvpmaxud命令へ置き換えます。
16要素を8要素にreduceできましたので、今度は8要素を4要素にreduceします。
ymm1レジスターに格納されている上位4要素をxmm0レジスターへ抽出します。下位4要素はymm1レジスターの下位であるxmm1レジスターへ残されます。この二つのレジスターをvpminsd命令へ与え、xmm2レジスターへ集約します。
8要素を4要素にreduceできましたので、今度は4要素を2要素にreduceします。
xmm2レジスターに格納されている上位2要素をxmm0レジスターの下位へ移動します。下位2要素はxmm2レジスターの下位へ残されます。この二つのレジスターをvpminsd命令へ与え、xmm1レジスターの下位2要素へ集約します。処理自体はxmmレジスターの4要素を対象としますが、上位の2要素は意味を持ちません。
4要素を2要素にreduceできましたので、今度は2要素を1要素にreduceします。
xmm1レジスターに格納されている下位2要素の上位要素をxmm0レジスターの最下位へ移動します。下位1要素はxmm1レジスターの最下位へ残されます。この二つのレジスターをvpminsd命令へ与え、xmm1レジスターの最下位要素へ結果を求めます。
本関数の戻り値は32ビット整数ですので、最後にxmmレジスターの最下位要素をeaxレジスターへ移動します。
16ビット整数をreduce
以降に、16ビット整数をreduceするコードを示します。
vextracti32x8 ymm1, zmm0, 1 ; reduce zmm0 MINST ymm1, ymm0, ymm1 vextracti128 xmm0, ymm1, 1 MINST xmm2, xmm0, xmm1 vpsrldq xmm0, xmm2, 8 MINST xmm1, xmm0, xmm2 vpsrldq xmm0, xmm1, 4 MINST xmm0, xmm0, xmm1 vpsrldq xmm1, xmm0, 2 MINST xmm0, xmm1, xmm0 vmovd eax, xmm0 ; vmovw ax, xmm0
reduceの段数を、[32ビット整数をreduce]へ一段追加します。処理の図は示しませんが、[32ビット整数をreduce]から想像できるでしょう。示したコードのMINST はマクロ展開時に実際の命令へ置き換えられます。データ型が符号付16ビット整数で最小値を探す場合は、vpminsw命令へ置き換えられます。最小値ではなく最大値を抽出したければ、vpmaxsw命令へ置き換えます。さらに、符号なし16ビット整数を処理したければ、vpminuw命令やvpmaxuw命令へ置き換えます。
8ビット整数をreduce
以降に、8ビット整数をreduceするコードを示します。
vextracti32x8 ymm1, zmm0, 1 ; reduce zmm0 MINST ymm1, ymm0, ymm1 vextracti128 xmm0, ymm1, 1 MINST xmm2, xmm0, xmm1 vpsrldq xmm0, xmm2, 8 MINST xmm1, xmm0, xmm2 vpsrldq xmm0, xmm1, 4 MINST xmm0, xmm0, xmm1 vpsrldq xmm1, xmm0, 2 MINST xmm0, xmm1, xmm0 vpsrldq xmm1, xmm0, 1 MINST xmm0, xmm1, xmm0 vmovd eax, xmm0 ; vmovb al, xmm0
reduceの段数を、[32ビット整数をreduce]へ二段追加します。処理の図は示しませんが、[32ビット整数をreduce]から想像できるでしょう。示したコードのMINST はマクロ展開時に実際の命令へ置き換えられます。データ型が符号付8ビット整数で最小値を探す場合は、vpminsb命令へ置き換えられます。最小値ではなく最大値を抽出したければvpmaxsb命令へ置き換えます。さらに、符号なし8ビット整数を処理したければ、vpminub命令やvpmaxub命令へ置き換えます。
64ビット浮動小数点をreduce
以降に、64ビット浮動小数点をreduceするコードを示します。
vextractf64x4 ymm1, zmm0, 1 ; reduce zmm0 MINST ymm1, ymm0, ymm1 vextractf64x2 xmm0, ymm1, 1 MINST xmm2, xmm0, xmm1 vpsrldq xmm0, xmm2, 8 MINST xmm0, xmm0, xmm2
最初に説明した[x.x 64ビット整数型配列]のreduceとほとんど同じです。扱うデータが64ビット整数から、64ビット浮動小数点へ変わりますが、畳み込む要素数は同じです。データ型が異なるため、型に合った命令に変更するだけで、使用する命令もほとんど同じです。MINST はマクロ展開時に、vminpd命令かvmaxpd命令へ置き換えられます。
32ビット浮動小数点をreduce
以降に、32ビット浮動小数点をreduceするコードを示します。
vextractf32x8 ymm1, zmm0, 1 ; reduce zmm0 MINST ymm1, ymm0, ymm1 vextractf128 xmm0, ymm1, 1 MINST xmm2, xmm0, xmm1 vpsrldq xmm0, xmm2, 8 MINST xmm1, xmm0, xmm2 vpsrldq xmm0, xmm1, 4 MINST xmm0, xmm0, xmm1
[32ビット整数をreduce]とほとんど同じです。扱うデータが32ビット整数から、32ビット浮動小数点へ変わりますが、畳み込む要素数は同じです。データ型が異なるため、型に合った命令に変更するだけで、使用する命令もほとんど同じです。MINST はマクロ展開時に、vminps命令かvmaxps命令へ置き換えられます。