计算机体系结构 第7章.PPT
循环移数网络通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成。N=16结点度:7直径:27.2互连网络的结构一般地,如果|j-i|=2r(r=0,1,2,…,n-1,n=log2N),则结点i与结点j连接。结点度:2n-1直径:n/27.2互连网络的结构树形和星形一棵5层31个结点的二叉树一般说来,一棵k层完全平衡的二叉树有N=2k-1个结点。最大结点度:3直径:2(k-1)星形结点度较高,为N-1。直径较小,是一常数2。可靠性比较差,只要中心结点出故障,整个系统就会瘫痪。7.2互连网络的结构7.2互连网络的结构胖树形7.2互连网络的结构网格形和环网形网格形一个3×3的网格形网络一般来说,N=nk个结点的k维网络的内部结点度是2k,网络直径为k(n-1)。环形网可看作是直径更短的另一种网格。将环形和网格形组合在一起,并能向高维扩展。沿阵列的每行和每列都有环形连接。一个n×n二元环网结点度:4直径:2×?n/2?7.2互连网络的结构7.2互连网络的结构超立方体一种二元n维立方体结构一般来说,一个二元n维立方体由N=2n个结点组成,它们分布在n维上,每维有两个结点。例8个结点的3维立方体4维立方体为实现一个n维立方体,只要把两个(n-1)维立方体中相对应的结点用链路连接起来即可。共需要2n-1条链路。n维立方体中结点的度都是n,直径也是n。7.2互连网络的结构8.带环立方体(CCC)一个带环n-立方体,由N=2n个结点环构成,每个结点环是一个有n个结点的环,结点总数为n*2n个。直径通常为2n,结点度为3,对称。带环3-立方体7.2互连网络的结构静态互连网络一览表网络类型结点度d网络直径D链路数l等分宽度B对称性网络规格说明线线阵列2N-1N-11非N个结点环形2[N/2]N2是N个结点全连接N-11N(N-1)/2(N/2)2是N个结点二叉树32(h-1)N-11非树高h=[log2N]星形N-12N-1[N/2]非N个结点2D网格42(r-1)2N-2rr非r×r网格,Illiac网4r-12N2r非与的带弦环等效2D环网42[r/2]2N2r是r×r网格,超立方体nnnN/2N/2是N个结点n=[log2N]CCC32k-1+[k/2]3N/2N/(2k)是N=k×2k结点环长k≥37.2互连网络的结构总线实际上是一组导线和插座,用于进行与总线相连的处理机、存储模块和外围设备等之间的数据传送。每一次总线只能用于一个源(主部件)到一个或多个目的(从部件)之间的数据传送。多个功能模块之间的争用总线或时分总线。特点价格低带宽较窄7.2.2动态互连网络7.2互连网络的结构一种由总线连接的多处理机系统*/55▲第7章互连网络7.1互连网络的基本概念7.2互连网络的结构互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络,用来实现计算机系统中结点之间的相互连接。结点:处理器、存储模块或其他设备。在拓扑上,互连网络为输入结点到输出结点之间的一组互连或映象。互连网络在系统中的位置,如下页图所示。7.1互连网络的基本概念7.1.1互连网络的功能和特性7.1互连网络的基本概念互连网络在系统中的位置7.1互连网络的基本概念可以从4个不同的方面来描述互连网络定时方式:有同步和异步两种。同步系统:使用一个统一的时钟。SIMD阵列处理机就属于这一种类型。异步系统:没有统一的时钟,系统中的各个处理机都是独立地工作。交换方法:有线路交换和分组交换两种。线路交换:源结点和目的结点之间的物理通路在整个数据传送期间一直保持连接。分组交换:把信息分割成许多组(又称为包),将它们分别送入互连网络。7.1互连网络的基本概念这些数据包可以通过不同的路径传送,到达目的结点后再拼合成原来的数据。结点之间不存在固定连接的物理通路。控制策略:有集中式和分散式两种集中控制方式:有一个全局的控制器接收所有的通信请求,并由它设置互连网络的开关连接。分散控制方式:不存在全局的控制器,通信请求的处理和开关的设置由互连网络分散地进行。7.1互连网络的基本