AVX/AVX2による整数のShuffleとPermute

# はじめに
整数値の__m256iに対するShuffleとPermuteについて説明します．

##  _mm256_shuffle_epi32 (AVX2)
```cpp
__m256i _mm256_shuffle_epi32 (__m256i a, const int imm8)
asm: vpshufd ymm, ymm, imm8
```
**動作**  
_mm256_shuffle_epi32
![permutepsall.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/7575472c-7fbb-2003-0cbf-a8157d9625b8.png)

**CPI, Uops**  

| Architecture | Latency | Throughput |Uops|
|--------------|:-------:|:----------:|:--:|
| Alderlake    |    1    |    0.5     |  - |
| Icelake      |    1    |    0.5     |  1 |
| Skylake      |    1    |     1      |  1 |
| Broadwell    |    1    |     1      |  1 |
| Haswell      |    1    |     1      |  1 |
| Zen3         |    1    |    0.5     |  1 |
| Zen2         |    1    |    0.5     |  1 |
| Zen          |    1    |     1      |  2 |

* Zen2，Zen3のメモリからのshuffleはUopsが1です．他は2になります．

**説明**  
floatとは異なり，**1つ**のレジスタの値を，128ビットの壁を超えずにintの整数を並べ替えます．
floatの場合のpermute_psと同じ挙動をするため，immによる指定によってXMMとYMMの並びは同じになります．
同様に`_MM_SHUFFLE`での指定が便利です．

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

```cpp
void test_shuffle_epi32()
{
	__m256i a, d;
	a = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
	print_m256i_int(a);
	printf("\n");
	d = _mm256_shuffle_epi32(a, _MM_SHUFFLE(3, 2, 1, 0));
	print_m256i_int(d);
	d = _mm256_shuffle_epi32(a, _MM_SHUFFLE(0, 1, 2, 3));
	print_m256i_int(d);
	d = _mm256_shuffle_epi32(a, _MM_SHUFFLE(0, 0, 0, 0));
	print_m256i_int(d);
	d = _mm256_shuffle_epi32(a, _MM_SHUFFLE(2, 2, 1, 1));
	print_m256i_int(d);
}
```
出力

```console
a:   0   1   2   3 |   4   5   6   7

d:   0   1   2   3 |   4   5   6   7
d:   3   2   1   0 |   7   6   5   4
d:   0   0   0   0 |   4   4   4   4
d:   1   1   2   2 |   5   5   6   6
```

##  _mm256_shufflelo_epi16 (AVX2)
```cpp
__m256i _mm256_shufflelo_epi16 (__m256i a, const int imm8)
asm: vpshuflw ymm, ymm, ymm
```
**動作**  
_mm256_shufflelo_epi16
![shuffleloepi16all.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/dfa4f3e7-2e82-e63c-5369-8cdb1bdc4d06.png)

**CPI, Uops**

| Architecture | Latency | Throughput |Uops|
|--------------|:-------:|:----------:|:--:|
| Alderlake    |    1    |    0.5     |  - |
| Icelake      |    1    |    0.5     |  1 |
| Skylake      |    1    |     1      |  1 |
| Broadwell    |    1    |     1      |  1 |
| Haswell      |    1    |     1      |  1 |
| Zen3         |    1    |    0.5     |  1 |
| Zen2         |    1    |    0.5     |  1 |
| Zen          |    1    |     1      |  2 |

* Zen2，Zen3のメモリからのshuffleはUopsが1です．他は2になります．

**説明**  
一つのレジスタのXMM，YMMそれぞれの下位64ビットだけを入れ替えます．
つまり16個ある要素のうち4＋4＝8要素だけをいれかえます．
前半と後半で並びは同じで，`_MM_SHUFFLE`での順序指定が便利です．

詳細説明は次のshufflehiと一緒に行います．

##  _mm256_shufflehi_epi16 (AVX2)
```cpp
__m256i _mm256_shufflehi_epi16 (__m256i a, const int imm8)
asm: vpshufhw ymm, ymm, ymm
```
**動作**  
_mm256_shufflehi_epi16 
![shufflehiepi16all.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/8637ff7a-7369-34c3-ff4c-f7ddee8bf9d7.png)

**CPI, Uops**

| Architecture | Latency | Throughput |Uops|
|--------------|:-------:|:----------:|:--:|
| Alderlake    |    1    |    0.5     |  - |
| Icelake      |    1    |    0.5     |  1 |
| Skylake      |    1    |     1      |  1 |
| Broadwell    |    1    |     1      |  1 |
| Haswell      |    1    |     1      |  1 |
| Zen3         |    1    |    0.5     |  1 |
| Zen2         |    1    |    0.5     |  1 |
| Zen          |    1    |     1      |  2 |

* Zen2，Zen3のメモリからのshuffleはUopsが1です．他は2になります．

**説明**  
一つのレジスタのXMM，YMMそれぞれの上位64ビットだけを入れ替えます．
つまり16個ある要素のうち4＋4＝8要素だけをいれかえます．
前半と後半で並びは同じで，`_MM_SHUFFLE`での順序指定が便利です．

つまり，全てを並び変えるには，shuffleloとshufflehiを共に発行する必要があります．
しかし，両方とも発行したとしても，64ビットの壁を超えて並び変えることができないため，shuffle_epi32と合わせて使わなければ，128ビット以内の並べ替えであっても任意に並び変えることができません．
レジスタマスクが必要なepi8用の物を使えば，任意に並び変えることは可能なため，maskをセットするコストとのトレードオフになります．

以下にhi，lo含めたサンプルコードを示します．
また，64ビットの壁を超えない16ビット用のshuffle命令のマクロも示します．

```cpp
#define _mm256_shuffle_epi16(src, imm8_lo, imm8_hi) _mm256_shufflehi_epi16(_mm256_shufflelo_epi16((src), (imm8_lo)), (imm8_hi));

void test_shuffle_epi16()
{
	__m256i a, d;
	a = _mm256_setr_epi16(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15);
	print_m256i_short(a);
	printf("\n");
	d = _mm256_shufflelo_epi16(a, _MM_SHUFFLE(3, 2, 1, 0));
	print_m256i_short(d);
	d = _mm256_shufflehi_epi16(a, _MM_SHUFFLE(3, 2, 1, 0));
	print_m256i_short(d);
	d = _mm256_shufflelo_epi16(a, _MM_SHUFFLE(0, 1, 2, 3));
	print_m256i_short(d);
	d = _mm256_shufflehi_epi16(a, _MM_SHUFFLE(0, 1, 2, 3));
	print_m256i_short(d);
	d = _mm256_shufflelo_epi16(a, _MM_SHUFFLE(0, 0, 0, 0));
	print_m256i_short(d);
	d = _mm256_shufflehi_epi16(a, _MM_SHUFFLE(0, 0, 0, 0));
	print_m256i_short(d);
	d = _mm256_shufflelo_epi16(a, _MM_SHUFFLE(2, 2, 1, 1));
	print_m256i_short(d);
	d = _mm256_shufflehi_epi16(a, _MM_SHUFFLE(2, 2, 1, 1));
	print_m256i_short(d);

	d = _mm256_shuffle_epi16(a, _MM_SHUFFLE(0, 1, 2, 3), _MM_SHUFFLE(0, 1, 2, 3));
	print_m256i_short(d); 
}
```

出力

```console
a:   0   1   2   3 ;   4   5   6   7|   8   9  10  11 ;  12  13  14  15

d:   0   1   2   3 ;   4   5   6   7|   8   9  10  11 ;  12  13  14  15
d:   0   1   2   3 ;   4   5   6   7|   8   9  10  11 ;  12  13  14  15
d:   3   2   1   0 ;   4   5   6   7|  11  10   9   8 ;  12  13  14  15
d:   0   1   2   3 ;   7   6   5   4|   8   9  10  11 ;  15  14  13  12
d:   0   0   0   0 ;   4   5   6   7|   8   8   8   8 ;  12  13  14  15
d:   0   1   2   3 ;   4   4   4   4|   8   9  10  11 ;  12  12  12  12
d:   1   1   2   2 ;   4   5   6   7|   9   9  10  10 ;  12  13  14  15
d:   0   1   2   3 ;   5   5   6   6|   8   9  10  11 ;  13  13  14  14
d:   3   2   1   0 ;   7   6   5   4|  11  10   9   8 ;  15  14  13  12
```

##  _mm256_shuffle_epi8 (AVX2)
```cpp
__m256i _mm256_shuffle_epi8 (__m256i a, __m256i mask)
asm: vpshufb ymm, ymm, ymm
```
**動作**
_mm256_shuffle_epi8
![shuffleepi8all.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/475cba9a-51dc-1dae-4aa9-535e1bc645dc.png)

**CPI, Uops**

| Architecture | Latency | Throughput |Uops|
|--------------|:-------:|:----------:|:--:|
| Alderlake    |    1    |    0.5     |  - |
| Icelake      |    1    |    0.5     |  1 |
| Skylake      |    1    |     1      |  1 |
| Broadwell    |    1    |     1      |  1 |
| Haswell      |    1    |     1      |  1 |
| Zen3         |    1    |    0.5     |  1 |
| Zen2         |    1    |    0.5     |  1 |
| Zen          |    1    |     1      |  2 |

* Zen2，Zen3のメモリからのshuffleはUopsが1です．他は2になります．

**説明**  
1つのレジスタを8ビット整数を128ビットレーン内で入れ替えます．
入れ替えはレジスタマスクによって指定します．
_mm256_set_epi8()で32個の要素を指定して入れ替え先を決定します．
要素の値は，128ビットレーン内のため0-15の値になります．

サンプルコードを以下に示します．
また，epi8の命令を使った16ビットの任意並べ替えの例も同時に示します．
32ビットも同じような方法で拡張可能ですが，同一の命令がpermuteにあるため割愛します．
また，AVX512が使えれば，16ビットも`_mm256_permutexvar_epi16()`が使用可能です．

```cpp
void test_shuffle_epi8()
{
	__m256i a, d;
	cout << "8-bit case" << endl;
	a = _mm256_set_step_epi8(0);
	print_m256i_uchar(a);
	printf("\n");

	d = _mm256_shuffle_epi8(a, _mm256_setr_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15));
	print_m256i_uchar(d);
	d = _mm256_shuffle_epi8(a, _mm256_set_epi8(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15));
	print_m256i_uchar(d);
	d = _mm256_shuffle_epi8(a, _mm256_set_epi8(2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15));
	print_m256i_uchar(d);
	d = _mm256_shuffle_epi8(a, _mm256_setr_epi8(2, 2, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15));
	print_m256i_uchar(d);

	cout << endl << "16-bit case" << endl;
	__m256i b;
	b = _mm256_set_step_epi16(0);
	print_m256i_short(b);
	printf("\n");
	d = _mm256_shuffle_epi8(b, _mm_shuffle16(0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3, 4, 5, 6, 7));
	print_m256i_short(d);
	d = _mm256_shuffle_epi8(b, _mm_shuffle16(7, 6, 5, 4, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0));
	print_m256i_short(d);
	d = _mm256_shuffle_epi8(b, _mm_shuffle16(0, 0, 0, 3, 4, 5, 6, 7, 1, 1, 1, 3, 4, 5, 6, 4));
	print_m256i_short(d);
}
```

出力

```console
8-bit case
a:   0   1   2   3;  4   5   6   7;  8   9  10  11; 12  13  14  15| 16  17  18  19; 20  21  22  23; 24  25  26  27; 28  29  30  31

d:   0   1   2   3;  4   5   6   7;  8   9  10  11; 12  13  14  15| 16  17  18  19; 20  21  22  23; 24  25  26  27; 28  29  30  31
d:  15  14  13  12; 11  10   9   8;  7   6   5   4;  3   2   1   0| 31  30  29  28; 27  26  25  24; 23  22  21  20; 19  18  17  16
d:  15  14  13  12; 11  10   9   8;  7   6   5   4;  3   2   1   0| 31  30  29  28; 27  26  25  24; 23  22  21  20; 19  18  18  18
d:   2   2   2   3;  4   5   6   7;  8   9  10  11; 12  13  14  15| 16  17  18  19; 20  21  22  23; 24  25  26  27; 28  29  30  31

16-bit case
b:   0   1   2   3;  4   5   6   7|  8   9  10  11; 12  13  14  15

d:   7   6   5   4;  3   2   1   0| 15  14  13  12; 11  10   9   8
d:   0   1   2   3;  4   5   6   7|  8   9  10  11; 12  13  14  15
d:   4   6   5   4;  3   1   1   1| 15  14  13  12; 11   8   8   8
```
## _mm256_permute4x64_epi64 (AVX2)
```cpp
__m256i _mm256_permute4x64_epi64 (__m256i a, const int imm8)
asm: vpermq ymm, ymm, imm8
```
**動作**
_mm256_permute4x64_epi64
![permute4x64all.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/4a8023f7-6a72-81a1-e911-6665fdcabc4b.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 |
| Zen3         |   6.5   |    1.25    |  2 |
| Zen2         |    6    |    1.25    |  2 |
| Zen          |    2    |     2      |  3 |

* uops Zen  L:2 T: 1
* uops Zen2 L:6 T: 1.27
* uops Zen3 L:6 T: 1.25
* Agner Zen  L2, T: 2
* Agner Zen2 L6, T: 1
* Agner Zen3 L6.5, T: 1
* AIDA64 Zen  L2，T:2
* AIDA64 Zen2  L6.1，T:1.25
* AIDA64 Zen3  L6.5，T:1.17
* ZenシリーズのUopsはメモリから読み込んでもIntel同様減りません．

**説明**
1つのレジスタの4個の要素を128ビットの壁を**超えて**任意に並べ替えます．
レイテンシは，超えないSWIZZLE命令よりも長くなっています．
挙動は_mm256_permute4x64_pdと同じで，doubleをlongにキャストした動作です．

`_MM_SHUFFLE`を使って，並べ替えます．
SSEのfloatに対するshuffle命令をAVXのdouble命令にちょうど拡張した動きをします．

## _mm256_permutevar8x32_epi32 (AVX2)
```cpp
__m256i _mm256_permutevar8x32_epi32 (__m256i a, __m256i idx)
asm: vpermd ymm, ymm, ymm
```
**動作**  
_mm256_permutevar8x32_epi32
![permutevar8x32all.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/67908/373aa98b-d552-1350-4106-160594d36942.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 |
| Zen3         |    8    |     1      |  2 |
| Zen2         |    8    |     2      |  2 |
| Zen          |    5    |     4      |  3 |

* UopsによるとZenシリーズの特定のパターンはL: 3
* AIDA64のZen2，Zen3はL8.5，Zen3のTは1を切り0.86．
* ZenシリーズのUopsはメモリから読み込んでもIntel同様減りません．

**説明**  
1つのレジスタの8個の要素を128ビットの壁を**超えて**任意に並べ替えます．
レイテンシは，超えないSWIZZLE命令よりも長くなっています．
挙動は_mm256_permute8x32_psと同じで，floatをintにキャストした動作です．