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

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

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

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

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

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

7、存儲(chǔ)器由系統(tǒng)存儲(chǔ)器由K K個(gè)存儲(chǔ)體集中組成，并經(jīng)個(gè)存儲(chǔ)體集中組成，并經(jīng)ICNICN為全部為全部N N個(gè)處理單元所共享。個(gè)處理單元所共享。 為使各處理單元對(duì)長(zhǎng)度為為使各處理單元對(duì)長(zhǎng)度為N N的向量中各個(gè)元的向量中各個(gè)元素都能同時(shí)并行處理，存儲(chǔ)體體數(shù)素都能同時(shí)并行處理，存儲(chǔ)體體數(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具有集中式共享存儲(chǔ)器的陣列處理機(jī)構(gòu)形具有集中式共享存儲(chǔ)器的陣列處理機(jī)構(gòu)形

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

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

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

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

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

13、個(gè)閉合螺線。 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步。步。這種陣列中，任意兩這種陣列中，任意兩個(gè)單元之間的最短距離不超過個(gè)單元之間的最短距離不超過 步。步。 例如：例如：從從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 陣列處理機(jī)的并行算法舉例陣列處理機(jī)的并行算法舉例1 1、矩陣加、矩陣加 把把C=A+BC=A+B中的屬于同一位置向量元素放在同一局部中的屬于同一位置向量元素放在同一局部存儲(chǔ)器中。存儲(chǔ)器中。兩個(gè)兩個(gè)8 8 8 8的矩陣的矩陣A A、

19、B B相加，所得結(jié)果相加，所得結(jié)果C C也也是是8 8 8 8矩陣，矩陣相加的存儲(chǔ)器分配如下圖所示矩陣，矩陣相加的存儲(chǔ)器分配如下圖所示(“(“全并行全并行”的工作特點(diǎn)，速度提高，但存儲(chǔ)單元分配的工作特點(diǎn)，速度提高，但存儲(chǔ)單元分配算法的設(shè)計(jì)比較麻煩算法的設(shè)計(jì)比較麻煩) )。 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矩陣相加的存儲(chǔ)器分配舉例矩陣相加的存

20、儲(chǔ)器分配舉例2 2、矩陣乘、矩陣乘 把把C=AC=A* *B B的各向量按列存放在一個(gè)局部存儲(chǔ)器中。的各向量按列存放在一個(gè)局部存儲(chǔ)器中。 設(shè)設(shè)A A、B B和和C C為為3 3個(gè)個(gè)8 8 8 8的二維矩陣，給定的二維矩陣，給定A A和和B B，計(jì)，計(jì)算算C=AC=A* *B B得得6464個(gè)分量可用公式：個(gè)分量可用公式： 其中其中0 i 70 i 7且且 0 j 70 j 7。 在在SISDSISD計(jì)算機(jī)上求解，用計(jì)算機(jī)上求解，用FORTRANFORTRAN語言編寫程序?yàn)椋赫Z言編寫程序?yàn)椋?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次相乘、加得時(shí)間，且每次還要包次相乘、加得時(shí)間，且每次還要包括執(zhí)行循環(huán)控制判別等其它操作所需得時(shí)間。括執(zhí)行循環(huán)控制判別等其它操作所需得時(shí)間。 如果在如果在SIMDSIMD陣列機(jī)上運(yùn)算，可用陣列機(jī)上運(yùn)算，可用8

22、8個(gè)處理單個(gè)處理單元并行計(jì)算矩陣元并行計(jì)算矩陣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語言編寫的程序?yàn)椋赫Z言編寫的程序?yàn)椋?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各部分同時(shí)在各部分同時(shí)在PEPE0 0PEPE7 7上運(yùn)算，這上運(yùn)算，這樣只需樣只需K K、J J二重循環(huán)，速度可提高至二重循環(huán)，速度可提高至8 8倍，即倍，即只需只需6464次乘、加的時(shí)間。次乘、加的時(shí)間。（164164頁圖頁圖6.56.5） 每次控制部件執(zhí)行的每次控制部件執(zhí)行的PEPE指令表面上是標(biāo)量指令表面上是標(biāo)量指令，實(shí)際上已等效于向量指令，是指令，實(shí)際上已等效于向量指令，是8 8個(gè)個(gè)PEPE并并行地執(zhí)行同一條指令。每次播送時(shí)，利用陣列行地執(zhí)行同一條指令。每次播送時(shí)，利用陣列處理機(jī)的播送功能將處理單元處理機(jī)的播送功能將處理單元PEPEK K中累加寄存中累加寄

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

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

26、分別存放在8 8個(gè)個(gè)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時(shí)稱超立方體網(wǎng)絡(luò)。時(shí)稱超立方體網(wǎng)絡(luò)。 單級(jí)立方體網(wǎng)絡(luò)的最大距離為單級(jí)立方體網(wǎng)絡(luò)的

28、最大距離為n n。 2.PM2I2.PM2I單級(jí)網(wǎng)絡(luò)單級(jí)網(wǎng)絡(luò) PM2IPM2I單級(jí)網(wǎng)絡(luò)是加減單級(jí)網(wǎng)絡(luò)是加減2 2i i單級(jí)網(wǎng)絡(luò)的簡(jiǎn)稱。單級(jí)網(wǎng)絡(luò)的簡(jiǎn)稱。能實(shí)現(xiàn)與能實(shí)現(xiàn)與j j號(hào)處理單元直接相連的是號(hào)為號(hào)處理單元直接相連的是號(hào)為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é)點(diǎn)數(shù)。它共有是結(jié)點(diǎn)數(shù)。它共有2n2n個(gè)互連函數(shù)。個(gè)

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ù)是不同的。對(duì)于是不同的。對(duì)于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個(gè)不同的互連函數(shù)。部分互連函數(shù)分別為：個(gè)不同的互連函數(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.混洗交換單級(jí)網(wǎng)絡(luò)混洗交換單級(jí)網(wǎng)絡(luò) 混洗交換單級(jí)網(wǎng)絡(luò)（混洗交換單級(jí)網(wǎng)絡(luò)（Shuffl

31、e-ExchangeShuffle-Exchange） 包含兩個(gè)互連函數(shù)，一個(gè)是全混（包含兩個(gè)互連函數(shù)，一個(gè)是全混（PerfectShufflePerfectShuffle）, ,另一個(gè)是交換（另一個(gè)是交換（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。相當(dāng)于將處理單元的進(jìn)制地址。相當(dāng)于將處理單元

32、的進(jìn)制地址位中的最左位移到最右位的循環(huán)移位。由于全混洗互位中的最左位移到最右位的循環(huán)移位。由于全混洗互連網(wǎng)絡(luò)不能實(shí)現(xiàn)全連網(wǎng)絡(luò)不能實(shí)現(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時(shí)全混交換互連網(wǎng)絡(luò)連接圖時(shí)全混交換互連網(wǎng)絡(luò)連接圖 在混洗交換網(wǎng)絡(luò)中，最遠(yuǎn)的

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

34、面：交換開關(guān)、拓?fù)浣Y(jié)構(gòu)和控制方式交換開關(guān)、拓?fù)浣Y(jié)構(gòu)和控制方式。 交換開關(guān)是具有兩個(gè)輸入端和兩個(gè)輸出端的交換開關(guān)是具有兩個(gè)輸入端和兩個(gè)輸出端的交換單元。交換單元。交換開關(guān)有直連、交換、上播、下播交換開關(guān)有直連、交換、上播、下播四種功能四種功能；控制方式則有；控制方式則有級(jí)控制、單元控制、部級(jí)控制、單元控制、部分級(jí)控三種方式。分級(jí)控三種方式。（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入入懸空。懸空。級(jí)控制級(jí)控制同一級(jí)的所有開關(guān)只用一個(gè)控制信號(hào)同一級(jí)的所有開關(guān)只用一個(gè)控制信號(hào) 控制，同時(shí)只能處于同一種狀態(tài)；控制，同時(shí)只能處于同一種狀態(tài)；單元控制單元控制每一個(gè)開關(guān)都有自己獨(dú)立的控制信每一個(gè)開關(guān)都有自己獨(dú)立的控制信 號(hào)控制，可各自處于不同的狀態(tài)；號(hào)控制，可各自處于不同的狀態(tài)；部分級(jí)控制部分級(jí)控制第第i i級(jí)的所有開關(guān)分別用級(jí)的所有開關(guān)分別用i+1i+1個(gè)信個(gè)信 號(hào)控制，號(hào)控制，0 i n-10 i n-1，n n為級(jí)數(shù)。為級(jí)數(shù)。1.1.多級(jí)立方體網(wǎng)絡(luò)多級(jí)立方體網(wǎng)絡(luò) 通常是采用交換互連單級(jí)網(wǎng)絡(luò)串接起來構(gòu)成通常是采用交換互連單級(jí)網(wǎng)絡(luò)串接起來構(gòu)成的。的。采用三種不同的

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

37、不同的級(jí)控制信號(hào)時(shí)，可以實(shí)現(xiàn)任一輸入端到任一輸出端的直接連接。端到任一輸出端的直接連接。第第i i級(jí)（級(jí)（0 i 0 i n-1n-1）交換單元處于交換狀態(tài)時(shí)，實(shí)現(xiàn)的是互）交換單元處于交換狀態(tài)時(shí)，實(shí)現(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多級(jí)立方體互連網(wǎng)絡(luò)多級(jí)立方體互連網(wǎng)絡(luò)開關(guān)組合控制：開關(guān)組合控制： 級(jí)控制、部分級(jí)控制級(jí)控

38、制、部分級(jí)控制-STARANSTARAN網(wǎng)絡(luò)網(wǎng)絡(luò)( (交換、交換、移數(shù)功能移數(shù)功能) )； 單元控制單元控制-間接二進(jìn)制間接二進(jìn)制n n方體網(wǎng)絡(luò)方體網(wǎng)絡(luò)( (更復(fù)雜更復(fù)雜的功能的功能) )。（1 1）交換功能）交換功能 開關(guān)組合控制方式：開關(guān)組合控制方式：級(jí)控制。級(jí)控制。級(jí)控制信號(hào)（級(jí)控制信號(hào)（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)組合控制方式：部分級(jí)控制部分級(jí)控制( (第第i i級(jí)有級(jí)有i+1i+1種控種控制信號(hào)制信號(hào)) )2 2級(jí)級(jí)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級(jí)級(jí)F,HF,H0 01 10 00 01 10 00 0E,GE,G1 11 10 01 11 10 00 00 0級(jí)級(jí)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)用 交換功能很適合于雙向互連等要求的實(shí)現(xiàn)；交換功能很適合于雙向互連等要求的實(shí)現(xiàn)；

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

43、ANSTARAN的交換功的交換功能能( (級(jí)控制方式）。級(jí)控制方式）。 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 各級(jí)開關(guān)狀態(tài)：各級(jí)開關(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：編號(hào)編號(hào)0F0F的的PEPE間，要實(shí)現(xiàn)下列通信配對(duì)：間，要實(shí)現(xiàn)下列通信配對(duì)：(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)。請(qǐng)畫出互連網(wǎng)絡(luò)結(jié)構(gòu)圖，寫出控制。請(qǐng)畫出互連網(wǎng)絡(luò)結(jié)構(gòu)圖，寫出控制方式及各開關(guān)狀態(tài)。方式及各開關(guān)狀態(tài)。答：答：因需實(shí)現(xiàn)雙向交換功能，選擇因需實(shí)現(xiàn)雙向交換功能，選擇STARANSTARAN網(wǎng)絡(luò)網(wǎng)絡(luò)的交換功

45、能的交換功能( (級(jí)控制方式級(jí)控制方式) )可滿足要求。可滿足要求。 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)： 因共有因共有1616個(gè)結(jié)點(diǎn)，編碼需要個(gè)結(jié)點(diǎn)，編碼需要4 4位，所以開關(guān)共位，所以開關(guān)共4 4級(jí)。級(jí)。 0 0級(jí)級(jí)開關(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級(jí)級(jí)-開關(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級(jí)級(jí)-開關(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級(jí)級(jí)-開關(guān)開關(guān)+ +逆逆ShuffleShuffle，f(bf(b2 2b b1 1b b0 0b b3 3)=b)=b3 3b b2 2b b1 1b b0 00123456789ABCDEF級(jí) k0 k1 k2 k30123456789ABCDEF配對(duì)要求：配對(duì)要求：(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é)點(diǎn)與的結(jié)點(diǎn)與7 7的結(jié)點(diǎn)配對(duì)，故的結(jié)點(diǎn)配對(duì)，故需需1 1組組1616元交

47、換元交換；因因0303的結(jié)點(diǎn)與的結(jié)點(diǎn)與8B8B的結(jié)點(diǎn)配對(duì)的結(jié)點(diǎn)配對(duì), ,故需故需2 2組組8 8元交換元交換；因因0101的結(jié)點(diǎn)與的結(jié)點(diǎn)與ABAB的結(jié)點(diǎn)配對(duì)的結(jié)點(diǎn)配對(duì), ,故需故需4 4組組4 4元交換元交換；因因0 0結(jié)點(diǎn)與結(jié)點(diǎn)與A A結(jié)點(diǎn)配對(duì)，故需結(jié)點(diǎn)配對(duì)，故需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 各級(jí)開關(guān)狀態(tài)：各級(jí)開關(guān)狀態(tài)：k k3 3k k2 2k k1 1k k0 0=(1010)=(1010)2.2.多級(jí)混洗交換網(wǎng)絡(luò)多級(jí)混洗交換網(wǎng)絡(luò)（網(wǎng)絡(luò)網(wǎng)絡(luò),即即OmegaOmega網(wǎng)絡(luò)網(wǎng)絡(luò)）ABCDEFGHIJKL012345672級(jí)級(jí)012345671級(jí)級(jí)0級(jí)級(jí)交換開關(guān)：交換開關(guān)：四功能；四功能；拓?fù)浣Y(jié)構(gòu)：拓?fù)浣Y(jié)構(gòu)：多級(jí)多級(jí)ShuffleShuffle；互連函數(shù)：互連函數(shù)：2 2級(jí)級(jí)-f(b-f(b2 2b b1 1b b0 0)=b)=b1 1b b0 0

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

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

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

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

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ī)多級(jí)網(wǎng)絡(luò)常規(guī)多級(jí)網(wǎng)絡(luò)( (如如STARANSTARAN、等等) )屬于阻塞型網(wǎng)屬于阻塞型網(wǎng)絡(luò)。絡(luò)。證明：證明：對(duì)對(duì)n=log2Nn=log2N級(jí)網(wǎng)絡(luò)，開關(guān)數(shù)級(jí)網(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ò)實(shí)現(xiàn)：全排列網(wǎng)絡(luò)實(shí)現(xiàn)：思想：思想：N!N!N NN/2N/2N NN/2N/2N NN N。方法：方法：a.a.原有多級(jí)網(wǎng)絡(luò)通過鎖存器運(yùn)行兩次即原有多級(jí)網(wǎng)絡(luò)通過鎖存器運(yùn)行兩次即 可；可； b.b.兩個(gè)兩個(gè)log2Nlog2N網(wǎng)絡(luò)背靠背串聯(lián)。網(wǎng)絡(luò)背靠背串聯(lián)。 用多級(jí)網(wǎng)絡(luò)也可以實(shí)現(xiàn)全排列網(wǎng)絡(luò)。用多級(jí)網(wǎng)絡(luò)也可以實(shí)現(xiàn)全排列網(wǎng)絡(luò)。將將loglog2 2N N級(jí)的級(jí)的N N個(gè)入端和個(gè)入端和N N個(gè)出端的互連網(wǎng)絡(luò)和它的個(gè)出端的互連網(wǎng)絡(luò)和它的逆網(wǎng)絡(luò)連在一起，省去中間完全重復(fù)的一級(jí)，就逆網(wǎng)絡(luò)連在一起，省去中間完全重復(fù)的一級(jí)，就可以得到總級(jí)數(shù)為可以得到總級(jí)數(shù)為2log2log2 2N-1N-1級(jí)

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

56、方為保證對(duì)存儲(chǔ)器的并行無沖突訪問，可采用的方法有，法有，數(shù)據(jù)交叉存儲(chǔ)在數(shù)據(jù)交叉存儲(chǔ)在m m個(gè)存儲(chǔ)體中，并且使存儲(chǔ)體個(gè)存儲(chǔ)體中，并且使存儲(chǔ)體M M大于每次要訪問的全部向量元素大于每次要訪問的全部向量元素N N，且為質(zhì)數(shù)。，且為質(zhì)數(shù)。將數(shù)將數(shù)組按行或列變換成一維數(shù)組，形成一個(gè)一維線性地址組按行或列變換成一維數(shù)組，形成一個(gè)一維線性地址空間，地址用空間，地址用a a表示，然后，將地址表示，然后，將地址a a所對(duì)應(yīng)的元素存所對(duì)應(yīng)的元素存放在體號(hào)地址放在體號(hào)地址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) 錯(cuò)位存儲(chǔ)錯(cuò)位存儲(chǔ) 訪存沖突及其避免方法訪存沖突及其避免方法 (c) 44 二維數(shù)組在二維數(shù)組在 7 體交叉存儲(chǔ)器中的存放體交叉存儲(chǔ)器中的存放 (a) 直接按行存儲(chǔ)直接按行存儲(chǔ) 體體 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 - 一、訪問需求一、訪問需求并行存取向量中各分量信息；并行存取向量中各分量信息；對(duì)矩陣可按行、列、對(duì)角線等方法訪問對(duì)矩陣可按行、列、對(duì)角線等方法訪問( (步長(zhǎng)不一致步長(zhǎng)不一致) )。二、存在問題二、存在問題存儲(chǔ)器帶寬限制存儲(chǔ)器帶寬限制存儲(chǔ)器帶寬達(dá)不到向量帶寬；存儲(chǔ)器帶寬達(dá)不到向量帶寬；訪存方式訪存方式( (步長(zhǎng)步長(zhǎng)) )不同，產(chǎn)

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

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