并行計算-2020-復習指南

制作：紀元

本提綱遵循CC-BY-NC-SA協議

(署名-非商業性-相同方式共享)

文章目錄

- 并行計算機系統及其結構模型
- - 存盤墻
  - 互聯網路
  - - 網路性能指標
    - 靜態互連網路
    - 動態互連網路
  - 并行計算機結構
  - - 定義
    - 圖示
  - 并行計算機訪存模型
  - - 概念
    - 小結
- 當代并行計算機系統介紹
- - 共享存盤的對稱多處理機SMP
  - - 結構特性：
    - 問題：
  - 分布存盤的大規模并行處理機 MPP
  - - MPP公共結構
    - MPP設計問題
  - 差別
  - 作業站機群COW
  - - 定義
    - 優勢
- 并行計算性能評測
- - 作業負載
  - 并行執行時間
  - 存盤器性能
  - - 存盤器的層次結構
    - 存盤器帶寬的估算
    - - 公式
      - 例：RISC加法指令帶寬估算
  - 三大定律
  - - 簡稱定義
    - Amdahl定律 - 固定負載的加速公式
    - - 原公式
      - 歸一化的公式
      - 修正的公式
      - 極限情況與條件
      - 出發點
      - 含義
    - Gustafson加速定律
    - - 原公式
      - 歸一化公式
      - 修正的公式
      - 極限情況與條件
      - 出發點
      - 含義
    - Sun和Ni定律 - 存盤受限的加速定律
    - - 原公式
      - 歸一化公式
      - 修正的公式
      - 極限情況與條件
      - 基本思想
- 并行演算法的設計基礎
- - 并行演算法基本概念
  - 并行計算模型基本概念
  - - PRAM(ParallelRandomAccessMachine)模型
    - - 分類
      - 優點
      - 缺點
      - 推廣
    - 異步PRAM模型
    - - 特點
      - 指令型別
    - BSP(BulkSynchronousParallel)模型
    - - 性質和特點
    - logP模型(logPModel)
    - - 引數
- 并行演算法的一般設計策略
- - 串行演算法直接并行化
  - 從問題描述開始設計并行演算法
  - 借用已有演算法求解新問題
- 并行演算法的基本設計技術
- - 劃分求解的基本步驟
  - 均勻劃分技術
  - 對數劃分技術
  - 功能劃分技術
- 并行演算法的一般設計程序
- - PCAM基本步驟
  - 劃分
  - 通信
  - - 通信模式
  - 組合
  - 映射
  - - 基本策略
- 演算法撰寫
- - 矩陣相乘、線性方程組求解(稠密)、快速傅里葉變換

符號釋義

? ? \lfloor \rfloor ??：向下取整數
? ? \lceil \rceil ??：向上取整數

題型設定

選擇 20x2
填空 10x2
簡答 2x10
編程 2*10

并行計算機系統及其結構模型

存盤墻

記憶體墻，指的是記憶體性能嚴重限制CPU性能發揮的現象，

在過去的20多年中，處理器的性能以每年大約55%速度快速提升，而記憶體性能的提升速度則只有每年10%左右，長期累積下來，不均衡的發展速度造成了當前記憶體的存取速度嚴重滯后于處理器的計算速度，記憶體瓶頸導致高性能處理器難以發揮出應有的功效，這對日益增長的高性能計算(High Performance Computing,HPC)形成了極大的制約，事實上，早在1994年就有科學家分析和預測了這一問題，并將這種嚴重阻礙處理器性能發揮的記憶體瓶頸命名為"記憶體墻"(Memorya Wall)，

在這里插入圖片描述

互聯網路

網路性能指標

節點度(Node Degree)：射入或射出一個節點的邊數，在單向網路中，入射和出射邊之和稱為節點度，
網路直徑(Network Diameter)：網路中任何兩個節點之間的最長距離，即最大路徑數，
對剖寬度(Bisection Width) ：對分網路各半所必須移去的最少邊數
對剖帶寬( Bisection Bandwidth):每秒鐘內，在最小的對剖平面上通過所有連線的最大資訊位(或位元組)數
對稱(Symmetry):從任一節點觀看網路都一樣

靜態互連網路

靜態互連網路：處理單元間有著固定連接的一類網路，在程式執行期間，這種點到點的鏈接保持不變；典型的靜態網路有一維線性陣列、二維網孔、樹連接、超立方網路、立方環、洗牌交換網、蝶形網路等，
嵌入(Embedding)：指將網路中的各節點映射到另一個網路中去，
膨脹(Dilation)：系數來描述嵌入的質量，它是指被嵌入網路中的一條鏈路在所要嵌入的網路中對應所需的最大鏈路數，如果該系數為1，則稱為完美嵌入，
- 例如，一個環網可完美嵌入到2-D 環繞網中，同樣，一個超立方網也可以完美嵌入到2-D環繞網中，并非所有網路之間均可實作完美嵌入，
- 一般而言，對于高度為 h 的完全二叉樹，其膨脹系數為 ? h / 2 ? \lceil{h/2}\rceil ?h/2? ，

網路名稱	網路規模	節點度	網路直徑	對剖寬度	對稱	鏈路數
線性陣列	N N N	2 2 2	N ? 1 N-1 N?1	1 1 1	非	N ? 1 N-1 N?1
環形	N N N	2 2 2	N ? 1 ( 單向 ) ? N / 2 ? ( 雙向 ) N-1(單向)\\\lfloor{N}/2\rfloor(雙向) N?1(單向)?N/2?(雙向)	2 2 2	是	N N N
2-D網孔	( N × N ) (\sqrt{N}\times\sqrt{N}) (N ?×N ?)	4 4 4	2 ( N ? 1 ) 2(\sqrt{N}-1) 2(N ??1)	N \sqrt{N} N ?	非	2 ( N ? N ) 2(N-\sqrt{N}) 2(N?N ?)
Illiac網孔	( N × N ) (\sqrt{N}\times\sqrt{N}) (N ?×N ?)	4 4 4	N ? 1 \sqrt{N}-1 N ??1	2 N 2\sqrt{N} 2N ?	非	2 N 2N 2N
2-D環繞	( N × N ) (\sqrt{N}\times\sqrt{N}) (N ?×N ?)	4 4 4	2 ( ? N / 2 ? ) 2(\lfloor\sqrt{N}/2\rfloor) 2(?N ?/2?)	2 N 2\sqrt{N} 2N ?	是	2 N 2N 2N
二叉樹	N N N	3 3 3	2 ? log ? N ? ? 1 2\lceil\log{N}\rceil-1 2?logN??1	1 1 1	非	N ? 1 N-1 N?1
星形	N N N	N ? 1 N-1 N?1	2 2 2	? N / 2 ? \lfloor{N/2}\rfloor ?N/2?	非	N ? 1 N-1 N?1
超立方	N = 2 n N=2^n N=2n	n n n	n n n	N / 2 N/2 N/2	是	n N / 2 nN/2 nN/2
立方環	N = k × 2 k N=k\times2^k N=k×2k	3 3 3	2 k ? 1 + ? k / 2 ? 2k-1+\lfloor{k/2}\rfloor 2k?1+?k/2?	N / ( 2 k ) N/{(2k)} N/(2k)	是	3 N / 2 3N/2 3N/2

在這里插入圖片描述

完美嵌入(膨脹系數=1)

在這里插入圖片描述

不完美嵌入(膨脹系數=2)

在這里插入圖片描述

動態互連網路

動態網路：用交換開關構成的，可按應用程式的要求動態地改變連接組態；典型的動態網路包括總線、交叉開關和多級互連網路等，
總線(Bus)實際上是連接處理器、存盤模塊和Ｉ/Ｏ外圍設備等的一組導線和插座，總線系統用以主設備(如處理器)和從設備(如存盤器)之間的資料傳輸，公用總線以分時作業為基礎，在多個請求情況下，總線的仲裁是重要的，
區域/本地總線(Local Bus)：在印刷電路板上實作的總線
- 本地總線：CPU板級上的總線(習慣叫法)
- 存盤器總線：存盤器板級上的總線
- 資料總線：Ｉ/Ｏ板級和通信板級上的總線，
- 系統總線：在底板上實作的，它為所有插入板之間的通信提供了通路，
區域/本地總線+存盤器總線，將處理器與存盤模塊相連；
Ｉ/Ｏ總線+系統總線，將Ｉ/Ｏ設備、網卡等連接起來，
- Ｉ/Ｏ總線有時也叫作小型機系統介面SCSI(Small Computer System Interface)總線，
絕大多數標準總線都可低價構造單一處理系統(Unity Processor System)，在構造多處理器系統時，常使用多總線和層狀總線，

板級、底板級和Ｉ/Ｏ級總線系統:

在這里插入圖片描述

總線系統造價最低，但易沖突；
交叉開關造價最高，但帶寬和選路性能最好；
多級互連網路是總線與交叉開關的折衷
- 主要優點采用模塊結構，可擴展性好
- 但延遲隨網路尺寸對數增長，

在這里插入圖片描述

并行計算機結構

定義

大型并行機系統一般可分為6類機器，SIMD計算機多為專用，其余的5種均屬于多指令多資料流MIMD計算機，

單指令多資料流SIMD
并行向量處理機PVP
- 多為定制，通常不使用高速快取，而是使用大量的向量暫存器和指令緩沖器
對稱多處理機SMP
- 系統對稱，每個處理器可等同的訪問共享存盤器、Ｉ/Ｏ設備和作業系統服務，能開拓較高的并行度
- 是共享存盤，限制系統中的處理器不能太多(一般少于64個)，同時總線和交叉開關互連一旦作成也難于擴展，
大規模并行處理機MPP
- 處理節點采用商品微處理器；
- 系統中有物理上的分布式存盤器；
- 采用高通信帶寬和低延遲的互連網路(專門設計和定制的)；
- 能擴放至成百上千乃至上萬個處理器；
- 它是一種異步的MIMD機器，程式系由多個行程組成，每個都有其私有地址空間，行程間采用傳遞訊息相互作用，
作業站機群COW
- COW的每個節點都是一個完整的作業站(不包括監視器、鍵盤、滑鼠等)，也可以是一臺PC或SMP；
- 各節點通過一種低成本的商品(標準)網路(如以太網、FDDI和ATM開關等)互連(有的商用機群也使用定做的網路)；
- 各節點內總是有本地磁盤，而MPP節點內卻沒有；
- 節點內的網路介面是松散耦合到Ｉ/Ｏ總線上的，而MPP內的網路介面是連到處理節點的存盤總線上的，因而可謂是緊耦合式的；
- 一個完整的作業系統駐留在每個節點中，而MPP中通常只是個微核，COW的作業系統是作業站UNIX，加上一個附加的軟體層以支持單一系統映像、并行度、通信和負載平衡等
分布共享存盤DSM多處理機，
- DSM在物理上有分布在各節點中的區域存盤，從而形成了一個共享的存盤器，對用戶而言，系統硬體和軟體提供了一個單地址的編程空間，DSM相對于MPP的優越性是編程較容易，

屬性	PVP	SMP	MPP	DSM	cow
結構型別	MIMD	MIMD	MIMD	MIMD	MIMD
處理器型別	專用	定制	商用	商用	商用
互連網路	定制交叉開關	總線、交叉開關	定制網路	定制網路	商用網路(以太ATM)
通信機制	共享變數	共享變數	訊息傳遞	共享變數	訊息傳遞
地址空間	單地址空間	單地址空間	多地址空間	單地址空間	多地址空間
系統存盤器	集中共享	集中共享	分布非共享	分布共享	分布非共享
訪存模型	UMA	UMA	NORMA	NUMA	NORMA

圖示

B(Bridge)是存盤總線和Ｉ/Ｏ總線間的介面
DIR(CacheDirectory)是高速快取目錄
IOB(Ｉ/Ｏ Bus)是Ｉ/Ｏ總線
NIC(InterfaceCircuitry)是網路介面電路(網卡)
P/C(MicroprocessorandCache)是微處理器和高速快取
VP(Vector Processor)向量處理器
SM(SharedMemory)是共享存盤器，
LM(Local Memory)本地/區域存盤
LD(LocalDisk)是本地磁盤
RC(RemoteCatch)遠程高速快取

在這里插入圖片描述

并行計算機訪存模型

概念

UMA(Uniform MemoryAccess)模型是均勻存盤訪問模型的簡稱,適于通用或分時應用，
- 對稱多處理機SMP(SymmetricMultiprocessor):所有的處理器都能等同地訪問所有Ｉ/Ｏ設備、能同樣地運行執行程式(如作業系統內核和Ｉ/Ｏ服務程式等)時稱為
- 非對稱多處理機：只有一臺或一組處理器(稱為主處理器)，它能執行作業系統并能操縱Ｉ/Ｏ，而其余的處理器無Ｉ/Ｏ能力(稱為從處理器)，只在主處理器的監控之下執行用戶代碼，
其特點是：
- 物理存盤器被所有處理器均勻共享；
- 所有處理器訪問任何存盤單元取相同的時間(此即均勻存盤訪問名稱的由來)；
- 每臺處理器可帶私有高速快取；
- 外圍設備也可以一定形式共享，這種系統由于高度共享資源而稱為緊耦合系統(TightlyCoupledSystem)，

在這里插入圖片描述

NUMA(Nonuniform MemoryAccess)模型是非均勻存盤訪問模型的簡稱，特點是：
- 被共享的存盤器在物理上是分布在所有的處理器中的，其所有本地存盤器的集合就組成了全域地址空間；
- 處理器訪問存盤器的時間是不一樣的：訪問本地存盤器ＬＭ或群內共享存盤器CSM較快，而訪問外地的存盤器或全域共享存盤器 GSM較慢(此即非均勻存盤訪問名稱的由來)；
- 每臺處理器照例可帶私有高速快取，且外設也可以某種形式共享，

在這里插入圖片描述

COMA(Cach-OnlyMemoryAccess)模型是全高速快取存盤訪問的簡稱，是 NUMA 的一種特例，其特點是：
- 各處理器節點中沒有存盤層次結構，全部高速快取組成了全域地址空間；
- 利用分布的高速快取目錄D進行遠程高速快取的訪問；
- COMA中的高速快取容量一般都大于2級高速快取容量；
- 使用COMA時，資料開始時可任意分配，因為在運行時它最侄訓被遷移到要用到它的地方，

在這里插入圖片描述

CC-NUMA(Coherent-CacheNonuniform MemoryAccess)模型是高速快取一致性非均勻存盤訪問模型的簡稱，它實際上是將一些SMP機器作為一個單節點而彼此連接起來所形成的一個較大的系統，其特點是：
- 絕大多數商用 CC-NUMA多處理機系統都使用基于目錄的高速快取一致性協議；
- 它在保留SMP結構易于編程的優點的同時，也改善了常規 SMP 的可擴放性問題；
- CC-NUMA 實際上是一個分布共享存儲的DSM多處理機系統；
- 它最顯著的優點是程式員無需明確地在節點上分配資料，系統的硬體和軟體開始時自動在各節點分配資料，在運行期間，高速快取一致性硬體會自動地將資料移至要用到它的地方，

在這里插入圖片描述

NORMA(No-RemoteMemoryAccess)模型是非遠程存盤訪問模型的簡稱，在一個分布存盤的多計算機系統中，如果所有的存盤器都是私有的、僅能由其處理器所訪問時就稱為 NORMA，系統由多個計算節點通過訊息傳遞互連網路連接而成，每個節點都是一臺由處理器、本地存盤器和/或Ｉ/Ｏ外設組成的自治計算機，NORMA的特點是：
- 所有存盤器均是私有的；
- 絕大多數 NUMA都不支持遠程存盤器的訪問；
- 在DSM中，NORMA 就消失了，

小結

物理上分布的存盤器從編程的觀點看可以是共享的或非共享的

共享存盤結構(多處理機)可同時支持共享存盤和訊息傳遞編程模型
共享存盤的編程模型可同時執行于共享存盤結構和分布式存盤結構(多計算機)上，

在這里插入圖片描述

當代并行計算機系統介紹

共享存盤的對稱多處理機SMP

SMP系統屬于UMA(Uniform MemoryAccess)機器
NUMA(Nonuniform MemoryAccess)機器是SMP系統的自然推廣
CC-NUMA (Coherent-CacheNUMA)實際上是將一些SMP作為單節點而彼此連接起來所構成的分布共享存盤系統

結構特性：

對稱性：系統中任何處理器均可訪問任何存盤單元和Ｉ/Ｏ設備；
單地址空間：單地址空間有很多好處，例如因為只有一個OS和DB等副本駐留在共享存盤器中，所以OS可按作業負載情況在多個處理器上調度行程從而易達到動態負載平衡，又如因為所有資料均駐留在同一共享存盤器中，所以用戶不必擔心資料的分配和再分配；
高速快取及其一致性：多級高速快取可支持資料的區域性，而其一致性可由硬體來增強；
低通信延遲：處理器間的通信可用簡單的讀/寫指令來完成(而多計算機系統中處理器間的通信要用多條指令才能完成發送/接收操作)，目前大多數商用SMP系統都是基于總線連接的，占了并行計算機很大的市場

問題：

欠可靠：總線、存盤器或OS失效均會造成系統崩潰，這是SMP系統的最大問題；
可觀的延遲：盡管SMP比MPP通信延遲要小，但相對處理器速度而言仍相當可觀(競爭會加劇延遲)，一般為數百個處理器周期，長者可達數千個指令周期；
慢速增加的帶寬：有人估計，主存和磁盤容量每3年增加4倍，而SMP存盤器總線帶寬每3年只增加2倍，Ｉ/Ｏ總線帶寬增加速率則更慢，這樣存盤器帶寬的增長跟不上處理器速度或存盤容量的步伐；
不可擴放性：總線是不可擴放的，這就限制最大的處理器數一般不能超過10，為了增大系統的規模，可改用交叉開關連接，或改用CC-NUMA或機群結構，

分布存盤的大規模并行處理機 MPP

MPP公共結構

所有的 MPP均使用物理上分布的存盤器，且使用分布的Ｉ/Ｏ也漸漸變多，節點間通過高速網路HSN(HighSpeedNetwork)相連，每個節點包括：

一個或多個處理器和高速快取(Ｐ/Ｃ)
一個區域存盤
有或沒有磁盤和網路介面電路 NIC(NetworkInterfaceCircuitry)，它們均連向本地互連網路(早期多為總線而近期多為交叉開關)

MPP設計問題

可擴放性：MPP著名特性就是系統能擴展至成千上萬個處理器，而存盤器和Ｉ/Ｏ的容量及帶寬亦能按比例的增加，為此，采用物理上分布的存盤器結構，它能提供比集中存盤器結構更高的總計存盤帶寬，因此有潛在的高可擴放性；
- 要平衡處理能力與存盤和Ｉ/Ｏ的能力，因為存盤器和Ｉ/Ｏ子系統的速度不可能與處理器成比例地提高；
- 要平衡計算能力與互動能力，因為行程/執行緒的管理、通信與同步等都相當費時間，
系統成本：因為 MPP系統中包含大量的元件，為了保證系統的低成本應確保每個元件的低成本，為此，
- 應采用現有的商用 CMOS微處理器
- 要采用相對穩定的結構，
- 要使用物理上分布的存盤器結構，它比同規模機器的中央(集中)存盤器結構要便宜；
- 要采用SMP節點方式以削級訓連規模，
- 設計者必須加入專門硬體以擴大物理地址空間規模
通用性和可用性：
- MPP要支持異步 MIMD模式；
- 要支持流行的標準編程模式；
- 諸節點應能按大、小作業要求進行不同的組合以支持互動和批處理模式；
- 互連拓撲應對用戶透明，看到的是一組全連接的節點；
- MPP應在不同層次上支持單一系統映像SSI(Single-SystemImage)
- MPP必須使用高可用性的技術，
通信要求：MPP和 COW 的關鍵差別是節點間的通信，COW 使用標準的LAN，而 MPP使用高速、專用高帶寬、低延遲的互連網路，無疑在通信方面優于 COW，
存盤器和Ｉ/Ｏ能力：因為 MPP是可擴放系統，所以就要求非常大的總計存盤器和Ｉ/Ｏ設備容量，目前Ｉ/Ｏ方面的進展仍落后于系統中的其余部分，

差別

MPP和 COW 的關鍵差別是節點間的通信，COW 使用標準的LAN，而 MPP使用高速、專用高帶寬、低延遲的互連網路，無疑在通信方面優于 COW，

作業站機群COW

定義

作業站機群COW(ClusterofWorkstations)是實作并行計算的一種新主流技術，是屬于分布式存盤的 MIMD并行計算機結構，系由作業站和互連網路兩部分組成，由于這種結構用于并行計算的主要資源是作業站，所以作業站機群的名稱便由此產生，作業站機群COW 這一名稱，在早期的研究階段，也曾被稱為作業站網路NOW(NetworkofWorkstations)，

從用戶、程式員和系統管理員的角度看，COW 相當于單一并行系統，感覺不到多個作業站的實際存在；
從程式設計模式的角度看，它與 MPP一樣可采用面向訊息傳遞的SPMD(SingleProgramMultipleData)編程方式，即各個作業站均運行同一個程式，但分別加載不同的資料，從而可支持粗粒度的并行應用程式，

優勢

投資風險小
編程方便
系統結構靈活
性能/價格比高
能充分利用分散的計算資源
可擴放性好

并行計算性能評測

名稱	符號	含意	單位
機器規模	n n n	處理器的數目	無量綱
時鐘速率	f f f	時鐘周期長度的倒數	M H z MHz MHz
作業負載	W W W	計算操作的數目	M f l o p Mflop Mflop
順序執行時間	T i T_i Ti?	程式在單處理機上的運行時間	s ( 秒 ) s(秒) s(秒)
并行執行時間	T n T_n Tn?	程式在并行機上的運行時間	s ( 秒 ) s(秒) s(秒)
速度	R n = W / T n R_n=W/T_n Rn?=W/Tn?	每秒百萬次浮點運算	M f l o p s Mflops Mflops
加速	S n = T 1 / T n S_n=T_1/T_n Sn?=T1?/Tn?	衡量并行機有多快	無量綱
效率	E n = S n / n En=S_n/n En=Sn?/n	衡量處理器的利用率	無量綱
峰值速度	R p e a k = n R ’ p e a k R_{peak}=nR’_{peak} Rpeak?=nR’peak?	所有處理器峰值速度之積， R p e a k ′ R'_{peak} Rpeak′?為一個處理器的峰值速度	M f l o p s Mflops Mflops
利用率	U = R n / R p e a k U=R_n/R_{peak} U=Rn?/Rpeak?	可達速度與峰值速度之比	無量綱
通信延遲	t 0 t_0 t0?	傳送0一位元組或單字的時間	μ s \mu{s} μs
漸近帶寬	r ∞ r_\infty r∞?	傳送長訊息通信速率	M B / s MB/s MB/s

作業負載

所謂作業負載(荷)，就是計算操作的數目，通常可用執行時間、所執行的指令數目和所完成的浮點運算元三個物理量來度量它，

執行時間：它可定義為在特定的計算機系統上的一個給定的應用所占用的總時間，系指應用程式從開始到結束所掠過時間(ElapsedTime)，它不只是CPU時間，還包括了訪問存盤器、磁盤、Ｉ/Ｏ通道的時間和 OS開銷等，
浮點運算：對于大型科學與工程計算問題，使用所執行的浮點運算元目來表示作業負載是很自然的，對于程式中的其他型別的運算，可按如下經驗規則折算成浮點運算(Flop)數：在運算運算式中的賦值操作、變址計算等均不單獨考慮(即它們被折算成0Flop)；單獨賦值操作、加法、減法、乘法、比較、資料型別轉換等運算均各折算成1Flop；除法和開平方運算各折算成4Flop；正(余)弦、指數類運算各折算成８Flop；其他類運算，可按其復雜程度，參照上述經驗資料進行折算之，
指令數目：對于任何給定的應用，它所執行的指令條數就可視為作業負載，常以百萬條指令為計算單位，與其相應的速度單位就是MIPS(每秒百萬條指令)，

并行執行時間

在無重疊操作的假定下，并行程式的執行時間 T n T_n Tn?為：
T n = T c o m p u t + T p a r o + T c o m m T_n=T_{comput}+T_{paro}+T_{comm} Tn?=Tcomput?+Tparo?+Tcomm?

Tcomput為計算時間
Tparo為并行開銷時間
- 包括行程管理(如行程生成、結束和切換等)時間，組操作(如行程組的生成與消亡等)時間和行程查尋(如詢問行程的標志、等級、組標志和組大小等)時間；
Tcomm為相互通信時間，
- 包括同步(如路障、鎖、臨界區、事件等)時間，通信(如點到點通信、整體通信、讀/寫共享變數等)時間和聚合操作(如歸約、前綴運算等)時間，

存盤器性能

存盤器的層次結構

容量Ｃ：表示各層的物理存盤器件能保存多少位元組的資料；
延遲Ｌ：表示讀取各層物理器件中一個字所需的時間；
帶寬Ｂ：表示在1秒鐘內各層的物理器件中能傳送多少個位元組，

在這里插入圖片描述

存盤器帶寬的估算

公式

帶寬 = 操作的存儲長度 × 時鐘頻率帶寬=操作的存盤長度\times時鐘頻率帶寬=操作的存儲長度×時鐘頻率

較快的時鐘頻率和處理器中較高的并行操作，可獲得較寬的帶寬

例：RISC加法指令帶寬估算

條件：字長64位(8位元組)，時鐘頻率100MHz，單拍內可完成指令

指令流程：取2個字a,b，執行操作后送回暫存器，共涉及3個字(24位元組)

$\begin{align}Speed&=Length\times{Frequency}\\&=(3\times8)\times(100\times10^6)\\&=2.4GB/s \end{align}$

三大定律

簡稱定義

是并行系統中處理器數；
W是問題規模(下文中也常叫作計算負載、作業負載，它定義為給定問題的總計算量)，
Ws 是應用程式中的串行分量，
Wp是W中可并行化部分(顯然 Ws+Wp= W)；
Wo為額外開銷
f是串行分量比例(f= Ws/Ｗ，Ws= W1)，
1-f為并行分量比例(顯然 f+(1-f)=1)；
Ts=T1 為串行執行時間，
Tp 為并行執行時間；
S為加速(比)，
E為效率，
G(p)反映存盤容量增加到p倍時作業負載的增加量

Amdahl定律 - 固定負載的加速公式

原公式

S = W s + W p W s + W p p S=\frac{W_s+W_p}{W_s+\frac{W_p}{p}} S=Ws?+pWp??Ws?+Wp??

歸一化的公式

將 W s + W p W_s+W_p Ws?+Wp?表示為 f + ( 1 ? f ) f+(1-f) f+(1?f)得：
S = f + ( 1 ? f ) f + 1 ? f p = p 1 + f ( p ? 1 ) S=\frac{f+(1-f)}{f+\frac{1-f}{p}}=\frac{p}{1+f(p-1)} S=f+p1?f?f+(1?f)?=1+f(p?1)p?

修正的公式

上并行加速不僅受限于程式的串行分量，而且也受并行程式運行時的額外開銷影響
$\begin{align}S&=\frac{W_s+W_p}{W_s+\frac{W_p}{p}+W_o}\\&=\frac{W}{fW+\frac{W(1-f)}{p}+W_o}\\ &=\frac{p}{1+f(p-1)+\frac{W_op}{W}} \end{align}$

極限情況與條件

對于理想情況：當 p → ∞ p\to\infty p→∞時取極限

S = 1 f S=\frac{1}{f} S=f1?

對于實際情況：當 p → ∞ p\to\infty p→∞時取極限

S = 1 f + W o W S=\frac{1}{f+\frac{W_o}{W}} S=f+WWo??1?

出發點

對于很多科學計算，實時性要求很高，即在此類應用中時間是個關鍵因素，而計算負載是固定不變的，為此在一定的計算負載下，為達到實時性可利用增加處理器數來提高計算速度；
因為固定的計算負載是可分布在多個處理器上的，這樣增加了處理器就加快了執行速度，從而達到了加速的目的，

含義

它意味著隨著處理器數目的無限增大，并行系統所能達到的加速之上限為 1 f \frac{1}{f} f1?

在這里插入圖片描述

Gustafson加速定律

原公式

$\begin{align} S'&=\frac{W_s+pW_p}{W_s+p\times\frac{W_p}{p}}\\ &=\frac{W_s+pW_p}{W_s+W_p} \end{align}$

歸一化公式

$\begin{align} S'&=f+p(1-f)\\ &=p+f(1-p)\\ &=p-f(p-1) \end{align}$