一次元配列の各要素を検査し、条件を満足していたら、その要素を抽出します。当時に抽出した要素の位置を得ます。ここでは任意の値以上の要素を抽出、任意の値以下の要素を抽出、任意範囲の要素を抽出するとともに、そのインデックスを得る例を示します。前の関数は要素だけを抽出しましたが、本関数は要素に加え、その要素の位置（インデックス値）を抽出します。以降に処理概要を図で示します。
符号付64ビット整数型
呼び出し側・符号付
以降に、呼び出し側のC++コードを示します。一次元配列から条件を満足する要素と、そのインデックスを要素を抽出します。
common.hをincludeしていますがSIMDで記述したアセンブリ言語の関数と等価な機能を持つC++言語で記述した共通関数のヘッダです。最下部にソースコードを示します。条件は関数名に含まれます。
#include "..\common.h" // TEMPLATES #define T long long extern "C" { int extWidxQLow (const T*, T*, int*, const T, size_t ); int extWidxQHigh(const T*, T*, int*, const T, size_t ); int extWidxQ (const T*, T*, int*, const T, size_t , const T); } 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], c[ArrLen], v[ArrLen]; int cIdx[ArrLen], vIdx[ArrLen]; const T low = -50, high = 50; cout << endl << "[ v < " << low << "]" << endl; init(a, ArrLen); int cLen = cextractLow(a, c, cIdx, low, ArrLen); int aLen = extWidxQLow(a, v, vIdx, low, ArrLen); verify(cLen, aLen, cIdx, vIdx, c, v, ArrLen); cout << endl << "[ v > " << high << "]" << endl; cLen = cextractHigh(a, c, cIdx, high, ArrLen); aLen = extWidxQHigh(a, v, vIdx, high, ArrLen); verify(cLen, aLen, cIdx, vIdx, c, v, ArrLen); cout << endl << "[ " << low << " < v < " << high << "]" << endl; cLen = cextract(a, c, cIdx, low, ArrLen, high); aLen = extWidxQ(a, v, vIdx, low, ArrLen, high); verify(cLen, aLen, cIdx, vIdx, c, v, ArrLen); return 0; }
簡単な処理ですので説明は省きます。
呼び出され側
本関数へ渡される内容とレジスターの対応を表で示します。
| レジスタ | 内容 |
|---|---|
| rcx | 入力配列 a の先頭アドレス |
| rdx | 出力配列 c の先頭アドレス |
| r8 | インデックスを格納する配列 vIdx の先頭アドレス |
| r9 | 任意の値、あるいは下限値（範囲指定の時） |
| [rsp+40] | 入力配列 a の要素数 |
| [rsp+48] | オプション、上限値（範囲指定の時） |
引数が可変なため少し面倒です。この関数は、一次元配列の1)任意の値以上、あるいは2)任意の値以下の要素を抽出するものと、3)任意の範囲の要素と、そのインデックス値を抽出します。任意の値以上、あるいは任意の値以下の要素を抽出する場合、任意の値は一つだけ必要です。しかし、任意の範囲の要素を抽出するには、二つの値が必要です。このため、上表を各パターンに分けると以下のようになります。
任意の値以上の要素を抽出、任意の値以下の要素を抽出
| rcx | 入力配列 a の先頭アドレス |
|---|---|
| rdx | 出力配列 c の先頭アドレス |
| r8 | インデックスを格納する配列 vIdx の先頭アドレス |
| r9 | 任意値 |
| [rsp+40] | 入力配列 a の要素数 |
任意範囲の要素を抽出
| rcx | 入力配列 a の先頭アドレス |
|---|---|
| rdx | 出力配列 v の先頭アドレス |
| r8 | インデックスを格納する配列 vIdx の先頭アドレス |
| r9 | 下限値 |
| [rsp+40] | 入力配列 a の要素数 |
| [rsp+48] | 上限値 |
4ビット整数型配列の要素を比較し、条件に合う値を取り出すライブラリを、マクロを使って開発したものを示します。本関数は、符号なし/符号付の両方に対応します。かつ、任意の値以上、任意の値以下、そして任意範囲の要素を抽出する6つの関数へ展開されます。
: _MM_CMPINT_LT EQU 1 ; - より小さい < _MM_CMPINT_GT EQU 6 ; - より大きい > : mymacro macro MNAME, CINST, CONDITION, CONDITION2 public MNAME align 16 MNAME proc vpbroadcastq zmm1, r9 ; zmm1 = low/high mov r11, qword ptr [rsp+40] ; length IFDEF CONDITION2 vpbroadcastq zmm2, qword ptr [rsp+48]; zmm2 = high ENDIF vmovdqu32 ymm3, ymmword ptr index ; ymm3 = index mov r9, 8 vpbroadcastd ymm4, r9 ; ymm4 = 8,...,8 xor r9, r9 ; init retrurn value = 0 xor rax, rax ; clear in index loop_f: vmovdqu64 zmm0, zmmword ptr [rcx+rax*8]; load a[] CINST k1, zmm0, zmm1, CONDITION IFDEF CONDITION2 CINST k2, zmm0, zmm2, CONDITION2 kandb k1, k2, k1 ENDIF vpcompressq zmmword ptr [rdx+r9*8]{k1}, zmm0 ; store zmm0 to &v[r9] vpcompressd ymmword ptr [r8 +r9*4]{k1}, ymm3 ; store ymm3 to &vIdx[r9] vpaddd ymm3, ymm3, ymm4 ; update index kmovb r10, k1 ; move mask bit popcnt r10, r10 add r9, r10 ; update retrurn value add rax, 8 cmp rax, r11 jb short loop_f mov eax, r9d ; return value ret MNAME endp endm ;------------------------------------------------------------------- ;.code _TEXT segment ;QWORD mymacro extWidxQLow, vpcmpq, _MM_CMPINT_LT ; < mymacro extWidxQHigh, vpcmpq, _MM_CMPINT_GT ; > mymacro extWidxQ, vpcmpq, _MM_CMPINT_GT, _MM_CMPINT_LT ; <> ;QWORD Unsigned mymacro extWidxUQLow, vpcmpuq, _MM_CMPINT_LT ; < mymacro extWidxUQHigh, vpcmpuq, _MM_CMPINT_GT ; > mymacro extWidxUQ, vpcmpuq, _MM_CMPINT_GT, _MM_CMPINT_LT ; <> _TEXT ends ;.data __DATA segment ;.data index dd 0, 1, 2, 3, 4, 5, 6, 7 __DATA ends end
mymacro マクロを定義し、これを使ってextWidxQLow、extWidxQHigh、extWidxQ、extWidxUQLow、extWidxUQHigh、extWidxUQ関数を作ります。各関数の機能を表で示します。
| 関数名 | 機能 |
|---|---|
| extWidxQLow | 一次元符号付64ビット整数配列から、任意の値以下の要素と、そのインデックス値を抽出する。 |
| extWidxQHigh | 一次元符号付64ビット整数配列から、任意の値以上の要素と、そのインデックス値を抽出する。 |
| extWidxQ | 一次元符号付64ビット整数配列から、任意範囲の要素と、そのインデックス値を抽出する。 |
| extWidxUQLow | 一次元符号なし64ビット整数配列から、任意の値以下の要素と、そのインデックス値を抽出する。 |
| extWidxUQHigh | 一次元符号なし64ビット整数配列から、任意の値以上の要素と、そのインデックス値を抽出する。 |
| extWidxUQ | 一次元符号なし64ビット整数配列から、任意範囲の要素と、そのインデックス値を抽出する。 |
分かり易くするため、extWidxQLowが展開されたソースリストを示します。
public extWidxQLow align 16 extWidxQLow proc vpbroadcastq zmm1, r9 ; zmm1 = low/high mov r11, qword ptr [rsp+40] ; length vmovdqu32 ymm3, ymmword ptr index ; ymm3 = index mov r9, 8 vpbroadcastd ymm4, r9 ; ymm4 = 8,...,8 xor r9, r9 ; init retrurn value = 0 xor rax, rax ; clear in index loop_f: vmovdqu64 zmm0, zmmword ptr [rcx+rax*8]; load a[] vpcmpq k1, zmm0, zmm1, _MM_CMPINT_LT vpcompressq zmmword ptr [rdx+r9*8]{k1}, zmm0 ; store zmm0 to &v[r9] vpcompressd ymmword ptr [r8 +r9*4]{k1}, ymm3 ; store ymm3 to &vIdx[r9] vpaddd ymm3, ymm3, ymm4 ; update index kmovb r10, k1 ; move mask bit popcnt r10, r10 add r9, r10 ; update retrurn value add rax, 8 cmp rax, r11 jb short loop_f mov eax, r9d ; return value ret extWidxQLow endp
まず、vpbroadcastq命令でr9 レジスターの値をzmm1レジスターへブロードキャストし初期化します。r9 レジスターは下限値が格納されています。これによって、zmm1レジスターの8要素がr9 レジスターで埋められます。次にr11 へ入力配列の要素数を読み込みます。
vmovdqu32命令でymm3レジスターへインデックスの初期値を設定します。vpbroadcastd命令で、ymm4レジスターへymm3レジスターが保持するインデックスの増分値を設定します。本例では、64ビット整数を対象とするため一回で8要素を処理します。これから、インデックスの増分値は8 です。使用しているレジスターから分かるように、値はzmmレジスターで8要素を、インデックスはymmレジスターで8要素を処理します。これはインデックス値をint型で管理するためです。
次にr9 レジスターとrax レジスターをxor命令でゼロクリアします。r9 レジスターは抽出した要素の数を、raxレジスターは一次元配列を参照するためのインデックスを保持します。
前準備が完了したためループへ入ります。zmm0レジスターへ配列の処理対象要素を読み込みます。これを下限値が格納されているzmm1レジスターと比較します。vpcmpq命令で条件に合致する要素のビットがオンになるマスクをk1マスクレジスターへ得ます。このマスクレジスターを使って要素と、そのインデックス値を抽出します。ただ、要素の抽出はvpcompressq命令、インデックス値の抽出はvpcompressd命令を使用します。これは、それぞれのデータ型が異なるためです。
抽出した要素がいくつになるか不明です。そこでk1レジスターをr10レジスターへ移動し、popcnt命令でオンになっているビット数を数えます。この値は抽出した要素数を示します。この値をr9へ加算し、出力配列用のインデックスを管理します。
次に、一次元配列のインデックスを保持するraxレジスターへ8を加算し、これを配列の要素数を保持するr11レジスターと比較し、すべての要素を処理したか調べます。処理が終わっていなければ、次の要素の処理へ移ります。全要素の処理が完了したら、r9に格納されている抽出した要素数を、eaxレジスターへ移動し処理を終了します。eaxレジスターは関数の戻り値であるint型の値です。
一部の処理は
arques.hatenablog.com
と同様な部分もありますので、それの説明も参考にすると良いでしょう。
common.h、共通関数
ヘッダーファイルの一部を示します。簡単な内容なので、説明は省きします。
: // C++ template <typename T> int cextractLow(const T* a, T* v, int* vIdx, const T cmpValue, const size_t length) { int rIndex = 0; for (size_t i = 0; i < length; i++) { if (a[i] < cmpValue) { v[rIndex] = a[i]; vIdx[rIndex] = i; rIndex++; } } return rIndex; } // C++ template <typename T> int cextractHigh(const T* a, T* v, int* vIdx, const T cmpValue, const size_t length) { int rIndex = 0; for (size_t i = 0; i < length; i++) { if (a[i] > cmpValue) { v[rIndex] = a[i]; vIdx[rIndex] = i; rIndex++; } } return rIndex; } // C++ template <typename T> int cextract(const T* a, T* v, int* vIdx, const T cmpLow, const size_t length, const T cmpHigh) { int rIndex = 0; for (size_t i = 0; i < length; i++) { if (a[i] > cmpLow && a[i] < cmpHigh) { v[rIndex] = a[i]; vIdx[rIndex] = i; rIndex++; } } return rIndex; } :
すべての型に対応させるため、テンプレート関数とします。cextractLow関数は、一次元配列から任意の値以上の要素とインデックス値を抽出します。cextractHigh関数は、一次元配列から任意の値以下の要素とインデックス値を抽出します。cextract関数は、一次元配列から任意の範囲の要素とインデックス値を抽出します。
このプログラムのビルドし、実行した様子を示します。
実行結果
[ v < -50]
asm Length = 2016
cpp Length = 2016
[ v > 50]
asm Length = 2064
cpp Length = 2064
[ -50 < v < 50]
asm Length = 16
cpp Length = 16
C++で処理した結果と、アセンブリ言語で開発したプログラムが同じ結果です。正常に処理されたようです。
念のため、任意範囲の要素とそのインデックス値を抽出するextWidxQ へ展開された関数のソースリストを示します。
public extWidxQ align 16 extWidxQ proc vpbroadcastq zmm1, r9 ; zmm1 = low/high mov r11, qword ptr [rsp+40] ; length vpbroadcastq zmm2, qword ptr [rsp+48]; zmm2 = high vmovdqu32 ymm3, ymmword ptr index ; ymm3 = index mov r9, 8 vpbroadcastd ymm4, r9 ; ymm4 = 8,...,8 xor r9, r9 ; init retrurn value = 0 xor rax, rax ; clear in index loop_f: vmovdqu64 zmm0, zmmword ptr [rcx+rax*8]; load a[] vpcmpq k1, zmm0, zmm1, _MM_CMPINT_GT vpcmpq k2, zmm0, zmm2, _MM_CMPINT_LT kandb k1, k2, k1 vpcompressq zmmword ptr [rdx+r9*8]{k1}, zmm0 ; store zmm0 to &v[r9] vpcompressd ymmword ptr [r8 +r9*4]{k1}, ymm3 ; store ymm3 to &vIdx[r9] vpaddd ymm3, ymm3, ymm4 ; update index kmovb r10, k1 ; move mask bit popcnt r10, r10 add r9, r10 ; update retrurn value add rax, 8 cmp rax, r11 jb short loop_f mov eax, r9d ; return value ret extWidxQ endp
zmm1レジスターの値と配列の8要素をvpcmpq命令で2回比較し、k1とk2マスクレジスターに結果を求めます。kandb命令で、両方を満足する条件をk1マスクレジスターへ得ます。以降は、先ほどと同様です。
