---
# System prepended metadata

title: 計算機組織與結構 L8 多重處理器
tags: [計算機組織與結構, L8, 多重處理器]

---

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

## Multiprocessor 基本概念

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

- 一顆 IC 中，
    - 放 **1** 顆 Core 的
        - 其 Processor 叫 **Multiprocessor**
        - 由 **Multiprocessor** 組成的電腦有**多顆 Processor**，即此電腦為**多顆單核的 Processor** 組成的
        - 後面在討論的都是這個
        
        ![image](https://hackmd.io/_uploads/rky3MVF9a.png =20%x)
    
    
    - 放**多**顆 Core 的
        - 其 Processor 叫 **Chip Multicore microProcessors (CMPs)**
        - 由 **CMPs** 組成的電腦**只有一顆 Processor**，即此電腦為**一顆多核的 Processor** 組成的
        ![image](https://hackmd.io/_uploads/HJ-ym4F9T.png =20%x)

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

    ![image](https://hackmd.io/_uploads/H1TUQVKca.png =70%x)
    
- **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**
        ![image](https://hackmd.io/_uploads/HkvoGrY5T.png =60%x)

    
    - **Nonuniform Memory Access Multiprocessors (NUMA) :** 
        - 使用 **Distributed Shared Memory**
        - 邏輯上一個 Memory，實際上**多**個 Memory
        - 用 **Network** 連接 Processor
        - Network 的通訊規範較寬鬆，NUMA 可以使用不一樣的處理器( **Heterogeneous Multiprocessor** )
        - Processors 分為 Local Memory 和 Remote Memory，因此，存取的**時間不相同**
        ![image](https://hackmd.io/_uploads/B1TpMBF56.png =40%x)

    </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**。利用**命令**交換資料
    - **優點**
        - 硬體設計簡單
    
    - **缺點**
        - 訊息傳送緩慢
        
    ![image](https://hackmd.io/_uploads/SyJ_gS99T.png =70%x)


## 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>
    
    > ![image](https://hackmd.io/_uploads/r1Q6QH55T.png =80%x)
    > 假設:
    > - 一行是一個 Instruction Package
    > - 一個 Instruction Package 最多可裝 4 個 Instruction
    > - Short Stall 定義為停 1 個指令，Long Stall 定義為停 1 個以上的指令
    > ![image](https://hackmd.io/_uploads/HygF4H5q6.png =80%x)

## 平行電腦的分類

- **Flynn's Taxonomy of Parallel Computers :**
    - **SISD :**
        - Single Instruction, Single Data Stream
        - 一個指令，同時間處理一筆資料
        - 如傳統個人電腦
        - ![image](https://hackmd.io/_uploads/rk77LH956.png =40%x)
    - **SIMD :**
        - Single Instruction, Multiple Data Streams
        - 一個指令，同時間處理不同資料
        - 適合處理向量資料，執行向量指令，純量運算較差
        - ![image](https://hackmd.io/_uploads/HJElwr5cp.png =40%x)
        
        > **Vector Processors :** 把 ALU 管線化
        > ![image](https://hackmd.io/_uploads/SkIy_S55a.png =30%x)

    - **MISD :**
        - Multiple Instructions, Single Data Stream (no such machine)
        - 單一資料被多個指令同時處理 (有 Data Race 問題)
        - 如果有，也只是解密用
        - ![image](https://hackmd.io/_uploads/SJuwdH95a.png =40%x)

    - **MIMD :**
        - Multiple Instructions, Multiple Data Streams
        - 多筆不同資料同時被不同指令處理
        - 是標準平行電腦
        - ![image](https://hackmd.io/_uploads/HkqlYHq9T.png =40%x)

## 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**
            - ![image](https://hackmd.io/_uploads/r1U5e8qqp.png)
            - **優點 : 成本低**
            - **缺點 : 沒有容錯能力、傳輸效能差**

        - **Fully**
            - ![image](https://hackmd.io/_uploads/SkcjlLqqT.png)
            - **優點 : 傳速快、容錯能力強**
            - **缺點 : 成本高、擴充性差**
        </br></br>
        > 以下假設一條 Link 可傳 1B 資料量
        
        - **Ring**
            - ![image](https://hackmd.io/_uploads/rJT3x85qa.png)
            - 評估 : 
                - Network Bandwidth : 4B
                - Diameter : 2
                - Bisection Bandwidth : 2B
                - Noded Degree : 2

        - **2D Mesh**
            - ![image](https://hackmd.io/_uploads/rkERlI5qp.png)
            - 評估 : 
                - Network Bandwidth : 32B
                - Diameter : 4
                - Bisection Bandwidth : 8B
                - Noded Degree : 4

        - **N Cube**
            - ![image](https://hackmd.io/_uploads/HkUe-L956.png)
            - 評估 : 
                - 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 :**
            - ![image](https://hackmd.io/_uploads/SJcgS89qa.png =40%x)

        - **Ω Network (= Omega Network) :**
            - ![image](https://hackmd.io/_uploads/B1DzrIccp.png =40%x)
