一、简答题（2题）

相关概念、原理、方法说明及比较分析

例题1：解释下列术语

层次机构：按照计算机语言从低级到高级的次序，把计算机系统按功能划分成多级层次结构，每一层以一种不同的语言为特征。
虚拟机：用软件实现的机器。
翻译：先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序，然后再在这低一级机器上运行，实现程序的功能。
解释：对于高一级机器上的程序中的每一条语句或指令，都是转去执行低一级机器上的一段等效程序。执行完后，再去高一级机器取下一条语句或指令，再进行解释执行，如此反复，直到解释执行完整个程序。
计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。
透明性：在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透明性。
计算机组成：计算机系统结构的逻辑实现，包含物理机器级中的数据流和控制流的组成以及逻辑设计等。
计算机实现：计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，模块、插件、底板的划分与连接，信号传输，电源、冷却及整机装配技术等。软件兼容：一个软件可以不经修改或者只需少量修改就可以由一台计算机移植到另一台计算机上运行。差别只是执行时间的不同。
兼容机：由不同公司厂家生产的具有相同系统结构的计算机。
模拟：用软件的方法在一台现有的计算机(称为宿主机)上实现另一台计算机(称为虚拟机)的指令系统。
仿真：用一台现有计算机(称为宿主机)上的微程序去解释实现另一台计算机(称为目标机)的指令系统。
并行性：计算机系统在同一时刻或者同一时间间隔内进行多种运算或操作。只要在时间上相互重叠，就存在并行性。它包括同时性与并发性两种含义。
时间重叠：在并行性概念中引入时间因素，让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以加快硬件周转而赢得速度。
资源重复：在并行性概念中引入空间因素，以数量取胜。通过重复设置硬件资源，大幅度地提高计算机系统的性能。
资源共享：这是一种软件方法，它使多个任务按一定时间顺序轮流使用同一套硬件设备。

例题2：试用实例说明计算机系统结构、计算机组成与计算机实现之间的相互关系。

答：如在设计主存系统时，确定主存容量、编址方式、寻址范围等属于计算机系统结构。确定主存周期、逻辑上是否采用并行主存、逻辑设计等属于计算机组成。选择存储芯片类型、微组装技术、线路设计等属于计算机实现。计算机组成是计算机系统结构的逻辑实现。计算机实现是计算机组成的物理实现。一种体系结构可以有多种组成。一种组成可以有多种实现。

例题3：简述现代计算机系统的多级层次结构
答：第0级：硬联逻辑级。计算机的内核，由门、触发器等逻辑电路组成。
第1级：微程序级。机器语言是微指令集，程序员用微指令编写的微程序，⼀般是直接由硬件执行的。
第2级：机器语言级。机器语言是指令集，程序员用机器指令编写的程序可以由微程序进行解释。
第3级：操作系统级。直接管理传统机器中的软硬件资源，同时也是机器语言的延伸。
第4级：汇编语言级。机器语言是汇编语言，完成汇编语言翻译的程序叫做汇编程序。
第5级：高级语言级。机器语言是各种高级语言，通常用编译程序来完成高级语言翻译的工作。
第6级：应用程序级。为了使计算机满足某种⽤途而专门设计的，这⼀级语言是面向问题的应用语言。

例题4：简述阵列处理机与多处理机的区别
答：①、结构方面：阵列处理机的互连较规整，有一定专用性，互连的处理单元数量大；多处理机要采用更灵活多变的结构，实现复杂的互连模式，互连的处理机数量少。
②、并行性方面：阵列处理机是操作级并行，是并行性的同时性；多处理机是作业、程序、任务级的并行，同时包含指令内部操作间的并行，是并行性的并发性。

⭐例题5：什么是多处理机的一致性？给出解决一致性的监听协议和目录协议的工作原理。

答：(1)、对多个处理器维护一致性的协议称为Cache一致性协议。
(2)、目录协议的工作原理：采用一个集中的数据结构——目录。对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息。目录协议根据该项目中的信息以及当前要进行的访问操作，依次对相应的Cache发送控制消息，并完成对目录项信息的修改。此外，还要向请求处理器发送响应信息。
(3)、监听协议的工作原理：每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。Cache通常连在共享存储器的总线上，当某个Cache需要访问存储器时，它会把请求放到总线上广播出去，其他各个Cache控制器通过监听总线来判断它们是否有总线上请求的数据块。如果有，就进行相应的操作。

例题6：简述先行控制的基本思想。
答：先行控制技术是把缓冲技术和预处理技术相结合。缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲器，用以平滑它们的工作。预处理技术是指预取指令、对指令进行加工以及预取操作数等。
采用先行控制方式的处理机内部设置多个缓冲站，用于平滑主存、指令分析部件、运算器三者之间的工作。这样不仅使它们都能独立地工作，充分忙碌而不用相互等待，而且使指令分析部件和运算器分别能快速地取得指令和操作数，大幅度地提高指令的执行速度和部件的效率。这些缓冲站都按先进先出的方式工作，而且都是由一组若干个能快速访问的存储单元和相关的控制逻辑组成。
采用先行控制技术可以实现多条指令的重叠解释执行。

例题7：指令的执行可采用顺序执行、重叠执行和流水线三种方式，它们的主要区别是什么？各有何优缺点。
答：(1)指令的顺序执行是指指令与指令之间顺序串行。即上一条指令全部执行完后，才能开始执行下一条指令。优点：控制简单，节省设备。缺点：执行指令的速度慢，功能部件的利用率低。
(2)指令的重叠指令是在相邻的指令之间，让第k条指令与取第k+1条指令同时进行。重叠执行不能加快单条指令的执行速度，但在硬件增加不多的情况下，可以加快相邻两条指令以及整段程序的执行速度。与顺序方式相比，功能部件的利用率提高了，控制变复杂了。
(3)指令的流水执行是把一个指令的执行过程分解为若干个子过程，每个子过程由专门的功能部件来实现。把多个处理过程在时间上错开，依次通过各功能段，每个子过程与其它的子过程并行进行。依靠提高吞吐率来提高系统性能。流水线中各段的时间应尽可能相等。

例题8：计算机系统结构的Flynn分类法是按什么来分类的？共分为哪几类？
答：Flynn分类法是按照指令流和数据流的多倍性进行分类。把计算机系统的结构分为：
①单指令流单数据流 SISD；②单指令流多数据流 SIMD；③多指令流单数据流 MISD；④多指令流多数据流 MIMD

例题9：多处理机系统与并行处理机的主要差别是什么？
①并行处理机的并行性在于指令内部，而多处理机的并行性在于指令外部。
②并行处理机把同种操作系统集中在一起，由指令直接启动各个PE同时工作多处理机用专用指令表示并发关系，一个任务开始执行时能够派生出与他同时执行的另一些任务如果任务多余处理机数，则进入任务队列等候。
③并行处理机只有一个CU，自然同步，多处理机执行时间可能互不相同。

例题10：
两种并行性概念 ：同时性并行：两个或两个以上事件在同一时刻发生；并发性并行：两个或两个以上事件在同一时间间隔内发生。
三条技术途径：资源重复：重复设置多个处理部件来提高速度；时间重叠：流水线；资源共享：分时系统，分布式系统
时间—空间关系：资源重复：增加空间以多个空间容纳多条指令；时间重叠：细分空间以多个子空间容纳多条指令

二、计算题（2题）

①、Amdahl定律，CPU性能公式；②、平均存储器访问时间AMAT，缺失率，缺失代价。

1、Amdahl定律、CPU性能公式

Amdahl定律：

$$Fe(指令占比)=\frac{可改进部分占用的时间}{改进前整个任务的执行时间}，Se(处理速度)=\frac{改进前改进部分的执行时间}{改进后改进部分的执行时间}$$

$$S_n=\frac{T_0}{T_n}=\frac{1}{(1-Fe)+\frac{Fe}{Se}}$$

$$拓展:S_n=\frac{1}{(1-\sum F_i)+\sum \frac{F_i}{S_i}}$$

CPU性能公式：

$$①、CPI是每条指令所花的时钟周期数；IC为指令条数:$$

$$时钟频率f(或时钟周期长度t)，t=1/f，f=1/t$$
$$CPU时间T=\frac{CPU时钟周期数(CPI\times IC)}{频率f}=CPU时钟周期数(CPI\times IC)\times 时钟周期长度t$$
$$每条指令所花的时钟周期数:CPI=\frac{CPU时钟周期数目}{IC}$$
$$②、考虑不同指令的CPI不同(n是指令种类数、I_i是第i种指令的执行次数、I_i/IC是第i种指令所占比例):$$
$$CPU时钟周期数=\sum _{i=1}^n(CP{I}_i\times I_i)$$
$$CPU时间T=时钟周期数长度t\times \sum _{i=1}^n(CP{I}_i\times I_i)$$
$$CPI=\frac{{\sum }_{i=1}^n(CP{I}_i\times I_i)}{IC}=\sum _{i=1}^n(CP{I}_i\times \frac{I_i}{IC})$$

例题1：假设将某系统的某一部件的处理速度加快到10倍,但该部件的原处理时间仅为整个运行时间的40%，则采用加快措施后能使整个系统的性能提高多少？
解：由题意可知：Fe＝0.4, Se＝10，根据Amdahl定律：
$$S_n=\frac{T_0}{T_n}=\frac{1}{(1-F_e)+\frac{F_e}{S_e}}$$
$$S_n=\frac{1}{(1-0.4)+\frac{0.4}{10}}=\frac{1}{0.64}\approx 1.56$$
故采用加快措施后能使整个系统的性能提高1.56。

例题2：采用哪种实现技术来求浮点数平方根FPSQR的操作对系统的性能影响较大。假设FPSQR操作占整个测试程序执行时间的20%。一种实现方法是采用FPSQR硬件，使FPSQR操作的速度加快到10倍。另一种实现方法是使所有浮点数据指令的速度加快，使FP指令的速度加快到2倍，还假设FP指令占整个执行时间的50%。请比较这两种设计方案。
解：分别计算出这两种设计方案所能得到的加速比：
$$S_n=\frac{T_0}{T_n}=\frac{1}{(1-F_e)+\frac{F_e}{S_e}}$$
$$S_{FPSQR}=\frac{1}{(1-0.2)+\frac{0.2}{10}}=\frac{1}{0.82}\approx 1.22$$
$$S_{FP}=\frac{1}{(1-0.5)+\frac{0.5}{2}}=\frac{1}{0.75}\approx 1.33$$
故使所有浮点数据指令的速度加快这一方案更好。

例题3：计算机系统中有三个部件可以改进，这三个部件的部件加速比为：
部件加速比₁=30； 部件加速比₂=20； 部件加速比₃=10
(1) 如果部件1和部件2的可改进比例均为30%，那么当部件3的可改进比例为多少时，系统加速比才可以达到10?
(2) 如果三个部件的可改进比例分别为30%、30%和20%，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？

例题4：如果FP操作的比例为25%，FP操作的平均CPI=4.0，其他指令的平均CPI为1.33，FPSQR操作的比例为2%，FPSQR的CPI为20。假设有两种设计方案，分别把FPSQR操作的CPI和所有FP操作的CPI减为2。试利用CPU性能公式比较这两种设计方案哪一个更好（只改变CPI而时钟频率和指令条数保持不变）。

解：由CPU性能公式：

$$CPI=\frac{{\sum }_{i=1}^n(CP{I}_i\times I_i)}{IC}=\sum _{i=1}^n(CP{I}_i\times \frac{I_i}{IC})$$

①、原系统：

$$CP{I}_{原}=\sum _{i=1}^n(CP{I}_i\times \frac{I_i}{IC})$$

$$=CP{I}_{FP}\times \frac{I_{FP}}{IC}+CP{I}_{其他}\times \frac{I_{其他}}{IC}$$

$$=4.0\times 25\%+1.33\times (1-25\%)$$

$$\approx 2$$

②、方案1：将FPSQR操作的CPI减为2

$$CPI=CP{I}_{原}-CP{I}_{原FPSQR}\times \frac{I_{FPSQR}}{IC}+CP{I}_{新FPSQR}\times \frac{I_{FPSQR}}{IC}$$

$$=CP{I}_{原}-\frac{I_{FPSQR}}{IC}(CP{I}_{原FPSQR}-CP{I}_{新FPSQR})$$

$$=2-2\%\times (20-2)$$

$$=1.64$$

③、方案2：将FP操作的CPI减为2

$$CPI=CP{I}_{原}-CP{I}_{原FP}\times \frac{I_{FP}}{IC}+CP{I}_{新FP}\times \frac{I_{FP}}{IC}$$

$$=CP{I}_{原}-\frac{I_{FP}}{IC}(CP{I}_{原FP}-CP{I}_{新FP})$$
$$=2-25\%\times (4.0-2)$$
$$=1.5$$
通过计算对比可知，方案2比方案1好。
方案2的加速比：$$S_n=\frac{T_0}{T_n}=\frac{CPU时{间}_{原}}{CPU时{间}_{方案2}}=\frac{CP{I}_{原系统}\times IC\times 时间周期}{CP{I}_{方案2}\times IC\times 时间周期}=\frac{CP{I}_{原系统}}{CP{I}_{方案2}}=2/1.5\approx 1.33$$

2、平均存储器访问时间AMAT，缺失率，缺失代价

$$程序执行时间=CPU执行程序的时间+等待存储访问的时间$$

$$存储器阻塞时钟周期=\frac{存储器总访问次数}{指令数}\times 缺失率\times 缺失代价$$

$$平均访问时间（AMAT）=命中时间+缺失率\times 缺失代价$$

例题1：假设指令cache的缺失率为2%，数据cache的缺失率为4%，处理器的CPI为2（没有存储器阻塞），且每次缺失的代价为100个时钟周期，那么配置一个从不发生缺失的理想的cache，处理器的速度快多少？假定全部LOAD和STORE的频率为36%。
解：$$指令缺失时钟周期=I\times 2\%\times 100=2.0I$$
$$数据缺失时钟周期=I\times 36\%\times 4\%\times 100=1.44I$$
$$总的存储器阻塞时钟周期=2.0I+1.44I=3.44I$$
$$总的CPI=2+3.44=5.44$$
$$配置理想CACHE后的性能是原来的5.44/2=2.72倍$$

例题2：处理器时钟周期的时间1ns,缺失代价是20个时钟周期，缺失率为每条指令0.05次缺失，cache的访问时间（包括命中判断）为1个时钟周期。假设读操作和写操作的缺失代价相同并且忽略其它写阻塞。请计算AMAT。
解：每条指令的平均存储器访问时间AMAT为：
$$AMAT=命中时间+缺失率\times 缺失代价$$
$$=1+0.05\times 20$$
$$=2个时钟周期$$
例题3：假定处理器基本的CPI为1.0，时钟频率为4GHz。假定主存访问时间为100ns，其中包括缺失处理时间。设一级cache中每条指令缺失率为2%。如果增加一个二级cache，命中或缺失访问的时间都是5ns，而且容量大到必须使访问主存的缺失率减少到0.5%,这时的处理器速率能提高多少？

解：主存的缺失代价：$$\frac{100ns}{0.25ns/时钟周期}=400个时钟周期$$
只有一级cache时,总的$$CPI=1.0+2\%\times 400=9.0$$
对于两级cache，二级cache的缺失代价：$$\frac{5ns}{0.25ns/时钟周期}=20个时钟周期$$
总的$$CPI=1.0+2\%\times 20+0.5\%\times 400=3.4$$
有二级cache的处理器性能是没有二级cache性能的$$9.0/3.4=2.6倍$$

三、设计分析题（4题）

①、循环展开实现流水线调度；②、应用时空图解决线性流水线调度问题，计算流水线吞吐率、加速比、效率；③、应用禁止启动距离、禁止向量、状态图解决非线性流水线调度问题，计算流水线吞吐率、加速比、效率；④、应用多级立方体网络、Ω网络实现通信。

1、循环展开实现流水线调度

流水线调度：分离导致流水线延迟的指令

例子：

for (i = 999; i >= 0; i = i - 1)
    x[i] = x[i] + s;

翻译这张图：

产生结果的指令	使用结果的指令	延迟
浮点计算	另一个浮点计算	3
浮点计算	浮点Store	2
浮点Load	浮点计算	1
浮点Load	浮点Store	0

①、未调度时：一次循环迭代9个时钟周期。

Loop:	L.D	F0,0(R1)
		stall
		ADD.D F4,F0,F2
		stall
		stall
		S.D F4,0(R1)
		DADDUI R1,R1,#-8
		stall (assume integer load latency is 1)
		BNE R1,R2,Loop

②、调度后：一次循环迭代7个时钟周期。

Loop:	L.D	F0,0(R1)
		DADDUI R1,R1,#-8
		ADD.D F4,F0,F2
		stall
		stall
		S.D F4,8(R1)
		BNE R1,R2,Loop

③、循环展开：展开因子4 (assume # elements is divisible by 4)，消除不必要的指令

四个元素共27个时钟周期：14+3*4+1（每个LOAD一次停顿，每个ADD两次停顿，DADDUI一次停顿）每个元素：27/4=6.75

Loop:	L.D F0,0(R1)
		ADD.D F4,F0,F2
		S.D F4,0(R1) ;drop DADDUI & BNE
		L.D F6,-8(R1)
		ADD.D F8,F6,F2
		S.D F8,-8(R1) ;drop DADDUI & BNE
		L.D F10,-16(R1)
		ADD.D F12,F10,F2
		S.D F12,-16(R1) ;drop DADDUI & BNE
		L.D F14,-24(R1)
		ADD.D F16,F14,F2
		S.D F16,-24(R1)
		DADDUI R1,R1,#-32
		BNE R1,R2,Loop

④、调度展开后的循环：4个元素共14个时钟周期：没有停顿；每个元素：14/4=3.5个时钟周期，总体性能提升： 9/3.5=2.57倍

Loop:	L.D F0,0(R1)
		L.D F6,-8(R1)
		L.D F10,-16(R1)
		L.D F14,-24(R1)
		ADD.D F4,F0,F2
		ADD.D F8,F6,F2
		ADD.D F12,F10,F2
		ADD.D F16,F14,F2
		S.D F4,0(R1)
		S.D F8,-8(R1)
		DADDUI R1,R1,#-32
		S.D F12,16(R1)
		S.D F16,8(R1)
		BNE R1,R2,Loop

例题1：

2、线性流水线调度问题

3、非线性流水线调度问题

非线性流水线的禁止向量：将预约表中每行任意两个“X”之间的距离都计算出来，然后去掉重复的，得到禁止向量F。
初始冲突向量：C＝（C_mC_m-1…C₂C₁），m是禁止向量中的最大值，如果i在禁止向量中，则C_i＝1，否则C_i＝0。
状态图：将冲突向量送入一个m位逻辑右移移位器，当移位器移出0时，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；否则不做任何处理，如此重复m次。对于中间新形成的每一个冲突向量，也要按照同样的方法进行处理。
简单循环：状态图中各种冲突向量只经过一次的启动循环。简单循环的个数一般是有限的。有简单循环可以计算出平均启动距离。
公式： 吞吐率：TP＝n / T_k（n为任务数，T_k为完成n个任务所用的时间）
加速比：S＝T₀ / T_k
效率：E＝n个任务占用的时空区 / k个流水段的总时空区＝T₀ /（k·T_k）

非线性流水线性能公式：

k为流水线的段数，n为任务个数

吞吐率为：$$TP=\frac{n}{{\sum }_{i=1}^k\Delta t_i+(n-1)max(\Delta t_1,\Delta t_2,\cdot \cdot \cdot ,\Delta t_k)}$$

最大吞吐率为：$$T{P}_{max}=\frac{1}{max(\Delta t_1,\Delta t_2,\cdot \cdot \cdot ,\Delta t_k)}$$

效率：$$E=\frac{n{\sum }_{i=1}^k\Delta t_i}{k[{\sum }_{i=1}^k\Delta t_i+(n-1)max(\Delta t_1,\Delta t_2,\cdot \cdot \cdot ,\Delta t_k)]}$$

$$加速比：S=\frac{n{\sum }_{i=1}^k\Delta t_i}{{\sum }_{i=1}^k\Delta t_i+(n-1)max(\Delta t_1,\Delta t_2,\cdot \cdot \cdot ,\Delta t_k)}$$

例题1、一条有4个功能段的非线性流水线，每个功能段的延迟时间都相等，它的预约表如下：

功能段＼时间	1	2	3	4	5	6	7
S1	X						X
S2		X				X
S3			X		X
S4				X

（1）写出流水线的禁止向量和初始冲突向量。
（2）画出调度流水线的状态图。
（3）求流水线的最小启动循环和最小平均启动距离。
（4）求平均启动距离最小的恒定距离。
解：
（1）禁止向量F＝（2，4，6）；初始冲突向量C=101010
（2）101010右移1位后：010101∨101010＝111111
101010右移3位后：000101∨101010＝101111
101010右移5位后：000001∨101010＝101011
101010右移7位或者大于7位后，还原到101010

11111右移7位或者大于7位后，还原到101010

101111右移5位后：000001∨101010＝101011
101111右移7位或者大于7位后，还原到101010

101011右移3位后：000101∨101010＝101111
101011右移5位后：000001∨101010＝101011
101011右移7位或大于7位后，还原到101010

（3)

简单循环	平均启动距离
（1，7）	4
（3，7）	5
（5，7）	6
（3，5，7）	5
（5，3，7）	5
（3，5）	4
（5）	5
（7）	7

由图可知，最小启动循环为（1，7）或（3，5），其平均启动距离为4。
（4）平均启动距离最小的恒定循环为（5）。

例题2、在一个5段的流水线处理机上需要经9拍才能完成一个任务，其预约表如图所示。

功能段\时间	0	1	2	3	4	5	6	7	8
1	X								X
2		X	X
3				X			X	X
4				X	X
5						X	X

（1）写出延迟禁止表F和冲突向量C；画出流水线状态转移图；求最小平均延迟、最大吞吐率和最佳调度方案。
（2）按最佳调度方案输入6个任务，画出流水时空图，并求实际吞吐率和效率。
解：（1）①、延迟禁止表F＝{1，3，4，8}；冲突向量C＝10001101
②、10001101右移2位后：00100011∨10001101＝10101111
10001101右移5位后：00000100∨10001101＝10001101
10001101右移6位后：00000010∨10001101＝10001111
10001101右移7位后：00000001∨10001101＝10001101

10101111右移5位后：00000101∨10001101＝10001101
10101111右移7位后：00000001∨10001101＝10001101

10001111右移5位后：00000100∨10001101＝10001101
10001111右移6位后：00000010∨10001101＝10001111
10001111右移7位后：00000001∨10001101＝10001101
流水线状态转移图：

③、最小平均延迟、最大吞吐率和最佳调度方案：

调度方案	平均延迟（拍）
（5）	5
（7）	7
（2，5）	3.5
（2，7）	4.5
（6，5）	5.5
（6，7）	6.5
（6）	6

由图可知，最小平均延迟为3.5拍；最大吞吐率为1/3.5（任务/拍）；最佳调度方案为（2，5）。
（2）按最佳调度方案为（2，5）输入6个任务（在S1流水线上，任务1在0开始，任务2隔2拍在2开始，任务3隔5拍在7开始，剩下任务以此类推，其他流水线也如此），流水时空图如下图所示：

由图可知，实际吞吐率为：TP＝6/25Δt；实际效率（利用率）E＝（11×6）Δt/（25×5)Δt=66/125

例题3：

解：（1）时空图如下图所示：（要点在于确定第2个任务的起始点，$TPmax=\frac{1}{3\Delta t}$，为了避免堵塞，任务时间间隔最少为$3\Delta t$）

实际吞吐率：$$TP=\frac{4}{15\Delta t}(任务/拍)$$
效率：$$E=\frac{4\times 6\Delta t}{4\times [6\Delta t+3\times 3\Delta t]}=\frac{24\Delta t}{60\Delta t}=40\%$$
（2）①、使用瓶颈段细分方法改造后的时空图：（将S₄分成S_4-1、S_4-2和S_4-3，执行时间皆为$\Delta t$）

实际吞吐率：$$TP=\frac{4}{9\Delta t}(任务/拍)$$

效率：$$E=\frac{4\times 6\Delta t}{6\times 9\Delta t}=\frac{24\Delta t}{54\Delta t}=\frac{4}{9}$$

②、使用瓶颈段并联方法改造后的时空图：

实际吞吐率：$$TP=\frac{4}{9\Delta t}(任务/拍)$$

效率：$$E=\frac{4\times 6\Delta t}{6\times 9\Delta t}=\frac{24\Delta t}{54\Delta t}=\frac{4}{9}$$

4、应用多级立方体网络、Ω网络实现通信

例题1：阵列有0-7共8个处理单元互连，要求按(0，5)，(1，4)，(2，7)，(3，6)配对通信。
（1）写出实现此功能的互连函数的一般式。
（2）画出用三级立方体网络实现互连函数的互连网络拓扑结构图，并标出各控制开关的状态。
解：（1）以(0,5)为例，0：000——5：101，可得
互连函数的一般式为$$Cube(b_2{b}_1{b}_0)=\overline{b_2}{b}_1\overline{b_0}$$
（2）互连网络拓扑结构图如下图所示：

其中，A、B、C、D为交换开关，E、F、G、H为直通开关，I、J、K、L为交换开关。

例题2：给出N=8的蝶式变换，对应关系为(0，0)，(1， 4)，(2，2)，(3，6)，(4，1)，(5， 5)，(6，3)，(7，7)。
1)写出此互连函数的关系式。
2)如果采用omega网络，需几次通过才能完成此变换。
3)列出omega网络实现此变换的控制状态图。

解：（1）互连函数的关系式为：$$B(b_2{b}_1{b}_0)=b_0{b}_1{b}_2$$

（2）Ω网络如下图所示：
若要实现此变换，则相关路径如下：

(0,0)：0→A上→E上→I上

(1,4)：1→B下→H上→K上

(2,2)：2→C上→E下→J上

(3,6)：3→D下→H下→L上

(4,1)：4→A上→E上→I下

(5,5)：5→B下→H上→K下

(6,3)：6→C上→E下→J下

(7,7)：7→D下→H下→L下

可知，会产生4个冲突，分别为(0,0)和(4,1)、(1,4)和(5,5)，(2,2)和(6,3)及(3,6)和(7,7)，故需要两次通过才能实现此变换。

（3）控制状态图如下：

例题3：用一个N=8的三级Omega网络连接8个处理机(P₀-P₇)，8个处理机的输出端分别依序连接Omega网络的8个输入端0-7，8个处理机的输入端分别依序连接Omega网络的8个输出端0-7。如果处理机P₆要把数据播送给处理机P₀-P₄，处理机P₃要把数据播送给处理机P₅-P₇，那么，Omega网络能否同时为它们的播送要求实现连接？画出实现播送的Omega网络的开关状态图。