Omega网络

✍ dations ◷ 2025-04-25 09:10:27 #网络

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

相关

  • H2受体阻抗剂H2受体阻抗剂(英语:H2 antagonist)是一系列用于阻断组织胺作用于胃壁细胞、减少壁细胞分泌胃酸的药物。H2受体阻抗剂用于治疗消化不良,但现在已经有效果更好的氢离子泵阻断剂。
  • 阿古斯塔A129猫鼬型直升机阿古斯塔韦斯特兰A129(AgustaWestland A129 Mangusta)是由意大利阿古斯塔韦斯特兰公司生产的攻击直升机。A129“猫鼬”项目始于1978年,考虑到意大利在北约集体防卫中的地位,主要
  • 罗伯特二世约翰二世罗伯特·斯图尔特 (奥尔巴尼公爵)亚力山大,巴肯伯爵简·斯图尔特凯瑟琳·斯图尔特戴维,凯斯内斯伯爵沃尔特,伯爵的城堡托马斯·斯图尔特 伊莎贝尔·斯图尔特罗伯特二
  • 山毛榉水青冈属(学名:Fagus)又称山毛榉属,为壳斗目山毛榉科的一类植物。广泛分布在亚洲、欧洲与北美洲。也是温带阔叶落叶林的主要构成树种之一。其果实也是一些小型哺乳动物的食物。
  • 家八哥Acridotheres tristis melanosternus Acridotheres tristis naumanni Acridotheres tristis tristis Acridotheres tristis tristoidesParadisaea tristis Linnaeus, 17
  • 刺杀杰西《神枪手之死》(英语:The Assassination of Jesse James by the Coward Robert Ford)是一部2007年美国现代西部电影,由澳洲导演安德鲁·多米尼克(英语:Andrew Dominik)(Andrew Domin
  • 平面 (数学)数学上,一个平面(plane)就是基本的二维对象。直观的讲,它可以视为一个平坦的拥有无穷大面积的纸。多数几何、三角学和制图的基本工作都在二维进行,或者说,在平面上进行。给定一个
  • .kh.kh为柬埔寨国家及地区顶级域(ccTLD)的域名。A .ac .ad .ae .af .ag .ai .al .am .ao .aq .ar .as .at .au .aw .ax .az  B .ba .bb .bd .be .bf .bg .bh .bi .bj .bm .bn
  • 夜色人生《夜色人生》(英语:,港台译《夜行人生》)是一部于2016年上映的美国犯罪剧情电影,由本·阿弗莱克执导、编剧和监制,剧情改编自丹尼斯·勒翰的2012年同名小说。该片主要讲述美国黑帮
  • 素数倒数幻方素数倒数幻方(prime reciprocal magic square)是指用素数倒数及其倍数的循环小数各位数组成的幻方。有些素数的倒数则可以形成对角线和也满足条件的幻方。考虑在十进制下的1/7