# 計算機組織與結構 L8 多重處理器

## Multiprocessor 基本概念

- **Multiprocessor :** 至少有 2 個以上 Processor 的單一電腦，可以針對
- **Sequential** (在 Runtime 無法平行分解指令)的 Software 進行 **JLP** 的改進，將**個別 Program** 分派給多個處理器執行，以獲得**高 Throughput**
- **Concurrent** (在 Runtime 可以平行分解指令)的 Software 進行 **TLP** 的改進，將程式分的**基本的執行單位 Thread** 分派給多個處理器執行，以**加速程式執行**

- 一顆 IC 中，
- 放 **1** 顆 Core 的
- 其 Processor 叫 **Multiprocessor**
- 由 **Multiprocessor** 組成的電腦有**多顆 Processor**，即此電腦為**多顆單核的 Processor** 組成的
- 後面在討論的都是這個


- 放**多**顆 Core 的
- 其 Processor 叫 **Chip Multicore microProcessors (CMPs)**
- 由 **CMPs** 組成的電腦**只有一顆 Processor**，即此電腦為**一顆多核的 Processor** 組成的

</br>

> **Core :** 一個 Core 只能同時進行 **1 個 Thread**，其中，Core 中包含 :
> - **Control Unit (= CU)**
> - **Arithmetic-Logic Unit (= ALU)**
> - **Memory**


- **Multiprocessor** 中的 Processors 要**傳訊息**有兩種**方式**，根據這兩種不同方式分成 :
- **Shared Memory Multiprocessor (SMP)**
- 只需要**一個 OS**
- 利用**共用變數**做資料交換
- 又分為 :
- **Uniform Memory Access Multiprocessor (UMA)**
- **Nonuniform Memory Access Multiprocessor (NUMA)**

- **Message Passing Multiprocessor (MPP)**
- 需要**多個 OS**
- 利用**命令**做資料交換

          send(processor ID, message), receive()

## 撰寫平行程式的挑戰

- **多處理器在要求高效能下，撰寫平行程式的困難 :**
- **Scheduling :**
- 以哪種功能分解好 ?
- **Load Balabce :**
- 處理器執行的資料難易不同，導致時間不均勻

- **Time For Synchornization :**
- 有些工作有因果性，需要某工作做完後才能繼續做，就需要等待 Synchornization 的 Time
- **Overhead of Communication :**
- 交換資料所花的時間

- 因為不是所有工作都可以完全平行化，所以 **Speedup 會被受限**
- 假設 $s$ 是工作中**不可被平行化處理的比例**，則</br></br> $Speedup(P) = \cfrac{EXTime(1)}{EXTime(P)}$ </br></br> $\qquad \qquad \quad \ \leq \cfrac{1}{s + \cfrac{(1-s)}{p}}$ </br></br> $\qquad \qquad \quad \ \leq \cfrac{1}{s}$

- **Scaling up** 有兩種**方法** :
- **Strong Scaling :**
- 利用**提升Multiprocessor，在不改變 Processor 個數和 Problem Size 下** 加速

- $\cfrac{1}{s + \cfrac{(1-s)}{p}}$ **固定**，**受限於 Amdahl's Law**

- **Weak Scaling :**
- 利用**增加 Problem Size，使可平行化比例增加** 加速

- $\cfrac{1}{s + \cfrac{(1-s)}{p}}$ **會變**，**不受限於 Amdahl's Law**

> **Strong Scaling 比 Weak Scaling 難很多**

## Shared Memory Multiprocessor (SMP)

- **Shared Memory Multiprocessor (SMP) :** 利用**共用變數**和 **Load、Store** 指令，讓所有 Processors 都可以存取 Memory 中的任何資料
- **Uniform Memory Access Multiprocessors (UMA) :**
- 使用 **Centralized Shared Memory**
- 邏輯上一個 Memory，實際上**一**個 Memory
- 用 **Bus** 連接 Processor
- 需要符合 Bus 的通訊規則，每個處理器都要一模一樣( **Homogeneous Multiprocessor** )
- Processors 存取 Memory 的**時間都相同**
- 又叫 **Symmetric Multiprocessor**

- **Nonuniform Memory Access Multiprocessors (NUMA) :**
- 使用 **Distributed Shared Memory**
- 邏輯上一個 Memory，實際上**多**個 Memory
- 用 **Network** 連接 Processor
- Network 的通訊規範較寬鬆，NUMA 可以使用不一樣的處理器( **Heterogeneous Multiprocessor** )
- Processors 分為 Local Memory 和 Remote Memory，因此，存取的**時間不相同**

</br>

> 因為是使用 Heterogeneous Multiprocessor，**NUMA** 的 **Programming 比較困難**，但 NUMA 的 **Memory 可以比較大**，且在**存取 Local Memory 時花費的 Latency 比較少**

> UMA 和 NUMA 因為是**Shared Memory**，所以都有兩種問題
> - **Synchornization (= Data Race = Critical Section)**
> - 用 **Lock** 解決 (一有 Processor 要寫，所有 Process 就 Lock)
>
> - **Cache Coherency**
> - **UMA** 用 **Snooping Protocol** 解決
> - **NUMA** 用 **Directory** 解決

## Message Passing Multiprocessor (MPP)

- **Message Passing Multiprocessor (MPP) :** 每個 Processor 有自己的 **Private Address Space**。利用**命令**交換資料
- **優點**
- 硬體設計簡單

- **缺點**
- 訊息傳送緩慢


## Snooping 解決 SMP 的 Cache Coherency

- **Exclusive Access :** 一個 Processor 寫入時不允許另一個 Processor 寫或讀

- **Snooping** 分為兩種**型態** :
- **Write-Invalidate :** 在**改變自己的 Cache 之前**，將所有拷貝資料**改為無效**，等到其他 Processor 需要資料時再更新資料
- **Write-Update (= Write-Broadcast) :** 用 **Bus 廣播此資料最新的值**，然後**所有的拷貝都更新成此值**
</br>
> **Write 家族**
> - **Write Hit 時**
> - **Write Through :** CPU 寫，Cache 和 Memory 一起改
> - **Write Back :** 只改 Cache，等到要被換掉才寫入 Memory
>
> - **Write Miss 時**
> - **Write Allocate :** 直接到 Memory 搬整個 Block 到 Cache Write
> - **Write Around :** CPU 繞過 Cache，直接改 Memory
>
> - **Snooping 時**
> - **Write Invalidate :** 在改變自己的 Cache 之前，將所有拷貝資料改為無效，等到其他 Processor 需要資料時再更新資料
> - **Write Around :** 用 Bus 廣播此資料最新的值，然後所有的拷貝都更新成此值

## Hardware Multithreading (Software Concurrent)

- 達成 Hardware Multithreading 的三種**方法** :
- **Fine-grained Multithreading (= Fine MT) :**
- 利用 **Round Robin 切 Thread** 跳過有 Stall 的 Thread
- **優點 :**
- 可以**藏 Long Stall 和 Short Stall 造成的 Throughput losses**
- **缺點 :**
- **單個 Thread 的執行時間被拖太長**

- **Coarse-grained Multithreading (= Coarse MT) :**
- 遇到 **Short Stall 停下來等**，遇到 **Long Stall 才切 Thread**
- **優點 :**
- **單個 Thread 時間不會被拉太長**
- **缺點 :**
- **會因為 **Pipeline Start-up Cost** 和 **Short Stall** 而被拖延時間

- **Simultaneous Multithreading (= SMT) :**
- **Hardware Multithreading 的變化**
- **有用到 Superscalar**
- **符合 ILP 和 TLP**
- **優點 :**
- 可以**藏 Long Stall 和 Short Stall 造成的 Throughput losses**
- **缺點 :**
- **單個 Thread 的執行時間被拖太長**
</br>

> 
> 假設:
> - 一行是一個 Instruction Package
> - 一個 Instruction Package 最多可裝 4 個 Instruction
> - Short Stall 定義為停 1 個指令，Long Stall 定義為停 1 個以上的指令
> 

## 平行電腦的分類

- **Flynn's Taxonomy of Parallel Computers :**
- **SISD :**
- Single Instruction, Single Data Stream
- 一個指令，同時間處理一筆資料
- 如傳統個人電腦
- 
- **SIMD :**
- Single Instruction, Multiple Data Streams
- 一個指令，同時間處理不同資料
- 適合處理向量資料，執行向量指令，純量運算較差
- 

> **Vector Processors :** 把 ALU 管線化
> 

- **MISD :**
- Multiple Instructions, Single Data Stream (no such machine)
- 單一資料被多個指令同時處理 (有 Data Race 問題)
- 如果有，也只是解密用
- 

- **MIMD :**
- Multiple Instructions, Multiple Data Streams
- 多筆不同資料同時被不同指令處理
- 是標準平行電腦
- 

## Graphics Processing Units (GPUs)

- **GPUs vs CPUs :**
- **GPUs 是用來支援 CPUs 的**
- **程式語言不一樣**
- **GPUs : High-level Application Programming Interfaces (APIs)** </br>eg. OpenGL、DirectX、C for Graphics (Cg)、High Level Shader Language (HLSL)
- **指令功能不一樣**
- **GPUs : 3D Geometry Primitives**
- **Data Type 不一樣**
- **GPUs :**
- **Vertices :** (x, y, z, w) 座標 (8*4 bits)
- **Pixels :** (red, green, blue, alpha) (8*4 bits)
- **Working Set 比 CPUs 大**
- **只需要 Spatial Locality**
- **GPUs 無法使用 Multilevel Cache，需要仰賴 TLP 掩飾到 Memory 的 Latency**
- **GPUs 的 Memory 重視 Bandwidth**
- **GPUs 不提供雙精度浮點數的運算**

> **Working Set :** 某時間內要用的指令或資料

> 以前的 GPUs 用異質性處理器居多，但現在用同質性居多，因為程式比較好上手，會比較多人來學，但缺點是 Performance 會變差

> 以前 GPUs 多用 SIMD，現在 GPUs 重視純量指令，雖然好用，但 Performance 低

- **General Purpose GPUs (= GPGPUs) :**
- 雖然傳統上 GPU 是被設計用來處理和圖形有關的計算，但是，由於現代 GPU 也可以被用來處理通用類型的資料計算，尤其是 SIMD 的應用
- 如 NVIDIA 的 CUDA (Compute Unified Device Architecture)

## Network Topology

- **Network Topology :** 討論處理器之間如何連結
- **Single Stage Network :** 線路開關只需要一次，就至少會有兩個 Processor 連接在一起
- **Linear**
- 
- **優點 : 成本低**
- **缺點 : 沒有容錯能力、傳輸效能差**

- **Fully**
- 
- **優點 : 傳速快、容錯能力強**
- **缺點 : 成本高、擴充性差**
</br></br>
> 以下假設一條 Link 可傳 1B 資料量

- **Ring**
- 
- 評估 :
- Network Bandwidth : 4B
- Diameter : 2
- Bisection Bandwidth : 2B
- Noded Degree : 2

- **2D Mesh**
- 
- 評估 :
- Network Bandwidth : 32B
- Diameter : 4
- Bisection Bandwidth : 8B
- Noded Degree : 4

- **N Cube**
- 
- 評估 :
- Network Bandwidth : 12B
- Diameter : 3
- Bisection Bandwidth : 4B
- Noded Degree : 3

> 評判哪個接法好有四個標準 :
> - 評**傳輸效能 :**
> - **Network Bandwidth :** 一秒可以傳多少資料量
> - **Diameter :** 最長的最短路徑
>
> - 評**容錯能力 :**
> - **Bisection Bandwidth :** 要一切為二兩個相等大小的子集合，要犧牲多少 Bandwidth (越大容錯能力越好)
> - **Noded Degree :** 每個 Node 可以接幾個 link (越大容錯能力越好)

- **Multistage Network :** 線路開關需要多次，才至少會有兩個 Processor 連接在一起
- **Crossbar :**
- 

- **Ω Network (= Omega Network) :**
-