计算机系统结构2011年串讲及汇总第二部分

1、第四章 存储体系1. 对存储器的基本要求是：大容量、高速度和低价格。2. 存储器容量为：SM = Wlm (其中W为存储体的字长，l为存储体的字数， m为并行工作的存储体数)3. 单体最大频宽：Bm = W / TM m体在座体并行的最大频宽：Bm = Wm / TM (TM 为连续启动一个在存储体所需时间间隔)4. 并行主存系统：能并行读出多个CPU字的单体多字、多体单字、多体多字的交叉访问主存系统系统为并行主存系统。5. 为什么主存实际频宽不是随着模m的提高而线情增大：(1)工程实现上由于模m越高，存储器数据总线越长，总线并联的负载越重，有时不得不增加门的级数，这些会使传输延迟增加(2)实

2、际程序中指令不总是顺序执行的，一旦出现转移，效率就会下降，而数据的性比指令的还差，实际的效率还更低。6. CPU与主存速度差给系统性能带来影响，解决办法有：(1)在CPU中设置通用寄存器 (2)采用存储器的多体交叉并行存取 (3)采用Cache存储器。7. 存储体系设计的主要依据是：程序访存的局部性， 其主要包括：(1) 时间上：最近的未来要用到的信息很可能是现在正在使用的信息，这是因为程序存在循环。(2) 空间上：最近的未来要用到信息很可能与现在正在使用的信息在程序空间上是邻近的，这是因为指令常是顺序存放、顺序执行，数据通常是以微量、阵列、树形、表格等形式簇聚地存放的。8. 命中率指CPU产

3、生的逻辑地址能在M1中访问到(命中到)的概率。若逻辑地址流的信息能在M1中访问到的次数为R1，当时在M2中还未调到M1的次数为R2，则命中率HR1 /（R1+R2）。）（影响因素：地址流、预判算法、M1的容量等）9. 未命中率(失效率)是指由CPU产生的逻辑地址在M1中访问不到的概率。对二级存储层次，失效率为1-H 10. 段式管理：将主存按段分配的存储管理方式称为段式管理。将虚地址（程序号，段号，段内位移）通过段表找到段的基地址，然后再形成物理地址，访问存储器。 段表结构 =（段名，段地址，装入位，段长，访问方式）11. 段式管理的主要优点：（1）程序模块化的性能好，各段在功能上是相互独立的

4、；（2）便于程序与数据的共享；（3）便于实现存储保护。12. 段式管理的主要缺点：（1）地址变换所需的时间比较长（2）主存的空间利用不充分。13. 页式管理：把主存空间和程序空间都机械等分成固定大小的页(页面大小随机器而异)14. 页式存储的优点：（1）主存储器的空间利用率比较高。（2）页表比较简单，大大简化了映像表的硬件，节省了页表的存储量（3）地址映象与地址转换速度比较快。15. 页式存储的缺点：（1）页表很长，占用很大的存储空间。 （2）程序的模块化性能不好。16. 段页式管理：把实存机械的等分成固定大小的页，把程序按模块分段，每个段分成与主存页面大小相同的页，每道程序通过 一个段表和相

5、应于每段的一组页表来进行定位。17. 装入位:标识该段的页表是否已装入主存。 地址字段:指明已装入页表在主存中的起始地址。 访问方式:指明该段的控制保护信息。 页表长:指明该段页表的行数。18. 地址的映象：将每个虚存单元按什么规则（算法）装入（定位于）实存，建立起多用户虚地址与实地址之间的对应关系。19. 页面替换算法：（1）随机算法(RAND) （2）先进先出法(FIFO)（3）近期最少使用法/近期最久未用算法 (LRU法)（4）最优替换算法(OPT)20.第五章 重叠、流水和向量处理机21. 指令的解释方式一般分为顺序、重叠、流水三种。22. 解释一条机器指令的微操作可归并为：（1）取指

6、令、（2）分析、（3）执行 三个部分。（1） 取指令：是按指令计数器的内容访主存，取出该指令送到指令寄存器。（2） 指令分析：是对指令的操作码进行译码，按寻址方式和地址字段形成操作数真地址，并用此真地址去取操作数。为取下条数据，还要形成下条指令的地址。（3） 指令的执行：是对操作数进行运算、处理，或存储运算结果。(可能要访主存)23. 顺序解释：指的是各条指令之间顺序串行进行。（即执行完一条指令后才取下一条指令） 优点：控制简单，节省设备； 缺点：速度慢，机器各部件的利用率很低；24. 重叠解释：是在解释第K条指令的操作完成之前，就可以开始解释第K+1条指令。25. 重叠解释方式存在着访存冲突

7、，解决访主存的冲突的几种方式：（1）主存分成两个独立编址的存储器，一个专门存放指令一个专门存放操作数；（加重了主存总线控制的复杂性及软件设计麻烦）（2）指令和数据仍然混存在一个存储器中，采用多体交叉主存结构；（不能根本解决）（3）增设采用先进先出方式工作的指令缓冲寄存器（指缓）。26. 一次重叠：把取指令操作隐含在分析、执行指令过程中，则在任何时候只允许上条指令“执行”与下条指令“分析”相重叠。27. 相关：因程序相邻指令之间出现了关联，为防止出错它们不能同时解释。这种现象称发生了“相关”。（1）数相关：第K+1条指令的源操作数地址正好是第K条指令结果地址。分为(1)主存空间的数相关(2)通用

8、寄存器组的数相关 顺序解释没问题，而重叠解释时，在“执行K”和“分析K+1”重叠时就出现问题。（2）指令相关：经过第K条指令的执行来形成第K+1条指令。（重叠解释时先从指缓中取到第K+1条指令是旧内容 出错） 指令相关是因为机器指令允许修改引起的。28. 指令相关的处理：可通过限定程序运行过程中不准修改指令不可行。IBM370采用“执行”指令。被修改的指令以“执行”指令的操作数形式出现，将指令相关转成数相关。（这样只要统一进行数相关处理就可以了）29. 主存空间数相关的处理：相邻两条指令之间出现对同一主存单元要求先写后读的关联。(设置优先级：写优先级 读优先级)30. 通用寄存器组相关（a.通

9、用寄存器组数相关 b.通用寄存器组基址和变址值相关）的处理：(1)推后分析K+1 (降低速度为代价) (2)设置相关专用通路（增加设备为代价）31. 流水是重叠的进一步延伸：一次重叠：把指令的解释分成两个子过程，同时解释两条指令。流水：把指令的解释分成多个子过程，同时解释多条指令。32. 流水的最大吞吐率：流水线满负荷，每隔 t流出一个结果时所达到的吞吐率。33. 流水的分类： 流水按扩展方向分类：（1）流水向下扩展：把子过程进一步细分。(过程并行)（2）流水向上扩展：在多个处理机之间流水。(任务并行) 流水按处理级别分为（1）部件级的流水：构成部件内的各个子部件之间的流水。（如运算器内的“浮

10、点加”流水）（2）处理机级流水：构成处理机的各个部件之间的流水。（如取指、分析、执行的流水）（3）系统级流水：构成计算机系统的多个处理机之间的流水，也称为宏流水。 按流水线的功能多少分为：（1）单功能流水线：只能实现一种功能的流水。（如“浮点加”流水）（2）多功能流水线：同一流水线的各个段之间可以有多种不同的连接方式实现多种不同的运算或功能的流水。 (a)静态流水线：在某一时间内各段只能按一种功能联接流水，只有等流水线全部流空后，才能切换成按另一种功能来联接流水。实现简单。 (b)动态流水线：各功能段在某一时间内可按不同运算或功能联接。控制复杂。 从流水线中各功能段之间是否有反馈回路分为：（1

11、）线性流水线：各个段之间串行连接，无反馈也无跳跃，每个任务流经流水线中各个段均只有一次。（2）非线性流水线：各个段之间除了有串行连接，还有反馈回路，使一个任务流经流水线时，需多次经过某段或越过某段。 按机器所具有的数据表示分为：（1）标量流水机 （2）向量流水机34. 流水处理机的主要性能：（1）吞吐率（2）效率35. 吞吐率：指在单位时间内流水线完成的任务数或输出的结果数。TP = n /Tk (n表示任务数，Tk表示完成n个任务所需时间)36. 最大吞吐率：TPmax = 1/maxt1, t2, t3 tn37. 瓶颈子过程：流水线中经过时间最长的子过程。38. 消除瓶颈的方法：（1）将

12、瓶颈子过程再细分（2）重复设置多套瓶颈段并联39. 加速比Sp：流水方式相对于非流水顺序方式速度提高的比值。40. 效率：流水线设备的实际使用时间占整个运行时间之比，也称流水线设备的时间利用率。41. 影响流水线效率不高的因素包括：（1）静态多功能流水线流水时，总有一些本功能用不到的段处于空闲状态。（2）流水建立过程中，本功能要用到的某些段也有部分处于空闲状态。（3）功能切换时，增加了前一种功能流水的排空时间及后一种功能流水的建立时间。（4）上一步运算的结果要送到流水线的输入端，下一任务才能开始。42. 全局性相关：机器系统出现相关时，影响面较宽，较严重，称为全局性相关。（如转移指令废指缓）4

13、3. 局部性相关：机器系统出现相关时，只影响相关的几条指令，最多影响流水线某些段工作的后推，不会改动指缓中预取到的指令，影响是局部的。（如指令相关，主存操作数相关等）44. 局部性相关的处理： 流水技术是重叠技术的发展，因此，重叠机器处理相关的方法也适用于流水机器，即 推后读 设置相关直接通路。 按流水线中流动顺序的安排，分为两种形式： （1）同步流动：任务(指令)流出流水线的顺序与流入流水线的顺序一致(顺序流动)。 （2）异步流动：任务(指令)流出流水线的顺序与流入流水线的顺序不一致。45. 异步流动要处理的三种相关(都是对同一单元的要求)：（1）“先写后读”相关：在先的指令先写入，在后的指

14、令才能读的关联，称“先写后读”相关。（2）“写写”相关：在先的指令先写入，在后的指令才能写的相关。（3）“先读后写”相关：在先的指令先读，在后的指令才能写的相关，称“先读后写”相关。s46. 全局相关的处理：（1） 猜测法：概率相近时宜选用i+1 不成功转移分枝；概率不均等时，宜选用高概率分支（2） 加快和提前形成条件码（3） 采取延迟转移（4） 加快短循环程序的处理47. 流水机器原中断处理：主要是为了处理好中断点现场的保存和恢复。48. 向量的流水处理：将向量数据表示和流水线技术结合起来，构成向量流水处理机，使向量运算最能充分发挥出流水线效率。49. 向量的三种处理方法：（1）横向(水平)

15、处理方法：以元素为单位，逐个求向量元素值。 例如求：D=A*(B+C)，则进行bi+cik，k*aidi操作。 横向处理适合标量处理机，发挥不出流水的优势。（2）纵向（垂直）处理方式：以向量为单位，对整个向量求结果向量。例如求：D=A*(B+C)，则进行B+CK，K*AD操作。（3）分组纵横处理方式：若向量的长度过长，则可分成若干组，使每组都能装入向量寄存器组，组内按纵向方式处理，组间靠软 件循环处理。50. 指令级高度并行的超级处理机：（1）超标量处理机（2）超长指令字处理机（3）超流水线处理机51. 超标量处理机：多条指令流水线，每个t同时流出m条指令(称为度m)，靠编译程序优化指令执行顺

16、序。组成：冗余设置，多套部件（多套单流水线部件），多部件并发工作。52. 超长指令字处理机：将水平型微码和超标量处理两者相结合。多个功能部件并发工作，共享大容量寄存器堆；工作原理如下：1.编译时找出潜在并行性，进行单指令，多操作，多操作码，多数据压缩，形成超长指令。2.执行时不检测并行性与相关性，直接执行。53. 超流水线处理机：工作原理：每个t只流出一条指令，但t很小，同超标量相比（度为m），是其节拍（单位时间）的1/m。超流水线是单流水线，t非常小，相当于原流水线的t= t/m。第六章 阵列处理机54. 阵列处理机：将大量重复设置的处理单元PE按一定方式互连成阵列，在单一控制部件CU控制下

17、对各自所分配的不同数据并行 执行同一指令规定的操作，是操作级并行的SIMD计算机。（处理单元PE是不带指令控制部件的算术逻辑部件） 从CU看，指令是串行执行的，从PE看，数据是并行处理的。（主要用于高速向量或矩阵运算中）55. 阵列处理机的基本构形：（1）采用分布式存储器的阵列处理机构形（2）采用集中式共享存储器的阵列处理机构形56. 阵列处理机的特点：（1）速度快，潜力大 （2）模块性好，生产和维护方便（3）可靠性高，容易实现容错和重构 （4）效率低（5）潜力大（6）依赖于互连网络和并行算法（7）需要有一台高性能的标量处理机57. 阵列处理机的并行算法举例：（1）矩阵加（2）矩阵乘（3）累加

18、和58. SIMD计算机的互连网络：（1）基本的单级互连网络（2）多级互连网络59. 基本的单级互连网络：（1）立方体单级网络（2）PM2I单级网络（3）混洗交换单级网络60. 多级互连网络：（1）多级立方体互连网络（2）多级混洗交换网络（3）多级PM2I网络61. 交换开关：是具有两个入端和两个出端的交换单元（a.直连 b.交换 c.上播 d.下播）62. 控制方式：对各个交换开关进行控制的方式（a.级控制 b.单元控制 c.部分级控制）63.第七章 多处理机64. 使用多处理机的目的：（1）用多台处理机进行多任务处理协同求解一个大而复杂的问题来提高速度（2）领先冗余的处理机及其重组来提高系

19、统的可靠性、适应性和可用性。65. 多指令流多数据流系统（MIMD）与单指令流多数据流系统（SIMD）的主要差别：并行处理机（SIMD）多处理机（MIMD）(1)结构灵活性主要针对向量数组处理，故具有专用性只需设计有限、固定的机间互连通路为实现作业、任务、程序段的并行，结构应灵活多变，以实现复杂的机间互连，避免争用共享的硬件资源。(2)程序并行性并行性存在于指令内部 程序员解决并行性存在于指令内部和外部(表现在多任务的并行) 利用算法、程序、编译、OS、指令、硬件等解决(3)并行任务活派生由指令反映数据间能否并行计算，并启动多个处理单元并行工作需专门指令或语句指明程序中各程序段的并发关系，控制

20、他们的并发执行，使一个任务执行时可派生出另一些任务(4)进程同步本来就是同步的，无需干涉若并发程序之间有数据相关或控制依赖，需要采取同步措施(5)资源分配和任务调度可知道实际参加并行执行的处理单元数无法知道并行执行的处理单元数故需要解决资源分配任务调度66. 多处理机（MIMD）存在的主要技术问题：（1）硬件结构上，如何解决好处理机、在座器模块及I/O了系统间的互连。（2）如何最大限度开发系统的并行性，以实现多处理机各级的全面并行。（3）如何选择任务和子任务的大小，即任务的粒度，使并行度高，辅助开销小。（4）如何协调好多处理机中各并行执行的任务和进程间的同步问题（5）如果将任务分配到多处理机上

21、，解决好处理机调度、任务高度和资源分配，防止死锁。（6）一旦某处理机发生故障，如何对系统进行重新组织，而不使其瘫痪。（7）多处理机机数增多后，如何能给编程者提供良好的编程环境，减轻程序的复杂性。67. 多处理机有紧耦合和松耦合两种。68. 紧耦合多处理机：通过共享主存实现处理机间通讯的，其通讯速率受限于主存频宽。（各处理机与主存经互连网络连接）（处理机数受限于a.互连网络带宽 b.各处理机访主存冲突的概率）69. 松耦合多处理机：每台处理机都有一个容量圈套的局部存储器，用于存储经常用的指令和数据，以减少紧耦合系统中存在的访主存冲突。(不同处理器之间通过a.通道互连实现通信或通过b.消息传送系统

22、MTS来交换信息)70. 多处理机机间互连的形式：（1）总线（2）环形互连（3）交叉开关（4）多端口存储器（5）开关枢纽结构71. 提高总线形式的系统效率的办法：（1）用优质调频同轴电缆来提高总线的传输速率（2）用多总线方式来减少访总线的冲突概率。72. 解决多个处理机同时访问公用总线的冲突的仲裁算法：（1）静态优先级算法（2）固定时间片算法（3）动态优先级算法（4）先来先服务算法73. 并行程序设计语言基本要求：能使程序员在其余灵活方便地表示出各类并行性，能在各种并行/向量计算机系统中高效地实现74. 并行进程的特点：这些进程在时间上重叠地执行，一个进程未结束，另一个进程就开始75. 并行任

23、务的派生：使一个任务在执行的同时，派生出可与它并行执行的其他 一个或多个任务，分配给不同的处理机完成76. 多处理机的操作系统：（1）主从型（2）各自独立型（3）浮动型77.第八章 其他系统结构78. 脉动阵列结构的特点：（1） 结构简单、规整，模块化强，可扩充性好，非常适合用超大规模集成电路实现。（2） PE间数据通信距离短、规则，使数据流和控制流的设计、同步控制等均单单规整。（3） 所有PE能同时运算，具有极高的并行性；输入数据能被多个处理单元重复使用，大大减轻了阵列与外界I/O通信量（4） 脉动阵列结构的构形与特定计算任务和算法密切相关，具有某种专用性，限制了应用范围，这对VLSI是不利

24、的。79. 发展通用脉动阵列结构的途径：（1） 通过增设附加的硬件，对阵列的拜年结构和互连方式用可编程开关进行重构（2） 用软件把不同的算法映象到固定的阵列结构上（3） 探寻与问题大小无关的脉动阵列处理方法，以及VLSI去处系统的侵害矩阵算法，使它们可以克服阵列只能求解固定大小题目的缺陷，同时探寻发展适合一类计算问题的通用算法和相应的设置方案。80. 大规模并行处理机MMP：将数百至数万个高性能、低成本的RISC微处理器用互连网络互连组成的系统。81. 机群系统：将多个高性能的工作站或高档微型计算机，使用调整的通信网络加以互连组成的系统。82. 机群系统比起传统的并行处理系统的优点：（1） 系

25、统有高的性能价格比。（2） 系统的开发周期短（3） 系统的可扩展性好（4） 系统的资源利用率高（5） 用户投资风险小（6） 用编程方便83. 数据驱动的数据流方式：只要一条或一组指令所要求的操作数全部全部准备就绪，就可以立即激发相应的指令或指令组执行。84. 数据驱动的数据流方式的特点：没有通常的共享变量的概念，即没有共享存储数据的概念，指令执行顺序只受指令中数据相关性的制约，数据是以数据令牌方式直接在指令之间传递的。85. 控制驱动的控制方式的特点：通过访问共享存储单元让数据在指令之间传递；指令执行的顺序性隐含于控制流中，可以显式使用专门的控制操作符来实现并行处理；指令执行顺序受程序计算机器的控制，即受控制令牌所支配。86. 数据令牌：实质上是一种表示某一操作数或参数已准备就绪的标志。87. 需求驱动计算：按需求值，只有当某一函数需要用到某一自变量时，才驱动对该自变量的求值操作，是一种滞后求值的策略。88. 数据流是基于（1）异步性和（2）函数性的一种计算模型。（1）异步性：是指一旦操作数到齐就开始操作，这是数据流计算机开拓并行性的基础。（2）函数性：是指每一数据流操作都是消耗一组输入值，产生一组输出值而不发生副作用，具有变量出现在赋值语句左边仅一次的单赋值我，从而保证任何两个并发操作可以按任意次序执行