[CS] Parallel Computing
大學修課時的些許知識點
What is Parallel Computing ?
平行運算主要是藉由使用多台電腦或多處理器類型電腦去解決一個問題
並期望透過 n 台電腦同時運算達到比原本一台電腦直接執行快 n 倍的效果
當然這是在理想情況下才能發生，由於下列原因現實狀況難以實現 :
(1) 同步執行當中，並非所有處理器皆在執行狀態
(2) 平行版本之相同目的程式可能會比原循序執行程式多些步驟
(3) 處理器執行期間需花費時間來溝通
(4) 平行程式非完全平行執行，有些步驟須由循序執行
而要如何才能達成超線性 (super-linear) 的加速率呢?
(1) 必須設計個子問題的最佳演算法 (sub-optimal sequential algorithm)
(2) 建設精益的系統架構
(3) 需有額外記憶體空間使用多處理器系統
(4) 具不同解法之演算法 (non-deterministic algorithm)
而在判斷平行處理運行效能是透過兩種運算時間去判斷優劣 :
分別是 communication time 和 computation time :
當 computation time 占比時間越多，代表平行化處理程度越高
How to evaluate the execution time for a parallel program ?
而 execution time 取決於執行最久的 processor 所花費之執行時間
System Classification
Multiprocessor :
多處理器系統 / 平行系統
Multi-computer :
多重電腦系統，由多部電腦組成之電腦，通常指每一處理器均有自己獨立的記憶體，且相互以高速網路進行連接溝通的電腦系統
Shared memory system :
共同合作之 process 以分享記憶體 (shared memory) 的技術來交換資訊
Distributed memory system :
每個處理器皆擁有獨立的記憶體跟當地資料，若可以利用遠端傳輸資料，必須與至少一至多個處理器進行遠端連接
Distributed shared memory system : (驚 !?)
每個 processor 除了物理上已各自獨立的記憶體來儲存 local data 外，
可以透過虛擬定址的方式來達成 shared memory 的技術
Flynn’s classification : (資工所考研出現過)
Flynn 利用 instruction stream 和 data stream 來分類四種類型的電腦
(1) SISD (Single instruction single data stream) :
傳統類型，利用一個指令運算單資料流，ex : 單核心處理電腦
(2) SIMD (Single instruction multiple data stream)
多資料流使用相同指令處理，ex : 陣列處理器 / 圖形處理器
(3) MISD (Multiple instruction single data stream) :
通常出現在不容錯的電腦系統上
(4) MIMD (Multiple instruction single data stream) :
目前最常見之多處理器系統
右下方分別是以 memory 結構 (Distributed / Global)
以及 通信機制 (shared memory / message passing) 來區分
MPI (Message Passing Interface)
由相關 message passing instructions 的 library 定義 message passing 之系統標準，而 MPICH 就是以此標準所實作的一套免費軟體
以下介紹 MPI 常用指令 :
Blocking Message Passing
Non-blocking Message Passing
Others
Broadcast :
向所有與問題相關的 processor 傳送相同訊息
Multicast :
傳送相同訊息到一組 processors ，須等到所有 processors 都完成 broadcast 動作才可以繼續執行 (同步效果)
Scatter :
將訊息分成 n 等分，並將每份資料分別傳送給不同的 processor
(第 i 份，傳給第 i 個 processor)
Gather :
將所有 processors 的資料收集傳回給某個指定的 processor
Reduce :
將所有 processors 的資料收集並做別的數學或邏輯運算，最後將此值傳回給某定的 processor
我們可將這些指令以 group communication functions 以及 send/receive function 來分類 :
Group communication function
MPI_Bcast(), MPI_Alltoall(), MPI_Gather(), MPI_Scatter(), MPI_Reduce()
Send/Receive function
MPI_Send(), MPI_Recv(), MPI_Isend(), MPI_Irecv()
至於彼此間 public variable 和 private variable 區分是透過 rank
在 if(rank == x)中為 private variable
以外為 public variable
Finding prime number using several methods
我們可利用 MPI 這項技術來有效率地尋找質數，提升效率
以下提供幾種常見的方式 :
Single processor
從 2 開始，將 n 個 data 中為質數的 data 刪除，直到處理完 n 個 data，留下的 data 便為質數了
Multiprocessor
將 data 放在 shared memory 中，每個 processor 皆有自己的 index ，彼此之間以 shared memory 之中的 data 來處理，將是自己 index 倍數的 data 刪除
Multi computer
每個 processor 皆擁有自己獨立的 memory，而每個 memory 存放著一部份原有的 data ，每個 processor 接執行尋找質數的動作，最後將每部 processor 執行最終結果彙整給 master processor，便構成解答
Other information
1. Amdahl’s law verse Gustafson’s law ?
Amdahl’s law：
Speedup factor is given by：
(不管有多少個processors，Speedup的最大被限制為1/f)
主要是在表示平行化後效率提升的加速情況
Gustafson’s Law：
主要是在表示增加Problem Size可相對提高性能的加速情況
Wrong Law：Amdahl’s law
原因：問題假設在固定的資料大小或是固定的運算量。如果以更多的CPU 來運算加大資料量的同個問題，那還是可以有提升效能的可能。
2. Types of network graph (16 processors)
Fat tree version
p.s. 若資訊有誤歡迎糾正
