Omega网络

✍ dations ◷ 2025-06-29 00:17:35 #网络

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

相关

  • 社会地理学社会地理学是研究各种社会集团的地域分布、差异及其形成过程的一门学科。其侧重于从社会结构的角度阐述和解释社会空间要素。社会地理学起源于20世纪初,发展于第二次世界大战
  • 莓果莓果是一种小的、果肉状的且可经常食用的水果。莓果通常呈现圆形且色泽明亮及光滑,味甜或酸,尽管外表可能附着许多种子或果仁。 常见的例子如草莓、蔓越莓、覆盆子、蓝莓、黑
  • LLM01战术灯及激光模组LLM01(英语:Laser Light Module 01:意为:激光及战术灯模组1型)是一种自适应的目标瞄准辅助模组。由德国施托卡赫的厄利空康特公司所制造。它的设计可以安装于HK G36式突击步枪的
  • 南海各方行为宣言《南海各方行为宣言》或称《南海共同行为宣言》(英语:Declaration on the Conduct of Parties in the South China Sea,简称DOC)由中华人民共和国和东盟10国(10+1)于2002年11月4日
  • 罗杰·费德勒罗杰·费德勒(德语:Roger Federer,德语:.mw-parser-output .IPA{font-family:"Charis SIL","Doulos SIL","Linux Libertine","Segoe UI","Lucida Sans Unicode","Code2000","Gen
  • 杜建时杜建时(1906年-1989年11月7日)字际平,河北省武清县(今天津市武清区)人,中华民国陆军中将,中华民国、中华人民共和国政治人物。1925年,杜建时入位于北京黄寺的奉系开办的东北讲武堂北
  • 克莱·汤普森亚历山大·克莱·汤普森(英语:Alexander Klay Thompson,1990年2月8日-),生于美国加利福尼亚州洛杉矶,美国职业篮球运动员。现效力于NBA球队金州勇士,场上位置为得分后卫。大学时期效
  • 保尔·汉宁森保尔·汉宁森(丹麦语:Poul Henningsen,1894年9月9日-1967年11月31日)是一位丹麦作家、建筑师和评论家。在两次世界大战之间是丹麦文化生活的重要人物。在丹麦,他常被简称作“PH”
  • 邓叔子邓叔子(?-555年),郁久闾氏,为亚洲蒙古一带古国柔然的最后君主,邓叔子是阿那瓌之叔父,那盖的次子。率部居于河套西北,552年,柔然被突厥首领土门所破,阿那瓌被杀。邓叔子于553年3月被西部
  • 脚臭脚臭是指人类脚部的体味,即足部异味,通常被认为是一种令人不快的气味。但作为气味色情的一种形式,它也可能为恋足癖者所喜欢。 足部异味是气味色情的广泛形式之一:在1994的研究