# 2017q1 Homework3 (software-pipelining)
contributed by < `king1224` >
###### tags: `king1224`
## 開發環境
```
OS: 16.04.1 Ubuntu
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數： 2
每通訊端核心數： 2
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 60
Model name: Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz
製程： 3
CPU MHz： 2913.305
CPU max MHz: 3400.0000
CPU min MHz: 800.0000
BogoMIPS: 5587.41
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
## [論文](http://www.cc.gatech.edu/~hyesoon/lee_taco12.pdf)閱讀
> * streams 的概念好抽象，似懂非懂
> * 文中的 13 項 benchmark，benchmark 只知道是測效能的東西，但那 13 項具體是什麼不太懂，是執行環境、編譯器、特定功能還是不同的測試程式
>
> [name=洪正皇][color=#da90e5]
對於現在講求效率的時代，cache miss 所帶來的 latency 影響越來越大，而 prefetching 是一個降低 cache miss 很好的方法，可從 software 與 hardware 兩個層面下手，但對於 prefetching 我們都還有很多的不瞭解。
### instruction
本文將探討 software 與 hardware 間的 prefetching 之間有如何影響，希望能讓 SW 與 HW prefetching 有更好的合作，這邊先展示一下實驗結果：
* 左 y 軸為執行時間
* 右 y 軸為 speedup 值
* x 軸為SPEC CPU 2006 benchmark
* 本數據為基於 Base 標準化後得到的結果
* Base : 沒有使用 HW prefetcher 也沒有手動插入 intrinsics
* GHB : compiler + a GHB hardware prefetcher，Global History Buffer
* STR : compiler + a stream-based hardware prefetcher
* SW : compiler + 手動在程式中插入 intrinsics
* Base 中 compiler 會自動插入一些 software prefetch instructions，但看不到多大的效益，因為 compiler 插入的非常保守
* 有趣的是可以看到，在 SW + HW 的相互影響下，某些情況中還可以看到效能是不升反降，本研究的目標將探索此相互關係
#### 結論
* SW prefetcher 對於短陣列、不規則的存取時，可以更有效地降低 L1 cache miss，和 Intel 的指南書中說的一樣
* SW prefetch 會影響到 HW prefetcher 的 training，特別是 SW prefetch 只用在 stream 的一部份時
> 還沒閱讀到後面
> 這邊不太清楚為什麼
> [name=洪正皇][color=#9ff4a3]
* 本實驗只會針對現有機制，而模擬與真實系統都會被使用，以模擬完成較複雜的實驗，再對其中的發現以真實系統做驗證
### SW & HW prefetching 的背景知識
不同的資料結構，就會適合不同的 SW 與 HW prefetching 策略，表格中的 _Hardware pref._ 及 _Software pref._ 即為推薦的策略
陣列和 Recursive Data Structures ( RDS ) 都是比較容易預測的，可以被 SW perfetch，然而像 hashing 這種較複雜的資料結構就難預測多了
* streams : 逐行 access cache-line
* strided : 隔兩行以上 access cache-line
#### Software Prefetch Intrinsics
* 這邊使用 x86 SSE SIMD 擴充，e.g. `_mm prefetch(char *ptr, int hint)`
* ptr : prefetch address
> 是要 prefetch 的資料的 address 嗎?
> 我們怎麼知道資料的 address
> [name=洪正皇][color=#da90e5]
* 其中的 hint
> 這個是用來告知哪些 cache 需要加入 intrinsic 的意思嗎
> 不太懂為什麼最後一個只有 L1 是打圈，但 Remarks 還是寫 all level caches
> [name=洪正皇][color=#da90e5]
#### Prefetch Classification
Prefetch 的情況可以分成六種種類，如下表
> Early 會有什麼不好嗎
> [name=洪正皇][color=#da90e5]
> 
> 看到了，會被新的 prefetch 資料驅逐出去
> [name=洪正皇]
#### Software Prefetch Distance
Prefetch 的距離是指要抓取多久之後會用到的資料，當要使用一筆會 cache miss 的資料時候，原本應該有很大的 latency，而即時完成的 prefetch 則可以省下這段 lantency 的時間，因此最佳的距離可以給足夠的時間來完成 prefetch，而完成時又剛好需要使用這筆 prefetch 的資料。
#### Direct and Indirect Memory Indexing
對於 memory index 的存取方式可以分成兩種：
* direct : 較好預測，因為通常都是有規律的連續存取或跳格存取 ( regular stream/stride behavior )
* indirect : 需要一些特別應對的 prefetch 方式，而此使用 SW prefetcher 可以較簡單的預測，但仍然比 direct 有更多的 overhead
### SW prefetching 所帶來的正面及負面影響
#### SW 比 HW prefetching 更好的益處
* Large Number of Streams (Limited Hardware Resources)
* 在一些 benchmarks 中，streams 的數量超過 HW 的容量，尤其是科學計算時帶來多重 streams 的負載
* 例：當資料是三維的時候
* Short Streams
* HW 需要一些經驗與時間來 training 預測的目的地及距離，至少需要經歷兩次 cache miss，太短的 stream 無法完成 training 或 training 完之後就結束了
* 例：當陣列為 3 X 3、每筆資料為 16 bytes，則總共 144 bytes，也就是只有 3 個 cache blocks，即使 cache miss 完兩次之後也沒什麼機會可以發揮作用了。
* Irregular Memory Access
* 對於較複雜的資料結構，SW 比 HW prefetcher 較有效果
> SW prefetch 是人工輸入要 prefetch 哪個位置對吧?
> 因此可以知道該 prefetch 哪裡
> [name=洪正皇][color=#da90e5]
* Cache Locality Hint
* SW prefetcher 可以自行選擇要將資料放在 higher level cache ( L1 ) 或 lower level cache ( L2、L3 )，而 HW 則通常會將資料放在 lower level cache，因此 SW prefetcher 使用得當將可以減少 L1 cache miss
* 將資料從 L2 搬至 L1 也會造成效能降低，因此也不能隨便將所有資料放到 L1
* Loop Bounds
* SW prefetch 可以透過一些方式來防止 prefetch 超過迴圈執行次數的資料
* 例如：loop unrolling, software pipelining, and using branch instructions 等技巧
* HW prefetch 則會照先前 training 的規律持續 prefetch 下去，但不知道迴圈何時會結束
> Several methods prevent generating prefetch requests out of array bounds
> 文中有一句是寫 array bounds，如果 prefetch 到 array bounds 以外的資料會 Segmentation fault 嗎
> 而超過迴圈次數的 prefetch，不一定會超過 array bounds 吧，在讀這邊的時候我有點混亂了
> [name=洪正皇][color=#da90e5]
#### SW prefetching 的缺點
* Increased Instruction Count
* SW prefetch 插入的程式碼，轉成 assembly code 時會多出一些 instructions，影響指令處理的 bandwidth
* Static Insertion
* SW prefetch 的指令的所有參數都是靜態的，無法隨著程式執行時的不同情況因應出不同的 distance 或目標
* 例如：多樣化的 latency、有效的 cache size 和 bandwidth
* HW prefetcher 則可以不斷的 training，更新合適的距離和目標
* Code Structure Change
* 如果迴圈中的計算量太少，導致這次 prefetch 指令還沒執行完的時候，又要執行下一條 prefetch 指令了，這時候就必須改變迴圈中的程式碼結構才可以達到效果
* 在某些情況中，加入的 prefetch 指令增加太多的 instructions，將會增加插入 SW prefetch 的困難度
#### SW + HW 的協同作用
* Handling Multiple Streams
* SW 和 HW 可以分工合作，照比較利益原則分別處理較合適的 streams，也達到同時處理更多 streams 的效果
* Positive Training
* SW prefetch 的經驗可以用來協助 HW training
#### SW + HW 的拮抗作用
* Negative Training
* 如果 SW 隱藏了一些 streams，那 HW 可能不會被正確的訓練
* SW 也可能導致 HW 過度訓練，過大的工作量導致效能反降
* Harmful Software Prefetching
* HW prefetch 的精準度原本就比 SW 還低，因此當 SW prefetch 失敗時，會給 HW 帶來更多效能上的影響
### 研究方法
## 原始版本
### 程式碼
* naive
單純的操作 `dst[i][j] = src[j][i]`
```clike=
void naive_transpose(int *src, int *dst, int w, int h)
{
for (int x = 0; x < w; x++)
for (int y = 0; y < h; y++)
*(dst + x * h + y) = *(src + y * w + x);
}
```
* sse
一次將 16 筆整數分別存進四個 128 bits 的 SSE 暫存器，並利用 unpackhi、unpacklo 來做到資料 swap 的效果，照直排處理的順序依序存進橫排
>[kobeyu大大的共筆](https://hackmd.io/s/BycRx2EC#)對於 unpackhi、unpacklo 有圖片說明
>我稍後對於 256 bits 的 AVX 版本再提供範例說明
>[name=洪正皇][color=#da90e5]
```clike=
void sse_transpose(int *src, int *dst, int w, int h)
{
for (int x = 0; x < w; x += 4) {
for (int y = 0; y < h; y += 4) {
__m128i I0 = _mm_loadu_si128((__m128i *)(src + (y + 0) * w + x));
__m128i I1 = _mm_loadu_si128((__m128i *)(src + (y + 1) * w + x));
__m128i I2 = _mm_loadu_si128((__m128i *)(src + (y + 2) * w + x));
__m128i I3 = _mm_loadu_si128((__m128i *)(src + (y + 3) * w + x));
__m128i T0 = _mm_unpacklo_epi32(I0, I1);
__m128i T1 = _mm_unpacklo_epi32(I2, I3);
__m128i T2 = _mm_unpackhi_epi32(I0, I1);
__m128i T3 = _mm_unpackhi_epi32(I2, I3);
I0 = _mm_unpacklo_epi64(T0, T1);
I1 = _mm_unpackhi_epi64(T0, T1);
I2 = _mm_unpacklo_epi64(T2, T3);
I3 = _mm_unpackhi_epi64(T2, T3);
_mm_storeu_si128((__m128i *)(dst + ((x + 0) * h) + y), I0);
_mm_storeu_si128((__m128i *)(dst + ((x + 1) * h) + y), I1);
_mm_storeu_si128((__m128i *)(dst + ((x + 2) * h) + y), I2);
_mm_storeu_si128((__m128i *)(dst + ((x + 3) * h) + y), I3);
}
}
}
```
* sse_prefetch
sse 版本加上 SW prefetcher，來增進效能
```clike=
void sse_prefetch_transpose(int *src, int *dst, int w, int h)
{
for (int x = 0; x < w; x += 4) {
for (int y = 0; y < h; y += 4) {
#define PFDIST 8
_mm_prefetch(src+(y + PFDIST + 0) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + PFDIST + 1) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + PFDIST + 2) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + PFDIST + 3) *w + x, _MM_HINT_T1);
__m128i I0 = _mm_loadu_si128 ((__m128i *)(src + (y + 0) * w + x));
__m128i I1 = _mm_loadu_si128 ((__m128i *)(src + (y + 1) * w + x));
__m128i I2 = _mm_loadu_si128 ((__m128i *)(src + (y + 2) * w + x));
__m128i I3 = _mm_loadu_si128 ((__m128i *)(src + (y + 3) * w + x));
__m128i T0 = _mm_unpacklo_epi32(I0, I1);
__m128i T1 = _mm_unpacklo_epi32(I2, I3);
__m128i T2 = _mm_unpackhi_epi32(I0, I1);
__m128i T3 = _mm_unpackhi_epi32(I2, I3);
I0 = _mm_unpacklo_epi64(T0, T1);
I1 = _mm_unpackhi_epi64(T0, T1);
I2 = _mm_unpacklo_epi64(T2, T3);
I3 = _mm_unpackhi_epi64(T2, T3);
_mm_storeu_si128((__m128i *)(dst + ((x + 0) * h) + y), I0);
_mm_storeu_si128((__m128i *)(dst + ((x + 1) * h) + y), I1);
_mm_storeu_si128((__m128i *)(dst + ((x + 2) * h) + y), I2);
_mm_storeu_si128((__m128i *)(dst + ((x + 3) * h) + y), I3);
}
}
}
```
### 效能圖
各種版本之間的執行時間比較
很明顯，以最直覺的方式執行矩陣轉置還有很大的進步空間
> 此時是關閉編譯器最佳化的情況下
> 如果使用編譯器最高等級的最佳化，他會自動幫我偵測並實現 SIMD 的改進方法嗎？
> [name=洪正皇][color=#da90e5]
將編譯時的參數 `-O0` 改為 `-Ofast` 後
恩... naive 已經沒救了！這邊很有趣的是，雖然不是很明顯，但 prefetch 版本卻比一般版本還要慢一點點，我想起論文中提過他的實驗不只單純是 SW、HW 還有編譯器的影響，我想在此的 SW prefetcher 不僅沒有提昇效能，還和編譯器產生了拮抗作用。
### perf 驗證 cache-miss
* naive
```
Performance counter stats for './naive_transpose':
17,485,773 cache-misses # 96.432 % of all cache refs
18,132,813 cache-references
1,448,989,391 instructions # 1.03 insn per cycle
1,405,095,405 cycles
0.425317842 seconds time elapsed
```
* sse
```
Performance counter stats for './sse_transpose':
4,780,438 cache-misses # 86.179 % of all cache refs
5,547,080 cache-references
1,236,891,448 instructions # 1.37 insn per cycle
903,504,713 cycles
0.279021276 seconds time elapsed
```
* sse_prefetch
```
Performance counter stats for './sse_prefetch_transpose':
4,740,400 cache-misses # 85.092 % of all cache refs
5,570,941 cache-references
1,284,190,779 instructions # 1.70 insn per cycle
754,114,180 cycles
0.228125595 seconds time elapsed
```
prefetch 雖然可以增進效能，但不會影響太多 cache-miss
>我猜測是因為 prefetch 只是將 cache-miss 的時間點提早，讓要使用資料時可以在 cache 內找到，但 prefetch 時就已經 cache-miss 了
>這邊很不確定，請各路大大指正
>[name=洪正皇][color=#da90e5]
#### 其他小問題
>要執行 perf 時會出現下列訊息，意思是權限不足，參考 [perf 原理和實務](https://hackmd.io/s/B11109rdg#)可以將權限打開，但重開機之後權限又回到了預設值，不知道有沒有一勞永逸的方法？
>[name=洪正皇][color=#da90e5]
```
perf stat -e cache-misses,cache-references,instructions,cycles ./naive_transpose
Error:
You may not have permission to collect stats.
Consider tweaking /proc/sys/kernel/perf_event_paranoid,
which controls use of the performance events system by
unprivileged users (without CAP_SYS_ADMIN).
The current value is 3:
-1: Allow use of (almost) all events by all users
>= 0: Disallow raw tracepoint access by users without CAP_IOC_LOCK
>= 1: Disallow CPU event access by users without CAP_SYS_ADMIN
>= 2: Disallow kernel profiling by users without CAP_SYS_ADMIN
Makefile:37: recipe for target 'cache-test' failed
make: *** [cache-test] Error 255
```
## AVX 版本
### 主要用到函式
* _mm256_loadu_si256 / _mm256_storeu_si256
* 將資料從矩陣中讀入 / 讀出 AVX 暫存器，一次將 8 個整數讀入一個暫存器
* 需要傳入參數為讀取 / 讀出 的起始位置
* _mm256_unpacklo_epi32 / _mm256_unpackhi_epi32
* 以 32 bits 為單位，交互存取放入目標 AVX 暫存器
* 需要傳入兩個 AVX 暫存器，各被取一半的資料
* _mm256_unpacklo_epi64 / _mm256_unpackhi_epi64
* 以 64 bits 為單位，交互存取放入目標 AVX 暫存器
* 需要傳入兩個 AVX 暫存器，各被取一半的資料
* _mm256_unpacklo_epi128 / _mm256_unpackhi_epi128 (以 _mm256_permute2x128_si256 實作)
* 以 128 bits 為單位，交互存取放入目標 AVX 暫存器
* 需要傳入兩個 AVX 暫存器，各被取一半的資料
##### 更多資料
[_mm256_unpacklo_epi8/16/32/64 Intel's reference](https://software.intel.com/en-us/node/524002)：此頁面還可以找到其他所有 SSE、AVX 指令
[_mm256_permute2x128_si256 Intel's reference](https://software.intel.com/en-us/node/524015)：用來實作 _mm256_unpacklo_epi128
[_mm256_unpacklo_epi128 與 _mm256_unpackhi_epi128 實作範例](https://github.com/regehr/nibble-sort/blob/master/arseny1.c)
### 程式碼
#### 作法與原理
參照 sse 版本的 code，因為一次處理 8 個整數，故一次將 8x8 的矩陣轉置，每一行資料都要變成每一列的資料，因此原本存在第一列的資料，要分散存到每一行的開頭，一列至少需做 3 次的資料交換( 因為 $2^3=8$ )，以純度來舉例，現在 row1 ~ row7 都是純正的，即裡面都是自己當初的資料，當兩兩經過一次交換之後，每列的純度都是 50%，只有一半是自己當初的資料，另外一半已經分給別列了，再經過兩次的交換，純度已經掉到 12.5%，每列都只有一個自己當初的資料，故原先各列的資料已經均勻分配出去了 => 每一列的資料變成每一行了，故交換 n 次可均勻分配 $2^n$ 筆資料
要達到交換的目的，需要用到 unpack 指令，並需要以不同大小的區塊當作單位來交換，否則就會換過去又換回來，例如：
`1 2 3 4 5 6 7 8`
`A B C D E F G H`
將上述兩列的奇數、偶數欄位分別取出可得
`1 A 3 C 5 E 7 G`
`2 B 4 D 6 F 8 H`
若再以相同方法，照奇數、偶數欄位取出，則又得到
`1 2 3 4 5 6 7 8`
`A B C D E F G H`
因此 unpack 的取出區愧大小，需依序為 32, 64, 128
但 AVX 的指令集中，並沒有 unpack 128 這個指令，但可以 _mm256_permute2x128_si256() 來實作
* unpack
* 只能將兩個輸入的資料的前 128 bits 或後 128 bits 取出
* 不可取第一個輸入取前半、第二個輸入取後半
* 不可第一個輸入前半、後半都取
* permute
* 將兩筆輸入的前半、後半分別標示為 A, B, C, D
* 可以將 A, B, C, D 任意選兩個，以任意排列放到目標中
因此 unpack 算是 permute 的子集合，unpack 能做的事 permute 都能做，而 permute 也可以將輸入以[ 32/64 bits ](https://software.intel.com/en-us/node/524010)切割後再任意排列
>那這兩個指令在效能上的差異不知道如何
>特地獨立出 unpack，常理上 unpack 應該會快一點吧
>[name=洪正皇][color=#da90e5]
* 以下為以 permute 實作 unpack128 的程式碼，透過第三個參數來控制所選擇的輸入資料取用方式
```clike=
static __attribute__((always_inline)) inline
__m256i _mm256_unpacklo_epi128(__m256i a, __m256i b)
{
return _mm256_permute2x128_si256(a, b, 0x20);
}
static __attribute__((always_inline)) inline
__m256i _mm256_unpackhi_epi128(__m256i a, __m256i b)
{
return _mm256_permute2x128_si256(a, b, 0x31);
}
```
* 終於開始的 AVX 實作
* 以註解提供各暫存器在程式執行時的中間值，可以照這些值 trace 了解一下 unpack 的功用
* 在程式碼後面附上純值版本，單純看資料變動的更簡潔
```clike=
void AVX_transpose(int *src, int *dst, int w, int h)
{
for (int x = 0; x < w; x += 8) {
for (int y = 0; y < h; y += 8) {
__m256i I0 = _mm256_loadu_si256 ((__m256i *)(src + (y + 0) * w + x)); /* I0: 0 1 2 3 4 5 6 7 */
__m256i I1 = _mm256_loadu_si256 ((__m256i *)(src + (y + 1) * w + x)); /* I1: 8 9 10 11 12 13 14 15 */
__m256i I2 = _mm256_loadu_si256 ((__m256i *)(src + (y + 2) * w + x)); /* I2: 16 17 18 19 20 21 22 23 */
__m256i I3 = _mm256_loadu_si256 ((__m256i *)(src + (y + 3) * w + x)); /* I3: 24 25 26 27 28 29 30 31 */
__m256i I4 = _mm256_loadu_si256 ((__m256i *)(src + (y + 4) * w + x)); /* I4: 32 33 34 35 36 37 38 39 */
__m256i I5 = _mm256_loadu_si256 ((__m256i *)(src + (y + 5) * w + x)); /* I5: 40 41 42 43 44 45 46 47 */
__m256i I6 = _mm256_loadu_si256 ((__m256i *)(src + (y + 6) * w + x)); /* I6: 48 49 50 51 52 53 54 55 */
__m256i I7 = _mm256_loadu_si256 ((__m256i *)(src + (y + 7) * w + x)); /* I7: 56 57 58 59 60 61 62 63 */
__m256i T0 = _mm256_unpacklo_epi32(I0, I1); /* T0: 0 8 1 9 4 12 5 13 */
__m256i T1 = _mm256_unpacklo_epi32(I2, I3); /* T1: 16 24 17 25 20 28 21 29 */
__m256i T2 = _mm256_unpacklo_epi32(I4, I5); /* T2: 32 40 33 41 36 44 37 45 */
__m256i T3 = _mm256_unpacklo_epi32(I6, I7); /* T3: 48 56 49 57 52 60 53 61 */
__m256i T4 = _mm256_unpackhi_epi32(I0, I1); /* T4: 2 10 3 11 6 14 7 15 */
__m256i T5 = _mm256_unpackhi_epi32(I2, I3); /* T5: 18 26 19 27 22 30 23 31 */
__m256i T6 = _mm256_unpackhi_epi32(I4, I5); /* T6: 34 42 35 43 38 46 39 47 */
__m256i T7 = _mm256_unpackhi_epi32(I6, I7); /* T7: 50 58 51 59 54 62 55 63 */
I0 = _mm256_unpacklo_epi64(T0, T1); /* I0: 0 8 16 24 4 12 20 28 */
I1 = _mm256_unpacklo_epi64(T2, T3); /* I1: 32 40 48 56 36 44 52 60 */
I2 = _mm256_unpacklo_epi64(T4, T5); /* I2: 2 10 18 26 6 14 22 30 */
I3 = _mm256_unpacklo_epi64(T6, T7); /* I3: 34 42 50 58 38 46 54 62 */
I4 = _mm256_unpackhi_epi64(T0, T1); /* I4: 1 9 17 25 5 13 21 29 */
I5 = _mm256_unpackhi_epi64(T2, T3); /* I5: 33 41 49 57 37 45 53 61 */
I6 = _mm256_unpackhi_epi64(T4, T5); /* I6: 3 11 19 27 7 15 23 31 */
I7 = _mm256_unpackhi_epi64(T6, T7); /* I7: 35 43 51 59 39 47 55 63 */
T0 = _mm256_unpacklo_epi128(I0, I1); /* T0: 0 8 16 24 32 40 48 56 */
T1 = _mm256_unpacklo_epi128(I4, I5); /* T1: 1 9 17 25 33 41 49 57 */
T2 = _mm256_unpacklo_epi128(I2, I3); /* T2: 2 10 18 26 34 42 50 58 */
T3 = _mm256_unpacklo_epi128(I6, I7); /* T3: 3 11 19 27 35 43 51 59 */
T4 = _mm256_unpackhi_epi128(I0, I1); /* T4: 4 12 20 28 36 44 52 60 */
T5 = _mm256_unpackhi_epi128(I4, I5); /* T5: 5 13 21 29 37 45 53 61 */
T6 = _mm256_unpackhi_epi128(I2, I3); /* T6: 6 14 22 30 38 46 54 62 */
T7 = _mm256_unpackhi_epi128(I6, I7); /* T7: 7 15 23 31 39 47 55 63 */
_mm256_storeu_si256((__m256i *)(dst + ((x + 0) * h) + y), T0);
_mm256_storeu_si256((__m256i *)(dst + ((x + 1) * h) + y), T1);
_mm256_storeu_si256((__m256i *)(dst + ((x + 2) * h) + y), T2);
_mm256_storeu_si256((__m256i *)(dst + ((x + 3) * h) + y), T3);
_mm256_storeu_si256((__m256i *)(dst + ((x + 4) * h) + y), T4);
_mm256_storeu_si256((__m256i *)(dst + ((x + 5) * h) + y), T5);
_mm256_storeu_si256((__m256i *)(dst + ((x + 6) * h) + y), T6);
_mm256_storeu_si256((__m256i *)(dst + ((x + 7) * h) + y), T7);
}
}
}
```
```
原始矩陣
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
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63
第一次互換後
0 8 1 9 4 12 5 13
16 24 17 25 20 28 21 29
32 40 33 41 36 44 37 45
48 56 49 57 52 60 53 61
2 10 3 11 6 14 7 15
18 26 19 27 22 30 23 31
34 42 35 43 38 46 39 47
50 58 51 59 54 62 55 63
第二次互換後
0 8 16 24 4 12 20 28
32 40 48 56 36 44 52 60
2 10 18 26 6 14 22 30
34 42 50 58 38 46 54 62
1 9 17 25 5 13 21 29
33 41 49 57 37 45 53 61
3 11 19 27 7 15 23 31
35 43 51 59 39 47 55 63
第三次互換後
0 8 16 24 32 40 48 56
1 9 17 25 33 41 49 57
2 10 18 26 34 42 50 58
3 11 19 27 35 43 51 59
4 12 20 28 36 44 52 60
5 13 21 29 37 45 53 61
6 14 22 30 38 46 54 62
7 15 23 31 39 47 55 63
```
* AVX 版本加上 prefetch
```clike=
void AVX_prefetch_transpose(int *src, int *dst, int w, int h)
{
for (int x = 0; x < w; x += 8) {
for (int y = 0; y < h; y += 8) {
#define AVXPFDIST 8
_mm_prefetch(src+(y + AVXPFDIST + 0) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + AVXPFDIST + 1) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + AVXPFDIST + 2) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + AVXPFDIST + 3) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + AVXPFDIST + 4) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + AVXPFDIST + 5) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + AVXPFDIST + 6) *w + x, _MM_HINT_T1);
_mm_prefetch(src+(y + AVXPFDIST + 7) *w + x, _MM_HINT_T1);
__m256i I0 = _mm256_loadu_si256 ((__m256i *)(src + (y + 0) * w + x));
__m256i I1 = _mm256_loadu_si256 ((__m256i *)(src + (y + 1) * w + x));
__m256i I2 = _mm256_loadu_si256 ((__m256i *)(src + (y + 2) * w + x));
__m256i I3 = _mm256_loadu_si256 ((__m256i *)(src + (y + 3) * w + x));
__m256i I4 = _mm256_loadu_si256 ((__m256i *)(src + (y + 4) * w + x));
__m256i I5 = _mm256_loadu_si256 ((__m256i *)(src + (y + 5) * w + x));
__m256i I6 = _mm256_loadu_si256 ((__m256i *)(src + (y + 6) * w + x));
__m256i I7 = _mm256_loadu_si256 ((__m256i *)(src + (y + 7) * w + x));
__m256i T0 = _mm256_unpacklo_epi32(I0, I1);
__m256i T1 = _mm256_unpacklo_epi32(I2, I3);
__m256i T2 = _mm256_unpacklo_epi32(I4, I5);
__m256i T3 = _mm256_unpacklo_epi32(I6, I7);
__m256i T4 = _mm256_unpackhi_epi32(I0, I1);
__m256i T5 = _mm256_unpackhi_epi32(I2, I3);
__m256i T6 = _mm256_unpackhi_epi32(I4, I5);
__m256i T7 = _mm256_unpackhi_epi32(I6, I7);
I0 = _mm256_unpacklo_epi64(T0, T1);
I1 = _mm256_unpacklo_epi64(T2, T3);
I2 = _mm256_unpacklo_epi64(T4, T5);
I3 = _mm256_unpacklo_epi64(T6, T7);
I4 = _mm256_unpackhi_epi64(T0, T1);
I5 = _mm256_unpackhi_epi64(T2, T3);
I6 = _mm256_unpackhi_epi64(T4, T5);
I7 = _mm256_unpackhi_epi64(T6, T7);
T0 = _mm256_unpacklo_epi128(I0, I1);
T1 = _mm256_unpacklo_epi128(I4, I5);
T2 = _mm256_unpacklo_epi128(I2, I3);
T3 = _mm256_unpacklo_epi128(I6, I7);
T4 = _mm256_unpackhi_epi128(I0, I1);
T5 = _mm256_unpackhi_epi128(I4, I5);
T6 = _mm256_unpackhi_epi128(I2, I3);
T7 = _mm256_unpackhi_epi128(I6, I7);
_mm256_storeu_si256((__m256i *)(dst + ((x + 0) * h) + y), T0);
_mm256_storeu_si256((__m256i *)(dst + ((x + 1) * h) + y), T1);
_mm256_storeu_si256((__m256i *)(dst + ((x + 2) * h) + y), T2);
_mm256_storeu_si256((__m256i *)(dst + ((x + 3) * h) + y), T3);
_mm256_storeu_si256((__m256i *)(dst + ((x + 4) * h) + y), T4);
_mm256_storeu_si256((__m256i *)(dst + ((x + 5) * h) + y), T5);
_mm256_storeu_si256((__m256i *)(dst + ((x + 6) * h) + y), T6);
_mm256_storeu_si256((__m256i *)(dst + ((x + 7) * h) + y), T7);
}
}
}
```
### 效能圖
### perf 驗證 cache-miss
## 其他嘗試
#### github 已經上傳程式碼，紀錄及解說待補
Sign in with Wallet
Connect another wallet