# 課程資訊
* 期中考
* 4/14 9:00-11:00
* 範圍至第二章
* 40%-50% 是非題，剩下的是題組
* 滿分 120~130
* 第二章看影片

# 第一章: Fundamentals of Quantitative Design and Analysis
## Performance 提升手段
* 提升 semiconductor technology: 如更快更好的晶片等
* 提升 computer architectures: 如 RISC 等

## 各種電腦裝置簡介
### Personal Mobile Device (PMD)
* 個人行動裝置，如手機、電腦等
* 主要考量議題
* 價格
* 即時性需求
* Soft real-time: 允許短暫的延遲，如影片播放
* Hard real-time: 不允許延遲，如自駕車系統
### Desktop Computing
* 桌面電腦
* 主要考量議題
* 價格與效能的平衡
### Servers
* 主要考量議題
* 可靠性（Dependability）
* 可擴展性（Scalability）
* 吞吐量（Throughput）
### Clusters/ Warehouse-Sacle Computers
* 與軟體即服務（SaaS, Software as a Service） 相關
* Clusters 代表一組相互連接的伺服器
* Warehouse-Sacle Computers (WSCs) 是規模擴展到數萬台伺服器，最大規模的叢集
* 主要考量議題
* 價格與效能比
* 功耗管理
### Embedded Computers
* 專門設計來執行特定功能的計算機系統
* 主要考量議題
* 即時性
* 低功耗
* 程式碼密度: 因為儲存空間有限
* 系統設計方法
* 系統單晶片（System on a Chip, **SoC**）: 將 CPU、I/O 等等必備硬體元件整合在同一晶片上的技術
* 直接使用現成的嵌入式處理器
* Custom Software + DSP + Processor Core: 將客製化軟體結合數位訊號處理器（DSP, Digital Signal Processor）與處理器核心（如 ARM、RISC-V）

## Parallelism 種類
* 應用層面
* Data-Level parallelism (DLP): 相同的運算可以在不同的資料上獨立進行
* Task-Level parallelism (TLP): 不同的任務可以獨立運行

## Parallel 架構 (重要)
* Single instruction stream, single data stream (SISD)
* **Single instruction stream, multiple data streams (SIMD)**: 最重要
* Multiple instruction streams, single data stream (MISD)
* Multiple instruction streams, multiple data streams (MIMD)

## Instruction Set Architecture (ISA)
* 指令集
* 主要類別:
* RISC: 較精簡，如 ARM
* CISC: 較複雜，如 x86

## Computer Designer 的任務
* Instruction set architecture: 指令集架構
* Organization: 組織結構設計
* Hardware: 硬體邏輯設計
* Architecture: 以上三者的合稱

## Power and Energy
* Power In: 電源供應器提供的能量
* Power out: 計算消耗及熱能
* Thermal Design Power (TDP): 熱設計功耗，代表CPU 在高負載下長時間穩定運行所需的功率
* DVFS: 根據負載調整 clock rate 和電壓
* Dynamic Energy
* Dynamic Power
* 降低電壓或頻率可以降低Dynamic 功耗
* Static Power: 維持 State 所需的基本能量

## Wafer and Die
* Wafer 表示晶圓
* Die 表示從晶圓上切割出來的單一晶片，會有良率問題

## Dependability
* 服務級別協議 (Service Level Agreement, SLA): 一份正式的合約，定義了服務供應商必須達到的標準。如服務可用性 99.9%
* 服務級別目標 (Service Level Objective, SLO): 為 SLA 內的一個具體目標如: API 回應時間不超過 200ms
* 系統在 SLA 考量下，可分成以下兩種狀態
* Service Accomplishment: 服務完成
* Service Interruption: 服務中斷

### 量化 (Define and quantity dependability)
* Failures In Time (FIT): 每 10 億 ($10^9$) 小時的失效次數
* 與之類似的 Failure rate = FIT/$10^9$，代表每 $10^9$ 小時平均的失效次數
* Mean Time To Failure (MTTF): 1/Failure rate = 1/(FIT/$10^9$)，代表系統在發生故障前的平均運行時間。換句話說，平均多久會失效一次
* Mean Time To Repair (MTTR): 從失效到恢復服務的平均修復時間
* Mean Time Between Failures (MTBF): MTTF + MTTR，表示兩次故障之間的平均時間
* Module availability: MTTF/(MTTF+MTTR)，表示服務在正常與中斷狀態間切換的比例

## 衡量 Performance (本章最重要)
### 使用數據衡量
* Response time: 系統從開始到解決服務所消耗的時間
* Execution time: 真實消耗在服務上的時間
* Execution time 與 Performance 為倒數關係
* Throughput:
* Wall-clock time
* Elapsed time
* CPU time: 程式實際佔用 CPU 執行的時間
* User CPU time:
* System CPU time

### 選擇程式衡量
* Real applications: 直接測試實際使用的應用程式
* Modified applications: 微調實際使用的應用程式後測試
* Kernels: 只測試核心部分
* Toy benchmarks: 小型、非常簡單的測試程式
* Synthetic Benchmarks: 類似 Kernels，與之不同的是完全人造，並不像 Kernels 取自真實程式碼
* 知名 benchmarks: Whetstone、Dhrystone

### 多個 benchmark 的平均計算
* 多硬體設備測試多個 benchmark 後的綜合評估方式
* Total Execution Time: 將不同的 benchmark test 所消耗的時間直接相加後取平均
* Weighted Execution Time: 將不同的 benchmark test 所消耗的時間乘以權重後，再相加取平均
* Normalized Execution Time of Geometric Means:
$$
\left( \prod_{i=1}^{n} \text{Execution time ratio}_i \right)^{\frac{1}{n}}
$$

## Locality
* 程式在執行時傾向於重複存取最近使用過的資料和指令
* 分成兩種:
* Temporal locality: 同一塊資料或指令可能在短時間內多次被存取
* Spatial locality: 存取某個 memory address 後，接下來可能會存取鄰近的 address

## Parallelism
* Pipelining: 讓 CPU 在執行一條指令的同時，開始處理下一條指令的某些階段
* Carry-Lookahead Adder: 現代 ALU 採用的平行化技術

## Amdahl's Law
* 升級某些結構能提升的 performance，受限於該結構站整體的比例
* Fraction enhances: 增強部分佔整體的比例
* Speedup enhanced: 增強部分的加速比例
* 若原本需花 5 秒才能完成的工作，現今只需要花 2 秒，則 Speedup enhanced 為 5/2

### 計算範例 1
新 CPU 的計算速度比原始 CPU 快 10 倍。假設原始 CPU 40% 的時間在執行計算，60% 的時間在等待 I/O。求引入這項增強後，整體的效能提升是多少？

Fraction enhances = 40% = 0.4
Speedup enhanced = 10

$\text{Speedup}_{\text{overall}} = \frac{\text{舊執行時間}}{\text{新執行時間}} = \frac{1}{0.6 + \frac{0.4}{10}}$

### 計算範例 2
對於某個 benchmark 來說
FPSQR（浮點平方根運算）占比 = 20%
所有浮點運算的占比 = 50%

假設有兩種設計選擇：

1. speed up FPSQR 10 倍
2. speed up 所有浮點運算 1.6 倍

比較這兩種設計方案哪一個比較好?

第一點優化後的總 speedup = $\frac{1}{0.8 + 0.2*\frac{1}{10}}$ = 1.219

第二點優化後的總 speedup = $\frac{1}{0.5 + 0.5*\frac{1}{1.6}}$ = 1.230

故第二點優化較好

## CPU Performance Equation
* 程式的 CPU time
= 程式共需要多少 clock cycle 才能執行完畢 x 完成一個 clock cycle 所需的時間
= $\frac{程式共需要多少 clock cycle}{Clock rate}$
* CPI (Cycle Per Instruction): 平均每一條指令需要花多少 CPU clock cycles；不同 Instruction 種類的 CPI 也不同
公式: $\frac{程式共消耗多少 clock cycle}{程式的指令數}$

### 計算範例 3
假設在某程式中:

浮點運算（不包括 FPSQR）占比 = 25%
浮點運算 (不包括 FPSQR) 的平均 CPI = 4.0
其他指令 (包括 FPSQR) 的平均 CPI = 1.33
FPSQR（浮點平方根運算）占比 = 2%
FPSQR 的 CPI = 20
假設有兩種設計選擇：

1. 降低 FPSQR 的 CPI 至 2
2. 降低所有浮點運算 （不包括 FPSQR） 的平均 CPI 至 2.5

比較這兩種設計方案哪一個比較好?

計算全部指令的全部平均 CPI = 4 * 25% + 1.33 * 75% = 2

第一點優化後的新 CPI = 2 - 2% * (20-2) = 1.64

第二點優化後的新 CPI = 2.5 * 25% + 1.33 * 75% = 1.625

故第二點優化較好

## 是非題與觀念解釋
* (X) Multiprocessors are a silver bullet (多處理器能輕易解決複雜問題)
* 過分依賴多處理器不好
* (X) Hardware enhancements that increase performance improve energy efficiency or are at worst energy neutral (提升硬體的性能表現同時會提升能源使用效率，或至少持平)
* 提升性能通常會消耗更多能源
* (X) Benchmarks remain valid indefinitely (基準測試無限期有效)
* 技術的不斷進步會改變基準測試應該衡量的內容
* (X) Peak performance tracks observed performance (峰值性能作為參考來反映實際性能)
* 峰值性能與觀測性能之間的差距很大，且因基準測試的不同而變化
* (X) Synthetic benchmarks predict performance for real programs (合成基準測試能預測真實程式的效能)
* 真實程式可能受到基準測試測量範圍外的因素影響
* (X) MIPS is an accurate measure for comparing performance among computers (MIPS 是一個準確的衡量電腦效能比較的指標)
* 不同指令集架構、不同 Compiler 都會影響 MIPS 的衡量

# 第二章 Memory Hierarchy Design
* 由於相較於 CPU 的發展速度,DRAM 的發展速度慢上許多，故需要透過 Memory Hierarchy 來減少差距
* 依照距離 CPU 的遠近，可以由小到大分成
* register (空間最小、速度最快)
* cathe
* Memory
* Disk (空間最大、速度最慢)

## 如何將資料傳遞至高層級
* 為了更好的管理，將儲存空間以 block 作為基本單位分割
* 當較高層級的儲存空間找不到需要的資料時，會將資料從低層級傳遞至高層級
* 由於高層級的空間較小，故多個低層級的 block 會對應至一個高層級的 block。有三種對應方式
* Fully associative: 從頭開始找，遇到空的 cache block 便直接擺進去
* Direct mapped: 透過模除的方式，決定 memory 的每個 block 可以擺在 cathe 中的哪個 block 中
* 例如 Memory 中的 block 12，只能擺在 cathe 中的 block 4 中 (12 mod 8==4)
* Set associative: 進一步將 cache 群組成 set，接著同樣透過模除的方式，決定 memory 的每個 block 可以擺在 cache 中的哪個 set 中

## 如何定位某個 block 是否在 cache 中
* 在判定一個 address 是否在 cathe 中時
* 透過 index 來確認要查找 cacthe 中的那個 block
* 透過 Tag 來確認目前查找的 cache block 是否是目標 (因為多個 memory 中的 block 可能會對應至一個 cache block)
* 當資料確實在 cache 時稱為 cache hit
* 當資料不在 cache 時稱為 cache miss

## 當 Cache miss 時，哪個 block 應該被取代
* Cache miss 發生後，會向下查詢 memory 中的資料，並將資料帶回 cache 中
* 若此時 cache 已滿，則需考量需要丟棄哪個 block 的資料
* 策略分為
* LRU: 參考作業系統筆記(最佳)
* Random: 完全隨機取代 (最差)
* FIFO: 較舊載入 cache 中的資料優先被取代

## 發生寫入時，cathe 跟 memory 的處理策略
### write hit
* write hit 指的是要寫入的資料剛好有在 cache 中時
* 分成兩大類
* Write Through: 資料同時寫入 cache 跟 memory
* Write Back: 資料只先寫入 cache，僅在 block 被替換時才寫回 memory
* 用 dirty bit 來標記是否待更新回 memory
* Write Stall 問題: 由於 CPU 必須等待寫入操作完成，故被迫暫停其他工作
* 解決方案: 透過 Write Buffer (一塊小 cache) 暫存要寫入 memory 中的資料，等到有空時再真的寫回去

### wirte miss
* Write allocate: 當發生 wirte miss 時，先將 block 從 memory 載入 cache 後，再寫入 cache
* No-Write Allocate: 當發生 wirte miss 時，直接寫入 memory

## Divisions of misses (cache miss 的類型)
* Compulsory Miss: 第一次存取資料時，無法避免的 miss
* 提升 block size 能改善
* Capacity Miss: 由於 cache size 不夠大，無法將所有的 memory block 都放進 cache 中導致的
* 是 cache miss 的主要原因
* 提升 cache size 能改善
* Conflict miss: 由於很多 memory block 可能會對應至同一個 cache 中的 block，於是這些 block 便有衝突關係；當發生衝突時便會 miss (即使其他地方還有空間)
* 提升 Set associative 中的 associative (每個 set 中能容納的資料數量)

## cache perfoermance 公式
* Average Memory Access Time (AMAT) = hit time + miss rate * miss penalty
* AMAT 是衡量 Processor Performance 的重要指標，但並非唯一指標

### 計算範例
假設有兩種 cache 架構：
1. Split Cache：
* 16KB 的 Instruction Cache
* 16KB 的 Data Cache
2. Unified Cache：
* 一個 32KB 的Unified Cache，共同儲存 Instruction 與 Data

假設
data transfer instruction 佔了 47 %
cache hit 消耗 1 個 clock cycle
cache miss 消耗 100 個 clock cycle
unified cache 在 load/store hit 時，還需要額外消耗一個 clock cycle
使用 write-through，故可以忽略 write buffer 的 stall

每執行 1000 條指令當中
有 3.82 次 instruction misses
有 40.9 次 data misses
有 43.3 次 Unified misses

試求兩種 cache 架構的 AMAT?

先計算:
instruction cache miss rate: $\frac{3.82}{1000} = 0.00382$
(每條指令都會有 1 次 instrucion cache access, 因此共有 1000 次 instruction cache access)

data cache miss rate: $\frac{40.9}{1000 * 0.47} = 0.087$
(平均每條指令會有 0.47 次 data cache access, 因此共有 470 次 data cache access)

Unified Cache miss rate: $\frac{43.3}{1000 * 1.47} = 0.0294$
(平均每條指令會有 1 次 instrucion cache access 跟 0.47 次 data cache access, 因此共有 1470 次 cache access)

在所有的 memory access 中 (共 1000+470 次)
instruction cache access 佔了 $\frac{1000}{1000+470}$ = 78%
data cache access 佔了 $\frac{470}{1000+470}$ = 22%

故
Split Cache 的 AMAT = 78% * (1 + 0.00382 * 100) + 22% * (1 + 0.087 * 100) = 3.21
Unified Cache 的 AMAT = 78% * (1 + 0.0294 * 100) + 22% * (1 + 1 + 0.0294 * 100) = 4.17

## 提升 cache performance
### 降低 Miss Penalty
* 引入多層 cache (如 L1, L2, L3 cache 等) 可改善
* 最常見的為 L2 cache
* 引入 L2 cache 後，計算 cache perfoermance 的公式變為:
* L1 hit time + L1 miss rate * (L2 hit time + L2 miss rate * L2 miss penalty)
* 多層 cache 的 miss rate 又可以細分為
* Local Miss Rate: 某一層 cache 的 miss 數除以該層 cache 的總存取次數
* Global Miss Rate: 某一層 cache 的 miss 數除以 CPU 想存取 cache 的總次數
* 多層 cache 的 Inclusion: 是 cache 階層的一種設計原則，主要規範 L1 快取中的資料必定存在於 L2 快取中；可以提高一致性
* 提早將從記憶體載入的資料交給 CPU
* Early Restart: 當發生 cache miss，從記憶體載入 block 至 cache 時，邊載入邊把載入到一半的資料先傳給 CPU
* Critical Word First: 當發生 cache miss 時，優先載入 CPU 需要的部分並即時給 CPU，而非整個 block；之後再補載入整個 block 至 cache 中
* Merging Write Buffer: 若新寫進 "寫入緩衝區" 的資料，與原本就在 "寫入緩衝區" 的資料地址相匹配的話 (如連續)，則將兩者合併 (write merging)，這樣做可以大幅減少寫入次數
* 上面是 write buffer 未進行 write merging 的情況，在寫進記憶體時 (一次寫入一個 write buffer 中的 row)，需要寫入四次
* 下面是 write buffer 進行 write merging 後的情況，在寫進記憶體時，只需要寫入一次
* Victim Cache: 多使用一小塊額外的 cache，記住因為 cache miss 而被 replace 的的 cache block，資源回收再利用

#### 計算範例
假設某臺電腦 cache block 的大小為 64-byte
當發生 cache miss，cache 要取得 Critical 8 bytes 所需的成本為 11 個 clock cycle，接下來，每多抓 8 byte 需要 2 個 clock cycle
CPU 每個 clock cycle 可以處理兩個 load，且每次 load 8 bytes

計算使用與不使用 Critical word first 的 miss penety

使用: miss penety = 11 + (8-1)*2 = 25 clock cycle (完全不用考慮 load 時間，因為可以提早開始跑 load)

不使用: miss penety = 25 + (64/8)/2 clock cycle (需要考慮 load 時間，共需要 8 次 load，故額外消耗 4 個 clock cycle)

### 減少 miss rate
* 透過編譯器優化，盡量避免產生出的指令造成 cache miss
* Merging Arrays: 合併兩個原本獨立的陣列，避免來回分別載入這兩個陣列導致的 cache miss

        // 壞例子 (兩個獨立的陣列)
        int X[1000], Y[1000];
        for (int i = 0; i < 1000; i++) {
            X[i] = Y[i] * 2;
        }

        // 好例子 (合併成結構體陣列)
        struct Point { int x, y; };
        struct Point arr[1000];
        for (int i = 0; i < 1000; i++) {
            arr[i].x = arr[i].y * 2;
        }

* Loop Interchange: 按照儲存在記憶體中的順序來存取陣列

        // 壞例子：以列為主 (column-major order)，cache miss 可能較多
        for (int j = 0; j < N; j++) {
            for (int i = 0; i < M; i++) {
                A[i][j] = B[i][j] + 1;
            }
        }

        // 好例子：以行為主 (row-major order)，提升 spatial locality
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                A[i][j] = B[i][j] + 1;
            }
        }

* Loop Fusion: 合併兩個獨立但操作相似的迴圈，讓資料可以還在 cache 中就存取

        // 壞例子：兩個獨立的迴圈
        for (int i = 0; i < N; i++) {
            A[i] = B[i] + 1;
        }
        for (int i = 0; i < N; i++) {
            C[i] = A[i] * 2;
        }

        // 好例子：迴圈融合
        for (int i = 0; i < N; i++) {
            A[i] = B[i] + 1;
            C[i] = A[i] * 2;
        }

* Blocking: 將資料分成較小的區塊，使其在 cache 內部可以優先被重複使用

        // 壞例子 (無 blocking)
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    C[i][j] += A[i][k] * B[k][j];
                }
            }
        }

        // 好例子 (使用 blocking，提升 cache 命中率)
        int Bsize = 32; // Block size
        for (int i = 0; i < N; i += Bsize) {
            for (int j = 0; j < N; j += Bsize) {
                for (int k = 0; k < N; k += Bsize) {
                    for (int ii = i; ii < i + Bsize; ii++) {
                        for (int jj = j; jj < j + Bsize; jj++) {
                            for (int kk = k; kk < k + Bsize; kk++) {
                                C[ii][jj] += A[ii][kk] * B[kk][jj];
                            }
                        }
                    }
                }
            }
        }

### 透過平行處理減少 penalty
* 透過 Prefetching 技術，預先載入指令或資料。可以直接載入至 cache 中，或者當資料量過大時，暫時放在較快的外部緩衝區中
* Hardware Prefetching:
* Instruction Prefetching: 一次讀取兩個 memory block，一個放入 Instruction Cache 中直接使用，一個放入 Instruction Stream Buffer 中供未來使用
* Data Prefetching: 預先載入之後可能會用到的資料至 Cache 中
* Software Prefetching: 允許透過撰寫程式或編譯器，明確地在程式碼中插入特殊的 Prefetching 指令，從軟體層面決定什麼時候要進行 Prefetching 操作
* Faulting: prefetch 操作可能導致異常 (如存取不應存取的位置)
* nonfaulting (nonbinding prefetch): prefetch 操作保證不會導致異常。造成異常的指令會自動轉為 no-op (不做任何事)
* 理想的 Prefetching 技術應為 Semantically Invisible，代表 Prefetching 操作不改變 register 跟 memory 中的值，且是 nonfaulting 的

補充: Prefetching 的 Stride 技術: 透過計算當前地址與前一個地址之間的差距，來決定下一個 Prefetch 的 block；這個方法在面對有規律的存取模式 (如陣列存取) 效果會非常好

### 計算範例
問:
使用 Prefetch 時，UltraSPARC III 的 effective miss rate 是多少？
(effective miss rate: 沒有使用任何優化機制的情況下，要達到相同效能所等效的 miss rate)

給定條件：
data cache size 為 64KB
Prefetch 會降低 data miss rate 20% (代表有 20 % 的 data miss 倍 Prefetch 機制救起來，prefetch hit rate = 20%)
每 1000 條指令中，data cache miss 平均發生 36.9 次，且 22% 的指令是 data access
Hit 會消耗 1 clock cycle
Miss penalty 會消耗 15 clock cycles

先計算 data cache miss rate = $\frac{36.9}{1000 * 0.22}$ = 0.167

接著，在有 Prefetch 機制下的 AMAT 公式變成:
hit time + miss rate * (prefetch hit rate * Prefetch hit time + prefetch miss rate * prefetch miss penety)

計算 AMAT
AMAT = 1 + 0.167 * (20% * 1 + 80% * 15) = 3.046

有了 AMAT 後，便可計算 effective miss rate:
3.046 = 1 + effective miss rate * 15
effective miss rate 約為 13.6%

### 減少 hit time
* 將 cache 設計的小又簡單，減少找資料所需的時間
* Way prediction: 基於 locality 的特性，在 cache 中花費額外 bits，用來預測下一次存取應該選擇的「路徑」（Way），即 cache 中某個 set 中的 block，來減少 hit time
* Trace Cache: 透過動態追蹤已執行的指令、預測未來的指令執行順序來減少 hit time

### 提升 cache bandwidth
* pipelineing 技術: 提前猜測並執行之後的指令。但猜測錯誤時會增加成本
* Nonblocking cache: 允許 cache 在 Miss 發生時仍然能同時處理其他請求
* 可以細分成:
* Hit Under Miss: 在 cache miss 發生的當下仍能處理其他 cache hit 請求
* Miss Under Miss（Hit Under Multiple Miss）: 在 cache miss 發生的當下仍能處理其他 miss 請求；換句話說，能同時處理多個 cache miss 請求
* 與其搭配的 CPU 需能做到 Out-of-Order Execution (OoO)，即能允許亂序執行指令
* Multiple Banks Cache: 將 cache 進一步切成多個 bank，且可以同時讀取不同 bank 的資料，增加平行度

### 其他優化方法
1. 提升 read 的優先度
* 由於 read 操作出現頻率遠高於 write，故優先處理 read
* 可以透過提高 write buffer 大小來讓 CPU 不需立即處理 write 操作
2. 盡量避免 address translation
* 作業系統在使用 cache 時，傳入的位址可能是 virtual address，會需要先將其轉換為 phycical address 後才能進行查詢
* 虛擬位址需透過 Page Table 與 TLB 才能轉換成實體位址
* 解決方法 -> 使用 Virtual Cache，直接透過 virtual address 查詢
* Virtual Cache 問題:
* Protection: TLB 的其中一個任務是進行記憶體保護。使用 Virtual Cache 會直接跳過這個問題
* Cache Flushing: 不同 process 的相同 virtual address 可能映射到不同的 phycical address，需要在 context switching (切換 process 時)，一併清空跟該 process 有關的 cache
* 實作上，可以在 cache tag 中新增 PID 欄位，來標記這筆資料是屬於哪個 cache 的
* Synonym/Alias: 作業系統可能使用不同的 virtual address 來指向相同的 phycical address，如果使用 virtual cache，同一份資料可能會被儲存在兩個不同的 cache 位置
* 硬體解決方案: 使用 Anti-Aliasing 技術，從根本上保證每個 cache block 只對應到一個唯一的 phycical address
* 軟體解決方案: Page Coloring: 限制 virtual address 的某些低位元與 phycical address 保持一致，使得不同 virtual address 仍然落在同一個 cache Set 中

## Auto-Tuners
* Auto-Tuners 是一組工具，會動態根據當前硬體特性，客製化出當前程式最佳的優化方法
* 接著重新生成客製化後的程式碼以供編譯和執行

## Main Memory 背景
* main memory 的 performance 衡量
* 在 memory 中消耗的時間 (cache miss penety): 可進一步分為
* Access Time: 發出請求到 memory 回傳第一個字的時間
* Cycle Time: 兩次連續的 memory request 的間隔時間
* Bandwidth: 記憶體在單位時間內可以傳輸多少數據給 cache
* Main Memory 主要使用的是 DRAM (成本低，不可斷電)
* Cache 主要使用的是 SRAM (成本高，可斷電)

## DRAM
* 隨著容量增大，Address Lines 變多，DRAM 使用位址多工 (multiplex the address lines) 來在硬體層面實作
* 將地址拆成兩個部分，分兩次送出
* Row Address
* Column Address

比較:
SRAM 不需要像 DRAM 一樣不斷的刷新，只需要少量靜態電流即可維持資料
故相較於 DRAM 速度較快

## DRAM 優化
1. Fast Page Mode (FPM): 在 DRAM 存取資料時，一次載入一個 row 到 row buffer 中，減少重新載入所消耗的時間
2. Synchronous DRAM (SDRAM): 加入 Clock Signal，使 DRAM 能與 CPU 頻率同步
3. Double Data Rate (DDR SDRAM): 除了在 Clock 的 Rising Edge 時工作，也同時在 Falling Edge 時工作，在相同的 clock rate 下提升頻寬

## DRAM Error correction
* 使用 Parity Bits 進行奇偶校驗
* 通常採用 SEC-DED (Single Error Correct, Double Error Detect)
* 並採用 64-bit Data + 8-bit Parity 的配置

## Virtual Machine
* VMM (Virtual Machine Monitor) 是負責管理虛擬機的軟體，又稱為 hypervisor
* 負責將虛擬資源 (Virtual Resources) 映射到 實體資源 (Physical Resources)，guest VM 只能存取虛擬資源
* 程式碼規模比 OS 小非常多
* 必須比 guest VM(VMM 管理的虛擬機) 擁有更高的權限
* 當在 VM 中執行的程式包含大量的 I/O 請求，VMM 需要攔截並處理這些 ststem call，導致 overhead (時間成本開銷) 高
* 如果應用主要吃 CPU ➜ VMM 幾乎沒有影響
* 如果應用大量使用 I/O ➜ 可能產生較高的虛擬化開銷
* 如果應用主要在等待 I/O ➜ 虛擬化開銷可以被隱藏，因為不用 VM 也一樣慢
* VM 的使用場景:
* 安全隔離
* 軟體管理 (如支援舊系統)
* 硬體管理 (如將一台實體機拆分成多台伺服器)

## Cache Coherency (一致性)
### multiple CPU
* 若某 CPU 修改了數據，其他 CPU cache 的資料便會過時
* 透過 cache 一致性協議解決，確保所有 CPU 都能讀取最新數據

### I/O
* I/O 設備通常直接與 main memory 進行數據交換，若此時 cache 中的資料還未寫入 memory 中，便會導致 I/O 讀到錯誤的資料
* 使用 write throuth 技術，確保 cache 與 memory 資料同步
* 將特定的記憶體區域 (如特別給 I/O 的) 標記為 Non-cacheable，，當 CPU 讀取這部分資料時，會直接從主記憶體讀取

## 是非題與觀念解釋
* (X) 根據某支程式的 cache performance 來推估另一支程式的 cache performance
* 每支程式都有不同特性 (如 I/O 密集、浮點數運算等)，不能以偏概全
* (O) 模擬的指令數量不足，可能會導致記憶體階層 performance 測量不準確
* 短時間 (10^6 instruction) 與長時間 ((10^9 instruction)) 的記憶體階層行為特性可能會不一樣
* (O) 在以 cache 為基礎的系統中，記憶體頻寬常會不足
* (O) 在非虛擬化友善的指令集架構上實作 VMM 很困難
* VMM 無法攔截某些會直接影響底層系統的指令
* 某些指令在非最高權限層級執行時，可能影響底層系統 (如針對特殊 register 的操作)

-------------------------------- 期中考線 --------------------------------

# 第三章: Instruction-Level Parallelism and Its Exploitation
## ILP (Instruction-Level Parallelism)
* 不同的指令部分重疊執行的能力便稱為 ILP
* Dynamic approach: 透過硬體判斷指令是否能平行執行
* Static approach: 透過軟體決定指令的執行順序
* Pipeline CPI = 理想的 pipeline CPI + Structural stalls + Data hazard stalls + Control stalls

## Depentences
### Data dependences
* (重要) 若後面的指令會用到前面指令計算出的結果，便會產生 Data dependences
* (重要) 若後面的指令需等待前面指令計算出結果後才能執行，便會產生 Data hazard
* 若指令 j 依賴指令 i 產生的結果，指令 k 依賴指令 j 產生的結果
* 則 "j is data depentent on i" (直接依賴)
* 則 "k is data depentent on i" (間接依賴)
* 有 Data dependent 可能會有 Data hazard，但有 Data hazard 的話一定有 Data dependent

#### Name Dependences
* 當兩條指令使用了相同的 register 或 memory 時，就會造成 Name Dependences
* 這導致兩條指令的位置不能任意對調
* 又可以細分成兩種:
* Anti dependence: 指令 i 讀取某個 register 中的值，而隨後的指令 j 寫入這個 register。指令 j 不可換到指令 i 之前
* Output Dependence: 指令 i 和隨後的指令 j 都寫入同一個 register。指令 j 不可換到指令 i 之前

#### (重要) Data Hazards 種類
* RAW（Read After Write）: 因為 data dependences 導致的
* WAW（Write After Write）: 因為 Output dependences 導致的
* WAR（Write After Read）: 因為 Anti dependence 導致的

### Control Dependences
* 當某些指令是否會執行，會依賴於前面條件的判斷結果時，便會產生 Control Dependences
* 推測執行（Speculative Execution）: 就算不知道分支結果，也先行執行後面的指令

## Basic Compiler Techniques for Exposing ILP
* (重要) 編譯器進行 scheduling 的能力取決於
* 是否能有效利用 ILP
* pipeline 中的 lantency

### Loop Unrolling 技巧
* (重要) 核心概念: 將迴圈部分或完全展開
* 這樣一來，不用每輪迴圈結束時都執行 branch 指令判斷是否跳出，能大幅減少 branch 指令的開銷
* 也允許來自不同 iteration 的指令能被一起 schedule
* 缺點:
* Loop Unrolling 多次後效益遞減
* Code size 會變大
* register 不夠用
* (重要) Loop Unrolling 流程:
1. 確認將 S.D 指令移到 DADDUI 及 BNE 後是否合法，並正確的調整 S.D offset
2. 判斷 Loop Unrolling 是否真的有用
3. 使用不同的 register，避免不必要的限制
4. 移除多餘的 test 跟 branch 指令，並重新改寫迴圈終止條件及 iteration 程式碼
5. 確認 loads 及 stores 指令執行順序是否可以交換，並妥善的 schedule 整份程式碼

範例:
原本要跑四次的迴圈

Loop: L.D F0,0(R1)
      ADD.D F4,F0,F2
      S.D F4,0(R1)
      DADDUI R1,R1,#-32
      BNE R1,R2,Loop

展開後

Loop: L.D F0,0(R1)
      ADD.D F4,F0,F2
      S.D F4,0(R1)
      L.D F0,0(R1)
      ADD.D F4,F0,F2
      S.D F4,0(R1)
      L.D F0,0(R1)
      ADD.D F4,F0,F2
      S.D F4,0(R1)
      L.D F0,0(R1)
      ADD.D F4,F0,F2
      S.D F4,0(R1)
      DADDUI R1,R1,#-32
      BNE R1,R2,Loop

* 觀察可以發現，節省了三次的 DADDUI 跟 BNE 指令

另外，若不同種類的指令相依賴時會有不同的 penety 的話，也可以透過 Loop Unrolling 來優化
例如

Loop: L.D F0,0(R1)
      L.D F6,-8(R1)
      L.D F10,-16(R1)
      L.D F14,-24(R1)
      ADD.D F4,F0,F2
      ADD.D F8,F6,F2
      ADD.D F12,F10,F2
      ADD.D F16,F14,F2
      S.D F4,0(R1)
      S.D F8,-8(R1)
      DADDUI R1,R1,#-32
      S.D F12,16(R1)
      BNE R1,R2,Loop
      S.D F16,8(R1) ;8-32 =-24

## static branch prediction
* (重要) Delayed Branch: 強制執行 branch 指令的下一條指令，以填補 branch 指令決定是否跳轉導致 stall 的空缺
* 但通常這樣做的效率不高，因此通常會採用 branch prediction 技術
* 在程式的編譯階段，透過編譯器事先預測 Branch 指令的結果
* 分成兩種方法:
* Always Predict Taken
* 每次都猜測 branch 指令會跳轉 (taken)
* 性能因程式有很大的差異
* Based on profile
* 根據上一次執行同樣程式的結果，來針對每個 branch 指令，決定它要不要跳轉
* 因為大部分的 branch 指令都會偏向其中一邊 (一直跳轉或一直不跳轉)，故這種方法的表現較好

## Dynamic Hardware Prediction (Hardware-Based Speculation)
* 透過硬體協助預測 Branch 指令的結果
* 相較於 static 的 Prediction
* 預測時能獲得的資訊量更多、更靈活、更彈性
* 能做到 precise exception，在發生 exception 時能夠完全還原狀態
* 缺點: 增加複雜性跟成本

### Branch-Prediction Buffers
* 透過一個小型的記憶體來紀錄，過去的每一條 Branch 指令最近跳 or 不跳
* 在程式執行的過程中不斷動態更新
* 又可以細分成:
* 1-Bit Prediction: 只用一個 bit 紀錄是否跳轉。若發現預測錯誤則直接將 bit 反轉
* 2-Bit Prediction: 用了兩個 bit 紀錄是否跳轉，以抵抗偶爾改變行為的情況。若發現連續預測錯誤兩次才將 bit 反轉
* 通常在 Instruction Decode 階段觸發

### Branch Target Buffers
* 透過一個小型的記憶體來預測 Branch 指令應該跳到哪裡 (存的是指令 address)
* 若發現某條指令的位址被紀錄在 Branch Target Buffers 中，代表這條指令是 Branch 指令
* -> 直接使用其紀錄的指令 address 決定下一條要的指令
* 通常在 Instruction Fetch 階段就會觸發，相較於 Branch-Prediction Buffers 省了一個 cycle (更快)

進階優化:
Branch Target Buffers 除了儲存指令 address 外，甚至還可以儲存指令本身，這樣可減少載入指令的時間，進一步加速
Branch folding: 省下那些必定跳轉的 Branch 指令所需消耗的 cycle 數。Branch Target Buffers 可以用來實做這個技巧

### Correlating Branch Predictors
* 某個 branch 是否跳轉，可能不只跟自己過去的結果 (Local) 有關，而是受到其他 branch 影響 (Global)
* 在 Correlating Branch Predictors 中，Predictors 記錄了最近的幾個 branch 是否跳轉
* (重要) 目的是讓程式紀錄 "在當前的 global history 及自己的 local history 下，這個 branch 通常會不會跳轉"
* (m,n) Predictor 指的是
* 考量最近 m 次 branch 的歷史行為 (Global 資訊)
* 針對每個 branch 的歷史行爲，使用 n 個 bit 紀錄之
* 故一個 (m,n) Predictor 的 entry 總共會消耗 $2^m * n$ bits

### Tournament Predictors
* Local Predictor 著重在某條 branch 過去的行為
* Global Predictor 著重在所有 branch 過去幾次的行為
* 兩個 Predictor 在不同的使用場景下各有優劣。故 Tournament Predictors 透過 Selector，讓兩個 Predictor 互相競爭。並根據過去經驗，來決定要相信哪個 Predictor

* Predictor 1 跟 Predictor 2 分別代表 Local Predictor 以及 Global Predictor

## 其他 Prediction
* Value Prediction: 預測指令產生的值
* Address Aliasing Prediction: 預測 load+load、load+store 會不會用到同一個 memory address

## Dynamic Scheduling --- Tomasulo’s Approach (必考)
* 透過硬體動態改變指令執行順序
* (重要) 優點:
* 透過 Register renaming 徹底解決 WAW and WAR hazards，並最小化 RAW hazard
* 分散式的處理 hazard detection 邏輯

### Register renaming
* 將那些牽涉到 WAW 跟 WAR hazards 的 register 重新命名成 reservation station (負責暫存等待資料之指令的結構)
* (重要) 這樣一來，寫入的 target 就不再是 register，而是隔離開來的 reservation station，也就避免了 WAW 跟 WAR hazards
* reservation station 會即時關注 Common Data Bus (CDB)，一旦在等的值被計算出來 (來自其他指令)，就可以開始執行
* (重要) 這樣一來，不需要等待 write back，可以提前開始做，也就盡可能最小化 RAW hazards
* 通常 reservation stations 的數量會多於 register 的數量，以增加靈活性

### (重要) 計算範例 1
給定以下指令，分別列出當第一條指令執行完畢並完成 write back 時，instructions、reservation station 跟 register 的 status
1. L.D F6,34(R2)
2. L.D F2,45(R3)
3. MUL.D F0,F2,F4
4. SUB.D F8,F2,F6
5. DIV.D F10,F0,F6
6. ADD.D F6,F8,F2

假設有 reservation station 種類為兩個 Load、三個 Add、兩個 Mul

instructions status
* 繪製 instructions status 表格時，column 分別為:
* Instruction: 依序寫出題目給定的指令
* Issue: 是否已分配給 reservation station 準備執行
* Execute: 執行狀態
* Write result: 指令的執行結果是否已完成 write back
* 一般來說，所有指令皆被 Issue
* 第一條指令執行完畢 -> 目前 Execute 到第二條指令
* 第一條指令執行完畢並完成 write back -> 目前只有第一條指令已經成功 write back

reservation station
* 繪製 reservation station 表格時，column 分別為:
* Name: 題目給定的 reservation entries 種類跟數目
* Busy 表示這個 reservation station 是否佔用中
* Op: 表示指令類型
* ADD 跟 SUB 指令都會被分配到 Add 類型的 reservation station
* MUL 跟 DIV 指令都會被分配到 Mult 類型的 reservation station
* $V_j$: 負責紀錄已計算完成的指令 oprand
* $V_k$: 負責紀錄已計算完成的指令 oprand
* $Q_j$: 負責紀錄還未計算完成的指令 oprand
* $Q_k$: 負責紀錄還未計算完成的指令 oprand
* A: 負責紀錄這條指令中，跟 memory address 相關的資訊
* 由於第一條指令已執行完畢，故釋放 Load1，Busy 為 no
* 第二條指令佔用 Load 2。column A 填入 Load 的目標 address
* 在安排 Add1 跟 Add2 時，需遵守 "Add2 的指令依賴 Add1 的執行結果" 原則，故 Add1 放的是 SUB 指令，Add2 放的是 ADD 指令
* SUB 所需的第一個 oprand F2 需要等待 Load2，故將 Load2 放在 Qj 中
* SUB 所需的第二個 oprand F6 已載入完成，故將成功載入的 Mem[34+Regs[R2]] 放在 Vk 中
* 其他同理
* 在安排 Mul1 跟 Mul2 時，需遵守 "Mul2 的指令依賴 Mul1 的執行結果" 原則，故 Mul1 放的是 SUB 指令，Mul2 放的是 DIV 指令

register status
* $Q_i$ 代表這個 register 的最新值將會由哪個 reservation station 提供

### 計算範例 2
給定以下指令，分別列出當第五條指令執行完畢並準備 write back 時，instructions、reservation station 跟 register 的 status
1. L.D F6,34(R2)
2. L.D F2,45(R3)
3. MUL.D F0,F2,F4
4. SUB.D F8,F2,F6
5. DIV.D F10,F0,F6
6. ADD.D F6,F8,F2

instructions status

reservation station

register status

## Instruction Commit
* (重要) 將原有架構中，"execution" 及 "commit" 分成兩個不同的 stage
* execution: 計算及執行指令，可以根據 scheduling 演算法來任意調整指令的執行順序 (可亂序)。但由於 branch 跟 exception 的可能性，執行完畢不代表會被採納
* commit: 做最後的驗證，確定採納並提交這條指令。需按照 scheduling 前的指令執行順序進行 commit (不可亂序)

### Four Pipeline Stages
* Issue Stage: 將指令從 Instruction queue，送入 pipeline
* Execute Stage: 當指令所需參數皆準備好時，執行之
* Write result: 將結果寫進 common Data Bus (CDB)，並傳遞至 ROB 中暫存
* ROB 是一塊硬體記憶單元，目的是儲存 Commit 前的執行結果。才能在 Dynamic Scheduling 的前提下，做出 branch 指令猜錯的 rollback、exception 的精確處理
* Commit: 確定採納並提交這條指令的執行結果，並在此步更新 register

## multiple issue
* 讓 CPU 在 一個 clock cycle 内 issue 多個指令

### VLIW
* 為一種 multiple issue 架構
* 與一般的處理器架構不同的是，VLIW 架構擁有五個單元
* Integer Unit
* FP Unit 1
* FP Unit 2
* Memory Unit 1
* Memory Unit 2
* 這些單元可以在同一個 clock cycle 中執行不同的指令
* 將多條指令綁定成一個 VLIW 指令。並搭配 static scheduling，在不違背指令間依賴關係的情況下，讓這些單元盡量保持忙碌
* 例如一條 VLIW 指令編碼包含: `[ Integer ADD ] [ FP MUL ] [ FP ADD ] [ Load A ] [ Store B ]`
*　通常會配合 Loop unrolling 的技巧
*　缺點
*　code size 會大幅增加。VLIW 指令中沒用到的欄位，經常會浪費指令編碼的空間
*　程式碼相容性低
*　解法: 透過 object-code translation 轉換成能相容的指令等

## Return Address Predictors
* 針對 indirect jumps (branch 指令跳躍的目的地不一樣) 的優化技巧
* 由於大部分的 indirect jumps 都來自函式 return (從當前函式跳回上一層函式)，因此特別設計一個小的 Return Address Stack
* 每當呼叫函式時，把 return address push 進去
* 每當 return 時，pop 一個 address 出來，這樣便不需實際查詢記憶體來得知要跳回哪個 address

## Window
* Instruction Window: CPU 能看見的、尚未 Issue 之指令的集合
* CPU 在 Issue 指令前，需要檢查 Window 中的所有指令間的相依性關係 (如 RWX 等等)
* 因此 Wondow 不能太大
* 通常會搭配特殊硬體快速檢查
* Window size 越大，CPU 就越有能力妥善處理 Issue 指令的任務，每個 Clock cycle 能 Issue 的指令數量也會越多

## Thread Level Parallelism
* 每個 Thread 都有自己的指令執行順序
* 不同的 Thread 部分重疊執行的能力稱為 Thread Level Parallelism(TLP)
* 比 Instruction Level Parallelism(ILP) 高階

### (重要) Mutlithreading
* Mutlithreading 是一種實現 TLP 的技術，可以細分為
* Fine-Grained Mutlithreading: 用 round-robin 的方式，每個 clock cycle 都切換一個新的且不處於 stall 狀態的 thread 來執行
* Coarse-Grained Mutlithreading: 只有在當前 thread 處於遇到需要長時間 stall 的情況時，才切換新的 thread 來執行
* Simultaneous Multithreading (SMT): 同時執行多個 thread 的指令。若有過多 thread，則優先執行 preferred thread。可以同時利用 ILP 跟 TLP
* 為了保留多個 context (執行狀態)，需要更大的 register file
* scheduling 具挑戰性
* 會導致 Cache 與 TLB 衝突

## 是非題與觀念解釋
* (X) 若 CPU 擁有較低的 CPI 或較高的 clock rate，其 performance 一定會比較好
* CPU 的 performance 還可能受到 ILP 等的影響
* (X) 更複雜的 branch predictor 總是比簡單的設計來的好
* branch predictor 與 workload 類型高度相關。若 workload 非常簡單，較簡單的設計可能會表現的更好

# 第四章 Data-Level Parallelism in Vector, SIMD, and GPU Architectures
為了做到 Data-Level Parallelism，可以採用以下方法:
* Vector: 專門設計來讓 CPU 一次操作整個 vector 的技術
* 可以彈性的決定一次要操作多少元素數量
* 除了進行 Vector 運算，本就支援 scalar (單一資料值) 運算
* 不支援 multithreading
* mask register 是指令集架構的一部份
* SIMD extensions: SIMD 指令集，也是運行在 CPU 上
* 與 Vector 的不同之處:
* SIMD 直接在指令中指定一次要操作的元素數量，較簡單暴力但缺乏彈性
* (重要) SIMD 可大幅度加速跟矩陣相關的運算
* SIMD 非常省電 (相較於 MIMD 而言)
* Graphics Processor Units (GPUs): 與 CPU 不同的另外硬體結構。
* 與 Vector 的不同之處:
* 相較於 Vector，GPU 完全不處理 scalar (單一資料值) 運算
* 使用 multithreading 技術
* 全由硬體決定 mask register 如何使用，軟體層面看不見也無法控制

## Vector (以 VMIPS Architecture 為例)
* 與一般的 MIPS 處理器架構不同的是，多了 "Vector register" 的部分 (但仍保留原本就有，負責儲存單一值的 scalar register)
* 透過 Vector register，便能實現一條指令處理多個資料，不需要像傳統 MIPS 一樣透過迴圈不斷循環

### Vector 執行時間計算
* Convey: 一組 (一或多個) 可以被一起執行的 vector instruction；無 structual hazard 的指令可以被分成同一個 Convey
* Chime: 執行一個 Convey 所需的時間。有幾個 Convey 就要花幾個 Chime 的時間
* 此外，還有 Chaining 技巧，當 一個 Convey 中的 Vector instruction 間出現 dependency 時，允許在個別元素結果可用時立即繼續進行下個 instruction

#### 計算範例

LV V1,Rx
MULVS.D V2,V1,F0
LV V3,Ry
ADDVV.D V4,V2,V3
SV Ry,V4

* convey 1: LV 指令跟 MULVS.D 指令
* convey 2: LV 指令跟 ADDVV.D 指令
* convey 3: SV

假設本題的 SIMD vector 有 64 個空間，則總耗時為 64 * 3 = 192

### Vector 架構優化方法
* Multiple Lanes: 透過硬體實現多通道 (運算線路)，以支援 Vector 平行運算
* 類似的，Memory 也可透過硬體實現多通道，以支援 Vector 的 load 跟 store 指令
* Vector Length Register: 透過額外的 register，動態決定一次要處理的向量長度
* Vector Mask Registers: 透過遮罩提供了 "只對部分元素運算" 的功能

### Stride
* Stride 指的是連續存取記憶體時，資料間的記憶體間隔
* 對於 Vector 架構來說，stride=1 時效率較高

## Graphical Processing Units
* 專為圖形處理設計，知名架構為 Nvidia 推出的 Fermi Architecture
* 在電腦架構中，CPU 仍然是 host，GPU 僅做為 device 存在
* (重要) 因此，GPU 通常是 heterogeneous(異質) execution model 的一部分，搭配 CPU 共同工作，非 homogeneous(同質)
* 可以利用 CUDA C/C++ 程式控制 GPU
* 是 Single Instruction Multiple Thread 架構
* 在 GPU 中，一個 Thread 負責處理一個元素的運算 (如 a[i] * b[j])
* (重要) GPU 硬體只負責管理 Thread，不涉及作業系統及應用程式層面

* GPU 的最小平行處理單位為 CUDA thread
* GPU 中有多個 SIMD processor
* 每個 SIMD processor 都可以使用 SIMD 指令一次處理多個 thread，這些一次處理的 thread 被稱作一個 warp
* SIMD processor 一次可以處理多少 thread，就有幾條 lane (運算線路) 連接之
* 一個 Block 中有多個 Thread
* 一個 Grid 中有多個 Block

### 範例
使用 GPU 進行兩個長度為 8192 的向量相乘操作
條件: 在 GPU 中，一個 Block 有 512 個 Thread、一個 GPU 中的 SIMD 指令一次可以處理 32 個元素

一個 Grid 將負責所有 8192 個元素相乘操作
由於一個 Block 有 512 個 Thread，故一個 Block 將負責 512 個元素相乘操作
由於一個 GPU 中的 SIMD 指令一次可以處理 32 個元素，故 SIMD processor 一次可以處理 32 個 Thread

### NVIDIA GPU Memory Structures
* NVIDIA GPU 的 memory 分成三種:
* Thread Private memory: 每個 thread 獨有的 memory
* local memory: 每個 block 獨有，block 間的 thread 共享的 memory
* GPU memory: 全 GPU 共享的 memory

## Loop-Level Parallelism
*　一個 Loop 是否能平行化，Loop 操作元素間是否存在 dependency 是關鍵
* 可以暴力模擬每一輪，以觀察是否存在 dependency
* 也可以採用以下有限制的快速判定法:
* 假設 Load from 陣列 index c x i + d
* 假設 Store from 陣列 index a x i + b
* 若 (d-b) % GCD(c, a) !=0，則 dependency 保證不存在 (但反之不一定)

## 是非題與觀念解釋
* (X) 只要使用相同的 ISA，就能輕鬆預測 performance
* performance 跟許多其他參數細節有關 (如 cache size 等)