Omega网络

✍ dations ◷ 2025-07-31 08:30:07 #网络

Omega网络是一种常用于并行计算架构的网络配置。它是一个依赖于完美洗牌互联算法的非直连拓扑。

一个8x8的Omega网络是一个多级互联网络,这意味着处理单元(英语:processing element,简称PE)是由多级交换机互联的。如上图,输入和输出标好了地址。每一级的输出和下一级的输入用一个完美洗牌系统(英语:Faro shuffle)连接起来,这意味着每个级间互联都仿佛是一叠扑克牌划分为数量相等的两叠然后洗牌洗到一起,一张来自一组的牌叠在一张来自另一组的牌上。如果我们考虑用二进制表示PE,那么每级的完美洗牌可以看作是一个循环逻辑左移位,地址中的每个位每次向左移一位,把最高位放置到最低位上。

在每一级上,相邻的一对输入被连接在一个简单的互换单元上,这个单元可以选择直通(英文:straight,也就是把输入直接传送到输出)也可以选择交叉(英文:crossed,也就是把上面的输入放到下面输出,把下面的输入放到上面输出)。对于 N {\displaystyle N} 个处理单元,一个Omega网络的每一级有 N / 2 {\displaystyle N/2} 个交换机,共有 log 2 N {\displaystyle \log _{2}N} 级。这些交换机的配置决定了网络在任意时间的通路的可用状态,配置方法有两种,分别为目的地标签路(英语:destination-tag routing)由和XOR标签路由(英语:XOR-tag routing)。

Omega网络是高阻塞的,然而在一个自由网络里对于任意一对输入输出总能找到一条路由。

在目的地标签路由中,交换机的配置完全按照要传递的消息的目的地决定。目的地地址的最高位被用来选择第一级交换机的输出口:如果最高位时0,那么选择上面的输出口;如果最高位是1,那么选择下面的输出口。第二高位被用来选择第二级交换机的输出口,依此类推直到到达最终的输出。

例如,如果一条消息的目的地是PE 001,那么交换机的配置为:上,上,下。如果一条消息的目的地是PE 101,那么交换机的配置为:下,上,下。这些交换机的配置不考虑输入的地址。

在XOR标签路由中,交换机的配置基于 (源PE地址) XOR (目的地PE地址)。这样生成的一个XOR标签包含的1的位置意味着地址在这一位上必须要被反转,而0的位置意味着源PE地址和目的地PE地址在这一位是相同的。XOR标签的最高位被用来设置第一级路由:如果它是0,则交换机选择直通;如果它是1,则交换机选择交叉。第二高位被用来选择第二级交换机的输出口,依此类推直到到达最终的输出。

例如,如果PE 001想发消息给PE 010,那么XOR标签位011,交换机配置为:A2直通,B3交叉,C2交叉。

在多处理器处理中,Omega网络可以被用来连接CPU和共享内存从而降低CPU到内存的连接成为瓶颈的概率。

Omega网络已被应用于Illinois Cedar Multiprocessor、IBM RP3和NYU Ultracomputer中.

相关

  • 埃莱夫西纳埃莱夫西纳(希腊语:Ελευσίνα;现代希腊语:.mw-parser-output .Polytonic{font-family:"SBL BibLit","SBL Greek","EB Garamond","EB Garamond 12","Foulis Greek",Cardo,
  • 司马迁司马迁(前145年-约前86年),字子长,龙门(今陕西韩城)人,是西汉时期著名的史学家和文学家。司马迁所撰写的《史记》被公认为是中国史书的典范,首创的纪传体撰史方法为后来历代正史所传
  • 塔毛利帕斯州塔毛利帕斯州 (西班牙语:Tamaulipas)是墨西哥东北部的一个州。面积79,384平方公里,人口3,024,238(2005.10.17)。坐标:24°17′14″N 98°33′48″W / 24.28722°N 98.56333°W / 24
  • 芮妮·齐薇格蕾妮·凯丝琳·齐薇格(英语:Renée Kathleen Zellweger,1969年4月25日-),美国女演员,生于得克萨斯州休斯顿郊区的卡地镇。她获得多个赞赏及奖项,包括两座奥斯卡金像奖、两座英国电影
  • 抚松抚松县是中国吉林省白山市下辖的一个县。县政府驻抚松镇。长白山机场建于县境内。清宣统元年十月二十日(1909年12月2日),东三省总督锡良、奉天巡抚程德奏请,拟在长白山岗后设县
  • 如梅利堡垒如梅利堡垒(Rumelihisarı)位于土耳其伊斯坦布尔的萨勒耶尔区,博斯普鲁斯海峡最狭窄处的欧洲一侧的小山上。它由奥斯曼帝国苏丹穆罕默德二世兴建于1452年,征服君士坦丁堡之前。
  • Hofele-DesignHOFELE-Design有限公司(英语:HOFELE-Design GmbH)于1983年在德国格平根区德茨道夫成立,是梅赛德斯-奔驰专业汽车改造公司。该公司亦是SAE International所认可之汽车制造商,并获
  • 维克托·马克西莫维奇·戈卢别夫维克托·马克西莫维奇·戈卢别夫(俄语:Виктор Максимович Голубев,1915年1月17日-1945年5月17日),苏联空军飞行员。苏联英雄。1915年1月17日出生于彼得格
  • 锺利俗钟利俗,隋末岷山羌人。617年四月初三,薛举和他的儿子薛仁果胁迫金城县令郝瑗发兵反隋,自称西秦霸王,改年号秦兴。他封薛仁果为齐公,幼子薛仁越为晋公。宗罗睺率部众归附,被封为义
  • 韩百谦韩百谦(朝鲜语:한백겸,1552年-1615年)是朝鲜王朝中期的文臣和学者。本贯淸州韩氏,字鸣吉(명길),号久菴(구암)。在任期间主持实施新收米法。新收米法首先在京畿道推行,规定以前向宫房