1、計(jì)算機(jī)體系結(jié)構(gòu)金星陣列處理機(jī)課件計(jì)算機(jī)體系結(jié)構(gòu)金星陣列處理機(jī)課件1、 SIMD基本構(gòu)形(1)分布式存儲(chǔ)器(2)集中式存儲(chǔ)器 牛牛文庫文檔分享1、 SIMD基本構(gòu)形(1)分布式存儲(chǔ)器www.niuwk.LM0互連網(wǎng)絡(luò)PE0CULM1PE1LMn-1PEn-1IOP分布式存儲(chǔ)器 牛牛文庫文檔分享LM0互連網(wǎng)絡(luò)PE0CULM1PE1LMn-1PEn-1PE0互連網(wǎng)絡(luò)CUPE1PEn-1IOPSM0SM1SMk-1集中式存儲(chǔ)器 牛牛文庫文檔分享PE0互連網(wǎng)絡(luò)CUPE1PEn-1IOPSM0SM12、陣列處理機(jī)與流水線機(jī)比較性能陣列處理機(jī)向量處理機(jī)冗余情況資源重復(fù)時(shí)間重疊并行類型同時(shí)性并發(fā)性設(shè)備利用率低

2、高提高速度的措施增大 處理單元數(shù)縮短時(shí)鐘周期單元連接方法簡(jiǎn)單規(guī)整的互連網(wǎng)絡(luò)一般連接機(jī)型專用機(jī)通用機(jī) 牛牛文庫文檔分享2、陣列處理機(jī)與流水線機(jī)比較性能陣列處理機(jī)向量處理機(jī)冗余情況二、并行算法1、I LLIAC IV的處理單元陣列結(jié)構(gòu) 牛牛文庫文檔分享二、并行算法1、I LLIAC IV的處理單元陣列結(jié)構(gòu)www 牛牛文庫文檔分享 牛牛文庫文檔分享I LLIAC IV的處理單元陣列結(jié)構(gòu)特點(diǎn)N=64處理單元數(shù)構(gòu)成8*8陣列第i個(gè)處理單元PUi與以下四個(gè)單元連接上: ( i 8 ) mod 64下: ( i + 8 ) mod 64左: ( i - 1 ) mod 64右: ( i + 1 ) mod

3、64網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)間最短路徑長度的最大值。對(duì)于n*n的陣列，網(wǎng)絡(luò)直徑為n-1 牛牛文庫文檔分享I LLIAC IV的處理單元陣列結(jié)構(gòu)特點(diǎn)N=64處理單元數(shù)2、并行算法舉例矩陣加：C=A+B，其中A，B，C為8*8的矩陣并行算法對(duì)數(shù)據(jù)存儲(chǔ)的要求：不同向量相同位置的元素放在同一個(gè)存儲(chǔ)器內(nèi)，同一向量的各元素放在不同存儲(chǔ)器的同一地址單元中。A(0,1)B(0,1)C(0,1)A(0,0)B(0,0)C(0,0)A(7,7)B(7,7)C(7,7)aa+1a+2PEM0 PEM1 PEM63LDA ALPHAADRN ALPHA+1STA ALPHA+2 牛牛文庫文檔分享2、并行算法舉例矩

4、陣加：C=A+B，其中A，B，C為8*8的三、SIMD計(jì)算機(jī)的互連網(wǎng)絡(luò)1、基本概念(1)互連網(wǎng)絡(luò)的定義 互連網(wǎng)絡(luò)是一種由開關(guān)元件按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)，用于實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或多個(gè)功能部件之間的相互連接。 牛牛文庫文檔分享三、SIMD計(jì)算機(jī)的互連網(wǎng)絡(luò)1、基本概念www.niuwk.(2)互連網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)結(jié)構(gòu)簡(jiǎn)單，降低成本互連靈活，滿足應(yīng)用要求步距小，提高速度結(jié)構(gòu)規(guī)整，擴(kuò)充性好 牛牛文庫文檔分享(2)互連網(wǎng)絡(luò)的設(shè)計(jì)目標(biāo)結(jié)構(gòu)簡(jiǎn)單，降低成本www.niuwk(3)互連網(wǎng)絡(luò)的分類靜態(tài)連接網(wǎng)絡(luò)：使用直接鏈路連接各結(jié)點(diǎn)，并且構(gòu)成后結(jié)點(diǎn)間的連接方式就固定不變的網(wǎng)絡(luò)。用于構(gòu)造通信模

5、式可預(yù)測(cè)或可用靜態(tài)連接實(shí)現(xiàn)的計(jì)算機(jī)系統(tǒng)。 動(dòng)態(tài)連接網(wǎng)絡(luò)： 結(jié)點(diǎn)之間的連接不固定，使用開關(guān)或仲裁器實(shí)現(xiàn)結(jié)點(diǎn)之間的互連，根據(jù)程序要求動(dòng)態(tài)連接開關(guān)，常用于集中式共享存儲(chǔ)器多處理系統(tǒng)。 牛牛文庫文檔分享(3)互連網(wǎng)絡(luò)的分類靜態(tài)連接網(wǎng)絡(luò)：(4)互連函數(shù)互連函數(shù)(路由函數(shù))： N個(gè)輸入端的結(jié)點(diǎn)號(hào)與N個(gè)輸出端的結(jié)點(diǎn)號(hào)的一種對(duì)應(yīng)關(guān)系可以用一個(gè)映射函數(shù)表示，稱為互連函數(shù)。它是處理單元集合對(duì)于自身的雙射映射，所以又稱為“置換”，或者“循環(huán)”。把互連網(wǎng)絡(luò)的n個(gè)結(jié)點(diǎn)用0, , n-1表示，則f(x)表示以結(jié)點(diǎn)x為入端的通道的出端。 牛牛文庫文檔分享(4)互連函數(shù)互連函數(shù)(路由函數(shù))：www.niuwk.co互連函數(shù)有

6、多種表示方式，如下例所示：f(0)=1f(1)=2f(2)=0f(3)=3a.枚舉法01230123b.開關(guān)狀態(tài)圖f=(0,1,2)(3)d.循環(huán)函數(shù)一個(gè)網(wǎng)絡(luò)通過開關(guān)切換可以形成多個(gè)映射關(guān)系，所以要用“互連函數(shù)族”來定義一個(gè)網(wǎng)絡(luò)。f= 0 1 2 3 1 2 0 3c.列表法 牛牛文庫文檔分享互連函數(shù)有多種表示方式，如下例所示：f(0)=100b.開關(guān)2 基本的單級(jí)互連網(wǎng)絡(luò)立方體PM2I混洗交換 牛牛文庫文檔分享2 基本的單級(jí)互連網(wǎng)絡(luò)立方體 牛牛立方體網(wǎng)絡(luò)連接規(guī)律：每個(gè)處理單元只能直接連接到它的二進(jìn)制編號(hào)某位取反的處理單元上。Cube0(P2 P1 P0)= P2 P1 P0Cube1(P2

7、P1 P0)= P2 P1 P0Cube2(P2 P1 P0)= P2 P1 P0 Cube0: ( 0 1 ) ( 2 3 ) ( 4 5 ) ( 6 7 ) Cube1 : ( 0 2 ) ( 1 3 ) ( 4 6 ) ( 5 7 ) Cube2 : ( 0 4 ) ( 1 5 ) ( 2 6 ) ( 3 7 ) 牛牛文庫文檔分享立方體網(wǎng)絡(luò)連接規(guī)律：每個(gè)處理單元只能直接連接到它的二進(jìn)制編號(hào)一般情況下，一個(gè)n( )維超立方體共有n個(gè)互連函數(shù)(分別由n位地址中的每一位求反位值來確定)：Cube0，Cube1，Cuben-1Cubei的功能是對(duì)入端結(jié)點(diǎn)編號(hào)二進(jìn)制形式的第i位取反 Cubei(P

8、n-1Pi+1PiPi-1P0)=Pn-1Pi+1PiPi-1P0，其中0in-1網(wǎng)絡(luò)直徑：立方體網(wǎng)絡(luò)直徑為n立方體網(wǎng)絡(luò)是一個(gè)可逆網(wǎng)絡(luò) 牛牛文庫文檔分享一般情況下，一個(gè)n( 連接規(guī)律：j號(hào)處理單元直接連接到j(luò)2i號(hào)處理單元PM2I函數(shù)定義：功能是對(duì)入端結(jié)點(diǎn)編號(hào)加或減2i，然后再作模N運(yùn)算。PM2+i（j）= (j + 2i) mod NPM2-i（j）= (j - 2i) mod N 其中j = 0 N - 1，i = 0 n - 1。PM2I函數(shù)共有n對(duì)成員，分別是PM20，PM21，PM2(n-1)。由于PM2(n-1)的函數(shù)值相等，所以只有2n-1個(gè)函數(shù) 網(wǎng)絡(luò)直徑：(2)PM2I網(wǎng)(移數(shù)

9、網(wǎng)、單級(jí)加減2i網(wǎng)） 牛牛文庫文檔分享連接規(guī)律：j號(hào)處理單元直接連接到j(luò)2i號(hào)處理單元(2)PMN=8時(shí)，有5個(gè)不同的互連函數(shù)PM2+0：( 0 1 2 3 4 5 6 7 )PM2-0：(7 6 5 4 3 2 1 0)PM2+1：( 0 2 4 6 )(1 3 5 7 )PM2-1： (6 4 2 0 )(7 5 3 1 )PM2+2：( 0 4 ) ( 2 6 ) ( 1 5 ) ( 3 7 ) 牛牛文庫文檔分享N=8時(shí)，有5個(gè)不同的互連函數(shù)PM2+0：( 0 1 2 3(3)均勻混洗交換網(wǎng)絡(luò)該網(wǎng)絡(luò)由混洗函數(shù)(shuffle)與交換函數(shù)(exchange即Cube0)定義.混洗函數(shù)：將結(jié)

10、點(diǎn)的二進(jìn)制編號(hào)循環(huán)左移一位shuffle（Pn-1Pn-2P0）= Pn-2P0Pn-1f= 0 1 2 3 4 5 6 7 0 2 4 6 1 3 5 7 牛牛文庫文檔分享(3)均勻混洗交換網(wǎng)絡(luò)該網(wǎng)絡(luò)由混洗函數(shù)(shuffle)與交n=3的混洗網(wǎng)絡(luò)拓?fù)湫螤钊缦聢D綠線所示，可以看出它不是一個(gè)連通圖，所以還需要增加一個(gè)交換函數(shù)（圖中紅線所示），才能構(gòu)成完整的單級(jí)混洗交換網(wǎng)絡(luò)。 單級(jí)混洗交換網(wǎng)絡(luò)的直徑是2n-1。f= 0 1 2 3 4 5 6 7 0 2 4 6 1 3 5 7 牛牛文庫文檔分享n=3的混洗網(wǎng)絡(luò)拓?fù)湫螤钊缦聢D綠線所示，可以看出它不是一個(gè)連3、多級(jí)互連網(wǎng) 定義：多級(jí)ICN使用多級(jí)開

11、關(guān)，將多個(gè)單級(jí)網(wǎng)絡(luò)串聯(lián)，以實(shí)現(xiàn)任意兩個(gè)處理單元之間的連接。將多級(jí)互連網(wǎng)絡(luò)循環(huán)使用可實(shí)現(xiàn)復(fù)雜的互連。 通常在N個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)中，多級(jí)ICN由n級(jí)構(gòu)成（n = log2N）。 經(jīng)典的多級(jí)互連網(wǎng)有多級(jí)立方體網(wǎng)、多級(jí)混洗交換網(wǎng)和多級(jí)PM2I網(wǎng)。 牛牛文庫文檔分享3、多級(jí)互連網(wǎng) 定義：多級(jí)ICN使用多級(jí)開關(guān)，將多個(gè)單級(jí)網(wǎng)多級(jí)網(wǎng)絡(luò)的三個(gè)參數(shù)：(1)交換開關(guān)：二元交換開關(guān)的基本接通狀態(tài)有“直連”、“交換”、“上播”和“下播”。直通交換上播下播(2)拓?fù)浣Y(jié)構(gòu)(3)控制方式 牛牛文庫文檔分享多級(jí)網(wǎng)絡(luò)的三個(gè)參數(shù)：(1)交換開關(guān)：二元交換開關(guān)的基本接通狀(3)控制方式各開關(guān)的控制信號(hào)可采用3種分配方式之一：級(jí)控方式、

12、部分級(jí)控方式和單元控制方式。級(jí)控方式就是同一級(jí)（即同一列）開關(guān)共用一個(gè)控制信號(hào)，動(dòng)作保持一致；部分級(jí)控方式在第i級(jí)設(shè)置i+1個(gè)獨(dú)立的控制信號(hào)，每個(gè)信號(hào)管轄若干開關(guān)；單元控制方式為每個(gè)開關(guān)獨(dú)自設(shè)置一個(gè)控制信號(hào)，各開關(guān)動(dòng)作獨(dú)立，性能比前兩種方式都更靈活，結(jié)構(gòu)也更復(fù)雜。 牛牛文庫文檔分享(3)控制方式各開關(guān)的控制信號(hào)可采用3種分配方式之一：級(jí)控方(1)多級(jí)立方體它由n級(jí)構(gòu)成，每一級(jí)包含N/2可控的二元交換開關(guān)采用二功能交換單元:直連和交換當(dāng)?shù)贗級(jí)開關(guān)處理交換狀態(tài)時(shí)，實(shí)現(xiàn)的是Cubei函數(shù) 牛牛文庫文檔分享(1)多級(jí)立方體它由n級(jí)構(gòu)成，每一級(jí)包含N/2可控的二元交換多級(jí)立方體網(wǎng)絡(luò)結(jié)構(gòu)ABCDEFGHI

13、JKL0123456701234567k = 0k = 1k = 20011223344556677 牛牛文庫文檔分享多級(jí)立方體網(wǎng)絡(luò)結(jié)構(gòu)ABCDEFGHIJKL012345670多級(jí)立方體網(wǎng)絡(luò)特點(diǎn)續(xù)：采作三種不同的控制方式，可以構(gòu)成三種不現(xiàn)的互連網(wǎng)絡(luò)：級(jí)控制構(gòu)成STARAN交換網(wǎng)絡(luò)部分級(jí)控制構(gòu)成STARAN移數(shù)網(wǎng)絡(luò)單元控制構(gòu)成間接立方體網(wǎng)絡(luò)靈活性好 牛牛文庫文檔分享多級(jí)立方體網(wǎng)絡(luò)特點(diǎn)續(xù)：采作三種不同的控制方式，可以構(gòu)成三種不STARAN交換網(wǎng)絡(luò)級(jí)控制信號(hào)(二進(jìn)制)：K2K1K0 Ki=0表示第i級(jí)的開關(guān)為直連狀態(tài)， Ki=1表示第i級(jí)的開關(guān)為交換狀態(tài)例：已知入端號(hào)和控制信號(hào)，求出端號(hào)若控制信號(hào)

14、Ki=1，則入端號(hào)的第 i 位取反例：已知入端號(hào)和出端號(hào)，求控制信號(hào)控制信號(hào)=入端號(hào)和出端號(hào)異或 牛牛文庫文檔分享STARAN交換網(wǎng)絡(luò)級(jí)控制信號(hào)(二進(jìn)制)：K2K1K0例：已恒等4組2元+2組4元4組2元 牛牛文庫文檔分享恒等4組2元4組2元 牛牛文庫文檔 牛牛文庫文檔分享 牛牛文庫文檔分享(2)多級(jí)混洗交換網(wǎng)絡(luò)多級(jí)混洗交換網(wǎng)絡(luò)又稱為Omega網(wǎng)。多級(jí)混洗交換網(wǎng)絡(luò)結(jié)構(gòu)：它由n級(jí)構(gòu)成，每一級(jí)包含一個(gè)全混拓?fù)渚€路和一列(N/2個(gè))可控的二元交換開關(guān)四功能交換單元控制方式：?jiǎn)卧刂?牛牛文庫文檔分享(2)多級(jí)混洗交換網(wǎng)絡(luò)多級(jí)混洗交換網(wǎng)絡(luò)又稱為Omega網(wǎng)多級(jí)混洗交換網(wǎng)絡(luò)結(jié)構(gòu)IJKLEFGHABCD0

15、123456701234567 牛牛文庫文檔分享多級(jí)混洗交換網(wǎng)絡(luò)結(jié)構(gòu)IJKLEFGHABCD0123456多級(jí)混洗交換網(wǎng)絡(luò)的特點(diǎn)續(xù)：在多級(jí)混洗交換網(wǎng)絡(luò)中，單獨(dú)一級(jí)混洗拓?fù)渚€路可完成一次數(shù)據(jù)混洗（shuffle），而單獨(dú)一列二元交換開關(guān)在處于“交換”狀態(tài)時(shí)可完成一次交換操作（Cube0）。如果各級(jí)二元交換開關(guān)都處于“直連”狀態(tài)，N個(gè)結(jié)點(diǎn)的數(shù)據(jù)通過網(wǎng)絡(luò)僅經(jīng)過n次混洗操作，排列順序最終恢復(fù)輸入狀態(tài)；如果各級(jí)二元交換開關(guān)都處于“交換”狀態(tài)，則N個(gè)結(jié)點(diǎn)的數(shù)據(jù)在每次混洗之后緊接著一次交換（Cube0），也就是地址碼的最低位取反，最后n位地址均被取反。程序員根據(jù)數(shù)據(jù)置換或復(fù)制的需要，可以靈活地設(shè)置各開關(guān)的狀

16、態(tài)。 牛牛文庫文檔分享多級(jí)混洗交換網(wǎng)絡(luò)的特點(diǎn)續(xù)：在多級(jí)混洗交換網(wǎng)絡(luò)中，單獨(dú)一級(jí)多級(jí)混洗交換網(wǎng)絡(luò)與多級(jí)立方體網(wǎng)絡(luò)的關(guān)系k = 0k = 1k = 2012345670426153702134657IJKLEFGHABCD0123456701234567 牛牛文庫文檔分享多級(jí)混洗交換網(wǎng)絡(luò)與多級(jí)立方體網(wǎng)絡(luò)的關(guān)系k = 0k = 1(3)多級(jí)PM2I包含n級(jí)單元間連接，每一級(jí)前后兩列 的單元都按PM2I拓?fù)溥B接。第I級(jí)的每一個(gè)入端都連接到三個(gè)出端：j、(j + 2i) mod N、 (j - 2i) mod N控制方式：部分級(jí)控制構(gòu)成數(shù)據(jù)變換網(wǎng)絡(luò)DM采用單元控制構(gòu)成強(qiáng)化數(shù)據(jù)變換網(wǎng)絡(luò)ADM 牛牛文庫文檔

17、分享(3)多級(jí)PM2I包含n級(jí)單元間連接，每一級(jí)前后兩列 的單元(4)全排列網(wǎng)絡(luò)非阻塞式網(wǎng)絡(luò)：所有入端、出端的連接都不發(fā)生沖突的網(wǎng)絡(luò)，又稱為全排列網(wǎng)絡(luò)N個(gè)結(jié)點(diǎn)的全部排列有N!種阻塞式網(wǎng)絡(luò)(Blocking ):在實(shí)現(xiàn)兩對(duì)或多對(duì)入出端連接時(shí)，都因可能因爭(zhēng)用數(shù)據(jù)傳送路徑而發(fā)生沖突的網(wǎng)絡(luò)。立方體網(wǎng)絡(luò)、PM2I、Omega網(wǎng)絡(luò)都是阻塞式網(wǎng)絡(luò)N個(gè)結(jié)點(diǎn)的多級(jí)阻塞式網(wǎng)絡(luò)在一次傳送這中能實(shí)現(xiàn)的排列有NN/2種 牛牛文庫文檔分享(4)全排列網(wǎng)絡(luò)非阻塞式網(wǎng)絡(luò)：所有入端、出端的連接都不發(fā)生沖 Benes網(wǎng)絡(luò)：三維立方體多級(jí)網(wǎng)絡(luò)和它的可逆網(wǎng)絡(luò)構(gòu)成的全排列網(wǎng)絡(luò)k = 0k = 1k = 2ABCDEFGHIJKL012

18、34567012345670123456702134657 牛牛文庫文檔分享 Benes網(wǎng)絡(luò)：三維立方體多級(jí)網(wǎng)絡(luò)和它的可逆網(wǎng)絡(luò)構(gòu)成的全排 Benes網(wǎng)絡(luò)：三維立方體多級(jí)網(wǎng)絡(luò)和它的可逆網(wǎng)絡(luò)構(gòu)成的全排列網(wǎng)絡(luò)k = 0k = 1k = 2ABCDEFGHIJKL01234567012345670123456702134657 牛牛文庫文檔分享 Benes網(wǎng)絡(luò)：三維立方體多級(jí)網(wǎng)絡(luò)和它的可逆網(wǎng)絡(luò)構(gòu)成的全排Benes網(wǎng)絡(luò)：三維立方體多級(jí)網(wǎng)絡(luò)和它的可逆網(wǎng)絡(luò)構(gòu)成的全排列網(wǎng)絡(luò)k = 0k = 1k = 2ABCDEFGHIJKL01234567012345670123456702134657k = 0k = 1

19、k = 2ABCDEFGHIJKL01234567012345670123456702134657 牛牛文庫文檔分享Benes網(wǎng)絡(luò)：三維立方體多級(jí)網(wǎng)絡(luò)和它的可逆網(wǎng)絡(luò)構(gòu)成的全排列四、并行存儲(chǔ)器的無沖突訪問陣列處理機(jī)中，存儲(chǔ)器要采用多體并行，才能保證其頻寬與多個(gè)處理單元速度匹配，還要保證實(shí)現(xiàn)無沖突訪存操作(即要訪問的數(shù)據(jù)不在同一體內(nèi))以數(shù)組為例：數(shù)組的訪問模式：行、列、主對(duì)角線、次對(duì)角線、子方陣 牛牛文庫文檔分享四、并行存儲(chǔ)器的無沖突訪問陣列處理機(jī)中，存儲(chǔ)器要采用多體并行1、一維數(shù)組連續(xù)訪問m=4個(gè)元素，無沖突按2i變址，沖突，存儲(chǔ)器頻寬降低一半為了避免沖突，M應(yīng)取質(zhì)數(shù)(只要變址跳距與m互質(zhì)) 牛牛文庫文檔分享1、一維數(shù)組連續(xù)訪問m=4個(gè)元素，無沖突www.niuwk.2、二維數(shù)組同時(shí)訪問某一行、主對(duì)角線、次對(duì)角線上的所有元素時(shí)，無沖突同時(shí)訪問某一列時(shí)，沖突，存儲(chǔ)器頻寬降低為1/4 牛牛文庫文檔分享2、二維數(shù)組同時(shí)訪問某一行、主對(duì)角線、次對(duì)角線上的所有元素時(shí)錯(cuò)位存放方案一中主對(duì)角線和次對(duì)角線并行訪問沖突方案二中當(dāng)訪問模式為行、列、主對(duì)角線、次對(duì)角線、子方陣時(shí)均無沖突 牛牛文庫文檔分享錯(cuò)位存放方案一中主對(duì)角線和次對(duì)角線并行訪問沖突www.niu(1)無沖突訪問錯(cuò)位存放方案的一種實(shí)現(xiàn)思想：