Omega网络

✍ dations ◷ 2025-04-26 13:54:26 #网络

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中.

相关

  • 组织细胞增生症医学中,组织细胞增生(英语:Histiocytosis)是指组织细胞(英语:histiocyte)(组织巨噬细胞)之过量存在;组织细胞增多症或组织细胞增生症常被用来指代一系列以此为特征的罕见病。偶见以此
  • 朱 荻朱荻(1954年5月-),中国制造工程专家。南京航空航天大学教授。生于辽宁沈阳,原籍辽宁沈阳。1978年毕业于南京航空航天大学机械工程系,1981年、1985年先后获该校硕士、博士学位。201
  • 魁北克大学魁北克大学(法语:Université du Québec),加拿大魁北克省的一所综合性大学。魁北克大学于1968年建立,目前拥有超过87,000名学生。按照学生人数统计,是加拿大最大的大学。魁北克大
  • 大卫·戈特利布大卫·戈特利布(英文:David Gottlieb;1911年-1982年),美国植物病理学学家,于1946年至1982年间在伊利诺伊大学香槟分校任职植物病理学教授,他亦是一位在真菌生理学及植物抗生素方面的
  • 热运动热运动是自然界中独立存在的基本运动形式之一,有巨大数量微观粒子(分子、原子、电子或点阵粒子等)参与的永不停息的无规则运动,并伴有频繁碰撞。宏观物质由巨大数量的微观粒子构
  • 高树乡坐标:22°49′35″N 120°36′03″E / 22.8264555°N 120.6007051°E / 22.8264555; 120.6007051高树乡(台湾客家语南四县腔:goˊ su hiongˊ)位于台湾屏东县北方,北临高雄市六龟
  • 潘多利诺潘多利诺(意大利语:Pendolino,pendolo “钟摆”和指小词后缀-ino)是一系列采用主动倾斜式技术的电联车品牌名称,运用于意大利、西班牙、葡萄牙、斯洛文尼亚、芬兰、俄罗斯、捷
  • 张 昭张昭(156年-236年),字子布,徐州彭城(今江苏省徐州市)人,东汉末年东吴名臣;享年八十一岁,死后谥曰文侯。张昭年轻时就以博学出名,深受当地士子敬重,尤其对钻研《汉书》别有心得。徐州刺史
  • 练习曲作品10第12号 (萧邦)练习曲作品10第12号是萧邦的一首练习曲作品。此曲亦被称作革命练习曲,为C小调,2/2拍,火热的快板(Allegro con fuoco)。此曲约写于1831年,献给"我(萧邦)的朋友李斯特·费伦茨"(à s
  • 王林 (作家)王林(1908年-1984年),原名王弢,男,河北衡水人,中国现代作家。1925年赴北京就读中学,1930年入中国共产主义青年团,参加学运遭捕,同年入青岛大学外文系。1931年加入中国共产党,青岛大学地