第9章并行體系結(jié)構(gòu)9.1計算機體系結(jié)構(gòu)的并行性9.2計算機體系結(jié)構(gòu)的分類9.3陣列處理機和向量處理機9.4互連網(wǎng)絡9.5多處理器系統(tǒng)9.6多計算機系統(tǒng)9.7并行處理面臨的挑戰(zhàn)

9.1計算機體系結(jié)構(gòu)的并行性

并行計算是指同時對多個任務、多條指令或?qū)Χ鄠€數(shù)據(jù)項進行處理。完成并行計算的計算機系統(tǒng)稱為并行計算機系統(tǒng)，它是將多個處理器、多個計算機通過網(wǎng)絡以一定的連接方式組織起來的大規(guī)模系統(tǒng)。在計算機系統(tǒng)中，實現(xiàn)并行機制的途徑有多種，大體上可以歸納為以下四類:

(1)時間重疊。

(2)資源重復。

(3)時間重疊+資源重復。

(4)資源共享。圖9.1計算機體系結(jié)構(gòu)的并行層次

1.片內(nèi)并行

片內(nèi)并行是在計算機體系結(jié)構(gòu)的最底層——芯片內(nèi)部引入的一種并行機制，即并行行為都發(fā)生在一個單獨的芯片內(nèi)部。它實現(xiàn)加速的方法是使芯片在同一時間內(nèi)完成更多的工

作來增加芯片的吞吐量。片內(nèi)并行的第一種形式是指令級并行，允許多條指令在片內(nèi)流水線的不同功能單元上并行執(zhí)行。第二種形式是芯片多線程，在這種并行中，CPU可以在多個線程之間來回切換，產(chǎn)生出虛擬的多處理器。第三種形式是單片多處理器(多核CPU)，即同一個芯片中設(shè)置了兩個或者更多個處理器內(nèi)核，并且允許它們同時運行。

2.協(xié)處理器

協(xié)處理器(Coprocessor)是為減輕主處理器負擔、協(xié)助主處理器完成特定工作的專用處理器，通過主處理器和協(xié)處理器的并行工作使計算機的速度得到提高。

3.多處理器

所有的CPU共享公共內(nèi)存的并行計算機稱為多處理器系統(tǒng)，如圖9.2(a)所示。運行在多處理器上的所有進程能夠共享映射到公共內(nèi)存的單一虛擬地址空間。任何進程都能通過執(zhí)行LOAD或者STORE指令來讀或?qū)懸粋€內(nèi)存字，其余工作由硬件來完成。通過一個進程先把數(shù)據(jù)寫入內(nèi)存然后由另一個進程讀出的方式，兩個進程之間可以進行通信。圖9.2并行體系結(jié)構(gòu)

4.多計算機

多計算機系統(tǒng)是由具有大量CPU但不共享公共內(nèi)存的系統(tǒng)構(gòu)成的。在多計算機系統(tǒng)中，每個CPU都有自己的私有本地內(nèi)存，私有內(nèi)存只能供CPU自己通過執(zhí)行LOAD和STORE

指令來使用，其他CPU則不能直接訪問，這種體系結(jié)構(gòu)也被稱為分布式內(nèi)存系統(tǒng)(DistributedMemorySystem，DMS)，如圖9.2(b)所示。

5.網(wǎng)格與云計算

到目前為止，使具有不同計算機操作系統(tǒng)、數(shù)據(jù)庫和協(xié)議的不同組織一起工作，進而共享資源和數(shù)據(jù)，還是非常困難的。然而，不斷增長的對大規(guī)模組織間協(xié)作的需求引領(lǐng)了

新的系統(tǒng)和技術(shù)的開發(fā)，這些系統(tǒng)和技術(shù)將廣域分布的計算機連接到一起構(gòu)成網(wǎng)格(Grid)。網(wǎng)格系統(tǒng)通過互聯(lián)網(wǎng)(Internet)將各種分散的相關(guān)組織連接在一起，共享計算能力、數(shù)據(jù)和其他資源。網(wǎng)格可以被視為非常大的、國際間的、松散耦合的、異構(gòu)的集群。

9.2計算機體系結(jié)構(gòu)的分類

Flynn于1966年提出了一種今天仍有價值的對所有計算機進行分類的簡單模型，這種分類模型可以為計算機系統(tǒng)設(shè)計制定一個框架，這就是1.4.1節(jié)中介紹的Flynn分類法。根據(jù)被調(diào)用的數(shù)據(jù)流和指令流的并行度，F(xiàn)lynn分類法將計算機歸為以下四類:

(1)單指令流單數(shù)據(jù)流(SingleInstruction-streamSingleData-stream，SISD)。

(2)單指令流多數(shù)據(jù)流(SingleInstruction-streamMultipleData-stream，SIMD)。

(3)多指令流單數(shù)據(jù)流(MultipleInstruction-streamSingleData-stream，MISD)。

(4)多指令流多數(shù)據(jù)流(MultipleInstruction-streamMultipleData-stream，MIMD)。圖9.3計算機分類9.3陣列處理機和向量處理機

9.3.1陣列處理機

陣列處理機屬于分布式內(nèi)存SIMD(DM-SIMD)系統(tǒng)，它由許多在不同數(shù)據(jù)集合上執(zhí)行同樣指令序列、完成同樣功能的完全相同的處理器組成。陣列處理機中的處理器共享一

個控制器(所以它不是通常意義上的獨立CPU)，控制器發(fā)布指令，指令由處理器陣列中的處理器執(zhí)行。因為陣列機中的所有處理器是以步調(diào)一致的方式工作的，所以處理器之間不

需要同步，這就大大簡化了這種系統(tǒng)的設(shè)計。圖9.4陣列處理機結(jié)構(gòu)9.3.2向量處理機

向量處理機屬于SIMD系統(tǒng)，一般采用共享內(nèi)存結(jié)構(gòu)。向量處理機對程序員來說和陣列處理機差不多，在對不同的數(shù)據(jù)元素執(zhí)行相同操作時能大幅度提高運算速度。不同的是，

它的所有加法運算都由一個單獨的高度流水的加法器實現(xiàn)。由SeymourCray創(chuàng)建的CrayResearch公司(現(xiàn)在是SGI公司的一部分)制造了許多向量處理機，最早的Cray-1在1974年推出。向量指令具有以下幾個重要特性:

(1)一條向量指令規(guī)定了相當于一個完整循環(huán)所做的工作，每條指令代表數(shù)十或數(shù)百個操作，因此指令獲取和譯碼的帶寬必須足夠地寬。

(2)向量指令使結(jié)果的向量元素計算是互不相關(guān)的，因此硬件在一條向量指令執(zhí)行期內(nèi)不必檢查數(shù)據(jù)相關(guān)(冒險)?？梢岳貌⑿械墓δ懿考嚵?、單一的深度流水的功能部件或者并行和流水的功能部件的組合來計算向量的各元素。

(3)硬件僅需要在兩條向量指令之間對每個向量操作數(shù)檢查一次數(shù)據(jù)相關(guān)，而不需要對向量的每個元素進行檢查。這意味著兩條向量指令之間需要的相關(guān)性檢查邏輯大致與兩條

標量指令之間需要的相同。

(4)如果向量元素是全部毗鄰的，向量指令訪問存儲器的最好模式是從一組交叉存取的存儲塊中獲取向量，這樣，對整個向量而言僅有一次等待主存的代價。

(5)由于整個循環(huán)由預先確定行為的向量指令所替代，所以通常由循環(huán)分支產(chǎn)生的控制相關(guān)(冒險)是不存在的。

1.基本的向量體系結(jié)構(gòu)

向量處理器典型地由一個普通的流水線標量單元加上一個向量單元組成。向量單元內(nèi)的所有功能部件有幾個時鐘周期的等待時間(Latency)，這樣，更短的時鐘周期就可以與具

有深度流水而不產(chǎn)生冒險的較長運行時間的向量運算相適應。標量單元基本上與先進的流水線CPU相同，且商用向量機已內(nèi)置了亂序標量單元(NECSX/5)和VLIW標量單元(Fujitsu

VPP5000)。多數(shù)向量處理器允許以浮點數(shù)、整數(shù)或者邏輯數(shù)據(jù)處理向量。向量-寄存器處理器的基本組成如圖9.5所示，它是以Cray-1為基礎(chǔ)的一個模型，標量部分是MIPS，向量部分是MIPS的邏輯向量擴展，其主要模塊功能如下:

(1)向量寄存器組。

(2)向量功能單元。

(3)向量Load-Store部件。

(4)標量寄存器組。圖9.5基本的向量-寄存器體系結(jié)構(gòu)我們利用一個典型的向量問題來說明向量處理機是如何工作的。假設(shè)我們要做如下的向量運算:

Y=a×X+Y

(9-1)

其中，X和Y是向量，最初存于存儲器中，a是標量。該運算是形成Linpack基準(benchmark)程序內(nèi)部循環(huán)的所謂SAXPY或DAXPY循環(huán)。SAXPY代表單精度a×X+Y，DAXPY

代表雙精度a×X+Y。圖9.6計算DAXPY算法

2.現(xiàn)代的向量超級計算機CrayX1

CrayX1和NECSX/8代表了現(xiàn)代向量超級計算機的技術(shù)水平。X1系統(tǒng)結(jié)構(gòu)支持數(shù)以千計的強大的向量處理器，這些向量處理器共享單一的全局存儲器。圖9.7

CrayMSP模塊圖9.8

CrayX1節(jié)點9.4互連網(wǎng)絡

9.4.1基本概念

互連網(wǎng)絡(InterconnectionNetwork)是一種由開關(guān)元件按照一定的拓撲結(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡，用于實現(xiàn)計算機系統(tǒng)中部件之間、處理器之間、部件與處理器之間甚至計

算機之間的相互連接，根據(jù)連接的設(shè)備數(shù)和設(shè)備的接近程度，可以將互連網(wǎng)絡分為以下四類:

(1)片上網(wǎng)(On-ChipNetwork，OCN)。

(2)系統(tǒng)/存儲區(qū)域網(wǎng)(System/StorageAreaNetworks，SAN)。

(3)局域網(wǎng)(LocalAreaNetworks，LAN)。

(4)廣域網(wǎng)(WideAreaNetworks，WAN)。

9.4.2網(wǎng)絡拓撲結(jié)構(gòu)

典型的網(wǎng)絡拓撲結(jié)構(gòu)有總線結(jié)構(gòu)、集中式交換網(wǎng)絡結(jié)構(gòu)和分布式交換網(wǎng)絡結(jié)構(gòu)。

1.總線

最簡單的互連網(wǎng)絡就是總線，如圖9.9所示。圖9.9總線互連結(jié)構(gòu)圖9.10卡內(nèi)基·梅隆大學的Cm*層次總線結(jié)構(gòu)

2.集中式交換網(wǎng)絡

1)交叉開關(guān)網(wǎng)絡

交叉開關(guān)(CrossbarSwitch)技術(shù)來源于電話網(wǎng)絡中采用的電路交換技術(shù)。電路交換(CircuitSwitching)專用于在源節(jié)點和目的節(jié)點之間建立通信通道(CommunicationsPath)，通道是在節(jié)點間的一組順序連接的物理鏈路(PhysicalLink)。圖9.11

4×4交叉開關(guān)

例9.1在UMA對稱多處理器系統(tǒng)中，假設(shè)有4個CPU作為互連網(wǎng)絡入端節(jié)點，4個內(nèi)存模塊作為出端節(jié)點，當將它們以圖9.11所示的交叉開關(guān)網(wǎng)絡進行連接時，試分析CPU與

內(nèi)存模塊的連接關(guān)系。

解因為CPU2與內(nèi)存模塊0之間的連線交叉點為閉合的交叉開關(guān)(黑圈)，可表示為

(CPU，內(nèi)存)=(10，00)=1

所以CPU2與內(nèi)存模塊0之間建立了連接。同理，因為(CPU，內(nèi)存)=(00，01)=1，(CPU，內(nèi)存)=(11，11)=1，所以CPU0與內(nèi)存模塊1之間建立了連接，CPU3與內(nèi)存模塊3之間建立了連接。圖9.12用4×4交叉開關(guān)模塊構(gòu)成16×16的兩級交叉開關(guān)網(wǎng)絡

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

另一種組織與控制更為有效的交換網(wǎng)絡是基于a×b交換開關(guān)構(gòu)造而成的。2×2交換開關(guān)是一種最常用的二元開關(guān)，如圖9.13(a)所示，它有兩個輸入和兩個輸出，從任意輸入

線到達的消息都可以交換到任意的輸出線上。圖9.13

2×2的交換開關(guān)圖9.14

Omega網(wǎng)絡多級互連網(wǎng)絡設(shè)計的關(guān)鍵是:

(1)選擇何種交換開關(guān);

(2)交換開關(guān)之間采用何種拓撲連接;

(3)對交換開關(guān)采用何種控制方式。最常選用的交換開關(guān)是2×2交換開關(guān)，因為它結(jié)構(gòu)簡單，容易控制，成本低。級間連接常用的拓撲有全混洗、蝶形、縱橫交叉、立方體連接等。對交換開關(guān)的控制一般有以下四種方式:

(1)整體控制:所有交換開關(guān)使用同一個控制信號控制。

(2)級控制:同一級交換開關(guān)使用同一個控制信號控制。

(3)單元級控制:每個交換開關(guān)分別控制。

(4)部分級控制:同一級中部分交換開關(guān)使用同一個控制信號控制。

例9.2假設(shè)CPU011需要從內(nèi)存模塊110中讀取一個字，試分析Omega網(wǎng)絡為此提供的連接路徑。

解我們利用圖9.15來說明Omega網(wǎng)絡的尋徑過程。圖9.15

Omega網(wǎng)絡尋址示意圖圖9.16

3級Clos網(wǎng)絡圖9.17兩種Bene拓撲結(jié)構(gòu)

例9.3計算使用一級交叉開關(guān)網(wǎng)絡互連4096個節(jié)點與采用2×2、4×4、16×16交換開關(guān)構(gòu)成的MIN互連4096個節(jié)點產(chǎn)生的相對成本。分別考慮單向鏈路的相對成本和開關(guān)的相

對成本，假設(shè)k×k交換開關(guān)的開關(guān)成本與k2成正比。

解使用一級交叉開關(guān)網(wǎng)絡時:

開關(guān)成本與40962成正比;

單向鏈路成本∝輸入節(jié)點與網(wǎng)絡連接的鏈路數(shù)

+輸出節(jié)點與網(wǎng)絡連接的鏈路數(shù)

=4096×2=8192使用k×k交換開關(guān)構(gòu)成MIN時:

3.分布式交換網(wǎng)絡

1)互連網(wǎng)絡的表示及性能參數(shù)

(1)圖?；ミB網(wǎng)絡可用圖表示，該圖是由有向邊或無向邊連接有限個節(jié)點組成的，如圖9.19所示。當一個信息經(jīng)過互連網(wǎng)絡到達接收方時造成的總時間延遲為

(9-2)

(2)互連函數(shù)?；ミB網(wǎng)絡也可以用互連函數(shù)表示，互連

函數(shù)定義為互連網(wǎng)絡輸入輸出端口地址的一對一映射(Bijection)，即

(9-3)互連函數(shù)有以下幾種表示方法:

(1)函數(shù)表示法:用x表示輸入端變量，用f(x)表示互連函數(shù)，如式(9-3)。

(2)表格表示法:適用于規(guī)則和不規(guī)則連接。

(3)循環(huán)表示法:將有輸入/輸出連接且編號能夠銜接并循環(huán)的一組連線的節(jié)點放在一個括號內(nèi)來表示輸入端口與輸出端口的映射關(guān)系。如存在輸入端口→輸出端口的連接為0→2、2→4、4→6、6→0，則有(0246)。

(4)圖形表示法:用連線表示輸入輸出端口的映射關(guān)系。

例9.4在Omega網(wǎng)絡中，級間連接采用了完全相同的全混洗連接，如圖9.18(a)所示，試寫出其互連函數(shù)。

解設(shè)輸入端節(jié)點編號與輸出端節(jié)點編號用二進制編碼pn-1pn-2…p1p0表示，則輸入與輸出節(jié)點全混洗連接關(guān)系可用如下互連函數(shù)表示:

這表示被連接的一對輸入輸出節(jié)點的編碼具有如此關(guān)系:將輸入端節(jié)點編號的二進制編碼循環(huán)左移一位就得到與之相連的輸出端節(jié)點編號的二進制編碼。

例9.5圖9.17給出了兩種Bene拓撲網(wǎng)絡，試分析圖9.17(a)的級間連接模式，并給出圖9.17(b)的級間互連函數(shù)。

解

(1)分析圖9.17(a)的級間連接模式。圖9.18多級互連網(wǎng)絡的級間連接

(2)確定圖9.17(b)的級間互連函數(shù)。

圖9.17(b)的級間連接采用的是蝶形連接，其中第2級的級間連接如圖9.18(b)所示，粗線和細線分別組成一個基本的連線圖形，因其形狀像蝴蝶，故稱為蝶形連接。分析圖9.18(b)輸入輸出節(jié)點編號間的關(guān)系可得出，如果將輸入節(jié)點的二進制地址(編號)的最高位與最低位互換位置，就獲得了與該輸入節(jié)點連接的輸出節(jié)點的二進制地址。設(shè)輸入節(jié)點與輸出節(jié)點二進制地址為pn-1pn-2…p1p0，則互連函數(shù)為

同樣，圖9.17(b)的Bene網(wǎng)的每級均是分組應用蝶形互連函數(shù)的。

2)幾種流行的分布式互連網(wǎng)絡拓撲結(jié)構(gòu)

(1)線性網(wǎng)絡拓撲結(jié)構(gòu)。

圖9.19是一組線性網(wǎng)絡拓撲結(jié)構(gòu)，這組網(wǎng)絡的共同特點是從源節(jié)點到目的節(jié)點只有一條路徑。圖中只畫出了鏈路(邊)和交換節(jié)點(點)，節(jié)點設(shè)備需要通過網(wǎng)絡接口連接到交換節(jié)點上。圖9.19線性網(wǎng)絡拓撲結(jié)構(gòu)

(2)環(huán)形網(wǎng)絡拓撲結(jié)構(gòu)。圖9.20是一組環(huán)形網(wǎng)絡拓撲結(jié)構(gòu)，與線性網(wǎng)絡結(jié)構(gòu)最大的不同是網(wǎng)絡中有一個連接所

有節(jié)點的環(huán)。環(huán)形網(wǎng)絡拓撲結(jié)構(gòu)的最大特點是具有對稱性(Symmetry)，即從任何節(jié)點看到的拓撲結(jié)構(gòu)都是一樣的。對稱拓撲的優(yōu)點是網(wǎng)絡中所有節(jié)點具有相同的連接模式，每個節(jié)點或每條鏈路上的負載(或流量)是均勻分布的，網(wǎng)絡的硬件實現(xiàn)和軟件編程較容易。圖9.20環(huán)形網(wǎng)絡拓撲結(jié)構(gòu)

(3)網(wǎng)格型網(wǎng)絡拓撲結(jié)構(gòu)。圖9.21是一組比較流行的網(wǎng)格型(Grid)網(wǎng)絡結(jié)構(gòu)，屬于二維網(wǎng)絡，有多種變體形式。網(wǎng)格

結(jié)構(gòu)有規(guī)律，易于擴展，其直徑與節(jié)點數(shù)的平方根成正比。許多大型商用系統(tǒng)都使用這種結(jié)構(gòu)，如IlliacⅣ、MPP、DAP、CM-2和IntelParagon等。圖9.21網(wǎng)格型網(wǎng)絡拓撲結(jié)構(gòu)

(4)超立方體網(wǎng)絡拓撲結(jié)構(gòu)。圖9.22是一組超立方體(Hypercube)網(wǎng)絡，也稱為二進制n-立方(Binaryn-cube)網(wǎng)。

n-立方網(wǎng)有N＝2n個節(jié)點，維數(shù)為n，節(jié)點分布在n維空間，

節(jié)點度為n，鏈路數(shù)為N(lbN)/2，直徑為n，對分寬度為N/2。圖9.22超立方體網(wǎng)絡拓撲結(jié)構(gòu)9.4.3常用的互連模式和互連網(wǎng)絡

1.常用互連模式

1)恒等置換(IdentityPermutation)

網(wǎng)絡輸入/輸出映射關(guān)系見圖9.23。圖9.23恒等置換

2)交換置換(ExchangePermutation)

網(wǎng)絡輸入/輸出映射關(guān)系見圖9.24。圖9.24交換置換

3)立方置換(CubePermutation)

其中，k=0~(n－1)，n=lbN，N是節(jié)點數(shù)。圖9.25

C1立方置換

4)全混洗置換(PerfectShufflePermutation)圖9.26全混洗置換

5)逆混洗置換圖9.27逆混洗置換

6)子混洗置換

網(wǎng)絡輸入/輸出映射關(guān)系見圖9.28。圖9.28子混洗置換

7)蝶形置換(ButterflyPermutation)圖

9.29蝶形置換

8)位序顛倒置換(BitReversalPermutation)圖9.30位序顛倒置換

9)移數(shù)置換(ShiftPermutation)圖9.31移數(shù)置換

10)加減2i置換(Plus-minus2iPermutation)

其中0≤x≤N－1，0≤i≤(lbN－1)，N是節(jié)點數(shù)。例:N=8，共有2×lbN=2×3=6個互連函數(shù)，循環(huán)表示為

加減2i置換的特點是輸入端口號與輸出端口號具有循環(huán)移位的關(guān)系，所以也稱為循環(huán)移數(shù)置換，它是移數(shù)置換中k=2i的特例。

PM2+1網(wǎng)絡輸入/輸出映射關(guān)系見圖9.31。PM2±2網(wǎng)絡輸入/輸出映射關(guān)系見圖9.32。圖9.32

PM2±2置換

2.常用互連網(wǎng)絡

1)立方體網(wǎng)絡

立方體網(wǎng)絡見圖9.33，當有N個節(jié)點時，立方體網(wǎng)絡的直徑為n=lbN，有n個互連函數(shù)Cubek(k=0~n－1)，實現(xiàn)的連接是:一條鏈路兩端節(jié)點的編碼有一位相反。圖9.33三維立方體網(wǎng)絡及內(nèi)含的三種互連關(guān)系

2)k-aryn-cube網(wǎng)絡

這是每一維基數(shù)均為k的超立方體網(wǎng)絡。節(jié)點數(shù)為N=kn，節(jié)點度為2n，鏈路總數(shù)為n×kn=nN，對分寬度為2×kn-1，直徑為

互連關(guān)系:節(jié)點(xn-1…xi+1xixi-1…x1x0)與節(jié)點(xn-1…

xi+1((xi±1)modk)xi-1…x1x0)連接。如果鏈路始終連通，則構(gòu)成靜態(tài)互連網(wǎng)絡。

n維立方體網(wǎng)絡是k-aryn-cube網(wǎng)絡的特例(k=2)，網(wǎng)格也是k-aryn-cube網(wǎng)絡的特例(n=2)。

3)STARAN網(wǎng)

STARAN網(wǎng)為多級動態(tài)互連網(wǎng)絡，見圖9.34。端口數(shù)為

N;采用兩功能交換開關(guān)(直通，交換)構(gòu)成多級互連網(wǎng)絡，使用級控方式;互連模式為輸入級恒等置換、級間和輸出級逆混洗置換。與圖9.14的Omega網(wǎng)絡對比可看出，STARAN網(wǎng)恰好是Omega網(wǎng)的逆網(wǎng)絡。圖9.34

N=8的STARAN網(wǎng)當所有交換開關(guān)直通時，實現(xiàn)恒等互連。即N=8時有如下關(guān)系:在N=8的STARAN網(wǎng)中，當控制信號為001時，意味著開關(guān)第0級(控制信號末位控制)上的所有交換開關(guān)處于交換狀態(tài)，其他開關(guān)級上的交換開關(guān)處于直通狀態(tài)。此時，實現(xiàn)的連接是出端號在入端號第0位變反，即

入端號排列:01

23

45

67

出端號排列:10

32

54

76

該網(wǎng)絡稱為STARAN交換網(wǎng)。當控制信號為111時，實現(xiàn)全交換(又稱鏡像交換)，完成對8個端口的一組8元交換，即

入端號排列:01234567

出端號排列:76543210

該網(wǎng)絡稱為STARAN移數(shù)網(wǎng)。

4)多級立方體網(wǎng)

多級立方體網(wǎng)也是動態(tài)互連網(wǎng)絡，見圖9.35。端口數(shù)為

N;采用兩功能交換開關(guān)(直通，交換)，使用單元控制方式;

互連模式為輸入級恒等置換、級間子蝶形置換、輸出級逆混洗置換。圖9.35多級立方體網(wǎng)絡子蝶形置換互連函數(shù)為

當所有交換開關(guān)直通時，實現(xiàn)恒等互連。即N=8時有如下關(guān)系:當A、B、C、D四個開關(guān)交換、其余直通時，實現(xiàn)Cube0互連函數(shù);

當E、F、G、H四個開關(guān)交換、其余直通時，實現(xiàn)Cube1互連函數(shù);

當I、J、K、L四個開關(guān)交換、其余直通時，實現(xiàn)Cube2互連函數(shù)。

采用三種不同的交換開關(guān)控制方式，可以構(gòu)成三種不同的互連網(wǎng)絡:

①采用級控制，可以構(gòu)成交換網(wǎng)。

②采用部分級控制，可以構(gòu)成移數(shù)網(wǎng)。

③采用單元控制，此網(wǎng)絡也稱為間接二進制n-立方體網(wǎng)。

5)Delta網(wǎng)

Delta網(wǎng)見圖9.36。它采用a×b交叉開關(guān)作為交換開關(guān)元件，交換開關(guān)控制方式不限，互連模式為級間a混洗，輸入與輸出恒等。圖9.36

42×32Delta網(wǎng)

9.5多處理器系統(tǒng)

9.5.1

UMA對稱多處理器系統(tǒng)

1.UMA對稱多處理器系統(tǒng)的體系結(jié)構(gòu)

UMA對稱多處理器系統(tǒng)的體系結(jié)構(gòu)如圖9.37所示，多個處理器-Cache子系統(tǒng)共享同一個物理存儲器，存儲器可以按多組方式組織。圖9.37集中式共享存儲器多處理器基本結(jié)構(gòu)

2.多處理器的Cache一致性

假設(shè)有兩個處理器CPU1和CPU2，分別擁有各自的寫直達Cache，用Cache1和Cache2表示。當CPU1和CPU2對同一個存儲器單元X進行讀/寫操作時，如果X的值被CPU1改寫，那么Cache1和存儲器中的副本會被更新，但Cache2卻未更新，這樣，在Cache1和Cache2中就有X單元的兩個不同的副本，出現(xiàn)數(shù)據(jù)在Cache中不一致的狀況。如果此時CPU2讀取X，則它將從Cache2中得到X單元的老數(shù)據(jù)，而不是X單元當前最新的數(shù)據(jù)，從而可能引起處理異常。這就是多處理器的Cache一致性(CacheCoherence或CacheConsistency)問題。產(chǎn)生Cache不一致性的原因主要有三種:

(1)共享數(shù)據(jù)。

(2)進程遷移。

(3)I/O操作。實現(xiàn)Cache一致性協(xié)議的關(guān)鍵在于跟蹤所有共享數(shù)據(jù)塊的狀態(tài)。目前廣泛采用的有兩類協(xié)議，它們采用不同的技術(shù)跟蹤共享數(shù)據(jù):

(1)監(jiān)聽式。

(2)目錄式。

1)監(jiān)聽協(xié)議(SnoopingProtocol)

(1)寫直達協(xié)議。

寫直達協(xié)議是最簡單的Cache一致性協(xié)議，該協(xié)議保證共享存儲器的數(shù)據(jù)總是最新的。該協(xié)議規(guī)定:

①當CPU要讀的字不在Cache中時，發(fā)生讀失效，Cache控制器則把包括該字的一個數(shù)據(jù)塊從共享存儲器讀入Cache(Cache塊一般為32或64字節(jié))。接下來對該數(shù)據(jù)塊的讀

操作就直接在Cache中進行(即讀命中)。

②當發(fā)生寫失效時，被修改的字寫入共享存儲器，但包括該字的數(shù)據(jù)塊不調(diào)入Cache。當發(fā)生寫命中時，修改Cache的同時把該字直接寫入共享存儲器。

(2)MESICache一致性協(xié)議。

為了保證一定的總線流量，人們設(shè)計了另一種Cache操作協(xié)議——寫回協(xié)議。該協(xié)議規(guī)定：

①CPU做寫操作時，修改數(shù)據(jù)寫入Cache塊，但不立刻寫入共享存儲器，在Cache中設(shè)置狀態(tài)以表示該Cache塊中的數(shù)據(jù)是正確的、共享存儲器中的數(shù)據(jù)是過時的。

②僅當需要替換該Cache塊時，將該Cache塊寫回共享存儲器。

MESI協(xié)議規(guī)定每個Cache塊都處于以下四種狀態(tài)之一:

·無效(Invalid)——該Cache塊包含的數(shù)據(jù)無效。

·共享(Shared)——多個Cache中都有這塊數(shù)據(jù)，共享存儲器中的數(shù)據(jù)是最新的。

·獨占(Exclusive)——沒有其他Cache包括這塊數(shù)據(jù)，共享存儲器中的數(shù)據(jù)是最新的。

·修改(Modified)——該塊數(shù)據(jù)是有效的，共享存儲器中的數(shù)據(jù)是無效的，而且在其他Cache中沒有該數(shù)據(jù)塊的副本。①“無效”狀態(tài)的設(shè)置。

②“獨占”狀態(tài)的設(shè)置。

③“共享”狀態(tài)的設(shè)置。

④“修改”狀態(tài)的設(shè)置。

⑤狀態(tài)轉(zhuǎn)換。

圖9.38

MESI協(xié)議簡化狀態(tài)轉(zhuǎn)換圖

2)目錄協(xié)議(DirectoryProtocol)

目錄協(xié)議不需要向所有Cache進行廣播，便于處理器速度和數(shù)量的增加，在大規(guī)模系統(tǒng)中越來越受到青睞。目錄協(xié)議經(jīng)常用在分布式存儲器結(jié)構(gòu)的系統(tǒng)中，但也適用于按組進

行組織的集中式存儲器結(jié)構(gòu)系統(tǒng)。為了達到Cache一致性要求，目錄協(xié)議需要完成兩個基本操作:

①處理讀失效;

②處理共享、未修改的Cache塊的寫操作(處理共享數(shù)據(jù)塊的寫失效由這兩個操作簡單組合而成)。為了實現(xiàn)這些操作，目錄必須跟蹤每個Cache塊的狀態(tài)。最簡單的Cache塊狀態(tài)可定義為以下三種:

·共享——在一個或多個處理器上具有這個數(shù)據(jù)塊的副本，且主存中的值是最新值(所有Cache副本均相同)。

·未緩存——所有處理器的Cache中都沒有該數(shù)據(jù)塊的副本。

·獨占——僅有一個處理器上有該數(shù)據(jù)塊的副本，且已對該塊進行了寫操作，而主存的副本仍是舊的(無效)。這個處理器稱為該塊的擁有者。圖9.39分布在節(jié)點上的目錄結(jié)構(gòu)9.5.2

NUMA對稱多處理器系統(tǒng)

對于處理器數(shù)目較少的多處理器系統(tǒng)，各個處理器可以共享單個集中式存儲器。在使用大容量Cache的情況下，單一存儲器(可能是多組)能夠確保小數(shù)目處理器的存儲訪問得

到及時響應。通過使用多個點對點的連接，或者通過交換機，集中共享存儲器(組)設(shè)計可以擴展到幾十個處理器。隨著處理器數(shù)量的增多以及處理器對存儲器要求的增加，系統(tǒng)的任何集中式資源都會變成“瓶頸”。圖9.40

DM-MIMD系統(tǒng)的基本結(jié)構(gòu)

NUMA系統(tǒng)與其他多處理器系統(tǒng)相比有以下特點:

(1)所有CPU看到的是同一個地址空間;

(2)使用LOAD和STORE指令訪問遠程共享存儲器;

(3)訪問遠程共享存儲器比訪問本地共享存儲器速度慢。圖9.41

SM-MIMD系統(tǒng)框圖9.5.3

SunT1多處理器

T1是Sun公司于2005年作為服務器處理器引入市場的多核處理器。T1特別引人注意的一點是，它是采用線程級并行而不是指令級并行開發(fā)的，它同時使用多核和多線程技術(shù)

來提高吞吐量。

圖9.42給出了T1處理器的組織結(jié)構(gòu)。圖9.42

T1處理器的組織結(jié)構(gòu)

9.6多計算機系統(tǒng)

9.6.1多計算機的概念

1.體系結(jié)構(gòu)

多計算機系統(tǒng)的基本結(jié)構(gòu)如圖9.43所示，它看起來與多處理器系統(tǒng)有些相似，但實際上有本質(zhì)的區(qū)別:多計算機系統(tǒng)為真正意義的DM-MIMD系統(tǒng)，具有多存儲器地址空間。圖9.43多計算機系統(tǒng)的基本結(jié)構(gòu)一般而言，多計算機系統(tǒng)具有以下結(jié)構(gòu)特點:

(1)每個節(jié)點計算機是一個完全獨立的計算機。

(2)采用分布式存儲器結(jié)構(gòu)。

(3)節(jié)點間通信采用消息機制。

(4)它可包容多處理器系統(tǒng)。

2.消息傳遞機制

多計算機系統(tǒng)是一個多內(nèi)存地址空間的機器，不同節(jié)點上的CPU在不同地址空間通信時需要通過顯式地傳遞消息來完成。消息傳遞機構(gòu)根據(jù)網(wǎng)絡協(xié)議，利用不同的消息來請求

特定的服務或進行數(shù)據(jù)傳輸，從而完成通信。目前使用的尋徑方式主要有四種:線路交換、存儲轉(zhuǎn)發(fā)、虛擬直通和蟲蝕尋徑。

(1)線路交換(CircuitSwitch)。該方法是先建立一條從源節(jié)點到目的節(jié)點的物理通路，然后再傳遞消息。該方法造成

的傳輸延遲為

(9-4)

該方法的優(yōu)點是實際通信時間較短，使用緩沖區(qū)少;缺點是建立源節(jié)點到目的節(jié)點的物理通路開銷很大，占用物理通路的時間長。

(2)存儲轉(zhuǎn)發(fā)(StoreandForward)。該方法是為每個節(jié)點設(shè)置一個數(shù)據(jù)包緩沖區(qū)，包從源節(jié)點經(jīng)過中間節(jié)點到達目的節(jié)點。存儲轉(zhuǎn)發(fā)網(wǎng)絡的傳輸延遲與源和目的地之間的距離成正比，即

(9-5)

該方法的優(yōu)點是占用物理通路的時間比較短;缺點是包緩沖區(qū)大，延遲大(與節(jié)點距離成正比)。

(3)虛擬直通(VirtualCutThrough)。這種技術(shù)同存儲轉(zhuǎn)發(fā)分組交換有點類似，只是轉(zhuǎn)發(fā)之前不存儲整個分組。一旦一個字節(jié)到達一個節(jié)點，它就可以沿著路徑轉(zhuǎn)發(fā)到下一個節(jié)點，不必等待整個分組都到達。也就是說，當接收方接收到用作尋徑的消息頭部時，即開始路由選擇。傳輸延遲為

(9-6)當出現(xiàn)尋徑阻塞時，只能將整個消息存儲在尋徑節(jié)點中。

該方法的優(yōu)點是通信延遲與節(jié)點數(shù)無關(guān);缺點是每個節(jié)點需要有足夠大的緩沖區(qū)來存儲最大數(shù)據(jù)包,在最壞的情況下與存儲轉(zhuǎn)發(fā)方式的通信延遲是一樣的，經(jīng)過的每個節(jié)點都發(fā)生阻塞，都需緩沖。

(4)蟲蝕(Wormhole)尋徑。該方法是將數(shù)據(jù)包分割為更小的片(或稱微包)，用頭片直接開辟一條從源節(jié)點到目的節(jié)點的路徑。每個消息中的片以異步流水方式在網(wǎng)絡中向前“蠕動”。當消息的頭片到達一個節(jié)點的尋徑器后，尋徑器根據(jù)頭片的尋徑消息立即做出路由選擇。如果所選擇的通道或者節(jié)點的片緩沖區(qū)不可用，則頭片必須在該節(jié)點的片緩沖區(qū)中等待，其他數(shù)據(jù)片也在原來的節(jié)點上等待。傳輸延遲為

(9-7)該方法的優(yōu)點是:每個節(jié)點的緩沖區(qū)較小，易于VLSI實現(xiàn);有較低的網(wǎng)絡傳輸延遲;通道共享性好，利用率高;易于實現(xiàn)選播和廣播通信方式。其缺點是當消息的一個片被阻塞時，

整個消息都被阻塞，占用了節(jié)點資源。9.6.2大規(guī)模并行處理器系統(tǒng)

1.MPP概述

大多數(shù)MPP系統(tǒng)使用標準的CPU作為它們的處理器，常用的有IntelPentium和Core系列、Oracle/SunSPARC和IBMPowerPC。MPP系統(tǒng)與其他系統(tǒng)的不同之處在于，它使用高性能的定制的高速互連網(wǎng)絡及網(wǎng)絡接口，可以在低延遲和高帶寬的條件下傳遞消息。

2.MPP實例——BlueGene系統(tǒng)

下面以BlueGene/L和BlueGene/P系統(tǒng)為例來說明MPP系統(tǒng)。

IBM在1999年投資1億美元啟動了建造大規(guī)模并行超級計算機BlueGene系統(tǒng)的項目。2001年11月，美國能源部的Livermore國家實驗室和IBM簽署了合作協(xié)議，成為BlueGene

家族第一代機器BlueGene/L的首位用戶。

BlueGene項目的目標是不僅要制造世界上最快的MPP機器，而且還要制造效率最高的機器，具體的指標就是萬億次浮點計算/美元(Teraflops/Dollar)、萬億次浮點計算/瓦

(Teraflops/Watt)和萬億次浮點計算/立方米(Teraflops/m3)。

正因如此，IBM未采用以往MPP的設(shè)計方法，即采用能買到的最快的部件，而是決定生產(chǎn)一種定制的片內(nèi)系統(tǒng)部件，讓它以適中的速度和功耗運行，這樣能夠生產(chǎn)出高密度封裝的巨型機。圖9.44

IBMBlueGene/L處理器芯片內(nèi)部結(jié)構(gòu)圖9.6.3集群

集群(Cluster)并不是一個全新的概念，早在20世紀70年代計算機廠商和研究機構(gòu)就開始了對集群系統(tǒng)的研究和開發(fā)。由于主要用于科學工程計算，所以這些系統(tǒng)并不為大家所熟知。直到Linux集群的出現(xiàn)，集群的概念才得以廣為傳播。

1.集群的定義和分類

簡單地說，集群就是一組計算機。明確地說，集群是由成百上千臺PC或者工作站通過商用網(wǎng)絡連接在一起構(gòu)成的系統(tǒng)。它們作為一個整體向用戶提供一組網(wǎng)絡資源，單個的計算機(系統(tǒng))就是集群的節(jié)點(Node)。集群系統(tǒng)的管理員可以隨意增加和刪改集群系統(tǒng)的節(jié)點。一個理想的集群是，用戶從來不會意識到集群系統(tǒng)底層的節(jié)點，在他們看來，集群是一個系統(tǒng)，而非多個計算機系統(tǒng)。集群系統(tǒng)的主要優(yōu)勢體現(xiàn)在高可擴展性、高可用性、高性能、高性價比。

1)高可用性集群

計算機系統(tǒng)的可用性是通過系統(tǒng)的可靠性(Reliability)和可維護性(Maintainability)來度量的。通常用平均無故障時間(MTTF)來度量系統(tǒng)的可靠性，用平均維修時間(MTTR)來度量系統(tǒng)的可維護性，那么可用性A定義為

(9-8)

表9.4是計算機業(yè)界根據(jù)可用性對計算機系統(tǒng)的分類。高可用性集群就是采用集群技術(shù)來實現(xiàn)計算機系統(tǒng)的高可用性，它致力于提供高度可靠的服務。高可用性集群通常分為兩種:

(1)容錯集群。

(2)負載均衡集群(LoadBalancingClusters)。

2)高性能計算集群

高性能計算是計算機科學的一個分支，它致力于開發(fā)超級計算機，研究并行算法和開發(fā)相關(guān)軟件，為用戶提供單個計算機所不能提供的強大的計算能力。高性能計算主要涉及兩大類問題:

(1)大規(guī)?？茖W計算。如天氣預報、地形分析和生物制藥等。

(2)存儲和處理海量數(shù)據(jù)。如數(shù)據(jù)挖掘、圖像處理和基因測序等。按并行任務間的關(guān)系可以將高性能計算分為:

(1)高吞吐量計算(High-ThroughputComputing)。

(2)分布計算(DistributedComputing)。

2.著名的集群系統(tǒng)

1)Beowulf集群

考慮某些特殊需求(如系統(tǒng)性能)及預算，有些Beowulf集群也采用一些用戶定制的設(shè)備(它們通常由一家廠商提供)。為了區(qū)分這些特殊的系統(tǒng)，通常把Beowulf分為兩大類:

(1)第一類Beowulf集群(CLASSⅠBeowulf)。

(2)第二類Beowulf集群(CLASSⅡBeowulf)。

Beowulf集群一般由四個層次構(gòu)成(見圖9.45):

·硬件:主要是指IntelIA-32架構(gòu)的PC服務器。

·網(wǎng)絡:指用于節(jié)點間通信的局域網(wǎng)(FastEthernet)和并行進程間通信的高速網(wǎng)(Myrinet、Giganet等)。

·軟件:主要指Linux操作系統(tǒng)和用于并行通信的并行編程庫(如MPI、PVM)等。

·并行應用。圖9.45

Beowulf集群組件視圖

2)COW集群

像Beowulf一樣，COW(ClusterOfWorkstation)也是由最常見的硬件設(shè)備和軟件系統(tǒng)搭建而成的，通常也是由一個管理或控制節(jié)點和多個計算節(jié)點構(gòu)成的。

3)Mosix集群

和Beowulf等其他集群相比，Mosix集群是一種非常特別的集群，它致力于在Linux系統(tǒng)上實現(xiàn)集群系統(tǒng)的單一系統(tǒng)映像(SingleSystemImage,SSI)。Mosix集群將網(wǎng)絡上運行Linux的計算機連接成一個集群系統(tǒng)，系統(tǒng)自動均衡節(jié)點間的負載。因為Mosix是在Linux系統(tǒng)內(nèi)核中實現(xiàn)的集群，所以用戶態(tài)的應用程序不需要任何修改就可以在Mosix集群上運行。通常用戶很少會注意到Linux和Mosix的差別，對于用戶來說，Mosix集群就是