Omega网络

✍ dations ◷ 2025-04-02 16:16:12 #网络

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

相关

  • 红霉素红霉素(拉丁语:Erythromycin)是一种大环内酯类的抗生素,可用于治疗呼吸道感染、皮肤感染(英语:skin infections)、衣原体菌感染(拉丁语:chlamydia infections),以及梅毒。本品也可用于
  • 分子演化现代生物分类群体从它们的 共同祖先遗传分化的图示。进化论介绍(英语:Introduction to evolution) 演化的证据 共同起源 共同起源的证据群体遗传学 · 遗传多样性 突变 · 自
  • 瘟神瘟神,或称疫病神,乃东亚民间信仰中的瘟疫之神,各地信仰的瘟神并不一致。中国、朝鲜半岛的瘟神以五福大帝最为著名,即:春瘟张元伯、夏瘟刘元达、秋瘟赵公明、冬瘟锺仕贵、总管中瘟
  • 酸酯.mw-parser-output ruby.zy{text-align:justify;text-justify:none}.mw-parser-output ruby.zy>rp{user-select:none}.mw-parser-output ruby.zy>rt{font-feature-settings:
  • 唐娜·斯特里克兰唐娜·西奥·斯特里克兰(英语:Donna Theo Strickland,1959年5月27日-),加拿大物理学家,是滑铁卢大学物理及天文学院的教授,也是激光物理领域的先驱。她于2018年获得诺贝尔物理学奖,是
  • KindleAmazon Kindle是亚马逊公司设计的一系列电子书阅读器。用户可以通过无线网络使用Kindle购买、下载和阅读电子书、报纸、杂志、部落格及其他电子媒体。亚马逊公司旗下Lab126
  • 第78届奥斯卡金像奖第78届奥斯卡颁奖典礼是美国电影艺术与科学学院旨在奖励2005年最优秀电影的一场晚会,于太平洋时区2006年3月5日下午17点(北美东部时区晚上20点)开始在美国加利福尼亚州洛杉矶好
  • 乐陵郡乐陵郡,东汉末到隋初的郡。汉献帝建安后期,分平原郡厌次、乐陵二县,勃海郡阳信、新乐二县,乐安郡湿沃县置乐陵郡,治厌次城(今山东省惠民县东北),属冀州。辖境在今山东省滨州市一带。
  • 彼得·穆森布罗克彼得·凡·穆森布罗克(荷兰语:Pieter van Musschenbroek,1692年3月14日-1761年9月19日)是一名荷兰科学家。他曾担任杜伊斯堡大学、乌特勒支大学、莱顿大学的教授。他在1746年发明
  • 童受童受论师(梵语:Kumāralabdha,生卒年不详),音译为拘摩罗逻多、鸠摩罗罗陀、鸠摩罗驮、究摩罗陀、鸠摩罗多,意译作童受、童首、豪童、童子。印度部派佛教著名论师,出自说一切有部,与