系统结构重点

1.1.1计算机系统的层次结构微程序机器级传统机器语言机器级操作系统机器级汇编语言机器级高级语言机器级应用语言机器级

从计算机语言的角度，可将通用计算机系统划分成多级层次结构，每一层以一种不同的语言为特征。

按由低层到高层的顺序，各层分别是：1.低层机器级对高层机器级的支持

各层机器级语言的功能是依靠下一层机器级的支持才能实现的，而且，这种支持要满足透明性要求。

透明性：从计算机系统的某一层的使用者角度看，只需通过该层的语言就可以使用机器，而不必关心其下层的机器级是如何工作和如何实现对上层的支持的。

计算机系统的“透明”是看不到的意思，即对某一层的使用者来说，他看不到该层以下各层的机器属性。1.发展计算机系统并行性的技术途径

可以通过3类技术途径来提高计算机系统的并行性，这就是时间重叠、资源重复和资源共享。

时间重叠是在并行性概念中引入时间因素，让多个处理过程在处理时间上错开，轮流重叠地使用同一套硬件设备的各个部件，提高多个处理过程的并发性。

资源重复是在并行性概念中引入空间因素，通过重复设置硬件资源分别同时用于多个处理过程，实现多个处理过程的同时性。

资源共享是利用软件方法让多个任务按一定顺序轮流使用一套资源，通过提高系统资源利用率来提高系统的性能和效率。

3.计算机系统结构的分类

指令流：是指机器执行的指令序列。数据流：是指由指令流调用的数据序列，包括输入数据和中间结果。多倍性:是指在系统最受限制的部件上，同时处于同一执行阶段的指令或数据的最大可能个数。Flynn按指令流和数据流的多倍性对计算机系统结构进行分类:单指令流单数据流（SISD）体系结构

单指令流多数据流（SIMD）体系结构

多指令流单数据流（MISD）体系结构

多指令流多数据流（MIMD）体系结构浮点数的机器字的格式为：

mfefem1位1位q位p位

其中mf为尾数符号位，ef为阶码的符号位。

mfefe(q)m(p)浮点数在数据存储单元中的存放方式mf:尾数符号ef:阶码符号e:阶码长度m:尾数的值。尾数用原码、纯小数表示，阶码用移码、整数表示。浮点数的表示范围定义为：P=23,q=7,rm=re=2,浮点数N的表示范围：绝对值不能无穷接近0值，即存在截止区(dead-zone),也叫下溢区十进制数0.1的16位多种表示方式尾数的值阶符阶码尾符尾数rm=2010101100,1100,1100,1100rm=40111001,10,01,10,01,10,01,10rm=801110110,011,001,100,110,0rm=16100000001,1001,1001,1001(阶码的基)阶码位数+阶码值(-8~7)=阶码的移码值(0~15)0.1(10)=0.1100110011001100(2)×2-3=0.121212(4)×4-1=0.63146314(8)×8-1=0.19999(16)×160浮点数的表数(representation)精度阶码(阶码的移码),q=1,rm=21(1.1)0(1.0)-1(0.1)-2(0.0)尾数p=2rm=20.75(0.11)3/2¾3/83/160.5(0.10)1½¼1/8-0.5(1.10)-1-1/2-1/4-1/8-0.75(1.11)-3/2-3/4-3/8-3/16(阶码的基)阶码位数+阶码值(-2~1)=阶码的移码值(0~3)若有2个浮点数a1=1/2,b1=3/4,a1+b1=5/4，不在这个浮点数集里面，因此必须用靠近这个数的值表示，如1或者3/2。由此产生表数误差。阶码尾数由于因此，能表示的绝对值最大的浮点可近似为：假设有2种浮点数表示方法F1和F2：F1:尾数的基为2，阶码的长度为q1；F2:尾数的基为，阶码的长度为q2，并设：；两种浮点数表示方式的表示范围为：尾数的基从2增加到，所能表示的阶码最大值就增加倍，而浮点数的表数范围，是根据其阶码增加以2的指数增加:q1=7,rm1=2；q2=6,rm2=16；T=2128尾数的基与表数范围2.2.1操作码优化设计1.操作码优化编码的方法

定长（等长）编码哈夫曼编码扩展编码

操作码编码的方法有3种：

定长编码:是指所有指令的操作码长度都是相等的。如果需要编码的操作码有n个，那么，定长操作码的位数最少需要|log2n|位。

使用哈夫曼算法构造哈夫曼树来进行编码。哈夫曼（Huffman）编码

构造哈夫曼树的方法是：每次从结点集中选择出2个频度最小的结点，将其合并成频度为这两个频度之和的父结点，若结点集不为空集，就将生成的新结点放到结点集中，继续从这个新的结点集中选择出2个频度最小的结点生成其父结点，直至结点集成为一个空集，就生成了一棵哈夫曼树。对每个结点的两个分支分别用“0”和“1”标识，从根结点到一个叶结点的路径（由0和1组成的序列）就是这个叶结点的哈夫曼编码。

限定使用少数几种码长，频度高的码点用短码表示，频度较低的码点用长码表示。特别需要指出的是，任何短码都不能是任何长码的前缀，即任何短码都不能是任何长码的前若干位，否则会造成解码的不惟一性。因此，需要留下若干个短码作为长码的扩展标志，以便长码在扩展编码时使用。

扩展编码一种称为码长表示法，用短横线前后的数字分别表示短码码长和长码码长。另一种称为码点数表示法，用斜线前后的数字分别表示短码码点个数和长码码点个数。

扩展编码有2种表示方法：

2.操作码优化编码的评价方法用平均码长来评价编码优化的程度，平均码长为：其中，pi是码点i的使用频度；li是码点i

的编码长度。也可以用位冗余量来衡量编码优化的程度，位冗余量为

：其中，H称为信息熵，，表示用二进制编码表示n个码点时，理论上的最短平均编码长度。因此，任何实际编码得出的平均码长l都有l>H，故有0<R<1。

3.2.2线性流水线的性能计算1.吞吐率

流水线的吞吐率是指流水线单位时间输出结果的数量。（1）各段执行时间相等的吞吐率若一条k段线性流水线，各段执行时间相等，均为，当有n个处理对象连续流入流水线时，流水线的工作过程可用时空图表示为：nn-1……321S1nn-1……321S2nn-1……321S3nn-1……321S4时间空间

各段执行时间均相等的流水线时空图：

流水线的实际吞吐率为：

最大吞吐率为：最大吞吐率与实际吞叶率的关系是：只有当n>>k时，即连续输入流水线的处理对象数n远大于流水线的段数k时，实际吞吐率TP才接近于最大吞吐率TPmax。

（2）各段执行时间不等的吞吐率若一条k段线性流水线，各段执行时间,,…,不相等，那么，除第一个对象外，其余(n-1)个对象必须按瓶颈时间间隔max(,,…,)连续流入流水线。

消除流水线的瓶颈段，以提高流水线吞吐率的方法有两种：①分离瓶颈段:把流水线中的瓶颈功能段分离成为几个独立的子功能段，消除各段执行时间的“瓶颈”。②重复设置瓶颈段:如果瓶颈功能段由于实现技术等方面的原因难以分离成几个独立的子功能段，那么，可以采用重复设置瓶颈段，让多个瓶颈段并行工作来消除瓶颈段原执行时间的“瓶颈”。这两种方法只要完全消除了“瓶颈”，提高吞吐率的程度是相同的。

2.加速比

流水线的加速比:是指使用顺序处理方式处理一批对象所用的时间与流水线使用流水处理方式处理同一批对象所用的时间之比。（1）各段执行时间相等的加速比一条各段执行时间均为的k段线性流水线，若有n个对象连续流入，那么，流水线流水处理这n个对象所用的时间为。若顺序处理这n个对象，则所用时间为。

实际加速比为:最大加速比为:（2）各段执行时间不等的加速比当流水线各功能段的执行时间不相等时，一条k段线性流水线完成n个连续输入的对象的实际加速比为

3.效率

流水线的效率:是指流水线的设备利用率。它是流水线各段的有效工作时间之和与流水线各段被占用时间（从第一个对象流入至最后一个对象流出）之和的比值。

可以由时空图直观地计算出流水线的效率为

（1）各段执行时间相等的效率各段执行时间相等的流水线效率为：最大效率为：（2）各段执行时间不等的效率各段执行时间不等的k段线性流水线连续输入n个对象的流水线效率为：【例3.4】

有一个5段单功能非线性流水线，每一个功能段的执行时间均为。处理对象在流水线中的处理过程由表3.1给出的预约表描述。预约表中的记号“

”表示处理对象在指定的时间（单位为）需要由相应的段进行处理。求流水线的最优调度策略。若按此最优调度策略连续输入8个对象，计算流水线的实际吞吐率、加速比和效率。

表3.15段单功能非线性流水线的一种预约表

S5

S4

S3

S2

S1987654321时间段解按下述步骤先求出最优调度策略，然后求实际吞吐率、加速比和效率。①由预约表得出禁止表F，禁止表是后续对象禁止流入流水线的时间间隔的集合。由表3.1给出的预约表可见，一个对象在1使用段S1后，在9将再次使用段S1。为避免后续对象同该对象发生争用段S1的冲突，后续对象禁止流入的时间间隔为9-1=8

。同样，为避免争用段S2的禁止时间间隔为；为避免争用段S3的禁止时间间隔为、

、；为避免争用S4的禁止时间间隔为；为避免争用S5的禁止时间间隔为。由此，可得出禁止表F={8,4,3,1}。②由禁止表得出初始冲突向量

C0=(10001101)。3-2=17-4=38-4=48-7=15-4=17-6=1③由初始冲突向量得出状态有向图。

初始状态为C0=(10001101)，C0有4个后继状态：C1=SHR(2)(C0)∨C0=(00100011)∨(10001101)=(10101111)C2=SHR(5)(C0)∨

C0=(00000100)∨(10001101)=(10001101)=C0C3=SHR(6)(C0)∨

C0=(00000010)∨(10001101)=(10001111)C4=SHR(7)(C0)∨

C0=(00000001)∨(10001101)=(10001101)=C0

C1有2个后继状态：C5=SHR(5)(C1)∨

C0=(10001101)=C0C6=SHR(7)(C1)∨

C0=(10001101)=C0C3有3个后继状态

：

C7=SHR(5)(C3)∨

C0=(10001101)=C0C8=SHR(6)(C3)∨

C0=(10001111)=C3C9=SHR(7)(C3)∨

C0=(10001101)=C0（10001101）（10101111）（10001111）257756657C0C1C3④表3.2图状态有向图的调度策略

(2+5)/2=3.55(7)(6)(6,7)(6,5)(5)(2,7)(2,5)平均时间间隔调度策略(2+7)/2=4.5(6+5)/2=5.5(6+7)/2=6.567⑤计算最优调度策略的流水线吞吐率、加速比和效率。最优调度策略（2,5）的平均时间间隔为3.5，可得出最优调度策略的流水线最大吞吐率为：

TPmax=1/3.5=0.286/

按最优调度策略流水处理8个对象所需时间为由于每一个对象的处理过程所需时间为9，所以，若按顺序处理方式处理8个对象，所需时间为

可得出按最优调度策略流水处理n=8个对象时，流水线的实际吞吐率、加速比和效率分别为【例3.6】

有一个5段单功能非线性流水线，每一个功能段的执行时间均为，处理对象在流水线中的处理过程由例3.4中的表3.1给出的预约表描述。（1）求流水线的最优调度策略和最大吞吐率。（2）若按最优调度策略连续流入6个对象，计算流水线的实际吞吐率、加速比和效率。（3）画出按最优调度策略连续流入6个对象的时空图，并由时空图计算流水线的实际吞吐率、加速比和效率。

解（1）因为处理对象的预约表相同，所以，流水线的最优调度策略即例3.4中求得的最优调度策略(2,5)。流水线的最大吞吐率就是最优调度策略的最大吞吐率，有TPmax=1/3.5。

（2）按最优调度策略连续流入6个对象，流水线的实际吞吐率和加速比分别为:由表3.1给出的预约表可见，一个处理对象在流水线中被流水线5个段实际处理的时间之和为(2+2+3+2+2)=11，所以，流水线5个段处理6个对象的实际处理时间之和为6×11=66。流水线5个段共被占用的时间之和为5×25=125。因此，流水线的效率为

654635241321S1665544332211S2665565443343221121S3665544332211S4665544332211S52Δt5Δt2Δt5Δt2Δt9Δtt(Δt)例3.6的时空图

由时空图得出流水线的实际吞吐率、加速比和效率分别为：

3.4流水线的相关问题与相关处理流水线的相关问题分为局部相关和全局相关两类。局部相关对程序执行过程的影响较小，它仅涉及到相关指令前后的一条或几条指令的执行。全局相关是指影响整个程序执行方向的相关，主要是转移类指令和中断引起的相关。3.4.1局部相关及处理

1.顺序流动的“先写后读”相关及处理顺序流动是指对象从流水线流出的次序同它们流入流水线的次序一样。如果指令h写入结果的目的地址同指令j读取操作数的源地址是同一个存储单元或寄存器，那么，称这两条指令有“先写后读”的要求。如果当指令j到达读段时，指令h还没有到达写段完成写入操作，那么，指令j读出的数据就是错误的，这就是“先写后读”相关。解决顺序流动的“先写后读”相关的方法是：延迟、异步流动和建立相关通路。3.4.2全局相关及处理

由条件转移或程序中断引起的相关称为全局相关。1.条件转移的处理在遇到条件转移指令时，为了使流水线不“断流”，通常采用“猜测法”，即在条件转移指令之后，选择一个分支方向，让后续指令进入流水线执行。假设在一般程序中条件转移指令所占比例为p，转移成功的概率为q，那么，对于一个由n条指令组成的程序在执行过程中，由于条件转移需要额外增加的执行时间就是pqn(k-1)。包括条件转移指令在内的n条指令的总的执行时间是可得出有条件转移影响的流水线的吞吐率为

当时，有条件转移影响的流水线的最大吞吐率为由于条件转移指令的影响，流水线吞吐率下降百分比为

由于条件转移指令对流水线的性能影响很大，必须采取措施来减小这种影响。可以采取的措施主要有以下几种。（1）延迟转移技术（2）静态转移预测技术（3）动态转移预测技术（4）提前形成条件码2.中断处理在顺序处理方式中，CPU任何时间都只执行一条指令，当中断发生时，被中断执行的那一条指令即是断点指令，被中断的指令的现场即是要保护的中断现场。在指令流水线中，同时有多条指令被执行，每一条指令在流水地执行过程中都不断地改变着现场。对此，有两种处理方法。

（1）不精确断点方法不精确断点方法对中断的处理是：凡是已经进入流水线的指令序列的指令都执行完成，断点指令就是该指令序列中最后进入流水线的那条指令。实际上，提出中断请求的指令可能并不是最后那条指令，所以称其为不精确断点法。这个方法只确定最后一条指令为断点指令，只保存这一条指令的现场。（2）精确断点方法精确断点方法对中断的处理是：对于在流水线中同时执行的多条指令，由哪一条指令的程序性错误或故障发出的中断申请，断点指令就是这条指令。为了实现精确断点法，需要把断点指令之前尚在流水线中已完全执行和部分执行的指令的执行结果都作为现场保存起来，为此，要设置一定数量的后援寄存器。3.4.3相关对流水线性能的影响

流水线处理对象之间的相关将导致流水线的性能下降。对于有相关问题的处理对象序列，可以用时空图来表示流水处理过程和分析相关对流水线性能的影响。3.5多发射处理机及其性能

单发射是指处理机在一个时钟周期（）只从存储器取出一条指令（IF）、只对一条指令译码（ID）、只执行一条指令（EX）和只写回一个运算结果（WR），因此，平均一个时钟周期只解释一条指令。单发射处理机的指令级并行度ILP<1。多发射是指处理机在一个时钟周期可发射多条指令。多发射处理机的指令级并行度ILP≥2。属于多发射处理机范畴的处理机有：超标量处理机、超流水处理机、超标量超流水处理机和超长指令字处理机。3.5.1超标量处理机及其性能计算

超标量处理机是在单发射处理机的基础上，采用资源重复的途径来发展指令流水线的并行性，通过重复设置硬件资源来提高处理机的指令级并行度。1.超标量处理机指令流水线的结构

3.5.2超流水处理机及其性能计算

超流水处理机是在单发射处理机的基础上，采用时间重叠的途径来发展指令流水线的并行性，通过把单发射的指令流水线各功能段进一步细分来提高处理机的指令级并行度。指令流水线平均执行一条指令所需要的时间称为流水线周期，单发射指令流水线的流水线周期就是时钟周期，超流水指令流水线的流水线周期为/n，在没有相关和段资源冲突的理想情况下，超流水处理机的指令级并行度ILP=n。3.5.5多发射处理机的性能比较机器类型单发射处理机超标量处理机超流水处理机超标量超流水处理机流水线周期1个时钟周期1个时钟周期1/n时钟周期1/n时钟周期同时发射指令条数1条m条1条m条指令发射等待时间1个时钟周期1个时钟周期1/n时钟周期1/n时钟周期指令级并行度ILP1mnm×n表3.64种不同类型处理机的性能比较【例3.12】

在向量流水处理机上，执行下述3条向量指令来计算向量D=A×(B+C)，其中，结果向量D的元素di=ai×(bi+ci)，i=1，2，…，N。N为向量元素个数。①V3←存储器 ；访存取A送入向量寄存器V3②V2←V0+V1 ；B+C→K③V4←V2*V3 ；K*A→D设启动存储器、启动乘/加流水线、数据打入寄存器各需时，向量加流水线完成一次加法需时6，访存一次需时6，向量乘流水线完成一次乘法需时7。求出分别采用下列3种方式工作时，完成3条向量指令所需的时间。（1）3条指令依序串行。（2）指令①与指令②并行执行完后，再执行指令③。（3）采用指令链接技术解（1）计算3条向量指令各自单独流水执行时所需时间。向量指令V3←存储器所需流水线建立的时间为启动存储器所需时钟周期数，即有s1=1；访存取向量A并打入向量寄存器V3中，以及流水操作打入A的第一个元素所需时钟周期数为6+=7，即e1=7；完成向量A其余N-1个元素的打入所需时钟周期数为(N-1)。因此，该向量指令单独流水执行所需时间向量指令V2←V0+V1单独流水执行所需时间向量指令V4←V2*V3单独流水执行所需时间因此，3条指令之间串行执行，共需时间

（2）由于指令①和指令②同时并行，所需时间，然后执行指令③，因此，共需时间（3）由于指令①与指令②之间既无向量流水线资源冲突（前者使用访存流水线，后者使用向量加流水线，二者之间无资源冲突），又无向量寄存器的先写后读相关，因此，这2条指令是一个编队，可以同时并行执行。但是，指令③与指令①之间有寄存器V3的先写后读相关，与指令②之间有寄存器V2的先写后读相关，因此，指令③是另一个编队。可以在编队之间采用链接技术，即可把指令①和指令②同时并行的流水线流出的结果向量元素直接流入指令③的流水线。指令①流水线与指令②流水线同时并行执行，流出第一对元素的时间为，因此，共需时间4.2.2低位交叉编址多体并行存储器

1.交叉编址方式

由m个存储体组成的多体并行存储器，其存储单元地址采用低位交叉编址的方法是：若每个存储体的容量均为n个存储字，则存储单元地址的低log2m位称为体号k，地址的高log2n位称为体内地址i。低位交叉编址的存储单元地址A的计算公式为：A=m×i+k

若已知地址A，则可计算出该存储单元所在存储体的体号k=Amodm，以及体内地址。

4.4.1Cache的地址映像与地址变换

1.全相联地址映像及其地址变换

全相联地址映像（Fully-AssociativeAddressMapping）是指主存中的任意一块可以装入到Cache中任意的块位置上。全相联映像的块冲突概率最低，Cache空间利用率最高。全相联映像的地址变换采用目录表来实现，目录表需存放在相联存储器中，目录表的行数（即相联存储器的存储单元数）是Cache的块数。图4.15全相联映像地址变换

【例4.6】

在Cache存储器中，Cache的容量是2C字节，主存是由m个存储体组成的低位交叉编址并行存储器，主存总容量是2M字节，按存储单元编址，每个存储体的存储单元是k字节。采用全相联映像，用相联目录表实现地址变换。（1）写出主存地址和Cache地址的格式，并指出各字段的长度。（2）求出目录表的行数、相联比较的位数和目录表的宽度。解（1）采用全相联映像时，主存地址和Cache地址都分为2个字段：块号和块内地址，格式分别为：

块号B块内地址W块号b块内地址w主存地址Cache地址因为主存的容量是2M字节，存储单元的存储字长是k字节，故主存存储单元数为2M/k，主存地址长度为Log2(2M/k)=M-log2k。因为Cache的容量是2C字节，存储字长是k字节，故Cache存储单元数为2C/k，Cache地址长度为log2(2C/k)=C-log2k。块的大小为m个存储字，故块内地址W和w的长度均为log2m。主存块号B的长度为(M-log2k)-log2m=M-log2kmCache块号b的长度为(C-log2k)-log2m=C-log2km

（2）相联目录表的行数是Cache的块数。块号b的长度为C-log2km，则Cache块的块数可表示为相联比较位数=M-log2km（位）目录表的宽度=(M-log2km)+(C-log2km)+1=M+C-2log2km+1（位）2.直接地址映像及其地址变换

直接地址映像（DirectAddressMapping）把主存空间按Cache的大小划分为若干区，主存各区和Cache再划分为若干块，主存各区中的区内块号B只能装入到与Cache块号b相同的那个块位置上。直接映像的块冲突概率最高，Cache空间利用率最低。直接映像的地址变换采用区表来实现，区表存放在按地址访问的物理Cache中。区表的行数是Cache的块数。3.组相联地址映像及其地址变换

组相联映像把主存按Cache的容量分区，主存中的各区和Cache再按同样大小划分成数量相同的组，组内按同样的大小划分成数量相同的块，主存的组到Cache的组之间采用直接映像，两个对应组的块之间采用全相联映像。组相联的地址变换采用块表来实现。存储块表的存储器可以采用按地址访问的存储器，也可以采用相联访问的存储器，两种存储器中的块表的结构不同。【例4.7】

采用组相联映像的Cache存储器，Cache容量为1K字，要求Cache的每一块在一个主存访问周期能从主存取得。主存采用4个低位交叉编址的存储体组成，主存容量为256K字。采用按地址访问存储器存放块表来实现地址变换，并采用4个相等比较电路。请设计地址变换的块表，求出该表的行数和容量。说明地址变换过程及每个比较电路进行相等比较的位数。

解采用组相联地址变换把主存地址变换为Cache地址时，需要把主存地址分为4个字段，把变换得到的Cache地址分为3个字段。为了确定块表的结构，首先需要确定各字段的长度。区号E组号G块号B块内地址W主存地址组号g组号b块内地址wCache地址主存容量为256K字，即有存储单元218个，故主存地址长度为18位。Cache容量为1K字，即有存储单元210个，故Cache地址长度为10位。主存按Cache大小分区，即主存分为256K/1K=256区，故主存地址的区号E的长度为8位。地址变换的块表采用4个相等比较电路，即一组分为4块，故组内块号B和b的长度为2位。块的大小由在一个主存访问周期能从主存取得的信息量来确定。主存采用4个存储体组成的并行存储器，因此，一个主存访问周期能从主存取得4个存储字，故块的大小为4个存储字，即块内地址W和w的长度为2位。区内组号G的长度=18-8-2-2=6位。组号g的长度=10-2-2=6位。块表中的e是有效位，有效位e的长度为1位。块表的行数为Cache的组数，即有26=64行。块表的宽度=组内块数×(E的长度+B的长度+b的长度+e的长度)=4×(8+2+2+1)=52位块表的容量=块表行数×块表宽度=64×52=3328位64行EBbeEBbeEBbeEBbe图4.19例4.7的块表结构

用块表进行地址变换的过程是：用访存的主存地址中的组号G字段作为块表首地址的偏移量，找到块表中的相应行。读出该行有效位e表示相应主存块有效的区号E和块号B，与主存地址中的区号E字段和块号B字段进行比较。若比较结果是相等，则把从块表中读出的块号b放入Cache地址的块号b字段，并把访存的主存地址中的组号G字段和块内地址W字段分别放入Cache地址的组号g字段和块内地址w字段，从而得出变换的Cache地址。每个比较电路进行相等比较的位数为E的长度+B的长度=(8+2)位=10位5.蝶式置换蝶式置换（Butterfly）实现的互连是：把输入端二进制地址的最高位与最低位互换位置就是连接的输出端的二进制地址。蝶式置换的互连函数为

子蝶式置换实现的互连是：把输入端二进制地址的第k位与最低位互换位置就是连接的输出端的二进制地址。子蝶式置换的互连函数为

超蝶式置换实现的互连是：把输入端二进制地址的最高位与第n-k-1位互换位置就是连接的输出端的二进制地址。超蝶式置换的互连函数为显然，下列等式成立

N=8的蝶式置换、子蝶式置换和超蝶式置换的互连函数分别为

（a）（b）（c）

图5.5N=8的蝶式置换和位序颠倒置换

5.2.1互连网络的结构参数

互连网络连接的拓扑结构可以用无向边或有向边连接有限个结点的图来表示。1.网络规模网络规模是指网络能连接的结点数。2.结点度一个结点射入或射出的边数称为这个结点的结点度。4.网络直径一个互连网络中任意两个结点之间距离的最大值称为这个网络的网络直径。2.Omega网络Omega网络的结构特征是：①采用2×2的4功能开关，这4个功能为：直接、交叉、上播和下播。网络输入端数和输出端数都为N，有个开关级，每级有N/2个开关，网络开关数为。②网络n个开关级从网络输入端到输出端依次为。n+1个级间连接依次为，其中，都是均匀洗牌置换，是恒等置换。③开关采用单元控制方式。

图5.19N=8的Omega网络3.STARAN网络

STARAN网络的结构特征是：①采用2×2的2功能开关，2个功能为直送和交叉。网络输入端数和输出端数都为N，有个开关级，每级有N/2个开关，网络开关数为。由于只使用2功能开关，级间连接都是置换连接，所以STARAN网络实现的连接都是置换连接。②网络n个开关级从网络输入端到输出端依次为。n+1个级间连接依次为，其中，是恒等置换，都是逆洗牌置换。③开关有2种控制方式，一种为级控方式，另一种为组控方式。

图5.23三级STARAN网络

（1）级控方式及其实现的置换连接在级控方式下，需要n位二进制信号作为网络开关控制信号，若fi=0，则级所有开关为直送；若fi=1，则ki级所有开关为交叉。因此，STARAN网络实现的置换连接可表示为：

当fi=1时，有。因此，若级控信号F中只有fi=1，其他各位都为0时，STARAN网络实现的置换连接为：

表5.2N=8的STARAN网络在级控方式下实现的互连f2f1f0实现的互连函数表示000001010011100101110111表5.3N=8的STARAN网络在级控方式下实现的分组交换置换f2f1f0连接的输出端号序列实现的分组交换置换连接00001234567恒等001103254764组2元交换010230167454组2元交换+2组4元交换011321076542组4元交换100456701232组4元交换+1组8元交换101547610324组2元交换+2组4元交换+1组8元交换110674523014组2元交换+1组8元交换111765432101组8元交换（2）组控方式及其实现的置换连接

组控方式是指：将第i级的N/2个2*2的2功能开关分成i+1组，每组用一个位信号f控制该组开关的状态。若f=0，则该组所有开关为直送；若f=1，则该组所有开关为交叉。对于级数是的网络，从第0级至第n-1级各开关级所需的位信号数分别为1,2,n个，因此，共需n(n+1)/2个位信号组成组控信号F。对于N=8的网络，需要6个位信号组成组控信号F，表示为。...表5.4N=8的STARAN网络在组控方式下实现的移数置换循环左移1位：循环左移2位：循环左移4位：f23f22f21f12f11f0连接的输出端号序列实现的移数置换连接00101112345670011110234567011110004567012300001112305674分组移数置换：分为2组，组内循环左移1位00011023016745分组移数置换：分为2组，组内循环左移2位00000110325476分组移数置换：分为4组，组内循环左移1位00000001234567【例5.9】

对于的间接二进制n方体网络，要求同时实现如下连接：0→1，1→6，2→4，3→1，4→2，5→7，6→5，7→0（1）若单元控制采用上控法，网络是否会发生阻塞？画出网络的开关状态图。（2）若单元控制采用输入端与输出端地址按位加的控制方法（T标记寻径），网络是否会发生阻塞？画出网络的开关状态图。图5.25三级间接二进制n方体网络的开关状态图5.Delta网络

Delta网络的结构特征是：①的Delta网络采用a×b的开关，有n个开关级，从网络输入端到输出端依次为K1，K2，…，Kn。开关级Ki的开关数是，1

。开关级Ki的输入端数是，输出端数是。开关级K1的的开关数是个，故网络的输入端数是。开关级Kn的开关数是个，故网络的输出端数是。上控法指定由到达开关上输入端的di

来决定开关的状态。若di=0，则开关为直送状态；若di=1，则开关为交叉状态。下控法指定由到达开关下输入端的di来决定开关的状态，若di=0，则开关为交叉状态；若di=1，则开关为直送状态【例5.11】

对于的Benes二进制置换网络，要求同时实现如下连接：0→2，1→3，2→4，3→0，4→6，5→7，6→5，7→1若单元控制采用上控法，那么网络是否会发生阻塞？画出网络的开关状态图。解根据8个输入端的连接要求，用上控法确定的各开关的状态要求分别如表5.9所示。由表5.9可见，8个输入端的连接要求没有发生开关状态冲突，也没有发生争用开关输出端的冲突，所以，网络不会发生阻塞。网络的开关状态如图5.30所示。

图5.30Benes二进制置换网络的开关状态图5.5.2寻径方法与多播通信

寻径的基本操作就是监控从输入端口进入的信包，并为每个信包选择一个输出端口。由一个高速互连网络连接的多个处理器可以同时向互连网络的多个输入端口发送信包，因此，互连网络的寻径方法（算法）应该尽可能简单和快速，能为同时到达的输入信包进行寻径。寻径方法有算术寻径法和查表寻径法等方法。1.算术寻径法对于具有规则的拓扑结构的互连网络，可以应用算术寻径法，它具有简单快速的优点。例如，曾在多级互连网络中讨论的终端标记寻径法、上控法、下控法和T标记寻径法等方法。维序寻径是按网格网中结点的坐标维的顺序来选择通信链路的寻径方法。二维网格网中的维序寻径称为X-Y寻径，超立方体网络中的维序寻径称为E-立方寻径。（1）X-Y寻径法在二维网格网中，X-Y寻径法规定：任何一个信包在网络中任何一个结点中首先沿X维方向传送，再沿Y维方向传送。

【例5.12】

在一个的二维网格网中，用表示结点。现有4个源—目的结点对同时有信包传送要求：（2,1）→（7,6），（5,4）→（2,0），（0,7）→（4,2），（6,3）→（1,5）。说明采用X-Y寻径算法时各自的传送路径。是否会发生信包争用传送链路或结点包缓冲区的冲突？解

4个信包在二维网格网上的传送路径如图5.33所示。如果信包经过一个结点的延时相等，皆为，那么，可以把这4个信包沿各自路径依序经过的结点顺序表示在表5.10中。

表5.108×8二维网格网中4个信包依序传送的结点序列

时间包1（2,1）（3,4）（4,1）（5,1）（6,1）（7,1）（7,2）（7,3）（7,4）（7,5）（7,6）包2（5,4）（4,4）（3,4）（2,4）（2,3）（2,2）（2,1）（2,0）包3（0,7）（1,7）（2,7）（3,7）（4,7）（4,6）（4,5）（4,4）（4,3）（4,2）包4（6,3）（5,3）（4,3）（3,3）（2,3）（1,3）（1,4）（1,5）（2）E-立方寻径

在个结点的n方体网络中，源结点S的地址为S=sn-1…s1s0，目的结点D的地址为D=dn-1…d1d0。从S到D的路径中的任一中间结点V的地址为V=vn-1…v1v0。E-立方寻径法规定：信包从当前结点V沿n维维序的传送由决定，若r1=1，则信包从当前结点沿维i传送一步到邻接结点；若ri=0，则信包不沿维i传送。【例5.13】

在一个4维超立方体网络中，信包从源结点S=0110传送到目的结点D=1101，采用E-立方寻径算法，说明信包的传送路径。解由S=0110和D=1101，得。第一步：i=0，由r0=1，信包从S传送到结点，即从S沿维0传送一步到结点v1=0111。

第二步：i=1，由r1=1，信包从V1传送到结点，即从V1沿维1传送一步到结点V2=0101。第三步：i=2，由r2=0，信包不沿维2传送。第四步：i=3，由r3=1，信包从V2传送到结点，即从V2沿维3传送一步到结点V3=1101