Omega网络

✍ dations ◷ 2025-07-06 09:51:44 #网络

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

相关

  • 5’端帽5′端帽(Five-prime cap)是在真核生物中信使RNA(mRNA)的5′端经修改后形成的的双核苷酸端点。5′加帽的过程对建立成熟的mRNA作翻译非常重要。加帽确保了mRNA在蛋白质生物合成
  • 石滩石滩可以指:
  • 拉腊马里亚诺·何塞·德·拉腊因(Mariano José de Larra)(1809年3月24日-1837年2月13日)是西班牙浪漫主义作家,最出名的是杂文。他最后自杀身亡。马里亚诺·何塞·德·拉腊因的作品往
  • 阿伊努族109–1000阿伊努族(阿伊努语:Aynu),是日本北方、俄罗斯东南方的一个原住民族群,或译爱努人、爱奴人、阿衣奴人),主要聚居在库页岛和北海道、千岛群岛及堪察加1。在阿伊努语中,“阿伊
  • 葛优葛优(1957年4月19日-),河北饶阳人,中华人民共和国一级演员,现任中国电影表演艺术学会第十四届会长、中华全国总工会文工团名誉团长,享受国务院政府特殊津贴。1993年凭借电影《大撒
  • 反共产国际协定反共产国际协定 (又称防共协定,德语:Antikominternpakt,日语:防共協定)是纳粹德国与大日本帝国在1936年11月25日签订的反对共产国际及苏联的协定。此协定后来陆续有其他国家加入。
  • 国树国树是指代表一个国家的树,并不是所有国家都有国树,也有些国家的国花与国树相同。
  • 普定县普定县位于贵州省中部偏西,隶属安顺市,东与安顺市西秀区、开发区、平坝区比邻,南与镇宁县、六枝特区相接,西靠六枝特区,北抵织金县。普定县城距安顺28公里,距贵阳118公里。普定县
  • 2014年国际足联世界杯外围赛 – 欧洲区F组2014年世界杯外围赛欧洲区F组(英语:2014 FIFA World Cup qualification UEFA Group F)是欧洲足协辖下2014年世界杯欧洲赛区外围赛的一个分组,包括葡萄牙、俄罗斯、以色列、北爱
  • 百鬼夜行百鬼夜行(ひゃっきやぎょう、ひゃっきやこう)是流传在日本民间传说中出现在夏日夜晚的妖怪大游行,也是著名妖怪绘师鸟山石燕一系列的妖怪绘卷(参见画图百鬼夜行:115)。当代因日本