计算机体系结构复习.doc

第一章 计算机系统结构设计基础系统结构的定义：计算机系统结构就是程序员所看到的计算机的基本属性，即概念性结构和功能性结构。分类：按“流”分类：单指令流单数据流(SISD)；单指令流多数据流(SIMD)；多指令流单数据流(MISD)；多指令流多数据流(MIMD)。按“并行级”和“流水线”分类 ：并行计算机显式并行流水多处理机(K1)阵列计算机(D1)字片机(W1)宏流水(K1)指令流水(D1)算术流水(D1)Erlangen 计算机系统分类方法研究范围：有关软、硬件等价的概念：功能在逻辑上是等价的。绝大部分硬件功能都可以用软件来实现，反之亦然。但两者在实现时将在性能价格比上以及实现的难易程度上不等价。用硬件代替软件所实现的功能往往在性能上占优，且占用存储量较少，但成本相对较高，改变的灵活性较差，用软件的情况正好相反。透明：一种本来存在的差异的事物或属性，从某种角度来看似乎不再存在，称为透明现象兼容：即可移植性，是指一个软件可不经修改或只需少量修改便可以由一台机器移植到另一台机器上去运行。即同一个软件可应用不同的环境。仿真：当宿主机(A机)本身采用微程序控制时，直接由A机中对应的一段微程序来完成对目标机(B机)指令系统的每条指令的解释执行。模拟：指用软件的方法在一台现有的计算机上实现另一台计算机的指令系统。即用实际存在的机器语言解释实现软件移植的方法称为模拟。模拟是采用纯软件解释执行的方法，因此运行速度较慢。系列机：通过统一的机器语言来实现软件移植的方法，即是预先确定好一种系统结构(软硬件界面)。然后软件工作者依此进行软件设计。硬件工作者则根据不同的性能、价格要求，采用各种不同的组成和物理实现技术，以向用户提供不同挡次的机器。阿姆达尔定律及加速比的计算：阿姆达尔定律是指：系统中对某一部件采用某种更快执行方式所能获得的系统性能改进程度，取决于这种执行方式被使用的频率，或占总执行时间的比例。TO：不采用任何增强功能措施完成某一任务所需时间； Te：采用某种增强功能措施后完成同一任务所需时间； fe：可采取增强功能措施的部分所占百分比 0 fe 1； re：采用增强功能措施是不采用增强功能措施执行的倍数。例题：将系统中某一功能的处理速度加快10倍，但该功能的处理使用时间仅为整个系统运行时间的40%，采用此增强功能方法后，整个系统功能提高多少？ 解：由题可知：fe=0.4 ，re=10第二章 计算机的性能和成本计算机性能(CPU时间、CPI等)，成本指什么？响应时间是指在用户向计算机系统送入一个任务后，直到获得他所需要的结果所需的时间。CPU时间不包括等待I/O的时间以及CPU转去运行另一道程序所花的时间。衡量计算机性能的主要标准。在元器件成本和直接成本基础上再加上间接成本就成为产品的平均售价。CPU性能的TCPU、CPI、MIPS和MFLOPS的计算。绝大多数计算机用固定速率运行的时钟，运行周期称为时钟周期(Clock cycles)，以时间长短(以ns表示)或运行速率(MHz)表示。一个程序在CPU上运行所需时间TCPU，可用下式表示： TCPU =INCPITC式中：IN 表示执行指令的总数；CPI表示执行每条指令所需的平均时钟周期数；TC 表示时钟周期的时间长度。IN取决于机器指令系统和编译技术；CPI与计算机组成和指令系统有关；TC则主要由硬件工艺和计算机组成决定。例题：见课本MIPS(Million instructions per second)每秒百万条指令TE表示执行该程序所需时间；RC=1/TC， 表示时钟速率。 相对MIPSRelMFLOPS(Million floating point operations per second)每秒百万次浮点运算 IFN表示程序中的浮点运算次数。在Livermore 循环测试程序中， 浮点加、减、乘及比较操作的正则化的值为1； 浮点除法、开方操作的正则化的值为4；用MFLOPS作衡量单位时，它的值不但会随整数、浮点数操作混合比例的不同发生变化，而且也会随快速和慢速浮点操作混合比例的变化而变化。1MFLOPS 3MIPS第三章 数据类型和数据表示IEEE754标准。符号位S，指数部分E，尾数部分M。 单精度格式(32位)：E=8位、M=23位； 扩展单精度格式：E11位、M=31位； 双精度格式(64位)：E=11位、M=52位； 扩展双精度格式：E15 位、M63位。第四章 指令系统的设计原理及风格指令系统集结构的分类：指令系统结构的分类主要是依据在CPU中以何种存储方式来存放操作数。 按照这一特征，可将指令系统结构分为堆栈型、累加器型、通用寄存器型三类。1. 堆栈型结构中，操作数被默认存放在栈顶中；2. 累加器结构中，操作数之一总是被默认存放在累加器中；3. 通用寄存器结构中，所有的操作数都必须加以显式说明，以指明其是存放在哪个寄存器中或是存储器的哪一单元中。又进一步可分为寄存器-寄存器型或是寄存器-存储器。堆栈结构：具有表达式求值的简单模型(符合逆波兰表示)以及指令字长较短因而能产生良好的代码密度。主要缺点是不能随机访问，因此很难生成高效代码。此外堆栈将成为瓶颈口，使性能受到影响。累加器结构：具有可使机器内部状态减至最小并能形成短指令的特点。缺点是累加器是唯一的操作数寄存器，将导致对存储器的频繁访问。寄存器结构：具有生成代码的最通用形式。缺点是由于要对所有操作数所使用的寄存器加以赋名，导致指令长度的增加。寄存器-存储器结构则介于累加器结构和寄存器一寄存器结构之间。堆栈性：累加器性：通用寄存器性指令集的结构：通用寄存器指令系统的进一步分类：按照ALU指令有多少个操作数需要至存储器中去存取，通用寄存器型指令系统中指令可以进一步分为RR、RM、MM三类。对RISC计算机而言，只有RR类型。在ALU指令中是不允许访问存储器的，当所需的操作数不在寄存器而在存储器中(或Cache)，必须先借助LOAD指令将此数据先存储到寄存器，再从寄存器中取出。当要将寄存器中的内容存入存储器中时，则必须借助于STORE指令。操作数访问(寻址)方式：寻址方式定 义立即数 指令中含有操作数值直接 指令地址字段中含有操作数的内存地址寄存器 指令地址字段中含有操作数的寄存器地址寄存器间接 指令所指明的寄存器中含有操作数所在存储单元的地址存储器间接 指令所指明的存储单元中含有操作数所在存储单元的地址相对 操作数地址是一个偏移值和程序计数器内容的和变址 操作数地址是一个偏移值和一个变址寄存器内容的和自增 操作数地址在一个寄存器中，在取操作数后其值自动加1自减 操作数地址在一个寄存器中，其值在取操作数之前自动减1比例 变址寄存器的内容需乘一个比例因子(1，2，4，8)注：EA=有效地址 (x)=x的内容 SR=段寄存器 PC=程序计数器 A=指令地址字段内容 R=寄存器 B=基址寄存器 I=变址寄存器 S=比例因子 寻址方式 地址计算 立即 操作数=A 寄存器 EA=R 位移 EA=(SR)+A 基址 EA=(sR)+(B) 移位基址 EA=(SR)+(B)+A 移位比例变址 EA=(SR)+(I)S+A 变址和移位基址 EA=(SR)+(B)+(I)S+A 比例变址和移位基址 EA=(SR)+(I)S+(B)+A 相对 EA=(PC)+A按地址访问方式：工作方式是串行顺序的，所给定的地址要事先加以计算。按内容访问方式：将所给定的访问内容与存储单元中的内容进行比较。按内容访问方式不提供被访问存储单元的地址，而是给出被访问的内容。指令格式及其优化-霍夫曼编码。 指令格式，就是选择指令字中的操作码长度和地址数。一个指令字(或一条指令)一般由两部分组成： 操作码部分指明指令所要完成操作，是指令必不可少的部分；操作数地址码部分用来指明需要进行某种操作的数据(包括输入数据、操作数变量以及所产生结果)来自何处和将被送往何处，它不一定是必需的。指令优化：1. 插入转移延迟槽2. 解决延迟方法：予取两个分支方法防止断流(硬件) 软件采用优化延迟转移技术。优化延迟转移，转移指令已准备将控制转向目标指令时，执行紧随其后的那条指令(即将转移指令后的延迟槽内的指令执行完毕后才发生真正转移，不管转移成功否)。第五章 标量流水技术控制流及其改变。控制流：指被处理的指令序列的执行顺序。控制流改变：1. 转移指令；2. 过程调用和返回；3. 协同程序；4. 中断和自陷。自陷：由计算机内部发现某一意外事件，如计算机出现非法操作等例外情况导致系统自动调用出错处理过程。标量流水工作原理：重叠操作方式和先行控制：指令的解释一般分为顺序、重叠、流水三种。1. 顺序方式：一条指令完全解释分为取数，分析和执行三个阶段，各个阶段时间分为t取、 t分、t执，对n条顺序指令则有 2. 重叠方式：即相邻的两条指令的解释过程中，某些不同解释阶段在时间上存在重叠部分。3. 流水方式。先行控制技术：使下一条指令的分析阶段包含在前几条指令的执行阶段中，使分析部件和执行部件能分别连续不断地分析和执行指令。指令缓冲栈：保存多条指令以供指令分析器使用。 先行操作栈：保存分析部件已完成的分析的结果。数据操作栈：有两个数据缓冲区：分析部件完成指令分析，但执行部件此时没有完成前条指令的执行时，从主存取出的操作数暂送读数据缓冲区。标量流水工作原理(b) 流水线工作时空图图5.7 流水线中各段及流水处理时空图S5S3S1S4S2排空充满S543545432TT(n-1)tmtnn-1填入nn-1 54321nn-1 4321nn-1 321n-1 21n 51流水处理机的最高工作频率：每个流水段延迟时间(通过时间)均为D ts，锁定时间为 D tl。标量流水分类：1. 按处理级别分类：操作部件级：是将复杂的算逻运算组成流水工作方式。指令级流水：是把一条指令解释过程分为多个子过程。处理机流水是一种宏流水，每一个处理机完成某一专门任务。2. 按功能分类： 单功能流水线：只完成一种功能。 多功能流水线：可完成多种功能，允许在不同时间甚至同一时间内在流水线内不同功能段子集来实现不同功能。3. 按工作方式分类 静态流水线：同一时间内只能以一种功能方式工作，它可以是单功能的，也可以是多功能的。 动态流水线：允许在同时间内将不同的功能段连接成不同的功能子集(前提是功能部件的使用不发生冲突)，以完成不同的运算功能 。 显然，动态流水线必是多功能流水线，而单功能流水线必是静态流水线。4. 按连接方式分类： 线性流水线。 从输入输出，每个功能段只允许经过一次。不存在反馈回路，一般流水线均属于此。非线性流水方式，流水段中则存在反馈回路，因此从输入输出过程中某些功能段将数次通过流水线，这种流水线适合线性递归。流水线的主要性能及其分析。1. 吞吐率最大吞吐率：指流水线达到稳定后，可获得的吞吐率。实际吞吐率 设流水线由m段组成时钟周期为Dt，连续处理的任务数为n。通过各段时间均为Dt，由图5.7可知完成n个任务所需时间为：T=mDt+(n-1)Dt=(m+n-1)Dt。实际吞吐率：2. 加速比指采用流水方式后的工作速度与等效的顺序串行方式的工作速度之比。3. 效率E 效率是指流水线中的各功能段的利用率一般用流水线各段处于工作时间性的时空区与流水线中各段总的时空区之比来衡量流水线效率。流水操作中的主要障碍：三种相关：资源(或结构)相关、数据相关、控制相关。资源冲突(结构冲突)：当有多条指令进入流水线后，在同一机器周期内争用同一功能部件所发生的冲突。停顿法：停顿一拍流水线。部件冗余法：重复设置一个存储器。数据相关冲突：由于后继指令所需的操作数，刚好是前一条指令的运算结果。后推法：停顿后继指令运行，直至前面指令结果已产生，这需要使流水线停顿较长时间。 采用定向技术(又称旁路技术或相关专用通路技术)控制转移冲突：控制相关主要是由转移指令引起的。尽早判别转移是否发生，尽早生成转移目标地址。预取转移成功或不成功两个控制方向上的目标指令。加快和提前形成条件码。加快短循环程序的处理。提高转移方向的猜准率。采用延迟转移枝术。流水线的中断处理:关键：处理好断点现场的保护及中断后的恢复运行问题。非线性流水线中功能段使用权冲突及相应调度。先进的流水技术：一、 先进的流水调度方法动态调度:动态调度是通过硬件重新安排指令的执行顺序以减少流水的停顿。 与静态调度相比，动态调度有如下的优点： 能处理某些在编译时无法知道的相关情况。 能简化编译程序的设计。 使代码有可移植性。 这种方法主要缺点是：相应的硬件较为复杂。流水的集中式的动态调度：整数部件浮点加浮点乘浮点除记录控制器RFIDIF控制/状态控制/状态命令图5.28 集中式动态调度流水的分布式动态调动：采用公共数据总线CDB来实现某些相关专用通路连接，并通过给每一个FLR(浮点数寄存器)，设置一个“忙”标志来判别指令间所用的数据是否发生数据相关，只要某些 FLR正在使用，就将“忙”位置“1”，表示存在数据相关，一旦使用完成，就置“0”。:动态硬件预测转移方法：借助硬件动态地预测转移方向。这是一种尽早生成转移目标地址的方法：它将过去发生的转移指令所在地址及它的目标地址存入一个由类似于Cache、称为BTB(Branch Target Buffer)的转移目标缓冲器中，转移指令地址作为标志，供检测用。二、 流水中指令级并行性的进一步开发并行有粗粒度和细粒度之分粒度：计算机处理问题的单位大小；细粒度：指处理单位为指令或指令中操作；粗粒度：指处理单位为进程，任务或作业。指令级并行度可用并行度来衡量，并行度指不存在相关时可同时并行执行指令数。超级标量方法：超级标量机的主要特点： 配置有多个性能不同的处理部件，采用多条流水线并行处理。 能同时对若干条指令进行译码，将可并行执行的指令送往不同的部件，从而达到在每个周期启动多条指令的目的。在程序运行期间由硬件(通常是状态记录和调度部件)完成指令调度。计算采用超标量方法获得的加速比，设 K：流水线级数，经过每级流水线所需的时间为1； N：流水线要处理的元素个数； m：为超标量在一个机器周期中所发动的指令数； n：为流水线的时钟速率； 因为基本流水线中的m和n均为1，因此N个元素所需的时间为：T(1，1)=K+N-1超标量机处理N个元素所需的时间为：超标量机的加速比为：VLIW(超长指令字)方法：长指令字往往可达上百位，甚至上千位，并发操作主要是在流水的执行阶段进行的。超长指令机的主要特点是：单一的控制流。只有一个控制器，每一个周期启动一条长指令。超长指令被分成多个控制字段，每一个字段直接独立地控制每一个功能部件。含有大量的数据通路和功能部件，由于编译时已考虑可能出现的数据相关和资源相关，故控制硬件较简单。在编译阶段完成超长指令中，多个可并行执行操作的调度。压缩技术表调度法，实际上是一种局部压缩只在程序基本块范围内进行压缩(只有一个入口和一个出口的代码段)。全局压缩（它允许代码操作可在基本块之间移动，从而可获得更好的压缩效果。）主要有三种：路径调度、渗透调度、软件流水。 路径调度：在编译期间把代码序列划分成若干个不相交子集，称之为路径，然后选择执行概率最高的路径作为 主路径。对主路径采用表调度法进行代码压缩。但允许代码操作按规定约束在基本块间移动。由于操作移动，必将在非主路径上增加相应副本操作以维持原来的语义，因此，这实际上是一种以牺牲非主路径为代价换取主路径执行具有最佳优化效果的方法。 图5.41显示了路径调度时对主路径的选择，以及需进行附加的补偿操作S和R的情况。 渗透调度：不选路径，它是通过一系列语义等价变换，把操作不断地移向前面(即渗透)。渗透后把属于不同基本块的操作最大限度的重叠起来。它不是按转移分支概率来选择，而是设法使操作尽可能早地执行。 软件流水：主要是为了加快程序中循环体的执行，VLIW计算机所采用的技术已广泛流传开来。展开循环体后调度：将要执行的循环体(Unrolling)展开多次，虽然增加了源代码的长度，但为并行执行调度提供了更多的机会。软件流水方法：借用硬件流水思想，以使循环体程序段的执行能够重叠执行方法。图5.50 采用软件流水展开n个体 设有一个程序段，长度为L，若每条指令执行时间平均需要t，当此循环程序体执行n次时，所需时间为：T=nLt T=4Lt/3+(n-2)Lt/3=(n+2)Lt/3超级流水方法：通过提高流水线运行速度来增强机器性能。为了提高运行速度，必须要加深流水深度，以减少每一段的延迟时间，这样就可加快流水线的运频率。第六章 向量流水处理向量流水机的基本系统结构：向量流水处理的主要特点：向量流水机对相同数量的数据项进行操作时，要比一 串标量指令操作更快。向量流水机还可使访存和有效地址计算流水化。高档向量机还允许多个向量操作同时进行，从而可开发对不同元素进行多个向量操作的并行性。向量机的基本系统结构向量机系统结构按向量操作对象及结果主要存入在寄存器中还是存放在存储器中，可分为RR工作方式向量机和MM工作方式向量机两大类。MM方式是源向量来自于M，结果M。R R方式是源向量来自于R，结果R。向量启动时间和启动率设有一条向量指令所需时间TVP为 TVP=Tst+nIr (6.1)Tst：流水线启动时间； (包括流水线固有的延迟时间)以便设置为完成向量操作所需的相应参数(如向量长度等)。 n：向量长度；Ir：启动率。表示一旦向量指令开始运行后，即向量流水线填满后，每流出一个结果所需的时间。 例：设一个向量乘法流水部件的启动时间为10个时钟周期，启动率Ir为1，则对于长度为64的向量乘法产生每个向量元素结果所需要的钟周期数为：每个结果需要的钟周期数对于RR方式来说，流水线的启动时间主要取决于功能部件流水的深度。向量操作长度控制和向量访问步长自然向量长度：每个向量寄存器中的向量元素个数。在向量长度寄存器中存放的长度值向量寄存器的长度(MVL)的向量均可放入向量寄存器。向量长度向量寄存器长度时，就必须将向量长度按向量寄存器长度分段。分段后的向量长度即是每次向量操作的长度，必须向量寄存器长度。例题见课本！向量处理方法增强向量处理性能的方法（4种）： 采用多功能部件，使它们并行工作。 加快一串相关向量指令的操作速度。又称链接技术，首先在Cray-1巨型机上得到应用，目前的向量机都支持这种技术。 另外两种方法主要是为了增加以向量方式操作的循环类型。这两种方法在许多向量机上采用。多功能部件的并行操作。链接技术：要实现链接，第三条指令与第一，二条指令均存在先写后读的相关冲突，因而可将第三条指令与第一，二条指令链接执行条件之外；还有时间上的要求，即：只有当前一条指令的第一结果分量R向的那一个时钟周期可链接，错过该时刻，就无法进行链接。要指出的是，当一条向量指令的两个源操作数分别是两条先行指令的结果R向时：要求先行两条指令产生的运算结果的时间必须相等(即有关功能部件的延迟时间相等)。上例中访存和浮点加的延时均为6个时间单位。还要求这两条向量指令的向量长度必须相等，否则就不可能链接。条件执行语句和稀疏矩阵和加速处理方法，向量归约操作的加速方法。向量处理性能的评估参数和方法在向量流水功能部件上执行一个长度为n的向量操作时间Tvp可用以下公式表示： Tvp=Ts+T1+(n-1) Tc=T0 +n Tc (6.2) Ts：建立流水线的时间。 T1：为第一对向量元素通过流水线时间。 Tc：流水线时钟周期。 T0 = Ts+T1-Tc 上式也可用下式表示： Tvp=sTc+lTc+(n-1) Tc=(s+l+n-1) Tc (6.3) s：建立流水线所需时钟周期数 l：完成每对向量元素操作所需的子操作数，即流水功能部件中的级数。 显然在上述流水线中，每对向量元素的平均执行时间是： R：当向量长度时，向量流水处理的渐近性能。 为了衡量向量流水线中的操作有效性，通常用半性能长度n1/2这一参数。 n1/2：指为了达到向量流水线最大性能值一半时所需要的向量长度。为了表达n1/2的含义，可将Tvp改成Tvp=(n1/2+n) Tc =(n1/2+n)/R (6.4) 由(6.2)和 (6.4)两式可知 Tvp=T0+n Tc =(n1/2+n) Tc 所以 n1/2= T0/ Tc 由(6.3)和 (6.4)两式可知 (n1/2+n) Tc =(s+l+n-1) Tc 所以 n1/2= s+l-1 因此 n1/2= T0/ Tc = s+l-1 对于串行方式工作的标量处理机，完成同样的向量操作所需时间Tsp为Tsp= Ts1+nlTcs =(s1+nl)/R (6.5) Tsl：标量循环建立时间。 Tcs ：标量部件工作的时钟周期。对于n个元素对，它的平均执行时间：第七章 存储体系引言-访存局部性原理时间局部性：如果一个存储项被访问，则可能很快再次被访问。空间局部性：如果一个存储项被访问，则可能该项及其邻近的项会很快地被访问。存储体系构成的基本原理：命中时间：在命中的情况下对上层存储器访存所需的时间(包括判断是否命中的时间)。失效时间：失效时的访存时间。包括对下层存储器的访问时间、将下层数据调入上一层所需的时间(传输时间)。层次化的存储体系还必须解决3个问题及其层次化的存储体系平均访问时间的计算。数据块在较高层次存储器存放在哪个位置？即块或页的定位问题。映象方法一般是查表。访存不命中时，将对下层进行访问，并将所查找的块调入上层，产生了替换的调度策略问题。在写访问时，写入上层存储器中的数据必须在适当时候存入下层存储器中，何时复制为宜？即数据写的方式问题，也即更新策略问题？ 平均访存时间=命中时间+失效时间失效率。Cache： Cache的地址变换和数据块的替换算法是由硬件实现。数据Cache：存放数据的Cache。指令Cache：存放指令的Cache。一体化Cache：即存放数据又存放指令的CacheCache性能分析：设Cache的大小一定时 块容量，Hc不高，访存空间局部性未利用。 块容量，调入相邻的数据越多。空间局部性得到利用，但块的数量要，时间的局部性得不到利用。 块的体积到一定程度，对命中率的影响越来越小，此时两种局部性规律的影响得到平衡。过这个平衡点，命中率随着块的增大而减小，这是空间局部性规律作用越来越小，时间部性律性起了主导作用。块的容量，块的调入时间，块的调入时间与块的大小是线性关系。平均访问速度： Tc：Cache的访问时间 Tm：MM的访问时间 Hc：Cache的命中率 Ta：平均读存时间Ta= Hc Tc+(1- Hc )Tm采用Cache后，读存速度的提高倍数为：更新策略有两种：全写法(Writethrough)：又称写直达法，即将写入的数据同时写入Cache和MM。写回法(Writeback)：写入Cache时暂不写入MM仅当被写入Cache的数据块被替换出去时，才写回MM。1. 直接映像法，2. 组相联映象法。Cache读取数据块的三种方式：需要时读取：只要不命中Cache，就从MM读取。方式比较简单，不需要额外的硬件支持或在表格中增加标记。预读取：读取时在一个存储块需要之前就预先读入Cache之中。简单的预读取方法是在读取第i块时把第i+1块也读入(若第i +1块不在Cache中)。选择性读取：根据情况决定是否进行预取。替换策略：RAND（随机）,FIFO,LRU(最近最少使用)MM及带宽拓宽方法：提高MM性能的方法； MM的主要性能指标是容量、速度、价格。 速度：访问时间，访存周期和带宽。 访问时间：从地址到达至MM输出所需时间。 周期：存储器两次访存的最小间隔时间。 带宽：存储器两次访存时的数据吞吐率。单位是bit/s或Byte/s。 提高主存的带宽，可采用更新结构的措施： 增加存储体的数据宽度，同时要求Cache数据宽度也增加。 采用多体交叉技术。多个存储体作为存储器的并行模块，使得总的数据吞吐率得到提高。 用新型存储芯片提高存储性能。多体交叉存储器：1. 高位交叉存储器地址由n位构成高位交叉存储器使地址高位段分别指向不同的存储体。低位地址用于选择一个体内不同存储单元。2. 低位地址多体交叉低位地址指向不同的存储体，高位段为选择一个体内地址单元。拓宽存储器带宽的方法：采用突发式(Burst Mode)传送，即在一个总线操作周期中以数据块传送方式将数据块从MM调入Cache第八章 I/O子系统BUS的概念：BUS是连接数字系统的信号线集。系统中可以有多个层次的BUS：芯片级、板级和系统级。 芯片级BUS即CPU芯片内部BUS，也称内部BUS。 板级BUS是连接印刷电路板中的各个部件的，通常也称为局部BUS。 系统级BUS是连接各印刷电路板。TCPU计算：考虑CPU和I/O处理的并行性，总处理时间为TWORKLOAD= TCPU+TI/OTOVERLAP其中 TOVERLAPmax(TCPU，TI/O)I/O 控制器的管理方式有三种： 程序控制 DMA I/O处理机方式 ，这种I/O子系统具有更强的功能。它执行自己的程序，除了完成数据传送外，还能进行数据变换、装配、拆卸、和校验等。通道流量的计算：Channel流量指通道在传送数据时，单位时间性内传送的字节数，其所能达到的最大流量称为Channel的极限流量。对于字节多路通道，要求设计的通道的极限流量 Channel所接各外设的字节传送速率之和 (实为设计时字节多路通道流量极限流量)。设有P台外部设备，则：TS：Channel选择设备的时间。TD：传送1B需要时间。实际流量： fi为第i台设备的流量 例题见教材。选择通道流量：n：传送一个数据块的字节数。因为传送一数据块才选择一次设备，所以传送一数据据块的时间为nTD+TS。则传送一个字节所需时间为TD+TS/n。实际流量为所接设备传送率中最大的一个 数组多路通道 也是传送一组数据之后，再选择另一台设备，若一组数据中有k个字节，则每隔k个字节才选择一次设备，所以实际流量也是所接设备传送率中最大的一个的一个数据传送率： 第九章 并行处理技术并行处理技术的发展，并行性：同时性和并发性。并行性是指在数值计算、数据处理、信息处理或是人工智能求解过程中可能存在某些可同时进行运算或操作的部分。并行性主要是指同时性或并发性。同时性在时间概念上要求较严，它是指同一时刻发生的两个或多个事件。并发性是指在同一段时间间隔内发生的两个或多个事件。 并行性指一种相对于串行处理的信息处理方式。它着重开发计算过程中存在的并发事件。并行粒度大小G可用以下公式表示(假定系统中共有P个处理器)。TW表示所有处理器进行计算的时间总和。TC表示所有处理器通信的时间总和。粒度：细粒度，粗粒度。 粗粒度并行开发主要采用MIMD方式。 细粒度并行开发主要采用SIMD方式。并行处理是指在这些层次上的任何一级或多级上的并行性开发。层次越高的并行处理粒度就越粗。而低层次上的并行处理粒度就较细。开发并行性，一般采用资源重复、时间重叠和资源共享三种：资源重复：通过使用多功能部件，引入空间重复因素，例：几个完全相同的处理器受同一控制器控制的SIMD方式的工作系统，就是利用资源重复的例子。时间重叠：是在并行概念中引入时间因素，让多个处理过程在时间上相互错开，重叠使用同一套部件的各部分，像流水操作。图9.3 阵列机两种结构类型资源共享：采用软件手段让多用户按时间片来轮流使用同一套硬件资源，以提高利用率，像多道程序和分时系统。SIMD并行计算机(阵列机)。阵列机通常由一个控制器(CU)、N个处理机单元(PE)、M 个MM模块(M)以及一个互连网络部件(IN)所组成。阵列机可分为两个基本结构：分布式存储器阵列机和集中共享存储器的阵列机。阵列机以单指令流多数据流方式工作的，特点如下：采用资源重复方法引入空间因素，即系统中设置多个相同的处理单元开发并行性，这与利用时间重叠的流水线处理机是不一样的。此外它是利用并行性中的同时性，而不是并发性，所有处理单元必须同时进行相同的操作。它是以某一类算法为背景的专用计算机。阵列机的研究必须与并行算法研究密切结结合，以使它的求解算法的适应性更强一些，应用面更广一些。从处理单元看，由于都是相同的，因而可将阵列机看成是一个同构型并行机，但它的控制器(CU)实质上是一个标量处理机，为了完成I/O操作及OS的管理，尚需一个前端机，因此实际的阵列机系统由上述三部分构成的一个异型多处理机系统。计算机互连网及互连函数。静态网络中的连接是固定的链路，在运行中不能更改，不能进行控制，而动态网络中的连接是当需要时才建立的，在运行中可以通过开关状态加以控制。 静态网络按连接的互连模式可进一步分为一维、二维、立方体(三维)或超立方体的(三维以上)。 动态网络按互连方式可分为基于总线和基于交换的网络。基于总线的网络又可进一步分为单总线和多总线的网络。基于交换的动态网络按照互连网络的结构又可进一步分为单级、多级和交叉开关网络。衡量互连网性能好坏的主要因素是它的连接度、延时性、带宽、可靠性和成本。连接度是指一个结点与其他结点的连接程度，一个结点连接的其他结点数越多，连接度就越高，表明连接性越好。延时性：指从一个结点传送信息到任何另一个结点所需的时间。通常可用结点间最大距离表示。通信工作方式 可分为同步和异步两种。 同步：不论各个PE对数据进行并行操作还是由控制器向PE广播命令，都由统一的时钟加以同步。 异步：不用统一时钟加以同步，各个PE根据需要相互建立动态连接。控制策略 分为集中和分散两种 集中式控制：由一个统一的控制器对各个互连的开关状态加以控制。 分散式控制：由各个互连开关自身实行管理。 一般SIMD并行机采用集中控制。交换方式： 分为线路交换和分组交换 线路交换：是在整个交换过程中，在源和目标结点之间建立固定的物理通路，适用于成批数据传送。 分组交换：把要传送的信息分成多个分组，分别送入互连网，这些分组可通过不同的路由到达目标结点。因此适用于短报文传送。 SIMD并行机一般采用线路交换方式。 MIMD多机系统往往采用分组交换方式。网络拓朴：分为静态和动态两种图9.11 静态有限互连网络的结构示意图静态拓扑：指各结点间有专用的连接通路，且在运行中不能改变。1. 全互连网络 链路数为N(N-1)/22. 有限互连网络 l 线形阵列网络直径为N-1l 环状网络，其网络直径为N/2l 树状网络3. 网格互连网络在一个n立方体中，每个结点的度为n。超立方体是一种对数的体系结构，这是因为在含有N=2n个结点的n立方体中，一个消息为到达它的目的地而必须遍历的最大链路数为log2N=n。动态拓扑：则因设置有源开关，所以可根据需要借助控制信号对连接通路加以重新组合。a) 基于总线的动态互连网络：单总线系统 单总线网络复杂性(空间复杂性)由所使用的总线数衡量，为O(1)，而时间复杂性由输入到输出的总延迟衡量，为O(N)。多总线系统可能的连接方案有：全总线一存储器连接的多总线，将所有存储器模块连接到所有总线。单总线一存储器连接的多总线，使每个存储器模块连接到一个特定的总线。部分总线一存储器连接的多总线。使每个存储器模块连接到一个总线子集组。总线仲裁器和仲裁算法仲裁器一般由某种仲裁算法和相应的实现硬件构成。仲裁算法有：静态优先级算法、固定时间片算法、动态优先级算法以及先来先服务算法。b) 基于交换的动态互连网络3种基本的互连拓扑：交叉开关、单级和多级。 静态互连网络的性能指标：影响互连网络性能好坏的主要因素是它的时延、带宽、网络直径、连接度、平均距离、成本和对称性。网络时延是指经过网络传输单个消息所需的时间，包括通道延迟和交换(开关)延迟，依赖于网络硬件。它与通信时延不同。通信时延是指传送消息所需的总时间，包括软件开销和接口延迟，通常与结点间的最大距离密切相关。消息时延是指发送0长度消息所需的时间，包括所需的软、硬件开销(路由查找、打包、解包等)。网络带宽是指互连网络在单位时间内可传输的字节数，它是网络拓扑结构、通道宽度、通道数量、网络规模(端口数量)、交换度、网络时钟频率的函数网络直径是指任何两个结点间最短距离中的最长者。连接度是指一个结点与其他结点的连接程度，也称为结点度，是指进入和离开一个结点的通道数的总和。平均距离是指一个消息在静态网络中传播的平均距离，其计算公式如下：其中，D是网络直径，Nd是对于一个给定的结点，与其距离为d的结点个数。成本通常用互连网络中所用的链路数来衡量。对称性是指如果将任何结点标识为原点它都同形于本身，即从任何结点观察网络都是一样的。环状和环绕网络是对称的，而线形阵列和网格网络则不对称。并行MM的无冲突访问。要对一维数组中元素实现无冲突访问，一般比较容易，只要将MM存储体分体数取成质数，且与跳步距离互质就可以实现无冲突访问。多处理机多处理机的主要特征及其分类：特征表现在以下几方面： 具有更大的灵活性和更强的通用性，适宜于求解通用算法，它能灵活地开发数据并行性和功能并行性，而SIMD系统只能开发数据并行性。因此通用性较差。 主要开发高层次作业及任务级(粗粒度)并行性。 SIMD机开发低层次操作一级的并行性。 并行任务的派生需要显式的专用语句或指令加以表示。SIMD中并行操作由单独指令表示的控制，故不需要设置专门的指令。 并发执行的进程间的同步需采取特殊措施，以保证原来的正确语义。而SIMD机中，由于受同一控制器控制，因此工作自然是同步的。对资源分配和任务分派要进行良好的调度，因此要采用软件的手段，否则系统性能将受很大的影响。SIMD机中往往只需用屏蔽来控制实际参加并行操作的PE数目。 MIMD系统在执行条件语句(如ifthenelse)时，比SIMD有更高的效率。由于是多指令流的特性，MIMD中每个处理单元，犹如单机一样，能独立地按任一方向执行。 在SIMD机中，当“条件”与处理单元中的局部数据相关时，就必须串行执行“then”模块和“else”模块。MIMD的异步特性使得它在执行一串完成时间可变的指令时，比SIMD有更快的速率。MIMD多机系统分类：l 多向量机(Multi Vector Processors。MVP)；l 对称多处理机(Symmetric Multiprocessor，SMP)；l 非均匀存储器访问多处理机(Non Uniform Memory Access，NUMA)；l 大规模并行处理机(Massively Parallel Processor，MPP) ；l 机群(Cluster)。多处理机在系统结构上可分为两类：紧耦合型和松耦合型。紧耦合系统按所用处理机类型是否相同及对称，又可分为同构或异构以及对称或非对称形式，常见的组合是同构对称式多机系统及异构非对称式多机系统。程序并行性的分析程序中数据相关性分析：数据相关，数据反相关，数据输出相关。数据相关 若语句P1左边变量出现在P2的右边变量集内时，则称P2 数据相关于P1，例：P1：A=B+CP2 ：D=AC数据反相关 若子P2的左边变量出现在P1的右边变量集内时，则称P1数据反相关于P2 。 例P1：A=B+CP2 ：C=ED 为了保证语义正确性，必须等P1将变量C读出后， P2方可将变量C写入数据，即必须先读后写。数据输出相关 若子P1和P2左边变量相同，则称P2数据输出相关于P1 。 例P1：A=B+CP2 ：A=ED 为保证语义正确性，必须保证P1先写入A，然后允许P2写入A。 除了上述三种相关外，还存在一种特殊情况：即两程序段的输入变量互为输出变量。此时，两者必须并行执行，方可保证语义的正确性，这就要求硬件机构能保证两者进行同步读写。伯恩斯坦的自动判别数据相关准则。设每个程序段在执行过程中通常使用输入和输出这两个分离的变量集。 Ii表示Pi程序段中操作所要读取的存储单元集。 Oi表示要写入的存储单元集。 则P1和P2两个程序段能并行执行的伯恩斯坦准则为： I1O2=，即P1的输入变量集与P2输出变量集不相交。 I2O1=，即P2的输入变量集与P1输出变量集不相交。 O1O2=，即P1与P2输出变量集不相交。例:若有P1、P2和P3三个求矩阵运算的算术表达式 P1：X=(A+B)(AB) P2：Y=(CE)(C+D)E P3：Z=X+Y 其中A、B、C、D、E均为nn的矩阵，它们的输入、输出变量集分别为 I1=A，B，I2=C，D，E， I3=X，Y O1=X， O2=Y， O3=Z 因为I1O2=， I2O1=，O1O2=所以P1和P2可以并行执行。 而 I3O1且I3O2，所以P3必须在P1和P2执行之后方可执行。并行语言的开发通常有两种方法：在现有高级语言的基础上扩展能表示并行进程结构的成分。称为扩展式并行程序语言。如并行FORTRAN和并行C。设计全新的并行语言第十章 新型计算机系统结构t1b+2t2b-2at1* t2一、计算模型分类控制驱动、数据驱动、需求驱动和模式匹配驱动四种类型。设有 a=(b+2)(b1)1. 控制驱动、共享