# Linux 核心專題: 〈每位程式開發者都該有的記憶體知識〉修訂
> 執行人: st10740
> [專題解說影片](https://youtu.be/1pLvttry894)
### Reviewed by `Wufangni`
- 問題一
>我使用 x86_64 架構處理器的 gcc 提供的 _mm_stream_si32 方法進行非暫存寫入，此方法可以將 32 bit 的整數數值寫入指定的記憶體位址，且資料會被標示為 non-temporal。如要使用一般寫入方法，則將其改為一般的陣列寫入方法即可。
`_mm_stream_si32` 方法是直接將數值寫入指定的位址，但如何判斷此時該位址記憶體是可使用的(未有資料佔據的情況)呢?
> [name=st10740]
> `_mm_stream_si32` 方法沒有限制不能將資料寫入已有資料佔據的記憶體位址。`_mm_stream_si32` 使用的是合併寫入方法 (Write combining, WC)，在將資料寫入主記憶體前會先被寫入 write combine buffer (WCB)，等累積一定的寫入操作量後才會一併寫入主記憶體中，不過根據 [Write Combining Memory
Implementation Guidelines](https://download.intel.com/design/PentiumII/applnots/24442201.pdf)：
>
> > The WC buffering of writes has another facet, data is also collapsed e.g. multiple writes to the same location will leave the last data written in the location and the other writes may be lost.
>
> 若對相同的記憶體位址進行多次寫入操作，只有最後一次寫入的資料會被保存並寫入到主記憶體。
- 問題二
實驗部分及 [〈What Every Programmer Should Know About Memory〉閱讀筆記](https://hackmd.io/@ivywang2015/cpumemory-note) 有大量圖片無法顯示的狀況出現。
> [name=st10740]
> 感謝提醒，已進行修正
### Reviewed by `otteryc`
在進行實驗時，有將程式限制在 CPU 0 上執行，在這執行這個實驗時，有沒有關閉 Hyper-Threading 的必要？
> [name=st10740]
> 將程式限制在 CPU 0 上執行的目的是確保實驗資料都儲存在相同的 L1d、 L2 和 L3 快取中，由於 Hyper-Threading 會在相同的 CPU 上作用，因此不需要對它進行限制。
## 簡介
〈[每位程式開發者都該有的記憶體知識](https://sysprog21.github.io/cpumemory-zhtw/)〉翻自 Ulrich Drepper 於 2007 年撰寫的論文〈[What Every Programmer Should Know About Memory](https://www.akkadia.org/drepper/cpumemory.pdf)〉(版次: 1.0)，儘管目前已涵蓋第一到第八章，然而仍有大量的改進要進行。
## TODO: 〈每位程式開發者都該有的記憶體知識〉閱讀並紀錄問題
> 若發現內容錯誤和過時的資訊，提交 pull request，嘗試做出貢獻
### 閱讀筆記
[〈What Every Programmer Should Know About Memory〉閱讀筆記](https://hackmd.io/@ivywang2015/cpumemory-note)
### 內容校閱
[Pull request](https://github.com/sysprog21/cpumemory-zhtw/pull/8)
### 改進句子流暢度
1. (Ch2.1.2 Dynamic RAM) DRAM 寫入工作原理
- 譯文
> 要寫到記憶單元中，則要適當地設置資料線路 𝐷𝐿，然後提高 𝐴𝐿 的電位一段足以讓電容充電或放電的時間。
- 原文
> To write to the cell the data line DL is appropriately set and then AL is raised for a time long enough to charge or drain the capacitor.
- 修正動機
「提高 𝐴𝐿 的電位一段足以讓電容充電或放電的時間」這段文字提到了「提高 𝐴𝐿 的電位」和「一段足以讓電容充電或放電的時間」兩件事情，但是從文字中較難看出兩者的關聯性，影響理解 AL 的運作機制，因此我將這段文字改寫，表示需要將 AL 的電位提高到一段足夠長的時間。
```
修正：
要寫到記憶單元中，則要適當地設置資料線路 𝐷𝐿，然後將 𝐴𝐿 的電位提高至足夠長的時間，以讓電容充電或放電。
```
2. (Ch4.2 Multi-Level Page Tables) 多層級分頁表的需求
- 譯文
> 這表示，最有可能是二個需要的第二層目錄，以及與此相應的、更多低層級的目錄。
- 原文
> This means that there are most likely two level 2 directories needed and correspondingly more lower level directories.
- 修正動機
根據前後文，這段文字主要是在探討資料無法總是被存取於記憶體中的連續位址空間，因此需要引入多層級的分頁表。且這邊舉 Stack 和 Heap 兩個不連續的記憶體空間為例，說明需要兩個第二層目錄，因此我認為使用「需要兩個第二層目錄」比起「二個需要的第二層目錄」更能強調兩個目錄的需求。
```
修正：
這表示，最有可能是需要兩個第二層目錄，以及與此相應的、更多低層級的目錄。
```
3. (Ch4.4 Impact Of Virtualization) DomU 的系統核心
- 譯文
> 目前，這基本上是與沒有特權的 DomU 系統核心相同的系統核心，而且 –– 就所關心的記憶體管理而言 –– 它們沒什麼區別。
- 原文
> Currently, this is basically the same kernel as the unprivileged DomU kernels and, as far as memory handling is concerned, they do not differ.
```
修正：
目前，這基本上是與沒有特權的 DomU 系統核心具有相同的系統核心，而且 –– 就所關心的記憶體管理而言 –– 它們沒什麼區別。
經老師建議後修正為：
目前，這跟運作於非特權模式的 DomU 具備相同的系統核心，而且 –– 就所關心的記憶體管理而言 –– 它們沒什麼區別。
```
### 修正詞彙
1. (Ch3 CPU Caches) 快取大小的影響
- 譯文
> 尤其是執行多個行程的系統，其工作集的容量為所有個別的處理器與系統核心的容量總和。
- 原文
> This is especially true for systems running multiple processes where the size of the working set is the sum of the sizes of all the individual processes and the kernel.
```
修正：
「其工作集的容量為所有個別的 處理器 與系統核心的容量總和」
這句話在原文中指的是 processes 的容量總和，而非 processors，應修正為：
「其工作集的容量為所有個別的 行程 與系統核心的容量總和」
```
### 修正未被翻譯到的句子
1. (Ch3.3.2 Measurements of Cache Effects) 快取預取的量測
- 原文
> There is no prefetching necessary so all element sizes just hit the L1d for each access.
```
可以翻譯成：
因為不需要預取，所以每次存取時，所有元素大小都直接命中 L1d。
```
2. (Ch4.3.2 Influencing TLB Performance) TLB 效能
- 原文
> Only now the alignment required is large.
```
可以翻譯成：
不過現在所需的對齊更大。
```
## TODO: 針對第六章的實驗，予以重現
> 若發現內容錯誤和過時的資訊，提交 pull request，嘗試做出貢獻
### 實驗環境
#### CPU information
```
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 39 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Vendor ID: GenuineIntel
Model name: Intel(R) Core(TM) i5-8265U CPU @ 1.60GHz
CPU family: 6
Model: 142
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
Stepping: 12
CPU max MHz: 3900.0000
CPU min MHz: 400.0000
BogoMIPS: 3600.00
Virtualization features:
Virtualization: VT-x
Caches (sum of all):
L1d: 128 KiB (4 instances)
L1i: 128 KiB (4 instances)
L2: 1 MiB (4 instances)
L3: 6 MiB (1 instance)
NUMA:
NUMA node(s): 1
NUMA node0 CPU(s): 0-7
Vulnerabilities:
Gather data sampling: Mitigation; Microcode
Itlb multihit: KVM: Mitigation: VMX disabled
L1tf: Not affected
Mds: Not affected
Meltdown: Not affected
Mmio stale data: Mitigation; Clear CPU buffers; SMT vulnerable
Retbleed: Mitigation; Enhanced IBRS
Spec rstack overflow: Not affected
Spec store bypass: Mitigation; Speculative Store Bypass disabled via prctl
Spectre v1: Mitigation; usercopy/swapgs barriers and __user pointer
sanitization
Spectre v2: Mitigation; Enhanced / Automatic IBRS; IBPB conditional
; RSB filling; PBRSB-eIBRS SW sequence; BHI Syscall har
dening, KVM SW loop
Srbds: Mitigation; Microcode
Tsx async abort: Not affected
```
#### Caches information
在 linux kernel 中，快取的資訊被紀錄在 `/sys/devices/system/cpu/cpu*/cache` 底下，該目錄底下分別有 `index0`, `index1`, `index2`, `index3` 四個目錄，紀錄了該 CPU 擁有的 快取資訊，其資訊被紀錄在目錄中多個檔案中，如 `type`, `level`, `shared_cpu_map`, `coherency_line_size`, `ways_of_associativity` 等。
cache 的結構彙整如下︰
| | | type | level | shared_cpu_map | coherency_line_size | ways_of_associativity |
| ---- | ------- | ----------- | ----- | -------------- | --- | --- |
| cpu0 | index 0 | Data | 1 | 11 | 64 | 8 |
| | index 1 | Instruction | 1 | 11 | 64 | 8 |
| | index 2 | Unified | 2 | 11 | 64 | 4 |
| | index 3 | Unified | 3 | ff | 64 | 12 |
| cpu1 | index 0 | Data | 1 | 22 | 64 | 8 |
| | index 1 | Instruction | 1 | 22 | 64 | 8 |
| | index 2 | Unified | 2 | 22 | 64 | 4 |
| | index 3 | Unified | 3 | ff | 64 | 12 |
| cpu2 | index 0 | Data | 1 | 44 | 64 | 8 |
| | index 1 | Instruction | 1 | 44 | 64 | 8 |
| | index 2 | Unified | 2 | 44 | 64 | 4 |
| | index 3 | Unified | 3 | ff | 64 | 12 |
| cpu3 | index 0 | Data | 1 | 88 | 64 | 8 |
| | index 1 | Instruction | 1 | 88 | 64 | 8 |
| | index 2 | Unified | 2 | 88 | 64 | 4 |
| | index 3 | Unified | 3 | ff | 64 | 12 |
| cpu4 | index 0 | Data | 1 | 11 | 64 | 8 |
| | index 1 | Instruction | 1 | 11 | 64 | 8 |
| | index 2 | Unified | 2 | 11 | 64 | 4 |
| | index 3 | Unified | 3 | ff | 64 | 12 |
| cpu5 | index 0 | Data | 1 | 22 | 64 | 8 |
| | index 1 | Instruction | 1 | 22 | 64 | 8 |
| | index 2 | Unified | 2 | 22 | 64 | 4 |
| | index 3 | Unified | 3 | ff | 64 | 12 |
| cpu6 | index 0 | Data | 1 | 44 | 64 | 8 |
| | index 1 | Instruction | 1 | 44 | 64 | 8 |
| | index 2 | Unified | 2 | 44 | 64 | 4 |
| | index 3 | Unified | 3 | ff | 64 | 12 |
| cpu7 | index 0 | Data | 1 | 88 | 64 | 8 |
| | index 1 | Instruction | 1 | 88 | 64 | 8 |
| | index 2 | Unified | 2 | 88 | 64 | 4 |
| | index 3 | Unified | 3 | ff | 64 | 12 |
- 每個 CPU 底下都有 4 個快取，分別是 L1d, L1i, L2, L3
- cpu0 和 cpu4 共享 L1d, L1i, L2，cpu1 和 cpu5 共享 L1d, L1i, L2，cpu2 和 cpu6 共享 L1d, L1i, L2，cpu3 和 cpu7 共享 L1d, L1i, L2 (由 `shared_cpu_map` 觀察得知)
- 所有的 cpu 皆共享同一個 L3
- 每個快取的快取行大小都是 64 bytes
- L1d 和 L1i 是 8-way set associative，L2 是 4-way set associative，L3 是 12-way set associative
### 6.1 Bypassing the Cache
#### 實驗說明
當一個大型的資料結構（如：矩陣）被產生但是沒有馬上被使用時，因為會佔據大量的快取空間，可能會導致一些很快會被使用到的資料被驅逐出快取，影響效能。為了解決這個問題，處理器提供了非暫存（non-temporal）寫入操作方法，讓資料可以直接寫入記憶體中，不經過快取。這個作法看似耗費成本，但是處理器會使用合併寫入（write-combining） 方法，合併多個寫入操作，讓快取行盡量被填滿後再一次進行存取。
本實驗的目的為探討分別使用非暫存寫入操作和一般寫入操作來存取大型矩陣的效能差異，並各別進行兩種測試，一種是以內部迴圈增加行號的方式存取，第二種是在內部迴圈增加列號的方式存取，如下圖所示，分別對應於順序存取 (sequential access) 與隨機存取 (random access) 兩種作法。
:::danger
修正圖片存取權限。
> 已進行修正。
:::
#### 實驗方法
[Github](https://github.com/st10740/cpumemory-experiment/tree/main/bypass_cache)
本實驗在四種測試情境下分別建立一個 3000 x 3000 的整數矩陣，其大小足以讓快取無法有效發揮，並計算初始化整個矩陣所需的秒數。我參考 [Random and sequential](https://hackmd.io/@dange/B1J3omXfV) 的作法進行實驗設計。 每種測試情境皆執行 20 次，並取中間 10 次結果平均，以防止極端情況的發生。
##### 環境設定
由於 3000 x 3000 的整數矩陣是儲存於記憶體中的 Stack 區域，而 Stack 的大小有受到限制，為了進行測試，需要先將限制解除：
```shell
$ ulimit -s unlimited
```
另外，為了降低實驗的誤差，將限制程式只執行在 cpu0 上。
```shell
$ taskset --cpu-list 0 ./$(EXEC)
```
##### 非暫存（non-temporal）寫入操作 & 順序存取
```c
double sequential_non_temporal_write(unsigned int size) {
int arr[size][size], i, j;
clock_t start, end;
double time;
start = clock();
for (i = 0; i < size; i++) {
for (j = 0; j < size; j++) {
_mm_stream_si32(&arr[i][j], i + j);
}
}
end = clock();
time = ((double) (end - start)) / CLOCKS_PER_SEC;
return time;
}
```
我使用 x86_64 架構處理器的 gcc 提供的 `_mm_stream_si32` 方法進行非暫存寫入，此方法可以將 32 bit 的整數數值寫入指定的記憶體位址，且資料會被標示為 non-temporal。如要使用一般寫入方法，則將其改為一般的陣列寫入方法即可。
```diff
- _mm_stream_si32(&arr[i][j], i + j);
+ arr[i][j] = i + j;
```
變數 `i` 用以增加列號，`j` 用以增加行號。因此將 `j` 在內部迴圈遞增可以進行順序存取，相反則是隨機存取。
#### 實驗結果
```shell
$ make run
normal write (sequential): 0.020516
non-temporal write (sequential): 0.019918
normal write (random): 0.037002
non-temporal write (random): 0.115992
```
| | sequential| random |
| -------- | -------- | -------- |
| normal | 0.020516s | 0.037002s |
| non-temporal | 0.019918s | 0.115992s |
此結果顯示的現象與論文中的數據結果差異不大，順序存取比起隨機存取表現較佳。而當同樣為順序存取時，一般寫入操作與非暫存寫入操作所花的時間差不多，非暫存寫入操作甚至稍快，其原因為使用了合併寫入方法，且記憶體排序（memory ordering）規則被放寬了，處理器寫回變得更有彈性，可以充分利用頻寬。當同樣為隨機存取時，非暫存寫入的效能較一般寫入的效能差，原因為無法使用合併寫入，且沒有暫存直接寫回記憶體所需的成本較高。
:::info
Non-Temporal Data
根據 Intel® 64 and IA-32 Architectures Software Developer’s Manual 中的說明：
> The non-temporal data is written to memory with WC semantics.
非暫存寫入使用合併寫入方法 (Write combining, WC)。
> Using the WC semantics, the store transaction will be weakly ordered, meaning that the data may not be written to memory in program order, and the store will not write allocate.
> WC semantics require software to ensure coherence, with respect to other processors and other system agents (such as graphics cards). Appropriate use of synchronization and fencing must be performed for producer-consumer usage models.
合併寫入方法不保證存儲操作按照原來的順序執行，且無法保證被寫入 write combine buffer (WCB) 的資料在各個處理器上具有一致的可見度，因此若要確保快取一致性 (cache coherency)，需要在使用 `_mm_stream_si32` 儲存資料後，使用 `mm_fence` 方法。
:::
### 6.2.1 Optimizing Level 1 Data Cache Access
#### 實驗說明
想要改善程式的效能最好的方法就是提升程式存取 L1 的效率，而最直接的做法就是改進空間局部性 (Spatial Locality) 和時間局部性 (Temporal Locality)。
本實驗將以 1000x1000 且型別為 double 的矩陣乘法為例，探討如何利用順序存取提升局部性以最佳化程式。
首先，矩陣存取最簡單的方法是直接根據數學公式進行實作：
$(AB)_{ij} = \sum_{k=0}^{N-1} a_{ik}b_{kj} = a_{i1}b_{1j} + a_{i2}b_{2j} + ... + a_{i(N-1)}b_{(N-1)j}$
```c
for (i = 0; i < N; ++i)
for (j = 0; j < N; ++j)
for (k = 0; k < N; ++k)
res[i][j] += mul1[i][k] * mul2[k][j];
```
這樣的做法會使得每次求`res` 中的值時 `mul2` 都使用非順序的方式進行存取，造成前後存取的資料無法位於同一個快取行中，因此每跑完一輪內部迴圈就要使用 1000 個快取行。
為了解決這個問題，第二種做法將 `mul2` 先進行轉置，使它和 `mul1` 採用相同的順序進行存取，因此原本每輪 1000 個快取行的需求變成只需要約 $1000 / (64 / 8) = 125$ 個快取行，其中一個快取行為 64 bytes，`sizeof(double)` 為 8，做法如下方程式碼：
```c
double tmp[N][N];
for (i = 0; i < N; ++i)
for (j = 0; j < N; ++j)
tmp[i][j] = mul2[j][i];
for (i = 0; i < N; ++i)
for (j = 0; j < N; ++j)
for (k = 0; k < N; ++k)
res[i][j] += mul1[i][k] * tmp[j][k];
```
雖然這個方法可以有效減少快取行數量的需求，但是需要先複製一份轉置後的矩陣資料到新的陣列中，這本身也是一種成本，尤其是當資料量很大時會耗費許多記憶體空間。
因此第三種做法嘗試以不需要複製整個矩陣資料的方式減少過多快取行存取的問題。它將原本一次計算一個 `res` 中的值的做法改成一次計算多個 `res` 中相鄰索引的值，如此可以充分利用完整個快取行後再利用下一個快取行。
```c
#define CLS 64
#define SM (CLS / sizeof (double))
for (i = 0; i < N; i += SM)
for (j = 0; j < N; j += SM)
for (k = 0; k < N; k += SM)
for (i2 = 0, rres = &res[i][j],
rmul1 = &mul1[i][k]; i2 < SM;
++i2, rres += N, rmul1 += N)
for (k2 = 0, rmul2 = &mul2[k][j];
k2 < SM; ++k2, rmul2 += N)
for (j2 = 0; j2 < SM; ++j2)
rres[j2] += rmul1[k2] * rmul2[j2];
```
`CLS` 為裝置的快取行大小，其值可以透過以下命令取得：
```shell
$ getconf LEVEL1_DCACHE_LINESIZE
```
`SM` 為一次處理 `res` 中的值的數量，由於陣列的型別為 `double`，因此 `SM` 為一個快取行可以放入的 double 資料的數量，以我的裝置為例，其值為 $64/8 = 8$。這個方法使用了六個迴圈，最外圍的三個迴圈的將整個問題切成多個子問題來處理，每個子問題負責一次計算8個 `res` 中相鄰索引的值，其由內部的三個迴圈負責處理。
第四種做法與第三種做法的邏輯相同，但另外使用了 SIMD（單指令多資料，Single Instruction, Multiple Data）技術來一次處理兩個值，這裡利用了 Intel 處理器提供的 SSE2 指令來達成這個目的。
```c
int i, i2, j, j2, k, k2;
double *restrict rres;
double *restrict rmul1;
double *restrict rmul2;
for (i = 0; i < N; i += SM)
for (j = 0; j < N; j += SM)
for (k = 0; k < N; k += SM)
for (i2 = 0, rres = &res[i][j], rmul1 = &mul1[i][k]; i2 < SM;
++i2, rres += N, rmul1 += N)
{
_mm_prefetch (&rmul1[8], _MM_HINT_NTA);
for (k2 = 0, rmul2 = &mul2[k][j]; k2 < SM; ++k2, rmul2 += N)
{
__m128d m1d = _mm_load_sd (&rmul1[k2]);
m1d = _mm_unpacklo_pd (m1d, m1d);
for (j2 = 0; j2 < SM; j2 += 2)
{
__m128d m2 = _mm_load_pd (&rmul2[j2]);
__m128d r2 = _mm_load_pd (&rres[j2]);
_mm_store_pd (&rres[j2],
_mm_add_pd (_mm_mul_pd (m2, m1d), r2));
}
}
}
```
`_mm_load_sd` 和 `_mm_unpacklo_pd` 皆為 Intel 提供的內置函數，根據 [Intel® Intrinsics Guide](https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html#)，`_mm_load_sd` 可以將一個 64 位元的 double 數值載入到一個 128 位元的整數向量的低 64 位，並將高位部分清除，而 `_mm_unpacklo_pd` 則可以組合兩個 `m128d` 型別的值，將第一個參數的 [63:0] 位元部分複製到返回值的 [63:0] 位元部分，並將第二個參數的 [63:0] 位元部分複製到返回值的 [127:64] 位元部分。因此，最後 `m1d` 中存了兩份 `rmul1[k2]` 數值，分別用於和 `rmul2` 中兩個相鄰的數值相乘。
```c
__m128d m1d = _mm_load_sd (&rmul1[k2]);
m1d = _mm_unpacklo_pd (m1d, m1d);
```
`_mm_load_pd` 和 `_mm_load_sd` 不同的是，`_mm_load_pd` 一次將傳入的指標參數指向的 128 位元資料存入向量返回值，而非只存其低 64 位元，因此 `m2` 和 `r2` 各別存了 `rmul2` 和 `rres` 中的兩個相鄰索引的元素數值。接著透過 `_mm_mul_pd`、`_mm_add_pd` 和 `_mm_store_pd` 進行如同第三個做法的 `rres[j2] += rmul1[k2] * rmul2[j2]` 操作，此過程都是一次對兩個元素數值進行運算。
```c
__m128d m2 = _mm_load_pd (&rmul2[j2]);
__m128d r2 = _mm_load_pd (&rres[j2]);
_mm_store_pd (&rres[j2], _mm_add_pd (_mm_mul_pd (m2, m1d), r2));
```
#### 實驗方法
[Github](https://github.com/st10740/cpumemory-experiment/tree/main/optimize_L1d_access/matrix_multiplication)
本實驗將針對上述四種矩陣乘法方法進行測試，並比較其所使用的 CPU cycle 數目，測試的矩陣資料存於型別為 double 的 1000 x 1000 陣列中。
##### 環境設定
與之前的實驗相同，由於矩陣儲存於 Stack 當中，且實驗所使用的矩陣大小較大，需要先將 Stack 的大小限制解除。此外為了降低實驗的誤差，也會限制程式只執行在 cpu0 上。
##### 效能評估方法
在量測 CPU cycle 數目方面，使用的是 Linux 效能分析工具 `Perf`。
```c
$ perf stat --repeat 10 -e cycles taskset --cpu-list 0 ./matrix_mult_origin
$ perf stat --repeat 10 -e cycles taskset --cpu-list 0 ./matrix_mult_tr
$ perf stat --repeat 10 -e cycles taskset --cpu-list 0 ./matrix_mult_subm
$ perf stat --repeat 10 -e cycles taskset --cpu-list 0 ./matrix_mult_vec
```
我將四種矩陣乘法實作方法寫於四個不同的原始程式檔中，並個別編譯後執行，透過 `perf stat` 量測各自執行所使用的 CPU cycle 數。需要注意的是，由於在進行矩陣乘法前會先初始化矩陣，因此最終得到的 CPU cycle 數目也會包含初始化所使用的 CPU cycle，不全然都是矩陣乘法。
##### 實驗設定細節
在每一個方法的原始程式檔中，`res`、`mul1` 和 `mul2` 都會做 64 bytes alignment，如此可以確保預期會在同一個快取行的資料真的在同一個快取行中。
```c
double res[N][N] __attribute__ ((aligned (64)));
double mul1[N][N] __attribute__ ((aligned (64)));
double mul2[N][N] __attribute__ ((aligned (64)));
```
此外，為了觀察不同做法對效能影響的差異性，需要抑制編譯器最佳化。
```c
$ gcc -O0 ...
```
#### 實驗結果
```shell
$ make run
perf stat --repeat 10 -e cycles taskset --cpu-list 0 ./matrix_mult_origin
Performance counter stats for 'taskset --cpu-list 0 ./matrix_mult_origin' (10 runs):
20,499,739,790 cycles:u ( +- 1.38% )
6.428 +- 0.194 seconds time elapsed ( +- 3.02% )
perf stat --repeat 10 -e cycles taskset --cpu-list 0 ./matrix_mult_tr
Performance counter stats for 'taskset --cpu-list 0 ./matrix_mult_tr' (10 runs):
11,745,078,715 cycles:u ( +- 0.92% )
3.2437 +- 0.0433 seconds time elapsed ( +- 1.33% )
perf stat --repeat 10 -e cycles taskset --cpu-list 0 ./matrix_mult_subm
Performance counter stats for 'taskset --cpu-list 0 ./matrix_mult_subm' (10 runs):
9,633,174,110 cycles:u ( +- 0.15% )
2.7229 +- 0.0106 seconds time elapsed ( +- 0.39% )
perf stat --repeat 10 -e cycles taskset --cpu-list 0 ./matrix_mult_vec
Performance counter stats for 'taskset --cpu-list 0 ./matrix_mult_vec' (10 runs):
12,480,753,121 cycles:u ( +- 0.07% )
3.4716 +- 0.0159 seconds time elapsed ( +- 0.46% )
```
| | Original | Transpose | Sub-Matrix | Vectorized |
| ------ | -------- | --------- | --- | --- |
| Cycles | 20,499,739,790 | 11,745,078,715 | 9,633,174,110 | 12,480,753,121 |
| Relative | 100% | 57% | 47% | 61% |
將此結果與論文中的結果對比，使用 Transpose 和 Sub-Matrix 的效能提升幅度沒有像論文中提升地那麼多，CPU cycle 的相對數目從原本的 100% 降低到 23.4%。另外，我觀察到使用 Vectorized 做法的效能提升並不如其他優化方法顯著，僅提升了 39%，若將 level 1 的編譯器最佳化開啟，則結果變化如下：
| | Original | Transpose | Sub-Matrix | Vectorized |
| ------ | -------- | --------- | --- | --- |
| Cycles | 6,123,203,663 | 4,340,239,814 | 2,539,652,819 | 1,884,549,102 |
| Relative | 100% | 71% | 41% | 31% |
Vectorized 做法搭配編譯器最佳化能有效提升整體效能，從原本只能提升 39%，變成提升了 69%。
:::danger
解讀實驗結果。
> 已補上。
:::
## TODO: 第八章的翻譯
> 提交 pull request，嘗試做出貢獻
Sign in with Wallet
Connect another wallet