第6章__陣列處理機

1、第第6 6章章 陣列處理機陣列處理機6.1 6.1 陣列處理機原理陣列處理機原理6.2 6.2 陣列處理機的并行算法陣列處理機的并行算法6.3 SIMD6.3 SIMD計算機的網(wǎng)絡(luò)互連計算機的網(wǎng)絡(luò)互連6.4 6.4 并行存儲器的無沖突訪問并行存儲器的無沖突訪問6.5 6.5 并行處理機舉例并行處理機舉例本章重點：本章重點： 總的要求是理解陣列處理機的結(jié)構(gòu)和工作原總的要求是理解陣列處理機的結(jié)構(gòu)和工作原理。了解與流水處理機的差別。理解在陣列處理。了解與流水處理機的差別。理解在陣列處理機解題時對并行算法及存儲單元分配規(guī)則、理機解題時對并行算法及存儲單元分配規(guī)則、互連網(wǎng)絡(luò)等的特殊要求。熟練掌握基本的單

2、級互連網(wǎng)絡(luò)等的特殊要求。熟練掌握基本的單級網(wǎng)絡(luò)及其互連函數(shù)表示。理解循環(huán)互連網(wǎng)絡(luò)的網(wǎng)絡(luò)及其互連函數(shù)表示。理解循環(huán)互連網(wǎng)絡(luò)的實現(xiàn)。熟練掌握多級網(wǎng)絡(luò)、全排列網(wǎng)絡(luò)的畫法。實現(xiàn)。熟練掌握多級網(wǎng)絡(luò)、全排列網(wǎng)絡(luò)的畫法。理解解決并行存儲器無沖突訪問的辦法。理解解決并行存儲器無沖突訪問的辦法。 互連函數(shù)和多級互連網(wǎng)絡(luò)?；ミB函數(shù)和多級互連網(wǎng)絡(luò)。本章難點：本章難點： 并行算法和多級互連網(wǎng)絡(luò)。并行算法和多級互連網(wǎng)絡(luò)。6.1 6.1 陣列處理機原理陣列處理機原理6.1.1 6.1.1 陣列處理機的基本構(gòu)形陣列處理機的基本構(gòu)形 陣列處理機陣列處理機(Array Processor),(Array Processor),

3、也稱為并也稱為并行處理機行處理機(Parallel Processor)(Parallel Processor)主要用于對大主要用于對大量向量、數(shù)組要求高速運算的場合。量向量、數(shù)組要求高速運算的場合。 陣列處理機是重復(fù)設(shè)置處理單元按一定方陣列處理機是重復(fù)設(shè)置處理單元按一定方式連成陣列在單一控制部件控制下對各自分配式連成陣列在單一控制部件控制下對各自分配的數(shù)據(jù)執(zhí)行同一指令規(guī)定的操作，是操作級并的數(shù)據(jù)執(zhí)行同一指令規(guī)定的操作，是操作級并行的行的SIMDSIMD的計算機。的計算機。 由于存儲器的組成方式不同，陣列處理機由于存儲器的組成方式不同，陣列處理機有兩種不同的基本構(gòu)形。有兩種不同的基本構(gòu)形。 1

4、 1、分布式存儲器的陣列處理機構(gòu)形、分布式存儲器的陣列處理機構(gòu)形 各各處理單元有局部存儲器處理單元有局部存儲器PEM(Processing PEM(Processing Element Memory)Element Memory)存放被分布的數(shù)據(jù)，只能被存放被分布的數(shù)據(jù)，只能被本處理單元直接訪問。在控制部件本處理單元直接訪問。在控制部件CUCU上有一上有一主存可傳播給各個處理單元，運算中可通過主存可傳播給各個處理單元，運算中可通過互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)ICNICN交換數(shù)據(jù)。交換數(shù)據(jù)。 在執(zhí)行主存中的用戶程序時，所有指令都在執(zhí)行主存中的用戶程序時，所有指令都在控制部件中進行譯碼，把只適合串行處理在控制

5、部件中進行譯碼，把只適合串行處理的標量或控制類指令留給控制部件的標量或控制類指令留給控制部件CUCU自己執(zhí)自己執(zhí)行，而把適合于并行處理的向量類指令行，而把適合于并行處理的向量類指令“播播送送”給各個給各個PEPE，控制處于，控制處于“活躍活躍”的那些的那些PEPE并行執(zhí)行。下圖是采用分布式存儲器的陣列并行執(zhí)行。下圖是采用分布式存儲器的陣列處理機構(gòu)形。處理機構(gòu)形。PEM0ICN互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)PE0CUCUMPEM1PE1PEMN-1PEN-1I/O接口接口SCD控制控制數(shù)據(jù)總線數(shù)據(jù)總線控制總線控制總線控制控制具有分布式存儲器的陣列處理機構(gòu)形具有分布式存儲器的陣列處理機構(gòu)形 為了有效高速地處理向

6、量數(shù)據(jù)，這種構(gòu)形要為了有效高速地處理向量數(shù)據(jù)，這種構(gòu)形要求能把數(shù)據(jù)合理地預(yù)分配到各個處理單元的局求能把數(shù)據(jù)合理地預(yù)分配到各個處理單元的局部存儲器中，使各處理單元部存儲器中，使各處理單元PEPEi i主要用自己的局主要用自己的局存存PEMPEMi i中的數(shù)據(jù)運算。中的數(shù)據(jù)運算。 采用這種構(gòu)形的陣列處理機是采用這種構(gòu)形的陣列處理機是SIMDSIMD的主流。的主流。典型機器有典型機器有ILLIAC ILLIAC 、MPPMPP、 DAPDAP、CM-2CM-2、MP-1MP-1、DAP600DAP600系列等。系列等。 2 2、集中式共享存儲器的陣列處理機構(gòu)形、集中式共享存儲器的陣列處理機構(gòu)形 系統(tǒng)

7、存儲器由系統(tǒng)存儲器由K K個存儲體集中組成，并經(jīng)個存儲體集中組成，并經(jīng)ICNICN為全部為全部N N個處理單元所共享。個處理單元所共享。 為使各處理單元對長度為為使各處理單元對長度為N N的向量中各個元的向量中各個元素都能同時并行處理，存儲體體數(shù)素都能同時并行處理，存儲體體數(shù)K K應(yīng)等于或多應(yīng)等于或多于處理單元數(shù)于處理單元數(shù)N N。PEPE0 0ICNICN互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)CUCUPEPE1 1PEPEN-1N-1I/O-CHI/O-CHMMMM0 0MMMM1 1MMMMk-1k-1 SC SC I/O I/OSMSM具有集中式共享存儲器的陣列處理機構(gòu)形具有集中式共享存儲器的陣列處理機構(gòu)形

8、各處理單元在訪主存時，為避免發(fā)生分體沖各處理單元在訪主存時，為避免發(fā)生分體沖突，也要求有合適的算法能將數(shù)據(jù)合理地分配到突，也要求有合適的算法能將數(shù)據(jù)合理地分配到各個存儲體中。各個存儲體中。 互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)ICNICN是用于在處理單元與存儲器分是用于在處理單元與存儲器分體之間進行轉(zhuǎn)接構(gòu)成數(shù)據(jù)通路，使各處理單元能體之間進行轉(zhuǎn)接構(gòu)成數(shù)據(jù)通路，使各處理單元能高速靈活地動態(tài)與不同的存儲體相連，使盡可能高速靈活地動態(tài)與不同的存儲體相連，使盡可能多的多的PEPE能無沖突地訪問共享的主存模塊。能無沖突地訪問共享的主存模塊。 集中式共享存儲器的陣列處理機主要特點是集中式共享存儲器的陣列處理機主要特點是將資源重

9、復(fù)和時間重復(fù)結(jié)合起來開發(fā)并行性。將資源重復(fù)和時間重復(fù)結(jié)合起來開發(fā)并行性。 采用這種構(gòu)形的典型機器有采用這種構(gòu)形的典型機器有BSPBSP。6.1.2 6.1.2 陣列處理機的特點陣列處理機的特點1 1、利用資源重復(fù)而不是時間重疊；利用并行性中的同、利用資源重復(fù)而不是時間重疊；利用并行性中的同 時性而不是并發(fā)性。時性而不是并發(fā)性。2 2、資源利用率不如流水線高，但提高速度的潛資源利用率不如流水線高，但提高速度的潛 力比流水線處理機大。力比流水線處理機大。（陣列處理機主要是（陣列處理機主要是 靠增大處理單元數(shù)提高速度，向量流水處理靠增大處理單元數(shù)提高速度，向量流水處理 機主要靠縮短時鐘周期提高速度）

10、。機主要靠縮短時鐘周期提高速度）。 3 3、陣列處理機陣列處理機使用簡單規(guī)整的互連網(wǎng)絡(luò)來確定處使用簡單規(guī)整的互連網(wǎng)絡(luò)來確定處 理單元間的連接，因此，互連網(wǎng)絡(luò)設(shè)計很重要。理單元間的連接，因此，互連網(wǎng)絡(luò)設(shè)計很重要。4 4、它是以某類算法為背景的專用計算機，基本上、它是以某類算法為背景的專用計算機，基本上 是專用于向量處理的計算機是專用于向量處理的計算機( (某類算法專用機某類算法專用機) )， 故陣列處理機專用性強。故陣列處理機專用性強。5 5、陣列機的研究必須與并行算法研究密切結(jié)陣列機的研究必須與并行算法研究密切結(jié)合，以使它的求解算法適應(yīng)性更強一些，應(yīng)合，以使它的求解算法適應(yīng)性更強一些，應(yīng)用面更

11、廣一些用面更廣一些( (與并行算法結(jié)合研究與并行算法結(jié)合研究) )。 陣列處理機實質(zhì)陣列處理機實質(zhì)上是由專門對付數(shù)上是由專門對付數(shù)組運算的處理單元陣列組成的組運算的處理單元陣列組成的處理機處理機、專門從事處理單元陣列的控制及標量處專門從事處理單元陣列的控制及標量處理的理的處理機處理機和專門從事系統(tǒng)輸入輸出及和專門從事系統(tǒng)輸入輸出及操作系統(tǒng)管理的操作系統(tǒng)管理的處理機處理機組成的一個異構(gòu)組成的一個異構(gòu)型多處理機系統(tǒng)。型多處理機系統(tǒng)。6.2 6.2 陣列處理機的并行算法陣列處理機的并行算法6.2.1 ILLIAC 6.2.1 ILLIAC 的處理單元陣列結(jié)構(gòu)的處理單元陣列結(jié)構(gòu) ILLIAC IVIL

12、LIAC IV處理陣列由處理陣列由8 8 8 86464個個PUPU組成。組成。每個每個PUPU由處理部件由處理部件PEPE和它的局部存儲器和它的局部存儲器PEMPEM組組成。成。 每一個每一個PUPUi i只和它的上、下、左、右四個只和它的上、下、左、右四個近鄰直接連接。近鄰直接連接。PUPUi+1i+1 mod 64 mod 64、PUPUi-1i-1 mod 64 mod 64、PUPUi+8i+8 mod 64 mod 64、PUPUi-8i-8 mod 64 mod 64 上下方向上同一列的上下方向上同一列的PUPU連成一個環(huán)，左右連成一個環(huán)，左右方向上構(gòu)成一個閉合螺線。方向上構(gòu)成一

13、個閉合螺線。 PU56 PU57 PU63 PU63 2 3 4 5 6 PU8 PU8 10 11 12 13 14 PU16 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 PU55 58 59 60 61 62 PU0 PU0 PU1 PU7PU0PU1PU8PU9PU56PU57PU7PU15PU63 采用閉合螺線最短距離不超過采用閉合螺線最短距離不超過7 7步。而普通網(wǎng)步。而普通網(wǎng)格最短距離不超

14、過格最短距離不超過8 8步。步。這種陣列中，任意兩這種陣列中，任意兩個單元之間的最短距離不超過個單元之間的最短距離不超過 步。步。 例如：例如：從從PUPU0 0到到PUPU3636的距離：采用普通網(wǎng)格必須的距離：采用普通網(wǎng)格必須8 8步：步：PUPU0 0 PUPU1 1 PU PU2 2 PU PU3 3 PU PU4 4 PU PU1212 PU PU2020 PU PU2828 PU PU3636或或 PUPU0 0 PU PU8 8 PU PU1616 PU PU2424 PU PU3232 PUPU3333 PU PU3434 PU PU3535 PU PU3636或或 （等于（等

15、于8 8步的很多，大于步的很多，大于8 8步的更多）步的更多）如果采用閉合螺旋線，只需要如果采用閉合螺旋線，只需要7 7步：步：PUPU0 0 PU PU63 63 PU PU62 62 PU PU61 61 PU PU60 60 PU PU52 52 PU PU44 44 PU PU36361 1N N 普通網(wǎng)格必須普通網(wǎng)格必須8 8步：步：PUPU0 0 PU PU1 1 PU PU2 2 PU PU3 3 PU PU4 4 PU PU12 12 PUPU20 20 PU PU28 28 PU PU3636或或 PUPU0 0 PU PU8 8 PU PU16 16 PU PU24 24

16、PU PU32 32 PU PU33 33 PU PU34 34 PU PU35 35 PU PU3636或或 閉合螺旋線只要閉合螺旋線只要7 7步：步：PUPU0 0 PU PU63 63 PU PU62 62 PU PU61 61 PU PU60 60 PU PU52 52 PU PU44 44 PU PU3636或或 PUPU0 0 PU PU63 63 PU PU55 55 PU PU47 47 PU PU39 39 PU PU38 38 PU PU37 37 PU PU3636或或 P P180180習(xí)題習(xí)題6.16.1 解解 如圖：如圖： 與與PU0PU0相連的處理單元有：相連的處

17、理單元有：PU1PU1、PU12PU12、PU15PU15、PU4PU4 與與PU1PU1、PU12PU12、PU15PU15、PU4PU4相連的有相連的有PU2PU2、PU3PU3、PU5PU5、PU13PU13、PU8PU8、PU11PU11、PU14PU14（刪去一步單元）（刪去一步單元）與與PU2PU2、PU5PU5、PU13PU13、PU8PU8、PU11PU11、PU14PU14相連的有：相連的有：PU6PU6、PU7PU7、PU9PU9、PU10PU10（刪去一、二步單元）（刪去一、二步單元） PE0PE0經(jīng)一步可將信息傳送至經(jīng)一步可將信息傳送至PU1PU1、PU4PU4、PU1

18、2PU12、PU15PU15。 PE0PE0至少需經(jīng)二步才能將信息傳送至至少需經(jīng)二步才能將信息傳送至PU2PU2、PU3PU3、PU5PU5、PU8PU8、PU11PU11、PU13PU13、PU14PU14。 PE0PE0至少需經(jīng)三步步才能將信息傳送至至少需經(jīng)三步步才能將信息傳送至PU6PU6、PU7PU7、PU9PU9、PU10PU10。 6.2.2 6.2.2 陣列處理機的并行算法舉例陣列處理機的并行算法舉例1 1、矩陣加、矩陣加 把把C=A+BC=A+B中的屬于同一位置向量元素放在同一局部中的屬于同一位置向量元素放在同一局部存儲器中。存儲器中。兩個兩個8 8 8 8的矩陣的矩陣A A、

19、B B相加，所得結(jié)果相加，所得結(jié)果C C也也是是8 8 8 8矩陣，矩陣相加的存儲器分配如下圖所示矩陣，矩陣相加的存儲器分配如下圖所示(“(“全并行全并行”的工作特點，速度提高，但存儲單元分配的工作特點，速度提高，但存儲單元分配算法的設(shè)計比較麻煩算法的設(shè)計比較麻煩) )。 C(0,1)C(0,1)B(0,1)B(0,1)A(0,1)A(0,1)C(7,7)C(7,7)B(7,7)B(7,7)A(7,7)A(7,7)C(0,0)C(0,0)B(0,0)B(0,0)A(0,0)A(0,0) 1 1 2 2 PEMPEM0 0PEMPEM6363PEMPEM1 1矩陣相加的存儲器分配舉例矩陣相加的存

20、儲器分配舉例2 2、矩陣乘、矩陣乘 把把C=AC=A* *B B的各向量按列存放在一個局部存儲器中。的各向量按列存放在一個局部存儲器中。 設(shè)設(shè)A A、B B和和C C為為3 3個個8 8 8 8的二維矩陣，給定的二維矩陣，給定A A和和B B，計，計算算C=AC=A* *B B得得6464個分量可用公式：個分量可用公式： 其中其中0 i 70 i 7且且 0 j 70 j 7。 在在SISDSISD計算機上求解，用計算機上求解，用FORTRANFORTRAN語言編寫程序為：語言編寫程序為： DO 10 I=0,7DO 10 I=0,7 DO 10 J=0,7 DO 10 J=0,7 C(I,J

21、)=0 C(I,J)=0 DO 10 K=0,7 DO 10 K=0,7 10 C(I,J)=C(I,J)+A(I,K) 10 C(I,J)=C(I,J)+A(I,K)* *B(K,J)B(K,J) k kj j7 71 1k ki ik ki ij jb ba aC C 需經(jīng)需經(jīng)I I、J J、K K三重循環(huán)完成。每重循環(huán)執(zhí)行三重循環(huán)完成。每重循環(huán)執(zhí)行8 8次，共需次，共需512512次相乘、加得時間，且每次還要包次相乘、加得時間，且每次還要包括執(zhí)行循環(huán)控制判別等其它操作所需得時間。括執(zhí)行循環(huán)控制判別等其它操作所需得時間。 如果在如果在SIMDSIMD陣列機上運算，可用陣列機上運算，可用8

22、8個處理單個處理單元并行計算矩陣元并行計算矩陣C(I,J)C(I,J)得某一行或某一列，即將得某一行或某一列，即將J J循環(huán)或循環(huán)或I I循環(huán)轉(zhuǎn)化成一維的向量處理，從而消去循環(huán)轉(zhuǎn)化成一維的向量處理，從而消去了一重循環(huán)。以消去了一重循環(huán)。以消去J J循環(huán)為例，可執(zhí)行的循環(huán)為例，可執(zhí)行的 FORTRANFORTRAN語言編寫的程序為：語言編寫的程序為： DO 10 I=0,7DO 10 I=0,7 C(I,J)=0 C(I,J)=0 DO 10 K=0,7 DO 10 K=0,7 10 C(I,J)=C(I,J)+A(I,K) 10 C(I,J)=C(I,J)+A(I,K)* *B(K,J)B(K

23、,J) 讓讓J=07J=07各部分同時在各部分同時在PEPE0 0PEPE7 7上運算，這上運算，這樣只需樣只需K K、J J二重循環(huán)，速度可提高至二重循環(huán)，速度可提高至8 8倍，即倍，即只需只需6464次乘、加的時間。次乘、加的時間。（164164頁圖頁圖6.56.5） 每次控制部件執(zhí)行的每次控制部件執(zhí)行的PEPE指令表面上是標量指令表面上是標量指令，實際上已等效于向量指令，是指令，實際上已等效于向量指令，是8 8個個PEPE并并行地執(zhí)行同一條指令。每次播送時，利用陣列行地執(zhí)行同一條指令。每次播送時，利用陣列處理機的播送功能將處理單元處理機的播送功能將處理單元PEPEK K中累加寄存中累加寄

24、存器器RAGRAGK K的內(nèi)容經(jīng)控制部件的內(nèi)容經(jīng)控制部件CUCU播送到全部播送到全部8 8個處個處理單元的理單元的RGARGA中去。中去。 為了讓各個處理單元為了讓各個處理單元PEPEi i盡可能只訪問所帶盡可能只訪問所帶局部存儲器局部存儲器PEMPEMi i，以保證高速處理，就必須要，以保證高速處理，就必須要求對矩陣求對矩陣A A、B B、C C各分量在局部存儲器中的分各分量在局部存儲器中的分布采用布采用165165頁如圖頁如圖6.66.6所示的方案。所示的方案。3 3、累加和、累加和 把向量存到所有處理單元的局部存儲器中。把向量存到所有處理單元的局部存儲器中。 將將N N個數(shù)的順序相加轉(zhuǎn)為

25、并行相加的問題。個數(shù)的順序相加轉(zhuǎn)為并行相加的問題。 取取N=8N=8，即有，即有8 8個數(shù)個數(shù)A(I)A(I)順序累加，其中順序累加，其中 0I70I7。 在在SISDSISD計算機上可以寫成計算機上可以寫成FORTRANFORTRAN程序：程序： C=0C=0 DO 10 I=0,7 DO 10 I=0,7 10 C=C+A(I) 10 C=C+A(I) 這是一個串行程序，需要這是一個串行程序，需要8 8次加法時間。次加法時間。 在陣列處理機上用成對遞歸相加算法，只需在陣列處理機上用成對遞歸相加算法，只需 次加法時間即可。首先，原始數(shù)據(jù)次加法時間即可。首先，原始數(shù)據(jù)A(I)A(I)分別存放在

26、分別存放在8 8個個PEMPEM的的 單元中，其中單元中，其中0I70I7，求累加和的步驟如下：，求累加和的步驟如下：（1 1）置全部）置全部PEPEi i為活躍狀態(tài)，為活躍狀態(tài)， 0I70I7；（2 2）全部）全部 A(I)A(I)從從PEMPEMi i的的 單元讀到相應(yīng)單元讀到相應(yīng)PEPEi i的累加寄存的累加寄存 器器RGARGAi i中，中， 0I70I7；（3 3）令）令K=0;K=0;（4 4）將全部）將全部PEPEi i的的(RGA(RGAi i) )轉(zhuǎn)送到傳送寄存器轉(zhuǎn)送到傳送寄存器RGRRGRi i, , 0I7 0I7；（5 5）將全部）將全部PEPEi i的的(RGR(RG

27、Ri i) )經(jīng)過互連網(wǎng)絡(luò)向右傳送經(jīng)過互連網(wǎng)絡(luò)向右傳送2 2K K步距步距, , 0I7 0I7；（6 6）令）令j=2j=2K K-1;-1;（7 7）置）置PEPE0 0PEPEj j為不活躍狀態(tài)；為不活躍狀態(tài)；3 38 8l lo og g2 2 （8 8）處于活躍狀態(tài)的所有）處于活躍狀態(tài)的所有PEPEi i執(zhí)行執(zhí)行(RGA(RGAi i) )：= = (RGA (RGAi i)+ (RGR)+ (RGRi i), ji7;), ji7;（9 9） K:=K+1;K:=K+1;（1010）如）如K3,K3n3時稱超立方體網(wǎng)絡(luò)。時稱超立方體網(wǎng)絡(luò)。 單級立方體網(wǎng)絡(luò)的最大距離為單級立方體網(wǎng)絡(luò)的

28、最大距離為n n。 2.PM2I2.PM2I單級網(wǎng)絡(luò)單級網(wǎng)絡(luò) PM2IPM2I單級網(wǎng)絡(luò)是加減單級網(wǎng)絡(luò)是加減2 2i i單級網(wǎng)絡(luò)的簡稱。單級網(wǎng)絡(luò)的簡稱。能實現(xiàn)與能實現(xiàn)與j j號處理單元直接相連的是號為號處理單元直接相連的是號為j j2 2i i的的處理單元，即：處理單元，即： PM2PM2+i+i(j)=j+2(j)=j+2i i mod N mod NPM2PM2-i-i(j)=j-2(j)=j-2i i mod N mod N其中其中0 i n-10 i n-1， 0 j N-1 0 j N-1 n=logn=log2 2N ,NN ,N是結(jié)點數(shù)。它共有是結(jié)點數(shù)。它共有2n2n個互連函數(shù)。個

29、互連函數(shù)。PM2IPM2I網(wǎng)絡(luò)的最大距離為網(wǎng)絡(luò)的最大距離為 n/2 n/2 。由于由于PM2PM2+(n-1)+(n-1)= = PM2 PM2-(n-1),-(n-1),所以所以PM2IPM2I互連網(wǎng)絡(luò)有互連網(wǎng)絡(luò)有2n-12n-1種互連函數(shù)種互連函數(shù)是不同的。對于是不同的。對于N=8N=8的三維的三維PM2IPM2I互連網(wǎng)絡(luò)的互連互連網(wǎng)絡(luò)的互連函數(shù)，有函數(shù)，有PM2PM2+0+0、PM2PM2-0-0、PM2PM2+1+1、PM2PM2-1-1、PM2PM22 2等等5 5個不同的互連函數(shù)。部分互連函數(shù)分別為：個不同的互連函數(shù)。部分互連函數(shù)分別為： PM2PM2+0+0：(0 1 2 3 4

30、 5 6 7)(0 1 2 3 4 5 6 7) PM2 PM2+1+1：（：（0 2 4 60 2 4 6） （1 3 5 71 3 5 7） PM2PM22 2 ：（：（0 40 4）（）（1 51 5）（）（2 62 6）（）（3 73 7）0 01 12 23 34 45 56 67 7PM2PM2+0+0 PM2PM2+1+1 PM2PM22 20 01 12 23 34 45 56 67 70 01 12 23 34 45 56 67 7PM2IPM2I互連網(wǎng)絡(luò)的部分連接圖互連網(wǎng)絡(luò)的部分連接圖3.3.混洗交換單級網(wǎng)絡(luò)混洗交換單級網(wǎng)絡(luò) 混洗交換單級網(wǎng)絡(luò)（混洗交換單級網(wǎng)絡(luò)（Shuffl

31、e-ExchangeShuffle-Exchange） 包含兩個互連函數(shù)，一個是全混（包含兩個互連函數(shù)，一個是全混（PerfectShufflePerfectShuffle）, ,另一個是交換（另一個是交換（ExchangeExchange）。）。 這種互連網(wǎng)絡(luò)由全混洗和交換兩種互連函數(shù)組成：這種互連網(wǎng)絡(luò)由全混洗和交換兩種互連函數(shù)組成： 全混全混Shuffle(PShuffle(Pn-1n-1P Pn-2n-2.P.P1 1P P0 0)=(P)=(Pn-2n-2.P.P0 0P Pn-1n-1) ) 式中，式中， n=logn=log2 2N N。相當于將處理單元的進制地址。相當于將處理單元

32、的進制地址位中的最左位移到最右位的循環(huán)移位。由于全混洗互位中的最左位移到最右位的循環(huán)移位。由于全混洗互連網(wǎng)絡(luò)不能實現(xiàn)全連網(wǎng)絡(luò)不能實現(xiàn)全0 0和全和全1 1單元與其他單元的連接，因單元與其他單元的連接，因此引入交換網(wǎng)絡(luò)中的此引入交換網(wǎng)絡(luò)中的CubeCube0 0函數(shù)，兩函數(shù)復(fù)合后為：函數(shù)，兩函數(shù)復(fù)合后為： ExchangeShuffle(PExchangeShuffle(Pn-1n-1P Pn-2n-2.P.P1 1P P0 0)=)= (P (Pn-2n-2.P.P0 0PPn-1n-1) )01234567N=8N=8時全混交換互連網(wǎng)絡(luò)連接圖時全混交換互連網(wǎng)絡(luò)連接圖 在混洗交換網(wǎng)絡(luò)中，最遠的

33、兩個在混洗交換網(wǎng)絡(luò)中，最遠的兩個入、出端號是全入、出端號是全“0”0”和全和全“1”1”，它，它們的連接需要們的連接需要n n次交換和次交換和n-1n-1次混洗，次混洗，所以最大距離為所以最大距離為2n-12n-1。6.3.3 6.3.3 多級互連網(wǎng)絡(luò)多級互連網(wǎng)絡(luò) 將前面三種單級互連網(wǎng)絡(luò)重復(fù)連接，就形成將前面三種單級互連網(wǎng)絡(luò)重復(fù)連接，就形成了最基本的多級互連網(wǎng)絡(luò)。即多級立方體互連網(wǎng)了最基本的多級互連網(wǎng)絡(luò)。即多級立方體互連網(wǎng)絡(luò)、多級混洗交換網(wǎng)絡(luò)和多級絡(luò)、多級混洗交換網(wǎng)絡(luò)和多級PM2IPM2I網(wǎng)絡(luò)。網(wǎng)絡(luò)。 決定多級互連網(wǎng)絡(luò)的特性的主要因素有以下決定多級互連網(wǎng)絡(luò)的特性的主要因素有以下三個方面：三個方

34、面：交換開關(guān)、拓撲結(jié)構(gòu)和控制方式交換開關(guān)、拓撲結(jié)構(gòu)和控制方式。 交換開關(guān)是具有兩個輸入端和兩個輸出端的交換開關(guān)是具有兩個輸入端和兩個輸出端的交換單元。交換單元。交換開關(guān)有直連、交換、上播、下播交換開關(guān)有直連、交換、上播、下播四種功能四種功能；控制方式則有；控制方式則有級控制、單元控制、部級控制、單元控制、部分級控三種方式。分級控三種方式。（1 1）直連直連ii入入連連i i出出，j j入入連連j j出出；（2 2）交換交換ii入入連連j j出出，j j入入連連i i出出；（3 3）上播上播ii入入連連i i出出和和j j出出，j j入入懸空；懸空；（4 4）下播下播jj入入連連i i出出和和j

35、 j出出，i i入入懸空。懸空。級控制級控制同一級的所有開關(guān)只用一個控制信號同一級的所有開關(guān)只用一個控制信號 控制，同時只能處于同一種狀態(tài)；控制，同時只能處于同一種狀態(tài)；單元控制單元控制每一個開關(guān)都有自己獨立的控制信每一個開關(guān)都有自己獨立的控制信 號控制，可各自處于不同的狀態(tài)；號控制，可各自處于不同的狀態(tài)；部分級控制部分級控制第第i i級的所有開關(guān)分別用級的所有開關(guān)分別用i+1i+1個信個信 號控制，號控制，0 i n-10 i n-1，n n為級數(shù)。為級數(shù)。1.1.多級立方體網(wǎng)絡(luò)多級立方體網(wǎng)絡(luò) 通常是采用交換互連單級網(wǎng)絡(luò)串接起來構(gòu)成通常是采用交換互連單級網(wǎng)絡(luò)串接起來構(gòu)成的。的。采用三種不同的

36、控制方式，可以構(gòu)成三種不采用三種不同的控制方式，可以構(gòu)成三種不同的互連網(wǎng)絡(luò)。同的互連網(wǎng)絡(luò)。采用級控制可以構(gòu)成采用級控制可以構(gòu)成STARANSTARAN交換網(wǎng)。交換網(wǎng)。采用部分級控制，可以構(gòu)成采用部分級控制，可以構(gòu)成STARANSTARAN移數(shù)網(wǎng)。移數(shù)網(wǎng)。采用單元控制可以構(gòu)成間接二進制采用單元控制可以構(gòu)成間接二進制n n方體網(wǎng)。方體網(wǎng)。 STARANSTARAN多級互連網(wǎng)絡(luò)就是多級互連網(wǎng)絡(luò)就是CubeCube0 0,Cube,Cube1 1,Cube,Cube2 2三種互連函數(shù)的三個單級立方體網(wǎng)串接起來的。三種互連函數(shù)的三個單級立方體網(wǎng)串接起來的。在采用不同的級控制信號時，可以實現(xiàn)任一輸入在采用

37、不同的級控制信號時，可以實現(xiàn)任一輸入端到任一輸出端的直接連接。端到任一輸出端的直接連接。第第i i級（級（0 i 0 i n-1n-1）交換單元處于交換狀態(tài)時，實現(xiàn)的是互）交換單元處于交換狀態(tài)時，實現(xiàn)的是互連函數(shù)，且都采用二功能交換單元。連函數(shù)，且都采用二功能交換單元。 A AB BC CD DE EF FG GH HI IJ JK KL L0 01 12 23 34 45 56 67 70 01 12 23 34 45 56 67 7k = 0k = 0k = 1k = 1k = 2k = 2N=8N=8多級立方體互連網(wǎng)絡(luò)多級立方體互連網(wǎng)絡(luò)開關(guān)組合控制：開關(guān)組合控制： 級控制、部分級控制級控

38、制、部分級控制-STARANSTARAN網(wǎng)絡(luò)網(wǎng)絡(luò)( (交換、交換、移數(shù)功能移數(shù)功能) )； 單元控制單元控制-間接二進制間接二進制n n方體網(wǎng)絡(luò)方體網(wǎng)絡(luò)( (更復(fù)雜更復(fù)雜的功能的功能) )。（1 1）交換功能）交換功能 開關(guān)組合控制方式：開關(guān)組合控制方式：級控制。級控制。級控制信號（級控制信號（k k2 2k k1 1k k0 0）000000001001010010011011100100101101110110111111入入 端端0 00 01 12 23 34 45 56 67 71 11 10 03 32 25 54 47 76 62 22 23 30 01 16 67 74 45

39、53 33 32 21 10 07 76 65 54 44 44 45 56 67 70 01 12 23 35 55 54 47 76 61 10 03 32 26 66 67 74 45 52 23 30 01 17 77 76 65 54 43 32 21 10 0功功能能i iCubeCube0 0CubeCube1 1CubeCube0 0+ +CubeCube1 1CubeCube2 2CubeCube0 0+ +CubeCube2 2CubeCube1 1+ +CubeCube2 2CubeCube0 0+ +CubeCube1 1+ +CubeCube2 2分組交換功能：分組交

40、換功能：組間次序不變，組內(nèi)元素鏡像。組間次序不變，組內(nèi)元素鏡像。 CubeCube0 0-4 4組組2 2元交換；元交換；CubeCube1 1-2 2組組4 4元交換元交換+4+4組組2 2元交換；元交換； CubeCube2 2-1 1組組8 8元交換元交換+2+2組組4 4元交換。元交換。（2 2）移位功能）移位功能 開關(guān)組合控制方式：開關(guān)組合控制方式：部分級控制部分級控制( (第第i i級有級有i+1i+1種控種控制信號制信號) )2 2級級K,LK,L0 00 01 10 00 00 00 0J J0 01 11 10 00 00 00 0I I1 11 11 10 00 00 00

41、 01 1級級F,HF,H0 01 10 00 01 10 00 0E,GE,G1 11 10 01 11 10 00 00 0級級A,B,C,DA,B,C,D1 10 00 01 10 01 10 0功功 能能移移1 1Mod 8Mod 8移移2 2Mod 8Mod 8移移4 4Mod 8Mod 8移移1 1Mod 4Mod 4移移2 2Mod 4Mod 4移移1 1Mod 2Mod 2不移不移衡等衡等 ModMod的作用：的作用：不同不同ModMod可用于不同的分組操作。可用于不同的分組操作。（3 3）應(yīng)用）應(yīng)用 交換功能很適合于雙向互連等要求的實現(xiàn)；交換功能很適合于雙向互連等要求的實現(xiàn)；

42、 移數(shù)功能很適合于累加求和等要求的實現(xiàn)。移數(shù)功能很適合于累加求和等要求的實現(xiàn)。（4 4）帶寬問題）帶寬問題 STARANSTARAN可同時多對結(jié)點連接，尚不能同時可同時多對結(jié)點連接，尚不能同時任意組合。任意組合。（5 5）例題）例題 例例1 1：1616個個PEPE采用采用STARANSTARAN網(wǎng)絡(luò)互連時，實現(xiàn)相網(wǎng)絡(luò)互連時，實現(xiàn)相當于當于4 4組組4 4元交換，然后元交換，然后2 2組組8 8元交換，再元交換，再1 1組組1616元元交換功能。寫出互連函數(shù)一般式、各級交換開關(guān)交換功能。寫出互連函數(shù)一般式、各級交換開關(guān)狀態(tài)。狀態(tài)。答：答：因需實現(xiàn)交換功能，故選擇因需實現(xiàn)交換功能，故選擇STAR

43、ANSTARAN的交換功的交換功能能( (級控制方式）。級控制方式）。 4 4組組4 4元交換元交換 CubeCube0 0+Cube+Cube1 1 2 2組組8 8元交換元交換 CubeCube0 0+Cube+Cube1 1+Cube+Cube2 2 1 1組組1616元交換元交換 CubeCube0 0+Cube+Cube1 1+Cube+Cube2 2+Cube+Cube3 3 相加相加 CubeCube0 0+Cube+Cube1 1 +Cube+Cube3 3 各級開關(guān)狀態(tài)：各級開關(guān)狀態(tài)：k k3 3k k2 2k k1 1k k0 0=(1011)=(1011) 互連函數(shù)：互連

44、函數(shù)：f(bf(b3 3b b2 2b b1 1b b0 0)=(b)=(b3 3b b2 2b b1 1b b0 0) )例例2 2：編號編號0F0F的的PEPE間，要實現(xiàn)下列通信配對：間，要實現(xiàn)下列通信配對：(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A)B),(0,A)。請畫出互連網(wǎng)絡(luò)結(jié)構(gòu)圖，寫出控制。請畫出互連網(wǎng)絡(luò)結(jié)構(gòu)圖，寫出控制方式及各開關(guān)狀態(tài)。方式及各開關(guān)狀態(tài)。答：答：因需實現(xiàn)雙向交換功能，選擇因需實現(xiàn)雙向交換功能，選擇STARANSTARAN網(wǎng)絡(luò)網(wǎng)絡(luò)的交換功

45、能的交換功能( (級控制方式級控制方式) )可滿足要求?？蓾M足要求。 網(wǎng)絡(luò)拓撲結(jié)構(gòu)：網(wǎng)絡(luò)拓撲結(jié)構(gòu)： 因共有因共有1616個結(jié)點，編碼需要個結(jié)點，編碼需要4 4位，所以開關(guān)共位，所以開關(guān)共4 4級。級。 0 0級級開關(guān)開關(guān)+(1)(1)，f(bf(b3 3b b2 2b b1 1b b0 0)=b)=b3 3b b2 2b b0 0b b1 1 1 1級級-開關(guān)開關(guān)+(2)(2)，f(bf(b3 3b b2 2b b0 0b b1 1)=b)=b3 3b b1 1b b0 0b b2 2 2 2級級-開關(guān)開關(guān)+， f(bf(b3 3b b1 1b b0 0b b2 2)=b)=b2 2b b1

46、1b b0 0b b3 3 3 3級級-開關(guān)開關(guān)+ +逆逆ShuffleShuffle，f(bf(b2 2b b1 1b b0 0b b3 3)=b)=b3 3b b2 2b b1 1b b0 00123456789ABCDEF級 k0 k1 k2 k30123456789ABCDEF配對要求：配對要求：(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A)(0,A) 開關(guān)控制：開關(guān)控制：因因77的結(jié)點與的結(jié)點與7 7的結(jié)點配對，故的結(jié)點配對，故需需1 1組組1616元交

47、換元交換；因因0303的結(jié)點與的結(jié)點與8B8B的結(jié)點配對的結(jié)點配對, ,故需故需2 2組組8 8元交換元交換；因因0101的結(jié)點與的結(jié)點與ABAB的結(jié)點配對的結(jié)點配對, ,故需故需4 4組組4 4元交換元交換；因因0 0結(jié)點與結(jié)點與A A結(jié)點配對，故需結(jié)點配對，故需8 8組組2 2元交換元交換。 相加相加 CubeCube1 1+ Cube+ Cube3 3 1 1組組1616元交換元交換 CubeCube0 0+Cube+Cube1 1+Cube+Cube2 2+Cube+Cube3 3 2 2組組8 8元交換元交換 CubeCube0 0+Cube+Cube1 1+Cube+Cube2 2

48、 4 4組組4 4元交換元交換 CubeCube0 0+Cube+Cube1 1 8 8組組2 2元交換元交換 CubeCube0 0 各級開關(guān)狀態(tài)：各級開關(guān)狀態(tài)：k k3 3k k2 2k k1 1k k0 0=(1010)=(1010)2.2.多級混洗交換網(wǎng)絡(luò)多級混洗交換網(wǎng)絡(luò)（網(wǎng)絡(luò)網(wǎng)絡(luò),即即OmegaOmega網(wǎng)絡(luò)網(wǎng)絡(luò)）ABCDEFGHIJKL012345672級級012345671級級0級級交換開關(guān)：交換開關(guān)：四功能；四功能；拓撲結(jié)構(gòu)：拓撲結(jié)構(gòu)：多級多級ShuffleShuffle；互連函數(shù)：互連函數(shù)：2 2級級-f(b-f(b2 2b b1 1b b0 0)=b)=b1 1b b0 0

49、b b2 2 1 1級級-f(b-f(b1 1b b0 0b b2 2)=b)=b0 0b b2 2b b1 1 0 0級級-f(b-f(b0 0b b2 2b b1 1)=b)=b2 2b b1 1b b0 0 開關(guān)組合控制：開關(guān)組合控制： 級控制、開關(guān)二功能級控制、開關(guān)二功能-STARANSTARAN交換網(wǎng)絡(luò)的逆網(wǎng)絡(luò)；交換網(wǎng)絡(luò)的逆網(wǎng)絡(luò)； 部分級控制、開關(guān)二功能部分級控制、開關(guān)二功能STARANSTARAN移數(shù)網(wǎng)絡(luò)的逆網(wǎng)絡(luò)；移數(shù)網(wǎng)絡(luò)的逆網(wǎng)絡(luò)； 單元控制、開關(guān)二、四功能單元控制、開關(guān)二、四功能-更強大的功能。更強大的功能。3.3.多級多級PM2IPM2I網(wǎng)絡(luò)網(wǎng)絡(luò) N=8N=8的多級的多級PM2

50、IPM2I網(wǎng)絡(luò)的結(jié)構(gòu)網(wǎng)絡(luò)的結(jié)構(gòu)如如174174頁圖頁圖6.166.16所示。它包含所示。它包含n n級單元間連接，每一級都是把前級單元間連接，每一級都是把前后兩列各后兩列各N=2N=2n n個單元按個單元按PM2IPM2I拓撲相互連接起來。拓撲相互連接起來。從第從第i i級（級（0in-10in-1）來說，每一個單元）來說，每一個單元j j （0iN-10iN-1）都有）都有3 3根連接線分別通往出單元根連接線分別通往出單元j j、j+2j+2i i mod Nmod N和和j-2j-2i i mod Nmod N，在圖中，它們分別用，在圖中，它們分別用點線、實線和虛線表示。點線、實線和虛線表

51、示。 采用單元控制增強對各級單元控制的靈活采用單元控制增強對各級單元控制的靈活性，讓每一單元都有自己獨立的控制信號性，讓每一單元都有自己獨立的控制信號H H、D D、U U（平控（平控H H、下控、下控D D、上控、上控U U）。此種多級。此種多級PM2IPM2I網(wǎng)絡(luò)網(wǎng)絡(luò)稱為強化數(shù)據(jù)變換網(wǎng)絡(luò)稱為強化數(shù)據(jù)變換網(wǎng)絡(luò)AMDAMD（Augmented Data Augmented Data ManipulatorManipulator），但是控制線多，成本較高。），但是控制線多，成本較高。 ADM ADM的拓撲結(jié)構(gòu)和控制方式使它可以完全模的拓撲結(jié)構(gòu)和控制方式使它可以完全模仿仿omegaomega網(wǎng)絡(luò)的

52、四功能交換單元。利用數(shù)據(jù)變換網(wǎng)絡(luò)的四功能交換單元。利用數(shù)據(jù)變換網(wǎng)絡(luò)可以實現(xiàn)各種靈活的移數(shù)、重復(fù)、間隔、展網(wǎng)絡(luò)可以實現(xiàn)各種靈活的移數(shù)、重復(fù)、間隔、展開等變換函數(shù)。開等變換函數(shù)。 多級網(wǎng)絡(luò)比較多級網(wǎng)絡(luò)比較靈活性靈活性( (低低高高) )：STARANSTARAN、間接二進制、間接二進制n n方體、方體、 Omega()Omega()、ADM(ADM(混洗四功能混洗四功能) )成本成本( (低低高高) )：同上同上用途：用途： STARANSTARAN、Omega PEMOmega PEM 間接二進制間接二進制n n方體方體 PEPEPEPE功能：功能：只能實現(xiàn)同時只能實現(xiàn)同時部分多對多部分多對多功

53、能功能。4.4.全排列網(wǎng)絡(luò)全排列網(wǎng)絡(luò)定義：定義：所有入端、出端的連接均不發(fā)生沖突的所有入端、出端的連接均不發(fā)生沖突的網(wǎng)絡(luò)，又稱非阻塞型網(wǎng)絡(luò)，即：網(wǎng)絡(luò)，又稱非阻塞型網(wǎng)絡(luò)，即：N N入入NN出有出有N N！種排列。種排列。常規(guī)多級網(wǎng)絡(luò)常規(guī)多級網(wǎng)絡(luò)( (如如STARANSTARAN、等等) )屬于阻塞型網(wǎng)屬于阻塞型網(wǎng)絡(luò)。絡(luò)。證明：證明：對對n=log2Nn=log2N級網(wǎng)絡(luò)，開關(guān)數(shù)級網(wǎng)絡(luò)，開關(guān)數(shù)=N/2=N/2n n。排列數(shù)排列數(shù)N NN NN N/ /2 2N Nl lo og gN N) )l lo og g( (N N/ /2 2N NN N! !N NN N2 22 2N N/ /2 22

54、22 2全排列網(wǎng)絡(luò)實現(xiàn)：全排列網(wǎng)絡(luò)實現(xiàn)：思想：思想：N!N!N NN/2N/2N NN/2N/2N NN N。方法：方法：a.a.原有多級網(wǎng)絡(luò)通過鎖存器運行兩次即原有多級網(wǎng)絡(luò)通過鎖存器運行兩次即 可；可； b.b.兩個兩個log2Nlog2N網(wǎng)絡(luò)背靠背串聯(lián)。網(wǎng)絡(luò)背靠背串聯(lián)。 用多級網(wǎng)絡(luò)也可以實現(xiàn)全排列網(wǎng)絡(luò)。用多級網(wǎng)絡(luò)也可以實現(xiàn)全排列網(wǎng)絡(luò)。將將loglog2 2N N級的級的N N個入端和個入端和N N個出端的互連網(wǎng)絡(luò)和它的個出端的互連網(wǎng)絡(luò)和它的逆網(wǎng)絡(luò)連在一起，省去中間完全重復(fù)的一級，就逆網(wǎng)絡(luò)連在一起，省去中間完全重復(fù)的一級，就可以得到總級數(shù)為可以得到總級數(shù)為2log2log2 2N-1N-1級

55、的全排列網(wǎng)絡(luò)。級的全排列網(wǎng)絡(luò)。175175頁圖頁圖6.176.17就是以三維立方體多級網(wǎng)絡(luò)和它的就是以三維立方體多級網(wǎng)絡(luò)和它的逆網(wǎng)絡(luò)連在一起，省去中間重復(fù)的一級后構(gòu)成的逆網(wǎng)絡(luò)連在一起，省去中間重復(fù)的一級后構(gòu)成的全排列網(wǎng)絡(luò)，稱此網(wǎng)絡(luò)為全排列網(wǎng)絡(luò)，稱此網(wǎng)絡(luò)為BenesBenes網(wǎng)絡(luò)網(wǎng)絡(luò)。6.4 6.4 并行存儲器的無沖突訪問并行存儲器的無沖突訪問 在陣列處理機中，存儲器頻寬要與多個處理單元在陣列處理機中，存儲器頻寬要與多個處理單元的速率匹配，如何保證在各種訪問模式下，存儲器都的速率匹配，如何保證在各種訪問模式下，存儲器都能實現(xiàn)無沖突訪問？能實現(xiàn)無沖突訪問？ 為保證對存儲器的并行無沖突訪問，可采用的

56、方為保證對存儲器的并行無沖突訪問，可采用的方法有，法有，數(shù)據(jù)交叉存儲在數(shù)據(jù)交叉存儲在m m個存儲體中，并且使存儲體個存儲體中，并且使存儲體M M大于每次要訪問的全部向量元素大于每次要訪問的全部向量元素N N，且為質(zhì)數(shù)。，且為質(zhì)數(shù)。將數(shù)將數(shù)組按行或列變換成一維數(shù)組，形成一個一維線性地址組按行或列變換成一維數(shù)組，形成一個一維線性地址空間，地址用空間，地址用a a表示，然后，將地址表示，然后，將地址a a所對應(yīng)的元素存所對應(yīng)的元素存放在體號地址放在體號地址j=a mod mj=a mod m，體內(nèi)地址，體內(nèi)地址i= a/n i= a/n 的單元中，的單元中，就可以滿足無沖突訪問的要求。就可以滿足無沖

57、突訪問的要求。 無沖突訪問技術(shù)無沖突訪問技術(shù) a30 a20 a10 a00 a31 a21 a11 a01 a32 a22 a12 a02 a33 a23 a13 a03 3 2 1 0 體體 3 體體 6 體體 5 體體 4 體體 3 體體 3 體體 2 體體 2 體體 2 體體 0 體體 0 體體 0 體體 1 體體 1 體體內(nèi)內(nèi)地地址址 體體內(nèi)內(nèi)地地址址 體體內(nèi)內(nèi)地地址址 (b) 錯位存儲錯位存儲 訪存沖突及其避免方法訪存沖突及其避免方法 (c) 44 二維數(shù)組在二維數(shù)組在 7 體交叉存儲器中的存放體交叉存儲器中的存放 (a) 直接按行存儲直接按行存儲 體體 0 2 1 0 3 2 1

58、 0 a31 a22 a13 a00 a32 a23 a10 a01 a33 a20 a11 a02 a30 a21 a12 a03 a32 a13 a00 a22 a03 a21 a02 a33 a20 a01 - a23 a10 a30 - a11 a31 a12 - 一、訪問需求一、訪問需求并行存取向量中各分量信息；并行存取向量中各分量信息；對矩陣可按行、列、對角線等方法訪問對矩陣可按行、列、對角線等方法訪問( (步長不一致步長不一致) )。二、存在問題二、存在問題存儲器帶寬限制存儲器帶寬限制存儲器帶寬達不到向量帶寬；存儲器帶寬達不到向量帶寬；訪存方式訪存方式( (步長步長) )不同，產(chǎn)

59、生訪存沖突。不同，產(chǎn)生訪存沖突。三、解決方法三、解決方法1 1、采用多體交叉存儲器、采用多體交叉存儲器 使存儲體數(shù)超過使存儲體數(shù)超過PEPE數(shù)，保證數(shù)，保證PEPE所需要的帶寬。所需要的帶寬。2 2、對向量分組操作、對向量分組操作 解決解決MEMMEM帶寬小于向量長度問題，提高處理效率。帶寬小于向量長度問題，提高處理效率。3 3、選擇適當?shù)拇鎯w數(shù)、選擇適當?shù)拇鎯w數(shù)m m 使存儲體數(shù)使存儲體數(shù)mPEmPE數(shù)，達到無沖突訪問數(shù)，達到無沖突訪問一維向量：一維向量： 順序存放，防止步長與順序存放，防止步長與m m成比例；成比例； m m取質(zhì)數(shù)取質(zhì)數(shù)( (與與PEPE數(shù)互質(zhì)數(shù)互質(zhì)) )，且與步長互質(zhì)

60、。，且與步長互質(zhì)。一維數(shù)組的并行遞歸算法一維數(shù)組的并行遞歸算法: :并行存儲體數(shù)不能再取并行存儲體數(shù)不能再取2 2的整數(shù)，而應(yīng)該取成質(zhì)數(shù)，當?shù)恼麛?shù)，而應(yīng)該取成質(zhì)數(shù)，當變址跳距與分體數(shù)互質(zhì)時，就可以進行無沖突訪問。變址跳距與分體數(shù)互質(zhì)時，就可以進行無沖突訪問。多維向量：多維向量： 錯位存放，滿足行、列、對角線等訪問要求；錯位存放，滿足行、列、對角線等訪問要求；對矩陣而言對矩陣而言(m(m大于大于PEPE數(shù)時數(shù)時)-)-設(shè)設(shè)m=2m=22P2P+1+1，1=21=2P P，同一列不同行錯開距離，同一列不同行錯開距離 2=12=1， 同一行不同列錯開距離同一行不同列錯開距離對對AabAab，體號：體