AVX/AVX2によるShuffleとPermute一覧とpermute2f128命令

# はじめに
いったんロードした連続したデータを並べ替えるためのSWIZZLE命令について説明します．
shuffleとpermuteは，レジスタの各要素を並べ替える命令です．
一部の命令は2つのレジスタ要素を混ぜるブレンド命令も兼ねています．

## 一覧表
shuffleとpermuteには18個の命令の種類があり，用途に応じて使い分けます．
以下の表にそれぞれの特徴を示します．

|ASM       |return |intrinsic                  |bld|imm|128|unit|index help       |
|----------|:-----:|---------------------------|:-:|:-:|:-:|:--:|-----------------|
|vperm2f128|__m256 |_mm256_permute2f128_ps     | x |   | x |128 |0x00～0x33       |
|vshufps   |__m256 |_mm256_shuffle_ps          | x |   |   | 32 |_MMSHUFFLE       |
|vpermilps |__m256 |_mm256_permute_ps          |   |   |   | 32 |_MMSHUFFLE       |
|vpermilps |__m256 |_mm256_permutevar_ps       |   | x |   | 32 |_mm256_set_epi32 |
|vpermps   |__m256 |_mm256_permutevar8x32_ps   |   | x | x | 32 |_mm256_set_epi32 |
|vperm2f128|__m256d|_mm256_permute2f128_pd     | x |   | x |128 |0x00～0x33       |
|vshufpd   |__m256d|_mm256_shuffle_pd          | x |   |   | 64 |0bxxxx           |
|vpermilpd |__m256d|_mm256_permute_pd          |   |   |   | 64 |0bxxxx           |　
|vpermilpd |__m256d|_mm256_permutevar_pd       |   | x |   | 64 |_mm256_set_epi64x|
|vpermpd   |__m256d|_mm256_permute4x64_pd      |   |   | x | 64 |_MMSHUFFLE       |
|vperm2f128|__m256i|_mm256_permute2f128_si256  | x |   | x |128 |0x00～0x33       |
|vperm2i128|__m256i|_mm256_permute2x128_si256  | x |   | x |128 |0x00～0x33       |
|vpermq    |__m256i|_mm256_permute4x64_epi64   |   |   | x | 64 |_MMSHUFFLE       |
|vpermd    |__m256i|_mm256_permutevar8x32_epi32|   | x | x | 32 |_mm256_set_epi32 |
|vpshufd   |__m256i|_mm256_shuffle_epi32       |   |   |   | 32 |_MMSHUFFLE       |
|vpshufhw  |__m256i|_mm256_shufflehi_epi16     |   |   |   | 16 |_MMSHUFFLE       |
|vpshuflw  |__m256i|_mm256_shufflelo_epi16     |   |   |   | 16 |_MMSHUFFLE       |
|vpshufb   |__m256i|_mm256_shuffle_epi8        |   | x |   |  8 |_mm256_set_epi8  |

* ASM:			アセンブラ命令
* return: 		戻り値（処理する型）
* intrinsic:	intrinsic名
* bld: 			2変数を取り，値をブレンドするか否か
* imm: 			移動の指定が即値か非即値か
* 128: 			データの移動が128ビットの壁を超えられるか否か
* unit: 		処理ビットの単位
* index help: 	並び順を指定するときに使うと便利な記述方法

並び替え命令は，一つのレジスタの要素を並び替えるだけではなく，二つのレジスタを合成する用途でも使われます．
shuffle命令は代表的な並び替えとブレンドを行う命令です．
基本的には，permute命令は1つのレジスタの入れ替え，shuffleが入れ替えとブレンドの兼用ですが例外もあります．
例えば，128ビット単位のpermuteは2つのレジスタのブレンド命令を兼ねており，整数のshuffleは1つのレジスタの入れ替えになります．
なお，ブレンドにはブレンド専用のblend命令もあります．

並べ替えの移動パターンは，最後の引数で決定され，imm8（immediateの略）とついているものは，即値であり，すなわちコンパイル時に移動方法が決定している必要があります．
varがつくpermutevar関数と，epi8に対するshuffleだけが非即値つまり実行時に並べ替えを決めることができます．

AVXでは256ビットの情報を扱え，XMMレジスタとYMMレジスタに128ビットづつ情報を保持しています．
XMMとYMMのレジスタには壁があり，その要素を超えて移動しようとする命令は，超えない命令よりも概ねパフォーマンスが低くなっています．
そのため，超えなくて良い場合と超えなければいけない場合に備えてそれぞれ命令が用意されています．

shuffle/permuteは，演算ではなくビットの移動命令であるため，型をキャストしてしまえば，入力がどの型であっても同様に扱えます．
例えばfloatのデータを２要素単位で動かしたい場合は，_mm256_permute_pd命令を使っても動作指定が可能です．
移動パターンによっては，いくつかの命令で実現可能であり，最善の組み合わせがあります．
例えば64ビット単位の移動命令で，整数の128ビットを超えない命令は有りません．
また，整数のshuffle命令はブレンド命令を兼ねません．
これらは，浮動小数点の命令に置き換えると高速化する場合があります．

これらの命令を移動要素数と型によってまとめたのが下記の一覧表です．
先頭につく記号の意味は下記となっています．

* M: レジスタを引数に取るため，実行時にパラメータ変更が可能です．それ以外は即値を取るため，コンパイル時に動作が決まります．
* Y: YMMレジスタつまり128ビットの壁を超えて並べ替えが可能です．
* H: 16ビットのシャッフル限定の特徴で，64ビットの壁の中でしか並べ替えができません．

Zenシリーズは，多くの命令でメモリから読み込む場合にロード命令分のUopsが1つ減ります．

|    |                                mm256                                |                              mm256d                             |                    mm256i                    |
|:--:|:-------------------------------------------------------------------:|:---------------------------------------------------------------:|:--------------------------------------------:|
|  2 |                          Y permute2f128_ps                          |                        Y permute2f128_pd                        | Y permute2f128_si256<br>Y permute2x128_si256 |
|  4 |                                  x                                  | permute_pd<br>shuffle_pd<br>M permutevar_pd<br>Y permute4x64_pd |              Y permute4x64_epi64             |
|  8 | permute_ps<br>shuffle_ps<br>M permutevar_ps<br>MY permutevar8x32_ps |                                x                                |   shuffle_epi32<br>MY permutevar8x32_epi32   |
| 16 |                                  x                                  |                                x                                |    H shufflehi_epi16<br>H shufflelo_epi16    |
| 32 |                                  x                                  |                                x                                |                M shuffle_epi8                |

## _mm256_permute2f128_ps|pd|si256 (AVX)
```cpp
__m256 _mm256_permute2f128_ps (__m256 a, __m256 b, int imm8)
__m256d _mm256_permute2f128_pd (__m256d a, __m256d b, int imm8)
__m256i _mm256_permute2f128_si256 (__m256i a, __m256i b, int imm8)
asm: vperm2f128 ymm, ymm, ymm, imm8  //ps
asm: vperm2f128 ymm, ymm, ymm, imm8  //pd
asm: vperm2f128 ymm, ymm, ymm, imm8  //si256

__m256i _mm256_permute2x128_si256 (__m256i a, __m256i b, int imm8)
asm: vperm2i128 ymm, ymm, ymm, imm8
```

**動作**
![permute2128all.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/647375cb-afcb-0804-4b37-4530d34bfce1.png)

**CPI/Uops**

| Architecture | Latency | Throughput |Uops|
|--------------|:-------:|:----------:|:--:|
| Alderlake    |    3    |     1      |  - |
| Icelake      |    3    |     1      |  1 |
| Skylake      |    3    |     1      |  1 |
| Broadwell    |    3    |     1      |  1 |
| Haswell      |    3    |     1      |  1 |
| Ivy Bridge   |    2    |     1      |  1 |
| Sandy Bridge |    2    |     1      |  1 |
| Zen3         |   3.5   |     1      |  1 |
| Zen2         |    3    |     1      |  1 |
| Zen          |    3    |     3      |  8 |

* uops Zen(L:4 T:3), Zen3(L:3, T:1)
* AIDA64 Zen2(L3.1, T:1.08), Zen3 (L3.3, T:1.0)
* Anger Zen3(L3.5, T:0.5)
* Zen2，Zen3でメモリから読み込む場合はUopsが1，Zenでメモリから読み込む場合はUopsが12です．
* Intel CPUでメモリから読み込む場合はUopsは2で，マイクロフュージョンはされません．

**説明**  
128ビットの壁を**超えて**，2つのレジスタの前半・後半128ビットの単位(XMM，YMMレジスタの単位)で値を入れ替えます．
レイテンシは，128ビットの壁を超えないSWIZZLE命令よりも長くなっています．

アセンブラ命令は，浮動小数点のps，pdとsi256で共通しています．
AVX2で整数専用のvperm2i128が追加されていますが，ポフォーマンスは同じです．
これは，最適化時に整数は整数として命令を出していたほうが都合がいいことが多いために用意されたものです．

imm8[0:3]に0～3の値，imm8[4:7]に0～3の値を入れることで出力dにaとbのXMM，YMMのどれを入れるか指定できます．  

```
0: a[127:0] a-XMM  
1: a[255:128] a-YMM  
2: b[127:0] b-XMM  
3: b[255:128] b-YMM  
```
16進数表記で記述すると，ちょうど4ビット単位で入力できるため書きやすいです．
imm8は=0x00～0x33でそれぞれ制御可能で，0:a前半，1: a後半,2: b前半，3: b後半​を表します．
例えば，0x00でa前半コピー​，0x01：a前半後半スワップ​，0x10：aをそのまま​出力，0x32：bをそのまま​出力となります．

様々な指定ができますが，基本的には，前半後半を入れ替えるために使います．
主に使う命令は，下記です．
* 0x01: aの前半後半入れ替え
* 0x03: b後半，a前半
* 0x21: a後半，b前半

入れ替えない場合は，0x10，0x32は何も処理をしないため必要なく，0x00のa前半のブロードキャストはinsert命令で実現可能であり，0x20のaとbの前半後半ごとに混ぜる命令はblend命令で実現したほうが速く動きます．

いくつかの例を示します．

0x01：a前半後半入れ替え
![permute212801.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/18862e1d-43f6-9ae3-4b82-71ef5e77ccb8.png)
0x03: a前半，b後半  
![permute212803.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/decbc83c-6647-e101-40e4-0f88f74d75bf.png)
0x21: b前半，a後半
![permute212821.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/771a472d-9257-2525-cc86-562a7a3d2b57.png)
0x10：aのコピー
![permute212810.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/afe6c6a3-bf0c-b762-3885-4900ea9cf8ef.png)
0x00：a前半ブロードキャスト
![permute212800.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/f17c568c-ab73-d2fd-1a5a-bb87fec9f990.png)
0x20：a前半，b後半
![permute212820.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/12bf6f24-9e2a-b687-d30b-7276336c9634.png)

サンプルコードを下記に示します．

```cpp
void test_permute2f128_ps()
{
	__m256 a, b, d;
	a = _mm256_setr_ps(0, 1, 2, 3, 4, 5, 6, 7);
	b = _mm256_setr_ps(10, 11, 12, 13, 14, 15, 16, 17);
	print_m256(a);
	print_m256(b);
	printf("\n");
	d = _mm256_permute2f128_ps(a, b, 0x00);
	print_m256(d);
	d = _mm256_permute2f128_ps(a, b, 0x01);
	print_m256(d);
	d = _mm256_permute2f128_ps(a, b, 0x10);
	print_m256(d);
	d = _mm256_permute2f128_ps(a, b, 0x32);
	print_m256(d);
	d = _mm256_permute2f128_ps(a, b, 0x30);
	print_m256(d);
}
```

出力

```console
a:   0.00   1.00   2.00   3.00 |   4.00   5.00   6.00   7.00
b:  10.00  11.00  12.00  13.00 |  14.00  15.00  16.00  17.00

d:   0.00   1.00   2.00   3.00 |   0.00   1.00   2.00   3.00
d:   4.00   5.00   6.00   7.00 |   0.00   1.00   2.00   3.00
d:   0.00   1.00   2.00   3.00 |   4.00   5.00   6.00   7.00
d:  10.00  11.00  12.00  13.00 |  14.00  15.00  16.00  17.00
d:   0.00   1.00   2.00   3.00 |  14.00  15.00  16.00  17.00
```