一、緒論
1.1 基本概念
- 加速比：表示加速效果，單個處理器運行花費時間 / P個處理器運行花費時間；\(S=\frac{T(1)}{T(p)}\)
- 效率：\(E = \frac{S}{p} = \frac{T(1)}{T(p)\times p}\)
- 開銷：\(C=T(p)\times p\)
- 可擴展性：處理器數目增多時并行程式的行為；
- 計算通信比：計算花費時間 / 處理器訊息通信花費時間；
- 計算：在1個時間單位內，每個PE（處理單元）能完成2個數相加，并在本地記憶體保存計算結果；
- 通信：在3個單位時間內，一個PE能夠把資料從自己的本地記憶體發送到另一個PE的本地記憶體；
- 輸入和輸出：程式開始時，整個輸入陣列A保存在0號處理單元PE0，程式結束時，計算結果應匯聚到PE0；
- 同步：所有PE同時進行計算、通信，或處于閑置狀態；
1.2 求和案例
1.2.1 分配流程
PE = 1：即為串行，
PE = 2：PE#0分1半任務給PE#1，分別計算，PE#1將求和后資料匯聚到PE#0，
PE = 4：
1.2.2 分發時間計算
以PE = 2為例
- 最初PE#0存盤全部資料；
- PE#0發送一般資料給PE#1，花費3個單位時間；（自己規定的，見1.2.4）
- 每個處理單元將資料相加，花費511個單元時間；（因為每個處理器分別有511個資料）
- PE#1求和后資料回傳給PE#1，花費3個單元時間；
- PE#0把2部分資料相加，花費1個時間單元；
共計 3 + 511 + 3 + 1 個時間單元
通用運算式
使用\(p=2^{q}\)個處理單元，以及\(n=2^{k}\)個輸入整數
- 資料分發次數：\(3 \times q\)
- 本地求和：\(\frac{n}{p} -1 = 2^{k-q}-1\)
- 收集中間資料：\(3 \times q\)
- 中間結果求和：：\(q\)
則共 \(T(p,n)=T(2^{q},2^{k})=3q+2^{k-q}-1+3q+q=2^{k-q}-1+7q\)
1.2.3 擴展性分析
強擴展性分析：改變處理器的數量，并行計算時間、加速比、開銷和效率變化規律；
弱擴展性分析：改變處理器的數量，同時改變資料量，并行計算時間、加速比、開銷和效率變化規律；
上述演算法不是強擴展性，是弱擴展性，
1.2.4 一般情形計算
$\alpha $：執行一次單獨的假發操作需要的時長
$\beta $：傳輸一批整數需要的時長；
運行時間：\(T_{\alpha,\beta }(p,n)=T(2^{q},2^{k})=\beta q+\alpha(2^{k-q}-1)+\beta q+\alpha q=2\beta q +\alpha (2^{k-q}-1 + q)\)
加速比：$S_{\alpha ,\beta } (2^{q}, 2^{k})=\frac{T_{\alpha ,\beta }(2^{0}, 2^{k})}{T_{\alpha ,\beta }(2^{q}, 2^{k}) }=\frac{\alpha(2^{k}-1)}{2\beta q + \alpha(2^{k-q}-1+q)} $
通信比：\(\gamma=\frac{\alpha}{\beta}\)
求解最優單元：\(2^{q}={\frac{\gamma\ln2}{2+\gamma}}2^{k}\)
比如，對于\(\gamma=\frac{1}{3}，n=1024\)，加速比最大可求\(p=1000\)
當處理資料規模固定，并行效率和加速比依賴于計算單元個數和計算通信比；
1.3 并行計算基礎
1.3.1 分布式記憶體
特點：每個PE只能訪問自己的本地記憶體，如果跨PE訪問，需要一個顯式的通信步驟，
資料劃分是分布式記憶體系統編程的關鍵，
1.3.2 共享記憶體系統
通過一個共享總線或者縱橫交換機，所有的CPU都能訪問同一塊公共記憶體空間，
- 除了共享主存外，每個核心包含一塊更小的本地記憶體；
- 快取一致性，存盤在本地快取中的值和存盤在共享記憶體中的值保持一致；
1.4 并行程式設計考慮因素
- 劃分：給定的問題劃分為子問題；
- 通信：選定劃分方案決定了行程或縣城之間需要的通信量和通信型別；
- 同步：為了以正確的方式共同運行，執行緒或行程之間可能需要同步操作；
- 負載平衡：多個縣城或多個行程之間的作業量需要平均分配，以平衡他們各自的負載，并最小化空閑時間；
求和案例
1.5 不同層次的并行
- 節點級并行化：需要針對分布式記憶體機器的模型實作演算法，例如MPI(在第9章深入學習）或者UPC++(在第10章深人學習)等，
- 節點內的并行化：通常基于針對共享記憶體系統(多核CPU)的語言，比如C++多執行緒(在第4章深人學習)，或者OpenMP(在第6章深人學習)，
- 加速卡級的并行化：把一部分計算任務分配給加速卡承擔，比如大規模并行GPU等，借助包括CVDA在內的特定語言(將在第7章深入學習)，
參考：《并行程式設計》
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/555489.html
標籤：其他
上一篇：集合體系結構
下一篇：返回列表