【正文】 存儲器、私有高速緩存、共享存儲器和共享外圍設(shè)備的一般處理機(jī)系統(tǒng)的互連結(jié)構(gòu) ?1 IPMN(處理機(jī) 存儲器網(wǎng)絡(luò) ) ?2 PION(處理機(jī) I/O網(wǎng)絡(luò) ) ?3 IPCN(處理機(jī)之間通信網(wǎng)絡(luò) ) ?P(處理機(jī) )C(高速緩沖存儲器 )SM(共享存儲器 )LM(本地存儲器 ) 磁盤 SM1 SM2 SMm IPMN …… Cn Pn LM C1 P1 LM IPCN …… …… …… PION 磁帶 打印機(jī) 終端 網(wǎng)絡(luò) … (共享存儲器 ) (共享 I/O與外設(shè) ) 處理機(jī)系統(tǒng)的互連結(jié)構(gòu) tiger September 2022 7 ?互連函數(shù) ?互連網(wǎng)的 N個輸入和 N個輸出端分別用整數(shù) (0, 1, 2, ..., N1)表示， 互連函數(shù) 表示相互連接的輸出端號和輸入端號之間的一一對應(yīng)關(guān)系 ?表示方法：互連函數(shù)法，圖形表示法 , 輸入輸出對應(yīng)表示法 ?函數(shù)表示法： f(x)表示互連函數(shù)， 為： f(xn1xn2...x1x0 ) ?x表示輸入端號，常用 n位二進(jìn)制形式表示 xn1xn2...x1x0 ?圖形表示法 : 用圖形表示輸入和輸出端之間的連接 ?輸入輸出對應(yīng) (矩陣 )表示法 ?循環(huán)表示法 : 把互連函數(shù) f(x)表示為 (x0， x1， ...， xj) (xk， xk+1， ...， xl) ... ?第 1個括號表示循環(huán) ?f(x0)=x1， f(x1)=x2， ...， f(xj)=x0 ?j+1稱為該循環(huán)的長度 0 1 2 ... N1 f(0) f(1) f(2)...f(N1) tiger September 2022 8 常用的互連函數(shù) ?1 恒等置換 I( xn1xn2 ... x1x0 )= xn1xn2 ...x1x0 tiger September 2022 9 2 交換置換 Exchange ?二進(jìn)制地址編號中第 0位位值不同的輸入和輸出端間的連接 E(xn1xn2 ... x1x0 )= xn1xn2 ... x1x0 ?其他互連函數(shù)還有：方體置換、均勻洗牌置換、蝶式置換、位序顛倒置換、移數(shù)置換、加減 2i置換 tiger September 2022 10 3 方體置換 Cube ?當(dāng) n=3時，共有 3種函數(shù)，每種函數(shù)能夠表示 8個結(jié)點之間的連接關(guān)系 ?交換函數(shù)主要用于超立方體互連網(wǎng)中，也稱為超立方體函數(shù)，用 Cube表示，如： Cube0、 Cube Cube2等 0111101111 . . .. . .). . .. . .( xxxxxxxxxxxxC kkknkkknk ?????? ?012022201202210120220)()()(xxxxxxCxxxxxxCxxxxxxC???tiger September 2022 11 C0, C1, C2 變化發(fā)生在 0, 1, 2位 分別是高 2, 1, 0位相同的為一個組 組數(shù) 4, 2, 1 組內(nèi)加 /減 1, 2, 4 C0循環(huán)表示 (0,1), (2,3), (4,5), (6,7) 3 方體置換 Cube 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 E 0 交換函數(shù) E 1 交換函數(shù) E 2 交換函數(shù) C0 C2 C1 tiger September 2022 12 4 均勻洗牌置換 Perfect shuffle ?把二進(jìn)制位循環(huán)左移一位 ?子混洗 (subshuffle)S(k) 最低 k位循環(huán)左移一位 ?超混洗牌 (supershuffle) S(k) 最高 k位循環(huán)左移一位 顯然成立 逆混洗函數(shù) 教材 P397L2,3,5,6錯 101320221 ...)...( ????? ? nnnnn xxxxxxxxxS011kn1nkn2n011knkn2n1n( k )1k012kk2n1n012k1kk2n1n( k )xx...xxx...x=)xx...xx...x(xxxx...xx...xx=)xx...xxx...x(x???????????????SSxxSxSxSxSxS nn????)()()()()()1()1()()(121001211 ...)...( xxxxxxxxS nnnn ????? ?tiger September 2022 13 4 均勻洗牌置換 Perfect shuffle ?均勻洗牌 : 由上到下分兩組，兩組互相交錯 ?0,1,2,3接至 0,2,4,6 ?4,5,6,7接至 1,3,5,7 ?輸入端由上到下分兩組，輸出端分四組 ?組 0,1,2,3接至輸出端各組的上 , 0,2,4,6 ?組 4,5,6,7接至輸出端各組的下 , 1,3,5,7 ?均勻洗牌循環(huán)表示 (0), (1,2,4), (3,6,5), (7) ?子洗牌是將整組數(shù)據(jù)分成若干個子組，對每個子組完成均勻洗牌變換。 S(2) 以最高位分兩組 0， 1， 2， 3； 4， 5， 6， 7 ?逆均勻洗牌是均勻洗牌的逆函數(shù)，兩者的輸入端和輸出端正好互換 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 均勻洗牌 置換 子 洗牌 置換 S ( 2 ) 超 洗牌 置換 S ( 2 ) 逆 均勻洗牌 置換 S 1 Ω tiger September 2022 14 4 均勻洗牌置換 Perfect shuffle ?只用均勻洗牌函數(shù)不能實現(xiàn)任意結(jié)點之間的互連 ?通常與其他函數(shù)，如交換函數(shù)一起構(gòu)成互連網(wǎng)絡(luò) ?00 ?77 ?均勻洗牌與逆均勻洗牌是兩種十分有用的互連函數(shù) ?以它們代表的鏈路與以交換置換代表的開關(guān)多級組合起來可構(gòu)成 Omega(Ω)網(wǎng)絡(luò)與逆 Omega(Ω^1)網(wǎng)絡(luò) tiger September 2022 15 5 蝶式置換 Butterfly ?蝶式函數(shù)的名稱來自于 FFT變換時的圖形，如蝴蝶式樣 ?將輸入端二進(jìn)制結(jié)點號的最高位和最低位互換位置 ?子蝶式 (subbutterfly) B(k)最低 k位的最高位與最低位互換位置 ?超蝶式 (superbutterfly) B(k)最高 k位的最高位與最低位互換位置 ?顯然成立 ?教材 P397倒數(shù) L2,3錯 ?教材 P398L1,2錯 11202221 ...)...( ???? ? nnnn xxxxxxxxB0111120221)(112021012121)(......=)......(......=)......(xxxxxxxxxxxxBxxxxxxxxxxxxxxBknnknnknknnnkkkknnkkknnk??????????????????xxBxBxBxBxB nn????)()()()()()1()1()()(tiger September 2022 16 5 蝶式置換 Butterfly ?與全混洗函數(shù)類似，只用蝶式函數(shù)也不能實現(xiàn)任意結(jié)點之間的互連 ?蝶式函數(shù)循環(huán)表示 (0), (2), (5), (7), (1,4), (3,6) 0 0 0 0 0 0 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 B ＝ R 函數(shù) B (2 ) =R (2 ) 函數(shù) B(2 )=R(2 )函數(shù) tiger September 2022 17 6 位序顛倒置換 Bit Reversal ?將輸入端二進(jìn)制地址的位序反過來就得相應(yīng)輸出的地址 ?子反位序函數(shù)：最低 k位的位序反過來 ?超反位序函數(shù)：最高 k位的位序反過來 ?對于 n=3的情況，正好有 R=B， R(2)=B(2)， R(2)=B(2) ?教材 P398 6. L5,6錯 12100121 ...)...( ???? ? nnnn xxxxxxxxR01112101121)(121021012121)(......=)......(......=)......(xxxxxxxxxxxxxRxxxxxxxxxxxxxxRknnnknknknknnnkkkknnkkknnk????????????????????tiger September 2022 18 7 移數(shù)置換 ?將輸入端數(shù)組循環(huán)移動一定的位置向輸出端傳輸 ?可將整個輸入數(shù)組分成若干個子數(shù)組，在子數(shù)組內(nèi)進(jìn)行循環(huán)移數(shù)置換，這種段內(nèi)循環(huán)移數(shù)的表達(dá)式可寫成兩個式子 (a)移數(shù)量 k=2 (b)段內(nèi)移數(shù)置換 k=1,r=2 NNkxxA ???? x0 ,m od)()(rrrrnrnkxxAxxA2m o d)()()()(0:)1(0:)1(:)1(:)1(???????tiger September 2022 19 8 加減 2i置換 ?其中： 0 ? x ? N1， 0 ? i ? n1， n = log2 N ?i=+0 循環(huán)表示 (0,1,2,3,4,5,6,7) ?i=+1 循環(huán)表示 (0,2,4,6), (1,3,5,7) NxxPMNxxPMiiiim o d)2()(2m o d)2()(2??????0 0 0