．-
■
●
第 l9卷 第 9期
1998年 9月
小 型 微 型计 算机 系统
MlNl—M ICRO SYSTEMS
VO1．19 No．9
一
sep11998
_．、H 、． ～ l'H 嘴
、
多级互连网络互连函数的 r ， 卜。L： 矩阵理论
一
、
．
，
- -
．
’
÷
。
，
． ：捌 - 一。。 一 r__。。 ’_ ～’ 。。 ，(广东士业大草i{ 村 学 工 系广卅5160 90)
- I 。
摘 要 多级互连 网络是大规模并行 处理系统和大型 ATM 交换机采用的主要互连结
构。本文采用矩璋形式表示多级网髂的输入、输出和互连函数，进而提出 了互连函数的
矩阵理 互连函数的矩阵理论可直接用于模拟计算和验证以三维立体互连为特征 的
荔鋈 ，照 ．．． ：、 关键词多级互连网络 光学互连，互连函数 ‘ W瀚l y ． 、—_-·-—_’_一’—_· ’’、·-___一 l ●
分类号 1TP。93 ．
、 ． l 、 ． ’ ’
．
’
’
}l ’ ，
．
J
，
l 引言
毒缨 幸耳 孝孥全混 )?蟀 (。Ba n y．an一)． 全享 (cr0s~一。日 ve ，r 箩，系由多级
开关单元按照一定的拓扑规则或互连函数连接而成，能够在连接性能与设备量之间取得较好
的平衡，是大规模并行处理系统和大容量空分A，I= 疼 卡几 甩 勺、主器互萼 ：2】。
多级互连网络可采用电子学V：LSt互连技术或光子学互连技术实现 一光学互连，特别是自
由空间光互连，是在垂直于二维平面阵列器件(如交换单乖阵列)的第；维． 由空间中进行的
立体互连，具有极高的互连密度：，各条光线(即通信链路) ．仅可以拄空间住意交叉互不干扰而
且 延产格襁等， 根本上摆脱了VLS!．互连技术 有的串话、时钟歪 细电磁干扰等缺陷。
‘在光互连网 的实验’研究中，网络的输入和输出通常是 个兰维的平茴数学菡象’-图象中
的每个象素点对应一条通道或链路。．_由．手现有互连函数白慑 东方法一般某角掏络入出端口地
址的二进制编码形式表宗 茵说呆堍譬 涌享 鲁 兰雍 啬 卤 辖久柑靖 努蒋征的
光互连网络的实验研究：我 们在实验研究的基础上曾经提_出 “互连矩 概念，并且利用互
连矩阵对实验结果进行过模拟计算n 。’本文将以此为基龇彤戡 苍1j巳皲莞整酌多级互连网
络互连函数的矩阵理论。 ’ ；) 一 c1， i· ‘ ll
t ； 峨 一 ： 、 一 j，、 lll ’
2 多级互连网络概论 (I⋯⋯ ll ⋯·一⋯⋯
2．1 拓扑结构 壬： 皇 ．
多级互连网络是指由多级交换单元按照特定的互连模式连接起来的一类有规则的网络拓
扑 2·x 2交觯 元包含 个 口和} 个出矗，其连接方式有 种好能敏劝能l_状态，如图 1所
示。交换单元 称结点()Lode)：港 点的状态由路径控制算法决定 适当选蠲}控制算法，可以实
19。 一 2一lo嘎礴一- 广东自然科学基金垮助项目·篁军·博士· 葶攀·手量 究 警为 互萼 ATM网络·
维普资讯
e
第 19 卷第 9 期才‘
1998 年 9 月
小型微型计算机系统
MINI-MICRO SYSTEMS
. 19 No. 9
盐 1 噜Se~.1998
丁~U 咱
多级互连网络互连函数的矩阵理论:'*
l
J :JUJH 气r，'1 J~
〈广东工业大审计算机科学与工程系 广州 51(090)- "
,1
叶'正当 了
摘要 多级互连网络是大规模并行处理率统和大型 ATM 支换机采用均主要互连结
构。本文革用矩碎形式表示乡级网络的输入、输出和主运函数:进而提出丁互连函数的
矩阵理论志;L连函数的招阵理论可直接用于模拟计算和验证以三维立体互连为特征的
尤互连网络的实验研究结果。， h! \ .1:\ f !J
关键词伊互连网络吧主主连，毛主空空 忖旦刺叫V记 J
分类号 TP393 飞
1 引言
'
鑫级互苟因等~ .， ~qρme回华华拿1昆r~t) ~梅树{写aIlyan)r:金交叉 (Cro帘。re气)!寺'系由多级
开关单元按照干定的拓扑规则或互连函数连接而成，能够在连接性能与设备量之间取得较择
衡，是大规模并行处理系统和大容量空分 AW与交换机养用的;主要互将带气) 。
多
由空间
立体~
且峙延
在
的每个象素点对应一条通道或链路。由于现有互连函数的去求方法一般某国尚结儿出端口地
址的二进制编码形式表示-因z比不桂抽宣接7》召芋拮导以二维肝平面e封樨孚国象输入川柑辅辅制、吕曲!封加捋征的
光互连网络的实验研先;我1怕f门1在实验阱究由辜础上曾经提出
连短阵对实验结果进行过模拟计算E协E←川~飞本文将以、此为垂陆影注-，告饨较完整的多级宜连网
i) :.-飞 '1' 、 f飞
• •
，论概
论各叫作吁阿倒在连哟
Ju
互
时
L级
配'多互-络
2
γ
J ，、 '!导-
(: t,
2. 1 拓扑结构 .j.. 坷'亏i Jr时说;
多级互连网络是指由多级交换单元按照特定的互连模式连接起来的一类有规则的网络拓
扑.2.'X2 竞摒碍'元毡啻" ，2:个λi口和'0'个出目，其连接方式有S 种窍能的功能-~最态，如固 1 所
示。交换单元见称结点也结点‘盹状崽由路径控制算黯捷定L-e 遭当选择控制算法，可以实
1 、 i 飞飞 :,
11 ._1
四9ji-12ω 收稿:3 ，广东自然科学基金资助项目·其军·博士·同学轧事哥珩究领域为边E革月络、ATM 网络.
"一、←-一一一-----.. ~…'一
8 小 型 微 型 计 算 机 系 统
现任一入端到任一出端的一对一连接，或任一入端到多个出端的多播连接 或任一入端到所有
出端的广播连接。 ·
⋯ 曼鍪 N的2 一 互连网络由(n+ 1 x，纵g．12
N
×
~ 2
结
N
点
~
2 2 和 聂 ’ ‘
n级链路(1ink)构成‘若把网络的输、 、 ．．．．～ 。． ．
入和输出级也包捂在阿 有℃Ti十 一 ‘ 豳 2变换单元白{}& 状悉
2)级链路)， l()g： 。每级结点有个 N结点，每级链路有条 2N链路。结点和链路统称网络元
件，从左到右依次编|为0，1，⋯，n级和(n--1)级。常见的多级光互连网络有Omega(多级全混
洗)、榕树(Banyan)、全交叉(,Crossover)三种：其拓扑结构如图 2所示。
，
． 霹 秘
(a)Omega (b)Banyan (c)Crossover网络的拓扑结构(2 8)
图 2 i
2·2 戛连函数 ．、 ．． ⋯
宣连函数即糟邻商级结点间链路的连接模 ，通南以 点或链路地址编号酌兰连制编码
形式衾示 ’。 l 一。1 ， 一 L Ill‘
1口t7 。‘ 蔓 苫 离 0、 ， ． ，‘ ’。 、 ’ i，‘ = 全交叉网络有直通和交叉两种互连函数 ： ’ ’· ～
a [( 1P -- 2-~-ViPo)i] (P 1 一_2⋯P<lPo) +1，n=!og~N。 ‘’。’ (1)
． + ．
B‘ [(P 一lP 一2一-plP9)：] (P ．_lP ⋯，p 一 ’，P 一I-l·： ： )：+。
、
：一 ’(2)
其中a“ 表示第j级链琏的直通互连诺 数，实际上是．一种恒等置换； 表示第i．级链路的
衮叉互连函数，它将第i级结点内二进彻地址为(Pn 。P 一2．．·P。P 结点连接到 第(i+1j级结
粤内=二避 l地址 P ÷ 了爵i-一 - )-o) 点 ．‘ ． ，：、 ‘ 0=．_，．+．
，榕树网锋的手连函数 有直通与瓣式耳连二种。蝶式耳 围蓼可誊示辜Ⅱ下．11 ．
1 ，． 7 曝一lf ·．P 一(Pn一 P。- P _ 椰-Pn—i一2． PJPn)I+卜 ．、． (3)
Ome
．ga母孥 每 碧罄帮 均为 津互连模式：；： ．、 ． ．
Q“ E(P P 一l⋯PlPo)i]一(P ⋯PlPoP )⋯ ． ． ．(4)
上式表明：第i级结点内二进制地址为(PnPn一。⋯P。P。)的出口应该连接到第 (i+1)级结点
内二进制地址为( 一，⋯P，P。P )的入口上。 0 ’ ：j ： 1
3 互连函数的矩阵理论 ∽ ；!
． ．
一
．
：’：、 一
+
： ⋯_ 0 0 ． 、 _ll 。。- 、
上述互连函数的传统表示方法与相邻两级结点或链路的地址及其二进觎编羁形式密切相
关，难以解释或预测以二维平面数字图象作为输入的光学‘l互连网络互连函．魏的实验结果。为
此，我们将网络的输入、输出和互连函数均以矩阵形式表示。 一
网络的输入、输出二维平面数字图象(假设有 2N×M个象素)可以分别用矩阵X(ZN，
●
●
■
●
维普资讯
••••
现任一λ端到任一出端的一对一连接，或任一入端到多个出端的多播连接 J或佳一λ端到所有
出端的广播连接。
端口数为 2N 的 2NX2N 多级
互连网络由 (n+D级 2X2 结点和
n 级链路(linU1咆成三若把目1月输飞 /旷
入和输出级也包括在内贸l有 tri斗~由}"~.2)!:à Ìè:换单元@6.甜功..状恙‘三
2)级链路) ,11.= log2，N。每级结点有个 N 结点，每级链路有条 2N 链路。结点和链路统称网络元
件，从左到在依次编切♂， 1 ，…， n 级和 (n一 D级。常见的多级光互连网络有 Omega(多级全混
洗)、榕树(Banytm) 、全交叉(Cros~over)三种;其福孙结构如图 2 所示。
互连函数
J 主运函数即柑邻两级结;在间链1路的连接模式，通常以结点或链路地址编号西兰进制编码
形式表示。 金 t ~
全交叉网络有直通和交叉两种互连函数=
〔(PJi气·剖PoLF (PJrt·-忡。1id=!?gjN ! 、 二牛 ω
俨[(P叫P.~2..:P~PQ);J~ (P.:"' lP.":2... ， p.-;' ， P.-i-:l…R瓦)~+l ' (2)
其中 ?t哈示窍嗖链陆的直通生连菌i数，实际上是卜种'恒等;置换 ;~i)表示:~(级售路的
交叉互运函数?它将t第 i 练结点内二进:制地址为(Pafld←ifjPIP41的结点连接-到lFfi+i)级结
点内二进制地址事σ叩P十2…pa?rTJ队均结点上。， , c^
1 榕耐网络的特函数有直通明式耳逗二币。蝶式平南致可表示如下: 1 ;.~~ :
_ ì'~'~.[~"rc1P"':2，~.~p.)'P，~i]=:= (P.-~p."':到fa→P.*lP…z…P~PO)i+l" 、
Om~ga用挚的备辑辜J连串数相同吨均为全E樨洗互连模式 zi:
。ω[(PnPn-l…P1PO)jJ= (P.- 1 …P1PoPn)j+l 刊" (的
上式表明 z第 i 级结点内二进制地址为(.- 1 …P1PO )的出口应该连接到第 O+D级结点
内二进制地址为(P.- 1 …P1PoPn)的入口上。 L 『 J L1JUY;;匀，EJL:tS这 f
互连函数的矩阵理论 白白兰 fty
上述互连函数的传统囊乐方法;与相邻两级结点或链路的地址及提二进制编辑形式密切相
关，难以解释或预测以二雄平面数字固盘!作为输入的光学，:g}连网络互连画数曲实验结果。为
此，我们将网络的输入、输出和互连函数均以短阵形式表示。
网络的输λ、输出工维平面数字图象(假设有 2NX M 个象素)可以分别用短阵 X(2N ，
(3)
1998 年
窜汁'
7口，
S
,'S
6
J
(c) Crossover 网络的拓扑结构(2N=8)
ë
z
阻塞
。、
ZW
飞‘，。
- 0 .Q
W- I
3:' 、 2 ‘
6 6
7 古
今回町，
主主
上描
主主
交叉
小型微型计算机系统
(b) Banyan
图 2
ZH
~i r=
11凶手 !-jd
(a) Omega
8
3
-
,101
●
’
-
●
9期 艾军：多级互连网络互连函数的矩阵理论 9
M)和 Y(2N，M)表示：
X(2N，M)=(X )，Y(2N，M)一[y ]；(k一1，2，⋯，2N；j=1，2，⋯，M) (5)
’Xkj和 ykj分别是输入、输出图象中坐标， ’ 。 一 ～～- ’
值为(k，j)的象素点所对应的灰度值。当M 删” ： 广— —__1
=1时，X(2N)、Y(2N)均为列向量，其元 —
． ． ． ． 卜
素可用来表示网络输入、输出端口的地址 一I l口 ．ntercon ct．口 [
编号。 ． 。N—1_-]_-I 卜r卜 。N
如果用Xi和Yi分别表示第i级结点 ’ 二：二二 “nk ‘ -L--_~--．
的输入、输出图象，参见图3，则有， Lt __—— ．+．
Yi：SiXl (6) s F- s．-
其中，St表示结点的状态，由结点控制 l 图3互连函数矩阵理论原理函
算法决定，作者称之为结点矩阵。
第 (i+1)级结点的输入图象(亦即第i级链路的输出图象)x． 可以通过下式由第i级结
点的输出图象(亦即第 i级链路的输入图象)Y 得到， 一 、、
一
， 二．． 一．
．
。
； }X =FiYi ～．
．
1
． ， ：j 。。 ‘ ： (7)
。
，
， ， ： ： ! 一 、 ．1、 ’ l l ’ 一 0 ’ ．
其中Ft是一个方阵，由网络的互连函数决定，作者称之为覃连矩阵 、 ．
据(6)和(7)式可得， 、 。 j
Yi=Si Xi=Si Fi—l Yi_． ． (8)
由于第n级结点的输出图象就是网络的输 图象，再利用(8)和(6)式，则有，
，
一 ． 、n 。 。 n
Y(2N，M) 一-Y [； Fi 一[{ siF -3SoX。 (9)
对于 CrossOver和 Banyan网络(参照图 2 )， 第 0级结点的输入图像就是网络的输入图
象。而对于Om e’ga 网络 第_0．级结点的 图象告手Omeg尸= 网络的互连矩阵与网络输入图象
的乘积。故有 ． ， }，． --。 r -． 、．r
．
X!
o fX ，(2N；M)，⋯{or、 ．c s sove，r '-an Ban~,a．n．， net．1J，w or，k'A．0--~ sl_，． (1o)
， Id·X(2N，M)j fo 毒话 network ： ： f l Jl u
所以只夏知道网络的缡 矩阵和互连矩阵麟可以通过r 9)和( Q)式毒接由网络的输入图
象X(2N，M)计算出相应的输出图象Y(2N，M)。结点矩阵由具体的阚驺 一斑端 构连接
模式要求和所采用的选路算法(结点控制算法)决定 互连矩阵可以根据特定网络的互连函数
求得。
3．1 Omega网络的互连矩阵 r
由于Omega网络的各级覃连函数相同，均为全混洗互连模式，所以对应的各级互连矩阵
也相同，具体形式求得如下： 一
r ‘ 一 。 1
o(2N)：[pij]’ pij=l 1’ for j=(2 1+[ ])m0d(2N) (11)
【0，for j：others．(i，j=l，2，⋯，2N)
维普资讯
9 期 艾军 z多级互连同络互连函数的矩阵理论 9
M) 和 Y(2N ， M)表示:
. X(α2N ，M)=(X.间ρj)'Y(α2N ，M)=[y.间ιj];(k=1 ， 2 ，俨.，….. ， 2N;门j=1 ， 2 ，俨.….. , M) (5)
闯』和 闻』分$剌IJ是输入
值为(仕k ，jρ〉的象素点所对应的;灰度值。当 M
=1 日时才， X(ω2N)λ、 Y(ω2N)均为列向量，其元
素可用来表示网络输入、输出端口的地址
编号。
如果用 Xi 和 Yi 分别表示第 i 级结点庐
的输入、输出图象，参见图 3 ，则有，
node I' tage i+1
2N 2N
X; '(; X忡 Y1+.
Yi=S;Xl (6) s F, 50+,
其中，Si 表示结点的状态，由结点控制 图 3 互连函数矩阵理论原理图
算法决定，作者称之为结点矩阵。
第(i+i)级结点的输入图象(亦即第 i级链路的输出图象))(山可以通过下式由第 i 级结
点的输出图象(亦即第 i 级链路的输入图象) Yi 得到， •·
itXt+;=FiYi 阜、
il
. L :r 、 (7)
其中 Fi 是一个方阵，由网络的互连函数决定，作者称之为互连矩阵.
据(6)和 (7)式可得，
Yi=Si Xi=Si Fi- 1 Yi- 1 (8)
由于第 n 级结点的输出图象1就是网络的输出图象，再利用 (8)和 (6)式，则有
1 ￥(剖，M)二.!=二S平民-1Y'*，斗，二 [iFIStFt止13Y。=[iEISFitI]SoXou e h (9>
对于 Cr佣由ver 和 &nyan 网络(参照图 2) ，第 O 级结点的输入图集就是网络的输入图
象。而对于 0卢g4 网络i结巴级结点的输X图装等于 Omeg严网络的主连矩阵与网络输入图象
的乘积。故有，( ,
fXX2N ~M) ， 10r Cr边s~over'afld Banyari networks (10) 07\0. 不(2N ， M)~ f01 Q~年~~ ~etwork i \, ') (
, 所以只要向道网络的绪J点矩阵和互连桓阵就可以通过:(9)和 q~)式离接由网络的输入图
• 象 X(2N ， M) 计算出相应的输出图象 Y(2N ，M)。结点矩阵由具俺的费曾~;;;'蹦辙口制连接
• 模式要求和所果用的选路算怯(结点控制篝法)决定~.~互连矩阵可以提据持定网络的直连函数
求得。，\二f为~:~ . _t..t
Omega 网络的互连矩阵
由于 Omeia 网络的各级革连函数相园，均为全垠洗互连模式，历引对应的各级互连矩阵
叫 ..: .\T'
也相同，具体形式求得如下 z
r. . . r2í-1 O(川= [pij] , Pij=~ 1 , for j= {2i一 1+[有]}mod 侧
lo , for j=others. (i , j=1 , 2 ,…,2N)
(11)
维普资讯
1998 年
端显可的8·
阵
α
『苟川、种垣
rh
.这少两连牛弘一-叉互川
L1·|lFZ
'tE
卢-'交叉、‘
elo---of
mHM
阳HHMluuh
午
Lt
一、和交
iLMM
I
，二一
--JL·I·
、的、
-Oi---
…叩
问川同问问问问
ωMJh:
←知制
γ
、…···l··
。何
叫叫叫叫川叫叫
UL-
也级
γ
四
}毒
io---01
量
。
opy00007CM刊第
A
「
|-IL
互
0009TOOOU0900oo--·
如制
λ'lι
…斗时山
00100000
出、川互阵卜阵归
100ohh
归
ω
瑜的主川一悍各
OOOOOF-G0
至川应轩'战事
ω-010000OLO
连司对创川分
jJ
刺
制\划单唱可
为00001000
守，"峭的二-具式
阵口归问忡忡忡问
M-MJE--
数
NIl-z
土
矩
=MlJ
函×
uru---sIa
喃
道
XJ
吃进卜
'1
川吕
互
-Mi
互个
JMU
…otto
阳
备的二'种一川归
MYid
m仰
-L+
动4-αμ
满足制
oLO
…宽
咿喇』
he
仇阵如同地
Lo--o
晗
矩盯相
4Jt
n叩幢幢川端川
AU连翩均阳
=qm
8-li
「入吻互直阵数
M=
=;1·mi
翩)揄式的有垣函町、
结连
2
斗端'则明
jt
明模网络互连
=11
于
于气入表连网互氏、
1l||||||
↑」叉
EF
对输。
124567养互交叉直且
阳取二结洗全交
AE
X
该
EA棍全于对μ全
2A
由
r·
口
a
然以
(1 2)
(1 3)
0 .
0. 0. 0.
0. 0. 0.
0. 1 0.
0. 0 0.
0. ，;0.公 o
1 0. 0
0. Q 1
AUAU
咽lhUAUAUAUAU
、、
0. 0.
1 0.
0. 0.
0. 0.
O 币
。 1
，;()，。
0. 0.
、 II~ 型微型计算，机系统10
, r
.
•
•
•
\~，el~ρ‘(};!Q Ot,11, ，~，~ ro 0. O~ 1: 吗lØ，' Q 01; ,'ro. 1 ,0: 0. 0. 0.，。伺
飞1 o' ， O.，o.， Oi~O R-J..PJ rn( 、 ~!010 1 科p ，o. .9. ο'， b :','. 'ì'.ll ,,q 0. 0. 9, 0. q 创)
10 0.'-0 0.飞ò'r o.'o.↑ J 飞， 1'0. 1 '0 σ 0. 0. ô' o.Î 卜. I 0. 0. 0.'1 '0. . () r
11 0. 0. 0. 0. 0. 0. 0. 1 10. 0. 1 0. 0. 0. 0. ' <~ Fo=M=|00;川江I ~可1 7=Ho Q川T冯。叭~J.川l
0. 0. 1 0. 0. 0. 0. 0. I ' I 0. 0. 0. 0. 0. 0. 1 0. I I o.. 0. 0. 0. 1 0.' 0. 0.
0. 1 . 1尸叶 τ) '1 0. o.;'ô" 6' o. í' Ò 0.(1 ' .... ló Ó 00. 0. 0. 0. 1
吁吁吐1 0.￥ ÒQ 1 Ö 0. 'óf '.~ ，、面1O'o"tri ~b 0.' aJ ;'凶。喻。0. o'ni
封3~ i幢树网锚的互连喔酣 在{II:王 "ι 川
13L 辖橱网络的直通直避短阵苟金交卫网络相同i 也是斗二个，NXN\的单位酶午第1 级蝶武互连
链路对应的互连理阵求得为 1
fG j 0. … 0. 1 '，:气\芷卫 l ~ ~~
i市注|干;-yt:1D Tf1i 其中并块是阵。二「EJTi11 A
V V I ~; PV -4 ~，
1 0. …0. G;\
‘ 吨，
(1 5)
(1 6)
F
刊.- ， :11 、
,
lJ
J-
-v
、、
、吨，.马
、
『T-fyl---r ·飞A
",
,
/
9期
E 是一个行、列数均为
4 结论
． -
艾军：多级互连网络互连函数的矩阵理论
、0 ⋯
1 。
．
．
●
-
●
●
⋯ O
譬 誓 阵分 ： ·
r0 1 0 “ 。
l 。。I (17) l 0 0 0 1 l
√
L0勺’1．0．J 一 一 一 ．
本文黜 ． 多级豆连 络互连函数钧矩悔理沧。采用矩侔形式表示多级网络的
不仅可以表示
阵描述网络的
象。文献[3～
典型实验结果
输入、输出
用互连矩
的输出图
络的若干
T ’
-
．
．∞ 、 ．一 一 ：荤 一． 考 衷 -馓 、 ．·、 ． ．
c： t j ，主 实 涤 ≥ 南!}吉 l结构分 ．× 攀 砬 t 一 。 } ，。～ ，一 一
￡2 j ddleh R=Y-’．-一 ul畸 帆 M 自 Prc t驿tuf铎．Oompu~ e~,qarks ls sy敷．，vo1． 27，l 5．1567-1613
c 3’] 艾军 等 榕树网络的互连矩蛑与模拟研壳． 光季学报．14(5)．513—517(1994)
4 冀翠 等． 粕 全受|雯苴连蕾傲酶，1E擎婪现：≯擗 学撼 5( 4) l妫s ‘0 - ， ’ ， ．
5 军 舍 谗 冀耳l酾教的袒 述 应母· 子 ·2s<41i 289—2 l9拿4 ． ，。 ， ‘ L-J ’ 一 ⋯
- L ’ 1’ ． 一 ’一 L 、 · ， ． 、 ． 0
MA鞠 l X雨H叵QR Y；~OF lN 嘞 0NN医0 fo CT I ON：FoR
‘ 1＼习妇 附S1-1AGE，4 ER∞ NNE-CT 下 f0RKS t ：一 ，。、
。 ≯ Sc·i‘enc e an。d—E ~， ， 痞 ；， ； olo g2I 。。。。
Abstract The Multistage Interconnection Net嘧 蓬寸窘f · ‘h rco 一
nectton architecture employed by massive parallel processing systems and large ATM switch-
e s． 嚣 露 盎 nf N s ．by．e瞳r,pr ess-
ro ：LM r 蔷 bf i矗 箍 cribn~undioff 矗 ejl蔷 e l t函 诧’ imultite．"calcu一
,htSto,r ~, e
．rify曲 riment辟 删 t ：opti l 州嘶 tbe．sig f thre~dime,nsional in—
Key w0rds Mu1tistage：
nte
’i'con ct~一br／ rk‘、‘ i n te rcon～n‘ec’t Iriter 0 ne dt ／o II￥ n ’
-
。^ ， 一
一
—．．．．．．．。．．．．． ．．．。．．．．．．．．．．．．．．．．．．L Jl
-_ E
n
且
阵
幺
的
一 ．_
不 一
络 一 网： ＆．
一
千∥ 一 B
如
例
．
鼍 ．
‘、
、 、
-
1
，
一
口 ，
^h ，、
一 t l
1
， ．
、／ I-
，
一
特
一 ，
L
． ，1
． ～
、，
_f． ●
¨
1
j
● ，
【
维普资讯
结论 FJ Jli11?
本立提J血:了::J多绕自主!哥络互连函数的婚阵理怆。采用矩阵形式表示多级网络的输入、输出
不仅可以表示网络J\:.、出端口的地址编号，也可描述三维平面输入4输出图象遍，由于采用豆连短
阵描述网络的互N画数J 因路只言豆豆输X画系， ~p可被rJ(7)式直接计算各级一链路的输出图
象。文献(3-S~ 蜘始阵分别对i叫r高4明晴和全交叉三种常见卷冥连多军网绪的若干
典型实验结果进行了计算任飞 山卢 'l; 飞
串，端口月湾战-式要求和主
国J圄轧 I 将输届国象与输J
的直截用T蜘i询问
h, (.。牛.1 11 .>参，1 带支
(1' jl ，主品是~~I田良量连自结绪街分时响唱出版社‘北京;11归。
i 到 1 :坐飞飞认眩耀盐1明常常器官JtZTfiiT;如92阳 Sy5t. • v叫. . 1567-1613
ι 革'立军等.量4来:&，1 釜发i茸崖散曲也范学实现J 推举字报丁，'15(4).，，1ω5 ' ;:1
口，;其丰货jJ'哼凭串串月伺坪敖的坦问丰~Jt.应时子明叫:m-m圳、
iMA军R IX' i1tHeORY~γOF fU71mCØNNE('Tfj=UN~TI (j)N :FOR
亏 A 自 MtJli:'NtST1AGE .t阳:咱ETWORKS' 了
11
j
/飞.
(17)
··j 、
9 期
101 E; 是→个行、列数均为 2…的生阵，即 E;==" : 二 01
LO … o 1 J 2
例如，对:;F ，宁J~-的榕树阔蝠，不准求虫各级蝶式互远的互连矩阵分别为 z
:有点 Fdbvida;ιf f矿 1 说J;1 气"飞 \ ': \
100011 110001
Bo(4)=1 I ,B,(4)=1
110001 100011
LO 1 0 OJ LO -0 1 'QJ
艾军 z多级互连网络互连函数的矩阵理论
--卢 ..
4
L 牛
、献、
"
:介才 1- _}, .f ~何 .r r 、 飞: l , ì , ;AI" J~fI" 、 乍 λl 川 >.::r (D'''P~;''~1/凹.， 0/ (;;;呻~~~r -S(~i""ce ~，;d E，，~i"~l'r;，;~:'G~，;giio，，~ U;lì~"r.;，~ý-oI1"ech，，0Io~y- G~，;gi:，加'U 510090)
Abstract The Multistage Interconnectìon Nei:特而幅增)::~l:悦e-fOL防i<óc}(，棋协rco~
nectìon archìtecture employed by massìve parallel processìng systems and large ATM swítch-
哈:I口h阜 p归ap盹e盹叩毛P附叩伊s辑叫εed良~t 1;le 1\叫峙4份串飞qwE斗;民圣飞哈P坷啊耳悍y of i均~t吨飞牛r飞呗哩嚼~.~抖T哇~~阳阳P伊归nG;t即ψ肌n f加Q町r Ml则N:呐哥号ν/卢e呻叩阳ress臼s
t山口S" thè1i恤ñput怡g';'0 õùfpJfs:-1~d inte~tòm'l1~'fibn (~n2fioits\){ 由IN~ 'hl ~tl.~ fo~m o( ma't'rltes. The
Pt6pb二~itM崎nx咀\èl9tý bf írtlèf苍白古怪ctibn ,funètfbrl' è'马面 ;be:i (firectly 由:ed slmuläte .calcu-
~% qr, .v:~nfy 白"申ètirnent~l~r，特ut饵of:optic则根卧坠t- yritJ]: tþe_sig~':of t~reeJdí~nsional in-
terconnects
Key words Multmgtin时conhect运川市二址 '6卢IAIjMi卢oAM IriMoJn卢叫rt ktKILti二n
•
, 1如 3 工 4 ￥Al 唱 4
?吃
, . ~ l C" v 斗、民口.‘ "
