陣列處理機(jī)和相聯(lián)處理機(jī)課件

第6章陣列處理機(jī)和相聯(lián)處理機(jī)6.1陣列處理機(jī)的原理6.2SIMD計算機(jī)的互連網(wǎng)絡(luò)6.3并行存儲器的無沖突訪問6.4脈動陣列處理機(jī)第6章陣列處理機(jī)和相聯(lián)處理機(jī)6.1陣列處理機(jī)的1本章要點陣列處理機(jī)的構(gòu)型及特點基本的單級互聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)圖及互聯(lián)函數(shù)兩功能交換開關(guān)及四功能交換開關(guān)多級立方體網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的畫法多級混洗交換網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的畫法并行存儲器的無沖突訪問本章要點陣列處理機(jī)的構(gòu)型及特點21.陣列處理機(jī)的構(gòu)形陣列機(jī)通常由一個控制部件CU、N個處理器單元PE、M個存儲模塊以及一個互連網(wǎng)絡(luò)部件(IN)組成。

根據(jù)存儲器模塊是以分布式方式存取還是集中方式存取，陣列機(jī)可分為兩種基本結(jié)構(gòu)：分布式存儲器的陣列機(jī)和共享存儲器的陣列機(jī)。6.1陣列處理機(jī)的原理6.1.1陣列處理機(jī)的構(gòu)形與特點1.陣列處理機(jī)的構(gòu)形根據(jù)存儲器模塊是3PEM0PE0PEM1PE1PEMN-1PEN-1INCUCUMI/O接口DSC分布存儲器的陣列機(jī)結(jié)構(gòu)

（1）分布式存儲器的陣列機(jī)各個處理單元設(shè)有局部存儲器存放分布式數(shù)據(jù)，只能被本處理單元直接訪問。在控制部件CU內(nèi)設(shè)有一個用來存放程序和數(shù)據(jù)的主存儲器CUM。各個PE同步執(zhí)行來自CU的操作命令，各處理單元通過IN來交換數(shù)據(jù)。PEM0PE0PEM1PE1PEMN-1PEN-1INCUI4…INPE0PE1PEN-1MM0MM1MMK-1CUSCI/O-CHI/OSM……具有共享存儲器的陣列機(jī)結(jié)構(gòu)

（2）集中式共享存儲器的陣列機(jī)每個PE沒有局部存儲器，存儲模塊以集中形式為所有PE共享?；ミB網(wǎng)IN受CU控制，用來構(gòu)成PE和MM的數(shù)據(jù)交換通路，具有雙向性。…INPE0PE1PEN-1MM0MM1MMK-1CUSCI52

陣列機(jī)的特點并行處理機(jī)有如下特點：（1）

利用資源重復(fù)（空間因素）而非時間重疊。（2）

利用同時性而非并發(fā)性。它的每個處理單元在同一時刻要同等地?fù)?dān)負(fù)起各種運(yùn)算功能。（3）提高運(yùn)算速度主要是靠增大處理單元個數(shù)，比起向量流水線處理機(jī)主要依靠縮短時鐘周期來說，速度提高的潛力要大得多（4）使用簡單而又規(guī)整的互連網(wǎng)絡(luò)來確定多個處理單元之間的連接模式。（5）并行處理機(jī)（陣列機(jī)）研究必須與并行算法研究密切結(jié)合，使之適應(yīng)性更強(qiáng)，應(yīng)用面更廣。2

陣列機(jī)的特點并行處理機(jī)有如下特點：66.1.2ILLIAC-IV處理單元陣列結(jié)構(gòu)處理單元陣列由64個PUi構(gòu)成,每個PUi包括(PEi、PEMi和MLU)

由64個結(jié)構(gòu)完全相同的處理單元PEi

構(gòu)成，每個處理單元PEi字長64位，PEMi為隸屬于PEi的局部存儲器，全部PEi由CU統(tǒng)一管理，PEi都有一根方式位線，用來向CU傳送每個PEi的方式寄存器D中的方式位，使CU能了解各PEi的狀態(tài)是否活動，作為控制它們工作的依據(jù)。陣列控制器CU相當(dāng)一臺小型控制計算機(jī)對處理單元陣列實現(xiàn)控制,(發(fā)控制信號,廣播公共地址,(廣播公共數(shù)據(jù))）對指令流進(jìn)行譯碼控制,利用CU內(nèi)部資源可以進(jìn)行標(biāo)量操作,接受和處理各類中斷，其他輸入輸出操作。I/O系統(tǒng)

由磁盤文件系統(tǒng)DFS，輸入輸出子系統(tǒng)和宿主計算機(jī)S/C構(gòu)成6.1.2ILLIAC-IV處理單元陣列結(jié)構(gòu)處理單元陣列7ILLIACⅣ的組成ILLIACⅣ的組成8PU16PU0PU8PU7PU55PU63PU0PU1PU7PU8PU9PU15PU56PU57PU63PU0PU1PU7PU56PU57PU58ILLIAC-IV的處理單元互連結(jié)構(gòu)PU16PU0PU8PU7PU55PU63PU0PU1PU79

特點:

(1)閉合螺線陣列

(2)任意單元的最短距離不超過7步將PU63傳送到PU10，最快可經(jīng)PU63→PU7→PU8→PU9→PU10。

(3)一般來講：個處理單元組成的陣列中，任意兩個處理單元之間的最短距離不會超過步（4）處理單元為通常的累加型運(yùn)算器，把累加寄存器RGA中的數(shù)據(jù)和存儲器來的數(shù)據(jù)進(jìn)行運(yùn)算操作，數(shù)據(jù)傳送寄存器RGR收發(fā)數(shù)據(jù)，實現(xiàn)數(shù)據(jù)在處理單元之間的傳送。特點:10一．矩陣加 矩陣加(配比加)是最簡單的情況。假定兩個8*8的矩陣A、B相加，所得結(jié)果矩陣C也是一個8*8的矩陣。設(shè)A、B的分量元素分別存在PEMi的Z,Z+1單元中,所得結(jié)果矩陣C各分量存在PEMi

的Z+2單元中用下面三條指令可一次完成(64個處理單元并行)LDAZ；全部（Z）由PEMi送到PE的累加器RGAiADRNZ+1；全部（Z+1）與（RGAi）進(jìn)行浮點加，結(jié)果送RGAiSTAZ+2；全部（RGAi）由PE送到PEMi的（Z+2）單元這里0≤i≤63

6.1.3ILLIACⅣ的并行算法舉例一．矩陣加這里0≤i≤636.1.3ILLIAC11矩陣加存儲器分舉例A(0,0)B(0,0)C(0,0)PEM0aa+1a+2A(0,1)B(0,1)C(0,1)PEM1A(7,7)B(7,7)C(7,7)PEM63處理速度為順序處理的64倍矩陣加存儲器分舉例A(0,0)B(0,0)C(0,0)PE12二．矩陣乘a0,0a0,1…a0,7a1,0a1,1…a1,7……a7,0a7,1…a7,7b0,0b0,1…b0,7b1,0b1,1…b1,7……b7,0b7,1…b7,7a0,0×b0,0+a0,1×b1,0+…+a0,7×b7,0…a0,0×b0,7+a0,1×b1,7+…+a0,7×b7,7a1,0×b0,0+a1,1×b1,0+…+a1,7×b7,0…a1,0×b0,7+a1,1×b1,7+…+a1,7×b7,7……a7,0×b0,0+a7,1×b1,0+…+a7,7×b7,0…a7,0×b0,7+a7,1×b1,7+…+a7,7×b7,7=×

如果順序執(zhí)行C=A×B，那么，計算每個元素cij需要做8次乘法，7次加法，共需做15次乘/加運(yùn)算。在ILLIACIV的處理機(jī)上，操作數(shù)B的64個元素存儲在64個PEM中。當(dāng)每次計算元素cij時，就把操作數(shù)A的8個元素aik(0<=k<=7)播送到相應(yīng)的8個PE中，然后并行地一次完成8個中間積的運(yùn)算。最后對8個中間積做7次加法，累加得到cij

。二．矩陣乘a0,0a0,1…a013A(0,0)A(1,0)...A(7,0)B(0,0)B(1,0)...B(7,0)C(0,0)C(1,0)...C(7,0)A(0,1)A(1,1)...A(7,1)B(0,1)B(1,1)...B(7,1)C(0,1)C(1,1)...C(7,1)A(0,7)A(1,7)...A(7,7)B(0,7)B(1,7)...B(7,7)C(0,7)C(1,7)...C(7,7)PE0PEM2PEM7...矩陣乘存儲器分配舉例（設(shè)用八個處理單元即PU并行）………...八個局部存儲器PEMi,每個連續(xù)存放A,B和結(jié)果向量C的一列元素A(0,0)A(1,0)...A(7,0)B(0,0)B(114三、累加和（成對遞歸）這是一個將N個數(shù)的順序相加過程轉(zhuǎn)變?yōu)椴⑿邢嗉舆^程的問題。設(shè)N為8，即有8個數(shù)A（I）順序累加，其中0≦I≦7。

在SISD計算機(jī)上可寫成下列程序：

C=0DO10I=0，7

10C=C+A（I）用成對遞歸算法，只需Log28=3在SIMD計算機(jī)上可寫成下列程序

C=ADO10K=0,Log28-110C=C+SHFTR(C,2**K)

其中SHFTR(C,2**K)是向量傳送語句,C向量各分量向右傳送步距為2的K次冪三、累加和（成對遞歸）這是一個將N個數(shù)的順序相加過程轉(zhuǎn)變?yōu)?5用成對遞歸算法求累加和的步驟：1.置全部PEi為活躍狀態(tài)，0≦i≦7。2.全部A（i）從PEMi的a單元讀到相應(yīng)PEi的累加寄存器RGAi中，0≦i≦7；3.令k=0；4.將全部PEi的（RGAi）傳送到寄存器RGRi，0≦i≦7；5.將全部PEi的（RGRi）經(jīng)過互連網(wǎng)絡(luò)向右傳送2k步距，0≦i≦7；6.令j=2k-1；7.置PE0至PEj為不活躍狀態(tài)；8.處于活躍狀態(tài)的所有PEj執(zhí)行（RGAi）:=(RGAi)+（RGRi），j≦i≦7；9.k:=k+1;10.如k<3,則轉(zhuǎn)回4,否則往下繼續(xù)執(zhí)行;11.置全部PEi為活躍狀態(tài)，0≦i≦7,存結(jié)果至a+1單元。設(shè)原始數(shù)據(jù)A（I）分別存在8個PEM的某a單元中用成對遞歸算法求累加和的步驟：設(shè)原始數(shù)據(jù)A（I）分別存在8個16設(shè)原始數(shù)據(jù)A（I）分別存在PEM的某個單元中步距1步距2步距4K=0K=1K=2PE0A0

A0

A0A0PE1A1A0+A1

A0+A1A0+A1PE2A2A1+A2A0+A1+A2A0+A1+A2PE3A3A2+A3A0+A1+A2+A3A0+A1+A2+A3PE4A4A3+A4A1+A2+A3+A4A0+A1+A2+A3+A4PE5A5A4+A5A2+A3+A4+A5A0+A1+A2+A3+A4+A5PE6A6A5+A6A3+A4+A5+A6A0+A1+A2+A3+A4+A5+A6PE7A7A6+A7A4+A5+A6+A7A0+A1+A2+A3+A4+A5+A6+A7設(shè)原始數(shù)據(jù)A（I）分別存在PEM的某個單元中步距117二、遞歸折疊求和用遞歸折疊方法來求累加和過程如下圖所示。

上述求累加和算法雖然使計算次數(shù)減少，但是速度的提高的倍數(shù)只是N/Log2N，速度并沒有提高多少。PE值步1步2步40A0A0+A1A0+A1+A2+A3A0+A1+A2+A3+1A1A4+A5+A6+A72A2A2+A33A34A4A4+A5A4+A5+A6+A75A56A6A6+A77A78個PE的遞歸折疊求和長度為N的遞歸計算時間正比于Log2N二、遞歸折疊求和用遞歸折疊方法來求累加和過程如下圖所示。18例：A和B都是元素為浮點表示的64×64的二維數(shù)組，一次浮點加法的計算過程由取數(shù)、求階差、對階、尾數(shù)加、規(guī)格化和存數(shù)共6個段組成。若每個段的執(zhí)行時間均為Δt，請分別求出在下列結(jié)構(gòu)不同的處理機(jī)上完成C=A+B所需時間及相對于順序處理的加速比。(1)順序處理方式的處理機(jī)(2)具有浮點加法流水線的流水處理機(jī)，且浮點加法流水線分為6個段，各段執(zhí)行時間均為Δt。(3)8×8的陣列處理機(jī)，且處理陣列上的每個處理器只能順序處理浮點加運(yùn)算。(4)8×8的陣列處理機(jī)，且處理陣列上的每個處理器均能流水處理浮點加運(yùn)算。(4)64×64的陣列處理機(jī)。例：A和B都是元素為浮點表示的64×64的二維數(shù)組，一次浮點19a0,0a0,1…a0,63a1,0a1,1…a1,63……a63,0a63,1…a63,63b0,0b0,1…b0,63b1,0b1,1…b1,63……b63,0b63,1…b63,63+a0,0+b0,0a0,1+b0,1…a0,63+b0,63a1,0+b1,0a1,1+b1,1…a1,63+b1,63……a63,0+b63,0a63,1+b63,1…a63,63+b63,63=解：(1)順序處理方式下，需要順序執(zhí)行的浮點加法次數(shù)為64×64=4096，每次浮點加運(yùn)算所需時間為6Δt

，則全部運(yùn)算所需時間為：T1=4096×6Δt=24576Δt(2)需要流水執(zhí)行的浮點加法次數(shù)為64×64=4096，則一個K=6段浮點加法流水線處理全部運(yùn)算所需時間為：T2=(k+n-1)Δt=(6+4096-1)Δt=4101Δt加速比：S2=T1/T2=5.9a0,0a0,1…a0,63b0,20(3)對于8×8的處理陣列，每個處理器需要處理64×64二維數(shù)組中的一個8×8子數(shù)組，因此，每個處理器需要執(zhí)行的浮點加法次數(shù)為8×8。每次浮點加法運(yùn)算需要時間6Δt

。每個處理器順序執(zhí)行64次浮點加法所需時間為64×6Δt=384Δt。64個處理器并行處理，同時完成各自的64次浮點加運(yùn)算，所以，全部運(yùn)算所需時間為：T3=384Δt加速比：S2=T1/T3=64(4)對于8×8的處理陣列，每個處理器需要處理64×64二維數(shù)組中的一個8×8子數(shù)組，因此，每個處理器需要執(zhí)行的浮點加法次數(shù)為8×8。K=6段的浮點加法流水線處理64次浮點加運(yùn)算需要時間(k+n-1)Δt=(6+64-1)Δt=67Δt

。64個處理器并行處理，同時完成各自的64次浮點加運(yùn)算，所以，全部運(yùn)算所需時間為：T4=67Δt加速比：S2=T1/T4=366.8(3)對于8×8的處理陣列，每個處理器需要處理64×64二維21(5)對于64×64的處理陣列，每個處理器只需執(zhí)行一次浮點加運(yùn)算，所需時間為6Δt

，所以，全部運(yùn)算所需時間為：T5=6Δt加速比：S2=T1/T5=4096(5)對于64×64的處理陣列，每個處理器只需執(zhí)行一次浮點226.2SIMD計算機(jī)的互連網(wǎng)絡(luò)6.2.1互連網(wǎng)絡(luò)的設(shè)計目標(biāo)及互連函數(shù)1.互聯(lián)網(wǎng)絡(luò)的設(shè)計目標(biāo)a.采取讓相鄰的處理單元之間只用有限的幾種直連方式實現(xiàn)任何兩個處理單元之間所需要的信息傳送。b.設(shè)計目標(biāo)：結(jié)構(gòu)不要太復(fù)雜；靈活性高；信息交換所需傳送步數(shù)盡可能少；能用規(guī)整單一的基本構(gòu)件組合而成，模塊性好；6.2SIMD計算機(jī)的互連網(wǎng)絡(luò)6.2.1互連網(wǎng)絡(luò)的設(shè)232.互連函數(shù)

互連網(wǎng)絡(luò)的連接特征一般用一組互連函數(shù)表示?；ミB函數(shù)：出端編碼是入端編碼的排列、組合、移位、取反等操作的結(jié)果。表示所有入端與出端的連接關(guān)系?；ミB函數(shù)有2種表示方法：

(1)輸入輸出對應(yīng)表示法互連01N-1

函數(shù)f(0)f(1)f(N-1)(2)函數(shù)式表示法：

入端編碼表示：x=bn-1…b0n=log2N

出端編碼表示：f(x)=基于bn-1…b0的操作的結(jié)果。自變量和函數(shù)可以用二進(jìn)制表示，也可以用十進(jìn)制等表示輸入:01234567

輸出:103254762.互連函數(shù)互連網(wǎng)絡(luò)的連接特征一般用一組互連函數(shù)表示?；?46.2.2互聯(lián)網(wǎng)絡(luò)的應(yīng)選擇的幾個問題（1）操作方式：有同步、異步、同異組合三種；（2）控制策略：集中和分布兩種；（3）交換方法：有線路交換、包交換及線路與包交換組合三種。（4）網(wǎng)絡(luò)拓?fù)洌夯ヂ?lián)網(wǎng)絡(luò)入、出端可以實現(xiàn)連接的模式。有靜態(tài)和動態(tài)兩種；動態(tài)網(wǎng)絡(luò)又有單級循環(huán)網(wǎng)絡(luò)和多級互連網(wǎng)絡(luò)兩類；6.2.3基本的單級互連網(wǎng)絡(luò)立方體、PM2I和混洗交換和蝶形單級網(wǎng)絡(luò)。

6.2.2互聯(lián)網(wǎng)絡(luò)的應(yīng)選擇的幾個問題6.2.3基本的單25三維立方體結(jié)構(gòu)處理單元ZYX三位二進(jìn)制碼編號

每個處理單元只能直接連到其二進(jìn)制編號的某一位取反的其他3個處理單元上。1.立方體單級網(wǎng)絡(luò)(交換互連網(wǎng)絡(luò))

三維立方體結(jié)構(gòu)處理單元ZYX三位二進(jìn)制碼編號26

互連函數(shù)：Cube0

(b2b1b0)=(b2b1b0)；Cube1(b2b1b0)=(b2b1b0)

Cube2(b2b1b0)=(b2b1b0)。

互連特性：

交換功能--互連函數(shù)可逆；互連函數(shù)個數(shù)=log28=3；最大連接度=log28=3；

結(jié)點最大間距=log28=3。

互連函數(shù)：Cubei函數(shù)表示相連的入端和出端的二進(jìn)制編號只在右起第i位(i=0,1,2)上有差別，即僅在該位上的代碼“0”、“1”互反，其余各位代碼都相同?；ミB函數(shù)：Cube0(b2b1b0)=(b2b1b27立方體單級網(wǎng)絡(luò)連接圖Cube0=(b2b1b0)（0，1）（2，3）（4，5）（6，7）Cube1=(b2b1b0)（0，2）（1，3）（4，6）（5，7）Cube2=(b2b1b0)（0，4）（1，5）（2，6）（3，7）其連接方式如下圖中的實線所示。100110注意：立方體坐標(biāo)編號不能標(biāo)錯。立方體單級網(wǎng)絡(luò)連接圖Cube0=(b2b1b0)（0，128

推廣到n維的情形，N個節(jié)點的立方體單級網(wǎng)絡(luò)共有n=log2N種互連函數(shù)，即

式中，0≤i≤n-1，bi為入端號二進(jìn)制碼的第i位。當(dāng)維數(shù)n＞3時，稱為超立方體(HyperCube)網(wǎng)絡(luò)。它的最大距離為n，任意兩個結(jié)點間有至少n條路徑，容錯性較強(qiáng)。PM2I單級網(wǎng)絡(luò)是“加減2i”

單級網(wǎng)絡(luò)的簡稱。能實現(xiàn)與j號處理單元直接相連的是號為j±2i的處理單元，即2.PM2I單級網(wǎng)絡(luò)推廣到n維的情形，N個節(jié)點的立方體單級網(wǎng)絡(luò)共有29

對于N=8的三維PM2I互連網(wǎng)絡(luò)的互連函數(shù)有PM2+0、

PM2-0、PM2+1、PM2-1、PM2±2等5個不同的互連函數(shù)，它們分別為：PM2+0:(01234567)PM2-0:(76543210)PM2+1:(0246)(1357)PM2-1:(6420)(7531)PM2±2:(04)(15)(26)(37)式中，0≤j≤N-1,0≤i≤n-1,n=log2N。因此，它共有2n個互連函數(shù)。由于總存在PM2+(n-1)=PM2-(n-1)，所以實際上，PM2I互連網(wǎng)絡(luò)只有2n-1種不同的互連函數(shù)。對于N=8的三維PM2I互連網(wǎng)絡(luò)的互連函30PM2I互連網(wǎng)絡(luò)的部分連接圖PM2I互連網(wǎng)絡(luò)的部分連接圖31PM2I單級網(wǎng)絡(luò)的最大距離為[n/2](向上取整)。以上面的三維PM2I互連網(wǎng)絡(luò)的例子就可以看出，最多只要二次使用，即可實現(xiàn)任意一對入、出端號之間的連接。

應(yīng)用：幾種PM2I變換的組合，可實現(xiàn)某結(jié)點到任意結(jié)點的連接，組合不同效率不同。

例：閉合螺旋結(jié)構(gòu)為PM2I±0(橫向)及PM2I±n/2(縱向)互連函數(shù)。PM2I單級網(wǎng)絡(luò)的最大距離為[n/2]323.混洗交換互連網(wǎng)絡(luò)8個處理單元的全混連接這種互連網(wǎng)絡(luò)由全混洗和交換兩種互連函數(shù)組成：全混Shuffle(bn-1bn-2...b1b0)=(bn-2...b1b0bn-1)相當(dāng)于將處理單元的二進(jìn)制地址位中的最左位移到最右位的循環(huán)移位。下圖示出了有8個PE的全混洗連接。0000010100111001011101110010100111001011101110003.混洗交換互連網(wǎng)絡(luò)8個處理單元的全混連接這種互連網(wǎng)33

由于全混洗互連網(wǎng)絡(luò)不能實現(xiàn)全0和全1單元與其他單元的連接，因此引入交換網(wǎng)絡(luò)中的Cube0交換互連函數(shù)，表達(dá)形式如下：

Exchange(bn-1bn-2...b1b0)=bn-1bn-2...b1b0

兩函數(shù)復(fù)合后為：Exchange[Shuffle(bn-1bn-2...b1b0)]=(bn-2...b1b0bn-1)下圖示出了這種混洗交換互連網(wǎng)絡(luò)的連接圖。（實線表示交換，虛線表示全混）N=8時全混交換互連網(wǎng)絡(luò)連接圖

在混洗交換網(wǎng)絡(luò)中，最大距離為2n-1。最遠(yuǎn)的兩個PE（全0和全1

）連接需要n次交換和n-1次混洗。由于全混洗互連網(wǎng)絡(luò)不能實現(xiàn)全0和全1單元與其他單344、蝶式置換--編碼最高位和最低位位交換位置互連函數(shù)：β(bn-1bn-2…b1b0)=(b0bn-2…b1bn-1)；000001010011100101110111N=8蝶式置換000001010011100101110111N=8β(1)子蝶式置換000001010011100101110111000001010011100101110111

子蝶式置換：

β(k)(bn-1…bk+1bkbk-1…b0)=(bn-1…bk+1b0bk-1…b1bk)β(k)(bn-1…bn-kbn-k-1bn-k-2…b0)=(bn-k-1bn-2…bn-kbn-1bn-k-2…b0)4、蝶式置換--編碼最高位和最低位位交換位置000N=355、移數(shù)置換--編碼值移位

互連函數(shù)：α(X)=(X+k)modN，0≤k≤N-1；000001010011100101110111k=1移數(shù)置換000001010011100101110111000001010011100101110111k=2移數(shù)置換000001010011100101110111

互連特性：互連函數(shù)不可逆(k=0除外)；

n位編碼有2n個移數(shù)變換功能。5、移數(shù)置換--編碼值移位000k=1移數(shù)置換000036

例：編號為0、1、…15的16個處理器用單級互連網(wǎng)絡(luò)互連，當(dāng)互連函數(shù)分別為:（1）Cube3

（2）PM2+3（3）PM2+2（Cube1

）（4）Shuffle(Cube2(PM2-3))時，第13號處理器各連至哪一個處理器？解：編號為0、1、..15的16個處理器，所以可用4位二進(jìn)制碼b3b2b1b0

表示。第13號處理器的二進(jìn)制編號為1101。所以（1）

Cube3（1101）=0101，即連接到5號處理器上。（2）PM2+3（13+23）mod16=5，即連接到5號處理器上。（3）PM2+2(Cube1(1101))=3，即連接到3號處理器上。（4）Shuffle(Cube2(PM2-3(13)))=Shuffle(Cube2(0101))=Shuffle（0001）=0010，即連接到2號處理器上。例：編號為0、1、…15的16個處理器用單級互連376.2.4基本的多級互連網(wǎng)絡(luò)交換開關(guān)交換開關(guān)是組成互連網(wǎng)絡(luò)的基本構(gòu)件。通常，它是二功能或四功能的。二功能是直連或交換。四功能就是在二功能基礎(chǔ)上在加上上播和下播，開關(guān)狀態(tài)連接方式如下圖所示；

決定多級互連網(wǎng)絡(luò)的特性的主要因素有以下三個方面：交換開關(guān)、拓?fù)浣Y(jié)構(gòu)和控制方式。

a.直連——i入連i出，j入連j出；b.交換——i入連j出，j入連i出；i入j入i出j出i入j入i出j出6.2.4基本的多級互連網(wǎng)絡(luò)交換開關(guān)決定多級互38c.上播——i入連i出和j出，j入懸空；d.下播——j入連i出和j出，i入懸空。拓?fù)浣Y(jié)構(gòu)是指各級之間出端和入端相互連接的模式?？蓪渭壔ミB網(wǎng)絡(luò)的那些連接模式進(jìn)行不同的組合，構(gòu)成多種不同的多級互連網(wǎng)絡(luò)。i入j入i出j出i入i出j入j出c.上播——i入連i出和j出，j入懸空；d.下播——j入39

控制方式是對各個交換開關(guān)進(jìn)行控制的方式，以多級立方體網(wǎng)絡(luò)為例，它可以有3種：

(1)級控制——同一級的所有開關(guān)只用一個控制信號控制，同時只能處于同一種狀態(tài)；

(2)單元控制——每一個開關(guān)都有自己獨立的控制信號控制，可各自處于不同的狀態(tài)；

(3)部分級控制——對不同的級采用不同數(shù)量的控制信號。第i級的所有開關(guān)分別用i+1個信號控制，0≤i≤n-1,n為級數(shù)。是前面兩種方式的折衷?？刂品绞娇刂品绞绞菍Ω鱾€交換開關(guān)進(jìn)行控制的方式，以多401.多級立方體網(wǎng)絡(luò)（STARAN和間接二進(jìn)制n方體網(wǎng)絡(luò)）以8個處理單元為例，其結(jié)構(gòu)如下圖所示。共同特點：第i級交換單元處于交換狀態(tài)時，實現(xiàn)的是Cubei互連函數(shù)，且都采用二功能交換單元。區(qū)別：控制方式不同，STARAN網(wǎng)絡(luò)采用級控制和部分級控制，間接二進(jìn)制n方體網(wǎng)絡(luò)采用單元控制。

常用的多級互連網(wǎng)絡(luò)有：多級立方體網(wǎng)絡(luò)、多級混洗交換網(wǎng)絡(luò)又稱omega網(wǎng)絡(luò)和多級PM2I網(wǎng)絡(luò)。1.多級立方體網(wǎng)絡(luò)（STARAN和間接二進(jìn)制n方體網(wǎng)絡(luò)41N=8多級立方體互連網(wǎng)絡(luò)Cube0Cube1Cube2N=8多級立方體互連網(wǎng)絡(luò)Cube0Cube1Cube242

具有N個入端和N個出端的多級立方體網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的畫法為：先求出該多級立方體網(wǎng)絡(luò)的級數(shù)n，每級畫N/2個二功能交換開關(guān)；級編號從輸入到輸出依次是：0,1,…i…n-1;讓所有第i級各交換開關(guān)的兩個出入端均按Cubei的關(guān)系配對編上號；再將各級開關(guān)同一編號的端用線連上。

STARAN網(wǎng)絡(luò)用作交換網(wǎng)絡(luò)時，采用級控制，實現(xiàn)的是交換函數(shù)。所謂交換(Flip)函數(shù)，是將一組元素首尾對稱地進(jìn)行交換。如果一組元素包含有2s個，則它是將所有第k個元素都與第(2s-(k+1))個元素相交換。如下表1列出級控信號采用各種不同組合情況下3級交換網(wǎng)絡(luò)所實現(xiàn)的入、出端的連接。

具有N個入端和N個出端的多級立方體網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖43K0控制Cube0K1控制Cube1K2控制Cube2Ki=0,直連Ki=1,交換表1三級STARAN交換網(wǎng)絡(luò)實現(xiàn)的入出端連接及所執(zhí)行的交換函數(shù)功能(Ki為第I級控制信號)(1)交換功能的控制與實現(xiàn)開關(guān)組合控制方式：級控制。K0控制Cube0K1控制Cube1K2控制Cube2Ki=44(2)移位功能的控制與實現(xiàn)開關(guān)組合控制方式：部分級控制(第i級有i+1種控制信號)Mod的作用：不同Mod可用于不同的分組操作。(3)網(wǎng)絡(luò)功能的應(yīng)用交換功能很適合于雙向互連(對稱)要求的實現(xiàn)；移數(shù)功能很適合于累加求和等要求的實現(xiàn)。(2)移位功能的控制與實現(xiàn)Mod的作用：不同Mod可45

例1：陣列有0~7共8個處理單元，要求按（0，5）、（1，4）、（2，7）、（3，6）配對通信。

(1)寫出實現(xiàn)此功能的互連函數(shù)一般式。（2）畫出用三級立方體網(wǎng)絡(luò)實現(xiàn)互聯(lián)函數(shù)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，標(biāo)出各級交換開關(guān)狀態(tài)。解：f（b2b1b0）=b2b1b0交換直連交換例1：陣列有0~7共8個處理單元，要求按（0，5）、46

例2：16個PE采用STARAN網(wǎng)絡(luò)互連時，實現(xiàn)相當(dāng)于4組4元交換，然后2組8元交換，再1組16元交換功能。寫出互連函數(shù)一般式,畫出相應(yīng)多級網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖，標(biāo)出各級交換開關(guān)狀態(tài)。

答：因需實現(xiàn)交換功能，故選擇STARAN的交換功能(級控制方式）。4組4元交換

Cube0+Cube12組8元交換

Cube0+Cube1+Cube21組16元交換

Cube0+Cube1+Cube2+Cube3

相加Cube0+Cube1+Cube3

互連函數(shù)：f(b3b2b1b0)=(b3b2b1b0)

各級開關(guān)狀態(tài)：k3k2k1k0=(1011)由此得出第0、1、3級開關(guān)狀態(tài)為交換，第2級為直連例2：16個PE采用STARAN網(wǎng)絡(luò)互連時，實現(xiàn)相當(dāng)47交換交換交換直連級k0k1k2k30123456789ABCDEF0123456789ABCDEF

∵共有16個結(jié)點，編碼需要4位，∴開關(guān)共4級。交換交換交換直連級k048

例3：現(xiàn)有16個PE(編號0~F)與網(wǎng)絡(luò)連接，程序在某個時刻需實現(xiàn)下列通信配對：7←→D、6←→C、5←→F、4←→E、3←→9、2←→8、1←→B、0←→A。請畫出互連網(wǎng)絡(luò)結(jié)構(gòu)圖，并寫出控制方式及各開關(guān)狀態(tài)。

答：因需實現(xiàn)雙向交換功能，選擇STARAN網(wǎng)絡(luò)的交換功能(級控制方式)可滿足要求。

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：

∵共有16個結(jié)點，編碼需要4位，∴開關(guān)共4級。

例3：現(xiàn)有16個PE(編號0~F)與網(wǎng)絡(luò)連接，程序在49

配對要求：(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A)

開關(guān)控制：∵≤7的結(jié)點←→＞7的結(jié)點，∴需1組16元交換；注意：組內(nèi)交換后結(jié)點次序已經(jīng)鏡像∵0~3的結(jié)點←→8~B的結(jié)點，∴需2組8元交換；∵0~1的結(jié)點←→A~B的結(jié)點，∴需4組4元交換；∵0結(jié)點←→A結(jié)點配對，已經(jīng)過3次鏡像∴需8組2元交換。

各級開關(guān)狀態(tài)：k3k2k1k0=(1010)

1組16元交換

Cube0+Cube1+Cube2+Cube3

2組8元交換

Cube0+Cube1+Cube2

4組4元交換

Cube0+Cube1

8組2元交換

Cube0

相加Cube1+Cube3配對要求：(7,D),(6,C),(5,F),(50級k0k1k2k30123456789ABCDEF0123456789ABCDEF由此得出第1、3級開關(guān)狀態(tài)為交換，第0、2級為直通級k051交換開關(guān)：四功能；拓?fù)浣Y(jié)構(gòu)：多級Shuffle；Omega網(wǎng)絡(luò)中各級編號的次序與多級立方體網(wǎng)絡(luò)正好相反，把Omega網(wǎng)絡(luò)的入、出端對調(diào)，就等于多級立方體網(wǎng)絡(luò)。2.多級混洗交換網(wǎng)絡(luò)(omega網(wǎng)絡(luò))ABCDEFGHIJKL012345672級012345671級0級

開關(guān)組合控制：級控制、開關(guān)二功能--STARAN交換網(wǎng)絡(luò)的逆網(wǎng)絡(luò)；部分級控制、開關(guān)二功能—STARAN移數(shù)網(wǎng)絡(luò)的逆網(wǎng)絡(luò);

單元控制、開關(guān)二、四功能--更強(qiáng)大的功能。交換開關(guān)：四功能；2.多級混洗交換網(wǎng)絡(luò)(omega網(wǎng)絡(luò))52網(wǎng)絡(luò)關(guān)系：按全混方法Shuffle（pn-1pn-2…

p0）=pn-2…

p0pn-1則有：

入0→0出入4→1出

1→25→32→46→53→67→7混洗拓?fù)渚褪菍⒕幪枮?，1….N-1的入端分成前后個數(shù)相等的兩半，前一半和后一半在連至輸出時順次一一相隔。各級畫好后，再將連線沿途所經(jīng)過的端號均標(biāo)成同一端號即可。網(wǎng)絡(luò)關(guān)系：按全混方法混洗拓?fù)渚褪菍⒕幪枮?，1….N-1的入53例：畫出0—7號共8個處理器的三級混洗交換網(wǎng)絡(luò)，在該圖上標(biāo)出實現(xiàn)將6號處理器數(shù)據(jù)播送給0—4號，同時將3號處理器數(shù)據(jù)播送給其余3個處理器時的各有關(guān)交換開關(guān)的控制狀態(tài)；例：畫出0—7號共8個處理器的三級混洗交換網(wǎng)絡(luò)，在該圖543.多級PM2I網(wǎng)絡(luò)（數(shù)據(jù)交換網(wǎng)絡(luò)）N=8三級PM2I網(wǎng)絡(luò)2jj+2imodNj-2imodN3.多級PM2I網(wǎng)絡(luò)（數(shù)據(jù)交換網(wǎng)絡(luò)）N=8三級PM2I網(wǎng)55結(jié)構(gòu)：n級，每一級把前后各N=2n個單元按PM2I拓?fù)浠ミB接。對第i級，每一個單元j（0≦j≦N-1）都有3根連線分別連到出端單元j、j+2imodN和j-2imodN，圖中分別用不同的線段表示?？刂七@三類連接線的信號分別為平控H、上控D、下控U。若采用單元控制方式，每一級都有自己獨立的控制信號H、D、U，稱此PM2I網(wǎng)絡(luò)為強(qiáng)化數(shù)據(jù)交換網(wǎng)絡(luò)（ADM）。結(jié)構(gòu)：n級，每一級把前后各N=2n個單元按PM2I拓?fù)浠ミB接566.2.5全排列網(wǎng)絡(luò)(1)多級網(wǎng)絡(luò)比較

靈活性(低→高)：STARAN、間接二進(jìn)制n方體、

Omega(ω)、ADM(混洗四功能)

成本(低→高)：同上

用途：

STARAN、OmegaPE←→PM

間接二進(jìn)制n方體PE--→PE

功能：同時只能實現(xiàn)部分互連函數(shù)功能。6.2.5全排列網(wǎng)絡(luò)(1)多級網(wǎng)絡(luò)比較靈活性(低→57(2)全排列網(wǎng)絡(luò)

定義：所有入端、出端的連接均不發(fā)生沖突的網(wǎng)絡(luò)，又稱非阻塞型網(wǎng)絡(luò)，即：N入→N出有N！種排列。

常規(guī)多級網(wǎng)絡(luò)(如STARAN、ω等)屬于阻塞型網(wǎng)絡(luò)。

證明：對n=log2N級網(wǎng)絡(luò)，開關(guān)數(shù)=N/2×n。排列數(shù)回下頁(2)全排列網(wǎng)絡(luò)常規(guī)多級網(wǎng)絡(luò)(如STARAN、ω等)58DTRMUX循環(huán)單級/多級網(wǎng)絡(luò)PE0來去PE0PEN-1來去PEN-1…DTRMUX(3)全排列網(wǎng)絡(luò)實現(xiàn)

方法：a.原有多級網(wǎng)絡(luò)通過鎖存器運(yùn)行兩次即可；思想：N!＜NN/2×NN/2＜NN。b.兩個log2N網(wǎng)絡(luò)背靠背串聯(lián)。Benes網(wǎng)絡(luò)DTRMUX循環(huán)單級/多級網(wǎng)絡(luò)PE0來去PE0PEN-1來去596.3并行存儲器無沖突訪問一、訪問需求并行存取向量中各分量信息；對矩陣可按行、列、對角線等方法訪問(步長不一致)。二、存在問題

存儲器帶寬限制—存儲器帶寬達(dá)不到向量帶寬；

訪存方式(步長)不同，產(chǎn)生訪存沖突。6.3并行存儲器無沖突訪問一、訪問需求二、存在問題60三、解決方法1、采用多體交叉存儲器使存儲體數(shù)超過PE數(shù)，保證PE所需要的帶寬。2、對向量分組操作解決MEM帶寬小于向量長度問題，提高處理效率。3、選擇適當(dāng)?shù)拇鎯w數(shù)m

使存儲體數(shù)m≥PE數(shù)，達(dá)到無沖突訪問

（1）一維向量：

順序存放，防止步長與m成比例；m取質(zhì)數(shù),與步長互質(zhì)。三、解決方法1、采用多體交叉存儲器2、對向量分組操作3、選擇61一維數(shù)組的存貯(m=4)假設(shè)并行存貯器的分體數(shù)m=4，交叉存放一維向量a0..，如下左圖所示。a.每次訪問m個相連的元素，無沖突；b.

若跳躍式訪問，步距為2：a0,a2,a4,a6，有沖突；

步距為4：a0,a4,a8,a12，有沖突；c.

把存貯器的體數(shù)取成一個質(zhì)數(shù)，只要變址步距與m互質(zhì)，存貯器總能無沖突訪問；（如下例所示，只要變址步長不是5的倍數(shù)就可以實現(xiàn)無沖突訪問。）一維數(shù)組的存貯(m=5)存貯器的體號43210一維數(shù)組的存貯(m=4)假設(shè)并行存貯器的分體數(shù)m=4，交叉62

如果設(shè)m=n=4,一個4×4的二維數(shù)組直接按行存貯，方案如下圖所示。雖然，同時訪問某一行、主對角線或次對角線上的所有元素時，都可以做到無沖突地訪問，但要同時訪問某一列的各元素時，由于它們集中存放在同一存貯分體內(nèi)，會產(chǎn)生訪存沖突，所以每次只能順序訪問該列中其中的一個元素，致使實際頻寬降低成1/4。4×4數(shù)組的直接按行存貯(m=n=4)（2）多維向量沖突如果設(shè)m=n=4,一個4×4的二維數(shù)組直接634×4數(shù)組一種錯位存放的方案為了使行或列的各元素都能并行訪問，若如下圖所示的將數(shù)據(jù)錯位存放，但這樣造成主對角線上各元素的并行訪問沖突。把存貯器的分體數(shù)m取成大于每次要訪問的向量或數(shù)組的個數(shù)n，且等于質(zhì)數(shù)，同時在多維數(shù)組的行、列等方向上采取不同的錯開距離。4×4數(shù)組一種錯位存放的方案為了使行或列的各元素都能并行訪64

錯位存放，滿足行、列、對角線等訪問要求；

對矩陣而言(m大于PE數(shù)時)--

設(shè)m=22P+1，δ1=2P，同一列不同行錯開距離

δ

2=1，同一行不同列錯開距離

對Aab，體號：

j=(aδ

1+bδ

2+C)modm

體內(nèi)序號：i=a

C為起始元素A00所在體號地址4×4數(shù)組錯位存放的例子(m=5,n=4,δ1=2,δ2=1)錯位存放，滿足行、列、對角線等訪問要求；654×5二維數(shù)組在并行存貯器中存放的例子(m=7,n=6)讓地址ɑ所對應(yīng)的元素存放在體號地址j=ɑmodm，體內(nèi)地址為i=ɑ/n的單元中，就可實現(xiàn)無沖突訪問。

當(dāng)向量元素不固定，或非n×n時--

將多維變換成一維數(shù)組S，再對S進(jìn)行處理。4×5二維數(shù)組在并行存貯器中存放的例子(m=7,n=6)666.4脈動陣列處理機(jī)和6.5相聯(lián)處理機(jī)（自己看）本章小結(jié)1。陣列處理機(jī)的原理（1）陣列機(jī)的分類及特點（2）ILLIACⅣ的結(jié)構(gòu)2。SIMD計算機(jī)的互連網(wǎng)絡(luò)（1）掌握各種互連函數(shù)，找出各處理單元的入出段連接。（2）掌握多級網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的畫法（3）根據(jù)要求標(biāo)出各級開關(guān)的狀態(tài)3。并行存貯器的無沖突訪問多維數(shù)組無沖突訪問的條件以及各元素存放的具體位置。6.4脈動陣列處理機(jī)和6.5相聯(lián)處理機(jī)（自己看）67第6章陣列處理機(jī)和相聯(lián)處理機(jī)6.1陣列處理機(jī)的原理6.2SIMD計算機(jī)的互連網(wǎng)絡(luò)6.3并行存儲器的無沖突訪問6.4脈動陣列處理機(jī)第6章陣列處理機(jī)和相聯(lián)處理機(jī)6.1陣列處理機(jī)的68本章要點陣列處理機(jī)的構(gòu)型及特點基本的單級互聯(lián)網(wǎng)絡(luò)結(jié)構(gòu)圖及互聯(lián)函數(shù)兩功能交換開關(guān)及四功能交換開關(guān)多級立方體網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的畫法多級混洗交換網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的畫法并行存儲器的無沖突訪問本章要點陣列處理機(jī)的構(gòu)型及特點691.陣列處理機(jī)的構(gòu)形陣列機(jī)通常由一個控制部件CU、N個處理器單元PE、M個存儲模塊以及一個互連網(wǎng)絡(luò)部件(IN)組成。

根據(jù)存儲器模塊是以分布式方式存取還是集中方式存取，陣列機(jī)可分為兩種基本結(jié)構(gòu)：分布式存儲器的陣列機(jī)和共享存儲器的陣列機(jī)。6.1陣列處理機(jī)的原理6.1.1陣列處理機(jī)的構(gòu)形與特點1.陣列處理機(jī)的構(gòu)形根據(jù)存儲器模塊是70PEM0PE0PEM1PE1PEMN-1PEN-1INCUCUMI/O接口DSC分布存儲器的陣列機(jī)結(jié)構(gòu)

（1）分布式存儲器的陣列機(jī)各個處理單元設(shè)有局部存儲器存放分布式數(shù)據(jù)，只能被本處理單元直接訪問。在控制部件CU內(nèi)設(shè)有一個用來存放程序和數(shù)據(jù)的主存儲器CUM。各個PE同步執(zhí)行來自CU的操作命令，各處理單元通過IN來交換數(shù)據(jù)。PEM0PE0PEM1PE1PEMN-1PEN-1INCUI71…INPE0PE1PEN-1MM0MM1MMK-1CUSCI/O-CHI/OSM……具有共享存儲器的陣列機(jī)結(jié)構(gòu)

（2）集中式共享存儲器的陣列機(jī)每個PE沒有局部存儲器，存儲模塊以集中形式為所有PE共享?；ミB網(wǎng)IN受CU控制，用來構(gòu)成PE和MM的數(shù)據(jù)交換通路，具有雙向性?！璉NPE0PE1PEN-1MM0MM1MMK-1CUSCI722

陣列機(jī)的特點并行處理機(jī)有如下特點：（1）

利用資源重復(fù)（空間因素）而非時間重疊。（2）

利用同時性而非并發(fā)性。它的每個處理單元在同一時刻要同等地?fù)?dān)負(fù)起各種運(yùn)算功能。（3）提高運(yùn)算速度主要是靠增大處理單元個數(shù)，比起向量流水線處理機(jī)主要依靠縮短時鐘周期來說，速度提高的潛力要大得多（4）使用簡單而又規(guī)整的互連網(wǎng)絡(luò)來確定多個處理單元之間的連接模式。（5）并行處理機(jī)（陣列機(jī)）研究必須與并行算法研究密切結(jié)合，使之適應(yīng)性更強(qiáng)，應(yīng)用面更廣。2

陣列機(jī)的特點并行處理機(jī)有如下特點：736.1.2ILLIAC-IV處理單元陣列結(jié)構(gòu)處理單元陣列由64個PUi構(gòu)成,每個PUi包括(PEi、PEMi和MLU)

由64個結(jié)構(gòu)完全相同的處理單元PEi

構(gòu)成，每個處理單元PEi字長64位，PEMi為隸屬于PEi的局部存儲器，全部PEi由CU統(tǒng)一管理，PEi都有一根方式位線，用來向CU傳送每個PEi的方式寄存器D中的方式位，使CU能了解各PEi的狀態(tài)是否活動，作為控制它們工作的依據(jù)。陣列控制器CU相當(dāng)一臺小型控制計算機(jī)對處理單元陣列實現(xiàn)控制,(發(fā)控制信號,廣播公共地址,(廣播公共數(shù)據(jù))）對指令流進(jìn)行譯碼控制,利用CU內(nèi)部資源可以進(jìn)行標(biāo)量操作,接受和處理各類中斷，其他輸入輸出操作。I/O系統(tǒng)

由磁盤文件系統(tǒng)DFS，輸入輸出子系統(tǒng)和宿主計算機(jī)S/C構(gòu)成6.1.2ILLIAC-IV處理單元陣列結(jié)構(gòu)處理單元陣列74ILLIACⅣ的組成ILLIACⅣ的組成75PU16PU0PU8PU7PU55PU63PU0PU1PU7PU8PU9PU15PU56PU57PU63PU0PU1PU7PU56PU57PU58ILLIAC-IV的處理單元互連結(jié)構(gòu)PU16PU0PU8PU7PU55PU63PU0PU1PU776

特點:

(1)閉合螺線陣列

(2)任意單元的最短距離不超過7步將PU63傳送到PU10，最快可經(jīng)PU63→PU7→PU8→PU9→PU10。

(3)一般來講：個處理單元組成的陣列中，任意兩個處理單元之間的最短距離不會超過步（4）處理單元為通常的累加型運(yùn)算器，把累加寄存器RGA中的數(shù)據(jù)和存儲器來的數(shù)據(jù)進(jìn)行運(yùn)算操作，數(shù)據(jù)傳送寄存器RGR收發(fā)數(shù)據(jù)，實現(xiàn)數(shù)據(jù)在處理單元之間的傳送。特點:77一．矩陣加 矩陣加(配比加)是最簡單的情況。假定兩個8*8的矩陣A、B相加，所得結(jié)果矩陣C也是一個8*8的矩陣。設(shè)A、B的分量元素分別存在PEMi的Z,Z+1單元中,所得結(jié)果矩陣C各分量存在PEMi

的Z+2單元中用下面三條指令可一次完成(64個處理單元并行)LDAZ；全部（Z）由PEMi送到PE的累加器RGAiADRNZ+1；全部（Z+1）與（RGAi）進(jìn)行浮點加，結(jié)果送RGAiSTAZ+2；全部（RGAi）由PE送到PEMi的（Z+2）單元這里0≤i≤63

6.1.3ILLIACⅣ的并行算法舉例一．矩陣加這里0≤i≤636.1.3ILLIAC78矩陣加存儲器分舉例A(0,0)B(0,0)C(0,0)PEM0aa+1a+2A(0,1)B(0,1)C(0,1)PEM1A(7,7)B(7,7)C(7,7)PEM63處理速度為順序處理的64倍矩陣加存儲器分舉例A(0,0)B(0,0)C(0,0)PE79二．矩陣乘a0,0a0,1…a0,7a1,0a1,1…a1,7……a7,0a7,1…a7,7b0,0b0,1…b0,7b1,0b1,1…b1,7……b7,0b7,1…b7,7a0,0×b0,0+a0,1×b1,0+…+a0,7×b7,0…a0,0×b0,7+a0,1×b1,7+…+a0,7×b7,7a1,0×b0,0+a1,1×b1,0+…+a1,7×b7,0…a1,0×b0,7+a1,1×b1,7+…+a1,7×b7,7……a7,0×b0,0+a7,1×b1,0+…+a7,7×b7,0…a7,0×b0,7+a7,1×b1,7+…+a7,7×b7,7=×

如果順序執(zhí)行C=A×B，那么，計算每個元素cij需要做8次乘法，7次加法，共需做15次乘/加運(yùn)算。在ILLIACIV的處理機(jī)上，操作數(shù)B的64個元素存儲在64個PEM中。當(dāng)每次計算元素cij時，就把操作數(shù)A的8個元素aik(0<=k<=7)播送到相應(yīng)的8個PE中，然后并行地一次完成8個中間積的運(yùn)算。最后對8個中間積做7次加法，累加得到cij

。二．矩陣乘a0,0a0,1…a080A(0,0)A(1,0)...A(7,0)B(0,0)B(1,0)...B(7,0)C(0,0)C(1,0)...C(7,0)A(0,1)A(1,1)...A(7,1)B(0,1)B(1,1)...B(7,1)C(0,1)C(1,1)...C(7,1)A(0,7)A(1,7)...A(7,7)B(0,7)B(1,7)...B(7,7)C(0,7)C(1,7)...C(7,7)PE0PEM2PEM7...矩陣乘存儲器分配舉例（設(shè)用八個處理單元即PU并行）………...八個局部存儲器PEMi,每個連續(xù)存放A,B和結(jié)果向量C的一列元素A(0,0)A(1,0)...A(7,0)B(0,0)B(181三、累加和（成對遞歸）這是一個將N個數(shù)的順序相加過程轉(zhuǎn)變?yōu)椴⑿邢嗉舆^程的問題。設(shè)N為8，即有8個數(shù)A（I）順序累加，其中0≦I≦7。

在SISD計算機(jī)上可寫成下列程序：

C=0DO10I=0，7

10C=C+A（I）用成對遞歸算法，只需Log28=3在SIMD計算機(jī)上可寫成下列程序

C=ADO10K=0,Log28-110C=C+SHFTR(C,2**K)

其中SHFTR(C,2**K)是向量傳送語句,C向量各分量向右傳送步距為2的K次冪三、累加和（成對遞歸）這是一個將N個數(shù)的順序相加過程轉(zhuǎn)變?yōu)?2用成對遞歸算法求累加和的步驟：1.置全部PEi為活躍狀態(tài)，0≦i≦7。2.全部A（i）從PEMi的a單元讀到相應(yīng)PEi的累加寄存器RGAi中，0≦i≦7；3.令k=0；4.將全部PEi的（RGAi）傳送到寄存器RGRi，0≦i≦7；5.將全部PEi的（RGRi）經(jīng)過互連網(wǎng)絡(luò)向右傳送2k步距，0≦i≦7；6.令j=2k-1；7.置PE0至PEj為不活躍狀態(tài)；8.處于活躍狀態(tài)的所有PEj執(zhí)行（RGAi）:=(RGAi)+（RGRi），j≦i≦7；9.k:=k+1;10.如k<3,則轉(zhuǎn)回4,否則往下繼續(xù)執(zhí)行;11.置全部PEi為活躍狀態(tài)，0≦i≦7,存結(jié)果至a+1單元。設(shè)原始數(shù)據(jù)A（I）分別存在8個PEM的某a單元中用成對遞歸算法求累加和的步驟：設(shè)原始數(shù)據(jù)A（I）分別存在8個83設(shè)原始數(shù)據(jù)A（I）分別存在PEM的某個單元中步距1步距2步距4K=0K=1K=2PE0A0

A0

A0A0PE1A1A0+A1

A0+A1A0+A1PE2A2A1+A2A0+A1+A2A0+A1+A2PE3A3A2+A3A0+A1+A2+A3A0+A1+A2+A3PE4A4A3+A4A1+A2+A3+A4A0+A1+A2+A3+A4PE5A5A4+A5A2+A3+A4+A5A0+A1+A2+A3+A4+A5PE6A6A5+A6A3+A4+A5+A6A0+A1+A2+A3+A4+A5+A6PE7A7A6+A7A4+A5+A6+A7A0+A1+A2+A3+A4+A5+A6+A7設(shè)原始數(shù)據(jù)A（I）分別存在PEM的某個單元中步距184二、遞歸折疊求和用遞歸折疊方法來求累加和過程如下圖所示。

上述求累加和算法雖然使計算次數(shù)減少，但是速度的提高的倍數(shù)只是N/Log2N，速度并沒有提高多少。PE值步1步2步40A0A0+A1A0+A1+A2+A3A0+A1+A2+A3+1A1A4+A5+A6+A72A2A2+A33A34A4A4+A5A4+A5+A6+A75A56A6A6+A77A78個PE的遞歸折疊求和長度為N的遞歸計算時間正比于Log2N二、遞歸折疊求和用遞歸折疊方法來求累加和過程如下圖所示。85例：A和B都是元素為浮點表示的64×64的二維數(shù)組，一次浮點加法的計算過程由取數(shù)、求階差、對階、尾數(shù)加、規(guī)格化和存數(shù)共6個段組成。若每個段的執(zhí)行時間均為Δt，請分別求出在下列結(jié)構(gòu)不同的處理機(jī)上完成C=A+B所需時間及相對于順序處理的加速比。(1)順序處理方式的處理機(jī)(2)具有浮點加法流水線的流水處理機(jī)，且浮點加法流水線分為6個段，各段執(zhí)行時間均為Δt。(3)8×8的陣列處理機(jī)，且處理陣列上的每個處理器只能順序處理浮點加運(yùn)算。(4)8×8的陣列處理機(jī)，且處理陣列上的每個處理器均能流水處理浮點加運(yùn)算。(4)64×64的陣列處理機(jī)。例：A和B都是元素為浮點表示的64×64的二維數(shù)組，一次浮點86a0,0a0,1…a0,63a1,0a1,1…a1,63……a63,0a63,1…a63,63b0,0b0,1…b0,63b1,0b1,1…b1,63……b63,0b63,1…b63,63+a0,0+b0,0a0,1+b0,1…a0,63+b0,63a1,0+b1,0a1,1+b1,1…a1,63+b1,63……a63,0+b63,0a63,1+b63,1…a63,63+b63,63=解：(1)順序處理方式下，需要順序執(zhí)行的浮點加法次數(shù)為64×64=4096，每次浮點加運(yùn)算所需時間為6Δt

，則全部運(yùn)算所需時間為：T1=4096×6Δt=24576Δt(2)需要流水執(zhí)行的浮點加法次數(shù)為64×64=4096，則一個K=6段浮點加法流水線處理全部運(yùn)算所需時間為：T2=(k+n-1)Δt=(6+4096-1)Δt=4101Δt加速比：S2=T1/T2=5.9a0,0a0,1…a0,63b0,87(3)對于8×8的處理陣列，每個處理器需要處理64×64二維數(shù)組中的一個8×8子數(shù)組，因此，每個處理器需要執(zhí)行的浮點加法次數(shù)為8×8。每次浮點加法運(yùn)算需要時間6Δt

。每個處理器順序執(zhí)行64次浮點加法所需時間為64×6Δt=384Δt。64個處理器并行處理，同時完成各自的64次浮點加運(yùn)算，所以，全部運(yùn)算所需時間為：T3=384Δt加速比：S2=T1/T3=64(4)對于8×8的處理陣列，每個處理器需要處理64×64二維數(shù)組中的一個8×8子數(shù)組，