计算机系统结构课件

计算机系统结构由赵斯琴制作参考教材:

徐炜民，严允中编著，计算机系统结构（第3版），电子工业出版社。教材讲述了计算机系统结构的基本概念、设计原理和分析方法。第一章计算机系统结构设计基础1.1计算机系统结构的含义和分类计算机系统性能有了提高，但价格下降。原因：器件技术不断发展；系统结构的改进。其中计算机系统结构的改进对性能的提高有着不容忽视的作用。1.1.1计算机系统结构的含义G.M.Amdahl指出：计算机系统结构是指程序设计员所看到的计算机的基本属性，即概念性结构和功能特性。是计算机系统结构的外特性。从计算机系统的层次结构上考虑，不同级的程序设计者所看到计算机属性是不一样的。用虚拟计算机观点定义计算机系统的功能层次系统总体分析M7：系统分析：问题分析—建立数学模型—设计应用系统所完成的功能观察者身份大致划分系统总体分析员M6：应用程序系统：服务请求——编译或解释——信息处理系统高级程序员（用户）应用软件M5：高级语言计算机：高级语言——编译或解释——运行程序程序员M4：汇编语言计算机：汇编语言——编译或解释——运行程序程序员M3：操作系统：键盘命令OS原语——操作系统——运行程序操作员M2：机器语言计算机：指令系统——CPU——机器程序机器语言程序员系统软件M1：微程序控制：机器指令时序——微程序控制——寄存器传送门M0：硬联逻辑：微程序时序——硬联逻辑——译码网络硬件设计员硬件设计员计算机系统结构的外特性包含的内容指令系统数据表示寻址方式寄存器构成定义中断系统存储体系和管理I/O系统机器工作状态的定义和切换信息保护计算机系统结构的内部特性——计算机组成内部特性是由硬件和固件实现的。也称为计算机组成，是计算机系统结构的逻辑实现，包括机器内的数据通道和控制信号的组成及逻辑设计，着重于机器级内各事件的时序方式与控制机构、各部件功能及相互联系。计算机实现是指计算机组成的物理实现，包括处理器、主存部件的物理结构，器件的集成度和速度的确定；芯片、模块、插件、底板的划分与连接；微组装及整机装配技术；专用芯片的设计以及信号传输、电源、冷却方法等。例如：指令系统功能的确定属于系统结构的外特性；而指令的实现，如取指、取操作数、运算、送结果等具体操作及其时序属于组成；而实现这些指令功能的具体电路、器件设计及装配技术等属于实现。1.1.2计算机系统结构的分类由于计算机系统的基本工作过程是执行一条指令的序列，对一组数据进行处理，因此Michael.J.Flynn提出按指令流和数据流的多倍性对计算机系统结构分类。指令流：机器执行的指令序列；数据流：由指令流调用的数据序列；多倍性：在系统中最受限制的部件上，同时处于同一执行阶段的指令或数据的最大个数。按Flynn分类方法分为：单指令流单数据流（SISD）、单指令流多数据流（SIMD）、多指令流单数据流（MISD）、多指令流多数据流（MIMD）.SISD结构只要指令部件一次只对一条指令进行译码并且只对一个执行部件分配数据。可以有多个存储体和多个执行部件。可以是流水线的，可以有一个以上功能部件，所有功能部件均由一个控制部件管理。CUPUMMISISDSSIMD结构以并行处理机（阵列处理机）为代表。同一个控制部件管理下，由多个处理单位PU,所有PU均接受从控制部件来的同一条指令。操作对象是来自不同数据流的数据组。CUPU1M1ISISDS1M2Mm…PU2DS2…PUnDSnMISD结构宏流水线中，每个处理器的结果是下一个处理器的输入操作数。CU1PU1M1IS1IS1DSM2Mm…PU2DS…PUnCU2IS2IS2IS1IS2CUnISnISnISn……MIMD结构大多数多处理机系统和多计算机系统可以归为这一类。多处理机之间有相互作用，因为所有数据来自所有处理机共享的同一个空间。CU1PU1IS1PU2…PUnCU2IS2IS1IS2CUnISnISn…M1DS1M2Mm…DS2DSn用最大并行度分类美籍华人冯泽云（Tse-yunFeng）提出用最大并行度对计算机系统进行分类最大并行度Pm是指计算机系统在单位时间内能够处理的最大二进制位数。最大并行度Pm=n·m,n表示同时处理时一个字中的二进制位数；m表示能同时处理的字数。按计算机对数据处理方式，则Pm值有下列4种类型。字串位串（WSBS）,n=1,m=1字串位并（WSBP）,n>1,m=1字并位串（WPBS）,n=1,m>1(即位片处理)字并位并（WPBP）,n>1,m>1(即全并行处理)按“并行级”和“流水线”分类WolfgangHandler根据计算机系统硬件结构的并行程度和流水线处理程度进行分类，着重于处理器控制部件（PCU）、算术逻辑部件（ALU）和位级电路(BLC)的并行-流水线处理。PCU可视作一个处理机或一个CPU；ALU相当于SIMD的处理单元（PE）；BLC对应于在ALU中进行一位运算所需的组合逻辑电路。一个计算机系统C可由6个独立项目组成的三元组描述为如下：T(C)=(K×K’,D×D’,W×W’)K为PCU数；K’为可组成流水线的PCU数；D为ALU(或PE)数；D’为可组成流水线的ALU数；W为ALU(或PE)的字长；W’为一个ALU(或PE)中的流水线段数1.2计算机系统的设计方法1.2.1软、硬件取舍的基本原则系统结构设计的主要任务是进行软、硬件功能分配和给用户提供机器级软硬界面。相同功能可以设计成软件或硬件把功能设计成硬件时，可以提高运算速度，减少存储容量，但提高硬件成本降低硬件利用率和系统的灵活性和适应性；把功能设计成软件时，可以降低硬件成本，提高系统的灵活性和适应性；但运算速度会下降，存储容量要增大，软件研发费用增加。因此，软、硬功能分配比例应该考虑现有的硬件和芯片条件下，争取系统有高的性能和价格比。1.2.2计算机系统设计的定量原则1.加快经常性事件的速度最重要的也是最广泛采用的设计原则。加快处理频繁出现事件对系统的影响比加速处理很少出现事件的影响大。2.Amdahl定律系统中对某一部件采用某种更快执行方式所能获得的系统性能改进程度，取决于这种方式被使用频率，或所占总执行时间的比例。Amdahl定义了加速比Te,To为采用某种增强功能措施后完成某一任务所需时间和不采用任何增强功能措施完成同一任务所需时间。fe为可采用增强功能措施的部分所占百分比Re采用增强功能措施比不采用增强功能可加快执行的倍数。例若考虑将系统中某一功能的处理速度加快10倍，但该功能的处理使用时间仅为整个系统运行时间的40%，则采用此增强功能方法后，能使整个系统性能提高多少？fe=40%，re=10Sp=1/((1-0.4)+0.4/10)=1.56设求浮点数平方根FPSQR的操作占整个测试程序执行时间的20%。一种实现方法是采用FPSQR硬件，使其速度加快10倍；另一种实现方法是使用所有浮点数指令FP速度加快2倍，同时设FP指令占整个程序执行时间的50%。请比较两种实现方法的优劣。3.

CPU性能公式CPU性能取决于3个要素：时钟频率f，每条指令时钟周期数和指令条数IC。时钟周期T=1/f。CPU时间=CPU时钟周期总数*时钟周期T若Ii是i指令在程序中的条数，CPIi为i指令的平均时钟周期，n为程序中指令的种类数，可以把CPU时间表示为每条指令平均时钟周期数CPI=CPU时钟周期总数/指令条数IC经代换，可得CPU时间=CPI*IC*T例：假设有两台机器A和B，对条件转移采用不同的方法。CPUA采用比较指令和条件转移指令处理方法，CPUB采用比较指令和条件转移指令合一方法。

在CPUA上，若条件转移指令占总执行指令数的20%，比较指令也占20%。CPUB的时钟周期比CPUA慢25%。若规定两台机器执行条件转移指令需2T，其它指令需要1T。现比较CPUA和CPUB哪个工作速度更快？解：CPU时间=CPI*IC*TCPIA=

20%*2+80%*1=1.2CPUA时间=CPIA*ICA*TA=1.2*ICA*TA

在B内，ICB=ICA-20%*ICA=

80%*ICA转移指令的比重是(20%*ICA)/

(80%*ICA)=25%其它指令比重是1-25%=75%CPIB=

25%*2+75%*1=1.25TB=1.25*TACPUB时间=CPIB*ICB*TB=1.25*(0.8*ICA）

*(1.25*TA)=1.25*ICA*TA

CPUA时间<CPUB时间若CPUB的条件转移指令比CPUA慢25%，比较CPUA和CPUB哪个工作速度更快？除了CPU时间之外，MIPS(每秒百万次指令)和MFLOPS(每秒百万次浮点运算)也是比较常用的计算机性能评估标准。ICF表示浮点运算次数4.程序访问的局部性原理程序访问的局部性是指程序执行中，呈现出频繁重新使用那些最近已被使用过的数据和指令的规律。统计表明一个程序执行时间中的90%是花费在10%的程序代码上。主要反映在时间和空间局部性两个方面。它是按层次构成存储体系的主要依据。1.2.3计算机系统设计的任务1.确定用户对计算机系统功能、价格和性能的要求功能要求有：应用领域，专用还是通用软件兼容层次，如，在程序设计语言层次，只需要有新的编译器；在目标代码层次，则系统完全确定，像系列机操作系统要求标准，数据表示、接口、总线、网络等等标准2.软件和硬件的平衡3.符合未来发展方向1.2.4计算机系统的设计步骤计算机系统从概念上和功能上可看做是一个多级构成的层次结构，从哪个层开始设计，对设计步骤是有影响的。通常有3种不同的设计思路：“由上往下”，“由下往上”，“由中间开始”。系统结构设计步骤如下：1.需求分析2.需求说明3.概念设计4.具体设计5.设计优化和评价1.3计算机系统结构的发展VonNeumann结构改进的VonNeumann结构器件发展对系统结构的影响应用对系统结构的影响软件、算法对系统结构的影响计算机系统结构的演变第2章数据表示和指令系统2.1数据表示数据类型是指一组值的集合及其上实施的操作的集合。数据表示指的是能由硬件直接辨认的数据类型。数据结构是指结构数据类型的组织方式。它反映了在应用中所用到的各种数据元素或信息单元之间的结构关系。数据结构要经过软件映像，变换成按地址访问一维存储器内的各种数据表示。计算机的数据表示如何确定是一个复杂的问题。基本的数据类型有逻辑（布尔）数，定点数（整数），浮点数（实数），十进制数，字符串，数组等。对这些基本数据类型有码制的选择，如原码、反码、补码、移码等，以及基值、位长等。关系到硬件实现的难易程度和数据表示范围以及数据表示的精度等问题。除了基本的数据表示之外，数据表示的确是关系到软、硬件的分配问题。00阶符尾符·例1假设正阶、正尾数浮点数的表示为如下图阶码相同，均为二进制。尾数基值rm=2和rm=16两种不同值时，浮点数的表示范围不同。采用规格化表示。最小阶码为0；最大阶码为22-1=3。rm=2时，最小尾数为2-1；最大尾数为1-2-4；正浮点数的表示范围是20*2-1到23*（1-2-4）。rm=16时，4位2进制数组成一个16进制数，最小尾数为16-1；最大尾数为1-16-1；正浮点数的表示范围是160*16-1到163*（1-16-1）。浮点数的下溢处理尾数下溢主要产生于加法中的对阶、规格化右移以及在乘法中的取单倍长度的乘积。常用的处理方法有：截断舍入法恒置“1”法ROM或PLA舍入法，又称查表舍入法例2衡量某种数据表示的是否合适，首先要看这种数据表示对完成任务时间和所需存储容量的影响。假设有两个200*200元素（定点数）的阵列A和B进行相加运算。若用PL/1语言仅需一条语句，经优化编译形成6条机器指令，其中4条需要循环40000次。若机器有阵列型数据表示，则只需要1条机器指令就能完成2个矩阵的相加。衡量某种数据表示的是否合适，还要看其通用性和利用率。2.2指令及其优化指令系统是计算机所有指令的集合。程序员用各种语言编写的程序都要翻译成（编译或解释）以指令形式表示的机器语言后才能运行。它是反映了计算机的基本功能，是硬件设计人员和程序设计人员都能见到的机器的主要属性。指令由地址码和操作码组成。随着指令类型的不同，对地址码的长度要求变化很大。同一个计算机中，可以有1Byte,2Byte,3Byte,4Byte等多种长度的指令。指令优化指令格式的优化指的是如何用最短的位数来表示指令的操作信息和地址信息，使程序中指令的平均字长最短。因此指令格式的优化包括操作码的优化和地址码的优化两部分。2.2.1

操作码的优化操作码的表示方法通常有三种，等长操作码，Huffman编码法和扩展编码法，下面分别介绍。等长操作码对于采用等长操作码的指令系统，若指令系统中共有N种不同功能的指令，则指令系统中的所有指令的操作码长度固定为┌log2N┐位。等长操作码的操作码长度规整，有利于简化硬件设计，减少指令译码时间。如IBM370指令系统，指令操作码的长度固定为8位。从压缩代码的观点出发，希望常用指令的操作码短些。用哈夫曼（Huffman）码制压缩的基本概念：出现概率最大的指令用最少的位来表示，而概率较小的指令用较多的位来表示，达到使平均位数缩短的目的。要采用Huffman编码法表示操作码，必须先知道各种指令在程序中出现的概率，这通常可以通过对已有典型程序进行统计得到。例现设有一台模型机，共有10种不同功能的指令，各指令的使用频度如表2.1所示。若用等长的操作码表示需用4位。指令序号指令使用频度pi指令序号指令使用频度piI10.17I60.09I20.15I70.08I30.15I80.07I40.13I90.03I50.12I100.01用哈夫曼压缩概念进行编码的步骤（1）将要编码的指令按出现概率的次序排列，频率相同的指令可任意排列。（2）把出现概率小的两个指令合并，并将其频率相加，按相加后的频率次序重新排序。（3）继续（2）的过程，直至只剩下两个频率。（4）对最后两个频率分别指定代码0和1（或1和0）。（5）若某一频率由两个频率相加而成，则分别指定这两个频率的下一个代码为0和1（或1和0）。（6）继续（5）的过程，直到所有指令均已指定不同代码为止。举例说明哈夫曼编码。哈夫曼树将所有的指令按频率由小到大排序，每次选择其中最小的两个频率合并成（求和）一个新的结点，然后把它作为叶结点。一个新的结点和其它的叶结点再按频率大小排序。如此重复，直至全部频率都处理完毕最后形成一个频率为1的根结点。此后，由根结点开始向下延伸，对两个分支分别用一位“1”或“0”（或相反）来表示，直至遍历所有的叶结点为止。把上述例子用哈夫曼数编码，如下图。构造的Huffman树以及各指令的Huffman编码均不是唯一的，但采用Huffman编码的操作码的平均长度是唯一的。

pi•li=0.17×2+（0.15+0.15+0.13+0.12）×3+（0.09+0.08+0.07）×4

+（0.03+0.01）×5=3.15位扩展哈夫曼码为了使指令操作码规整，用扩展哈夫曼码。Huffman编码法是最优化的编码方法，但这种编码方法形成的操作码很不规整，10种指令就有4种不同的操作码长度，既不便于译码，也不实用。所以，在此基础上再结合采用等长操作码的编码方法，可以得到扩展操作码编码。扩展操作码编码是介于等长操作码编码和Huffman编码之间的一种编码方式，使操作码的长度只限于有限的几种码长（如这里只有两种码长）。为便于实现和分级译码，一般采用等长扩展。把上述例子用扩展哈夫曼数编码。若采用2-4等长扩展操作码编码，其操作码的平均码长为：

pi•li=（0.17+0.15）×2+（0.15+0.13+0.12+0.09+0.08+0.07+0.03+0.01）×4=3.36位比较一下3种编码方式，即直接用二进制编码，哈夫曼编码方式，扩展哈夫曼编码方式的操作码的平均长度。不同的扩展标志对于等长扩展码，根据采用不同的扩展标志还可以有多种不同的扩展方法。例如，对于4-8-12位扩展码，有采用每次保留一个码点标志的15/15/15编码法，也有采用每次保留一个标志位的8/64/512编码法。2.2.2地址码的优化只是有了操作码的优化表示，而没有在地址码表示和寻址方式方面采取相应的措施，程序所需总位数还是难以减少的。如果主存是按位编址，操作码的优化表示会直接带来程序所需总位数的减少。然而，有些指令却需2个主存周期才能读出，这会使机器速度明显下降。为了不降低访存取指令的速度，就要维持指令字按整数边界存贮。那么如何发挥操作码优化表示的作用呢？显然只有地址也是可变长的，才能用得上空白部分，如图所示。若要充分利用空白浪费空间，就必须对地址码部分进行优化。操作码空白浪费地址码短操作码空白浪费地址码长操作码地址码地址码的优化有四种方法不允许指令字跨边界存储。配合操作码长度调整地址码长度。改变指令中地址码长度和地址数，设计单地址、双地址、三地址指令。设法利用指令中空白处，存放立即数或常数。例一台模型机共有7条指令，各指令的使用频度分别为35%，25%，20%，10%，5%，3%，2%。该模型机有8位和16位两种指令字长，采用2-4扩展操作码。8位字长指令为寄存器-寄存器（R-R）二地址类型，16位字长指令为寄存器-存储器（R-M）二地址变址寻址（-128<=变址范围<=127）类型。(1)设计该机的两种指令格式，标出各字段位数并给出操作码编码。(2)该机允许使用多少个可编址的通用寄存器，多少个变址寄存器？(3)计算操作码的平均码长。解：(1)7条指令的2-4扩展操作码编码如表所示。指令号指令的使用频率2-4扩展操作码编码135%00225%01320%10410%110055%110163%111072%1111为了加快使用频率高的指令的执行速度，设计时，让操作码长度只有2位的3条指令的操作在通用寄存器之间进行，而其它的指令则在寄存器和存储器之间进行。由于R-R型指令长度为8位，操作码占2位，因此源、目的寄存器编码部分各占3位，其格式如下：R-R型：操作码OP源寄存器Rs目的寄存器Rd2位3位3位由变址寻址的位移量范围(-128～+127)可知，R-M型指令格式中偏移地址占8位，由于操作码占4位，源寄存器编码占3位，R-M型指令长度为16位，因此变址寄存器的编码只占1位，R-M型指令格式如下：R-M型：操作码OP源寄存器Rs变址寄存器Rx偏移地址4位3位1位8位(2)根据(1)中设计的指令格式，通用寄存器编码占3位，变址寄存器编码占1位可知：该机允许使用8个可编址的通用寄存器和2个变址寄存器。(3)根据表2.4可计算操作码的平均码长为：

pi•li=（0.35+0.25+0.2）×2+（0.1+0.05+0.03+0.02）×4=2.4位2.2.1寻址方式分析寻址是指如何确定数据地址和转移指令的下一条要执行的指令的地址。每一条指令的寻址方式由指令本身确定，或按某些预先约定规则进行。有按地址访问、按内容访问、按堆栈访问等访问方式，还可以是按立即数方式。不同计算机的寻址方式也各不相同。常用的寻址方式有立即数寻址，寄存器寻址，直接寻址，间接寻址，基址寻址，变址寻址，相对寻址等。寻址方式有多种，相应地，一条指令的实现也有多种。指令系统的分析指令系统的设计主要是确定它的指令格式、类型、操作以及操作数的访问方式。硬件价格的下降，指令系统逐步扩充，指令功能也逐步增强。指令系统的改进是围绕着缩小与高级语言的语义差异以及有利于操作系统优化而进行的。通过操作码扩展、各种各样的寻址方式、可变的指令长度来设计复杂指令。指令系统从早期的简单形式，逐步发展为多种寻址方式、多种数据格式的复杂指令集，这是为了提高计算机功能以满足用户日益增长的需求。IBM370计算机上用不同语言编写的程序所出现的指令的频度做了统计，经分析得出，程序的80%是存取、转移、算术逻辑运算等简单指令，而复杂指令的使用仅占20%。但为复杂指令而设计的微程序却占微程序ROM的80%。复杂指令增加而使CPU结构趋于复杂，对编译程序的优化好处不大。第3章存储系统结构并行主存系统主存系统的类型1.主存系统的类型根据主存中存储体的个数，以及CPU访问主存一次所能读出的信息的位数，可以将主存系统分为以下四种类型：(1)单体单字存储器，即存储器只有一个存储体，而且存储体的宽度为一个字。如图3.1所示是一个字长为W位的单体主存，一次可以访问一个存储器字，所以主存最大频宽Bm=W/TM。假设，此存储器字长W与CPU所要访问的字（数据字或指令字，简称CPU字）的字长W相同，则CPU从主存获得信息的速率就为W/TM。我们称这种主存是单体单字存储器。W位地址寄存器读出寄存器图3.1单体单字存储器

(2)单体多字存储器，即存储器只有一个存储体，但存储体的总线宽度较大，可以是多个字，如图3.2所示。若要想提高主存频宽Bm，使之与CPU速度匹配，显然可以想到，在同样的器件条件（即同样的TM）下，只有设法提高存储器的字长W才行。例如，改用图3.2的方式组成，这样，主存在一个存储周期内就可以读出4个CPU字，相当于CPU从主存中获得信息的最大速率提高到原来的4倍，即Bm=4W/TM。我们称这种主存为单体多字存储器。地址寄存器W位单字长寄存器W位W位W位W位

图3.2单体多字（m=4）存储器(3)多体单字交叉存取的存储器。如：多体交叉存储器，因为每个存储体都是一个CPU字的宽度。

(4)多体多字交叉存储器。它将多分体并行存取与单体多字相结合。我们将能并行读出多个CPU字的单体多字、多体单字交叉、多体多字交叉存取的主存系统称为并行主存系统。2.单体多字方式与多体单字交叉方式的区别(1)单体多字方式要求可并行读出的m个字必须是地址顺序排列且处于同一主存单元。

(2)而主存采用多体单字方式组成，即采用m个存储体交叉编址，多个存储体并行进行存取操作，每个存储体的宽度一般是一个字的宽度。其所花费的器件和总价格并不比采用单体多字方式的多多少，但其实际带宽却可以比较高。这是因为多体单字方式只要m个地址不发生分体冲突（即没有发生两个以上地址同属一个分体），即使地址之间不是顺序的，仍可并行读出，使实际带宽提高成单体单字的m倍。基本的多体交叉方法有两种，即高位交叉访问存储器和低位交叉访问存储器。2.高位交叉访问存储器图3.3是高位交叉的四体交叉存储器结构示意图。如果主存空间为N=2n字，那么访问该存储器的地址为n位。若存储器由M=2m个存储体构成，用高m位地址来选择不同的存储体，低n-m位为体内的地址。当高m位不相同时，便可以访问不同的存储体，即当多个处理机发出的访存地址高位不相同时，可对共享存储器内的不同存储体进行同时存取。当多个处理机发出的访存地址高位相同时，即访存同一存储体时，就不能并行操作了，我们称之为存储器的分体冲突。高位交叉访问存储器一般适合于共享存储器的多机系统。图3.3高位交叉的四体交叉存储器结构示意图3.低位交叉访问存储器图3.4是低位交叉的四体交叉存储器结构示意图。如果主存空间为N=2n字，那么访问该存储器的地址为n位。若存储器由M=2m个存储体构成，用低m位地址来选择不同的存储体，高n-m位为体内地址。当低m位不相同时，便可以访问不同的存储体，即当处理机发出的访存地址访问不同的存储体时（地址不一定连续），可对存储器内的不同存储体进行并行存取（这里的并行性指的是并发性）。当处理机访存同一存储体时，就不能并行操作了。低位交叉访问存储器一般适合于单处理机内的高速数据存取及带Cache的主存。在最好的情况下，即一个模m的多体交叉访问存储器在不发生分配冲突时的带宽是单体带宽的m倍。图3.4低位交叉的四体交叉存储器结构示意图如果模块的字是与数据总线等宽（W位）。若模块存取一个字的存储周期是θ，由m个子周期τ（τ要大于或等于总线传送周期）组成，即θ=mτ，并使用m个模块来交叉存取，则成块存取可按τ间隔流水进行，即每经τ时间延迟后即启动下一模块。这样，连续读m个字所需时间为θ+(m-1)τ,而顺序组织方式却要mθ时间，显然加快了成块存取速度。模四多体交叉存取存储器的流水存取示意图如图3.5所示。图3.5模四多体交叉存取存储器的流水存取示意图前面讲过，并行主存系统可达到的最大频宽Bm=W·m/TM,由这个式子可以看出：提高模m的值，是能提高主存系统的频宽的，但主存频宽并不是随m值增大而线性提高，也就是说其实际效率并不像所希望的那么高。例如，CDC-6600、7600采用模32交叉实际频宽只是理想频宽的三分之一都不到，这是因为：(1)工程实现上由于模m越高，存储器数据总线越长，总线上并联的负载越重，有时还不得不增加门的级数，这些都会使传输延迟增加；

(2)是系统效率问题。对模m交叉，如果都是顺序的取指令，效率是可以提高到m倍的，但实际上程序中指令不总是顺序执行的，一旦出现转移，效率就会下降，转移的频度越高，这种并行主存系统的效率下降就越大，而数据的顺序性比指令差，实际的频宽可能还要低一些。第4章流水线结构第5章并行处理机第6章多处理器系统多处理机属于MIMD系统，它与SIMD并行处理机有很大的差别，所有的差别归根结底来源于两者开发的并行性等级不同。多处理机实现的是作业、任务之间的并行，粒度组合主要为粗粒度和中粒度。因此，在结构上，多处理机中的每个结点都应该是一台能独立执行指令的处理机，而不只是一个简单的处理单元，各处理机之间通过总线或互连网络实现通信；在算法上，不再限于数组和向量中的数据并行性，还要挖掘和实现更多通用算法中隐含的并行性；在系统管理上，要更多地依靠软件手段有效解决资源管理，特别是粒度的组合与调度、多处理机调度、进程的同步和通信等。6.1多处理机的概念6.1.1多处理机系统的定义P.H.Enslow对多处理机给出了下列定义：1）包含两个或两个以上功能大致相同的处理器；2）所有处理器共享一个公共内存；3）所有处理器共享I/O通道、控制器和外围设备；4）整个系统由统一的操作系统控制，在处理器和程序之间实现作业、任务、程序段、数组和数组元素等各级的全面并行。6.1.2

多重处理对处理机特性的要求1）进程恢复能力2）有效的现场切换3）大的物理地址空间和虚拟地址空间4）高效率的同步原语5）处理机之间有高效率的通信机构6）指令系统6.1.3

多处理机的特点1）很高的性能价格比。2）很高的可靠性。3）很高的处理速度。4）很好的模块化。5）具有更大的结构灵活性和更强的通用性。由于在MIMD多处理机中各结点是一台独立的处理机，可以与其它处理机共享主存储器或采用分布式存储器，因而在不同的处理机上可并行执行不同的作业、任务或程序段，所以MIMD多处理机适宜于求解通用算法。另外，它能灵活地开发数据并行性和功能并行性，而SIMD并行处理机只能开发数组和向量中存在的数据并行性，因此其通用性较差。6）主要开发高层次作业及任务级并行性。对于高层次的并行性开发，通常是通过算法和程序设计语言来描述程序中的显式并行性，或通过编译器、操作系统和硬件来开发程序中存在的隐式并行性。而SIMD并行处理机则主要是开发低层次，即操作一级的并行性。7）并行任务派生需要用显式的专用指令来表示。在MIMD多处理机中，一个程序当中就存在多个并发的程序段，需要专用的指令来表示它们的并发关系以控制它们的并发执行，以便一个任务开始被执行时就能派生出可与它并行执行的另一些任务。这个过程称为并行任务派生。派生出的新任务被分配到其它处理机上去并行执行，若处理机的数量不够，那些暂时不能分配到空闲处理机的任务就进入排队器，等待即将释放的处理机。在SIMD并行处理机中，并行操作由单独指令表示和控制，故不需要设置专用的指令。8）并发执行的进程间的同步需要采取特殊措施，以保持程序所要求的正确顺序。由于MIMD多处理机实现的是作业、任务和程序级的并行性，一般来说，各处理机在同一时刻执行的是不同的指令。并行任务派生后，由于空闲处理机的限制使得所有的新任务不一定能同时投入运行，又加上各并发进程之间可能存在数据相关、控制相关等，为保持程序所要求的正确顺序，必须采取特殊的措施来实现并发进程间的同步。如采用数据同步(信号量、锁、生产者-消费者)、控制同步(路障、临界区)等。而在SIMD并行处理机中，由于所有的处理单元在同一控制器控制下，同时执行同一条指令的功能，工作是自然同步的。9）合理地进行资源分配和任务调度。在MIMD多处理机中，由于任务的大小不相同，各处理机的速度也可能不相同(如异构型多处理机系统)，互连网络的拓扑结构和通信延迟在不同的多处理机中也有很大的差别，在执行并发任务时，并不是使用的处理机个数越多，系统获得的性能就越高。因此需要采用软件手段，合理地进行资源分配和任务调度，否则系统性能将受较大影响。而在SIMD并行处理机中，程序员只需用屏蔽的手段来设置部分处理单元为不活跃状态，来控制实际参加并行操作的处理单元数目。6.2多处理机结构6.2.1多处理机的基本结构多处理机在系统结构上可分为两类：紧耦合多处理机和松耦合多处理机。1.紧耦合(tightlycoupled)多处理机紧耦合多处理机是通过共享主存来实现处理机间的通信的。各处理机与主存之间通过一个互连网络连接。在这种系统中，处理机间的数据通信速率将受限于主存的带宽，而处理机的数目受限于处理机-主存互连网络带宽以及多台处理机同时访问主存所引起的冲突概率。为了减少处理机访问主存的冲突，常采用如下方法：(1)多处理机的主存采用多模块交叉存取；模块数越多，发生冲突的概率将越低，但必须解决好数据在各存储器模块中的定位和分配。

(2)让每台处理机拥有一个小容量的局存，用来存放频繁使用的核心代码等，以减少对主存的访问；(3)让每台处理机都有一个Cache，以减少对主存的访问。但必须注意Cache与主存之间以及各个Cache之间的数据一致性。紧耦合多处理机的典型结构如图7.1所示。系统由m个共享存储器模块，p台处理机和d个I/O通道组成，每台处理机可以拥有一个Cache存储器或一个小容量的本地存储器。用三个互连网络PPIN(处理机-处理机)、PMIN(处理机-主存)和PIOIN(处理机-I/O通道)将所有的处理机、共享存储器模块，以及I/O通道连接起来。紧耦合多处理机按所用处理机类型是否相同可分为同构型和异构型多处理机。图6.1紧耦合多处理机系统的典型结构在紧耦合多处理机中，如果每台处理机在访问任意一个存储器模块或I/O设备时，都具有同等的能力，包括字宽和读写时间等都相同，那么这个系统就具有对称性。反之，表示多处理机是非对称的。一个多处理机要成为对称式多处理机必须满足两个条件：首先存储器必须是集中共享的，其次系统所用的互连网络也必须是对称的。紧耦合多处理机按其对称性可分为对称式多处理机和非对称式多处理机。对称式多处理机能实现各处理机与各I/O通道之间完全连接，有很大的灵活性，但价格昂贵，所以多数多处理机仍采用非对称式的互连，即连到一台处理机的设备不能被另一台处理机直接访问。带非对称I/O子系统的多处理机如图6.2所示。图6.2带非对称I/O子系统的多处理机图6.3带冗余连接的非对称I/O子系统在非对称式多处理机中，一旦某台处理机出现故障，它所接的外设将无法被其它处理机所访问。例如，在图6.2中，若处理机P1出现故障，则它所接的IOP1将不能被其它处理机中的任何一个所访问。因此在很多非对称式多处理机中都采用了适当的冗余连接，在一定程度上提高了设备的利用率。带冗余连接的非对称I/O子系统的多处理机如图6.3所示。在此图中，若处理机P1发生故障，处理机Pp仍可以访问IOP1，但这是以增加一个多通路仲裁逻辑为代价的。在紧耦合多处理机中，常见的组合是同构对称式多处理机及异构非对称式多处理机。(1)同构对称式多处理机Sequent公司生产的Balance多处理机就是同构对称式的，它的结构如图6.4所示。处理机数为2～32个，共享存储器模块数为1～6个。其中，每台处理机由80386微处理器和浮点运算器Weitek1167FPU组成，并带有64KB的Cache。存储器由8MB（可扩充到48MB）的存储器模块和一个存储控制器组成。各处理机和存储器模块均与系统总线相连，系统总线还通过总线适配器与Ethernet局域网、SCSI相连，或通过磁盘控制器与磁盘相连。此外，系统总线还可借助总线适配器和Multibus与远程网相连。图6.4Sequent的Balance同构对称式多处理机(2)异构非对称式多处理机异构非对称式多处理机的一般结构如图6.5所示。其中主CPU所用的处理机可不同于从机中的处理机。从机中CIOP处理机与字符外设相连，BIOP与数组外设相连，NIOP及GIOP分别为网络及图形处理机，ACOP为向量加速处理机。图6.5异构非对称式多处理机的一般结构2.松耦合(looselycoupled)多处理机松耦合多处理机是通过消息传递方式来实现处理机间的相互通信的。而每台处理机是由一个独立性较强的计算机模块组成，该模块由处理器、较大容量的本地存储器(在运算时所需的绝大部分的指令和数据均取自本地存储器)、I/O设备以及与消息传递系统(MessageTransferSystem，MTS)相连的接口组成。当不同模块上运行的进程间需要通信时，可通过网络接口电路及消息传递系统进行信息交换。由于这种相互间的耦合程度是很松散的，因此称之为松耦合多处理机。松耦合多处理机可分为非层次式和层次式两种结构。(1)非层次式松耦合多处理机图6.6是一个典型的通过消息传递系统进行互连的松耦合非层次式多处理机。该系统有N个计算机模块（或称结点）。每个计算机模块由微处理器、Cache、本地存储器LM和一组I/O设备组成。各计算机模块的进程之间通过网络接口电路NIC(NetworkInterfaceCircuitry)和消息传递系统进行通信。其中的NIC通常是由通道和仲裁开关CAS(ChannelandArbiterSwitch)组成，用于对两个或多个计算机模块同时请求访问MTS的某个物理段时进行仲裁。按照一定的算法，选择其中一个请求并延迟其它的请求，直至被选择的请求服务完成。图6.6松耦合非层次式多处理机系统的典型结构(2)层次式松耦合多处理机在层次式松耦合多处理机中采用了多级总线实现层次连接。图6.7中示出了卡内基-梅隆大学研制的由50个LSI-11小型机组成的Cm*层次式松耦合多处理机。最基本的计算机模块Cm中有自己的LSI-11总线，通过开关S经MAP总线与其它Cm相连。每个MAP总线可连接多达14个计算机模块Cm，构成一个计算机模块群(cluster)，模块群内的各处理机用较低的通信开销实现数据共享。图6.7Cm*层次式松耦合多处理机与MAP总线相连的Kmap是系统内各计算机模块群间的连接器，而各模块群间的连接是通过群间双总线实现的，采用双总线的主要目的是为了提高系统的可靠性。因此，Cm*是一个三层总线多处理机，三级的访存时间分别为：计算机模块内3.5μs，计算机模块群内9.3μs，而群间则为26μs。在松耦合多处理机中，由于各计算机模块实际上是一台完整的计算机，各计算机除了带有本地存储器外，一般都设有Cache存储器，因此与紧耦合多处理机一样，要解决多处理机Cache之间、Cache与主存之间的一致性问题。

6.2.2多处理机系统的存储器结构1.主存的组成2.多处理机系统的Cache结构Cache一致性问题的原因如果多台处理机在运行同一程序时不存在共享数据、或共享数据不允许调入各自的Cache时，将不会出现Cache的一致性问题。若允许共享数据调入各处理机的Cache中，并且允许处理机对共享数据进行写入操作时，就会产生各Cache中的共享数据之间、Cache与共享存储器之间的数据的不一致，具体来说，有以下三个方面的原因：(1)共享可写数据；(2)多处理机的进程迁移；(3)绕过Cache的I/O操作。以下以没有任何Cache一致性控制的共享存储器双处理机为例说明上述原因。处理机P1和P2拥有各自的Cache存储器Cache1和Cache2，我们将对写直达(WT)法和写回(WB)法分别予以分析。若使用写直达法，Cache数据的更新总是会引起主存内容的立即更新。若使用写回法，只有当Cache中的某一个数据块被替换时，该数据块才会在替换前被写回主存，所以在对Cache的写操作命中后的一段时间内，Cache和主存内容是不一致的。A.由共享可写数据引起的Cache不一致假设在写操作之前Cache的初始状态如图6.8(a)所示。处理机P1和P2各自Cache中的数据(标为x)与共享主存器中的相应数据是一致的，图中数据x加方框表示数据x所在的数据块。图6.8由共享可写数据引起的Cache不一致若使用写直达法，如图6.8(b)所示。当处理机P1修改Cache1中的数据成x＇时，在共享存储器中的相应数据也立即更新为x＇，这导致与处理机P2中Cache2所缓存的数据不一致。若使用写回法，如图6.8(c)所示。当处理机P1修改Cache1中的数据成x＇时，Cache1的变化不会引起Cache2和共享存储器的变化，这导致与共享存储器和处理机P2中Cache2所缓存的数据不一致。由此可见，在多处理机中要解决由共享可写数据引起的不一致，必须在每次写操作后立即使其它处理机的Cache中包含有相同Cache块的不同拷贝失效或者进行更新。B.由进程迁移引起的Cache不一致假设在迁移前Cache的初始状态如图6.9(a)所示，处理机P1的Cache1中有共享存储器中数据x的拷贝。若使用写直达法，如图6.9(b)所示。当某进程从P1迁移到P2后，处理机P2在执行此进程时由于要使用数据x，会将x所在的Cache块由共享存储器调入Cache2，假设进程运行时将Cache2的数据x改写为x＇，在共享存储器中的相应数据也立即更新为x＇，这导致与处理机P1中Cache1所缓存的数据不一致。图6.9由进程迁移引起的Cache不一致若使用写回法，如图6.9(c)所示。当处理机P1修改Cache1中的数据成x＇时，Cache1的变化不会引起共享存储器的变化。当某进程从P1迁移到P2后，处理机P2在执行此进程时由于要使用数据x，会将x所在的Cache块由共享存储器调入Cache2。此时调入的数据x并非是已经修改过的x＇，这将导致共享存储器及Cache2与处理机P1中Cache1所缓存的数据不一致。C.由绕过Cache的I/O操作引起的不一致假设在执行I/O操作之前Cache的初始状态如图6.10(a)所示。处理机P1和P2各自Cache中的数据(标为x)与共享存储器中的相应数据是一致的。若使用写直达法，当I/O处理机执行输入操作直接将共享存储器中的数据x改写成x＇时，这将导致Cache1和Cache2与共享存储器数据的不一致，如图6.10(b)所示。若使用写回法，当处理机P1对Cache1中的数据x改写为x＇时，由于Cache1数据的修改不会立即引起共享存储器中数据x的更新，此时若此数据恰好被I/O处理机输出，就会造成输出错误，如图6.10(c)所示。这表明I/O操作应当在Cache控制器的协调下进行。图6.10由绕过Cache的I/O操作引起的不一致由前面介绍的三种引起Cache不一致的原因，表明了在多处理机环境下共享可写数据、进行进程迁移或I/O操作时采用一致性协议的必要性。一致性协议主要有两种，一种是基于总线的监听一致性协议(snoopycoherencyprotocol)，此类协议需要由总线或环提供的广播机制，通过监听总线(snoopybus)实现。主要思想是不断地监听总线上处理机和存储器模块间的Cache操作事件，各处理机根据监听的信息对各自Cache中的数据采取保持一致性的措施；另一种是基于目录的一致性协议，此类协议需要建立一个Cache目录，记录共享数据块的处理机信息，当某一处理机完成写操作后，同时通过此数据块所在的各目录项，把一致性命令发给存放有该数据块拷贝的Cache，使之无效或更新，但它主要应用于具有分布式存储器模型的多处理机中。

3.监听一致性协议当各处理机的Cache都连接到公共总线时，为保持Cache的一致性有两种选择，一种是采用写无效(write-invalidate)协议，另一种是采用写更新(write-update)协议。写无效协议是指在某本地Cache数据被更新后使所有其它Cache中的相应数据拷贝失效。写更新协议是指在某本地Cache数据被更新后，广播修改后的数据以更新所有Cache中的相应数据拷贝。注意，这里要区分多处理机的Cache一致性协议与更新主存内容的协议之间的区别。前者是为了保持多处理机中各Cache的一致性，而后者是为了保持某台处理机的Cache与主存储器之间的一致性。通常所说的写直达(WT)法和写回(WB)法属于后者。A.写无效协议在图6.11(a)中，可以看到在写操作前，处理机P1和P2的各自Cache中都存有共享存储器中数据x的拷贝，图中数据x加方框表示数据x所在的数据块。当处理机P1想要进行写操作时，首先它必须获得对x访问的独占权，然后更新数据为x＇并使Cache2中的相应数据块拷贝失效(标志为I)，如图6.11(b)、6.11(c)所示。若使用写直达法，该共享存储器中的数据x将会立即更新为x＇，如图6.11(b)所示。若使用写回法，共享存储器中数据x所在的数据块也将被设置为无效，如图6.11(c)所示。若使用写直达法，当处理机P2想要访问已修改的数据x＇时，会发生Cache2不命中并从共享存储器中读取新值x＇，并调入数据x＇所在的数据块。若使用写回法，当处理机P2想要访问已修改的数据x＇时，会发生Cache2不命中并从处理机P1的Cache1读取新值x＇，并调入数据x＇所在的数据块，同时会更新主存中的相应数据块。图6.11写无效监听协议B.写更新协议假设在写操作前，处理机P1和P2的各自Cache中都存有共享存储器中数据x的拷贝，如图6.12(a)所示。当处理机P1对Cache1中的数据x进行写操作时，它必须通过广播x＇的方法来更新x在所有处理机Cache中的拷贝。当其它的处理机要访问修改过的x＇时，会在本地Cache命中，如图6.12(b)、6.12(c)所示。若使用写直达法，则共享存储器中数据x所在的数据块会如图6.12(b)中所示的立即更新。若使用写回法，则共享存储器中数据x所在的数据块将会被置为无效，如图6.12(c)所示。共享存储器中的数据也可以立即更新，这由所使用的具体实现方法决定。从上述过程可以看出，写更新协议为保持所有Cache中共享数据的高度一致性，需耗费大量的总线周期来更新所有的Cache和共享存储器中的共享数据块，这无疑会加重总线传输的负担，因此在大多数多处理机中都选择使用写无效协议。图6.12写更新监听协议MESI监听协议MESI属于写无效协议。它根据所有的读、写、命中或不命中和在总线上监听的事件来跟踪Cache数据块的状态。带有2级Cache的双Pentium多处理器系统实现的MESI协议，如图6.13所示。图6.13有2级Cache的双Pentium处理器系统PentiumMESI协议同时支持写直达法和写回法，这由一个外部信号控制。当发生Cache的写不命中时使用不按写分配(non-write-allocate)法，即不从共享的主存储器中载入该数据所在的Cache块。4.基于目录的协议当某台处理机采用写无效协议正在更新一个变量并且其它的处理机也试图读该变量时，则会发生读失效并可能导致总线的流量大大增加。另外，写更新协议可以更新远程Cache中的数据，而其它处理机可能永远也不会使用这些数据。因此，这些问题使采用总线来构造大型多处理机系统受到限制。当用多级网络来构造有数百台处理机的大型系统时，就必须修改Cache的监听协议以适应网络的性能。由于在多级网络上实现广播功能的代价很大，所以把一致性命令只发给存放块拷贝的Cache。这样就产生了用于网络连接的多处理机系统的基于目录的协议。A.目录结构Cache目录(cachedirectory，DIR)实际上是一个Cache位置表，它是用目录的形式记录所有Cache块和共享数据块的位置和状态，从而支持Cache一致性。各种基于目录协议的不同之处主要是目录如何维护信息和存放什么信息。Cache目录的方案有集中式和分布式两种，它们的主要区别就在于其Cache目录的存放形式。由于集中式目录记录了Cache的当前信息和所有Cache块的状态，需要大量的存储器来实现，因此集中式目录只适用于具有集中式共享存储器的小规模SMP的Cache一致性控制。在分布式目录中，每个存储器模块维护了一个单独的目录来记录所有的Cache块的状态和当前信息。无论Cache目录采用集中方式还是分布方式来存放，其内容都是大量的指针，用以指明块拷贝的地址。每个目录项还有一个污染位(dirtybit)，用以指明是否只有某个唯一的Cache有此数据块的写权限。不同目录协议的区别在于目录的结构不同。根据目录的结构，可以把目录协议分成三类：全映射目录(full-mapdirectory)、有限目录(limiteddirectory)和链式目录(chaineddirectory)。全映射目录存放与全局存储器中每个Cache块有关的数据。这样，系统中的每个Cache可以同时存储任何数据块的拷贝。而在有限目录中，无论系统的规模多大，它的每个目录项的指针数都是固定的，所以每个数据块能够装入Cache的数目是有限的。链式目录的特点是把目录分布到全部的Cache中，其余部分与全映射相同。B.全映射目录用全映射目录协议实现的目录项中有N个处理机位和一个污染位，其中N为处理机的台数。目录项的结构如图6.14所示。处理机位表示相应处理机对应的Cache块的状态为“有效”或“无效”。“有效”表示该Cache块已存在于某台处理机的Cache中，并且为有效状态；“无效”表示该Cache块已存在于某台处理机的Cache中，并且为无效状态，或者在某台处理机的Cache中该块根本就不存在。污染位表示某一个Cache块是否已经被修改过，它有“未写”和“污染”两种状态。“未写”表示当前Cache块没有被修改过；“污染”表示某一个Cache块已被修改。如果污染位为“1”而且有且仅有一个处理位为“1”时，则允许该处理机对该块进行写操作。图6.14目录项的结构Cache的每个数据块有两个状态位。一位表示数据块是否有效，另一位表示有效数据块是否允许写。Cache一致性协议必须保证目录的状态位与Cache数据块的状态位一致。图6.15是全映射目录的三种不同状态。第一种状态表示整个系统所有Cache中都没有单元x的拷贝。当三台处理机都对x有过读请求之后，就出现了第二种状态。这时，目录项中的三个指针(处理机位)被置“1”，表示这些Cache已有数据块拷贝。在前述这二种状态下，目录项最左边的污染位被置为未写(Clean，C)状态，表示没有一台处理机允许写入该数据块。在P3处理机获得了对x的写权限后就出现了第三种状态。这时污染位被置为污染(Dirty，D)状态，而且有一个指针指向Cache3的数据块。下面再来详细说明图6.15中从第二种状态转换到第三种状态的过程。一旦处理机P3向Cache3发出请求时，将发生以下事件：(1)Cache3检测出包含单元x的块是有效的，即P3访问x时在Cache3中命中，但Cache块的写允许位状态表示不允许P3对该块进行写操作。(2)Cache3向包含单元x的存储器模块发写请求，并暂停P3的工作。(3)该存储器模块发出一个无效请求给Cache1和Cache2。(4)Cache1和Cache2接收到无效请求后，把相应的块置为无效状态，并发送一个回答信号给发出请求的存储器模块。(5)存储器模块接收到回答信号后，把污染位置为“D”，表示此共享数据块已被修改，并清除指向Cache1和Cache2的指针，发写允许信号给Cache3。(6)Cache3接收到写允许信号后，更新包含单元x的块在Cache3的状态为写允许状态并且激活P3处理机。至此，全部过程结束，P3就可以写x单元了。在P3完成写操作之前，存储器系统一直等待接收回答信号。图6.15全映射目录的三种状态由于和存储器中数据块有关的目录项大小同处理机的数目成正比，所以目录所花费的存储器容量就同存储器大小O(N)和目录项大小O(N)的乘积成正比，因此，整个存储器的开销将与处理机数目的平方O(N2)成正比。尽管全映射目录协议的效率比较高，但由于过多的存储器开销，所以不具有可扩展性。C.有限目录有限目录的每个目录项只用一定数量的指针，而不管系统的大小如何。这减少了Cache目录对存储空间的要求，因而当存储器数据块共享比较少时更加经济。但如果有大量的处理机Cache共享相同的数据，那么它有可能降低Cache/主存的更新速度。有限目录协议的状态与全映射目录协议十分相似，但目录项中的指针(处理机位)实际上是处理机的地址编码，若共有N台处理机，则目录项中指针部分为log2N位，每个目录项中指针的个数远远小于处理机的台数N。正因为如此，当多于允许数目的Cache同时要求某一个数据块的拷贝的时候，就必须进行指针的替换。这种指针替换过程称为驱逐(eviction)。由于多处理机系统中的处理机具有局部性（即在任何给定的时间间隔内，只有一小部分的处理机访问某个给定的存储器数据），所以有限目录足以应付这个小的处理机组了。如图6.16所示，假设多处理机系统中共有3台处理机，目录项中只有2个指针，存储单元x所在的数据块对应的目录项中2个指针分别指向处理机P1和P2，即在P1和P2的Cache中都有单元x所在的数据块的拷贝。当P3请求访问单元x时，需将单元x在共享存储器中的数据块调入Cache3，同时采用某种替换算法修改目录项中的指针部分。在图6.16中假设替换的是指向处理机P2的指针。在这里，任一时刻最多只能有2台处理机的Cache共享一个数据块。由于和存储器中数据块有关的目录项大小同log2N成正比，所以目录所花费的存储器容量就同存储器大小O(N)和目录项大小O(log2N)的乘积O(Nlog2N)成正比。图6.16有限目录的驱逐D.链式目录链式目录通过将目录信息分布到多个小规模的本地目录中来模拟全映射机制。其主要思想是通过维护一个目录指针链来跟踪共享数据块的拷贝。要想得到某个数据块在所有Cache中的共享情况，必须搜索整个Cache目录链。链式目录有两种实现方法，一种是单向链表，另一种是双向链表。这里我们主要介绍基于双向链表格式的典型链式目录协议的例子：IEEESCI(ScalableCoherentInterface)的Cache一致性协议。每个存储器数据块都有一个指针(称作头指针)，指向Cache链表的第一个结点。每个Cache块有两个指针，它们分别指向前趋结点和后继结点。图6.17示出了SCI协议Cache和存储器之间的链表的链接关系。图6.17链式目录协议当某一处理机读或写单元x所在的数据块不命中时，需将该数据块调入该处理机的Cache中，同时采用双向链表的插入操作修改双向链表；当某一处理机的Cache中单元x所在的块所替换时，将采用双向链表的删除操作修改双向链表；当某一处理机写单元x所在数据块命中时，若此Cache是双向链表中唯一的Cache结点，则直接将数据写入该Cache；否则，通过搜索双向链表，将除此Cache以外的其它所有Cache中包含单元x所在的数据块全部都置为无效状态，并且将此Cache作为头结点插入到双向链表中。6.3程序的划分和调度6.3.1粒度的组合和调度在并行程序设计中会涉及两个基本问题：(1)如何能将一个程序划分为并行分支、程序模块、微任务或颗粒以便获得尽可能短的运行时间；(2)在计算中最佳的并行粒度为多大。这种粒度问题既要求测定并行程序中的颗粒（或微任务）数目，又要求测定颗粒的大小。下面我们以阶段并行模型来介绍在N个处理器上并行执行应用程序所需的总的时间。首先来了解一下有关并行度DOP(DegreeofParallelism)的概念，所谓并行度是指应用程序的某个阶段可开发的最大并行性，它主要与程序的数据相关性有关。设顺序程序C由一串k个分计算阶段C1，C2，…，Ck所组成，步Ci的计算工作负载为Wi百万浮点操作(Mflop)且在单处理器上需用T1(i)秒，它的并行度为DOPi，如图6.19所示。图6.19应用程序的阶段并行模型则在N个处理器上总的并行处理时间为：

(6.1)其中，Tcomp表示总的并行计算时间，Tpar表示所有的并行性开销，Tinteract表示所有的交互开销。在图6.19中，总的并行计算时间(6.2)由式6.2可以看出，当处理器的个数N趋于无穷大时，应用程序的并行度越高，计算所需的时间越短；若应用程序的并行度DOP趋于无穷大时，处理器的个数N越大，计算最需的时间越短。Tpar主要与操作系统有关，它主要包括以下几个方面：(1)进程管理，如进程的创建、进程终止、现场切换等；(2)进程组操作，如进程组的创建与撤消；

(3)进程查询，如查询进程标识、排序号、组标识、组大小等。Tinteract的大小主要与工作负载的大小、计算机硬件结构，以及粒度的组合和调度有关，它主要包括以下几个方面：(1)同步，如原子性、控制同步和数据同步；(2)聚集，如归约和扫描；(3)通信，如采用共享变量或消息传递方式的点对点通信、集合通信。将式6.2代入式6.1，得：(6.3)由式6.3可以看出，颗粒度越细，并行性越高，计算时间Tcomp越短，但分布式多计算机系统之间的通信开销Tinteract将越大。颗粒度越粗，并行性越低，计算时间Tcomp越长，但分布式多计算机系统之间的通信开销Tinteract将越小。为了获得尽可能短的运行时间Tpp，必须在并行性（即粒度的大小）和调度/同步开销之间进行折衷。6.3.2静态多处理机调度静态多处理机的粒度确定和调度优化过程包括四个主要步骤：(1)构造细粒度程序图；(2)调度细粒度运算；(3)进行粒度组合得到粗粒度程序图；(4)在组合图基础上产生并行调度方案。多处理机调度的目的是为了得到一个调度方案，使并行处理时间Tpp最短。下面我们介绍有关静态多处理机调度的一个例子来说明这一点。例6.1

将两个2×2矩阵A和B相乘，并计算所得乘积矩阵C=A×B中4个元素之和。假设一次乘法所需的时间为101个CPU周期，一次加法所需的时间为8个CPU周期，采用多处理机时，两台处理机之间通信时间延迟为212个CPU周期。试设计一种较好的调度方案，使得总的处理时间尽可能短。解：这个程序共要完成8次乘法和7次加法，如下式所示：A11

A12

B11B12C11C12×=A21

A22

B21B22C21C22

C11=A11×B11+A12×B21C12=A11×B12+A12×B22C21=A21×B11+A22×B21

C22=A21×B12+A22×B22SUM=C11+C12+C21+C22(1)构造细粒度程序图在多处理机上并行处理的细粒度程序图实际上是执行过程中各条语句之间的关系图，它与数据相关性图极其相似，只要不发生数据相关，就可以并行执行，如图6.20所示。8次乘法在8个“×”结点中完成，每一个结点的粒度为101个CPU周期。其余7次加法在7个“+”结点组成的3级二叉树上完成，每个加结点需用8个CPU周期。图6.20细粒度程序图(2)调度细粒度运算在单处理机上串行顺序调度与在8台处理机上采用细粒度并行调度方法分