并行處理機(jī)和相聯(lián)處理機(jī).ppt

《并行處理機(jī)和相聯(lián)處理機(jī).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《并行處理機(jī)和相聯(lián)處理機(jī).ppt（72頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第6章并行處理機(jī)和相聯(lián)處理機(jī),6.1并行處理機(jī)原理6.2并行處理機(jī)舉例6.3相聯(lián)處理機(jī),6.1并行處理機(jī)原理,6.1.1并行處理機(jī)的構(gòu)形與特點(diǎn),1.并行處理機(jī)的基本構(gòu)形,圖6.1具有分布式存貯器的并行處理機(jī)構(gòu)形,圖6.2具有集中式共享存貯器的并行處理機(jī)構(gòu)形,2.并行處理機(jī)的特點(diǎn)并行處理機(jī)的單指令流多數(shù)據(jù)流處理方式和由它產(chǎn)生的特殊結(jié)構(gòu)是以諸如有限差分、矩陣、信號(hào)處理、線性規(guī)劃等一系列計(jì)算問(wèn)題為背景發(fā)展起來(lái)的。這些計(jì)算問(wèn)題的共同特點(diǎn)是可以通過(guò)各種途徑把它們轉(zhuǎn)化成為對(duì)數(shù)組或向量的處理，而并行處理機(jī)正好利用多個(gè)處理單元對(duì)向量或數(shù)組所包含的各個(gè)分量同時(shí)計(jì)算，從而獲得很高的處理速度。與同樣擅長(zhǎng)于向量處理

2、的流水線處理機(jī)相比，并行處理機(jī)利用的是資源重復(fù)，而不是時(shí)間重疊；利用并行性中的同時(shí)性，而不是并發(fā)性。它的每個(gè)處理單元要同等地?fù)?dān)負(fù)起各種運(yùn)算功能，但其設(shè)備利用率卻可能沒(méi)有多個(gè)單功能流水線部件那樣高。因此，只有在硬件價(jià)格有了大幅度下降及系統(tǒng)結(jié)構(gòu)有了較大改進(jìn)的情況下，并行處理機(jī)才能具有較好的性能價(jià)格比。并行理機(jī)主要是靠增大處理單元個(gè)數(shù)來(lái)提高運(yùn)算速度，比起向量流水線處理機(jī)主要依靠縮短時(shí)鐘周期來(lái)說(shuō)，速度提高的潛力要大得多。,6.1.2并行處理機(jī)的算法,1.ILLIACⅣ的處理單元陣列結(jié)構(gòu),圖6.3ILLIACⅣ處理單元的互連結(jié)構(gòu),PUi為處理部件，包含64位的算術(shù)處理單元PEi、所帶的局部存貯器PEMi

3、和存貯器邏輯部件MLU。64個(gè)處理部件PU0~PU63排列成88的方陣。任何一個(gè)PUi只與其上、下、左、右4個(gè)近鄰PUi-8(mod64)、PUi+8(mod64)、PUi-1(mod64)和PUi+1(mod64)直接相連。循此規(guī)則，上、下方向上同一列兩端的PU相連構(gòu)成一個(gè)環(huán)，左、右方向上每一行的右端PU與下一行的左端PU相連，最下面一行右端的PU與最上面一行左端PU相連，從而形成一種閉合的螺線形狀，所以又稱閉合螺線陣列。在這個(gè)陣列中，步距不等于1或8的任意處理單元之間的通信，可以用軟件方法尋找最短路徑進(jìn)行，其最短距離都不會(huì)超過(guò)7步。,例如，要將PU63的信息傳送到PU10，最快可經(jīng)PU63

4、→PU7→PU8→PU9→PU104步即可實(shí)現(xiàn)，而要將PU9的信息傳送到PU45，最快可經(jīng)PU9→PU1→PU57→PU56→PU48→PU47→PU46→PU457步實(shí)現(xiàn)。普遍來(lái)講，個(gè)處理單元組成的陣列中，任意兩個(gè)處理單元之間的最短距離不會(huì)超過(guò)步。,2.陣列處理機(jī)的算法舉例1)有限差分問(wèn)題求解場(chǎng)方程時(shí)，常使用有限差分法。它是把一個(gè)有規(guī)則的網(wǎng)格覆蓋在整個(gè)場(chǎng)域上，用網(wǎng)格點(diǎn)上的變量值寫(xiě)出差分方程組來(lái)代替場(chǎng)方程進(jìn)行計(jì)算。在解決物理問(wèn)題時(shí)，如果將描述平面場(chǎng)的拉普拉斯方程,中的二階偏導(dǎo)數(shù)表示為差分形式：,并代入原方程，即可得有限差分計(jì)算公式,式中，(x,y)為網(wǎng)格點(diǎn)坐標(biāo)，h為網(wǎng)格點(diǎn)的間距。,2)矩

5、陣加在陣列處理機(jī)上，解決矩陣加法是最簡(jiǎn)單的一維情形。若有兩個(gè)88的矩陣A、B相加，所得結(jié)果矩陣C也是一個(gè)88的矩陣。只需把A、B居于相應(yīng)位置的分量存放在同一個(gè)PEM內(nèi)，且在全部64個(gè)PEM中，令A(yù)的分量均為同一地址α，B的分量單元均為同一地址α+1，而結(jié)果矩陣C的各個(gè)結(jié)果分量也相應(yīng)存放于各PEM同一地址α+2的單元內(nèi)，如圖6.4所示。這樣，只需用下列3條ILLIACⅣ的匯編指令就可以一次實(shí)現(xiàn)矩陣相加：,LDAALPHA;全部(α)由PEMi送PEi的累加器RGAiADRNALPHA+1;全部(α+1)與(RGAi)進(jìn)行浮點(diǎn)規(guī)舍加，結(jié)果送RGAiSTAALPHA+2;全部(RGAi)由PEi

6、送PEMi的α+2單元這里，0≤i≤63。,圖6.4矩陣相加的存貯器分配舉例,3)矩陣乘由于矩陣乘是二維數(shù)組運(yùn)算，故它比循環(huán)加要復(fù)雜一些。設(shè)A、B和C為3個(gè)88的二維矩陣。若給定A和B，則為計(jì)算C=A*B的64個(gè)分量，可用下列公式,其中，0≤i≤7且0≤j≤7。,在SISD計(jì)算機(jī)上求解這個(gè)問(wèn)題，可執(zhí)行用FORTRAN語(yǔ)言編寫(xiě)的下列程序,DO10I=0,7DO10J=0,7C(I,J)=0DO10K=0,710C(I,J)=C(I,J)+A(I,K)*B(K,J),需要經(jīng)過(guò)I、J、K三重循環(huán)完成。每重循環(huán)執(zhí)行8次，總共需要512次乘、加的時(shí)間，此外每次還應(yīng)包括執(zhí)行循環(huán)控制、判別等其他操

7、作需花費(fèi)的時(shí)間。而如果在SIMD陣列處理機(jī)上運(yùn)算，則可用8個(gè)處理單元并行計(jì)算矩陣C(I，J)的某一行或某一列，即將J循環(huán)或I循環(huán)轉(zhuǎn)化成一維的向量處理，從而消去了一重循環(huán)。以消去J循環(huán)為例，可執(zhí)行用FORTRAN語(yǔ)言編寫(xiě)的下列程序DO10I=0,7C(I,J)=0DO10K=0,710C(I,J)=C(I,J)+A(I,K)*B(K,J),圖6.5矩陣乘程序執(zhí)行流程圖,圖6.6矩陣乘的存貯器分配舉例,4)累加和這是一個(gè)將N個(gè)數(shù)的順序相加過(guò)程轉(zhuǎn)變?yōu)椴⑿邢嗉舆^(guò)程的問(wèn)題。為了得到各項(xiàng)累加的部分和和最后的總和，要用到處理單元中的活躍標(biāo)志位。只有處于活躍狀態(tài)的處理單元，才能執(zhí)行相應(yīng)的操作。為敘

8、述方便，取N為8，即有8個(gè)數(shù)A(I)順序累加，其中0≤I≤7。在SISD計(jì)算機(jī)上可寫(xiě)成下列FORTRAN程序：C=0DO10I=0,710C=C+A(I)這是一個(gè)串行程序，需要8次加法時(shí)間。,如果在并行處理機(jī)上，采用成對(duì)遞歸相加的算法，則只需log28=3次加法時(shí)間就夠了。首先，原始數(shù)據(jù)A(I)分別存放在8個(gè)PEM的α單元中，其中0≤I≤7。然后，按照下面的步驟求累加和：第一步置全部PEi為活躍狀態(tài)，0≤i≤7；第二步全部A(I)從PEMi的α單元讀到相應(yīng)PEi的累加寄存器RGAi中，0≤i≤7;第三步令k=0;第四步將全部PEi的(RGAi)轉(zhuǎn)送到傳送寄存器RGRi，0≤i

9、≤7；第五步將全部PEi的(RGRi)經(jīng)過(guò)互連網(wǎng)絡(luò)向右傳送2k步距，0≤i≤7;,第六步令j=2k-1;第七步置PE0至PEj為不活躍狀態(tài)；第八步處于活躍狀態(tài)的所有PEi執(zhí)行(RGAi):=(RGAi)+(RGRi)，j＜i≤7；第九步k:=k+1;第十步如k＜3，則轉(zhuǎn)回第四步，否則往下繼續(xù)執(zhí)行；第十一步置全部PEi為活躍狀態(tài)，0≤i≤7;第十二步將全部PEi的累加寄存器內(nèi)容(RGAi)存入相應(yīng)PEMi的α+1單元中，0≤i≤7。,圖6.7并行處理機(jī)上累加和計(jì)算過(guò)程的示意圖,圖6.8循環(huán)互連網(wǎng)絡(luò)組成框圖,6.1.3SIMD計(jì)算機(jī)的互連網(wǎng)絡(luò),1.互連網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)及互連函數(shù),2

10、.基本的單級(jí)互連網(wǎng)絡(luò),1)立方體單級(jí)網(wǎng)絡(luò),圖6.9三維立方體結(jié)構(gòu),這是一個(gè)三維的情形。立方體的每一個(gè)頂點(diǎn)(網(wǎng)絡(luò)的節(jié)點(diǎn))代表一個(gè)處理單元，共有8個(gè)處理單元，用zyx三位二進(jìn)制碼編號(hào)。它所能實(shí)現(xiàn)的入、出端連接如同立方體各頂點(diǎn)間能實(shí)現(xiàn)的互連一樣，即每個(gè)處理單元只能直接連到其二進(jìn)制編號(hào)的某一位取反的其他3個(gè)處理單元上。如010只能連到000、011、110，不能直接連到對(duì)角線上的001、100、101、111。所以，三維的立方體單級(jí)網(wǎng)絡(luò)有3種互連函數(shù)：Cube0、Cube1和Cube2。其連接方式如圖6.10中的實(shí)線所示。Cubei函數(shù)表示相連的入端和出端的二進(jìn)制編號(hào)只在右起第i位(i=0,1,2)上

11、有差別，即僅在該位上的代碼“0”、“1”互反，其余各位代碼都相同。,圖6.10立方體單級(jí)網(wǎng)絡(luò)連接圖,推廣到n維的情形，N個(gè)節(jié)點(diǎn)的立方體單級(jí)網(wǎng)絡(luò)共有n=log2N種互連函數(shù)，即,式中，0≤i≤n-1，Pi為入端號(hào)二進(jìn)制碼的第i位。當(dāng)維數(shù)n＞3時(shí)，稱為超立方體(HyperCube)網(wǎng)絡(luò)。,2)PM2I單級(jí)網(wǎng)絡(luò)PM2I單級(jí)網(wǎng)絡(luò)是“加減2i”(Plus-Minus2i)單級(jí)網(wǎng)絡(luò)的簡(jiǎn)稱。能實(shí)現(xiàn)與j號(hào)處理單元直接相連的是號(hào)為j2i的處理單元，即,式中，0≤j≤N-1,0≤i≤n-1,n=log2N。因此，它共有2n個(gè)互連函數(shù)。由于總存在PM2+(n-1)=PM2-(n-1)，所以實(shí)際上，PM2I互連

12、網(wǎng)絡(luò)只有2n-1種不同的互連函數(shù)。,對(duì)于N=8的三維PM2I互連網(wǎng)絡(luò)的互連函數(shù)有PM2+0、PM2-0、PM2+1、PM2-1、PM22等5個(gè)不同的互連函數(shù)，它們分別為：PM2+0:(01234567)PM2-0:(76543210)PM2+1:(0246)(1357)PM2-1:(6420)(7531)PM22:(04)(15)(26)(37),圖6.11PM2I互連網(wǎng)絡(luò)的部分連接圖,有的陣列處理機(jī)采用單向環(huán)網(wǎng)或雙向環(huán)網(wǎng)實(shí)現(xiàn)處理器的互連，可以看成是PM2I網(wǎng)絡(luò)的特例，它僅使用了其中的PM2+0、PM2-0或PM20互連函數(shù)。不難看出，ILLIACⅣ處理單元的互連也是PM

13、2I互連網(wǎng)絡(luò)的特例，只采用了其中的PM20和(即PM23)4個(gè)互連函數(shù)。PM2I單級(jí)網(wǎng)絡(luò)的最大距離為［n/2］。以上面的三維PM2I互連網(wǎng)絡(luò)的例子就可以看出，最多只要二次使用，即可實(shí)現(xiàn)任意一對(duì)入、出端號(hào)之間的連接。,3)混洗交換單級(jí)網(wǎng)絡(luò),圖6.128個(gè)處理單元的全混連接,用互連函數(shù)表示為,式中，n=log2N，Pn-1Pn-2…P1P0為入端編號(hào)的二進(jìn)制碼。,Shuffle函數(shù)還有一個(gè)重要特性。如果把它再作一次Shuffle函數(shù)變換，得到的是一組新的代碼，即Pn-3…P0Pn-1Pn-2。這樣，每全混一次，新的最高位就被移至最低位。當(dāng)經(jīng)過(guò)n次全混后，全部N個(gè)處理單元便又恢復(fù)到最初的排列次

14、序。在多次全混的過(guò)程中，除了編號(hào)為全“0”和全“1”的處理單元外，各個(gè)處理單元都遇到了與其他多個(gè)處理單元連接的機(jī)會(huì)。,圖6.13N=8時(shí)全混交換互連網(wǎng)絡(luò)連接圖,3.多級(jí)互連網(wǎng)絡(luò),交換開(kāi)關(guān)是具有兩個(gè)入端和兩個(gè)出端的交換單元，用作各種多級(jí)互連網(wǎng)絡(luò)的基本構(gòu)件。不論入端或出端，如果令居于上方的都用i表示，居于下方的都用j表示，則可以定義下列4種開(kāi)關(guān)狀態(tài)或連接方式：(1)直連——i入連i出，j入連j出；(2)交換——i入連j出，j入連i出；(3)上播——i入連i出和j出，j入懸空；(4)下播——j入連i出和j出，i入懸空。,只具有前兩種功能的稱二功能交換單元，具有全部4種功能的稱四功能交換單元

15、。兩個(gè)入端同時(shí)連到一個(gè)出端的情形是不允許的，因?yàn)闀?huì)發(fā)生信息傳送的沖突現(xiàn)象。此外，還可以有第5種開(kāi)關(guān)狀態(tài)，即i入連j入，i出連j出，稱此為返回。它可用來(lái)實(shí)現(xiàn)入端與入端相連，出端與出端相連，從而將N個(gè)入端和N個(gè)出端的網(wǎng)絡(luò)變?yōu)?N個(gè)處理單元的互連網(wǎng)絡(luò)。拓?fù)浣Y(jié)構(gòu)是指各級(jí)之間出端和入端相互連接的模式。,控制方式是對(duì)各個(gè)交換開(kāi)關(guān)進(jìn)行控制的方式，以多級(jí)立方體網(wǎng)絡(luò)為例，它可以有3種：(1)級(jí)控制——同一級(jí)的所有開(kāi)關(guān)只用一個(gè)控制信號(hào)控制，同時(shí)只能處于同一種狀態(tài)；(2)單元控制——每一個(gè)開(kāi)關(guān)都有自己獨(dú)立的控制信號(hào)控制，可各自處于不同的狀態(tài)；(3)部分級(jí)控制——第i級(jí)的所有開(kāi)關(guān)分別用i+1個(gè)信號(hào)控制，0≤

16、i≤n-1,n為級(jí)數(shù)。,1)多級(jí)立方體網(wǎng)絡(luò)多級(jí)立方體網(wǎng)絡(luò)有STARAN網(wǎng)絡(luò)、間接二進(jìn)制n方體網(wǎng)絡(luò)等。,圖6.14N=8多級(jí)立方體互連網(wǎng)絡(luò),STARAN網(wǎng)絡(luò)用作交換網(wǎng)絡(luò)時(shí)，采用級(jí)控制，實(shí)現(xiàn)的是交換函數(shù)。所謂交換(Flip)函數(shù)，是將一組元素首尾對(duì)稱地進(jìn)行交換。如果一組元素包含有2s個(gè)，則它是將所有第k個(gè)元素都與第(2s-(k+1))個(gè)元素相交換。,表6.1三級(jí)STARAN交換網(wǎng)絡(luò)實(shí)現(xiàn)的入出端連接及所執(zhí)行的交換函數(shù)功能(Ki為第i級(jí)控制信號(hào)),從表6.1可以看出，控制信號(hào)為111時(shí)，實(shí)現(xiàn)的是全交換，又稱鏡像交換，完成對(duì)這8個(gè)處理單元(元素)的一組8元交換，其變換圖像如下：入端排列|01234

17、567|出端排列|76543210|控制信號(hào)為001時(shí)，完成對(duì)這8個(gè)處理單元(元素)的4組2元交換，其變換圖像為：入端排列|01|23|45|67|出端排列|10|32|54|76|,控制信號(hào)為010時(shí)，完成的功能相當(dāng)于在4組2元交換后，再2組4元交換，其變換圖像是：|1032|5476||2301|6745|而控制信號(hào)為101時(shí)，相當(dāng)于在實(shí)現(xiàn)上述兩種交換后，再1組8元交換，其變換圖像是：|23016745||54761032|,出端排列,出端排列,表6.2三級(jí)移數(shù)網(wǎng)絡(luò)能實(shí)現(xiàn)的入出端連接及移數(shù)函數(shù)功能,2)多級(jí)混洗交換網(wǎng)絡(luò)多級(jí)混洗交換網(wǎng)絡(luò)又稱omega網(wǎng)絡(luò)，如圖6.15所示

18、。,圖6.15N=8多級(jí)混洗交換網(wǎng)絡(luò),3)多級(jí)PM2I網(wǎng)絡(luò),圖6.16N=8多級(jí)PM2I網(wǎng)絡(luò),4.全排列網(wǎng)絡(luò)如果互連網(wǎng)絡(luò)是從N個(gè)入端到N個(gè)出端的一到一的映射，就可以把它看成是對(duì)此N個(gè)端的重新排列。因此，互連網(wǎng)絡(luò)的功能實(shí)際上就是用新排列來(lái)置換N個(gè)入端原有的排列。前面所介紹的各種基本多級(jí)網(wǎng)絡(luò)都能實(shí)現(xiàn)任意一個(gè)入端與任意一個(gè)出端間的連接，但是要同時(shí)實(shí)現(xiàn)兩對(duì)或多對(duì)入端與出端之間的連接時(shí)，都有可能因爭(zhēng)用數(shù)據(jù)傳送路徑而發(fā)生沖突。我們稱具有這類性質(zhì)的互連網(wǎng)絡(luò)為阻塞式網(wǎng)絡(luò)(BlockingNetwork)。反之，不具有這類性質(zhì)的互連網(wǎng)絡(luò)為非阻塞式網(wǎng)絡(luò)，或稱為全排列網(wǎng)絡(luò)。非阻塞式網(wǎng)絡(luò)連接的靈活性好，但連線多，控

19、制復(fù)雜，成本高。,阻塞式網(wǎng)絡(luò)在一次傳送中不可能實(shí)現(xiàn)N個(gè)端的任意排列。大家知道，N個(gè)端的全部排列共有N!種?？墒?，對(duì)使用單元控制的n=log2N級(jí)組成的間接二進(jìn)制n方體網(wǎng)絡(luò)來(lái)說(shuō)，每級(jí)有N/2個(gè)開(kāi)關(guān)，n級(jí)互連網(wǎng)絡(luò)所用交換開(kāi)關(guān)的總數(shù)為(Nlog2N)/2。為實(shí)現(xiàn)入出端的一對(duì)一映射，每個(gè)開(kāi)關(guān)只能使用直連和交換兩種功能。這樣，所有開(kāi)關(guān)處于不同狀態(tài)的總數(shù)最多只有2(Nlog2N)/2，即NN/2種。當(dāng)N為大于2的任何整數(shù)時(shí)，總有NN/2＜N!,這就是說(shuō)，它無(wú)法實(shí)現(xiàn)相應(yīng)的所有N!種排列。以N=8的三級(jí)網(wǎng)絡(luò)為例，共12個(gè)兩功能交換開(kāi)關(guān)，只有212=4096種不同狀態(tài)，最多只能控制對(duì)端子的4096種排列，不可

20、能實(shí)現(xiàn)全部8!=40320種排列。所以，多對(duì)入出端要求同時(shí)連接時(shí)，就有可能發(fā)生沖突。,然而，只要對(duì)這個(gè)多級(jí)互連網(wǎng)絡(luò)通行兩次，每次通行時(shí)，讓各開(kāi)關(guān)處于不同狀態(tài)，就可以滿足對(duì)N個(gè)端子的全部N!種排列。因?yàn)榇藭r(shí)，全部開(kāi)關(guān)的總狀態(tài)數(shù)可有NN/2NN/2=NN種，足以滿足N!種不同排列的開(kāi)關(guān)狀態(tài)要求。這種只要經(jīng)過(guò)重新排列已有入出端對(duì)的連接，就可以完成所有可能的入出端間的連接而不發(fā)生沖突的互連網(wǎng)絡(luò)，稱為可重排列網(wǎng)絡(luò)(RearrangeableNetwork)。實(shí)現(xiàn)時(shí)，可以在上述任何一種基本多級(jí)互連網(wǎng)絡(luò)的出端設(shè)置鎖存器，使數(shù)據(jù)在時(shí)間上順序通過(guò)兩次，這實(shí)際上就是循環(huán)互連網(wǎng)絡(luò)的實(shí)現(xiàn)思路。,圖6.17多級(jí)全排列網(wǎng)

21、絡(luò)舉例(Benes網(wǎng)絡(luò)),6.1.4并行存貯器的無(wú)沖突訪問(wèn),圖6.18一維數(shù)組的存貯(m=4),如果設(shè)m=n=4,一個(gè)44的二維數(shù)組直接按行存貯，方案如圖6.19所示。雖然，同時(shí)訪問(wèn)某一行、主對(duì)角線或次對(duì)角線上的所有元素時(shí)，都可以做到無(wú)沖突地訪問(wèn)，但要同時(shí)訪問(wèn)某一列的各元素時(shí)，由于它們集中存放在同一存貯分體內(nèi)，會(huì)產(chǎn)生訪存沖突，所以每次只能順序訪問(wèn)其中的一個(gè)元素，致使實(shí)際頻寬降低成1/4。,圖6.1944數(shù)組的直接按行存貯(m=n=4),圖6.2044數(shù)組一種錯(cuò)位存放的方案(m=n=4,δ1=δ2=1),假設(shè)在nn的二維數(shù)組中，同一列兩個(gè)相鄰元素在并行存貯器中錯(cuò)開(kāi)的地址距離為δ1，而同一行兩個(gè)相

22、鄰元素在并行存貯器中錯(cuò)開(kāi)的距離為δ2，當(dāng)m取成22p+1(p為任意正整數(shù))時(shí)，實(shí)現(xiàn)無(wú)沖突訪問(wèn)的充分條件就是讓?duì)?=2p,δ2=1。圖6.21就是對(duì)44的二維數(shù)組按上述規(guī)則存貯的一種方案。其中p=1,m=5,δ1=2,δ2=1。,圖6.2144數(shù)組錯(cuò)位存放的例子(m=5,n=4,δ1=2,δ2=1),圖6.2245二維數(shù)組在并行存貯器中存放的例子(m=7,n=6),,6.2并行處理機(jī)舉例,6.2.1ILLIACⅣ陣列處理機(jī),圖6.23ILLIACⅣ的組成,PE的字長(zhǎng)為64位，內(nèi)部主要包括4個(gè)64位的寄存器，它們是累加器A、操作數(shù)寄存器B、數(shù)據(jù)路由寄存器R、通用存貯寄存器S。其運(yùn)算部分有一個(gè)加

23、法/乘法器、邏輯部件以及分別用于算術(shù)、布爾和移位操作的桶形開(kāi)關(guān)。另有一個(gè)16位的變址寄存器X，一個(gè)8位的用于存放測(cè)試結(jié)果和PE屏蔽標(biāo)志的方式寄存器，一個(gè)形成訪存地址的地址加法器。在PE中能進(jìn)行64或32位浮點(diǎn)運(yùn)算、48或24位定點(diǎn)運(yùn)算、8位字符處理、64位邏輯運(yùn)算等。所有PE都按CU播送來(lái)的指令工作，但可通過(guò)屏蔽標(biāo)志來(lái)確定本PE是否活躍，即是否執(zhí)行該指令。PEMi是依附于PEi的局部存貯器，容量為2K字。,并行讀寫(xiě)磁盤(pán)用作后援存貯器，容量為109位。傳送控制器將數(shù)據(jù)從磁盤(pán)取到PEM時(shí)，按CU來(lái)的要求向B6500發(fā)中斷請(qǐng)求。緩沖I/O存貯器用作B6500的緩沖。I/O接口用作處理單元陣列與I/O

24、子系統(tǒng)及磁盤(pán)間的數(shù)據(jù)通路轉(zhuǎn)接和緩沖。PEM中的指令或數(shù)據(jù)經(jīng)CU總線送往CU，每次可送8個(gè)字，即512位。CU經(jīng)64位的公共數(shù)據(jù)總線向所有PE播送公用信息，經(jīng)指令控制線向所有PE發(fā)送控制命令。方式位線共64根，每個(gè)PEi有一根，用來(lái)向CU傳送該P(yáng)Ei的方式寄存器中的方式位。,6.2.2BSP科學(xué)處理機(jī),圖6.24BSP的5級(jí)數(shù)據(jù)流水線結(jié)構(gòu)示意圖,圖6.25BSP科學(xué)處理機(jī)系統(tǒng)組成,6.2.3MPP位平面陣列處理機(jī),圖6.26MPP并行處理機(jī)原理框圖,6.2.4CM連接機(jī),圖6.27CM-5的組成,圖6.28二叉胖樹(shù),,6.3相聯(lián)處理機(jī),6.3.1相聯(lián)處理機(jī)和相聯(lián)存貯器的組成1.相聯(lián)處理機(jī)的特點(diǎn)和

25、組成,圖6.29相聯(lián)處理機(jī)的構(gòu)成,2.相聯(lián)存貯器的組成及相聯(lián)處理機(jī)的結(jié)構(gòu)類型,圖6.30相聯(lián)存貯器的組成,圖6.31相聯(lián)存貯器位單元的邏輯電路方案,6.3.2相聯(lián)檢索算法,1)全等查找算法所謂全等查找，是指找出與比較數(shù)寄存器CR未屏蔽的那部分內(nèi)容完全相同的全部字單元。因此，只要將比較查找的內(nèi)容裝入比較數(shù)寄存器CR中，然后對(duì)屏蔽寄存器MR中為“1”的那些位片段，逐位地進(jìn)行相聯(lián)查找即可。凡出現(xiàn)與比較數(shù)寄存器內(nèi)容不相等，即當(dāng)CRj=1而B(niǎo)ij=0或CRj=0而B(niǎo)ij=1時(shí)，查找產(chǎn)生的信號(hào)將字選擇寄存器的WSRi置成“0”。這樣，只要等各位片逐一查找比較完畢之后，字選擇寄存器WSR中標(biāo)志位仍為1的

26、那些存貯單元就是全等查找的響應(yīng)單元，其內(nèi)容必定與比較數(shù)完全相等。由于全等查找比較簡(jiǎn)單，如采用全并行方式工作的相聯(lián)存貯器，硬件保證位片間同時(shí)操作，將使查找速度有顯著提高。,2)最大值查找算法所謂最大值查找，是要找出存貯器中所存的最大數(shù)及存放此最大數(shù)的所有單元，相同的最大值完全可能有多個(gè)。與全等查找算法類似，同樣可以事先設(shè)置好屏蔽寄存器和字選擇寄存器的初始狀態(tài)來(lái)控制位向和字向的哪些部分參與查找。首先，將字選擇寄存器置成全“1”，比較數(shù)寄存器CR置初始值為全“1”，屏蔽寄存器的最高位置為“1”、其余位置為“0”。然后，進(jìn)行比較，看是否有單元響應(yīng)。這時(shí)只是檢查各待查單元的最高位是否為1。,若有響應(yīng)，

27、表明最大值的最高位為1，讓所有未響應(yīng)單元產(chǎn)生信號(hào)，將字選擇寄存器的對(duì)應(yīng)位WSRi都置成“0”，使其不再繼續(xù)參與下一個(gè)位片的查找；如果沒(méi)有一個(gè)響應(yīng)，表明最大值的最高位為0，因此只要將比較數(shù)寄存器的該位改置為“0”，并維持字選擇寄存器中的內(nèi)容不變即可。下一步，將屏蔽寄存器的次高位置為“1”，其余位置為“0”，再進(jìn)行類似的比較及處理。這樣，自左到右逐位比較處理完畢，其比較數(shù)寄存器中保留的內(nèi)容就是要找的最大值，而字選擇寄存器中的狀態(tài)就是存放此最大值所在存貯單元的位置。,3)幅值比較查找算法幅值比較查找是指在給定某比較數(shù)后，要分別找出存貯器中內(nèi)容大于、等于、小于該比較數(shù)的單元位置，也就是將存貯器的單元

28、按給定幅值進(jìn)行比較，將其分成3類。為此，可對(duì)每個(gè)單元設(shè)置一個(gè)三位的標(biāo)志位XYZ。查找開(kāi)始前，設(shè)各單元的標(biāo)志位XYZ為100，表示“未定”狀態(tài)。然后自左至右逐位查找，結(jié)果可能會(huì)出現(xiàn)下面3種狀況：(1)CRj=0,Bij=1。這表示i單元第j位的值大于比較數(shù)第j位的值，可以置標(biāo)志位XYZ為010，此后，該i單元不再參與比較；,(2)CRj=1,Bij=0。這表示i單元第j位的值小于比較數(shù)第j位的值，可以置標(biāo)志位XYZ為001，此后，該i單元也不再參與比較；(3)CRj=Bij。這表示i單元的第j位的值等于比較數(shù)第j位的值，讓標(biāo)志位維持100不變，之后，該i單元仍繼續(xù)參與下一個(gè)位片的比較。如果將所有單元從最高位到最低位全部查找一遍，根據(jù)各個(gè)單元標(biāo)志位XYZ的狀態(tài)就能知道哪些單元的內(nèi)容等于比較數(shù)，哪些大于比較數(shù)，哪些小于比較數(shù)。這樣，按幅值分類的工作也就完成了。4)其他算法,6.3.3相聯(lián)處理機(jī)結(jié)構(gòu)舉例,1.PEPE系統(tǒng),圖6.32PEPE系統(tǒng)的邏輯結(jié)構(gòu),2.STARAN系統(tǒng),圖6.33STARAN機(jī)系統(tǒng)結(jié)構(gòu)框圖,圖6.34相聯(lián)陣列模塊的結(jié)構(gòu),,