．-
■
●
第 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网络·
维普资讯
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，
●
●
■
●
维普资讯
●
’
-
●
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期
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
● ，
【
维普资讯
