并行處理技術

并行處理技術

（并行計算）

第一部分

并行基本概念

自90年代以來，并行計算得以空前的飛速發(fā)展,

一方面，由于單處理機的計算速度不斷提高，并行

計算機的體系結構趨于成熟，數(shù)據(jù)傳輸網(wǎng)絡的標準

化和傳輸速率的大幅提升，使得并行計算機的研制

周期能夠從幾年到幾個月，為研制并行計算機系統(tǒng)

創(chuàng)造了有利條件。另一方面，推動并行計算發(fā)展的

主要動力來自于國際上的一些重要研究計劃。

（1）美國HPCC計劃：科學和工程計算需要能夠提供

1TFLOPS計算能力、仃B內存容量、1TB/S的I/O

帶寬，也就是3T性能目標。美國為了保持其在高性

能計算與計算機通信領域的領先地位，在1993年，

由科學、工程、技術聯(lián)邦協(xié)調理事會向國會提交了

“重大挑戰(zhàn)項目：高性能計算與通信”的報告，也

就是被稱為HPCC計劃的報告，即美國總統(tǒng)科學戰(zhàn)

略項目，其目的是通過加強研究與開發(fā)解決一批重

要的科學與技術挑戰(zhàn)問題。

(2)美國ASCI計劃：全面禁止核試驗條約簽訂后，

對核武器的研制只能通過在實驗室的數(shù)值模擬來完

成。1996年6月由美國能源部提出了“加速戰(zhàn)略計

算創(chuàng)新”計劃，也即ASCI計劃項目。提出通過數(shù)

值模擬來評估核武器的性能、安全性、可靠性、更

新等。要求數(shù)值模擬達到高分辨率、高逼真度、三

維、全物理、全系統(tǒng)的規(guī)模和能力。該計劃被認為

是與當年曼哈頓計劃等同的一個巨大的挑戰(zhàn)，它不

僅需要自然科學家的參與，而且也需要與計算機等

工業(yè)界的合作，提供保障ASCI計劃中的應用所需

的計算機平臺。

?并行處理技術

并行處理是一種有效地強調開發(fā)計算過程中并

行事件的信息處理方式。

(1)并行性含義

同時性：指兩個或多個事件在同一時刻發(fā)生在

多個資源中。

并發(fā)性：指兩個或多個事件在同一時間間隔內

發(fā)生在多個資源中。

流水線：指兩個或多個事件發(fā)生在可能重疊的

時間段內。

并行計算之所以可行，主要在于，并發(fā)性是物

質世界的一種普遍屬性，具有實際應用背景的計算

問題在許多情況下都可以分解為能并行計算的多個

子任務。

(2)并行計算

給定一個問題，并行計算就是這樣的過程：把

問題分解成子問題，同時計算子問題，最后把子問題

的解合并得到原問題的解。

把每一個非常大的問題分成子問題是很不容易的,

這是由于子問題之間可能存在數(shù)據(jù)相關性。由于數(shù)據(jù)

相關性，處理器之間必須相互通信，通常兩個處理器

之間的通信時間與處理時間相比是很高的。因此，為

了得到好的并行算法，通信方案應該進行很好地規(guī)劃。

并行處理面臨著兩個重要的挑戰(zhàn)：

(a)程序中有限的并行性

(b)相對較高的通信開銷

并行計算（高性能計算、超級計算）

分解

大任務?多個子任務

分給

協(xié)同合作-二

快速求解不同處理單元

由此，為了成功開展并行計算，必須具備三個

基本條件：

(a)并行機。并行機至少包含兩臺或兩臺以上處理機,

這些處理機通過互連網(wǎng)絡相互連接，相互通信。

(b)應用問題必須具有并行度。也就是說，應用可以

分解為多個子任務，這些子任務可以并行地執(zhí)行。

將應用分解為多個子任務的過程，稱為并行算法設

并。

(c)并行編程。在并行機提供的并行環(huán)境上，具體實

現(xiàn)并行算法，編制并行程序，并運行該程序，從而

達到求解應用問題的目的

?并行計算研究的目的

對于具體的應用問題，采用并行計算技術的主

要目的在于兩個方面：

(1)加速求解問題的速度。例如，給定某應用，在單

處理器上，執(zhí)行需要兩個星期(14天)；而借助并

行計算，使用100臺處理器，加速50倍，則執(zhí)行時間

縮短為6.72個小時。

(2)提高求解問題的規(guī)模。例如，在單處理器上，受

內存資源2GB的限制，只能計算10萬個網(wǎng)格，但當數(shù)

值模擬要求計算1千萬個網(wǎng)格時，則仍需借助并行計

算，使用100個處理器，將問題規(guī)模線性地擴大100

倍。

?并行計算的研究內容：

(1)并行計算機設計

(2)有效算法的設計

(3)評價并行算法的方法

(4)并行計算機語言

(5)并行編程環(huán)境與工具

(6)并行程序的可移植性

(7)并行計算機的自動編程

(3)并行的層次

(a)串行處理

(b)程序級并行(作業(yè)級并行)f子程序級并行

(任務級并行)f語句級并行一操作級并行f

微操作級并行。

(4)并行性等級

從執(zhí)行程序的角度看：指令內部并行、指令間并行、

任務間并行、作業(yè)間并行。

從處理數(shù)據(jù)的角度看：字串位串、字串位并、字并位

串、字并位并。

?問題的并行求解過程

問題的并行求解過程

?并行計算機的理論模型（PRAM模型）

PRAM（ParallelRandomAccessMachine）模型

又稱共享存儲器模型，具有4種不同的操作方式：

EREW（互斥讀互斥寫）CREW（并發(fā)讀互斥寫）

ERCW（互斥讀并發(fā)寫）CRCW（并發(fā)讀并發(fā)寫）

(1)分類

(a)PRAM-CRCW并發(fā)讀并發(fā)寫

?CPRAM-CRCW(CommonPRAM-CRCW)：僅允

許寫入相同數(shù)據(jù)

^PPRAM-CRCW(PriorityPRAM-CRCW)：僅允

許優(yōu)先級最高的處理器寫入

，APRAM-CRCW(ArbitraryPRAM-CRCW)：允

許任意處理器自由寫入

(b)PRAM-CREW并發(fā)讀互斥寫

(c)PRAM-EREW互斥讀互斥寫

(2)計算能力比較

PRAM-CRCW是最強的計算模型，PRAM-EREW

可logp倍模擬PRAM-CREW和PRAM-CRCW

TE…

EREW。（TCREW「OgP）=OJRCW」°gP）

(3)優(yōu)缺點

優(yōu)點：適合并行算法表示和復雜性分析，易于使用，隱

藏了并行機的通訊、同步等細節(jié)。

缺點：不適合MIMD并行機，忽略了SM的競爭、通訊

延遲等因素。

?并行計算與計算科學

并行計算，簡單地講，就是在并行計算機上所

做的計算，它和常說的高性能計算、超級計算是同

義詞，因為任何高性能計算和超級計算總離不開使

用并行技術。

當今，計算科學已經(jīng)和傳統(tǒng)的兩種學科：理論

科學和實驗科學，并列為第三門科學，它們彼此相

輔相成地推動科學發(fā)展與社會進步。

并行處理是計算科學的重要內容，是實現(xiàn)高性

能計算的重要途徑，是并行算法設計、并行程序設

計語言和并行計算機體系結構三者相結合的產(chǎn)物，

是一門計算科學與其它工程學科相結合的處于發(fā)展

過程中的交叉學科，其研究重點在于挖掘各個計算

層次的并行性。

?大型并行機系統(tǒng)一般可分為：

(1)單指令多數(shù)據(jù)流機(SIMD)

(2)多指令多數(shù)據(jù)流機(MIMD)

MIMD類機器又可分為：并行向量處理機PVP、

對稱多處理機SMP、大規(guī)模并行處理機MPP、工作

站機群COW、分布共享存儲多處理機DSM五類。

(c)MPP

(d)DSM

(e)COW

?并行性的發(fā)展

并行性概念乃是推動計算機系統(tǒng)結構發(fā)展的重要因

素，為了達到高性能的要求并滿足大量計算應用領域

的需要，一方面可在單處理內廣泛采取多種并行性措

施，沿著時間重疊、資源重復和資源共享三條技術途

徑向現(xiàn)代并行處理領域發(fā)展，另一方面把多臺計算機

連接起來、相互配合、各盡其能，沿著功能專門化、

多機群和網(wǎng)絡化這三種基本技術途徑向現(xiàn)代并行處理

領域發(fā)展。

(1)時間重疊

在并行性概念中引入時間因素，即多個處理過程在

時間上相互錯開輪流重疊使用同一套硬件的各個部件

以加快部件的周轉而提高速度。

(2)資源重復

在并行性概念中引入空間因素，根據(jù)以數(shù)量取勝的原則，

重復設置硬件資源以大幅度提高計算機系統(tǒng)的性能。

（3）資源共享

利用軟件的方法，使多個用戶分時使用同一個計算

機系統(tǒng)，以提高計算機系統(tǒng)資源的利用率。

單處理機系統(tǒng)朝并行處理領域發(fā)展

多計算機

網(wǎng)絡化功能專用化

通信處理機松散耦合系統(tǒng)

計算機網(wǎng)絡專用外圍機

處

局部計高級語言］理

算機網(wǎng)絡數(shù)據(jù)庫/機

分布處同構型異構型

理系統(tǒng)多處理機多處理機

多計算機機系統(tǒng)朝并行處理領域發(fā)展

分布式計算機系統(tǒng)特征

?資源分散性

通常計算機系統(tǒng)包括物理資源（中央處理器、

存儲器、輸出輸入設備）和邏輯資源（文件系統(tǒng)、各

種軟件系統(tǒng)等）。所謂分布式是相對于集中式而言的,

一般是指其功能是分布式的，是通過資源分散配置

來實現(xiàn)的。傳統(tǒng)的VonNeumann計算機是單機集中式，

其功能和資源都是集中式。而分布式系統(tǒng)是把處理

功能、存儲功能、傳輸功能分散到各個系統(tǒng)，軟件

的資源分散到各個系統(tǒng)上，通過通信網(wǎng)絡和軟件把

它們連成一個整體。

■工作并行性

工作并行性是由于它的資源分散和重復性，真正實

現(xiàn)了多指令多數(shù)據(jù)流。這是一種真正的并行而不是并發(fā)

執(zhí)行。分時系統(tǒng)中，對每個用戶來說宏觀上好象是并行

工作。但某一時刻，中央處理器只能處理一個作業(yè)。實

質上是串行地執(zhí)行。而分布式系統(tǒng)，每臺計算機都具有

自己的CPU和存儲器，允許多個進程真正并行執(zhí)行。

?結構模塊性

結構模塊性是指系統(tǒng)由多個分散的物理和邏輯資源

組成。它們雖然互連成一個整體，但它們分別又是相互

獨立的。每個子系統(tǒng)或節(jié)點有獨立的處理功能、存儲功

能、I/O設備、通信功能，這樣就形成一個完整的模塊,

這種模塊性的結構易于擴展、更新和重構。

?協(xié)作自治性

分布式系統(tǒng)中控制上的自治性是區(qū)別多處理機系統(tǒng)的關鍵

所在。并行處理和多處理機系統(tǒng)大多共享它們的內存，對資源集

中控制和管理。而分布式計算機系統(tǒng)采用協(xié)作自治管理方式。這

種控制自治性體現(xiàn)在各個模塊是處于平等自治地位，分別是在統(tǒng)

一協(xié)調配合下自主地工作。這種工作方式使系統(tǒng)有了任意擴展的

可能，并使其工作可靠性得到確實的保證。

?運行堅定性

系統(tǒng)總是會出錯的，這包括硬件系統(tǒng)和軟件系統(tǒng)的

故障。為了提高系統(tǒng)的可利用性和可靠性，近幾年對容

錯技術進行了大量的研究。分布式系統(tǒng)對于冗余、重構、

快速恢復的潛在能力具有突出的優(yōu)越性。由于模塊結構

和在操作系統(tǒng)級采用了容錯的措施，使分布式系統(tǒng)在當

出現(xiàn)故障時，首先可以降級使用或采用重構的措施，特

別是近幾年在分布式操作系統(tǒng)級實現(xiàn)了進程遷移，使系

統(tǒng)對用戶運行更加堅定。

?系統(tǒng)透明性

系統(tǒng)對用戶透明己成為分布式計算機系統(tǒng)最

關鍵的特征之一。很多多機系統(tǒng)和網(wǎng)絡系統(tǒng)不滿

足這個條件。對于局域網(wǎng).其系統(tǒng)的拓撲結構、

互聯(lián)網(wǎng)方式、傳輸介質、通信速率和轄域與分布

式系統(tǒng)類似，但只是為了通信和共享資源而已，

而分布式計算機系統(tǒng)對用戶是透明的，即用戶不

知道它的程序在哪一臺機器上運行，也不知道它

的文件存于何處，當調用一個文件系統(tǒng)時，系統(tǒng)

能保證總是提供最新版本。

下面是ASSA(AdvancedNetworkSystemArchitecture)

定義的8種透明性：

1.訪問透明性：可用同樣的操作訪問本地和遠程的文件以及其他

對象。

2.位置透明性：訪問任何對象時都不必了解其所在位置。

并發(fā)透明性：多個用戶或應用程序在使用共享數(shù)據(jù)時互相不干

3.Iio

4.復制透明性：可以使用文件或其他數(shù)據(jù)的多個副本以增加可靠

性和性能，但用戶或應用程序不必了解是否使用了副本。

5.錯誤透明性：錯誤被封閉起來.即使山現(xiàn)了軟硬件故障，也不影

響應用程序完成任務。

6.遷移透明性：系統(tǒng)中的對象可在不同機器之間遷移，但不影響

應用程序運行。

7.性能透明性：允許系統(tǒng)進行重構來改變性能，從而適應用戶負

載的變化。

8.伸縮透明性：允許系統(tǒng)或應用擴充規(guī)櫛而不必改變系統(tǒng)結構或

應用算法。

例：兩個浮點向量Xi和Yi(i=l,2,??.n),相加后

的結果為Zi。設浮點加法運算分4段(對階、

尾加、規(guī)格化、舍入)完成。分別計算當

n=100,m=4(段數(shù))，N=20(處理單兀數(shù))

時，T=1US(每段時間)時，串行、流水和向

量運算所需的時間。

T串行=m*n*工=4*100*lus=400us

T流水=(m+n-1)*T=(4+100-1)*lus=103us

T向量=t#*「n/Nl=m*T*rn/N

=4*lus*「100/201=20us

其中N〈n,t#為首先計算N對元素(Xi,Yi,

i=l,2,…N)所需的時間。

第二部分

流水線（并行）技術

?流水線技術

流水線技術是并行計算中一個非常有效

的、常用的手段，在并行計算中起著非常重

要的作用。

流水線技術在60年代中開始用于計算機系

統(tǒng)，該技術采用時間上重疊的方法來實現(xiàn)并

行性，因而可以用較少的設備取得較高的性

能。目前，幾乎所有的計算機系統(tǒng)都采用了

流水線技術。

流水原理

所謂流水就是將一個過程分解成若干個子過程,

使每個子過程都可以有效地在其專用的功能段上

與其它子過程并行執(zhí)行。

例如，將指令的執(zhí)行過程分成6個階段：取指(FI)、指

令譯碼(DI)、計算操作數(shù)地址(CO)、取操作數(shù)(F0)、執(zhí)行

指令(EI)、寫操作數(shù)(W0)。每段都在其相應的功能部件上

實現(xiàn)，且執(zhí)行時間為△仁

AtAtAtAtAtAt

入出

?流水線的性能參數(shù)

設流水線段數(shù)=m,每段執(zhí)行時間=Z\t,指令數(shù)=n。

串行處理所需時間：T§=m*n*Zkt

流水處理所需時間：TP=(m+n-l)*At

流水線時■空圖：(m=4,n=7)

入求階差對階尾數(shù)相加規(guī)格化出

-A-△&A-A

(a)浮點加法流水線

空間A

規(guī)格化123456?

尾數(shù)相加1234567

對階1234567

求階差1234567

G&6匕bifah5時間

(b)描述流水線工作的時空圖

三項性能指標：吞吐率、加速比和效率

(1)流水線的吞吐率

吞吐率是指單位時間內流水線所完成的任務數(shù)或輸出結果

的數(shù)量。(單位時間內流水線能處理的指令數(shù))

實際吞吐率：TP=n/Tp=n/[(m+n—1)*Zkt]

最大吞吐率明數(shù)是指流水線在達到穩(wěn)定狀態(tài)后所得到的

吞吐率。

最大吞吐率：TPmax=1/At

(2)加速比

加速比是指流水線速度與等功能的非流水線速度之比。

S=Ts/TP當n?m時，S-m

(3)效率

效率是指流水線設備的利用率。

E=n*At/TP

例2：設有一個15000條指令的程序在一臺時鐘速率為

25MHz的線性流水線處理機上執(zhí)行。假設指令流水

線有5段，且每個時鐘周期發(fā)射一條指令。求流水線

的吞吐率TP、加速比S、效率E。(不考慮相關問題)

則：

n=15000,m=5,At=1/25=0.04us

TP=(5+15000-1)*0.04=600.16us

T=5*15000*0.04=3000us

TP=15000/600.16=24.99MIPS

S=3000/600.16=4.99

E=15000*0.04/600.16=99.97%

?各功能段時間不相等時的參數(shù)計算

設流水線段數(shù)=m,第i段執(zhí)行時間=△［指

令（或任務）數(shù)=n,貝ll：

m

串行處理所需時間：T=〃xZAti

sz=l

m

流水處理所需時間:Tp=EAti+(^-l)Atj

Z=1

其中即最慢一段所需的時間。

最大吞吐率：TPmax=l/maxfAtJ

最大吞吐率取決于流水線中最慢一段所需的時間,

該段成為流水線的瓶頸

實際吞吐率：

n

實際吞吐率型=軍方可

加速比:

mm

S=Ts/Tp=〃xEAti/ZAti+（〃一l）Atj

z=1z=1

效率：從時-空圖上看，效率就是力個任務所占的時空

區(qū)與5個段總的時空區(qū)之比，因此從時-空圖上看，

效率就是刀個任務所占的時空區(qū)與5個段總的時空區(qū)

之比。

石,里務占用的時空區(qū)

5個段總的時空區(qū)

例：設某指令流水線為4段，各段的執(zhí)行時間如圖所示,

且△t°=lus,求執(zhí)行3條指令時，流水線的吞吐率、

加速比、效率。

kkk

，At0—3At0—At0—"At0一

m

Ati

串行處理所需時間：T=-xZ=18us

smf=l

流水處理所需時間：Tp=EAti+-OAtj=12US

Z=1

最大吞吐率：TPmax=l/max{Ati}=1/(3At0)=O.33MIPS

實際吞吐率：TP=n/Tp=3/12=0.25MIPS

加速比：S=TS/TP=18/12=1.5

效率：E=18At0/(4xl2At0)=37.5%

?相關問題

所謂相關是指程序的相近指令之間出現(xiàn)某

種關聯(lián)，使指令流水線出現(xiàn)停頓，影響了流水線

的效率。指令間的相關大體可分控制相關和數(shù)據(jù)

相關兩類。

(a)控制相關：如果一條指令要等前一條(或幾

條)指令作出轉移方向的決定后，才能進入流水

線，便發(fā)生了控制相關。包括轉移和中斷兩種情

況。

條件轉移：為了在遇到條件轉移指令后，流水線仍能繼續(xù)

向前流動，多數(shù)機器采用的是“猜測法”技術。猜測

哪個分支是事先確定的，一般選擇轉移不成功的分支。

(b)數(shù)據(jù)相關：數(shù)據(jù)相關是在幾條相近的指令間共用同

一個存儲單元或寄存器時發(fā)生的。三種數(shù)據(jù)相關如下：

先寫后讀相關：指對同一個單元，要求在前的指令先寫入,

在后的指令才能讀出的關聯(lián)。

例：L：R1=R2+R3

I2：R4=Ri*R5

先讀后寫相關：指對同一個單元，要求在前的指令先讀出,

在后的指令才能寫入的關聯(lián)。

例：I1：RLR2+R3

=

I2：R2R4*R5

寫-寫相關：指對同一個單元，要求在前的指令先寫入，

在后的指令才能寫入的關聯(lián)。

例：L：R=R2+R3資源相關

[2：R]=R4+R5

例：有一8段順序流動流水線，其中第2段為讀段，第7

段為寫段。指令串h、i、j、k、1、m、n>依次進

入流水線。如果第j條指令的源操作數(shù)地址與第h條

指令的結果地址相同，則可斷定指令h和j之間發(fā)生

了先寫后讀相關。

kj***ih順序流動

指令kjihj和h相關

兩種解決方法如下：相關專用通路

推后讀：當j到達讀段時，流水線斷流，直到h到達寫段并完成寫入后在繼續(xù)。

設置相關專用通路：避免相關單元的寫入和讀出時間，使指令j提前流動。

?流水線的分類

（1）按完成的功能分

單功能流水線：指只能完成一種固定功能的流水線。

多功能流水線：指各段可以進行不同的連接，從而完成

不同的功能。

（2）按同一時間內各段之間的連接方式分

靜態(tài)流水線：指在同一時間內，流水線的各段只能按同

一種功能的連接方式工作。

動態(tài)流水線：指在同一時間內，流水線的各段可按不同

運算的連接方式工作，即當某些段正在實現(xiàn)某種運算

時，另一些段卻在實現(xiàn)另一種運算。

（3）按任務輸入/輸出的順序分

順序流動流水線和異步流動流水線。異步流動流

水線也可稱為無序流水線、錯序流水線或亂序流水線。

（4）按流水線的級別分

部件級流水線：又叫運算操作流水線，是把處理機的

算術邏輯部件分段，使得各種數(shù)據(jù)類型的操作能夠

進行流水。

處理機級流水線：又叫指令流水線，是把解釋指令的

過程按照流水方式處理。

系統(tǒng)級流水線（處理機間流水線）：又叫宏流水線，

是由兩個以上的處理機串行地對同一數(shù)據(jù)流進行處

理，每個處理機完成一項任務。

（5）按數(shù)據(jù)表示分

標量流水線（處理機）：是指處理機不具有向量數(shù)據(jù)

表示，僅對標量數(shù)據(jù)進行流水處理。

向量流水線（處理機）：是指處理機具有向量數(shù)據(jù)表

示，并通過向量指令對向量的各元素進行處理。

（6）按流水線中是否有反饋回路分

線性流水線：指流水線的各段串行連接，沒有反饋回路。

非線性流水線：指流水線中除有串行連接的通路外，還有

反饋回路。

非線性流水線存在流水線調度問題，即確定什么時

候向流水線引進新的輸入，從而使新輸入的數(shù)據(jù)和先前

操作的反饋數(shù)據(jù)在流水線中不產(chǎn)生沖突。

反饋回路

出

Soo

流動順序：S］、S2>S3、S4、s2>S3、S4、o

?CRAY-1向量流水處理機

(1)向量沖突

數(shù)相關：V2=V0+V1部件相關：V4=v2+v3

V4=V2*V3V5=V1+V6

源向量沖突（相關）：V4=V1+V2

%=V\+V3

無相關，可并行執(zhí)行的兩組向量：V0=Vi+V2

*

(2)四種典型的向量指令

V、￥Vj

功訪

能存

部

件

向量一向量向量一標量向量取向量存

運算指令運算指令數(shù)指令數(shù)指令

(3)鏈接技術

鏈接技術是流水線中加快運算速度的一種重要技術。

只要不發(fā)生功能部件沖突和源向量沖突，就可以把兩個

或兩個以上的功能部件連接起來形成一條鏈子進行流水

處理。通過鏈接結構，可使數(shù)據(jù)相關的向量指令也能并

行執(zhí)行。

例1.向量運算：D=A*(B+C),向量長度n064。

則當B、C取到V。、Vi后，就可用以下三條指令求解。

(a)V3—存儲器(訪內取A)

(b)V2―V0+V1(浮點力口)

(c)V4<-V2*V3(浮點乘，V4存放D)

(a)、(b)兩條指令無相關，可以并行執(zhí)行。而(c)與

(a)、(b)兩條指令有數(shù)相關，本不能并行執(zhí)行，但若能

把(a)、(b)兩條指令的結果元素直接鏈接進⑹條指令所

用的功能部件，則第(c)條指令就能與(a)、(b)兩條指令

并行執(zhí)行。

設從功能部件取數(shù)和向

功能部件存數(shù)都需一拍，訪

存需6拍,浮點加需6拍,浮

點乘需7拍，則從訪內開始,訪

存

直至把第一個結果元素存入

浮

V4,所需拍數(shù)為：

1+6+1+1+7+1=17拍點

當向量元素N=64時，加

鏈接運算所需時間為：

T=17+(N-1)=80拍。

非鏈接運算所需時間為：

T=17+m(N-l)

=17+2(64-1)浮

—]43拍點

m為鏈接的指令數(shù)。乘

取向量長度N=3,鏈接指令數(shù)m=2時,

鏈接與非鏈接的時間對比。

013456789101112131415161718192021222324252627

?單功能非線性流水線調度問題

非線性流水線調度要解決的問題是：確定控制

處理對象流入流水線的時間間隔，使其既不發(fā)生對象

爭用流水線段的沖突，又有較高的吞吐率和效率。

（1）預約表

行：表示流水線中的段。

歹U：表示任務經(jīng)過流水線所需的時間（時鐘數(shù)）。

如果任務在tj時刻需學處理，則在表中的i行和第

j列的交叉處用“X”表示。

調度：每個時鐘周期

（每拍）向流水線輸

入一個新任務。

4段線性流水線預約表

每個任務按S1，S2,S3,S3,S4,S2,S［順序流過

各段，預約表如下：其中每個任務從輸入到輸出共需

7個時鐘周期。

tlht

4t5t6

S1XX

XX

S2

S3XX

S4X

4段非線性流水線預約表

(2)禁止表

如果表中的&行有兩個(或多個)“義”，它們

之間相距d個時鐘周期，那么在相隔d個時鐘周期

輸入新任務時，則一定會出現(xiàn)新任務與舊任務同時

爭用*段的情況，即在號段上產(chǎn)生沖突。

禁止表：由預約表中每一行所有不同的兩個“x”

之間距離的集合組成。

m

其中，m為段數(shù)，fi={d|d為Sj行中所有不同的兩

個“x”之間距離}。

例如：4段非線性流水線的禁止表為

F={6}o{4}u{l}={1,4,6)

（3）均勻調度（等間隔調度）

在非線性流水線的任務輸入過程中，找出一個

最小時間間隔，并按此時間間隔進行調度，使多個

任務輸入非線性流水線，并在處理過程中不會出現(xiàn)

爭用某段的情況。

由上面禁止表F可以看出，相鄰兩任務輸入流水

線的時間間隔數(shù)不能是1,4和6,即這些值在調度時

應當禁止使用。

一般地當連續(xù)輸入多個任務時，對于任何一個

任務T（T>1）,流水線按時間間隔K進行進行均勻

調度，不發(fā)生爭用沖突的條件是：

T*KeF

其中TNI,k￡l且為正整數(shù)，但若要提高非線性流水

線的效率，則對均勻調度來說，應取：min{kJo

例：對于禁止表F二{1,4,6},確定均勻調度方案。

取曷=2,T=2,則T*k"F,不能按相隔2拍調度

取曷=3,T=2,則T*k”F,不能按相隔3拍調度

取曷=5,T>1,則T*leF,可以按相隔5拍調度

取k2=7,T>1,則T*k2eF,可以按相隔7拍調度

由此得K={kpk2,...}={5,7,…},所以取

min{kJ=5,進行均勻調度時會吐率最高。

若設n=3,每個時鐘周期為At,貝小

最大吞吐率：TPmax=l/(5At)

實際存吐率：TP=3/(17At)

效率：E=(3x7)/(4xl7)=30.9%

按K=5均勻調度

（4）非均勻調度

由前面分析可知，在任一時刻輸入新任務與當

時在流水線中各任務的推進情況有關，因此新任務

與舊任務是否發(fā)生爭用沖突，可以用一個n位沖突向

量C表示。即:

C=（CnCn/…C2C。

其中，第i位的狀態(tài)表示與當時相隔i個時鐘周期

是否允許向流水線輸入新的任務，該位為“0”表示允

許輸入，該位為“1”表示不允許輸入。

初始沖突向量：輸入第一個任務時建立的沖突向量。

此向量的位數(shù)n是最大的禁止間隔，故Cn總是等于1。

例：對于禁止表F二{1,4,6},當流水線輸入第一個

任務后，初始沖突向量為：

C=（C6c5c4c3c2力）=（101001）

非均勻調度基本思想：

根據(jù)沖突向量概念，將初始沖突向量中5=0所對

應的時間間隔作為第2個任務的輸入時刻，但5=0所

對應的時間間隔并不一定能作為第3個任務的輸入時

亥I」。通常，根據(jù)初始沖突向量輸入第2個任務后，又

會產(chǎn)生新的沖突向量，然后由這個新的沖突向量再決

定第3個任務在什么時刻輸入等等。按照此思路，選

擇各種可能的時鐘周期數(shù)（時間間隔）輸入新的任務,

產(chǎn)生新的沖突向量，此過程一直進行到不再產(chǎn)生不同

的新的沖突向量為止。在此基礎上進行的非線性流水

線調度，則不會產(chǎn)生段的爭用沖突。

新的沖突向量產(chǎn)生方法：

隨著流水線中第1個任務每個時鐘周期向前推進

一段，原先禁止第2個任務輸入流水線的各種間隔時

鐘數(shù)均應減去1,這相當于將初始沖突向量右移1位,

左邊空位補“0、動態(tài)形成當時的沖突向量。隨著

任務在流水線中的推進，會不斷地形成當時的沖突

向量。

新的沖突向量=當時的沖突向量v初始沖突向量

其中，7'為按位或操作。

例：已知初始沖突向量C=(101001),貝IJ：

(a)選擇第2個任務間隔2個時鐘周期輸入流水線，當

時的沖突向量為：(001010),新的沖突向量為：

(001010)V(101001)=(101011)

(b)選擇第2個任務間隔3個時鐘周期輸入流水線，當

時的沖突向量為：(000101),新的沖突向量為：

(000101)V(101001)=(101101)

(c)選擇第2個任務間隔5個時鐘周期輸入流水線，當

時的沖突向量為：(000001),新的沖突向量為：

(000001)V(101001)=(101001)

非線性流水線狀態(tài)轉移圖

圖中，兩個沖突向量之間有向弧上的數(shù)字為引

入后繼任務的時間間隔數(shù)，對于圖中的多種閉合回

路，按其中的任何一個回路進行流水線調度都不會

產(chǎn)生段爭用沖突。

最佳調度方法：

表中給出了各回路的平均時間間隔數(shù)，顯然按

其中的最小者進行調度，流水線的存吐率最高，即

所謂最佳調度。

調度方法平均時間間隔TAPxmax

(5)51/(5At)

(2,3),(3,2)2.52/(5At)

(2,5),(5,2)3.52/(7At)

(3,5),(5,3)4l/(4At)

(2,3,5),(3,2,5)3.333/(10At)

按(2,3)非均勻調度

n=5,TP=5/(17At)

最優(yōu)調度方法獲得最優(yōu)調度策略的步驟是：

(1)根據(jù)處理對象對流水線各段的使用時間要

求建立一個預約表。

(2)由預約表得出禁止表，禁止表是禁止后續(xù)

對象流入流水線的時間間隔的集合。

(3)由禁止表得出初始沖突向量。

(4)由初始沖突向量得出狀態(tài)有向圖。

(5)由狀態(tài)有向圖得出最優(yōu)調度策略。有向圖

的任何一條環(huán)路都是一個可用的無沖突調度策

略，從中選擇一個平均時間間隔最小的調度策

略就是最優(yōu)調度策略。

練習：

在一個5段的流水線處理機上需經(jīng)過9Z\t才能完

成一個任務，各段執(zhí)行時間均為43任務處理過程對

各段使用時間的預約表如下所示：

x

s1x

x

S2x

XXX

XX

XX

按最優(yōu)調度策略輸入6個任務，求流水線的實際

吞吐率和加速比。

第三部分

并行計算機互連網(wǎng)絡

并行計算性能評測

并行計算機是由一組處理單元組成的，這組處

理單元通過相互之間的通信與協(xié)作，以更快的速度

共同完成一項大規(guī)模的計算任務。因此，并行計算

機的兩個最主要的組成部分是計算節(jié)點和節(jié)點間的

通信與協(xié)作機制。并行計算機體系結構的發(fā)展也主

要體現(xiàn)在計算節(jié)點性能的提高以及節(jié)點間通信技術

的改進兩方面。

?并行計算(處理)機的組成

大多數(shù)并行處理機都由一定數(shù)量的處理單元

(PE),一定數(shù)量的存儲體(M),某種形式的互連網(wǎng)絡

(ICN),和某種形式的控制部件(CU)組成。根據(jù)這

些部件不同的連接方法以及不同的相互作用方法，

可構成兩種典型的并行處理機結構。

控

制

具有分布存儲器的并行處理機結構

>sc

sc：管理處理機

控CU：控制部件

制

PEi：處理單元

ICN：互連網(wǎng)絡

全局存儲器

I/O-CH：I/O通道

I/O：I/O設備

SM：外存儲器

具有共享存儲器的并行處理機結構

SIMD和MIMD計算機都使用了各種形式的互連

網(wǎng)絡，從而實現(xiàn)處理器之間的通信和協(xié)同工作。每

種并行計算機體系結構分別使用不同的互連網(wǎng)絡方

式。在分布式存儲器SIMD體系結構中，互連網(wǎng)絡物

理地連接這些處理器，從而使處理器將數(shù)據(jù)按某種

順序存儲在寄存器中。在共享存儲器SIMD計算機中,

互連網(wǎng)絡為不同的處理器提供了直接訪問不同存儲

模塊數(shù)據(jù)的功能。在分布式存儲器結構中，互連網(wǎng)

絡物理地連接系統(tǒng)中的CPU,并且在CPU之間直接提

供顯式的發(fā)送和接收通信的功能。在共享存儲器

MIMD系統(tǒng)中，互連網(wǎng)絡為CPU提供訪問系統(tǒng)中所有

存儲模塊的功能，處理器通信通過讀寫共享存儲器

來實現(xiàn)。因此，互連網(wǎng)絡的目的就是為了把信息可

靠地傳輸?shù)秸_的目的地。

?靜態(tài)與動態(tài)互連網(wǎng)絡

靜態(tài)互連網(wǎng)絡各結點之間的連接是固定的，不能

重新組合。

所謂靜態(tài)網(wǎng)絡是指處理單元間有著固定連接的一

類網(wǎng)絡，在程序執(zhí)行期間，這種點到點鏈接保持不

變。典型的靜態(tài)網(wǎng)絡有：一維線性陣列、二維網(wǎng)孔、

樹連接、超立方網(wǎng)絡、立方環(huán)、洗牌交換網(wǎng)、蝶形

網(wǎng)絡等。

所謂動態(tài)網(wǎng)絡是用開關單元構成的，可按應用程

序的要求動態(tài)地改變連接組態(tài)。典型的動態(tài)網(wǎng)絡包括:

總線、交叉開關和多級互連網(wǎng)絡等。

互連網(wǎng)絡具有三大要素抑結點間互連拓撲（包含

連接通路）、開關元件和控制方式。在不同的系統(tǒng)中，

開關元件所處的物理位置可能是不同的。

互連網(wǎng)絡的直接作用是建立機間連接通路?；ミB

網(wǎng)絡有兩種形式。一種是非共享連接通路，即結點與

結點直接相連，非直接相連的結點之間的通信經(jīng)過中

間結點轉送。另一種是共享連接通路，即多個結點相互

間經(jīng)過開關元件相連，以建立可變的連接通路，同一路

徑段通過開關元件的選擇在不同時刻可為不同的結點

對服務，達到共享的目的。

不同網(wǎng)絡之間的差異主要表現(xiàn)在以下幾

個方面：

(1)編址方案。

(2)最大分組尺寸。

(3)網(wǎng)絡訪問機制。

(4)超時機制。

(5)差錯恢復。

(6)狀態(tài)報告。

(7)路由選擇。

(8)用戶訪問控制。

(9)連接和無連接服務。

?靜態(tài)互連網(wǎng)絡的幾個性能參數(shù)

定義1:射入或射出一個節(jié)點的邊數(shù)稱為節(jié)點度。

定義2：網(wǎng)絡中任何兩個節(jié)點之間的最長距離（最大路

徑數(shù)）稱為網(wǎng)絡直徑。

定義3：如果從任一節(jié)點看網(wǎng)絡都一樣，則稱網(wǎng)絡為對

稱的。

定義4：對分網(wǎng)絡各半所必須移去的最少邊數(shù)稱為對剖

寬度。

網(wǎng)絡名稱網(wǎng)絡規(guī)模節(jié)點度網(wǎng)絡直徑對剖寬度對稱鏈路數(shù)

線性陣列N個節(jié)點2N-11非N-1

環(huán)形N個節(jié)點2l_N/2_|（雙向）2是N

星形N個節(jié)點N-12LN/2J非N-1

超立方N=2n個節(jié)點nnN/2是nN/2

?互連網(wǎng)絡的定義和模型

定義：互連網(wǎng)絡是一種由開關元件按一定的拓撲

結構和控制形式構成的網(wǎng)絡。

模型：互連網(wǎng)絡可以表示為一個三元組(N,M,C),

N為輸入端數(shù)，M為輸出端數(shù)，C為連接能力，即

網(wǎng)絡能同時實現(xiàn)的連接的最大數(shù)目。

輸輸

入c出

端端

控制機制

?互連函數(shù)

(a)恒等互連

I(Xn-lXn-2…X1X。)=..X^Q

(b)交換(方體)互連

Ck(Xn-l…Xk+1XkXk-l???XO)=Xn-1???Xk+1XkXk-l???XO^

(C)混洗互連

0(Xn-lXn-2???XiXo)=Xn.2...X^Q

(d)蝶式互連

B(Xn/Xn.2???XiXo)=X。Xn.2...X^

(e)反位序互連

P(Xn-lXn_2???XiXo)=X。X】???Xn.2X”/

例：

000——000000000000000

001——001001001001001

010——010010010010010

Oil——OilonononOil

100——100100100100100

101——101101101101101

110——110110110110110

111——111111111111111

(

I(X2X1XO)=x2x1x0ox2x1x0>x1x0x2P(X2X1X0>X0X/2

c0(x2x1x0)=x2x1x0B(X2X1X0>X0X1X2

?單級互連網(wǎng)絡

例：單級立方體網(wǎng)絡

010011010011010011

100101100101100101

c0a

單級立方體互連網(wǎng)絡函數(shù)：

Cube={孰，CPC2,1}

?多級互連網(wǎng)絡

單級互連網(wǎng)絡只能實現(xiàn)有限的幾種基本

連接，并不能實現(xiàn)任意處理器之間的連接。

基本構件：交叉開關。

下播

例：多級立方體網(wǎng)絡

o

1AEI

2

3

出

入

端

端4

5

6

7

直

連

級o

換

交

ABCD=1,EFGH=1,IJKL=1n(07)(16)(25)(34)

級控制信號(K^KQ)

000001010011100101110111

001234567

110325476

入223016745

端332107654

號445670123

554761032

667452301

776543210

4組2元

4組2元2組4元+4組2元

恒等4組2元+2組4元+2組4元+1組8元

2組4元1組8元+1組8元

1組8元

例：多級混洗交換（Omega）網(wǎng)絡

o0

11

22

入33出

端端

44

55

66

77

級012

立方體網(wǎng)絡可以同時實現(xiàn)5到0,7到1的連接，Omega網(wǎng)絡可以

同時實現(xiàn)0到5,1到7的連接。

并行計算性能評測

并行計算的性能評測與并行計算機體系結構、

并行計算和并行程序設計一道構成了“并行計算”

研究的四大分支。

?幾個性能參數(shù)

(1)粒度：是各個處理機可獨立并行執(zhí)行的任務大小

的度量。大粒度反映可并行執(zhí)行的運算量大，亦稱

為粗粒度。指令級并行等則是小粒度并行，亦稱為

細粒度。

(2)加速比：串行執(zhí)行時間為Ts,使用q個處理機并

行執(zhí)行的時間為Tp(q),則加速比為

Sp(q)=Ts/7p(q)

(3)效率:設q個處理機的加速比為Sp(q),則并行算

法的效率

Ep(q)=Sp(q)/q

(4)性能：求接一個問題的計算量為I/IA執(zhí)行時間為了,

則性能(FLOP⑸為

Perf=W/T

在80年代，使用FLO■為單位，90年代，使

用MFLOP/s和GFLOP/s,27世紀普遍使用

GFLOP/s和TFLOP/s,目前也逐漸開始使用

PFLOP/s。

?計算機性能的評測

怎樣評測一臺計算機的性能，與測試者

所處的角度有關。計算機用戶說機器很快，

往往是因為程序運行時間少；而計算中心管

理員說機器很快，則往往是因為在一段時間

里它能夠完成更多的任務。用戶關心的是響

應時間，即從事件開始到結束之間的時間，

也稱為執(zhí)行時間；而管理員關心的是如何提

高流量，即在單位時間內所能完成的工作量。

為了比較不同設計的差別，通常要對兩

臺機器的性能進行比較。假設這兩臺計算機為

X和Y,“X比Y快”的含義是：對于給定任務，X的

響應時間比丫少o"X比Y快n倍”是指：

響應時間y

=n

響應時間x

由于響應時間與性能成反比，又有：

1

口向應時間y，性育旨y，性育旨管

口向應日寸間牙1，性育旨y

，性能X

響應時間最直觀的定義是計算機完成某一任務

所花費的全部時間，包括訪問磁盤、訪問存儲器、

輸入/輸出、操作系統(tǒng)開銷等。

?加速比性能定律

在不同計算對象和資源約束條件下，有三種加速

比模型：適用于固定負載的Amdahl定律（1967）、適用

于可擴展問題的Gustafson可擴展加速比定律（1988）、

受限于存儲器的Sun與Ni加速比模型（1993）。

（1）并行度

并行計算機執(zhí)行一個程序可以在執(zhí)行過程的不同

時間范圍內使用不同數(shù)目的處理機，我們將每個時間

范圍內用來執(zhí)行程序的處理機數(shù)目稱為并行度（DOP）o

并行度反映了軟件并行性與硬件并行性匹配的程

度，這是一個離散時間函數(shù)，只取非負整數(shù)。

DOP的時間函數(shù)曲線稱為一給定程序的并行性分

布圖。

算法的并行度是指該算法中可并行執(zhí)行的操作次

數(shù)。

(2)并行系統(tǒng)的加速比

并行系統(tǒng)的加速比是指對于一個給定的應用，并

行算法(或并行程序)的執(zhí)行速度相對于串行算法

(或串行程序)的執(zhí)行速度加快了多少倍。

加速比=Ts/Tp

(3)Amdahl定律

Amdahl定律指出：加快某部件執(zhí)行速度所獲得

的系統(tǒng)加速比，受限于該部件在系統(tǒng)中的重要性。

Amdahl定律即可以用來確定系統(tǒng)中對性能限制

最大的部件，也可以用來計算通過改進某些部件所獲

得的系統(tǒng)性能的提高。Amdahl定律是研究并行系統(tǒng)

中最基本的定律之一。

假定對機器進行某種改進,那么機器系統(tǒng)的加

速比就是：

力少|土一改進后系統(tǒng)的性能改進前總執(zhí)行時間

系統(tǒng)加速比==

改進前系統(tǒng)的性能改進后總執(zhí)行時間

系統(tǒng)加速比告訴我們改進后的機器比改進前快多

少倍。系統(tǒng)加速比與兩個因素有關：

(1)計算機執(zhí)行某個任務的總時間中可被改進部分的

時間所占的百分比，記為冗，它總是小于1。例如，

一個需運行60s的程序中有20s的運算可以加速，那么

該比例就是20/60。

(2)改進部分采用改進措施后比沒有采用改進措施前

性能提高的倍數(shù)，記為，，它總是大于1。例如，系

統(tǒng)改進后執(zhí)行程序，其中可改進部分花費的時間為2s,

而改進前該部分需花費的時間為5s,則性能提高為

5/2o

改進后整個任務的執(zhí)行時間1口為：

F

T

n=T。。-Fe+U

式中，1為改進前整個任務而執(zhí)行時間。

改進后整個系統(tǒng)的加速比Sp為：

To1

S==

Tn(1-Fe)+Fe/Se

式中，(1-Fe)表示不可改進部分。當Fe為0,即

沒有可改進部分時，Sp為1,所以性能的提高幅度受

改進部分所占比例的慎制。當Se-00,貝IJS”-。

Amdahl定律

?系統(tǒng)加速比依賴于兩個因素：

?“可改進比例”：可改進部分在原系統(tǒng)計算時間中所

占的比例，它總是小于等于1的。

?“部件加速比”可改進部分改進以后的性能提高，一

般情況下它是大于1的。

Amdahl定律

i

s=

(i-/J+-

se

Amdahl定律練習

例：假設在某程序的執(zhí)行過程中，浮點操作時間

占整個執(zhí)行時間的10%,現(xiàn)希望對浮點操作加速。

-設對浮點操作的加速比為與。請畫出程序總的加

速比S和y之間的關系曲線；

-請問程序的最大加速比可達多少?

Amdahl定律練習

I(i-/J+f

sf

i

—10%

1(1-10%)+

Smax_lim01S/

000.9+

s,1

—0.1

=10/90.9+——

S,

例1：假設系統(tǒng)某一部件的處理速度加快9倍，但該部

件的原處理時間僅為整個運行時間的45%,則采用加

快措施后能使整個系統(tǒng)的性能提高多少？

由題意Fe=0.45,Se=9

則11

二二

SP?1.56

0.55+0.45/90.64

例2:如果想用100個處理器達到80的加速比，求原計

算程序中串行部分所占比例。

由Amdahl定律

（I一E皿舞翱口F糊）+（E卯翅氈5爾糊\鐳彤川彝爾）

皿厚爾=

I

假設并行模式下的理論加速比即為處理器的個

數(shù)，加速部分的比例即并行部分所占的比例，代入

上式：