《計算機系統(tǒng)結構(第五版)》課件-第6章

6.1向量的流水處理和向量流水處理機6.2陣列處理機的原理

6.3SIMD計算機的互連網(wǎng)絡6.4共享主存構形的陣列處理機中并行存儲器的無沖突訪問6.5脈動陣列流水處理機

6.6本章小結

6.1向量的流水處理和向量流水處理機

6.1.1向量的處理和向量的流水處理雖然向量運算比標量運算更易發(fā)揮出流水線的效能，但處理方式選擇不當也不行?！纠?-1】

計算D=A×(B+C)，其中A、B、C、D都是有N個元素的向量，應該采用什么方式處理才能充分發(fā)揮流水線的效能

如果采用逐個求D向量元素的方法，即訪存取ai、bi、ci元素求di，再取ai+1、bi+1、ci+1求di+1，則這種處理方式稱為橫向(水平)處理方式。6.1.2向量流水處理機的結構舉例

向量流水處理機的結構因具體機器的不同而不同。

圖6-1只畫出了CRAY-1中央處理機中有關向量流水處理部分的簡圖。圖6-1CRAY-1的向量流水處理部分簡圖

CRAY-1有標量類和向量類指令共128條，其中有4種向量指令如圖6-2所示。

第Ⅰ種源向量分別取自兩個向量寄存器組Vj、Vk，結果送向量寄存器組Vi。第Ⅱ種與第Ⅰ種的差別只在于它的一個操作數(shù)取自標量寄存器Sj。圖6-2CRAY-1的四種向量指令6.1.3通過并行、鏈接提高性能

一般可采取讓多個流水線功能部件并行、流水線鏈接、加快條件語句和稀疏矩陣處理、加快向量的歸約操作等辦法來提高向量流水處理的性能。以CRAY-1的向量流水為例，向量寄存器組Vi在同一時鐘周期內可接收一個結果分量并為下次操作再提供一個源分量。每個Vi組都有單獨的總線連到各功能部件上，而每個

功能部件也都有把運算結果送回向量寄存器組的輸出總線。所謂Vi沖突，指的是并行工作的各向量指令的源向量或結果向量使用了相同的Vi。所謂功能部件沖突，指的是同一個功能部件被要求并行工作的多條向量指令所使用。第一、二條指令無任何沖突，可以并行執(zhí)行。第三條指令與第一、二條指令出現(xiàn)Vi沖突，存在先寫后讀數(shù)相關，本來是不能并行執(zhí)行的，但若能把第一、二條指令的結果分量直接鏈接進第三條指令所用的功能部件，那第三條指令就能與第一、二條指令在大部分時間內并行。它們的鏈接過程如圖6-3所示。圖6-3通過鏈接技術實現(xiàn)向量指令之間大部分時間并行6.1.4提高向量流水處理速度的其他辦法

1.條件語言和稀疏矩陣的加速處理

當程序中出現(xiàn)條件語句或進行稀疏向量、矩陣運算時，難以發(fā)揮出向量處理的優(yōu)點。

2.向量遞歸操作的加速處理

CRAY-1的向量指令還可以通過讓源向量和結果向量使用同一個向量寄存器組，并控制分量計數(shù)器值的修改，來實現(xiàn)遞歸操作。圖6-4畫出了其部分時間關系示意圖。設源/結果向量寄存器組用V0，另一源向量寄存器組用V1。在指令開始執(zhí)

行前，先把V0的零分量(V00)置“0”。V1置入需要運算的全部浮點數(shù)分量。向量長度寄存器VL的內容假定置為64。圖6-4遞歸向量和的部分時間關系運算結束后，V0中各個分量的內容如下：(V056)=(V048)+(V156)=(V10)+(V18)+(V116)+(V124)+(V132)+(V140)+(V148)+(V156)(V057)=(V049)+(V157)=(V11)+(V19)+(V117)+(V125)+(V133)+(V141)+(V149)+(V157)第八部分(結果部分)(V058)=(V050)+(V158)

=(V12)+(V110)+(V118)+(V126)+(V134)

+(V142)+(V150)+(V158)

(V059)=(V051)+(V159)

=(V13)+(V111)+(V119)+(V127)+(V135)

+(V143)+(V151)+(V159)第八部分(結果部分)(V060)=(V052)+(V160)

=(V14)+(V112)+(V120)+(V128)+(V136)

+(V144)+(V152)+(V160)

(V061)=(V053)+(V161)

=(V15)+(V113)+(V121)+(V129)+(V137)

+(V145)+(V153)+(V161)第八部分(結果部分)(V062)=(V054)+(V162)

=(V16)+(V114)+(V122)+(V130)+(V138)

+(V146)+(V154)+(V162)

(V063)=(V055)+(V163)

=(V17)+(V115)+(V123)+(V131)+(V139)

+(V147)+(V155)+(V163)第八部分(結果部分)6.2.1陣列處理機的構形和特點

1.陣列處理機的構形

陣列處理機有兩種構形，兩者的差別主要在于存儲器的組成方式和互連網(wǎng)絡的作用不同。

構形1

圖6-5是具有分布式存儲器的陣列處理機的構形。

構形2

圖6-6是具有集中式共享存儲器的陣列處理機構形。6.2陣列處理機的原理圖6-5具有分布式存儲器的陣列處理機構形圖6-6具有集中式共享存儲器的陣列處理機構形

2.陣列處理機的特點

陣列處理機的單指令流多數(shù)據(jù)流處理方式和由它產(chǎn)生的特殊結構是以諸如有限差分、矩陣、信號處理、線性規(guī)劃等一系列計算問題為背景發(fā)展起來的。6.2.2ILLIACⅣ的處理單元陣列結構

由于陣列處理機上的并行算法的研究是與結構緊密聯(lián)系在一起的，因此，下面先介紹ILLIACⅣ陣列機上處理單元的互連結構。ILLIACⅣ采用如圖6-5所示的分布存儲器構

形，其處理單元陣列結構如圖6-7所示。圖6-7ILLIACⅣ處理單元的互連結構6.2.3ILLIACⅣ的并行算法舉例

1.矩陣加

陣列處理機解決矩陣加是最簡單的一維情況。兩個8×8的矩陣A、B相加，所得的結果矩陣C也是一個8×8的矩陣。只需把A、B、C居于相應位置的分量存放在同一個PEM內，且在全部64個PEM中，讓A、B和C的各分量地址均對應取相同的地址α、α+1和α+2即可，如圖6-8所示。圖6-8矩陣相加的存儲器分配舉例

2.矩陣乘

矩陣乘是二維數(shù)組運算，比矩陣加要復雜。設A、B和C為3個8×8的二維矩陣，給定A和B，計算C=A×B的64個分量的公式為

其中，0≤i≤7且0≤j≤7。讓J=0~7各部分同時在PE0~PE7上運算，這樣只需K、I二重循環(huán)，速度可提高為原來的8倍，即只需64次乘、加時間。其程序流程圖如圖6-9所示。圖6-9矩陣乘程序執(zhí)行流程圖然而為了讓各個處理單元PEi盡可能只訪問所帶局部存儲器PEMi，以保證高速處理，就必須要求對矩陣A、B、C各分量在局部存儲器中的分布采用如圖6-10所示的方案。圖6-10矩陣乘的存儲器分配舉例

3.累加和

這是一個將N個數(shù)的順序相加轉為并行相加的問題。為得到各項累加的部分和與最后的總和，要用到處理單元中的活躍標志位。只有處于活躍狀態(tài)的處理單元才能執(zhí)行相應的

操作。為敘述方便起見，取N=8，即有8個數(shù)A(I)順序累加，其中0≤I≤7。圖6-11描繪了陣列處理機上累加和的計算過程。最后一列框中的數(shù)字表明各處理單元每次循環(huán)后相加的結果。圖中用數(shù)字0~7分別代表A(0)~A(7)。畫有陰影線的處理單元表示此時不活躍。圖6-11陣列處理機上累加和的計算過程6.3.1互連網(wǎng)絡的設計目標與互連函數(shù)

在SIMD計算機中，無論是處理單元之間，還是處理單元與存儲分體之間，都要通過互連網(wǎng)絡進行信息交換。6.3

SIMD計算機的互連網(wǎng)絡6.3.2互連網(wǎng)絡應抉擇的幾個問題

在確定PE之間通信的互連網(wǎng)絡時，需要對操作方式、控制策略、交換方法和網(wǎng)絡的拓撲結構作出抉擇。

循環(huán)互連網(wǎng)絡的模型如圖6-12所示。圖6-12循環(huán)互連網(wǎng)絡的模型6.3.3基本的單級互連網(wǎng)絡

1.立方體單級網(wǎng)絡

立方體單級網(wǎng)絡(Cube)的名稱來源于圖6-13所示的三維立方體結構。圖6-13三維立方體結構如010只能連到000、011、110，不能直接連到對角線上的001、100、101、111。所以，三維的立方體單級網(wǎng)絡

有3種互連函數(shù)：Cube0、Cube1和Cube2，其連接方式如圖6-14中的實線所示。Cubei函數(shù)表示相連的入端和出端的二進制編號只在右起第i位(i=0，1，2)上0、1互反，其余各位代碼都相同。圖6-14立方體單級網(wǎng)絡連接示意(a)Cube0;(b)Cube1;(c)Cube2

2.PM2I單級網(wǎng)絡

PM2I單級網(wǎng)絡是“加減2i”(PlusMinus2i)單級網(wǎng)絡的簡稱。能實現(xiàn)與j號處理單元直接相連的是j±2i號處理單元，即

其中，(01234567)表示0連到1，與此同時，1連到2，2連到3，……，7連到0。圖6-15只畫出了其中3種互連函數(shù)的情況。PM2-0和PM2-1的連接與PM2+0和PM2+1的差別只是連接的箭頭方向相反而已?？梢娫赑M2I中，0可以直接連到1，2，4，6，7上，比立方體單級網(wǎng)絡只能直接連到1，2，4的要靈活。圖6-15PM2I互連網(wǎng)絡的部分連接圖

3.混洗交換單級網(wǎng)絡

混洗交換單級網(wǎng)絡(ShuffleExchange)包含兩個互連函數(shù)，一個是全混(PerfectShuffle)，另一個是交換(Exchange)。圖6-16表示8個處理單元間的全混連接?？梢钥闯觯溥B接規(guī)律是把全部按編碼順序排列的處理單元從當中分為數(shù)目相等的兩半，前一半和后一半在連接至出端時正好一一隔開。全混互連函數(shù)表示為

Shuffle(Pn-1Pn-2

…P1P0)=Pn-2…P1P0Pn-1

圖6-168個處理單元的全混連接由于單純的全混互連網(wǎng)絡不能實現(xiàn)二進制編號為全“0”和全“1”的處理單元與其他處理單元的連接，因此還需增加Cube0交換函數(shù)。這就是全混交換單級網(wǎng)絡，其N=8的連接如圖6-17所示。其中，實線表示交換，虛線表示全混。圖6-17N=8時全混交換互連網(wǎng)絡連接圖

4.蝶形單級網(wǎng)絡

蝶形單級網(wǎng)絡(Butterfly)的互連函數(shù)為

Butterfly(Pn-1Pn-2…P1P0)=P0Pn-2…P1Pn-1

即將二進制地址的最高位和最低位相互交換位置。

圖6-18為N=8個處理單元之間用蝶形單級互連網(wǎng)絡互連的情況。圖6-188個處理單元的蝶形單級互連6.3.4基本的多級互連網(wǎng)絡

最基本的多級互連網(wǎng)絡就是與上述前3種單級互連網(wǎng)絡相對應組成的多級立方體互連網(wǎng)絡、多級混洗交換網(wǎng)絡和多級PM2I網(wǎng)絡。

1.多級立方體互連網(wǎng)絡

多級立方體互連網(wǎng)絡有STARAN網(wǎng)絡、間接二進制n方體網(wǎng)絡等。以8個處理單元為例，其普遍結構如圖6-19所示。

表6-1列出了三級交換網(wǎng)絡在級控制信號采用各種不同組合情況下所實現(xiàn)的入、出端的連接。圖6-19N=8的多級立方體互連網(wǎng)絡表6-1三級STARAN交換網(wǎng)絡實現(xiàn)的入、出端連接及所執(zhí)行的交換函數(shù)功能(ki為第i級控制信號)從表6-1水平方向不難看出，任何輸入端只要通過不同的級控制信號，總可以接到任何所需要的輸出端上。

當STARAN網(wǎng)絡用作移數(shù)網(wǎng)絡時，采用部分級控制，控制信號分組和控制結果列在表6-2中?？梢钥闯鏊鼈兌际菆?zhí)行各種不同的移數(shù)功能的。表6-2三級移數(shù)網(wǎng)絡能實現(xiàn)的入、出端連接及移數(shù)函數(shù)功能【例6-2】

InteliPSC系統(tǒng)用超立方體將8~128個結點進行互連，每個結點有一臺80286微處理器、一臺80287浮點協(xié)處理器、512KB~4.5MB內存和7片Ethenet收發(fā)器接口芯片(因為

每個結點要接7個鏈路，每個鏈路用1片)。

2.多級混洗交換網(wǎng)絡

多級混洗交換網(wǎng)絡又稱omega網(wǎng)絡，如圖6-20所示。

3.多級PM2I網(wǎng)絡

N=8的多級PM2I網(wǎng)絡的結構如圖6-21所示。

圖6-20

N=8的多級混洗交換網(wǎng)絡圖6-21

N=8的多級PM2I網(wǎng)絡

4.基準網(wǎng)絡

圖6-22所示是N=8的基準網(wǎng)絡。

5.多級交叉開關網(wǎng)絡

多級交叉開關(CLOS)網(wǎng)絡是一種非阻塞式網(wǎng)絡，圖6-23給出了一個三級交叉開關網(wǎng)絡的結構。

圖6-22

N=8的基準網(wǎng)絡圖6-23三級交叉開關網(wǎng)絡的結構圖6-24是一個N(3，2，2)的三級交叉開關網(wǎng)絡。入、出端各有4個，如采用一級交叉開關實現(xiàn)，共需4×4=16個交叉點，每個交叉點為四中選1。這種實現(xiàn)可能比三級交叉開關實現(xiàn)要便宜，盡管每個結點只需二中選1。圖6-24

N(3,2,2)的多級交叉開關互連網(wǎng)絡

6.多級蝶式網(wǎng)絡

圖6-25是由16個8×8交叉開關作為基本構件組成的二級蝶式網(wǎng)絡，級間采用8路混洗，構成了64×64的蝶式互連

再用其與64個8×8的交叉開關擴展構成512×512的三級蝶式互連網(wǎng)絡，如圖6-26所示。圖6-25用8×8交叉開關構造的二級

64×64的蝶式互連網(wǎng)絡圖6-26用8×8交叉開關作為基本構件擴充成

512×512的三級蝶式互連網(wǎng)絡6.3.5全排列網(wǎng)絡

如果互連網(wǎng)絡是從N個入端到N個出端的一到一的映射，就可以把它看成是對此N個端的重新排列，因此互連網(wǎng)絡的功能實際上就是用新排列來置換N個入端原有的排列。

圖6-27就是將三級基準網(wǎng)絡和它的逆網(wǎng)絡連在一起，省出中間重復的一級后構成的全排列網(wǎng)絡，稱此網(wǎng)絡為Benes網(wǎng)絡。圖6-27多級全排列網(wǎng)絡舉例(Benes網(wǎng)絡)

情況1

對一維數(shù)組為例，假定并行存儲器分體數(shù)m為4，交叉存放一維數(shù)組a0，a1，a2，…，如圖6-28所示。6.4共享主存構形的陣列處理機中并行存儲器的無沖突訪問圖6-28一維數(shù)組的存儲(m=4)情況2

對于二維數(shù)組(結論也適用于多維數(shù)組)而言，假設主存有m個分體并行，從中訪問有n個元素的數(shù)組子集。這n個元素的變址跳距對于二維數(shù)組的行、列、主對角線、次對角

線都是不一樣的，但要求都能實現(xiàn)無沖突訪問。如果設m=n=4，一個4×4的二維數(shù)組直接按行存儲的方案則如圖6-29所示。圖6-29

4×4數(shù)組的直接按行存儲(m=n=4)為了能使行或列的各元素都能并行訪問，采取將數(shù)據(jù)在存儲器中錯位存放的方案，如圖6-30所示。圖6-304×4數(shù)組一種錯位存放的方案(m=n=4，δ1=δ2=1)假設n×n的二維數(shù)組在并行存儲器中同一列兩個相鄰元素地址錯開的距離為δ1，同一行兩個相鄰元素地址錯開的距離為δ2，當m取成22P+1(P為正整數(shù))時，實現(xiàn)無沖突訪問的充分條件是讓δ1=2P，δ2=1。圖6-31就是對4×4二維

數(shù)組按上述規(guī)則存儲的一種方案。其中，P=1，m=5，δ1=2，δ2=1。圖6-314×4數(shù)組錯位存放的例子(m=5，n=4，δ1=2，δ2=1)【例6-3】

圖6-32表示了一個4×5二維數(shù)組(元素以列為主序排列)按上述規(guī)則將其存放在m=7的存儲器中的例子。圖6-324×5二維數(shù)組在并行存儲器中存放的例子(m=7，n=6)6.5.1脈動陣列結構的原理

脈動陣列結構是由一組處理單元(PE)構成的陣列。

根據(jù)具體計算的問題不同，脈動陣列可以有一維線形、二維矩陣/六邊形/二叉樹形/三角形等陣列互連構形(如圖6-33所示)，還可以有不少變形。6.5脈動陣列流水處理機圖6-33脈動陣列結構的構形舉例(a)一維線形陣列；(b)二維矩形陣列;(c)二維六邊形陣列；(d)二叉樹形陣列；(e)三角形陣列每個處理單元PE內含一個乘法器和一個加法器，可完成一個內積步運算。每經(jīng)一拍，處理單元可把3個輸入端送來的信息沿三個不同方向，即由左向右的水平方向、由下向上的垂直方向和由左下角到右