静态互连网络各种拓扑结构
更新时间:2023-09-20 15:51:01 阅读量: 医药卫生 文档下载
静态互连网络各种拓扑结构
(1)线性阵列 在线性阵列中,
个结点用
条链路连接起来(如下图)。内部
结点度为2,端结点度为1。直径为 ,等分宽度为1,不对称。当 很大时,通信效率很低,
而且可靠性不高。一旦某条链路失效,则系统就不能工作。
(2)环 将一个线性阵列的两端相连就构成一个环。环可以是单向工作的,也可以是双向工作的。双向环因为有两条通路,所以可靠性比单向环更高。环是对称的,结点度为常数2。单向环直径为
,双向环直径为
。
(3)带弦环 在环中不相邻的结点之间加入链路,就得到了带弦环。与环相比,带弦环的结点度大。
结点度为3的带弦环中,链路数为18,直径为4(图中红色结点之间的距离),度为3,不对称,等分宽度为2。结点度为4的带弦环中,链路数为24,直径为3,度为4,对称,等分宽度为8。一般地,结点度越高,直径越短,链路数越多。
(4)链接 链接又称为全连接。它是带弦环的一种特殊情形。链接中的每个结点和其它结点之间都有一条直接链路。下图是8个结点的链接,有28条链路,直径为1,度为7,对
称,等分宽度为16。链接的直径最短,性能最好。但是它需要大量的链路,每个结点需要大量的网络接口,这在实际中是很难实现的,成本也是很高的。
(5)树形和星形 一棵K层完全二叉树有N=2k-1个结点。最大结点度为3,直径为
(即左边任意一个叶子结点到右边任意一个叶子结点),不对称,等分宽度
为1。由于结点度为常数,所以树是一种可扩展的系统结构。
星形实际上是二层树。星形如下图(a)所示,它等价于(b)中的二层树。由N个结点构成的星形网络中,包含N-1条链路,直径为2。根结点的度为N-1,叶子结点的度为1,不对称。
为了弥补其不足,树形结构有许多变形结构,例如带环树和胖树。带环树是在树结构的
基础上,将同级的兄弟结点环状连接起来。这种结构对树结构的改进之处在于减小了网络直径。
传统二叉树的另一个问题是根部容易成为通信瓶颈。这是因为,子结点之间若要通信,都必须通过父结点。这样,越靠近根部的链路和结点通信量就越大。1985年Leiserson提出将计算机科学中所用的一般树结构修改为胖树形(fat tree)。二叉胖树结构如下图所示。
在胖树结构中,结点之间的通路自叶向根逐渐变宽,适应了通信量自叶向根逐渐变大的实际要求。连接机CM-5采用了胖树结构。
(6)网(Mesh) 网又称为网格。在一个
的二维网格中,有N个结点和
条链路。每个结点只与其上、下、左、右的近邻结点相连(边界结点除外)。二
维网格中,结点度为4,直径为
,等分宽度为
。
一般地,在结点数为N=nk的k维网中,内部结点度为2k(每一维上有两个邻居),网络直径为k(n-1)。
网也有多种变形,比如Illiac网和环绕网格。如果把一个网格在各维上都环绕连接起来,就构成环绕网格。下图是一种二维环绕网格(2D-Torus)。
一般说来,
的环绕网格有2N条链路,直径为
,结点度为4,对称。
所有附加的回绕连接使直径较纯网减少一半。如果把一个二维网在一维上环绕连接,另一维上蛇形连接,就构成Illiac网。
一般说来,一个
的Illiac网有2N条链路,直径为
,仅为纯网的直径的
一半。结点度为4。
(7)搏动式阵列(Systolic Array) 搏动式阵列是一类为实现特定的算法而设计的多维流水线阵列结构。下图是完成矩阵-矩阵相乘而专门设计的搏动式阵列,其内部结点度为6。
正在阅读:
静态互连网络各种拓扑结构09-20
长安大学桥梁工程2015届优秀本科毕业设计 - 连续刚构桥 - 图文09-30
半导体蚀刻技术04-02
果实裂果的因素和防治措施05-12
(参考)2019年九年级化学上学期期中试题(含解析) 新人教版3701-07
安全播音稿06-09
救护队安全生产责任制06-27
小升初数学应用题综合训练(含答案)(5)12-13
林业个人工作总结08-23
- 小学五年级数学上册应用题大全123
- 严禁食用野生菌宣传教育活动简报 - 图文
- 2011级1班《文明礼仪》主题班会教案 - 图文
- 喷油器清洗机
- 新员工入职安全培训讲义
- 监狱考试练习题(已做题)
- 张志东购物中心服务品质提升
- JOIN-IN五年级下册单词汇总
- 党校初级培训判断题
- 天眷堂馆藏《古钱币图录--清代第二卷》(康熙雍正)
- 术前预防性应用欧必亭和枢丹对病人PONV发生率的影响
- 九年级物理全册期末复习专题五欧姆定律练习(新版)新人教版
- 中国古代城市城墙史研究综述
- C语言上机题参考答案
- 初中二次函数考题规律
- 中国特殊教育产业规模调查及未来五年投资策略研究报告
- 人教版四年级语文上册生字组词(课文内)
- 液压与气动技术复习题及答案111
- 2018年秋九年级数学上册第二十二章二次函数22.3.1实际问题与二次函数导学案新版新人教版20181210184
- 物流信息系统复习题