Omega网络

✍ dations ◷ 2025-04-04 11:24:38 #网络

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

相关

  • 约瑟夫·诺曼·洛克耶约瑟夫·诺曼·洛克耶(英语:Joseph Norman Lockyer 1836年5月17日-1920年8月16日)英国科学家、天文学家,与法国科学家皮埃尔·让森一同发现了氦气。科学期刊《自然》创始人和首
  • 克拉伦斯·沃尔顿·李拉海克拉伦斯·沃尔顿·“沃尔特”·李拉海(英语:Clarence Walton "Walt" Lillehei,1918年10月23日-1999年7月5日),美国外科医生,心内直视手术的先驱开创者之一,被称作“心内直视手术之
  • 监护人监护人是指一个人在未成熟、经验不足或社会认为需要受监护的情况下对其进行指导和监督的人,尤其指避免监护对象行差踏错者。监护人不一定有法律地位。但一些政治人物的监护人
  • 宣战宣战是指一个国家宣告该国与其他(可多于一个)国家处于战争状态。文艺复兴时,已有国家作出正式的宣战声明,自此,民主国家已接受宣战作为一个外交手段。在国际法中,宣战声明代表该等
  • 詹森多面体约翰逊多面体,有译作约翰逊多面体或庄逊多面体,是指正多面体、半正多面体、棱柱、反棱柱之外,所有由正多边形面组成的凸多面体。这些立体由诺曼·约翰逊(英语:Norman Johnson (ma
  • 旧金山缆车系统旧金山缆车系统(英语:San Francisco cable car system)是旧金山市内的缆索铁路交通系统,是历史最悠久的循环式缆索铁路交通系统,也是旧金山城市铁路系统的一部分。旧金山缆车系统
  • 赣文化赣文化,指赣地从古至今所创造的物质文明和精神文明的所有成果。赣文化在上古时代脱胎于越文化、吴文化,在两千多年中不断和中原文化融合,最终发展成。赣文化经常以“文节俱高”
  • 各国互联网使用者数目列表以下是截至2017年互联网用户数量的国家列表。互联网用户定义为过去12个月内从任何设备(包括移动电话)访问互联网的人员。 注1:渗透率是每个国家/地区中互联网用户占总人口的百
  • 扎因·艾沙拉夫扎因·艾沙拉夫王后(阿拉伯语:زين الشرف بنت جميل‎,英语:Queen Zein al-Sharaf,1916年8月2日-1994年4月26日),是约旦第二任国王塔拉勒·伊本·阿卜杜拉的妻子及王后
  • 印尼鸡汤印尼鸡汤(印尼语:Soto ayam)是一种黄色、带香辣的鸡汤,内有隆东饭(或称马来粽)、粉丝或面条。流行于印尼、新加坡、马来西亚和苏里南。在汤中加入姜黄为汤水带来黄色。这是印尼菜