体系结构2020_假设在3000次访存中,第一级cache不命中110次

一、应用题

1. 试以系列机为例，说明计算机系统结构、计算机组成和计算机实现三者之间的关系。

计算机组成是计算机系统结构的逻辑实现；计算机实现是计算机组成的物理实现。
一种系统结构可以有多种组成；一种组成可以有多种实现。同一系列机中各种型号的机器具有相同的系统结构，但采用不同的组成和实现技术，因而具有不同的性能和价格。

2. 计算机系统结构设计和分析中最经常使用的四个定量原理是什么？

(1) 大概率事件优先原则：对于大概率事件(最常见的事件)，赋予它优先的处理权和资源使用权，以获得全局的最优结果。
(2) Amdahl定律：加快某部件执行速度所获得的系统性能加速比，受限于该部件在系统中所占的重要性。
(3) CPU 性能公式。执行一个程序所需的CPU 时间 = IC ×CPI ×时钟周期时间。
(4) 程序的局部性原理：程序在执行时所访问地址的分布不是随机的，而是相对地簇聚。

3. 根据Amdahl定律，系统加速比由哪两个因素决定？

系统加速比依赖于两个因素：
（1）可改进比例：可改进部分在原系统计算时间中所占的比例。
（2）部件加速比：可改进部分改进以后的性能提高。

4.简述指令的动态调度有何优点。

（1）能够处理一些编译时情况不明的相关（比如涉及存储器访问的相关），并能简化编译器。
（2）能够使本来是面向某一流水线优化编译的代码在其他的流水线（动态调度）上也能高效地执行。动态调度的这些优点是以硬件复杂性的显著增加为代价的。

5.简述记分牌算法中，记分牌记录的信息有哪三个部分？

(1)指令状态表：记录正在执行的各指令已进入到了哪一段；
(2)功能部件状态表：记录各个功能部件的状态。每个功能部件有一项，每一项由9个字段组成；
(3)结果寄存器状态表：每个寄存器在该表中有1项，用于指出哪个功能部件将把结果写入该寄存器。

6. 简述Tomasulo算法中指令流出段所做的主要工作？

从指令队列取一条指令，若该指令的操作所要求的保留站有空闲的，就把该指令送到其保留站R。若其操作数在寄存器中就绪，就将这些操作数送入保留站R.若其操作数还没有就绪，则把将产生该操作数的保留站号送入保留站R。另外，还要完成对目的寄存器的预约工作，将其设置为接受保留站R的结果。

7.简述Tomasulo算法的基本思想。

核心思想是：① 记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW冲突的可能性减小到最少；② 通过寄存器换名来消除WAR冲突和WAW冲突。寄存器换名是通过保留站来实现，它保存等待流出和正在流出指令所需要的操作数。
基本思想：只要操作数有效，就将其取到保留站，避免指令流出时才到寄存器中取数据，这就使得即将执行的指令从相应的保留站中取得操作数，而不是从寄存器中。指令的执行结果也是直接送到等待数据的其它保留站中去。因而，对于连续的寄存器写，只有最后一个才真正更新寄存器中的内容。一条指令+流出时，存放操作数的寄存器名被换成为对应于该寄存器保留站的名称（编号）。

8.Tomasulo算法采用分布的保留站，具有什么特点？

（1）冲突检测和指令执行控制是分布的。每个功能部件的保留站中的信息决定了什么时候指令可以在该功能部件开始执行。
（2）计算结果通过CDB直接从产生它的保留站传送到所有需要它的功能部件，而不用经过寄存器。

9.在Tomasulo算法中，进入“流出”段的条件是什么？对于浮点操作来说，要进行哪些动作和记录工作？

进入“流出”段的条件：有空闲保留站r。
动作和记录工作要点：
（1）判断第一操作数是否就绪；如果是，就把操作数读到保留站，否则就把寄存器状态表中的标识送给保留站。
（2）判断第二操作数是否就绪；如果是，就把操作数读到保留站，否则就把寄存器状态表中的标识送给保留站。
（3）把保留站置为忙。
（4）把操作码送保留站。
（5）把保留站号r送到与该指令的结果寄存器对应的寄存器状态表项。

10.动态分支预测技术的目的是什么？

预测分支是否成功和尽快找到分支目标地址（或指令），从而避免控制相关造成流水线停顿。

11.采用动态分支预测技术,需要解决哪两个关键问题？

（1）如何记录分支的历史信息；（2） 如何根据这些信息来预测分支的去向（甚至取到指令）。

12.BTB表格中的每一项至少有哪两个字段？

执行过的成功分支指令的地址；预测的分支目标地址。

13.简述猜测执行的基本思想。

对分支指令的结果进行猜测，并假设这个猜测总是对的，然后按这个猜测结果继续取、流出和执行后续的指令。只是执行指令的结果不是写回到寄存器或存储器，而是放到一个称为Reorder Buffer的缓冲器中。等到相应的指令得到“确认”（即确实是应该执行的）后，才将结果写入寄存器或存储器。

14.基于硬件猜测执行结合了哪三种思想？

（1）动态分支预测。用来选择后续执行的指令。
（2）在控制相关的结果尚未出来之前，猜测地执行后续指令。
（3）用动态调度对基本块的各种组合进行跨基本块的调度。

15. 循环展开和指令调度时要注意哪几个问题？

（1）保证正确性。在循环展开和调度过程中尤其要注意两个地方的正确性：循环控制和操作数偏移量的修改。
（2）注意有效性。只有能够找到不同循环体之间的无关性，才能够有效地使用循环展开。
（3）使用不同的寄存器。如果使用相同的寄存器，或者使用较少数量的寄存器，就可能导致新的冲突。
（4）删除多余的测试指令和分支指令，并对循环结束代码和新的循环体代码进行相应的修正。
（5）注意对存储器数据的相关性分析。
（6）注意新的相关性。由于原循环不同次的叠代在展开后都到了同一次循环体中，因此可能带来新的相关性。

16.为什么对循环展开以后通常可以改进性能 ?

循环的迭代之间通常是不相关的，或者至少包含一些不依赖于该循环的上一次迭代的运算。但由于存在着因为转移跳转到循环起始处而引起的控制竞争，这就使得处理器很难同时发射多次循环选代的指令。
循环展开将几次迭代合并成一条直线式代码部分，处理器或者编译器通过检查该代码部分可以找出不相关指令。
这些做通常能提高程序中的指令级并行性,从而能够改进程序性能。循环展开还可以减少在循环执行过程中执行的条件转移指令数量，从而进一步改进性能。

17. 流水线冲突有哪几种？

流水线冲突有以下3种类型：
(1)结构冲突：因硬件资源满足不了指令重叠执行的要求而发生的冲突。
(2)数据冲突：当指令在流水线中重叠执行时，因需要用到前面指令的执行结果而发生的冲突。
(3)控制冲突：流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。

18. 在存储器层次结构设计中，论述首先要解决的四个问题及其含义？

（1）块的放置策略：块如何放置在存储器层次中？
（2）块的替换策略：一次失效时，如何替换一个块？ 
（3）块的标识策略：一个块在存储器层次中如何找到它？ 
（4）写的策略：写的时候将会发生什么？。

19．解决流水线数据冲突的方法有哪些？

（1）定向技术
在某条指令产生一个结果之前，其他指令并不真正需要该计算结果，如果将该计结果从其产生的地方直接送到其他指令需要它的地方，就可以避免暂停。
（2）暂停技术
设置一个“流水线互锁”的功能部件，一旦流水线互锁检测到数据相关，流水线暂停执行发生数据相关指令后续的所有指令，直到该数据相关解决为止。
（3）采用编译器调度
为了减少停顿，对于无法用定向技术解决的数据冲突，可通过在编译时让编译器实现指令调度或流水线调度来消除冲突。
（4）重新组织代码顺序
重新组织指令顺序，以加大相关指令的距离，进而减少数据冲突的可能性。

20. 超标量处理机与VLIW处理机比较有哪些优点？

答：(1)超标量结构对程序员是透明的，处理机能自己检测下一条指令是否能流出，不需要由编译器或专门的变换程序对程序中的指令进行重新排列。
(2)没有经过编译器针对超标量结构进行调度优化的代码或是旧的编译器生成的代码也可以运行，只是效果不会很好。

21. 指令多流出处理器的流出能力主要受哪方面影响？

答：(1)程序固有的指令级并行性。
(2)硬件实现上的困难。多流出的处理器需要大量的硬件资源，随着每个时钟周期流出指令数的增加，所需的硬件成正比例地增长，所需的存储器带宽和寄存器带宽也会大大增加，带宽要求必然导致增加硅片面积，加大面积就导致时钟频率下降、功耗增加、可靠性降低等问题。
(3)超标量和超长指令字处理器固有的技术限制。

22. 解决流水线结构冲突的方法有哪些？

（1）流水化功能单元；（2）资源重复；（3）暂停流水线。

23. 简述使用编译器来减少分支延迟的三种方法。这些方法的共同点是什么？

答：(1)预测分支失败
沿失败的分支继续处理指令，就好象什么都没发生似的。当确定分支是失败时，说明预测正确，流水线正常流动；当确定分支是成功时，流水线就把在分支指令之后取出的指令转化为空操作，并按分支目标地址重新取指令执行。
（2）预测分支成功
当流水线ID段检测到分支指令后，一旦计算出了分支目标地址，就开始从该目标地址取指令执行。
（3）延迟分支
主要思想是从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成。不管分支是否成功，都要按顺序执行延迟槽中的指令。
三种方法的共同特点：它们对分支的处理方法在程序的执行过程中始终是不变的。它们要么总是预测分支成功，要么总是预测分支失败。

24. 造成Cache Misses的三类原因。

（1)强制缺失：指最初访问的block总是不在Cache中，必须从memory中取入Cache，故又称为第一次访问缺失。
（2)容量缺失：如果程序执行时，所需块由于容量不足不能全部调入Cache中，则当某些块被替换后，若又重新被访问就会发生缺页，也成为抖动现象。
（3)冲突缺失：因为有多个Blocks映射到同一块，其它的组或块有空闲位置。这是组相联和直接相联的副作用所致。

25. 降低Cache失效率有哪几种方法？简述其基本思想？

常用的降低Cache失效率的方法有下面几种：
（1） 增加Cache块大小。增加块大小利用了程序的空间局部性。
（2） 提高相联度，降低冲突失效。
（3） Victim Cache，降低冲突失效。
（4） 伪相联Cache，降低冲突失效。
（5） 硬件预取技术，指令和数据都可以在处理器提出访问请求前进行预取。
（6） 由编译器控制的预取，硬件预取的替代方法，在编译时加入预取的指令，在数据被用到之前发出预取请求。
（7） 编译器优化，通过对软件的优化来降低失效率。

26. 减少Cache失效开销有哪些方法？

(1) 让读失效优先于写。
(2) 写缓冲合并。
(3) 请求字处理技术。
(4) 非阻塞Cache或非锁定Cache技术。
(5) 采用二级Cache。

27. 采用容量小且结构简单的Cache有什么好处？

（1）可以有效地提高Cache的访问速度。因为硬件越简单，速度就越快。小容量Cache可以实现快速标识检测，对减少命中时间有益。
（2）Cache足够小，可以与处理器做在同一芯片上，以避免因芯片外访问而增加时间开销。
（3）保持Cache结构简单可采用直接映像Cache。直接映像Cache的主要优点是可以让标识检测和数据传送重叠进行，这样可以有效地减少命中时间。

28.组相联Cache的失效率比相同容量直接映像Cache的失效率低。由此能否得出结论：采用组相联映像一定能带来性能上的提高？为什么？

不一定。因为组相联命中率的提高是以增加命中时间为代价的，组相联需要增加多路选择开关。

29. 解释Victim cache的基本思想？

在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，用于存放被替换出去的块，以备重用。这些被保存的替换块被称为Victim块，存放这些块的缓冲称为Victim cache。Victim cache对于减小冲突失效很有效，特别是对于小容量的直接映象数据Cache，作用尤其明显。

30. 解释伪相联cache的工作原理？

在逻辑上把直接映象Cache的空间上下平分为两个区。对于任何一次访问，伪相联Cache先按直接映象Cache的方式去处理。若命中，则其访问过程与直接映象Cache的情况一样。若不命中，则再到另一区相应的位置去查找。若找到，则发生了伪命中，否则就只好访问下一级存储器。

31.在有Cache的计算机系统中，进行I/O操作时，会产生哪些数据不一致问题？如何克服？

（1）存储器中可能不是CPU产生的最新数据 ，所以I/O系统从存储器中取出来的是陈旧数据。 
（2）I/O系统与存储器交换数据之后，在Cache中，被CPU使用的可能就会是陈旧数据。 
第一个问题可以用写直达Cache解决。
第二个问题操作系统可以保证I/O操作的数据不在cache中。如果不能，就作废Cache中相应的数据。

32. 通过编译器对程序优化来改进Cache性能的方法有哪几种？简述其基本思想。

在编译时，对程序中的指令和数据进行重新组织，是连续访问的指令或数据能够具有根号的时间和空间局部性，以降低Cache失效率。主要方法有：
（1）数组合并，通过提高空间局部性来减少失效次数。有些程序同时用相同的索引来访问若干个数组的同一维，这些访问可能会相互干扰，导致冲突失效，可以将这些相互独立的数组合并成一个复合数组，使得一个Cache块中能包含全部所需元素。
（2）内外循环交换。循环嵌套时，程序没有按数据在存储器中的循序访问。只要简单地交换内外循环，就能使程序按数据在存储器中的存储循序进行访问。
（3）循环融合。有些程序含有几部分独立的程序断，它们用相同的循环访问同样的数组，对相同的数据作不同的运算。通过将它们融合成一个单一循环，能使读入Cache的数据被替换出去之前得到反复的使用。
（4）分块。通过改进时间局部性来减少失效。分块不是对数组的整行或整列进行访问，而是对子矩阵或块进行操作。

33. 在“Cache-主存”层次中，主存的更新算法有哪两种？它们各有什么特点？

（1）写直达法。易于实现，而且下一级存储器中的数据总是最新的。
（2）写回法。速度快，“写”操作能以Cache 存储器的速度进行。而且对于同一单元的多个写最后只需一次写回下一级存储器，有些“写”只到达Cache，不到达主存，因而所使用的存储器频带较低。

34. 组相联Cache的失效率比相同容量直接映象Cache的失效率低。由此能否得出结论：采用组相联一定能带来性能上的提高？为什么？

不一定。因为组相联命中率的提高是以增加命中时间为代价的，组相联需要增加多路选择开关。

35.影响多处理机并行处理的两个最大的挑战？

有限的并行度和较长的远程通信延时是多处理器的两个最大的挑战。
在软件中采用更好的并行算法来克服并行度低的问题。
降低远程通信延时则可通过体系结构实现，也可通过程序员实现。在硬件上缓存共享数据，或在软件上重新构造数据就能增加本地访问，因而也就减少了远程访问的频率。还可使用预取或多线程来减少延迟的影响。

36. 简述RISC指令集结构的设计原则

（1）选取使用频率最高的指令，并补充一些最有用的指令；
（2）每条指令的功能应尽可能简单，并在一个机器周期内完成；
（3）所有指令长度均相同；
（4）只有Load和Store操作指令才访问存储器，其它指令操作均在寄存器之间进行；
(5) 以简单有效的方式支持高级语言。

37. 简述CISC指令集结构功能设计的主要目标。从当前的计算机技术观点来看，CISC指令集结构的计算机有什么缺点？

主要目标是增强指令功能，把越来越多的功能交由硬件来实现，并且指令的数量也是越来越多。
缺点：
(1) CISC结构的指令集中，各种指令的使用频率相差悬殊。
(2) CISC结构指令的复杂性带来了计算机体系结构的复杂性，这不仅增加了研制时间和成本，而且还容易造成设计错误。
(3) CISC结构指令集的复杂性给VLSI设计增加了很大负担，不利于单片集成。
(4) CISC结构的指令集中，许多复杂指令需要很复杂的操作，因而运行速度慢。
(5) 在CISC结构的指令集中，由于各条指令的功能不均衡性，不利于采用先进的计算机体系结构技术（如流水技术）来提高系统的性能。

38． 根据CPU性能公式简述RISC指令集结构计算机和CISC指令集结构计算机的性能特点。

CPU性能公式：CPU时间＝IC×CPI×T 
其中，IC为目标程序被执行的指令条数，CPI为指令平均执行周期数，T是时钟周期的时间。 
相同功能的CISC目标程序的指令条数ICCISC 少于RISC的ICRISC，但是CISC的CPICISC和TCISC都大于RISC的CPIRISC和TRISC，因此，CISC目标程序的执行时间比RISC的更长。

39. 指令的执行可采用顺序执行、重叠执行和流水线三种方式，它们的主要区别是什么？各有何优缺点？

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

40. 简述定向技术的思想

定向技术的思想是:在某条指令产生一个计算结果之前，其他指令并不真正需要该计算结果，如果将该计算结果产生的地方直接送到其他指令需要他的地方，那么就可以避免暂停。

41. 简述分布式共享多处理机的优缺点

分布式存储器结构的优点：
(1)如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；
(2)对局部存储器的访问延迟低。
主要缺点：处理器之间的通信较为复杂，且各处理器之间访问延迟较大。

42. 简述伪相联Cache的特点

伪相联Cache既能获得多路组相联Cache的低失效率，又能保持直接映像Cache的命中速度。采用这种方法时，在命中情况下，访问Cache的过程和直接映像Cache中的情况相同，而发生失效时，在访问下一级存储器之前会先检查Cache另一个位置，看是否匹配。

43. 试说明名相关的两种类型

反相关：指令i先执行，指令j写的名是指令i读的名。反相关指令之间的执行顺序是必须保证的，反相关就是先读后写相关。
输出相关：指令j和指令i写相同的名。输出相关指令的指令顺序是不允许颠倒的。输出相关就是写后写相关。

44. 什么是指令级并行性(ILP)？处理器如何利用指令级并行性来改善其性能的？

指令级并行性是指顺序程序中的许多指令是不相关的，这意味着可以不必按照指令在程序中的顺序来执行，依然能生成正确结果。
利用该特性，处理器就可不按顺序执行指令，而是按并行方式执行指令，从而减少了处理器执行程序所需要的时间。

45. 比较循环展开和软件流水的异同？

都可以开发循环级并行，但循序展开增加了代码体积，减少了循环次数；而软件流水对代码体积和循环次数的影响比较小。
这两种技术所消除的流水线开销完全不同；循环展开主要减少由分支指令和修改循环索引变量的指令所引起的循环控制开销，如将某循环展开4次，循环控制开销会减少为原来的四分之一，但执行每个迭代时用于充满和排空流水线的开销并不会减少。软件流水则正好减少了这部分开销，使得迭代内的指令级并行达到最大。

46. 你对Cache存储器的速度不满意，于是申请到一批有限的经费，为能发挥其最大经济效益，有人建议你再买一些同样速度的Cache片子以扩充其容量;而另有人建议你干脆去买更高速的Cache片子将现有的低速Cache片子全部换掉。你认为哪种建议可取？你如何做决定？为什么？

Cache本身的速度与容量都会影响Cache存储器的等效访问速度。如果对Cache存储器的等效访问速度不满意，需要改进的话，就要作具体分析，看看现在Cache存储器的等效访问速度是否已接近于Cache本身的速度。如果差得较远，说明Cache的命中率低，应从提高Cache命中率着手，包括调整组的大小、块的大小、替换算法以及增大Cache容量等。如果Cache存储器的等效访问速度已经非常接近于Cache本身的速度还不能满足需要，就应该更换更高速的Cache片子。

二、计算题

1.假定第一种改进措施使用了20％的时间，但提高了2倍的性能；假定第二种改进措施使用了70％的时间，但提高了1.3倍的性能。设旧执行时间为Told，问：使用哪一种改进措施能使执行时间减少最多？

解答： 应用Amdahl定律，针对第一种改进措施有：
新执行时间=旧执行时间×（（1-0.2）+0.2/2）=0.9旧执行时间
针对第一种改进措施有：
新执行时间=旧执行时间×（（1-0.7）+0.7/1.3）=0.84旧执行时间
因此尽管使用第二种改进措施后性能提高相对较小，但它对使用改进措施后的总执行时间影响较大。

2.假定在运行某个程序时，某计算机将90％的时间用于处理某特定计算类型。某制造商进行修改后，使该计算类型的执行速度提高了10倍。问：

（1）当该程序原来的执行时间为100秒，该程序修改以后的执行时间是多少？
（2）新旧系统之间的加速比是多少？
解答：(1) 应用Amdahl定律：
新执行时间=100×（（1-0.9）+0.9/10）=19秒
(2) 加速比 = 原执行时间/现执行时间=100/19=5.3

3.某台机器的指令集原来进行存储器访问的指令只有Load/Store，其他指令只能在寄存器间操作。这台机器Load/Store指令的使用频率和时钟数如下:

现采用优化编译改善其性能,若编译可减少50%的ALU指令，但它不能减少Load、Store、Branch指令，忽略系统因素，并假设时钟周期是20ns(50MHz),问：优化编译后的MIPS和没有优化编译时的MIPS各为多少？MIPS的变化和执行时间的变化是否一致？

4. 考察代码

               L.D       F6, 34(R2)
               L.D       F2, 45(R3) 
               MULT.D   F0, F2, F4
               SUB.D    F8, F6, F2
               DIV.D     F10, F0, F6
               ADD.D    F6, F8, F2
1
2
3
4
5
6

假设L.D 可在 1 个时钟周期内完成，CDB需要1个时钟周期把结果送到目的。基于Tomasulo算法进行动态调度，请填写经过10个时钟周期时的保留站和寄存器状态表：

5.代码段，实现序列如下

If (d==0) d=1;

if(d==1) { …… }

设Reg[R1]=d, MIPS代码如下：

BNEZ R1,L1 ; 分支 b1

DADDIU R1,R0,# 1 ;

L1: DADDIU R3,R1,# -1

BNEZ R3,L2 ; 分支 b2

……

L2:

6.FP操作的latencies如下：

7. 指令的延迟情况同题6，根据需要展开下面的循环并进行指令调度，循环展开两次可消除延迟，请给出代码。

LOOP:	L.D	F0,0(R1)
	MUL.D	F0,F0,F2
	L.D	F4,0(R2)
	ADD.D	F0,F0,F4
	S.D	F0,0(R2)
	DSUBI	R1,R1,#8
	DSUBI	R2,R2,#8
	BNEZ	R1,LOOP
1
2
3
4
5
6
7
8

解：根据所给延迟情况，程序执行如下：
LOOP: L.D F0,0(R1)
stall ;产生F0的为取操作，使用F0的为浮点计算操作，延迟为1
MUL.D F0,F0,F2
L.D F4,0(R2)
stall ;产生F4的为取操作，使用F4的为浮点计算操作，延迟为1
stall ;产生F0的为浮点计算操作，使用F4的为浮点计算操作，所以延迟共为3
ADD.D F0,F0,F4
stall
stall ;产生F0的浮点计算操作，使用F0的为存操作，所以延迟共为2
S.D F0,0(R2)
DSUBI R1,R1,#8
DSUBI R2,R2,#8 ；使用R1的为分支指令，所以该指令恰好填补了1的延迟）
BNEZ R1,LOOP
stall ；和下一轮循环之间有1个延迟

8.确定下面Loop中存在的true、output和anti等相关性，并用renaming方法消除所有假相关性。

for ( i=1; i<=100; i=i+1)
{
   Y[i] = X[i] / 10;       /*S1*/
         X[i] = X[i] + 50;      /*S2*/
         Z[i] = Y[i] + 24;      /*S3*/
         Y[i] = 30 - Y[i];      /*S4*/
}
解答：for ( i=1; i<=100; i=i+1){
     T[i]   = X[i] / C;            /*将Y改名为T,消除output 相关*/
     X1[i] = X[i] + C;         /*将X改名为X1,消除anti 相关*/
     Z[i]   = T[i] + C;            /*将Y改名为T,消除anti 相关*/
     Y[i]   = C - T[i];
}
1
2
3
4
5
6
7
8
9
10
11
12
13

9.指出下面代码段的所有数据相关，若是真相关，说明它们是否是循环传递相关。并分析能否从这段循环中开发出循环级并行，并说明原因。

for ( i=2; i<=100; i=i+1)
{
    a[i] = a[i] + b[i] ;        /*S1*/
          c[i -1] = a[i] + d[i];      /*S2*/
           a[i -1] = 2*b[i];         /*S3*/
          b[i+1]= 2*b[i]；        /*S4*/
}
1
2
3
4
5
6
7

分析：
(1) 因为对a[i]的写和读， S1和S2之间存在真数据相关。不会妨碍将循环展开，但却限制S2不能被调度到S1之前执行。
(2) 因为对a[i]的写和读，S3和S1之间存在真数据相关，是循环传递相关（Loop-carried dependence）。
(3) 因为对b[i]的写和读, S4和S1，S4和S3，S4和S4之间存在真数据相关，是循环传递相关，且相关距离为1，这使得无法有效开发循环级并行。
(4) 因为对a[i]的写， S1和S3之间存在输出相关，是循环传递相关。

10.有如下代码:

SW 512(R0), R3 ;M[512]←R3 (cache index 0)
LW R1, 1024(R0) ;R1←M[1024] (cache index 0)
LW R2, 512(R0) ;R2←M[512] (cache index 0)

假设采用直接映象的写直达Cache，它把512和1024这两个地址映射到cache 的一个相同块，它带有4个字的写缓存，问:执行代码序列后R3的值和R2的值相等吗？

分析：这是一个存储器中RAM冲突

1. 执行第1条指令后，R3的值被写入了写缓存
2. 第2条取指令由于使用了相同的cache index，因而导致读缺失，从MM1024地址读出新数据块到cache
3. 当执行第3条指令，试图从MM512处读入数据，cache再次发生读缺失，但此时应写入512的R3的值还在缓存中，这时从主存512处取入Cache和R2的值将是更新前的旧值
4. 此时R3和R2的值不等

11.用GCD测试法检测下列循环是否存在相关性？

 for ( i=1; i<=100; i=i+1)
	X[2*i+3] = X[2*i] * 6; 
1
2

解：已知a=2, b=3, c=2, d=0,则GCD(c,a)=2. 又d-b = -3; 2除不尽-3，所以，无相关性存在。

12.一台32个处理器的计算机，对远程存储器访问时间为400ns。除了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器时钟时间为1GHz，如果指令基本的IPC为2(设所有访存均命中Cache)，求在没有远程访问的状态下与有0.2%的指令需要远程访问的状态下，前者比后者快多少?

解：没有远程访问时，机器的CPI为： 1/基本IPC=1/2=0.5
有0.2%远程访问的机器的实际CPI为 ：
CPI＝基本CPI＋远程访问率×远程访问开销
＝0.5＋0.2%×远程访问开销
远程访问开销为:
　 远程访问时间/时钟周期时间＝400 ns/1 ns＝400个时钟周期
CPI＝0.5＋0.2%×400＝1.3
因此在没有远程访问的情况下的计算机速度是有0.2%远程访问的计算机速度的1.3/0.5=2.6倍。

13. 假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误开销为 4 个时钟周期，缓冲不命中的开销为 3 个时钟周期。假设：命中率为 90%，预测度为90%，分支频率为15%，没有分支的基本CPI为1。

（1）求程序执行的CPI。
（2）相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快？
解：（1）程序执行的 CPI = 没有分支的基本CPI + 分支带来的额外开销分支带来的额外开销是指在分支指令中，缓冲命中但预测错误带来的开销与缓冲没有命中带来的开销之和。
　 分支带来的额外开销= 15% * (90%命中×10%预测错误×4 + 10％没命中×3)= 0.099 ，所以，程序执行的CPI ＝ 1 ＋ 0.099 = 1.099
（2）采用固定的2 个时钟周期延迟的分支处理CPI = 1 + 15%×2 = 1.3
由（1）（2）可知分支目标缓冲方法执行速度快

14. 假设分支目标缓冲的命中率为90%，程序中无条件转移指令的比例为5%，没有无条件转移指令的程序CPI值为1。假设分支目标缓冲中包含分支目标指令，允许无条件转移指令进入分支目标缓冲，则程序的CPI值为多少？假定原来的CPI为1.1。

解：对于进入分支目标缓冲器的无条件分支指令，分支预测的精度为100%，也就不会带来分支延迟。而没有进入分支目标缓冲器的无条件分支指令会带来一定分支延迟。首先要求出一条无条件分支指令的分支延迟是多少，不妨设为L个时钟周期。
由题知无条件分支指令不进入分支目标缓冲时程序执行的CPI为1.1，而程序中没有无条件转移指令的CPI为1，因此有

15. 列举出下面循环中的所有相关，包括输出相关、反相关、真相关。

for (i=2; i<100; i=i+1)
	{
a[i]=b[i]+a[i]		;/* s1 */	
	   c[i+1]=a[i]+d[i]    ; /* s2 */	
	   a[i-1]=3*b[i]		; /* s3 */		
b[i+1]=3*b[i]	    ;/* s4 */
}
1
2
3
4
5
6
7

解：展开循环两次：

a[i] = b[i] + a[i]	       ; /* s1 */
c[i+1] = a[i] + d[i]	       ; /* s2 */
a[i-1] = 3 * b[i]	        ; /* s3 */
b[i+1] = 3 * b[i]     	    ; /* s4 */
a[i+1] = b[i+1] + a[i+1]  	; /* H1’ */
c[i+2] = a[i+1] + d[i+1]	    ; /* H2 ‘*/
a[i] = 3 * b[i+1]	        ; /* H3 ‘*/
b[i+2] =3 * b[i+1]	        ; /* H4 ‘*/
1
2
3
4
5
6
7
8

对于单次循环，其中：
 输出相关：无、
 反相关：无、
 真相关：S1和S2 关于a[i]

由于循环引入的相关，其中：
 输出相关：S1和H3
 反相关：S1 和H3、S2 和H3。
 真相关：S4 和H1、S4 和H3、S4 和H4。

16. 假设一台计算机的I/O处理时间占10%，当其CPU性能改进为原来的100倍，而I/O性能仅改进为原来的2倍时，系统总体性能会有什么样的变化？

17.某台主频为400MHz的计算机执行标准测试程序，程序中指令类型、执行数量和平均时钟周期数如下：

求该计算机的有效CPI、MIPS和程序执行时间。

解：（1）CPI ＝(45000×1＋75000×2＋8000×4＋1500×2) / 129500＝1.776
（2）MIPS速率＝f/ CPI ＝400/1.776 ＝225.225MIPS
（3）程序执行时间=$$(45000\times 1＋75000\times 2＋8000\times 4＋1500\times 2)／（400\ast 10^6）=575us$$

18. 计算机系统中有三个部件可以改进，这三个部件的部件加速比为分别为：30、20、10。

（1） 如果部件1和部件2的可改进比例均为30%，那么当部件3的可改进比例为多少时，系统加速比才可以达到10？
（2） 如果三个部件的可改进比例分别为30%、30%和20%，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？

19. 假设某应用程序中有4类操作，通过改进，各操作获得不同的性能提高。具体数据如下表所示：

（1）改进后，各类操作的加速比分别是多少？
（2）各类操作单独改进后，程序获得的加速比分别是多少？
（3）4类操作均改进后，整个程序的加速比是多少？

20. 编译器设计者试图在两个代码之间进行选择。硬件设计者给出了如下数据：

21.用GCD测试法检测下列循环是否存在相关性？

    for (k=1;k<=50;k++)    a[2k]=a[2k-1];
1

解：在这个循环中a=2，b=0，c=2，d=-1，这样GCD(a,c)=2, d-b=-1，由于前者不能够整除后者；该循环不存在循环携带的真数据相关。

22.用假设在3000次访存中，第一级cache不命中110次，第二级cache不命中55次。试问：在这种情况下，该cache系统的局部不命中率和全局不命中率各是多少？

解：第一级cache不命中率（全局和局部）是110/3000，即3.67%；
第二级cache的局部不命中率是55/110，即50%；
第二级cache的全局不命中率是55/3000，即1.83%。

23.假设在一台40MHz处理机上运行200000条指令的目标代码，程序主要由四种类型的指令所组成。根据程序跟踪实验结果，已知指令混合比和每类指令的CPI值如下表所示。

(1)试计算用上述跟踪数据在单处理机上执行该程序时的平均CPI；     
(2)根据(1)所得到的CPI，计算相应的MIPS速率及程序的执行时间。

24.假设某台计算机的特性及性能为：

（1）存储器总线宽度为1个字（32位），送地址需要4个时钟周期，每个字的访问时间为24个时钟周期，传送1个字的数据需4个时钟周期；

（2）Cache块大小为1个字时，Cache失效率为3%；

（3）平均每条指令访存1.2次；

（4）在不考虑Cache失效时，平均CPI为2。

要求：
（1）计算Cache失效开销，存储器的带宽以及在考虑Cache失效时的CPI；
（2）若Cache块大小为2个字时，Cache失效率为2%，计算相应的CPI；
（3）若Cache块大小为2个字时，讨论在采用2路多体交叉存取以及将存储器和总线宽度增加一倍时，对提高性能（用CPI说明）各有何作用？
解：（1）当Cache块大小为一个字时， Cache失效开销为4+24+4=32个时钟周期。
存储器的带宽为每个时钟周期4/32=1/8字节。
在考虑Cache失效时的CPI为2＋（1.2×3%×32） = 3.15个时钟周期。

（2）若Cache块大小为2个字时，Cache失效率为2%，相应的CPI为2＋（1.2×2%×2×32） ＝ 3.54个时钟周期。
（3）若Cache块大小为2个字且采用2路多体交叉存取时，相应的CPI为2＋1.2×2%×（4＋24＋8）＝ 2.86个时钟周期。
性能相对于不采用2路多体交叉存取，提高了（3.54-2.86）/ 3.54 =19.21%。
若Cache块大小为2个字且采用64位总线和存储器，不采用多体交叉时， 相应的CPI为2＋1.2×2%×1×32 = 2.77个时钟周期。
性能相对于不采用存储器和总线宽度增加一倍，提高了（3.54-2.77）/ 3.54 =21.75%。

25. 给定以下的假设，试计算直接映象Cache和两路组相联Cache的平均访问时间以及CPU的性能。由计算结果能得出什么结论？

（1）理想Cache情况下的CPI为2.0，时钟周期为2ns，平均每条指令访存1.2次； 
（2）两者Cache容量均为64KB，块大小都是32字节； 
（3）组相联Cache中的多路选择器使CPU的时钟周期增加了10％； 
（4）这两种Cache的失效开销都是80ns； 
（5）命中时间为1个时钟周期； 
（6）64KB直接映象Cache的失效率为1.4％，64KB两路组相联Cache的失效率为1.0％.