天津师范大学——系统结构期末复习(共15页)

1、精选优质文档-倾情为你奉上第一章1.计算机系统结构的定义：计算机系统结构主要研究软硬件功能分配和对软硬件界面的确定3.透明性概念：本来存在的事物或属性，从某种角度看似乎不存在4.计算机系统的多层次模型：第6级 专用应用语言机器 特定应用用户（使用特定应用语言）（经应用程序翻译成高级语言）第5级 通用高级语言机器 高级语言程序员（使用通用高级语言）（经编译程序翻译成汇编语言）第4级 汇编语言机器 汇编语言程序员（使用汇编语言）（经汇编程序翻译成机器语言、操作系统原语）第3级 操作系统语言机器 操作系统用户（使用操作系统原语）（经原语解释子程序翻译成机器语言）第2级 传统机器语言机器 传统机器程序

2、员（使用二进制机器语言）（由微程序解释成微指令序列）第1级 微指令语言机器 微指令程序员（使用微指令语言）（由硬件译码器解释成控制信号序列）第0级 硬联逻辑 硬件设计员第0级由硬件实现，第1级由微程序实现，第2级至第6级由软件实现，由软件实现的机器称为：虚拟机从学科领域来划分：第0和第1级属于计算机组织与结构，第3至第5级是系统软件，第6级是应用软件。它们之间仍有交叉。第0级要求一定的数字逻辑基础；第2级涉及汇编语言程序设计的内容；第3级与计算机系统结构密切相关。在特殊的计算机系统中，有些级别可能不存在。5. 计算机运算速度评价的主要方法：1）时钟频率（2）指令执行速度MIPS及KIPS、GI

3、PS、TIPS 书P15-16（3）等效指令速度。（CPI (Cycles Per Instruction) 为每条指令所需的平均时钟周期数，IPC为每个时钟周期平均执行的指令条数。）例子：如果浮点开平方操作FPSQR的比例为2%，它的CPI为100 ，其他浮点操作的比例为23% ，它的CPI4.0，其余指令的CPI1.33 ，计算该处理机的 等效CPI。如果FPSQR操作的CPI也为4.0，重新计算等效CPI。解： 等效CPI1100 2 4 231.33 753.92 等效CPI24 251.33 752.00 由于改进了仅占2 的FPSQR操作的CPI，使等效速度提高了近一倍。6.Amd

4、ahl定律的内容及计算（公式： ）书P9-10内容：系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关。其中：Sn全局加速比；To原执行时间（old）；Tn新执行时间（new）；Se被改进部分的局部加速比；Fe被改进部分原执行时间占原来总时间的百分比。8.CPU性能公式：CPU时间=（ICCPI）/频率 书P10-119.存储器访问的局部性原理实质：根据程序运行的最近情况，可以较为精确的预测出最近的将来将要访问哪些指令和数据。(1) 时间局部性：最近访问过的代码在很短的时间内有可能被再次访问；主要对应于循环语句；（2）空间局部性：与刚被

5、访问过的指令或数据相邻的指令或数据有可能马上被访问；主要对应于顺序执行的语句。 访问的局部性原理是构成层次化存储系统的理论基础。10. 计算机系统结构的通用分类：（1） 佛林（Flynn）分类法：按照指令流和数据流的多倍性特征对计算机系统进行分类。具体内容：书7页有图 （1）单指令流单数据流SISD（2）单指令流多数据流SIMD（3）多指令流单数据流SIMD （4）多指令流多数据流SIMD（2） 冯泽云分类法：用最大并行度来对计算机系统进行分类。（3） Handler分类法练习题一、题4 （P32）二、题12 （P33）答案： 一4：(N/M)3Ks 3：(N/M)2Ks 2：(N/M)Ks

6、1：Ks二、Amdahl定律公式，Sn=20/(20-19Fe)用三点作图法作出关系曲线第二章4.操作码优化表示（哈弗曼及扩展编码方法）：计算 书P91-956.CISC与RISC的概念与区别：CISC（复杂指令系统计算机）：增强指令功能，设置功能复杂的指令；面向目标代码、面向高级语言、面向操作系统；用一条指令代替一串指令RISC（精简指令系统计算机）：简化指令功能，只保留功能简单的指令；较复杂的功能用子程序来实现CISC与RISC区别：CISCRISC指令系统复杂庞大简单精简指令数大于200小于100指令格式一般大于4一般小于4寻址方式一般大于4一般小于4指令字长不固定固定32位访存指令不限

7、制Load Store质量使用频率相差很大相差不大指令执行时间相差很大一个机器周期之内优化编译实现难容易代码程度较短较长控制逻辑实现微程序硬连接7.RISC的特点：(1) 简单而统一格式的指令译码。(2) 大部分指令可以单周期执行完成。(3) 只有LOAD和STORE指令可以访问存储器。(4) 简单的寻址方式。 (5) 采用延迟转移技术 。(6) 采用LOAD延迟技术。9.RISC的关键技术：延时转移技术（重点看一下）、指令取消技术、重叠寄存器窗口技术、指令流调整技术、以硬件为主固件为辅10.减少指令平均执行周期CPI是RISC 思想的精华练习题：1、假定要将某一执行部件的执行速度提高到原来的

8、10倍，改进后被改进部件执行时间占系统总运行时间的50。问： (1)改进后获得的加速比时多少？(2)改进前该部件的之下时间占总之下时间的百分比时多少？2、有一台计算机系统可以按功能分为四级，自下向上表示为、。每一级的功能各不相同，每一级的指 令都比其下一级的指令在功能上强M倍，即第I级的一条指令能够完成第I1级的M 条指令的计算量。现若需第I 级的N条指令解释第I1级的一条指令，而有一段第级的程序需要运行Ks，问在第、各级一段功能等效 的程序各需多长时间？3、某模型机共有9条指令，使用频度分别为：0.30 、0.24 、0.06 、0.07 、0.07 、0.02 、0.03 、0.20 、0

9、.01 。该机 具有若干通用寄存器，主存为16位字长，字节编址，采用按整数边界存取，任何指令必须在一个主存周期中取得， 短指令为寄存器寄存器型，长指令为寄存器主存型，主存地址应当能够变址寻址。 (1)、设计优化实用的操作码编码；(2)、最多可以使用多少个通用寄存器(3)、画出两种指令格式，指出主存变址寻 址的最大相对位移量为多少？第三章 看书1.存储器的主要性能指标：速度 容量 价格 2.存储系统（或存储体系、存储层次）的定义两个或两个以上速度、容量和价格各不相同的存储器用硬件、软件、或软件与硬件相结合的方法连接起来成为一个 系统。这个系统对应用程序员透明，并且，从应用程序员看，它是一个存储器

10、，这个存储器的速度接近速度最快的那个存储器，存储容量与容量最大的那个存储器相等，单位容量的价格接近最便宜的那个存储器。3.命中率与存储系统等效访问速度和效率的计算 书133页4.虚拟存储器是由主存储器和磁盘存储器共同组成。4.Cache存储系统：由Cache和主存储器构成5.虚拟存储器的三种地址映像与变换方式：页式虚拟存储器、段式虚拟存储器、段页式虚拟存储器6.cache地址映象：全相联映象、直接相联映象、组相联映象、位选择组相联映象、段相联映象7. 堆栈型替换算法的定义与堆栈模拟图的应用：定义：对任意一个程序的页地址流作两次主存页面数分配，分别分配m个主存页面和n个主存页面，并且有mn。如果

11、在任何时刻t，主存页面数集合Bt都满足关系： Bt（m） Bt（n） 则这类算法称为堆栈型替换算法。堆栈模拟图的应用（计算题）例题：一个虚拟存储系统，采用最久没有使用算法，实存共5页，为2道程序分享，页地址流分别如下P1= 1 2 3 4 1 3 2 1P2= 1 2 3 4 2 2 3 3试作2个实存分配方案，分别使2道程序满足(1)命中率相同；(2)命中次数之和最大。结论如下(1)命中率相同的方案是n1=3而n2=2；(2)命中次数之和最大的方案是n1= 4而n2= 1。8.Cache存储系统工作：基于程序局部性访问原理，是对主存信息的拷贝9.组相联地址映像及其变换（180页图）10.ca

12、che系统的加速比：书P9310.Cache与主存不一致性产生的原因及更新方法：造成Cache与主存的不一致的原因：(1) 由于CPU写Cache，没有立即写主存(2) 由于IO处理机或IO设备写主存Cache的更新算法：(1) 写直达法，又称写通过法，WT（Writethrough）：CPU在执行写操作时，把数据同时写入Cache和主存。(2) 写回法，又称为抵触修改法，WB（WriteBack）：CPU的数据只写入Cache，不写入主存。仅当替换时， 才把修改过的Cache块写回到主存。习题：Cache存储系统中，Cache的访问周期为10ns，主存储器的访问周期为60ns,每个数据在Ca

13、che中平均重复使用4次。当块的大小为1个字时，存储系统的访问效率只有0.5，现在要提高增加块的大小，使存储系统的访问效率达到0.94。1、当存储系统的访问效率为0.5时，计算命中率和等效访问周期；2、为了使存储系统的访问效率达到0.94，命中率和等效访问周期应当为多少？3、为了使存储系统的访问效率从0.5提高到0.94，块的大小至少要增加到几个字？第四章1.IO系统的特点及其相应解决方法输入输出系统的特点集中反映在异步性，实时性，和与设备无关性三项基本要求上，它们对输入输出系统的组织产生决定性影响。实时性反映了不同种类设备对于CPU响应时间的区别，采用层次结构的方法来解决 设备无关性表明了标

14、准接口非标准设备驱动软件的实现途径，采用分类处理的方法来解决。 异步性反映了设备相对于CPU的独立性，采用自治控制的方法来解决。2.输入输出系统的组织方式1. 自治控制：输入输出系统是独立于CPU之外的自治系统，处理机与外围设备之间要有恰当的分工。2. 层次结构：最内层是输入输出处理机、输入输出通道等中间层是标准接口。标准接口通过设备控制器与输入输出设备连接。3. 分类组织：面向字符的设备，如字符终端、打字机等，面向数据块的设备，如磁盘、磁带、光盘等。2.3种基本I/O方式：程序控制输入输出方式、中断输入输出方式、直接存储器访问方式2. 输入输出系统的特点：输入输出系统是处理机与外界数据交换的

15、通道。输入输出系统最典型地反映着硬件与软件的相互结合。3. 中断的定义：当出现来自系统外部，机器内部，甚至处理机本身的任何例外的，或者虽然是事先安排的，但出现在现行程序的什么地方是事先不知道的事件时，CPU暂停执行现行程序，转去处理这些事件，等处理完成后再返回来继续执行原先的程序。4. 中断源：引起中断的各种事件 安排中断优先顺序主要由下列因素来决定：中断源的急迫性。设备的工作速度。数据恢复的难易程度。要求处理机 提供的服务量。 要求：响应速度快，灵活性好。 通过软件设置中断屏蔽码改变中断服务顺序。4.中断处理的流程表示通常用硬件实现 现行指令结束，且没有更紧急的服务请求 ；关CPU中断 ；保

16、存断点，主要保存PC中的内容表示可以用硬件实现，也可以用软件实现 撤消中断源的中断请求 ；保存硬件现场，主要是PSW及SP等 ；识别中断源 ；改变设备的屏蔽状态表示通常用硬件实现 进入中断服务程序入口表示可以用硬件实现，也可以用软件实现 保存软件现场，在中断程序中使用的通用寄存器等表示通常用软件实现 开CPU中断，可以响应更高级别的中断请求 ；中断服务，执行中断服务程序 ；关CPU中断表示可以用硬件实现，也可以用软件实现 恢复软件现场 ；恢复屏蔽状态 ；恢复硬件现场 ；开CPU中断 表示通常用软件实现 返回到中断点必须用硬件实现的有：保存中断点和进 入中断服务程序入口。必须用软件实现的有：中断

17、服务和返回到中断点。5. 中断响应时间：从中断源向处理机发出中断服务请求开始，到处理机开始执行这个中断源的中断服务程序时为止5. 中断屏蔽的两种方法：方法一：每级中断源设置一个中断屏蔽位。方法二：改变处理机优先级使用中断屏蔽位实现中断屏蔽的计算：有四个中断源D1、D2、D3和D4，它们的中断优先级从高到低分别是1级、2级、3级和4级。这些中断源的正常中断屏蔽码和改变后的中断屏蔽码见下表。每个中断源一位，共4位屏蔽码。1表示不允许中断，0表示允许中断中断源名称 中断优先级 正常中断屏蔽码D1 D2 D3 D4 改变后的中断屏蔽码D1 D2 D3 D4D1 1 1111 1000D2 2 0111

18、 1100D33 0011 1110D4400011111解：如果4个中断源都使用正常的中断屏蔽码，处理机的中断服务顺序将严格按照中断源的中断优先级进行。如果改变中断屏蔽码，当D1、D2、D3和D4这4个中断源同时请求中断服务时，处理机实际为各个中断源服务的先后次序就会改变。处理机响应的顺序是D1、D2、D3、D4实际服务的顺序是D4、D3、D2、D1例题2：某处理机共有4个中断源D1、D2、D3和D4，它们的硬件中断优先级从低到高分别为1级、2级、3级和4级。处理机本身的优先级最低，为0级。在中断源D1、D2、D3、D4的中断向量中，程序员为它们设置的优先级分别为4级、3级、2级、1级。解：

19、在处理机状态字中设置3个中断屏蔽位。000为处理机本身的优先级，001100分别表示4个中断源的中断优先级。当4个中断源同时请求中断服务时，8.通道的种类及其工作方式字节多路通道 为多台低中速的外围设备服务，有多个子通道，每个子通道连接一个控制器选择通道 为高速外围设备服务，只有一个以成组方式工作的子通道 数组多路通道 字节多路通道和选择通道的结合。 每次为一台高速设备传送一个数据，并轮流为多台外围设备服务。 从磁盘存储器读出文件的的过程分为三步：定位、找扇区、读出数据。数组多路通道的实际工作方式是：在为一台高速设备传送数据的同时，有多台高速设备可以在定位或者在找扇区。与选择通道相比，数组多路

20、通道的数据传输率和通道的硬件利用都很高，控制硬件的复杂度也高。9.通道传输时间与流量的计算公式字节多路通道的数据传送过程:一个字节多路通道连接 P台设备，每台设备都传送 个字节选择通道的数据传送过程：选择通道连接 P 台设备，每台设备都传送 个字节数组多路通道的数据传送过程:数组多路通道连接P 台设备，每台设备都传送 个字节10. 通道流量分析：书P243 练习题：1、某处理机有4个中断源，分别为D1、D2、D3、D4。要求处理机响应中断源的中断请求次序从高到低依次为D1、D2、D3、D4，而处理机实际为各个中断源服务的先后次序为D3、D2、D1、D4。每个中断源有四位中断屏蔽码，其中“0”表

21、示开放中断，“1”表示该中断被屏蔽。（1） 试设计各中断源的中断优先级和中断屏蔽码； （2） 如果处理机在运行主程序时，同时有D1、D2两个中断源请求中断服务，而在运行中断源D2的中断服务程序的过程中，中断源D3、D4又同时请求中断服务，试画出处理机响应各个中断源的中断服务请求和实际运行中断服务程序过程的示意图。 2 、如果某通道在数据传送过程中，选择设备需要9.8us，传送一个字节需要0.2us，某个低速设备每隔500us发出一个字节传送请求，问该通道至多可接几台这种低速设备？对于如下A-F六种高速设备，一次通讯传送的字节数不少于1024 个字节，问哪些设备可以挂接在此通道上，那些不能？ 3

22、 、书p251 第五章1.指令重叠的执行方式：1.顺序执行方式2.一次重叠执行方式3.二次重叠执行方式2.采用先行控制方式的处理机结构3.各缓冲栈的作用1.先行指令缓冲栈：处于主存储器与指令分析器之间，用它来平滑主存储器取指令和指令分析器使用指令之间的速度差异2.先行操作栈： 处于指令分析器和运算控制器之间，使指令分析器和运算器能够各自独立工作。采用先进先出方式工作，由指令寄存器堆和控制逻辑组成。3.先行读数栈 处于主存储器与运算器之间，平滑运算器与主存储器的工作。每个缓冲寄存器由地址寄存器、操作数寄存器和标志三部分组成。也可以把地址寄存器和操作数寄存器合为一个。 当收到从指令分析器中送来的有

23、效地址时，就向主存申请读操作数。读出的操作数存放在操作数寄存器中或覆盖掉地址寄存器中的地址。4.后行写数栈 每个后行缓冲寄存器由地址寄存器、数据寄存器和标志三部分组成。指令分析器遇到向主存写结果的指令时，把形成的有效地址送入后行写数栈的地址寄存器中，并用该地址 寄存器的编号替换指令的目的地址部分，形成RR*指令送入先行操作栈。当运算器执行这条RR*型写数指令时，只要把写到主存的数据送到后行写数栈的数据寄存器中即可。3. 先行控制技术的关键是缓冲技术和预处理技术4. 线性流水线：每一个流水段都流过一次，而且仅流过一次5. 非线性流水线：某些流水段之间有反馈回路或前馈回路。4.流水线的三个主要性能

24、指标的定义及计算 书P285-294主要指标：吞吐率、加速比和效率5. 非线性流水线的无冲突调度算法 书P294-300线性流水线能用流水线连接图唯一表示，对于非线形流水线，连接图不能唯一表示工作流程，需要引入流水线预约表启动距离：连续输入两个任务之间的时间间隔例题：一条4功能段的非线性流水线，每个功能段的延迟时间都相等，它的预约表如下：(1)写出流水线的禁止向量和初始冲突向量。(2)画出调度流水线的状态图。(3)求最小启动循环和最小平均启动距离。(4)求平均启动距离最小的恒定循环。解：(1)禁止向量为： (2，4，6)初始冲突向量：S = (2)构造状态图S逻辑右移2、4、6位时，不作任何处

25、理，逻辑右移1、3、5和大于等于7时：S右移1位之后： ，S右移3位之后： ，S右移5位之后： ，S右移7位或大于7位后还原到它本身。右移5位之后：，右移3位之后：，右移5位之后：。简单循环：状态图中各种冲突向量只经过一次的启动循环。(3)最小的启动循环为 （1，7）和（3，5）,平均启动距离为4。(4) 启动距离最小的恒定循环为（5）6.数据相关与控制相关的概念数据相关：在执行本条指令的过程中，如果用到的指令、操作数、变址量等是前面指令的执行结果，这种相关称为数据相关。控制相关：由条件分支指令、转子程序指令、中断等引起的相关。7.超标量处理机的概念有两条或两条以上能同时工作的指令流水线，超标

26、量处理机采用的是空间并行性。（先行指令窗口：能够从指令Cache中预取多条指令，能够对窗口内的指令进行数据相关性分析和功能部件冲突检测，保存暂时不能进入操作部件的指令。先行指令窗口的作用类似于先行指令缓冲栈，典型大小为28条指令。超流水线处理机：在一个周期内分时发射多条指令的处理机，超流水线处理机采用的是时间并行性。）超标量超流水线处理机：一个时钟周期发射m次，每次发射n条指令三种处理机的性能关系：超标量处理机的相对性能最高，其次超标量超流水处理机，超流水线处理机的相对性能最低9.顺序与乱序的概念 多流水线的调度主要有三种方法：顺序发射顺序完成、顺序发射乱序完成、乱序发射乱序完成 指令发射顺序

27、是按照程序中指令排列顺序进行的称为顺序发射。指令完成顺序是按照程序中指令排列顺序进行的称为顺序完成习题：1、 一个15000条指令的程序在一台时钟频率为25MHZ的线性流水线处理机上运行，假设该流水线分为相等的5段，并且每个时钟周期发射一条指令，忽略由于转移指令和数据相关造成的损失。（1） 、使用该流水线执行这个程序，并用流过延迟时间与其相等的一个等效非流水线处理机执行同一程序。两者相比较，加速比是多少？（2）、计算该流水线的效率和吞吐率。解：(1)等效非流水线处理机执行一条指令需要5个时钟周期，依照加速比的定义：S=n*k/(k+n-1)=15000*5/(5+15000-1)=75000/

28、15004=4.9986(2)流水线的效率：E=n*k/(k*(k+n-1)=15000/15004=0.9997吞吐率：TP=n*f/(k+n-1)=15000*25M/(k+n-1)=24.99MIPS2、一个5段流水线处理机的预约表如下：1、列出禁止向量和冲突向量2、画出状态转移图3、列出所有简单循环，指出最小启动循环及其启动距离4、计算该流水线的最大吞吐率5、指出最小恒定循环，计算相对应的吞吐率解：(1)禁止向量（3，4，5），冲突向量（11100）(2)状态转移图(3)简单循环(1,1,6),(2.6),(6),(1,6),最小启动循环（1，1，6），启动距离2.67(4)最大吞吐率

29、:设该流水线时钟周期为t，则Tp=3/8t(5)最小恒定循环为6，相对应的吞吐率Tp=1/6t第七章1.互连网络主要特性（了解）特性：(1)网络规模：网络中结点的个数 (2)结点度：与结点相连接的边数称为结点度，进入结点的边数叫入度， 从结点出来的边数则叫出度 (3)距离：两个结点之间相连的最少边数 (4) 网络直径：网络中任意两个结点间距离的最大值。用结点间的连接边数2.互联网络传输的性能参数：(1)频带宽度 (Bandwidth)：传输信息的最大速率(2)传输时间 (Transmission time)：等于消息长度除以频宽。(3)飞行时间 (Time of flight)：第一位信息到达

30、接收方所花费的时间。(4)传输时延 (Transport latency)：等于飞行时间与传输时间之和。(5)发送方开销 (Sender overhead)：处理器把消息放到互连网络的时间。(6)接收方开销 (Receiver overhead)：处理器把消息从网络取出来的时间。3.互连网络的种类：1 静态互连网络2 循环互连网络3 多级互连网络4 全排列互连网络5 全交叉开关网络4.6种基本互连函数的定义与计算（计算）书P395例6.2：假设16个处理机的编号分别为0、1、15，采用单级互连网络。互连函数分别为：(1)Cube3(2)PM2+3(3)PM2-0(4)Shuffle(5)But

31、terfly (6)Reversal第12号处理机分别与哪一个处理机相连？解：(12)10下= (1100)2下1100最高位取反得0100，4号处理机(12 + 8) MOD 16 = 4，4号处理机12 1 = 11，11号处理机1100循环左移1位得到1001, 9号处理机1100的最高最低位交换0101, 5号处理机1100的位序反过来为0011, 3号处理机13.多级立方体网的构成及工作原理 习题1：有编号为031共32个处理机，分别计算下列互连函数（E：交换函数；S：混洗函数；B：蝶式函数；PM2I：移数函数；自变量为10进制处理机编号）。第八章并行性的两种类型和三种技术途径两种并

32、行性概念：(1)同时性并行Simultaneity：两个或两个以上事件 在同一时刻发生。(2)并发性并行Concurrency：两个或两个以上事件在 同一时间间隔内发生。三条技术途径：(1)资源重复：重复设置多个部件来提高速度。(2)时间重叠：流水线(3)资源共享：分时系统，分布式系统并行处理机的定义：多个处理部件PU按照一定方式互连，在同一个控 制部件CU控制下，对各自的数据完成同一条指令规定 的操作。从CU看，指令是串行执行的，从PU看，数据 是并行处理的。并行处理机也称为阵列处理机，按照按照佛林分类法，它属于SIMD处理机。并行处理机的两种分类及其结构分类：分布存储器并行处理机和共享存储

33、器并行处理机 分布式存储器并行处理机的结构框图 共享存储器并行处理机的结构框图第九章多处理机的定义与特点多处理机定义：两个或两个以上处理机(包括PU和CU)，通过高 速互连网络连接起来，在统一的操作系统管理下， 实现指令以上级（任务级、作业级）并行。多处理机系统的特点1. 结构灵活并行处理机：专用，PE数多，固定有限通信多处理机： 通用，PE数少，高速灵活通信2. 程序并行性并行处理机的并行性存在于指令内部，识别比较容易。 多处理机的并行性存在于指令外部，在多个任务之间，识 别难度较大。一个简单的例子：Y = A+B*C*D/E+F，用两个处理机计算：CPU1：B*C， A+F， A+B*C*

34、D/E+FCPU2：D/E， B*C*D/E，3. 并行任务派生并行处理机把同种操作集中，由指令直接启动各PE同时工 作。多处理机用专门的指令来表示并发关系，一个任务执行时 能够派生出与它并行的另一些任务。如果没有空闲处理机，任务进入排队器等待。4. 进程同步并行处理机仅一个CU，自然是同步的。多处理机中，各处理机执行不同的指令，工作进度不会也不必保持相同。先做完的要停下等待。有数据相关和控制相关也要停下等待。要采取同步措施来保持程序要求的正确顺序5. 资源分配和进程调度并行处理机的PE是固定的，用屏蔽来改变实际参加操 作的PE数目。多处理机执行并发任务，需用处理机的数目不固定， 各处理机进出

35、任务的时刻不相同，所需共享资源的品种、数量随时变化。多处理机基本模型及其结论多处理机运算的基本模型目标：由M个任务组成的程序，在N台处理机组成的系统上运行，求最短执行时间？基本模型仅考虑由两台处理机组成的系统。假设：1、每个任务的执行时间R；2、不在同一个处理机上的两个任务需要相互通讯，每次通讯时间为C。总处理时间R*Max(MK，K)C*(MK)*K其中：R：每个任务的执行时间，C：通信开销，K：任务分配参数。通信时间C(M-K)K是一个开口向下的二次函数，任务执行时间是两根相交的直线，最小值发生在中间即 K=M/2令：通讯时间执行时间则 R*M/2=C*M/2*(M-M/2)则 R/C=M

36、/2当通信时间比较大时(R/CM/2)，总时间的最小值发生在中点 (K=M/2)。总时间最短的结论：1、当R/CM/2时，把所有任务分配给同一台处理机，K0；2、当R/CM/2时，把任务平均分配给两台处理机，KM/2。N台处理机系统的基本模型要解决的问题：把M个任务分配给N台处理机，求总处理时间的最小值。T=Rmax(Ki)+C/2Ki(M-Ki)与两台处理机的情况类似，实际的最小值发生在极端分配 情况下：或者将所有的任务集中在一台处理机上，或者将任务平均分配给所有处理机。M不是N的整数倍，如何平均分配？：例1：个任务平均分给台处理机：例2： 11个任务平均分给台处理机：M个任务分配给N台处理

37、机的最佳分配方法：1、 M是N的整数倍，平分2、 M是N的整数倍， 台处理机，每台 个任务如果M/N0，则：另外有1台处理机分得剩下的 个任务；剩下的 台处理机不分配任何任务。例如：101个任务平均分给50台处理机：有33台处理机，每台分给3个任务；另有台处理机分给个任务；剩下的16台处理机不分配任务。假设Ki 个任务分给了第台处理机：第一项求出N台处理机中最大执行时间；第二项计算出Ki 与（MKi ）任务之间两两通信的开销 时间，它是关于Ki 的二次函数。Ki最多有3个取值： 、 和0当M 是N 的倍数时，单台处理机执行全部M个任务的总时间：总处理时间RM使两者差为0，得到R/C=M/2结论

38、：当R/CM/2时采用平均分配方法， 当R/CM/2时采用集中分配方法。总结上面几个模型，可以得出如下结论：(1)多处理机系统结构所需的额外开销，包括调度，对 共享资源的竞争、同步、处理机之间通信等。(2)当处理机台数增加时，额外开销时间也增加。有 时，额外开销的增加可能比处理机数目的线性增加更 快。(3)R/C比值越大，越有利于计算过程。如果采用粗粒 度，能够获得较大的R/C比值；但是并行程度将大为降 低。 (4)为了使价格和性能都比较合理，处理机数目存在一 个极大值，这个值主要依赖于机器的系统结构、基本 技术（尤其是通信技术）和具体的应用问题。粒度与并行的关系并行性在很大程度上依赖于R/C

39、比值，R/C是衡量任务粒度(Granularity)的尺度，其中：R: 程序执行时间，C: 通信开销细粒度并行：R/C小，通信开销大,并行度低。粗粒度并行：R/C大，通信开销小,并行性高。多机任务平均分配的方法（没找到）多处理机Cache间不一致的原因、两种协议、监听协议的两种方法、写一次协议的内容出现不一致性问题的原因有三个：共享可写的数据、进程迁移、I/O传输有两类解决Cache不一致性问题的协议：在总线互连的多处理机系统中，通常采用监听协议。在其他多处理机系统中，通常采用基于目录协议。使用监听协议，有两种方法：方法一：写无效（Write Invalidate）策略，在本地 Cache的数据块修改时使远程数据块都无效。方法二：写更新（Write Update）策略，在本地Cache 数据块修改时通过总线把新的数据块广播给含该块的所 有其他Cache采用写无效或写更新策略与Cache