（脱線）quadsort、SIMD化できるかな妄想(8個x8組を40clockで？）

#quadsortのsimd sortを妄想してみた。

quadsortの考え方をベースにSIMDで書けるかな？を考えてみるとこんな感じになる。

| step | 0 |   | 1 |   | 2 |   | 3 |   | 4 |   | 5 |    | 6 |  | 7 |   |
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
| 1-1 | val0 | <= | val1 | <= | val2 | <= | val3 |    |      |    |      |    |      |    |      |
| 1-2 |      |    |      |    |      |    |      |    | val4 | <= | val5 | <= | val6 | <= | val7 |
| 2-1 | val0 | <= | val1 |    |      |    |      | <= | val4 | <= | val5 |(<= | val6 | <= | val7)|
| 2-2 |(val0 | <= | val1 | <=)| val2 | <= | val3 |    |      |    |      | <= | val6 | <= | val7 |
| 3   |(val0 | <= | val1 | <=)| val2 | <= | val3 | <= | val4 | <= | val5 |(<= | val6 | <= | val7)|


各stepは、max() 4 instruction ＋min() 4instruction。
つまり、8 instruction ✕ 5step = 40 instructionあればソートできる。

下記の例は、AVX2 対応で、32bit整数を8個ずつ8組ソートする実装。
つまり、64要素をを8個ずつソート済み状態から、マージソートができる。
うん、これは悪くない気がしてきている。

という思考実験でした。

## 2020/02/22 追記
ああ、だめだ

> val{}={101,100,103,102,4,2,1,3} の場合、
step1-1 : val{}={100,101,102,103,4,2,1,3}
step1-2 : val{}={100,101,102,103,1,2,3,4} 

まではいいんだが

>step2-1 : val{}={1,2,102,103,100,101,3,4}  // ここで、val5 <= val6 でなくなっている

うーん……

## もう一回考える

```
val{}={101,100,103,102,4,2,1,3} 

SWAP4( val0, val1, val2, val3);
SWAP4( val4, val5, val6, val7);

val{}={100,101,102,103,1,2,3,4} 

SWAP4( val0, val1, val4, val5);
SWAP4( val2, val3, val6, val7);

val{}={1,2,3,4,100,101,102,103} 

ってなるから大丈夫か……

```


```c
u32_t *val;

_m256i val0,val1,val2,val3;
_m256i val4,val5,val6,val7;
_m256i tmp0,tmp1,tmp2,tmp3;

// load from memory
val0 = _mm256_load_si256( (void*)val + 32 * 0) ;
val1 = _mm256_load_si256( (void*)val + 32 * 1) ;
val2 = _mm256_load_si256( (void*)val + 32 * 2) ;
val3 = _mm256_load_si256( (void*)val + 32 * 3) ;
val4 = _mm256_load_si256( (void*)val + 32 * 4) ;
val5 = _mm256_load_si256( (void*)val + 32 * 5) ;
val6 = _mm256_load_si256( (void*)val + 32 * 6) ;
val7 = _mm256_load_si256( (void*)val + 32 * 7) ;

// Step 1
// val0 <= val1 <= val2 <= val3
tmp0 = _mm256_min_epi32 ( val0, val1 ); tmp1 = _mm256_max_epi32 ( val0, val1 );
tmp2 = _mm256_min_epi32 ( val2, val3 ); tmp3 = _mm256_max_epi32 ( val2, val3 );
val0 = _mm256_min_epi32 ( tmp0, tmp2 ); val1 = _mm256_max_epi32 ( tmp0, tmp2 );
val2 = _mm256_min_epi32 ( tmp1, tmp3 ); val3 = _mm256_max_epi32 ( tmp1, tmp3 );

// val4 <= val5 <= val6 <= val7
tmp0 = _mm256_min_epi32 ( val4, val5 ); tmp1 = _mm256_max_epi32 ( val4, val5 );
tmp2 = _mm256_min_epi32 ( val6, val7 ); tmp3 = _mm256_max_epi32 ( val6, val7 );
val4 = _mm256_min_epi32 ( tmp0, tmp2 ); val5 = _mm256_max_epi32 ( tmp0, tmp2 );
val6 = _mm256_min_epi32 ( tmp1, tmp3 ); val7 = _mm256_max_epi32 ( tmp1, tmp3 );

// Step 2
// val0 <= val1 <= val4 <= val5　(4 <= val6 <= val 7)
tmp0 = _mm256_min_epi32 ( val0, val4 ); tmp1 = _mm256_max_epi32 ( val0, val4 );
tmp2 = _mm256_min_epi32 ( val1, val5 ); tmp3 = _mm256_max_epi32 ( val1, val5 );
val0 = _mm256_min_epi32 ( tmp0, tmp2 ); val1 = _mm256_max_epi32 ( tmp0, tmp2 );
val4 = _mm256_min_epi32 ( tmp1, tmp3 ); val5 = _mm256_max_epi32 ( tmp1, tmp3 );

// (val0 <= val1 <= ) val2 <= val3 <= val6 <= val7
tmp0 = _mm256_min_epi32 ( val2, val6 ); tmp1 = _mm256_max_epi32 ( val2, val6 );
tmp2 = _mm256_min_epi32 ( val3, val7 ); tmp3 = _mm256_max_epi32 ( val3, val7 );
val2 = _mm256_min_epi32 ( tmp0, tmp2 ); val3 = _mm256_max_epi32 ( tmp0, tmp2 );
val6 = _mm256_min_epi32 ( tmp1, tmp3 ); val7 = _mm256_max_epi32 ( tmp1, tmp3 );

// Step 3
// (val0 <= val1 <= ) val2 <= val3 <= val4 <= val5 ( <= val6 <= val 7)
tmp0 = _mm256_min_epi32 ( val2, val4 ); tmp1 = _mm256_max_epi32 ( val2, val4 );
tmp2 = _mm256_min_epi32 ( val3, val5 ); tmp3 = _mm256_max_epi32 ( val3, val5 );
val2 = _mm256_min_epi32 ( tmp0, tmp2 ); val3 = _mm256_max_epi32 ( tmp0, tmp2 );
val4 = _mm256_min_epi32 ( tmp1, tmp3 ); val5 = _mm256_max_epi32 ( tmp1, tmp3 );

// store to memory
_mm256_load_si256( (void*)val + 32 * 0, val0 ) ;
_mm256_load_si256( (void*)val + 32 * 1, val1 ) ;
_mm256_load_si256( (void*)val + 32 * 2, val2 ) ;
_mm256_load_si256( (void*)val + 32 * 3, val3 ) ;
_mm256_load_si256( (void*)val + 32 * 4, val4 ) ;
_mm256_load_si256( (void*)val + 32 * 5, val5 ) ;
_mm256_load_si256( (void*)val + 32 * 6, val6 ) ;
_mm256_load_si256( (void*)val + 32 * 7, val7 ) ;
```