計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)(ch-5)

第5章并行處理技術(shù)5.1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)中并行性的發(fā)展5.2SIMD并行處理機(jī)5.3SIMD計(jì)算機(jī)的互連網(wǎng)絡(luò)5.4網(wǎng)絡(luò)特性5.5靜態(tài)互接網(wǎng)絡(luò)5.6動(dòng)態(tài)互接網(wǎng)絡(luò)5.1.1并行性的基本概念1、并行性的定義指在數(shù)值計(jì)算、數(shù)據(jù)處理、信息處理或是人工智能等求解過程中可能存在某些可同時(shí)進(jìn)行運(yùn)算或操作的部分。開發(fā)并行性的目的是為了能進(jìn)行并行處理，以提高計(jì)算機(jī)系統(tǒng)求解問題的效率。并行性有二重含義，即同時(shí)性(simultaneity)和并發(fā)性(concurrency)。同時(shí)性是指多個(gè)事件在同一時(shí)刻發(fā)生；并發(fā)性是指多個(gè)事件在同一時(shí)間段內(nèi)發(fā)生。

5.1計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)中并行性的發(fā)展2、并行處理的概念是指一種相對(duì)于串行處理的信息處理方式，它著重開發(fā)計(jì)算過程中存在的并發(fā)事件。進(jìn)行并行處理時(shí)，每次處理的規(guī)模大小可能是不同的，這可用并行性顆粒度(granularity)來表示。粗粒度開發(fā)主要采用MIMD方式，開發(fā)功能并行性；細(xì)粒度開發(fā)主要采用SIMD方式，開發(fā)數(shù)據(jù)并行性。5.1.1并行性的基本概念

5.1.1并行性的基本概念3、并行性的等級(jí)

層次1作業(yè)級(jí)（程序）

層次2任務(wù)級(jí)（程序段或過程）

層次3子任務(wù)級(jí)（例行程序，子程序）

層次4循環(huán)和迭代

層次5語句和指令

粗5.1.2并行性技術(shù)的實(shí)現(xiàn)途徑1.時(shí)間重疊（timeinterleaving）引入時(shí)間因素，多個(gè)處理過程在時(shí)間上相互錯(cuò)開，輪流重疊地使用同一套硬件設(shè)備的各個(gè)部分，以加快硬件周轉(zhuǎn)而贏得速度。2.資源重復(fù)（resourcereplication）是指在并行性概念中引入空間因素，通過重復(fù)設(shè)置硬件資源來提高可靠性或性能。3.資源共享（resourcesharing）是指利用軟件的方法讓多個(gè)任務(wù)按一定的時(shí)間順序（分時(shí)）輪流地使用同一套資源，以提高其利用率，這樣相應(yīng)地也可以提高整個(gè)系統(tǒng)的性能。如流水線如超標(biāo)量處理機(jī)如多終端小型機(jī)5.1.3計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)中并行性的發(fā)展

標(biāo)量

順序

先行

I/E重疊

功能并行

多功能部件

流水線

隱式向量

顯式向量

存儲(chǔ)器-

寄存器-

存儲(chǔ)器型

寄存器型

SIMD

MIMD

相聯(lián)處理機(jī)

處理機(jī)陣列

多計(jì)算機(jī)

多處理機(jī)

多機(jī)系統(tǒng)多處理機(jī)：存儲(chǔ)器共享，緊耦合多計(jì)算機(jī)：消息傳遞，松耦合5.2SIMD并行處理機(jī)5.2.1SIMD并行處理機(jī)的基本結(jié)構(gòu)與特點(diǎn)按存儲(chǔ)器的組成方式不同分為兩類分布式存儲(chǔ)器結(jié)構(gòu)集中式共享存儲(chǔ)器結(jié)構(gòu)1.分布式存儲(chǔ)器結(jié)構(gòu)

LMN-1

LM0

主機(jī)

控制部件存儲(chǔ)器

（程序與數(shù)據(jù)）

標(biāo)量處理機(jī)

大容量存儲(chǔ)器

陣列控制

部件

互連網(wǎng)絡(luò)

PE0

LM1

PE1

PEN-1

標(biāo)量指令

向量指令

指令

廣播總線

網(wǎng)

絡(luò)

控

制

數(shù)

據(jù)

總

線

I/O用戶

···

2.集中式共享存儲(chǔ)器結(jié)構(gòu)SMK-1SM0主機(jī)控制部件存儲(chǔ)器（程序與數(shù)據(jù)）標(biāo)量處理機(jī)大容量存儲(chǔ)器陣列控制部件互連網(wǎng)絡(luò)PE0SM1PE1PEN-1標(biāo)量指令向量指令指令廣播總線網(wǎng)絡(luò)控制數(shù)據(jù)總線I/O用戶······3.SIMD并行處理機(jī)的主要特點(diǎn)(1)SIMD并行處理機(jī)利用的是資源重復(fù)，而不是時(shí)間重疊，利用并行性中的同時(shí)性，而不是并發(fā)性；(2)SIMD并行處理機(jī)是以某一類算法為背景的專用計(jì)算機(jī)；(3)SIMD并行處理機(jī)的研究必須與并行算法的研究密切結(jié)合，以使它的求解算法的適應(yīng)性更強(qiáng)一些，應(yīng)用面更廣一些；(4)從處理單元上看，由于各處理單元都是相同的，因而可將SIMD并行處理機(jī)看成是一個(gè)同構(gòu)型并行處理機(jī)。但從整體上看又是一個(gè)異構(gòu)的多處理機(jī)系統(tǒng)（主機(jī)、處理單元陣列、標(biāo)量處理機(jī)）5.2.2ILLIAC-IV的處理單元陣列結(jié)構(gòu)是世界上最早采用SIMD結(jié)構(gòu)的計(jì)算機(jī)，美國(guó)寶來公司和伊利諾依大學(xué)1965年開始研制，1972年正式生產(chǎn)。采用分布式存儲(chǔ)器結(jié)構(gòu)。陣列共由64個(gè)處理部件組成，排列成平面8×8陣列結(jié)構(gòu)，每一個(gè)PU都與其四個(gè)鄰近的PU相連，即按上、下、左、右方向可以與其它PU通信。PU在連接上采用了縱向連環(huán)，橫向閉合螺線，又稱閉合螺線陣列。在n×n個(gè)PU組成的陣列中，這種連接可以使任意兩個(gè)PU間的最短距離不超過（n-1）步。5.2.2ILLIAC-IV的處理單元陣列結(jié)構(gòu)

PU0

PU7

···

··

·

···

·

·

·

i-8

i-1

i

i+1

i+8

PU1PU8PU9PU15PU56PU57PU63·····

·

5.2.3陣列處理機(jī)的并行算法1.矩陣加并行算法設(shè)A和B是n×n階矩陣，A、B的和矩陣為C，它也是n×n階矩陣。矩陣加的算法為：A+B=C=(cij)n×ncij=aij+bij

αA（0，0）

α+1B（0，0）

α+2C（0，0）

A（0，1）

B（0，1）

C（0，1）

A（7，7）

B（7，7）

C（7，7）

LM0LM1LM63

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

···

1.矩陣加并行算法P≥n2TP=t加P＜n2

αA（0，0）

α+1B（0，0）

α+2C（0，0）

A（0，1）

B（0，1）

C（0，1）

A（7，7）

B（7，7）

C（7，7）

LM0LM1LM63

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

···

2.矩陣乘并行算法設(shè)A和B是n×n階矩陣，A、B的乘積矩陣為C，它也是n×n階矩陣。矩陣乘的傳統(tǒng)串行算法為：A×B=C=(cij)n×n串行運(yùn)行時(shí)間為T1=n3×(t乘+t加)設(shè)處理單元數(shù)P=m2，互連成m×m的二維雙向鏈路環(huán)網(wǎng)結(jié)構(gòu)，下面分兩種情況討論矩陣乘所需的總計(jì)算時(shí)間。(1)若處理單元的個(gè)數(shù)P＜n2

設(shè)n為m的整數(shù)倍。將A、B與C以適當(dāng)方式分為P塊Aij、Bij和Cij(0≤i,j≤m-1)，每塊為(n/m×n/m)子矩陣，將這些塊映像到m×m個(gè)邏輯處理陣列機(jī)上，每個(gè)處理機(jī)記為Pij，Pij存儲(chǔ)Aij，Bij，并計(jì)算Cij。例圖5.7。c[i,j]=0;for(i=0;i<n;i++)for(j=0;j<n;j++)for(k=0;k<n;k++)c[i,j]=c[i,j]+a[i,k]*b[k,j];(1)若處理單元的個(gè)數(shù)P＜n2

A(0，0)

A(0，1)

A(0，7)

A(0，56)

A(0，57)

A(0，63)

A(1，0)

A(1，1)

A(1，7)

A(1，56)

A(1，57)

A(1，63)

A(7，0)

A(7，1)

A(7，7)

A(7，56)

A(7，57)

A(7，63)

A(56，0)A(56，1)

A(56，7)

A(56，56)A(56，57)A(56，63)

A(57，0)A(57，1)A(57，7)

A(57，56)A(57，57)A(57，63)

A(63，0)A(63，1)A(63，7)

A(63，56)A(63，57)A(63，63)

64×64

A00LM0A07LM7

A70LM56

A77LM63

···

···

···

···

···

···

···

···

···

···

···

···

···

···

···

···

···

···

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

·

(1)若處理單元的個(gè)數(shù)P＜n2計(jì)算Cij時(shí)，需要所有子矩陣塊Aik、Bkj(0≤k≤m-1)，因此A的塊在處理機(jī)陣列每行作多對(duì)多廣播，而B的塊在處理機(jī)陣列每列作多對(duì)多廣播。當(dāng)Pij接收完Ai0，Ai1，…，Ai(m-1)；B0j，B1j，…，B(m-1)j后，執(zhí)行子矩陣乘法和加法運(yùn)算。計(jì)算時(shí)間用Pij計(jì)算Cij時(shí)，需對(duì)(n/m×n/m)階子矩陣中的每個(gè)元素cij進(jìn)行n次乘法和n次加法(cij=Σaikbkj)，故Pij的運(yùn)行時(shí)間為：n×n/m×n/m×(t乘+t加)=n3/m2×(t乘+t加)=n3/P×(t乘+t加)通信時(shí)間ts：發(fā)送消息的啟動(dòng)時(shí)間，tw：傳送每個(gè)浮點(diǎn)數(shù)時(shí)的通信時(shí)間，由于需要在m臺(tái)處理機(jī)組成的組中作二次多對(duì)多廣播，每次包含處理機(jī)陣列上所有行或列的m次并發(fā)廣播，發(fā)送消息的個(gè)數(shù)由n2/P個(gè)元素的子矩陣組成，所以整個(gè)通信時(shí)間為：2(mts+mn2/P×tw)=2(mts+n2/m×tw)整個(gè)并行運(yùn)行時(shí)間為：TP=n3/m2×(t乘+t加)+2(mts+n2/m×tw)c[i,j]=0;for(i=0;i<n/m;i++)for(j=0;j<n/m;j++)for(k=0;k<n;k++)c[i,j]=c[i,j]+a[i,k]*b[k,j];矩陣乘法C程序傳統(tǒng)串行處理時(shí)：cij=0;for(i=0;i<n;i++)for(j=0;j<n;j++)for(k=0;k<n;k++)cij=cij+aik*bkj;n*n*n次加法和乘法分塊并行后：cij=0;for(i=0;i<n/m;i++)for(j=0;j<n/m;j++)for(k=0;k<n;k++)cij=cij+aik*bkj;n*(n/m)*(n/m)次乘法和加法(2)若處理單元的個(gè)數(shù)P≥n2是前一種情況在m=n下的一個(gè)特例，將m=n代入前式得：①計(jì)算時(shí)間n(t乘+t加)②通信時(shí)間2(nts+ntw)=2n(ts+tw)③整個(gè)并行運(yùn)行時(shí)間為：TP=n(t乘+t加)+2n(ts+tw)3.累加和并行算法為了加快并行計(jì)算，常采用遞歸折疊方法。一般而言，在P個(gè)處理單元上實(shí)現(xiàn)P個(gè)元素累加，需要折疊次，并行相加

次并行處理所需的總的時(shí)間為：nt加+xt傳

第3步

A0+A1+A2+A3+A4+A5+A6+A7

第2步A0+A1+A2+A3A4+A5+A6+A7

第1步A0+A1

A2+A3

A4+A5A6+A7

PE值0A01A1

2A23A3

4A45A5

6A67A7

注意與向量方式的區(qū)別上次課內(nèi)容回顧向量流水處理機(jī)性能參數(shù)R∞、n1/2、nv并行性的基本概念并行性與并行處理同時(shí)性與并發(fā)性并行性顆粒度并行性技術(shù)的實(shí)現(xiàn)途徑時(shí)間重疊、資源重復(fù)、資源共享SIMD并行處理機(jī)分布式存儲(chǔ)器結(jié)構(gòu)集中式共享存儲(chǔ)器結(jié)構(gòu)處理單元陣列（PE）、標(biāo)量處理機(jī)、陣列控制部件、主機(jī)、互連網(wǎng)絡(luò)上次課內(nèi)容回顧并行性的基本概念并行性與并行處理同時(shí)性與并發(fā)性并行性顆粒度并行性技術(shù)的實(shí)現(xiàn)途徑時(shí)間重疊資源重復(fù)資源共享SIMD并行處理機(jī)分布式存儲(chǔ)器結(jié)構(gòu)集中式共享存儲(chǔ)器結(jié)構(gòu)組成：處理單元陣列（PE）、標(biāo)量處理機(jī)、陣列控制部件、主機(jī)、互連網(wǎng)絡(luò)ILLACⅣ、閉合螺線陣列陣列處理機(jī)并行算法矩陣加、矩陣乘、累加和5.3SIMD計(jì)算機(jī)的互連網(wǎng)絡(luò)5.3.1互連網(wǎng)絡(luò)的設(shè)計(jì)準(zhǔn)則1.通信工作方式同步和異步兩種同步方式由統(tǒng)一的時(shí)鐘加以同步；異步方式則不用統(tǒng)一的時(shí)鐘加以同步，各處理單元根據(jù)需要相互建立動(dòng)態(tài)連接。SIMD并行機(jī)一般都采用同步方式2.控制策略集中和分散兩種集中式控制由統(tǒng)一控制器對(duì)各互連開關(guān)的狀態(tài)加以控制，而分散式控制則由各個(gè)互連開關(guān)自身進(jìn)行管理。SIMD并行機(jī)一般都采用集中控制。5.3.1互連網(wǎng)絡(luò)的設(shè)計(jì)準(zhǔn)則3.交換方式線路交換和分組交換兩種。線路交換是在整個(gè)交換過程中，在源和目標(biāo)結(jié)點(diǎn)之間建立固定的物理通路，適用于成批數(shù)據(jù)傳送。分組交換則把要傳送的一個(gè)信息分成多個(gè)分組，分別送入互連網(wǎng)絡(luò)。這些分組可通過不同的路由到達(dá)目標(biāo)結(jié)點(diǎn)。因此，較適合于短數(shù)據(jù)報(bào)文的傳送。SIMD并行機(jī)因?yàn)樘幚韱卧g的連接比較緊密，一般采用線路交換。MIMD多機(jī)系統(tǒng)則往往采用分組交換方式。4.網(wǎng)絡(luò)拓?fù)渲富ミB網(wǎng)絡(luò)中各個(gè)結(jié)點(diǎn)間的連接關(guān)系，通常用圖來描述。靜態(tài)和動(dòng)態(tài)兩種。5.3.2互連函數(shù)的表示互連函數(shù)：描述各處理單元之間或處理單元與共享主存各模塊之間傳遞數(shù)據(jù)時(shí)，互連網(wǎng)絡(luò)的出端號(hào)和入端號(hào)的一一對(duì)應(yīng)關(guān)系。如果定義互連網(wǎng)絡(luò)的所有入端號(hào)分別為0、1、...、j、…、N-1，那么互連函數(shù)f(j)則表示的是入端號(hào)j連至出端號(hào)f(j)的函數(shù)對(duì)應(yīng)關(guān)系?；ミB函數(shù)的分析工具一般有二種：(1)入、出端連接圖。一般只在結(jié)點(diǎn)數(shù)比較少的情況下使用。(2)函數(shù)關(guān)系式。把所有入端j和出端f(j)都使用二進(jìn)制編碼，從二者的二進(jìn)制編碼上找出其對(duì)應(yīng)的函數(shù)規(guī)律，并用函數(shù)關(guān)系式來表示。5.3.3單級(jí)互連網(wǎng)絡(luò)1.立方體單級(jí)網(wǎng)絡(luò)（Cube）二元三維處理單元編號(hào)（z,y,x）1.立方體單級(jí)網(wǎng)絡(luò)（Cube）Cubei（Pn-1…Pi…P1P0）=Pn-1…Pi…P1P0n維立方體單級(jí)網(wǎng)絡(luò)，實(shí)現(xiàn)任意兩個(gè)PE之間的連接，最多需使用n次不同的互連函數(shù)，即：n維立方體單級(jí)網(wǎng)絡(luò)的最大距離為n。000

001

100

101

110

111

Cube0=zyx010011000

001

110

111

100

101

Cube1=zyx010011000

001

110

111

100

101

Cube2=zyx0100112.PM2I單級(jí)網(wǎng)絡(luò)是加減2i的簡(jiǎn)稱，Plus-Minus2i。PM2+i（j）=（j+2i）modNPM2-i（j）=（j-2i）modN式中，0≤j≤N-1，0≤i≤n-1，n=log2N，N為處理器的個(gè)數(shù)。因此，它共有2n個(gè)互連函數(shù)例如，對(duì)于N=8，各互連循環(huán)為：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）（1→5）（2→6）（3→7）8個(gè)處理單元的PM2I互連網(wǎng)絡(luò)的部分連接圖

0

1

2

3

4

5

6

7

PM2+0

0

1

2

3

4

5

6

7

PM2+1

0

1

2

3

4

5

6

7

PM2±2

2.PM2I單級(jí)網(wǎng)絡(luò)可以證明：PM2+（n-1）=PM2-（n-1），所以實(shí)際上，PM2I網(wǎng)絡(luò)只有2n-1種不同的互連函數(shù)。如何證明？ILLIAC-Ⅳ中的64個(gè)處理單元間的互連，實(shí)際上就是只采用了PM2I互連網(wǎng)絡(luò)中的PM2±0和PM2±3這四個(gè)互連函數(shù)。驗(yàn)證PM2I單級(jí)網(wǎng)絡(luò)的最大距離為，使用不同的PM2I函數(shù)。

0

1

2

3

4

5

6

7

PM2+0

0

1

2

3

4

5

6

7

PM2±2

分j+2n-1≤2n和j+2n-1>2n兩種情況證明1）若j+2n-1≤2n則:PM2+（n-1)(j)=(j+2n-1)mod2n=(j+2n-1)PM2-（n-1)(j)=(j-2n-1)mod2n=2n+(j-2n-1)=PM2+（n-1)(j)同理2）也成立。3.混洗交換互連網(wǎng)絡(luò)（Shuffle-Exchange）由全混洗和交換兩種互連函數(shù)組成。(1)全混洗Shuffle（Pn-1Pn-2···P1P0）=Pn-2···P1P0Pn-1

0

01

1

2

2

3

3

4

45

5

6

6

7

7

循環(huán)左移1位洗撲克牌？3.混洗交換互連網(wǎng)絡(luò)（Shuffle-Exchange）(2)交換由于單一的全混洗互連網(wǎng)絡(luò)不能實(shí)現(xiàn)二進(jìn)制編號(hào)為全“0”和全“1”的處理器與其它任何處理器的連接，所以又增加了Cube0交換互連函數(shù)。稱為混洗交換單級(jí)互連網(wǎng)絡(luò)，Shuffle+Cube0

。

0

1

2

3

4

5

67最遠(yuǎn)的兩個(gè)入、出端的連接，需要經(jīng)過n次交換和n-1次混洗，所以混洗交換網(wǎng)絡(luò)的最大距離為2n-1。上次課內(nèi)容回顧互連網(wǎng)絡(luò)的設(shè)計(jì)準(zhǔn)則通信工作方式同步、異步控制策略集中、分散交換方式線路交換、分組交換網(wǎng)絡(luò)拓?fù)潇o態(tài)、動(dòng)態(tài)單級(jí)互連網(wǎng)絡(luò)CubeiPM2IShuffle-ExchangeButterfly4.蝶形互連網(wǎng)絡(luò)（Butterfly）蝶形互連網(wǎng)絡(luò)的互連函數(shù)為：Butterfly（bn-1bn-2……b1b0）=b0bn-2……b1bn-1

00

1

1

2

2

3

3

4

4

5

5

6

6

7

7

蝶形否？5.4網(wǎng)絡(luò)特性與尋徑功能5.4.1結(jié)點(diǎn)度和網(wǎng)絡(luò)直徑與結(jié)點(diǎn)相連接的邊（鏈路或通道）數(shù)稱為結(jié)點(diǎn)度(nodedegree)。在單向通道的情況下，進(jìn)入結(jié)點(diǎn)的通道數(shù)叫做入度(indegree)，而從結(jié)點(diǎn)出來的通道數(shù)則稱為出度(outdegree)。結(jié)點(diǎn)度就是入度與出度之和。反映結(jié)點(diǎn)所需端口數(shù)。網(wǎng)絡(luò)直徑(networkdiameter)：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)之間最短路徑的最大值。路徑長(zhǎng)度用遍歷的鏈路數(shù)來度量。這是說明網(wǎng)絡(luò)通信性能的一個(gè)指標(biāo)。網(wǎng)絡(luò)對(duì)稱性(networksymmetry)：如果從網(wǎng)絡(luò)任意結(jié)點(diǎn)看上去拓?fù)浣Y(jié)構(gòu)都是相同的，則稱該網(wǎng)絡(luò)是對(duì)稱的，否則網(wǎng)絡(luò)是非對(duì)稱的。網(wǎng)絡(luò)的對(duì)稱性可提高可擴(kuò)展性和尋徑效率。5.4.2聚集帶寬和等分帶寬聚集帶寬(aggregatebandwidth)從一半節(jié)點(diǎn)到另一半結(jié)點(diǎn)每秒傳輸?shù)淖畲笪粩?shù)或字節(jié)數(shù)。例如：HPS是對(duì)稱式網(wǎng)絡(luò)，包含512個(gè)節(jié)點(diǎn)，每個(gè)端口帶寬為40MB/s，則HPS的聚集帶寬為：512/2×40MB/s=10GB/s。等分平面：有n個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)的等分平面是一組連線，它的移動(dòng)將把網(wǎng)絡(luò)分為兩個(gè)n/2個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)。最小的等分平面是指具有最小連線數(shù)的等分平面。等分帶寬(bisectionbandwidth)：每秒鐘內(nèi)在最小等分平面上通過所有連線的最大信息位數(shù)或字節(jié)數(shù)。設(shè)b為穿越最小等分平面的鏈路數(shù)，w為每條鏈路的連線數(shù)，r為每條連線的數(shù)據(jù)傳輸率（單位為：位/秒），那么該網(wǎng)絡(luò)的等分帶寬為B=bwr位/秒。5.4.3數(shù)據(jù)尋徑功能數(shù)據(jù)尋徑網(wǎng)絡(luò)用來進(jìn)行PE間數(shù)據(jù)交換?？梢允庆o態(tài)的，如TMC/CM-2所用的超立方體尋徑網(wǎng)絡(luò)；也可以是動(dòng)態(tài)的，如IBMGF11所用的多級(jí)網(wǎng)絡(luò)（通過消息傳遞來實(shí)現(xiàn)）。硬件尋徑器可用來在多個(gè)計(jì)算機(jī)結(jié)點(diǎn)之間尋徑傳送消息。常見的PE之間的數(shù)據(jù)尋徑功能包括：個(gè)人通信（一對(duì)一或一對(duì)多）；廣播、散射（一對(duì)多）；匯合/聚集、歸約（多對(duì)一）；置換、循環(huán)移位、掃描、洗牌、全交換（多對(duì)多）等。5.4.3數(shù)據(jù)尋徑功能一對(duì)一（點(diǎn)對(duì)點(diǎn)、point-to-point）通信，僅一個(gè)發(fā)送者和一個(gè)接收者。一對(duì)多通信包括廣播(broadcast)和散射(scatter)兩種，廣播是指一個(gè)進(jìn)程（或稱根進(jìn)程）向所有進(jìn)程（包括自己）發(fā)送相同消息。散射是通用化的廣播操作，因?yàn)楦M(jìn)程對(duì)不同進(jìn)程發(fā)送不同消息。多對(duì)一通信包括匯合/聚集(gather)和歸約(reduction)兩種，匯合操作是指根進(jìn)程從每個(gè)進(jìn)程接收一個(gè)不同消息。歸約是指某個(gè)根進(jìn)程接收來自每個(gè)進(jìn)程（包括自己）的局部值，并將它們?cè)诟M(jìn)程中歸約求和形成一個(gè)最后值。多對(duì)多通信中最簡(jiǎn)單的形式是置換(permutation)，其中每個(gè)進(jìn)程只向一個(gè)進(jìn)程發(fā)送并只接收一個(gè)進(jìn)程發(fā)來的消息。如循環(huán)移位(circularshift)、掃描(scan)、全交換(totalexchange)等。5.4.3數(shù)據(jù)尋徑功能P11P23P35P11P23P35，1P11P23P35P11，1P23，1P35，1（a）點(diǎn)對(duì)點(diǎn)：P1發(fā)1給P3（b）廣播：P1發(fā)1給全體5.4.3數(shù)據(jù)尋徑功能P11，3，5P2

P3

P11，3，5P23P35P11P23P35P11，3，5P23P35（c）散射：P1向每個(gè)結(jié)點(diǎn)發(fā)送一個(gè)值（d）匯合：P1從每個(gè)結(jié)點(diǎn)接收一個(gè)值5.4.3數(shù)據(jù)尋徑功能P11P23P35P11，9P23P35P11P23P35P11，5P23，1P35，3（e）歸約：P1得到和1+3+5=9（f）循環(huán)移位：每個(gè)結(jié)點(diǎn)向下一結(jié)點(diǎn)發(fā)送一個(gè)值，并接收來自上一結(jié)點(diǎn)的一個(gè)值5.4.3數(shù)據(jù)尋徑功能P11P23P35P11，1P23，4P35，9P11，2，3P24，5，6P37，8，9P11，4，7P22，5，8P33，6，9（g）掃描：P1得到1，P2得到和1+3=4，P3得到和1+3+5=9（h）全交換：每個(gè)結(jié)點(diǎn)向其他結(jié)點(diǎn)發(fā)送一個(gè)不同消息5.5靜態(tài)連接網(wǎng)絡(luò)互連網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)?networkingtopology)可以采用靜態(tài)或動(dòng)態(tài)的結(jié)構(gòu)。這兩類網(wǎng)絡(luò)已在SIMD計(jì)算機(jī)中實(shí)現(xiàn)了PE間的數(shù)據(jù)尋徑要求。靜態(tài)網(wǎng)絡(luò)(staticnetwork)由點(diǎn)-點(diǎn)直接相連而成，這種連接方式在程序執(zhí)行過程中不會(huì)改變。常用來實(shí)現(xiàn)集中式系統(tǒng)的子系統(tǒng)之間或分布式系統(tǒng)的多個(gè)計(jì)算結(jié)點(diǎn)之間的固定連接。比較適合于構(gòu)造通信模式可預(yù)測(cè)或可用靜態(tài)連接實(shí)現(xiàn)的計(jì)算機(jī)。動(dòng)態(tài)網(wǎng)絡(luò)(dynamicnetwork)是用開關(guān)通道實(shí)現(xiàn)的，它可動(dòng)態(tài)地改變結(jié)構(gòu)，使之與用戶程序中的通信要求匹配。包括總線、交叉開關(guān)和多級(jí)網(wǎng)絡(luò)等，它們常用于共享存儲(chǔ)器型多處理機(jī)中。5.5.1線性陣列是一種一維網(wǎng)絡(luò)，N個(gè)結(jié)點(diǎn)用N-1條鏈路連成一行。內(nèi)部結(jié)點(diǎn)度為2，端結(jié)點(diǎn)度為1。網(wǎng)絡(luò)直徑為N-1，N較大時(shí)，網(wǎng)絡(luò)直徑就比較大，等分帶寬為1。不具有對(duì)稱性，當(dāng)N很大時(shí)，通信效率很低。5.5.2環(huán)和帶弦環(huán)用一條附加鏈路將線性陣列的兩個(gè)端結(jié)點(diǎn)連接在一起，就構(gòu)成了環(huán)形網(wǎng)絡(luò)，或簡(jiǎn)稱環(huán)(ring)。環(huán)可以分為單向環(huán)和雙向環(huán)兩種。若兩個(gè)環(huán)在同一處出現(xiàn)故障，則這種雙向環(huán)結(jié)構(gòu)就變成了線性陣列。單向環(huán)和雙向環(huán)結(jié)構(gòu)的結(jié)點(diǎn)度均為2，并且它們都是對(duì)稱的。單向環(huán)的網(wǎng)絡(luò)直徑為N-1，雙向環(huán)的網(wǎng)絡(luò)直徑為[N/2]。5.5.2環(huán)和帶弦環(huán)分別增加一條和兩條附加鏈路就可以得到結(jié)點(diǎn)度分別為3和4的帶弦環(huán)(chordalring)。增加的鏈路愈多，則結(jié)點(diǎn)度愈高，網(wǎng)絡(luò)直徑愈小。5.5.3循環(huán)移數(shù)網(wǎng)絡(luò)和全連接循環(huán)移數(shù)(barrelshifter)網(wǎng)絡(luò)：將環(huán)上每個(gè)結(jié)點(diǎn)到與其距離為2整數(shù)冪的結(jié)點(diǎn)之間增加一條附加鏈而構(gòu)成的。即如果|j-i|=2r，r=0，1，2，…，n-1，網(wǎng)絡(luò)規(guī)模N=2n，則結(jié)點(diǎn)i與結(jié)點(diǎn)j連接。這種循環(huán)移數(shù)網(wǎng)絡(luò)的結(jié)點(diǎn)度為2n-1，網(wǎng)絡(luò)直徑為n/2。全連接：任意兩個(gè)結(jié)點(diǎn)間都有固定的線路連接。是對(duì)稱的網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)規(guī)模為N時(shí)，結(jié)點(diǎn)度為N-1，網(wǎng)絡(luò)直徑為1，鏈路數(shù)為N(N-1)/2。5.5.4樹形和星形一般來說，一棵h層完全平衡二叉樹應(yīng)有N=2h-1個(gè)結(jié)點(diǎn)。最大結(jié)點(diǎn)度為3，網(wǎng)絡(luò)直徑為2(h-1)。星形(star)是一種2層樹，若結(jié)點(diǎn)的個(gè)數(shù)為N，則結(jié)點(diǎn)度為N-1，網(wǎng)絡(luò)直徑為2。5.5.5胖樹形5.5.6網(wǎng)格形和環(huán)網(wǎng)形5.5.7超立方體5.5.8帶環(huán)立方體5.5.9k元n-立方體網(wǎng)絡(luò)4元3-立方體靜態(tài)連接網(wǎng)絡(luò)的特性網(wǎng)絡(luò)特性結(jié)點(diǎn)度網(wǎng)絡(luò)直徑鏈路數(shù)等分帶寬對(duì)稱性網(wǎng)絡(luò)規(guī)模和說明線性陣列2N-1N-11非N個(gè)結(jié)點(diǎn)環(huán)形2[N/2]N2是N個(gè)結(jié)點(diǎn)全連接N-11N(N-1)/2(N/2)2是N個(gè)結(jié)點(diǎn)二叉樹32(h-1)N-11非樹高h(yuǎn)=[lbN]星形N-12N-1[N/2]非N個(gè)結(jié)點(diǎn)2D網(wǎng)格42(r-1)2N-2rr非N=r2Illiac網(wǎng)4r-12N2r非等效N=r2帶弦環(huán)2D環(huán)網(wǎng)42[r/2]2N2r是N=r2超立方體nnnN/2N/2是N結(jié)點(diǎn)，log2N維3-CCC32k-1+[k/2]3N/2N/(2k)是k×2k結(jié)點(diǎn)環(huán)長(zhǎng)k≥3K元n-立方體2nn[k/2]nN2kn-1是N=kn個(gè)結(jié)點(diǎn)n維環(huán)網(wǎng)n[r/2]n[r/2]nN2rn-1是N=rn個(gè)結(jié)點(diǎn)上次課內(nèi)容回顧互連網(wǎng)絡(luò)的設(shè)計(jì)準(zhǔn)則通信工作方式同步、異步控制策略集中、分散交換方式線路交換、分組交換網(wǎng)絡(luò)拓?fù)潇o態(tài)、動(dòng)態(tài)單級(jí)互連網(wǎng)絡(luò)CubeiPM2IShuffle-ExchangeButterfly網(wǎng)絡(luò)特性結(jié)點(diǎn)度與網(wǎng)絡(luò)直徑聚集帶寬與等分帶寬數(shù)據(jù)尋徑功能上次課內(nèi)容回顧靜態(tài)互連網(wǎng)絡(luò)線性陣列環(huán)和帶弦環(huán)循環(huán)移數(shù)網(wǎng)和全連接樹型和星型胖樹型網(wǎng)格型和環(huán)網(wǎng)型超立方體帶環(huán)超立方體K元n-立方體例5.2設(shè)計(jì)一種采用加、乘和數(shù)據(jù)尋徑操作的算法，分別在下面兩種計(jì)算機(jī)系統(tǒng)上用最短的時(shí)間來計(jì)算表達(dá)式S=A1×B1+A2×B2+…+A32×B32。假設(shè)加法和乘法分別需要2個(gè)和4個(gè)單位時(shí)間，從存儲(chǔ)器取指令、取數(shù)據(jù)、譯碼的時(shí)間忽略不計(jì)，所有的指令和數(shù)據(jù)已裝入有關(guān)的PE。試確定下列每種情況的最小計(jì)算時(shí)間。(1)一臺(tái)串行計(jì)算機(jī)，處理機(jī)中有一個(gè)加法器和乘法器，同一時(shí)刻只有其中一個(gè)可以使用。不需要數(shù)據(jù)尋徑操作。(2)一臺(tái)有8個(gè)PE(PE0，PE1，…，PE7)的SIMD計(jì)算機(jī)，8個(gè)PE連成雙向環(huán)結(jié)構(gòu)。每個(gè)PE用1個(gè)單位時(shí)間可以把數(shù)據(jù)直接送給它的相鄰PE。操作數(shù)Ai和Bi最初存放在PEi(mod8)中，其中i=1，2，…，32。每個(gè)PE可在不同時(shí)刻執(zhí)行加法或乘法。(3)若將(2)中8個(gè)PE之間的連接改為單向環(huán)結(jié)構(gòu)，結(jié)果如何？例5.2解：(1)采用單處理機(jī)系統(tǒng)串行處理所需的時(shí)間為：t=32×4+31×2=190(單位時(shí)間)(2)根據(jù)題意，畫出8個(gè)PE的連接圖和操作數(shù)的初始存放位置如下圖所示。

PE5PE4

A8B8/A16B16/A24B24/A32B32

A1B1/A9B9/A17B17/A25B25

PE0PE1

PE7PE2

PE6PE3

例5.2數(shù)據(jù)尋徑操作的算法如下：①每個(gè)PE同時(shí)執(zhí)行乘法4次，加法3次；②PE0→PE7、PE1→PE2、PE6→PE5、PE3→PE4同時(shí)傳遞和1次，再加法1次；③PE7→PE6→PE5、PE2→PE3→PE4同時(shí)傳遞和2次，再加法1次；④PE4→PE5傳遞和1次，最后加法1次。因此，采用8個(gè)PE并行處理所需的最小時(shí)間為：t=4×4+3×2+1+2+2+2+1+2=32(單位時(shí)間)PE5PE4

PE0PE1

PE7PE2

PE6PE3

例5.2(3)若將(2)中8個(gè)PE之間的連接由雙向環(huán)結(jié)構(gòu)改為單向環(huán)結(jié)構(gòu)，8個(gè)PE的連接圖和操作數(shù)的初始存放位置如下圖所示。

A8B8/A16B16/A24B24/A32B32

A1B1/A9B9/A17B17/A25B25

PE0PE1

PE7PE2

PE6PE3

PE5PE4

例5.2數(shù)據(jù)尋徑操作的算法如下：①每個(gè)PE同時(shí)執(zhí)行乘法4次，加法3次；②PE0→PE1、PE2→PE3、PE4→PE5、PE6→PE7同時(shí)傳遞和1次，再加法1次；③PE1→PE2→PE3、PE5→PE6→PE7同時(shí)傳遞和2次，再加法1次；④PE3→PE4→PE5→PE6→PE7傳遞和4次，最后加法1次。因此，采用8個(gè)PE并行處理所需的最小時(shí)間為：t=4×4+3×2+1+2+2+2+4+2=35(單位時(shí)間)例5.2推廣到一般情形，假設(shè)處理器的個(gè)數(shù)N=2m，一次乘法需t1時(shí)間，一次加法需t2時(shí)間，相鄰PE間傳送數(shù)據(jù)需t3時(shí)間，則計(jì)算所需時(shí)間為：(1)若各處理器之間采用雙向環(huán)連接：[n/N]t1+([n/N]-1)t2+mt2+2m-1t3(２)若各處理器之間采用單向環(huán)連接：[n/N]t1+([n/N]-1)t2+mt2+（2m-1）t3每個(gè)ＰＥ同時(shí)執(zhí)行加、乘時(shí)間折疊相加時(shí)間數(shù)據(jù)傳送時(shí)間5.6動(dòng)態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)只適用于通信模式可預(yù)測(cè)的情況。為了達(dá)到多用或通用的目的，需要采用動(dòng)態(tài)互連網(wǎng)絡(luò)，能根據(jù)程序要求實(shí)現(xiàn)所有的通信互連模式。常見動(dòng)態(tài)互連網(wǎng)絡(luò)方式總線互連方式交叉開關(guān)互連方式多級(jí)網(wǎng)絡(luò)互連方式蝶式網(wǎng)絡(luò)組合網(wǎng)絡(luò)5.6.1總線互連方式是多機(jī)系統(tǒng)中實(shí)現(xiàn)互連的最簡(jiǎn)單的一種結(jié)構(gòu)形式。多個(gè)處理機(jī)、存儲(chǔ)器和I/O部件通過各自的接口部件（或通過公共的接口部件）與一條公用系統(tǒng)總線相連。信息以分時(shí)或多路轉(zhuǎn)換方式在系統(tǒng)的主設(shè)備（如處理器）及從設(shè)備（如存儲(chǔ)器模塊）之間傳送。目前已建立了許多標(biāo)準(zhǔn)總線，例如PCI、VME、Multibus、Sbus、Microchannel、IEEEFuturebus等，大多數(shù)標(biāo)準(zhǔn)總線在構(gòu)造單處理機(jī)系統(tǒng)時(shí)價(jià)格很低。而多處理機(jī)總線和層次總線，常用來構(gòu)筑SMP（SymmetricMultiprocessor）、NUMA（Non-UniformMemoryAccess）和DSM（DistributedSharedMemoryMultiprocessor）機(jī)器。1.多處理機(jī)總線

IF

CC

緩沖器

IF

IFMC

存儲(chǔ)器

LMCPUIOC

高速緩存

IF

本地總線

系統(tǒng)總線(在底板上或中夾板上)

存儲(chǔ)器總線

IOPIF

局部總線(I/O總線)

局部總線

緩沖器

IF

CPU板

存儲(chǔ)器板

I/O板

通信板

磁盤或磁帶

部件

本地外圍設(shè)備

打印機(jī)或

繪圖儀

網(wǎng)絡(luò)

(以太網(wǎng)等)

(SCSI總線)

…

2.層次總線

CCCCCC

存儲(chǔ)器

存儲(chǔ)器

存儲(chǔ)器

機(jī)群間總線

P

P

P

PP

P

C

C

C

CC

C

…

…

…

…

…

機(jī)群高速緩存

高速緩存

機(jī)群總線

處理器

機(jī)群1

機(jī)群2機(jī)群N

…

CC-NUMA的層次總線3.總線互連的缺點(diǎn)因?yàn)榭偩€由多個(gè)處理機(jī)分時(shí)共享，因此即使當(dāng)總線帶寬很高，每個(gè)處理器的帶寬也只是總帶寬的一部分。另外由于總線缺乏冗余機(jī)制易于出錯(cuò)，且總線的可擴(kuò)展性有限?？偩€一般限制在很小的機(jī)架內(nèi)，當(dāng)層次總線擴(kuò)展到幾個(gè)機(jī)架時(shí)，時(shí)鐘扭斜和全局定時(shí)就成了非常嚴(yán)重的問題。后面介紹的交叉開關(guān)和多級(jí)互連網(wǎng)絡(luò)可在一定程度上克服這些缺點(diǎn)。5.6.2交叉開關(guān)互連方式一個(gè)交叉開關(guān)(crossbar)是一個(gè)單級(jí)交換網(wǎng)絡(luò)，可以實(shí)現(xiàn)所有處理機(jī)結(jié)點(diǎn)之間、處理機(jī)結(jié)點(diǎn)與存儲(chǔ)器模塊之間或處理機(jī)結(jié)點(diǎn)與I/O模塊之間的無阻塞連接，可為每個(gè)端口提供更高的帶寬。與總線互連中采用分時(shí)使用機(jī)制不同，交叉開關(guān)采用的是空間分配機(jī)制。在并行處理中，交叉開關(guān)一般有兩種使用方式：一種是用于對(duì)稱式多處理機(jī)或多計(jì)算機(jī)機(jī)群中的處理器間的通信；另一種是用于SMP服務(wù)器或向量超級(jí)計(jì)算機(jī)中處理器和存儲(chǔ)器之間的存取。5.6.2交叉開關(guān)互連方式交叉開關(guān)互連由一組二維陣列的開關(guān)組成。它將橫向的處理機(jī)P及縱向的存儲(chǔ)器模塊M連接起來。總線條數(shù)=處理器數(shù)p+存儲(chǔ)器模塊數(shù)m。只要m≥p就必然可以使每個(gè)處理機(jī)都能有一套總線與某一存儲(chǔ)器模塊相連，從而可以大大加寬帶寬。

···

Pp

P2

P1

·

·

·

M1

M2

Mm

交叉開關(guān)5.6.2交叉開關(guān)互連方式每個(gè)交叉點(diǎn)都是一套開關(guān)，除了有多路轉(zhuǎn)換邏輯外，為了處理多個(gè)處理機(jī)同時(shí)訪問某一存儲(chǔ)器模塊所發(fā)生的沖突，縱橫交叉互連方式需要有相應(yīng)的仲裁部件。若P個(gè)處理機(jī)還要通過交叉開關(guān)與i個(gè)I/O模塊相連，這時(shí)陣列中的總線條數(shù)等于p+m+i。只有當(dāng)m≥p+i時(shí)，才能實(shí)現(xiàn)無阻塞連接。為了降低復(fù)雜性，通?？蓪⒍鄠€(gè)規(guī)模較小的交叉開關(guān)串并連接，構(gòu)成多級(jí)交叉開關(guān)網(wǎng)絡(luò)以取代單級(jí)較大規(guī)模具有相同互連能力的交叉開關(guān)。例如，由16×16交叉開關(guān)構(gòu)成的單級(jí)網(wǎng)絡(luò)將有256個(gè)交叉點(diǎn)，若用8個(gè)4×4交叉開關(guān)模塊構(gòu)成的二級(jí)16×16的交叉開關(guān)網(wǎng)絡(luò)，如圖所示，則僅需128個(gè)交叉點(diǎn)，比起單級(jí)交叉開關(guān)來可節(jié)省一半設(shè)備量。采用多級(jí)交叉開關(guān)網(wǎng)絡(luò)雖然降低了硬件復(fù)雜性，但是時(shí)延隨著網(wǎng)絡(luò)級(jí)數(shù)的增加而增大。8個(gè)4×4交叉開關(guān)構(gòu)成二級(jí)16×16交叉開關(guān)網(wǎng)絡(luò)4×4交叉開關(guān)5.6.3多級(jí)互連網(wǎng)絡(luò)多級(jí)互連網(wǎng)絡(luò)(multistageinterconnectionnetwork，簡(jiǎn)稱MIN)是指將多套單級(jí)互連網(wǎng)絡(luò)通過交換開關(guān)或交叉開關(guān)串連擴(kuò)展而成的網(wǎng)絡(luò)。與單級(jí)網(wǎng)絡(luò)相比，多級(jí)網(wǎng)絡(luò)可以通過改變開關(guān)的控制方式，靈活地實(shí)現(xiàn)各種連接，滿足系統(tǒng)應(yīng)用的需要。正是因?yàn)槎嗉?jí)網(wǎng)絡(luò)互連的靈活性，在SIMD和MIMD計(jì)算機(jī)設(shè)計(jì)中已經(jīng)使用了MIN。多級(jí)互連網(wǎng)絡(luò)在每級(jí)上使用多個(gè)開關(guān)模塊，相鄰級(jí)間的開關(guān)使用了固定的級(jí)間連接，常見的多級(jí)互連網(wǎng)絡(luò)有多級(jí)立方體互連網(wǎng)絡(luò)、多級(jí)混洗交換網(wǎng)絡(luò)(Omega網(wǎng)絡(luò))、多級(jí)PM2I網(wǎng)絡(luò)、BENES二進(jìn)制轉(zhuǎn)換網(wǎng)絡(luò)和多級(jí)CLOS網(wǎng)絡(luò)等。多級(jí)互連網(wǎng)絡(luò)的基本結(jié)構(gòu)輸入端開關(guān)開關(guān)輸出端級(jí)間固定連接1.多級(jí)互連網(wǎng)絡(luò)的3個(gè)參量1）交換開關(guān)是具有兩個(gè)入端和兩個(gè)出端的交換單元，用作各種多級(jí)互連的基本構(gòu)件。交換開關(guān)的4種開關(guān)狀態(tài)或連接方式如下圖所示。

①直連i入i出

j入j出

②交換

i入j出j入i出④下播

i入j出j入i出③上播

i入i出j入j出1.多級(jí)互連網(wǎng)絡(luò)的3個(gè)參量把只具有直連和交換兩種功能的交換開關(guān)稱為二功能交換單元。把具有直連、交換、上播和下播等全部4種功能的交換開關(guān)稱為四功能交換單元。2）拓?fù)浣Y(jié)構(gòu):指各級(jí)之間出端和入端互連模式。3）控制方式①級(jí)控制：同一級(jí)的所有開關(guān)只用一個(gè)控制信號(hào)控制，同時(shí)只能處于同一種狀態(tài)；②部分級(jí)控制：第i級(jí)的所有開關(guān)分別用i+1個(gè)信號(hào)控制，0≤i≤n-1，n為級(jí)數(shù)；③單元控制：每一個(gè)開關(guān)都有自己?jiǎn)为?dú)的控制信號(hào)控制，可各自處于不同的狀態(tài)。2.常見的多級(jí)互連網(wǎng)絡(luò)按照多級(jí)互連網(wǎng)絡(luò)對(duì)輸入與輸出連接程度的不同，可將它們分為阻塞網(wǎng)絡(luò)、非阻塞網(wǎng)絡(luò)和可重排非阻塞網(wǎng)絡(luò)。阻塞網(wǎng)絡(luò)：同時(shí)實(shí)現(xiàn)兩對(duì)或多對(duì)入端與出端之間的連接時(shí)，可能會(huì)出現(xiàn)開關(guān)狀態(tài)設(shè)置的沖突。如多級(jí)立方體網(wǎng)絡(luò)、多級(jí)混洗交換網(wǎng)絡(luò)（Omega網(wǎng)絡(luò)）、多級(jí)PM2I網(wǎng)絡(luò)、基準(zhǔn)網(wǎng)絡(luò)等。非阻塞網(wǎng)絡(luò)（全排列網(wǎng)絡(luò)）：不具有上述性質(zhì)的互連網(wǎng)絡(luò)。如多級(jí)CLOS網(wǎng)絡(luò)?？芍嘏欧亲枞W(wǎng)絡(luò)：為一對(duì)空閑的輸入輸出結(jié)點(diǎn)建立一條通路時(shí)，可能要影響到當(dāng)前正在使用的配置。但通過重新設(shè)置通路，仍可以同時(shí)實(shí)現(xiàn)原配置及新的一對(duì)結(jié)點(diǎn)的通路。如多級(jí)BENES網(wǎng)絡(luò)。上次課內(nèi)容回顧靜態(tài)互連網(wǎng)絡(luò)線性陣列環(huán)和帶弦環(huán)循環(huán)移數(shù)網(wǎng)和全連接樹型和星型胖樹型網(wǎng)格型和環(huán)網(wǎng)型超立方體帶環(huán)超立方體K元n-立方體動(dòng)態(tài)互連網(wǎng)絡(luò)總線方式交叉開關(guān)互連方式多級(jí)互連網(wǎng)絡(luò)多級(jí)互連網(wǎng)絡(luò)的三個(gè)量交叉開關(guān)直連、交叉、上播、下播兩功能交換單元、四功能交換單元拓?fù)浣Y(jié)構(gòu)控制方式級(jí)控制、部分級(jí)控制、單元控制多級(jí)立方體網(wǎng)絡(luò)1）多級(jí)立方體網(wǎng)絡(luò)由n級(jí)組成，從輸入到輸出端依次為K0、K1、……、Kn-1級(jí)。n+1個(gè)級(jí)間連接依次為C0、C1、……、Cn，其中C0為恒等置換、C1為子蝶式置換、C2為蝶式置換、C3為逆均勻洗牌置換，每級(jí)2n-1個(gè)二功能交換開關(guān)。教材有誤

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入端

出端

0

2

1

3

4

6

5

7

0

1

2

3

4

5

6

7

0

2

1

3

4

6

5

7

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

0

4

1

5

2

6

3

7

K0級(jí)K1級(jí)K2級(jí)

A

B

C

D

E

F

G

H

C0C1C2C31）多級(jí)立方體網(wǎng)絡(luò)常見的有STARAN網(wǎng)絡(luò)和間接二進(jìn)制n方體網(wǎng)絡(luò)。相同點(diǎn)：當(dāng)?shù)趇級(jí)（0≤i≤n-1）交換單元處于交換狀態(tài)時(shí)，實(shí)現(xiàn)的是Cubei互連函數(shù)，且都采用二功能交換單元；不同點(diǎn)：交換開關(guān)的控制方式不同，STARAN網(wǎng)絡(luò)采用級(jí)控制（稱交換網(wǎng)絡(luò)）或部分級(jí)控制（稱移數(shù)網(wǎng)絡(luò)）；而間接二進(jìn)制n方體網(wǎng)絡(luò)采用單元控制。STARAN網(wǎng)絡(luò)用作交換網(wǎng)絡(luò)時(shí)，采用級(jí)控制。級(jí)控制信號(hào)為0時(shí)，交換開關(guān)都完成直連功能；級(jí)控制信號(hào)為1時(shí)，交換開關(guān)都完成Cubei交換函數(shù)的功能。STARAN交換網(wǎng)絡(luò)(N=8)級(jí)控制信號(hào)的組合及所實(shí)現(xiàn)的功能級(jí)控制信號(hào)（K2K1K0）000001010011100101110111入端號(hào)012345670123456710325476230167453210765445670123547610236745230176543210執(zhí)行的交換函數(shù)功能恒等四組二元四組二元+二組四元二組四元四組二元+一組八元四組二元+二組四元+一組八元四組二元+一組八元一組八元iCube0Cube1Cube0+Cube1Cube2Cube0+Cube2Cube1+Cube2Cube0+Cube1+Cube2K2K1K0=011時(shí)的各級(jí)交換開關(guān)狀態(tài)

E

F

G

H

0

4

1

5

2

6

3

7

0

4

1

5

2

6

3

7

0

2

1

3

4

6

5

7

0

2

1

3

4

6

5

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入

端

出

端

0級(jí)1級(jí)2級(jí)

A

B

C

D

K0=1K1=1K2=0

Cube0+Cube1K2K1K0=101時(shí)，實(shí)現(xiàn)4組2元+2組4元+1組8元交換入端排列：01234567分成4組：|01|23|45|67|每組2元交換：|10|32|54|76|分成2組：|1032|5476|每組4元交換：|2301|6745|分成1組：|23016745|每組8元交換：54761032Cube0+Cube2STARAN網(wǎng)絡(luò)用作移數(shù)網(wǎng)絡(luò)采用部分級(jí)控制，第i級(jí)的2n-1個(gè)二功能交換開關(guān)分成i+1組，每組用一個(gè)控制信號(hào)控制。對(duì)于n級(jí)STARAN移數(shù)網(wǎng)絡(luò)來說，從第0級(jí)到第n-1級(jí)所需的控制信號(hào)個(gè)數(shù)分別為1，2，3，…，n個(gè)。當(dāng)處理單元個(gè)數(shù)N=8時(shí)，共需要6個(gè)控制信號(hào)，每一級(jí)控制信號(hào)的分組和控制結(jié)果如表5.3所示。STARAN移數(shù)網(wǎng)絡(luò)的置換函數(shù)可以表示為：α(x)=(x+2m)mod2pp和m為整數(shù)，且0≤m＜p≤n。三級(jí)移數(shù)網(wǎng)絡(luò)能實(shí)現(xiàn)的入出端連接及移數(shù)函數(shù)功能部分級(jí)控制信號(hào)2級(jí)K，LJI0010111110000000000001級(jí)F，HE，G011100011100000級(jí)A，B，C，D1001010入端號(hào)0123456712345670234567014567012312305674230167451032547601234567相當(dāng)于實(shí)現(xiàn)的移數(shù)功能移1mod8移2mod8移4mod8移1mod4移2mod4移1mod2不移全等三級(jí)移數(shù)網(wǎng)舉例（表5.3功能部分第一列）

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入端

出端

0

2

1

3

4

6

5

7

0

1

2

3

4

5

6

7

0

2

1

3

4

6

5

7

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

0

4

1

5

2

6

3

7

0級(jí)1級(jí)2級(jí)

A

B

C

D

E

F

G

H

α(x)=(x+20)mod23三級(jí)移數(shù)網(wǎng)舉例（表5.3功能部分第五列）

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入端

出端

0

2

1

3

4

6

5

7

0

1

2

3

4

5

6

7

0

2

1

3

4

6

5

7

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

0

4

1

5

2

6

3

7

0級(jí)1級(jí)2級(jí)

A

B

C

D

E

F

G

H

α(x)=(x+22)mod22分2組，組內(nèi)循環(huán)移2位2）多級(jí)混洗交換網(wǎng)絡(luò)又稱Omega網(wǎng)絡(luò)，由n級(jí)相同的網(wǎng)絡(luò)組成，每一級(jí)都包含一個(gè)全混洗拓?fù)浜碗S后一列2n-1個(gè)四功能交換單元，采用單元控制方式。一個(gè)2n輸入的Omega網(wǎng)絡(luò)需要n級(jí)2×2開關(guān)，每級(jí)都包含2n-1個(gè)采用單元控制方式的四功能交換單元。如果Omega網(wǎng)絡(luò)采用級(jí)控制，并且四功能單元只完成直連和交換兩種功能，則它就成為了STARAN網(wǎng)絡(luò)的逆網(wǎng)絡(luò)，即它們的輸入端和輸出端的數(shù)據(jù)流向相反。N=8的多級(jí)混洗交換網(wǎng)絡(luò)

0

2

1

3

4

6

5

7

0

2

1

3

4

6

5

7

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入

端

出

端

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

2級(jí)1級(jí)

0級(jí)

A

B

C

D

E

F

G

H

C3C2C1C0每級(jí)間都是全混洗級(jí)編號(hào)與STARAN相反N=8的多級(jí)立方體網(wǎng)絡(luò)和Omega網(wǎng)絡(luò)的關(guān)系

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入

端

出

端

0

2

1

3

4

6

5

7

0

1

2

3

4

5

6

7

0

2

1

3

4

6

5

7

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

0

4

1

5

2

6

3

7

0級(jí)1級(jí)2級(jí)

A

B

C

D

E

G

F

H

多級(jí)立方體網(wǎng)絡(luò)0

2

1

3

4

6

5

7

0

2

1

3

4

6

5

7

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入

端

出

端

0

4

1

5

2

6

3

7

0

1

2

3

4

5

6

7

2級(jí)1級(jí)

0級(jí)

A

B

C

D

E

F

G

H

Omega網(wǎng)絡(luò)互為逆網(wǎng)絡(luò)上次課內(nèi)容回顧多級(jí)立方體網(wǎng)絡(luò)STARAN網(wǎng)交換網(wǎng)絡(luò)：級(jí)控制移數(shù)網(wǎng)絡(luò)：部分級(jí)控制間接二進(jìn)制n方體網(wǎng)絡(luò)單元控制相同點(diǎn)：第i級(jí)處于交換像狀態(tài)時(shí)，實(shí)現(xiàn)Cubei互連函數(shù)；都采用兩功能交換單元多級(jí)混洗交換網(wǎng)又稱Omega網(wǎng)絡(luò)，采用四功能交換單元、單元控制如采用級(jí)控制、二功能交換單元，則是STARAN的逆網(wǎng)絡(luò)動(dòng)態(tài)互連網(wǎng)絡(luò)總線方式交叉開關(guān)互連方式多級(jí)互連網(wǎng)絡(luò)多級(jí)互連網(wǎng)絡(luò)的三個(gè)量交叉開關(guān)直連、交叉、上播、下播兩功能交換單元、四功能交換單元拓?fù)浣Y(jié)構(gòu)控制方式級(jí)控制、部分級(jí)控制、單元控制3）多級(jí)PM2I網(wǎng)絡(luò)多級(jí)PM2I網(wǎng)絡(luò)包含n級(jí)單元間連接，每一級(jí)都是把前后兩列各N=2n個(gè)單元按PM2I拓?fù)浠ミB起來。8個(gè)處理單元的多級(jí)PM2I網(wǎng)絡(luò)如圖5.32所示。就第i級(jí)而言(0≤i≤n-1，這里為0≤i≤2)，每個(gè)輸入端j(0≤j≤N-1)都有3根線分別連接到輸出端(j-2i)modN、j和(j+2i)modN。第0級(jí)完成的是PM2±0，第1級(jí)完成的是PM2±1，第2級(jí)完成的是PM2±2。單級(jí)PM2I網(wǎng)絡(luò)的最大距離為┌n/2┐，但組成多級(jí)PM2I網(wǎng)絡(luò)時(shí)用了多級(jí)。在這種網(wǎng)絡(luò)中，從一個(gè)處理單元到另一個(gè)處理單元的路由有多條路徑可供選擇。如為實(shí)現(xiàn)6號(hào)處理單元將信息傳送4號(hào)處理單元，可以經(jīng)6→6→4→4，或6→2→4→4等多條路徑完成。顯然在多級(jí)網(wǎng)絡(luò)中提供的這種冗余通路，有利于提高系統(tǒng)的可靠性。N=8的多級(jí)PM2I網(wǎng)絡(luò)

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

PM2+2

PM2-2

PM2+1PM2-1

PM2+0PM2-0

入端

出端

a

b

c

d

a

b

c

d

e

f

g

h

e

f

g

h

i

j

j

i

k

l

k

l

m

m

n

n

2級(jí)1級(jí)0級(jí)

多級(jí)PM2I網(wǎng)絡(luò)中各級(jí)各單元的單元控制原理

上播（上控）

下播

直連

上播

下播（下控）

直連（平控）

D

H

U

5種多級(jí)互連網(wǎng)絡(luò)的比較多級(jí)互連網(wǎng)絡(luò)的3個(gè)參量多級(jí)互連網(wǎng)絡(luò)的類型交換開關(guān)控制方式拓?fù)浣Y(jié)構(gòu)多級(jí)立方體網(wǎng)絡(luò)STARAN交換網(wǎng)絡(luò)二功能交換單元級(jí)控制單級(jí)立方體網(wǎng)絡(luò)STARAN移數(shù)網(wǎng)絡(luò)二功能交換單元部分級(jí)控制單級(jí)立方體網(wǎng)絡(luò)間接二進(jìn)制n方體網(wǎng)絡(luò)二功能交換單元單元控制單級(jí)立方體網(wǎng)絡(luò)多級(jí)混洗交換網(wǎng)絡(luò)（Omega網(wǎng)絡(luò)）四功能交換單元單元控制單級(jí)混洗交換網(wǎng)絡(luò)強(qiáng)化數(shù)據(jù)變換網(wǎng)絡(luò)（ADM網(wǎng)絡(luò)）多功能交換單元單元控制單級(jí)PM2I網(wǎng)絡(luò)4）基準(zhǔn)網(wǎng)絡(luò)從結(jié)構(gòu)上看，它與二進(jìn)制立方體網(wǎng)絡(luò)的逆網(wǎng)絡(luò)非常相似，只是在第1級(jí)的級(jí)間互連有所不同?；鶞?zhǔn)網(wǎng)絡(luò)的級(jí)間互連從輸入到輸出依次為恒等、逆均勻混洗、子逆均勻混洗和恒等置換，所有的開關(guān)均為二功能交換單元，采用單元控制方式?；鶞?zhǔn)網(wǎng)絡(luò)常用于在多級(jí)互連網(wǎng)絡(luò)的研究過程中，將基準(zhǔn)網(wǎng)絡(luò)作為中間介質(zhì)，模擬一種網(wǎng)絡(luò)的拓?fù)浜凸δ艿?。N=8的基準(zhǔn)網(wǎng)絡(luò)

I

J

K

L

0

1

2

3

4

5

6

7

0

1

2

3

4

5

6

7

入

端

出