并行計算綜述————第一章 并行計算硬體平台：并行計算機

并行計算綜述

第一章 并行計算硬體平台：并行計算機

Ch1 并行計算與并行計算機結構模型

1.1多核處理器與線程級并行

1.何謂多核處理器？

将功能複雜的單一核處理器劃分為若幹個功能相對簡單的多個處理器核心。這些多處理器集中在一塊晶片上。最初稱為單晶片多處理器CMP，Intel公司将其商用名定為多核處理器

2.多核處理器的意義：

• 解決單處理器瓶頸：密集半導體內建，功耗劇增。設計指令級并行體系結構來利用半導體資源，但軟體與硬體設計複雜
• 具有自己的優勢：CMP設計驗證周期短、開發風險成本低，相對較低的主頻功耗也相對較低、單處理器程式移植easy，通過布局可以改善多處理器核心之前延遲和帶寬

3.微處理器中的并行方式

• ILP：指令級并行。單處理器同一時候運作多條指令，包含亂序運作、分支預測、指令多發射、硬體預取等技術
• TLP：線程級并行，多處理器多線程運作
• 多任務OS：多程序多線程分時間片輪轉或搶占式，OS管理
• SMT：同一時候多線程技術，超标量與多線程的結合，同一時候發射多個線程中的多條不相關指令
• CMP：單晶片多處理器
• 虛拟計算技術：異構平台，剝離指令集結構和處理器依賴關系（運作時虛拟化JVM、系統虛拟化）
• Intel超線程技術：單核心模拟雙核心環境運作多線程，是一種SMT

1.2 并行計算機體系結構

1.并行計算機結構模型

（1）結構類型

• SISD：單指令流單資料流計算機（馮諾依曼機）
• SIMD：單指令流多資料流計算機
• MISD：多指令流單資料流計算機
• MIMD：多指令流多資料流計算機

（2）幾種MIMD

• PVP并行向量處理機：多VP（向量處理器）通過交叉開關和多個SM（共享記憶體）相連
• SMP對稱多處理機：多P/C（商品微處理器）通過交叉開關/總線和多個SM（共享記憶體）相連
• MPP大規模并行處理機：處理節點有商品微處理器+LM（分布式本地記憶體）。節點間通過高帶寬低延遲定制網絡互聯，異步MIMD，多個程序有自己的位址空間，通過消息傳遞機制通信
• COW工作站機群：節點是完整作業系統的工作站，且有磁盤
• DSM分布共享存儲處理機：快速緩存檔案夾DIR確定緩存一緻性。将實體分布式LM組成邏輯共享SM進而提供統一位址的程式設計空間

注：對稱指全部處理器都能同等地訪問I/O非常相同的運作程式（如OS和I/O服務程式）。而非對稱主從式是僅有主處理器運作OS和控制訪問I/O并監控從處理器運作

2.并行計算機訪存模型

• UMA（Uniform Memory Access）均勻存儲訪問：實體存儲器被全部處理器均勻共享，全部處理器對全部SM訪存時間相同，每台處理器可帶有快速私有緩存，外圍裝置共享。
• NUMA非均勻存儲訪問：共享的SM是由實體分布式的LM邏輯構成，處理器訪存時間不一樣，訪問LM或CSM（群内共享存儲器）記憶體儲器比訪問GSM（群間共享存儲器）快
• COMA（Cache-Only MA）全快速緩存存儲訪問：NUMA的特例、全快速緩存實作
• CC-NUMA（Coherent-Cache NUMA）快速緩存一緻性NUMA：NUMA＋快速緩存一緻性協定
• NORMA（No-Remote MA）非遠端存儲訪問：無SM，全部LM私有。通過消息傳遞通信

3.Cache一緻性協定

• 監聽總線協定：總線連接配接通信。寫無效和寫更新政策
• 基于檔案夾的協定：檔案夾記錄共享資料緩存狀态，讀缺失時檢視檔案夾D，寫更新時通知檔案夾D

4.其它并行計算概念

衡量并行計算機性能機關：

• PFLOPS：每秒1千萬億 (=10^15) 次的浮點運算
• TFLOPS：每秒1萬億 (=10^12) 次的浮點運算
• GFLOPS：每秒10億 (=10^9) 次的浮點運算

TOP500前500名超級計算機排名名額(GFLOPS)：

• Rmax：Maximal LINPACK(Linear system package) performance achieved
• Rpeak：Theoretical peak performance

Ch2 并行計算機系統互連與基本通信操作

2.1 并行計算機互連網絡

互連網絡是并行計算機系統中各處理器與記憶體子產品等之間傳輸的機制

1.靜态互連

處理單元間有固定連接配接的網絡。程式運作期間這樣的點到點的連接配接不變

• 一維線性陣列LA/LC：二鄰近串聯
• 二維網孔MC：四鄰近連接配接（Illiac連接配接、2D圍繞）
• 樹連接配接TC：二叉樹、星型網絡、二叉胖樹（節點通路向根節點方向逐漸變寬，解決通信瓶頸）
• 超立方HC：3立方、4立方
• 立方環：3立方頂點用環取代

2.動态互連

交換開關構成的，可按應用程式要求動态改變連接配接組态

• 總線：連接配接處理器、存儲子產品、I/O外圍裝置等的一組導線和插座，分時工作、多請求總線仲裁，多總線（本地、存儲、資料、系統）和多層總線（闆級、底闆級、I/O級）
• 交叉開關：高帶寬的開關控制的專用連接配接通路網絡。NxN的開關網絡同一時候僅僅能接通N對源目的通信
• 多級網際網路絡MIN：每一級用多個開關單元，各級之間有固定的級聯拓撲

3.标準網絡互連

• FDDI光纖分布式資料接口
• 快速以太網
• Myrinet：商用千兆位包開關網
• InfiniBand：交換式通信結構

2.2-2.5 通信代價公式

1.選路

（1）消息格式

消息是由一些定長的信包組成，信包包含了

• 選路資訊R
• 順序号S
• 多個資料片D

（2）存儲轉發選路SF

SF中信包是基本傳輸機關，中間節點必須收齊信包中全部分片且存儲在緩沖器後才可能傳向下一節點

長度為m的信包，穿越l條鍊路，SF基本通信時間公式：

tcomm(SF)=ts+(mtw+th)l

當中ts是啟動時間，th是節點延遲時間。tw是傳輸每一個位元組的時間（帶寬倒數）

（3）切通選路CT

CT中信包切片傳輸（標頭和資料片），相似流水線

長度為m的信包。穿越l條鍊路。CT基本通信時間公式：

tcomm(CT)=ts+mtw+lth

2.SF一到多點傳播送

（1）一維環

最遠的節點是瓶頸：

tone−to−all(SF)=(ts+mtw)⌈p/2⌉

（2）帶圍繞的Mesh

先完畢行SF圍繞播送，再完畢列的SF圍繞播送（即兩次節點個數為p‾‾√的一維環SF）：

tone−to−all(SF)=2(ts+mtw)⌈p‾‾√/2⌉

（3）超立方

同理帶圍繞的Mesh，可推知：

tone−to−all(SF)=3(ts+mtw)⌈p13/2⌉

3.CT一到多點傳播送

CT通信時間與中繼節點無關。採取先按高維播送，再按中維播送，最後按低維播送：

tone−to−all(CT)=∑i=1log(p)(ts+mtw+th×p/2i)=(ts+mtw)log(p)+th(p−1)

（2）帶圍繞的Mesh

tone−to−all(CT)=(ts+mtw)log(p)+2th(p‾‾√−1)

tone−to−all(CT)=(ts+mtw)log(p)

2.SF多到多點傳播送

p-1次環路傳播：

tall−to−all(SF)=(ts+mtw)(p−1)

先行環路多點傳播，再列環路多點傳播

tall−to−all(SF)=(ts+mtw)(p‾‾√−1)+(ts+mp‾‾√tw)(p‾‾√−1)=2ts(p‾‾√−1)+mtw(p−1)

tall−to−all(SF)=tslog(p)+mtw(p−1)

Ch4 并行計算性能評測

4.1 基本性能名額（見書）

4.2 加速比性能定律

約定：

• p是處理器數
• 問題規模W=程式中串行分量Ws+可并行部分Wh
• f為串行部分比例，f=Ws/W
• S為加速比

1.Amdahl加速定律

固定負載加速比公式：

Slimp→∞S=Ws+WpWs+Wpp=1f+1−fp=1f

若考慮并行額外開銷W0：

Slimp→∞S=Ws+WpWs+Wpp+W0=1f+1−fp+W0W=1f+W0W

2.Gustafson

實際應用中增多了處理器不會固定問題規模，而是保持總時間不變的情況下去增大問題規模：

S=Ws+pWpWs+pWpp=Ws+pWpWs+Wp=f+p(1−f)

S=Ws+pWpWs+pWpp+W0=Ws+pWpWs+Wp+W0=f+p(1−f)1+W0/W

3.Sun&Ni定律

問題規模添加了，對應的存儲容量也要添加p倍，令因子G(p)為存儲容量添加到p倍時工作負載的添加，則有加速比：

S=Ws+G(p)WpWs+G(p)Wpp=f+(1−f)G(p)f+(1−f)G(p)/p

S=Ws+G(p)WpWs+G(p)Wp+W0p=f+(1−f)G(p)f+(1−f)G(p)/p+W0/W