计算机系统结构

更新时间:2025-05-23 22:33:10 阅读：评论：0

计算机系统的层次结构第6级（虚拟机）应用语言机器第5级（虚拟机）高级语言机器第4级（虚拟机）汇编语言机器第3级（虚拟机）操作系统机器第2级（物理机）传统机器语言机器第1级（物理机）微程序机器

计算机系统结构定义

计算机系统结构是指传统计算机程序员所看到的计算机属性，即概念性结构与功能特性计算机系统结构的实质是确定计算机系统中软硬件的交界面，界面之上是软件实现的功能，界面之下是硬件和固件实现的功能

计算机组成和计算机实现

计算机组成是计算机系统结构的逻辑实现，包含物理机器级别中的数据流和控制流的组成以及逻辑设计等计算机实现是计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，模块、插件、地板的划分与连接，信号传输，电源、冷却及整机装配技术等

计算机系统结构的划分 Flynn分类法

按照指令流和数据流的多倍性分类

指令流：计算机执行的指令序列数据流：由指令调用的数据序列多倍性：在系统最受限的部件上，同时处于同一执行阶段的指令或数据的最大数目

分为4类：

单指令流单数据流单指令流多数据流多指令流单数据流多指令流多数据流冯氏分类法

按照最大并行度分类最大并行度Pm定义为：计算机系统在单位时间内能够处理的最大二进制位数用平面直角坐标系中的一个点代表一个计算机系统，其横坐标表示字宽（n位），纵坐标表示一次能同时处理的字数（m字）。m×n就表示了其最大并行度。

Handler分类法

根据并行的和流水线分类将硬件分为三个层级：

程序控制部件（PCU）的个数算术逻辑部件（ALU）或处理部件（PE）的个数d 每个算术逻辑部件包含基本逻辑线路（ELC）的套数w

计算机系统的结构可以表述为： $$t(系统型号)=(k, d, w)$$ 为了进一步反映流水线的特性，公式改进为： $$t(系统型号)=(k*k', d*d', w*w')$$ 其中k'表示宏流水线中程序控制部件的个数，d'表示指令流水线中算术逻辑部件的个数，w'表示操作流水线中的基本线路的套数

计算机系统设计的定量原理 Amdahl定律

$$加速比 = \frac{系统性能_{改进前}}{系统性能_{改进后}} = \frac{总执行时间_{改进前}}{总执行时间_{改进后}}$$

可改进部分的执行时间在总时间中的占比，简称可改进比例：$$Fe$$ 可改进部件改进后性能提被绑架的美女高的倍数，即改进前所需的执行时间与改进后执行时间的比：$$Se$$

$$T_n = T_0 (1 - Fe + \frac{Fe}{Se})$$ $$S_n = \frac{T_0}{T_n} =\frac{1}{(1 - Fe) + \frac{Fe}{Se}}$$ 例题

CPU性能公式

执行一个程序所需的CPU时间： $$CPU时间 = 执行程序所需的时钟周期数 * 时钟周期时间$$ 其中时钟周期数是时钟频率的倒数引入CPI，即每条指令的平均时钟周期数，有时简称为指令的平均时钟周期数： $$CPI = 执行程序所需的时钟周期数 / 所执行的指令条数$$ 因此有CPU性能公式： $$CPU时间 = IC * CPI * 时钟周期时间$$ 其中IC为所执行的指令条数 CPU时钟周期总数 $$CPU时钟周期数 = \sum^{n}_{i=1}{CPI_i * IC_i}$$ 此时CPU性能公式为： $$CPU时间 = CPU时钟周期数 * 时钟周期时间 = \sum^{n}_{i=1}{CPI_i * IC_i} * 时钟周期时间$$ CPI可表示为： $$CPI = \frac{时钟周期数}{IC} = \frac{\sum^{n}_{i=1}{CPI_i * IC_i}}{IC} = \sum^{n}_{i=1}{CPI_i * \frac{IC_i}{IC}}$$ 例题

计算机系统的性能评测

X的性能是Y的n倍： $$\frac{Y的执行时间}{X的执行时间} =六级试卷 n = \frac{\frac{1}{性能_y}}{\frac{1}{性能_x}} = \frac{性能_x}{性能_y}$$ 二、流水线技术

什么是流水线

把一个重复过程分解为若干个子过程，每个子过程由专门的功能缓解压力部件来实现流水线中的每个子过程或及其功能部件称为流水线的级或段流水线的段数称为流水线的深度

流水线的分类部件级流水线、处理机流水线及系统级流水线

按照流水技术用于计算机系统的不同阶段

单功能流水线与多功能流水线

按照流水线所完成的功能

单功能流水线：只能完成一种固定功能的流水线多功能流水线：流水线的各段可以进行不同的连接，以实现不同的功能。静态流水线与动态流水线

多功能流水线可以进一步分为静态流水线和动态流水线静态流水线静态流水线是指在同一时间内，多功能流水线中的各段只能按照同一种功能的连接方式工作的流水线动态流水线动态流水线是指在同一时间内，多功能流水线中的各段可以按照不同方式连接，同时执行多种功能的流水线

线性流水线和非线性流水线线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次非线性流水线：流水线中除了有串行的连接外，还有反馈回路顺序流水线和乱序流水线

根据流水线中任务流入和流出的顺序是否相同

顺序流水线：流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。每一个任务在流水线的各段中是一个跟着一个顺序流动的乱序流水线：流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同，允许后进入流水线的任务先完成（从输出端流出）。也称为无序流水线、错序流水线、异步流水线标量处理机与向量流水处理机

把指令执行部件中采用了流水线的处理机称为流水线处理机。

标量处理机：处理机不具有向量数据表示和向量指令，仅对标量数据进行流水处理。向量流水处理机：具有向量数据表示和向量指令的处理机。

向量数据表示和流水技术的结合。

流水线的性能指标流水线的吞吐率

单位时间内流水线所完成的任务数量或输出结果的数量。 $$TP = \frac{n}{T_k}$$ n为任务数，Tk是处理完n个任务所用的时间

各段时间均相等的流水线

流水线完成n个连续任务所需要的总时间为：（假设一条k段线性流水线） $$T_k = k \delta t + (n-1)\delta t = (k+n-1) \delta t$$ 流水线实际吞吐率为： $$TP = \frac{n}{ (k+n-1) \delta t}$$ 最大吞吐率为： $$TP_{max} = lim_{n \to \infty} \frac{n}{ (k+n-1) \delta t} = \frac{1}{\delta t}$$ 最大吞吐率与实际吞吐率的关系： $$TP = \frac{n}{n+k-1} TP_{max}$$

各段时间不完全相等的流水线

流水线中这种时间最长的段称为流水线的瓶颈段各段时间不等的流水线的实际吞吐率为：Δti为第i段的时间，共有k个段） $$TP = \frac{n}{\sum^{k}_{i=1}{\delta t_i}+(n-1)max(\delta t_1, \delta t_2, ... ,\delta t_k)}$$ 流水线最大吞吐率： $$TP_{max} = \frac{1}{max(\delta t_1, \delta t_2, ... ,\delta t_k)}$$ 消除瓶颈方法：

细分瓶颈段

重复设置瓶颈段

改进后 $$TP_{max} = \frac{1}{\delta t}$$

流水线的加速比

加速比是指使用顺序处理方式处理一批任务所用时间与流水线使用流水处理方式处理同一批任务所用时间之比。 $$S = \frac{T_s}{T_k}$$

流水线各段时间相等（都是△t）

$$S = \frac{nk\delta t}{(k+n-1)\delta t} = \frac{nk}{k+n-1}$$ 最大加速比 $$S_{max} = lim_{n \to \infty}\frac{nk}{k+n-1} = k$$

流水线的各段时间不完全相等时

一条k段流水线完成n个连续任务的实际加速比为： $$S = \frac{n\sum^{k}_{i=1}\delta t_{i}}{\sum^{k}_{i=1}\delta t_{i}+(n-1)max(\delta t_1, \delta t_2, ... ,\delta t_k)}$$

流水线的效率

流水线的效率即流水线设备的利用率，它是指流水线中的设备实际使用时间与整个运行时间的比值

各段时间相等

$$e_1 = e_2 = e_3 = ... = e_k = \frac{n \delta t}{T_k} = \frac{n}{k+n-1}$$ 整条流水线的效率为： $$E = \frac{e_1 + e_2 + e_3 + ... + e_k}{k} = \frac{ke_1}{k} = \frac{kn\delta t}{kT_k}$$ $$E = \frac{n}{k+n-1}$$ 最高效率： $$E_{max} = lim_{n \to \infty}\frac{n}{k+n-1} = 1$$ 得到： $$E = TP*\delta t$$ $$E = \frac{S}{k}$$

各段时间不等

$$E = \frac{n\sum^{k}_{i=1}\delta t_{i}}{k[\sum^{k}_{i=1}\delta t_{i}+(n-1)max(\delta t_1, \delta t_2, ... ,\delta t_k)]}$$ 例题

非线性流水线的调度单功能非线性流水线的最优调度

向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离会引起非线性流水线功能段使用冲突的启动距离则称为禁用启动距离启动距离和禁用启动距离一般都用时钟周期数来表示，是一个正整数预约表

横向（向右）：时间（一般用时钟周期表示）纵向（向下）：流水线的段

如果在第n个时钟周期使用第k段，则在第k行和第n列的交叉处的格子里有一个√ 如果在第k行和第n列的交叉处的格子里有一个√，则表示在第n个时钟周期要使用第k段

根据预约表写出禁止表F

禁止表F：一个由禁用启动距离构成的集合。具体方法：对于预约表的每一行的任何一对√，用它们所在的列号相减（大的减小的），列出各种可能的差值，然后删除相同的，剩下的就是禁止表的元素。在上例中：

第一行的差值只有一个：8；第二行的差值有3个：1，5，6；第3行只有一个√，没有差值；第4和第5行的差值都只有一个：1；

其禁止表是：F= { 1，5，6，8 }

根据禁止表F写处处是冲突向量C0

冲突向量C：一个N位的二进制位串。进行从一个集合到一个二进制位串的变换设$$C_0 = (c_Nc_{N-1}...c_i...c_2c_1)$$,则： $$C_i = \begin{cases} 1, & i \in F \\ 0, & i \notin F \end{cases}$$

根据初始冲突向量C0画出状态转换图当第一个任务流入流水线后，初始冲突向量C0决定了下一个任务需间隔多少个时钟周期才可以流入。在第二个任务流入后，新的冲突向量是怎样的呢？假设第二个任务是在与第一个任务间隔j个时钟周期流入，这时，由于第一个任务已经在流水线中前进了j个时钟周期，其相应的禁止表中各元素的值都应该减去j，并丢弃小于等于0的值。对冲突向量来说，就是逻辑右移j位（左边补0）。在冲突向量上，就是对它们的冲突向量进行“或”运算。 SHR(j)（C0）∨C0 其中:SHR(j)表示逻辑右移j位

推广到更一般的情况假设: Ck：当前的冲突向量 j: 允许的时间间隔则新的冲突向量为： SHR(j)（Ck）∨C0

对于所有允许的时间间隔都按上述步骤求出其新的冲突向量，并且把新的冲突向量作为当前冲突向量，反复使用上述步骤，直到不再产生新的冲突向量为止。从初始冲突向量C0出发，反复应用上述步骤，可以求得所有的冲突向量以及产生这些向量所对应的时间间隔。由此可以画出用冲突向量表示的流水线状态转移图。有向弧：表示状态转移的方向弧上的数字：表示引入后续任务（从而产生新的冲突向量）所用的时间间隔（时钟周期数）

根据状态转移图写出最优调度方案

根据流水线状态图，由初始状态出发，任何一个闭合回路即为一种调度方案。列出所有可能的调度方案，计算出每种方案的平均时间间隔，从中找出其最小者即为最优调度方案。上例中，各种调度方案及其平均间隔时间。最佳方案：（3，4）平均间隔时间：3.5个时钟周期（吞吐率最高）方案（4，3）的平均间隔时间也是3.5，但它不是最佳方案，为什么？奇数个任务是，最后一个是4，比3多

流水线的相关与冲突经典5段流水线取指 IF 以程序计数器PC中的内容作为地址，从存储器中取出指令并放入指令寄存器IR；同时PC值加4（假设每条指令占4个字节），指向顺序的下一条指令。

译码 ID 对指令进行译码，并用IR中的寄存器地址去访问通用寄存器组，读出所需的操作数。

执行 EX 不同指令所进行的操作不同： load和store指令：ALU把指令中所指定的寄存器的内容与偏移量相加，形成访存有效地址。寄存器－寄存器ALU指令：ALU按照操作码指定的操作对从通用寄存器组中读出的数据进行运算。寄存器－立即数ALU指令：ALU按照操作码指定的操作对从通用寄存器组中读出的操作数和指令中给出的立即数进行运算。分支指令：ALU把指令中给出的偏移量与PC值相加，形成转移目标的地址。同时，对在前一个周期读出的操作数进行判断，确定分支是否成功。

访存 MEM 该周期处理的指令只有load、store和分支指令。其它类型的指令在此周期不做任何操作。

写回 WB ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组。 ALU运算指令：结果数据来自ALU。 load指令：结果数据来自存储器。分支指令需要4个时钟周期（如果把分支指令的执行提前到ID周期，则只需要2个周期）； store指令需要4个周期；其它指令需要5个周期才能完成。

采用流水线方式实现时，应解决好以下几个问题要保证不会在同一时钟周期要求同一个功能段做两件不同的工作避免IF段的访存（取指令）与MEM段的访存（读/写数据）发生冲突 ID段和WB段都要访问同一寄存器文件考虑PC的问题 5段流水线的两种描述方式

第一种：类似时空图

第二种：按时间错开的数据通路序列

相关与流水线冲突

相关有三种类型：数据相关、名相关、控制相关

流水线冲突是指对于具体的流水线来说，由于相关的存在，使得指令流中的下一条指令不能在指定的时钟周期执行。流水线冲突有三种类型：结构冲突、数据冲突、控制冲突

相关是程序固有的一种属性，它反映了程序中指令之间的相互依赖关系。具体的一次相关是否会导致实际冲突的发生以及该冲突会带来多长的停顿，则是流水线的属性。

可以从两个方面来解决相关问题

保持相关，但避免发生冲突。指令调度

通过代码变换，消除相关

程序顺序由原来程序确定的在完全串行方式下指令的执行顺序。只有在可能会导致错误的情况下，才保持程序顺序。控制相关并不是一个必须严格保持的关键属性对于正确地执行程序来说，必须保持的最关键的两个属性是：数据流和异常行为。

保持异常行为是指：无论怎么改变指令的执行顺序，都不能改变程序中异常的发生情况。即原来程序中是怎么发生的，改变执行顺序后还是怎么发生。弱化为：指令执行顺序的改变不能导致程序中发生新的异常。

数据流：指数据值从其产生者指令到其消费者指令的实际流动。分支指令使得数据流具有动态性，因为一条指令有可能数据相关于多条先前的指令。分支指令的执行结果决定了哪条指令真正是所需数据的产生者。

有时，不遵守控制相关既不影响异常行为，也不改变数据流。可以大胆地进行指令调度，把失败分支中的指令调度到分支指令之前。

动态分支预测技术

动态分支预测：在程序运行时，根据分支指令过去的表现来预测其将来的行为。

如果分支行为发生了变化，预测结果也跟着改变。有更好的预测准确度和适应性。

分支预测的有效性取决于：

预测的准确性预测正确和不正确两种情况下的分支开销

决定分支开销的因素：

流水线的结构预测的方法预测错误时的恢复策略等

采用动态分支预测技术的目的

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

在预测错误时，要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。

采用分支历史表BHT

分支历史表BHT（Branch History Table）

最简单的动态分支预测方法。用BHT来记录分支指令最近一次或几次的执行情况（成功还是失败），并据此进行预测。

采用两位二进制位来记录历史

提高预测的准确度研究结果表明：两位分支预测的性能与n位（n>2）分支预测的性能差不多

两位分支预测中的操作有两个步骤：

分支预测；当分支指令到达译码段（ID）时，根据从BHT读出的信息进行分支预测。若预测正确，就继续处理后续的指令，流水线没有断流。否则，就要作废已经预取和分析的指令，恢复现场，并从另一条分支路径重新取指令。

状态修改

BHT方法只在以下情况下才有用：判定分支是否成功所需的时间大于确定分支目标地址所需的时间前述5段经典流水线：由于判定分支是否成功和计算分支目标地址都是在ID段完成，所以BHT方法不会给该流水线带来好处。

采用目标缓冲器

目标：将分支的开销降为0 方法：分支目标缓冲

将分支成功的分支指令的地址和它的分支目标地址都放到一个缓冲区中保存起来，缓冲区以分支指令的地址作为标识这个缓冲区就是分支目标缓冲器（Branch-Target Buffer，简记为BTB，温布尔顿或者分支目标Cache（ranch-Target Cache）

BTB的结构

看成是用专门的硬件实现的一张表格。表格中的每一项至少有两个字段：

执行过的成功分支指令的地址；（作为该表的匹配标识）预测的分支目标地址。

采用BTB后，各种可能情况下的延迟：

BTB的另一种形式在分支目标缓冲器中增设一个至少是两位的“分支历史表”字段

更进一步，在表中对于每条分支指令都存放若干条分支目标处的指令，就形成了分支目标指令缓冲器。

多指令流出技术

在每个时钟周期内流出多条指令，CPI＜1

多流出处理机有两种基本风格

超标量（Superscalar）在每个时钟周期流出的指令条数不固定，依代码的具体情况而定。（有个上限）设这个上限为n，就称该处理机为n-流出。可以通过编译器进行静态调度，也可以基于Tomasulo算法进行动态调度。

超长指令字VLIW（Very Long Instruction Word）在每个时钟周期流出的指令条数是固定的，这些指令构成一条长指令或者一个指令包。指令包中，指令之间的并行性是通过指令显式地表示出来的。指令调度是由编译器静态完成的。

超标量处理机与VLIW处理机相比有两个优点：

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

要想达到很好的效果，方法之一：使用动态超标量调度技术。

基于静态调度的多流出技术在典型的超标量处理器中，每个时钟周期可流出1到8条指令指令按序流出，在流出时进行冲突检测

由硬件检测当前流出的指令之间是否存在冲突以及当前流出的指令与正在执行的指令是否有冲突。举例：一个4-流出的静态调度超标量处理机

在取指令阶段，流水线将从取指令部件收到1～4条指令（称为流出包）。在一个时钟周期内，这些指令有可能是全部都能流出，也可能是只有一部分能流出。

流出部件检测结构冲突或者数据冲突。一般分两阶段实现：第一段：进行流出包内的冲突检测，选出初步判定可以流出的指令；第二段：检测所选出的指令与正在执行的指令是否有冲突。

MIPS处理机是怎样实现超标量的呢？假设：每个时钟周期流出两条指令：1条整数型指令＋1条浮点操作指令其中：把load指令、store指令、分支指令归类为整数型指令。

要求：同时取两条指令（64位），译码两条指令（64位）。对指令的处理包括以下步骤：从Cache中取两条指令；确定那几条指令可以流出（0～2条指令）；把它们发送到相应的功能部件。

双流出超标量流水线中指令执行的时空图假设：所有的浮点指令都是加法指令，其执行时间为两个时钟周期。为简单起见，图中总是把整数指令放在浮点指令的前面。

采用“1条整数型指令＋1条浮点指令”并行流出的方式，需要增加的硬件很少。浮点load或浮点store指令将使用整数部件，会增加对浮点寄存器的访问冲突。增设一个浮点寄存器的读/写端口。

由于流水线中的指令多了一倍，定向路径也要增加。限制超标量流水线的性能发挥的障碍 load指令 load后续3条指令都不能使用其结果，否则就会引起停顿。

分支延迟如果分支指令是流出包中的第一条指令，则其延迟是3个时钟周期；否则就是流出包中的第二条指令，其延迟就是两个时钟周期。

超长指令字技术把能并行执行的多条指令组装成一条很长的指令；（100多位到几百位）设置多个功能部件；指令字被分割成一些字段，每个字段称为一个操作槽，直接独立地控制一个功能部件；在VLIW处理机中，在指令流出时不需要进行复杂的冲突检测，而是依靠编译器全部安排好了。 VLIW存在的一些问题程序代码长度增加了提高并行性而进行的大量的循环展开；指令字中的操作槽并非总能填满。解决：采用指令共享立即数字段的方法，或者采用指令压缩存储、调入Cache或译码时展开的方法。

采用了锁步机制任何一个操作部件出现停顿时，整个处理机都要停顿。

机器代码的不兼容性

多流出处理器受到的限制主要受以下3个方面的影响：

程序所固有的指令级并行性硬件实现上的困难超标量和超长指令字处理器固有的技术限制

超流水线处理机

将每个流水段进一步细分，这样在一个时钟周期内能够分时流出多条指令。这种处理机称为超流水线处理机。对于一台每个时钟周期能流出n条指令的超流水线计算机来说，这n条指令不是同时流出的，而是每隔1/n个时钟周期流出一条指令。实际上该超流水线计算机的流水线周期为1/n个时钟周期。

一台每个时钟周期分时流出两条指令的超流水线计算机的时空图。

在有的资料上，把指令流水线级数为8或8以上的流水线处理机称为超流水线处理机。典型的超流水线处理器：SGI公司的MIPS系列R4000 R4000微处理器芯片内有2个Cache：指令Cache和数据Cache东莞太子酒店容量都是8KB 每个Cache的数据宽度为64位

R4000的核心处理部件：整数部件一个32×32位的通用寄存器组一个算术逻辑部件（ALU）一个专用的乘法/除法部件

浮点部件一个执行部件浮点乘法部件浮点除法部件浮点加法/转换/求平方根部件（它们可以并行工作）

一个16×64位的浮点通用寄存器组。浮点通用寄存器组也可以设置成32个32位的浮点寄存器。

R4000的指令流水线有8级

IF：取指令的前半步，根据PC值去启动对指令Cache的访问。 IS：取指令的后半步，在这一级完成对指令Cache的访问。 RF：指令译码，访问寄存器组读取操作数，冲突检测，并判断指令Cache是否命中。 EX：指令执行。包括：有效地址计算，ALU操作，分支目标地址计算，条件码测试。 DF：取数据的前半步，启动对数据Cache的访问。 DS：取数据的后半步，在这一级完成对数据Cache的访问。 TC：标识比较，判断对数据Cache的访问是否命中。 WB：load指令或运算型指令把结果写回寄存器组。

四、存储系统

存储系统的层次结构

计算机系统结构设计中关键的问题之一：如何以合理的价格，设计容量和速度都满足计算机系统要求的存储器系统？人们对这三个指标的要求

容量大、速度快、价格低

三个要求是相互矛盾的

速度越快，每位价格就越高；容量越大，每位价格就越低；容量越大，速度越慢。

解决方法：采用多种存储器技术，构成多级存储层次结构。

程序访问的局部性原理：对于绝大多数程序来说，程序所访问的指令和数据在地址上不是均匀分布的，而是相对簇聚的。(局部性原理) 程序访问的局部性包含两个方面时间局部性：程序马上将要用到的信息很可能就是现在正在使用的信息。空间局部性：程序马上将要用到的信息很可能与现在正在使用的信息在存储空间上是相邻的。

存储系统的多级层次结构

假设第i个存储器Mi的访问时间为Ti，容量为Si，平均每位价格为Ci，则访问时间：T1< T2 < … < Tn 容量：S1< S2 < … < Sn 平均每位价格：C1> C2> … > Cn

整个存储系统要达到的目标：从CPU来看，该存储系统的速度接近于M1的，而容量和每位价格都接近于Mn的。存储器越靠近CPU，则CPU对它的访问频度越高，而且最好大多数的访问都能在M1完成。

存储层次的性能参数

下面仅考虑由M1和M2构成的两级存储层次：

M1的参数：S1，T1，C1 M2的参数：S2，T2，C2

存储容量S 一般来说，整个存储系统的容量即是第二级存储器M2的容量，即S=S2。每位价格C $$C = \frac{C_1S_1+C_2S_2}{S_1+S_2}$$ 当S1<<S2时，C≈C2。命中率H和不命中率F 命中率：CPU访问存储系统时，在M1中找到所需信息的概率。 $$H = \frac{N_1}{N_1+N_2}$$

N1── 访问M1的次数 N2 ── 访问M2的次数

不命中率：$$F = 1 - H$$ 平均访问时间TA $$T_A = HT_1 + (1-H)(T_1+T_2) \\ = T_1 + (1-H)T_2 \\ = T_1 + FT_2$$

当命中时，访问时间即为T1（命中时间）当不命中时，情况比较复杂。不命中时的访问时间为： T2＋TB＋T1＝T1＋TM TM ＝T2＋TB

不命中开销TM：从向M2发出访问请求到把整个数据块调入M1中所需的时间。传送一个信息块所需的时间为TB。三级存储系统

三级存储系统

Cache（高速缓冲存储器）主存储器磁盘存储器（辅存）

可以看成是由“Cache—主存”层次和“主存—辅存”层次构成的系统。

从主存的角度来看

“Cache－主存”层次：弥补主存速度的不足 “主存－辅存”层次：弥补主存容量的不足

存储层次的四个问题

当把一个块调入高一层(靠近CPU)存储器时，可以放在哪些位置上?（映象规则）当所要访问的块在高一层存储器中时，如何找到该块?（查找算法）当发生不命中时，应替换哪一块？（替换算法）当进行写访问时，应进行哪些操作?（写策略） Cache基本知识

基本结构和原理 Cache是按块进行管理的。Cache和主存均被分割成大小相同的块。信息以块为单位调入Cache。

主存块地址（块号）用于查找该块在Cache中的位置。块内位移用于确定所访问的数据在该块中的位置。

映象规则全相联映象全相联：主存中的任一块可以被放置到Cache中的任意一个位置。

直接映象直接映象：主存中的每一块只能被放置到Cache中唯一的一个位置。对于主存的第i块，若它映象到Cache的第j块，则: j＝imod (M)（M为Cache的块数）设M=2^m，则当表示为二进制数时，j实际上就是i的低m位:

组相联映象组相联：主存中的每一块可以被放置到Cache中唯一的一个组中的任何一个位置。

组的选择常采用位选择算法若主存第i块映象到第k组，则: k＝i mod（G）（G为Cache的组数）设G＝2^g，则当表示为二进制数时，k 实际上就是i 的低g 位: 低g位以及直接映象中的低m位通常称为索引。 n 路组相联：每组中有n个块(n＝M/G ) n 称为相联度相联度越高，Cache空间的利用率就越高，块冲突概率就越低，不命中率也就越低。

主存块的块地址的高位部分，称为标识。每个主存块能唯一地由其标识来确定

并行查找与顺序查找提高性能的重要思想：主候选位置(MRU块) （前瞻执行）并行查找的实现方法相联存储器目录由2^g个相联存储区构成，每个相联存储区的大小为n×(h+log2n)位。根据所查找到的组内块地址，从Cache存储体中读出的多个信息字中选一个，发送给CPU。

单体多字存储器＋比较器优缺点

不必采用相联存储器，而是用按地址访问的存储器来实现。所需要的硬件为：大小为2^g ×n×h位的存储器和n个h位的比较器。当相联度n增加时，不仅比较器的个数会增加，而且比较器的位数也会增加。

Cache的工作过程例子：DEC的Alpha AXP21064中的内部数据Cache 简介

容量：8KB 块大小：32B 块数：256 映象方法：直接映象写缓冲器大小：4个块

“读”访问命中（完成4步需要2个时钟周期） Cache的容量与索引index、相联度、块大小之间的关系 Cache的容量=2^index×相联度×块大小把容量为8192、相联度为1、块大小为32（字节）代入：索引index：8位标识：29－8＝21位 “写”访问命中设置了一个写缓冲器（提高“写”访问的速度）按字寻址的，它含有4个块，每块大小为4个字。当要进行写入操作时，如果写缓冲器不满，那么就把数据和完整的地址写入缓冲器。对CPU而言，本次“写”访问已完成，CPU可以继续往下执行。由写缓冲器负责把该数据写入主存。在写入缓冲器时，要进行写合并检查。即检查本次写入数据的地址是否与缓冲器内某个有效块的地址匹配。如果匹配，就把新数据与该块合并。发生读不命中与写不命中时的操作读不命中：向CPU发出一个暂停信号，通知它等待，并从下一级存储器中新调入一个数社保卡怎么用据块（32字节）。写不命中：将使数据“绕过”Cache，直接写入主存。对比：Alpha AXP 21264的数据Cache结构容量：64KB 块大小：64字节LRU替换策略主要区别

采用2路组相联采用写回法

没有写缓冲器

替换算法主要的替换算法有三种

随机法-优点：实现简单先进先出法FIFO 最近最少使用法LRU

最近最少使用法LRU 选择近期最少被访问的块作为被替换的块。（实现比较困难）

实际上：选择最久没有被访问过的块作为被替换的块。优点：命中率较高

LRU算法的硬件实现堆栈法

用一个堆栈来记录组相联Cache的同一组中各块被访问的先后次序。用堆栈元素的物理位置来反映先后次序栈底记录的是该组中最早被访问过的块，次栈底记录的是该组中第二个被访问过的块，…，栈顶记录的是刚访问过的块当需要标的资产替换时，从栈底得到应该被替换的块（块地址）

堆栈中的内容必须动态更新当Cache诈弹访问命中时，通过用块地址进行相联查找，在堆栈中找到相应的元素，然后把该元素的上面的所有元素下压一个位置，同时把本次访问的块地址抽出来，从最上面压入栈顶。而该元素下面的所有元素则保持不动。如果Cache访问不命中，则把本次访问的块地址从最上面压入栈顶，堆栈中所有原来的元素都下移一个位置。如果Cache中该组已经没有空闲块，就要替换一个块。这时从栈底被挤出去的块地址就是需要被替换的块的块地址。

堆栈法所需要的硬件需要为每一组都设置一个项数与相联度相同的小堆栈，每一项的位数为log2n位。

硬件堆栈所需的功能相联比较能全部下移、部分下移和从中间取出一项的功能

速度较低，成本较高（只适用于相联度较小的LRU算法）

比较对法基本思路: 让各块两两组合，构成比较对。每一个比较对用一个触发器的状态来表示它所相关的两个块最近一次被访问的远近次序，再经过门电路就可找到LRU块。例如：假设有A、B、C三个块，可以组成3对：AB、AC、BC。每一对中块的访问次序分别用“对触发器”TAB、TAC、TBC表示。 TAB为“1”，表示A比B更近被访问过； TAB为“0”，表示B比A更近被访问过。 TAC、TBC也是按这样的规则定义。显然，当TAC＝1且TBC＝1时，C就是最久没有被访问过了。（A比C更近被访问过、且B比C也是更近被访问过）即：CLRU= TAC·TBC 同理可得：

用触发器和与门实现上述逻辑的电路：

比较对法所需的硬件量

与门有多少个块，就要有多少个与门；每个与门的输入端要连接所有与之相关的触发器。对于一个具有P块的组中的任何一个块来说，由于它可以跟除了它自己以外的所有其他的块两两组合，所以与该块相关的比较对触发器个数为P－1，因而其相应的与门的输入端数是P－1。

触发器所需要的触发器的个数与两两组合的比较对的数目相同。

块数少时，所需要的硬件较少，随着组内块数P的增加，所需的触发器的个数会以平方的关系迅速增加，门的输入端数也线性增加。（硬件实现的成本很高）当组内块数较多时，可以用多级状态位技术减少所需的硬件量。

写策略 “写”操作必须在确认是命中后才可进行 “写”访问有可能导致Cache和主存内容的不一致写策略是区分不同Cache设计方案的一个重要标志

写直达法（也称为存直达法）执行“写”操作时，不仅写入Cache，而且也写入下一级存储器。

写回法（也称为拷回法）执行“写”操作时，只写入Cache。仅当Cache中相应的块被替换时，才写回主存。(设置“修改位”)

两种写策略的比较写回法的优点：速度快，所使用的存储器带宽较低。写直达法的优点：易于实现，一致性好。

采用写直达法时，若在进行“写”操作的过程中CPU必须等待，直到“写”操作结束，则称CPU写停顿。减少写停顿的一种常用的优化技术：采用写缓冲器

“写”操作时的调块按写分配(写时取) 写不命中时，先把所写单元所在的块调入Cache，再行写入。

不按写分配(绕写法) 写不命中时，直接写入下一级存储器而不调块。

写策略与调块写回法── 按写分配写直达法── 不按写分配

Cache的性能分析

不命中率

与硬件速度无关容易产生一些误导

平均访存时间

平均访存时间＝命中时间＋不命中率×不命中开销

程序执行时间 CPU时间＝（CPU执行周期数+存储器停顿周期数）×时钟周期时间其中：

存储器停顿时钟周期数＝“读”的次数×读不命中率×读不命中开销＋“写”的次数×写不命中率×写不命中开销存储器停顿时钟周期数＝访存次数×不命中率×不命中开销

Cache不命中对于一个CPI较小而时钟频率较高的CPU来说，影响是双重的：

CPIexecution越低，固定周期数的Cache不命中开销的相对影响就越大。在计算CPI时，不命中开销的娜梅莉亚单位是时钟周期数。因此，即使两台计算机的存储层次完全相同，时钟频率较高的CPU的不命中开销较大，其CPI中存储器停顿这部分也就较大。

因此Cache对于低CPI、高时钟频率的CPU来说更加重要。

降低Cache不命中率

三种类型的不命中(3C)

强制性不命中(Compulsory miss) 当第一次访问一个块时，该块不在Cache中，需从下一级存储器中调入Cache，这就是强制性不命中。(冷启动不命中，首次访问不命中）

容量不命中(Capacity miss ) 如果程序执行时所需的块不能全部调入Cache中，则当某些块被替换后，若又重新被访问，就会发生不命中。这种不命中称为容量不命中。

冲突不命中(Conflict miss) 在组相联或直接映象Cache中，若太多的块映象到同一组(块)中，则会出现该组中某个块被别的块替换(即使别的组或块有空闲位置)，然后又被重新访问的情况。这就是发生了冲突不命中。(碰撞不命中，干扰不命中)

相联度越高，冲突不命中就越少；强制性不命中和容量不命中不受相联度的影响；强制性不命中不受Cache容量的影响，但容量不命中却随着容量的增加而减少。

减少三种不命中的方法

强制性不命中：增加块大小，预取（本身很少）容量不命中：增加容量（抖动现象）冲突不命中：提高相联度（理想情况：全相联）

许多降低不命中率的方法会增加命中时间或不命中开销增加Cache的容量

最直接的方法是增加Cache的容量缺点: 增加成本可能增加命中时间

这种方法在片外Cache中用得比较多

提高相联度

采用相联度超过8的方案的实际意义不大。 2:1 Cache经验规则容量为N的直接映象Cache的不命中率和容量为N/2的两路组相联Cache的不命中率差不多相同。

提高相联度是以增加命中时间为代价。

伪相联Cache(列相联Cache) 多路组相联的低不命中率和直接映象的命中速度

伪相联Cache的人本主义理论优点

命中时间小不命中率低

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

快速命中与慢速命中要保证绝大多数命中都是快速命中

缺点：多种命中时间硬件预取

指令和数据都可以预取预取内容既可放入Cache，也可放在外缓冲器中。例如：指令流缓冲器

指令预取通常由Cache之外的硬件完成预取效果指令预取(4KB，直接映象Cache，块大小＝16字节) 1个块的指令流缓冲器：捕获15％～25％的不命中 4个块的指令流缓冲器：捕获50％ 16个块的指令流缓冲器：捕获72％

数据预取(4KB,直接映象Cache) 1个数据流缓冲器：捕获25％的不命中还可以采用多个数据流缓冲器

预取应利用存储器的空闲带宽，不能影响对正常不命中的处理，否则可能会降低性能

编译器控制的预取在编译时加入预取指令，在数据被用到之前发出预取请求按照预取数据所放的位置，可把预取分为两种类型：

寄存器预取：把数据取到寄存器中。 Cache预取：只将数据取到Cache中。太极桩功

按照预取的处理方式不同，可把预取分为：

故障性预取：在预取时，若出现虚地址故障或违反保护权限，就会发生异常。非故障性预取：在遇到这种情况时则不会发生异常，因为这时它会放弃预取，转变为空操作。

本节假定Cache预取都是非故障性的，也叫做非绑定预取。在预取数据的同时，处理器应能继续执行。只有这样，预取才有意义。非阻塞Cache (非锁定Cache) 编译器控制预取的目的：使执行指令和读取数据能重叠执行。循环是预取优化的主要对象

不命中开销小时：循环体展开1～2次不命中开销大时：循环体展开许多次

每次预取需要花费一条指令的开销

保证这种开销不超过预取所带来的收益编译器可以通过把重点放在那些可能会导致不命中的访问上，使程序避免不必要的预取，从而较大程度地减少平均访存时间

编译器优化基本思想：通过对软件进行优化来降低不命中率。（特色：无需对硬件做任何改动）程序代码和数据重组可以重新组织程序而不影响程序的正确性

把一个程序中的过程重新排序，就可能会减少冲突不命中，从而降低指令不命中率。把基本块对齐，使得程序的入口点与Cache块的起始位置对齐，就可以减少顺序代码执行时所发生的Cache不命中的可能性。

如果编译器知道一个分支指令很可能会成功转移，那么它就可以通过以下两步来改善空间局部性：

将转移目标处的基本块和紧跟着该分支指令后的基本块进行对调；把该分支指令换为操作语义相反的分支指令。

数据对存储位置的限制更少，更便于调整顺序。编译优化技术包括

数组合并将本来相互独立的多个数组合并成为一个复合数组，以提高访问它们的局部性。

内外循环交换循环融合将若干个独立的循环融合为单个的循环。这些循环访问同样的数组，对相同的数据作不同的运算。这样能使得读入Cache的数据在被替换出去之前，能得到反复的使用。

分块

“牺牲”Cache 一种能减少冲突不命中次数而又不影响时钟频率的方法。基本思想：在Cache和它从下一级存储器调数据的通路之间设置一个全相联的小Cache，称为“牺牲”Cache（Victim Cache）。用于存放被替换出去的块(称为牺牲者)，以备重用。作用

对于减小冲突不命中很有效，女性角色名特别是对于小容量的直接映象数据Cache，作用尤其明显。减少Cache不命中开销

采用两级Cache

第一级Cache(L1)小而快第二级Cache(L2)容量大

性能分析

平均访存时间＝命中时间L1＋不命中率L1×不命中开销L1 不命中开销L1＝命中时间L2＋不命中率L2×不命中开销L2 平均访存时间＝命中时间L1＋不命中率L1×（命中时间L2＋不命中率L2×不命中开销L2）

局部不命中率与全局不命中率

局部不命中率＝该级Cache的不命中次数/到达该级Cache的访问次数全局不命中率＝该级Cache的不命中次数/CPU发出的访存的总次数

全局不命中率L2＝不命中率L1×不命中率L2 评价第二级Cache时，应使用全局不命中率这个指标。它指出了在CPU发出的访存中，究竟有多大比例是穿过各级Cache，最终到达存储器的。采用两级Cache时，每条指令的平均访存停顿时间：

每条指令的平均访存停顿时间＝每条指令的平均不命中次数L1×命中时间L2＋每条指令的平均不命中次数L2×不命中开销L2

对于第二级Cache，我们有以下结论：

在第二级Cache比第一级Cache大得多的情况下，两级Cache的全局不命中率和容量与第二级Cache相同的单级Cache的不命中率非常接近。局部不命中率不是衡量第二级Cache的一个好指标，因此，在评价第二级Cache时，应用全局不命中率这个指标。

第二级Cache不会影响CPU的时钟频率，因此其设计有更大的考虑空间

它能否降低CPI中的平均访存时间部分？它的成本是多少

第二级Cache的参数

容量第二级Cache的容量一般比第一级的大许多。大容量意味着第二级Cache可能实际上没有容量不命中，只剩下一些强制性不命中和冲突不命中。

相联度第二级Cache可采用较高的相联度或伪相联方法。

块大小

第二级Cache可采用较大的块如64、128、256字节

为减少平均访存时间，可以让容量较小的第一级Cache采用较小的块，而让容量较大的第二级Cache采用较大的块。多级包容性需要考虑的另一个问题：第一级Cache中的数据是否总是同时存在于第二级Cache中。

让读不命中优先于写

Cache中的写缓冲器导致对存储器访问的复杂化在读不命中时，所读单元的最新值有可能还在写缓冲器中，尚未写入主存。

解决问题的方法(读不命中的处理) 推迟对读不命中的处理（缺点：读不命中的开销增加）检查写缓冲器中的内容

在写回法Cache中，也可采用写缓冲器

写缓冲合并

提高写缓冲器的效率写直达Cache 依靠写缓冲来减少对下一级存储器写操作的时间。如果写缓冲器为空，就把数据和相应地址写入该缓冲器。从CPU的角度来看，该写操作就算是完成了。

如果写缓冲器中已经有了待写入的数据，就要把这次的写入地址与写缓冲器中已有的所有地址进行比较，看是否有匹配的项。如果有地址匹配而对应的位置又是空闲的，就把这次要写入的数据与该项合并。这就叫写缓冲合并。如果写缓冲器满且又没有能进行写合并的项，就必须等待。

提高了写缓冲器的空间利用率，而且还能减少因写缓冲器满而要进行的等待时间。

请求字处理技术从下一级存储器调入Cache的块中，只有一个字是立即需要的。这个字称为请求字应尽早把请求字发送给CPU

尽早重启动：调块时，从块的起始位置开始读起。一旦请求字到达，就立即发送给CPU，让CPU继续执行。请求字优先：调块时，从请求字所在的位置读起。这样，第一个读出的字便是请求字。将之立即发送给CPU。

这种技术在以下情况下效果不大：

Cache块较小下一条指令正好访问同一Cache块的另一部分

非阻塞Cache技术非阻塞Cache：Cache不命中时仍允许CPU进行其它的命中访问。即允许“不命中下命中” 进一步提高性能：

“多重不命中下命中” “不命中下不命中”（存储器必须能够处理多个不命中）

可以同时处理的不命中次数越多，所能带来的性能上的提高就越大。

减少命中时间

命中时间直接影响到处理器的时钟频率。在当今的许多计算机中，往往是Cache的访问时间限制了处理器的时钟频率。容量小、结构简单的Cache 硬件越简单，速度就越快；应使Cache足够小，以便可以与CPU一起放在同一块芯片上某些设计采用了一种折衷方案：把Cache的标识放在片内，而把Cache的数据存储器放在片外。虚拟Cache 物理Cache

使用物理地址进行访问的传统Cache。标识存储器中存放的是物理地址，进行地址检测也是用物理地址。缺点：地址转换和访问Cache串行进行，访问速度很慢。

虚拟Cache 可以直接用虚拟地址进行访问的Cache。标识存储器中存放的是虚拟地址，进行地址检测用的也是虚拟地址。优点：在命中时不需要地址转换，省去了地址转换的时间。即使不命中，地址转换和访问Cache也是并行进行的，其速度比物理Cache快很多。

虚拟索引＋物理标识优点：兼得虚拟Cache和物理Cache的好处局限性：Cache容量受到限制 (页内位移) Cache容量≤页大小×相联度

Cache容量＝16×4KB＝64KB 另一种方法：硬件散列变换 Cache访问流水化对第一级Cache的访问按流水方式组织访问Cache需要多个时钟周期才可以完成例如

Pentium访问指令Cache需要一个时钟周期 Pentium Pro到Pentium Ⅲ需要两个时钟周期 Pentium 4 则需要4个时钟周期

踪迹Cache 开发指令级并行性所遇到的一个挑战是：当要每个时钟周期流出超过4条指令时，要提供足够多条彼此互不相关的指令是很困难的

一个解决方法：采用踪迹Cache 存放CPU所执行的动态指令序列包含了由分支预测展开的指令，该分支预测是否正确需要在取到该指令时进行确认。

优缺点

地址映象机制复杂，相同的指令序列有可能被当作条件分支的不同选择而重复存放, 能够提高指令Cache的空间利用率。 Cache优化技术总结

虚拟存储器

虚拟存储器的基本原理虚拟存储器是“主存—辅存”层次进一步发展的结果。虚拟存储器可以分为两类：页式和段式

页式虚拟存储器把空间划分为大小相同的块。(页面) 段式虚拟存储器则把空间划分为可变长的块。(段) 页面是对空间的机械划分，而段则往往是按程序的逻辑意义进行划分。

快速地址转换技术地址变换缓冲器TLB TLB是一个专用的高速缓冲器，用于存放近期经常使用的页表项； TLB中的内容是页表部分内容的一个副本； TLB也利用了局部性原理。 TLB中的项由两部分构成：标识和数据标识中存放的是虚地址的一部分。数据部分中存放的则是物理页帧号、有效位、存储保护信息、使用位、修改位等。

五、输入输出系统

I/O系统的性能

输入/输出系统简称I/O系统它包括：

I/O设备 I/O设备与处理机的连接

I/O系统的性能对CPU的性能有很大的影响，若两者的性能不匹配，I/O系统就有可能成为整个系统的瓶颈。系统的响应时间(衡量计算机系统的一个更好的指标)

从用户输入命令开始，到得到结果所花费的时间。由两部分构成： I/O系统的响应时间 CPU的处理时间

多进程技术只能够提高系统吞吐率，并不能够减少系统响应时间。评价I/O系统性能的参数主要有：

连接特性（哪些I/O设备可以和计算机系统相连接） I/O系统的容量（I/O系统可以容纳的I/O设备数）响应时间和吞吐率等

另一种衡量I/O系统性能的方法：考虑I/O操作对CPU的打扰情况。即考查某个进程在执行时，由于其他进程的I/O操作，使得该进程的执行时间增加了多少。

I/O系统的可靠性、可用性和可信性

反映外设可靠性能的参数有：

可靠性（Reliability）可用性（Availability）可信性（Dependability）

系统的可靠性：系统从某个初始参考点开始一直连续提供服务的能力。

用平均无故障时间MTTF来衡量。系统中断服务的时间用平均修复时间MTTR来衡量。 MTTF的倒数就是系统的失效率。如果系统中每个模块的生存期服从指数分布，则系统整体的失效率是各部件的失效率之和。

系统的可用性：系统正常工作的时间在连续两次正常服务间隔时间中所占的比率。 $$可用性 = \frac{MTTF}{MTTF+MTTR}$$ MTTF+MTTR：平均失效间隔时间MTBF（Mean Time Between Failure）系统的可信性：服务的质量。即在多大程度上可以合理地认为服务是可靠的。（不可以度量）

廉价磁盘冗余阵列RAID

磁盘阵列DA（Disk Array）：使用多个磁盘（包括驱动器）的组合来代替一个大容量的磁盘。

多个磁盘并行工作。以条带为单位把数据均匀地分布到多个磁盘上。（交叉存放）条带存放可以使多个数据读/写请求并行地被处理，从而提高总的I/O性能。

这里并行性有两方面的含义：

多个独立的请求可以由多个盘来并行地处理。减少了I/O请求的排队等待时间如果一个请求访问多个块，就可以由多个盘合作来并无机玻璃钢行处理。提高了单个请求的数据传输率

大多数磁盘阵列的组成可以由以下两个特征来区分：

数据交叉存放的粒度（可以是细粒度的，也可以是粗粒度的）细粒度磁盘阵列是在概念上把数据分割成相对较小的单位交叉存放。成都三圣乡优点：所有I/O请求都能够获得很高的数据传输率。缺点：在任何时间，都只有一个逻辑上的I/O在处理当中，而且所有的磁盘都会因为为每个请求进刘跨越行定位而浪费时间。

粗粒度磁盘阵列是把数据以相对较大的单位交叉存放。多个较小规模的请求可以同时得到处理。对于较大规模的请求又能获得较高的传输率。

冗余数据的计算方法以及在磁盘阵列中的存放方式

如何计算冗余信息?

大多都是采用奇偶校验码；也有采用汉明码（Hamming code）或Reed-Solomon码的。

如何把冗余信息分布到磁盘阵列中的各个盘?

把冗余信息集中存放在少数的几个盘中。把冗余信息均匀地存放到所有的盘中。（能避免出现热点问题）

有关RAID的几个问题

关键问题：如何发现磁盘的故障在磁盘扇区中除了保存数据信息外，还保存有用于发现该扇区错误的检测信息。

设计的另一个问题如何减少平均修复时间MTTR 典型的做法：在系统中增加热备份盘

热交换技术与热备份盘相关的一种技术

RAID0 非冗余磁盘阵列，无冗余信息。严格地说，它不属于RAID系列。把数据切分成条带，以条带为单位交叉地分布存放到多个磁盘中。

RAID1 镜像磁盘，对所有的磁盘数据提供一份冗余的备份。每当把数据写入磁盘时，将该数据也写入其镜像盘。在系统中所有的数据都有两份。

能实现快速的读取操作。对于写入操作，镜像的两个磁盘都要写入。但可并行进行，而且不需要计算校验信息，所以其速度比级别更高的RAID都快。可靠性很高，数据的恢复很简单。实现成本最高。

RAID2 存储器式的磁盘阵列（按汉明纠错码的思路构建）含4个数据盘的RAID2

每个数据盘存放所有数据字的一位（位交叉存放）各个数据盘上的相应位计算汉明校验码，编码位被存放在多个校验（ECC）磁盘的对应位上。冗余盘是用来存放汉明码的，其个数为log2m级。m：数据盘的个数（也就是数据字的位数）并未被广泛应用，目前还没有商业化产品。

RAID3 位交叉奇偶校验磁盘阵列

采用奇偶校验写数据时：为每行数据形成奇偶校验位并写入校验盘读出数据时：如果控制器发现某个磁盘出故障，就可以根据故障盘以外的所有其他盘中的正确信息恢复故障盘中的数据。（通过异或运算实现）

细粒度的磁盘阵列，即采用的条带宽度较小。（可以是1个字节或1位）能够获得很高的数据传输率，这种磁盘阵列对大数据量的读写具有很大的优越性。不能同时进行多个I/O请求的处理。

只需要一个校验盘，校验空间开销比较小。

RAID4

块交叉奇偶校验磁盘阵列采用比较大的条带，以块为单位进行交叉存放和计算奇偶校验。实现目标：能同时处理多个小规模访问请求

读取操作每次只需访问数据所在的磁盘。仅在该磁盘出现故障时，才会去读校验盘，并进行数据的重建。

写入操作假定:有4个数据盘和一个冗余盘。写数据需要2次磁盘读和2次磁盘写操作。

RAID4能有效地处理小规模访问，快速处理大规模访问，校验空间开销比较小。但其控制比较复杂。 RAID5 块交叉分布奇偶校验磁盘阵列数据以块交叉的方式存于各盘，无专用冗余盘，奇偶校验信息均匀分布在所有磁盘上。

RAID6 P＋有角鳄Q双校验磁盘阵列

校验空间开销是RAID5的两倍容忍两个磁盘出错

RAID10与RAID01 RAID10又称为RAID1+0 先进行镜像（RAID1），再进行条带存放（RAID0）

RAID01又称为RAID0+1 先进行条带存放（RAID0），再进行镜像（RAID1）

RAID的实现与发展

实现盘阵列的方式主要有三种：

软件方式：阵列管理软件由主机来实现。优点：成本低缺点：过多地占用主机时间，且带宽指标上不去。

阵列卡方式：把RAID管理软件固化在I/O控制卡上，从而可不占用主机时间，一般用于工作站和PC机。子系统方式：一种基于通用接口总线的开放式平台，可用于各种主机平台和网络系统。

六、互连网络互连网络是一种由开关元件按照一定的拓扑结构和控制方式构成的网络，用来实现计算机系统中结点之间的相互连接。

结点：处理器、存储模块或其它设备。在拓扑上，互连网络为输入结点到输出结点之间的一组互连或映象。 SIMD计算机和MIMD计算机的关键组成部分。 3大要素：互连结构，开关元件，控制方式。互连函数

变量x：输入（设x=0，1，…，N－1）函数f(x)：输出通过数学表达式建立输入端号与输出端号的连接关系。即在互连函数f的作用下，输入端x连接到输出端f(x)。互连函数反映了网络输入数组和输出数组之间对应的置换关系或排列关系。（有时也称为置换函数或排列函数）互连函数f(x)有时可以采用循环表示即：（x0x1x2…xj-1）表示：f(x0)=x1，f(x1)=x2，…，f(xj-1)=x0 j称为该循环的长度。设n=log2N，则可以用n位二进制来表示N个输入端和输出端的二进制地址，互连函数表示为： f（xn-1xn-2…x1x0）

几种基本的互连函数

恒等函数恒等函数：实现同号输入端和输出端之间的连接。

交换函数交换函数：实现二进制地址编码中第k位互反的输入端与输出端之间的连接。

主要用于构造立方体互连网络和各种超立方体互连网络。它共有n＝log2N种互连函数。（N为结点个数）当N＝8时，n＝3，可得到常用的立方体互连函数：

均匀洗牌函数均匀洗牌函数：将输入端分成数目相等的两半，前一半和后一半按类似均匀混洗扑克牌的方式交叉地连接到输出端（输出端相当于混洗的结果）。也称为混洗函数（置换）

即把输入端的二进制编号循环左移一位。互连函数（设为s）的第k个子函数：把s作用于输入端的二进制编号的低k位。互连函数（设为s）的第k个超函数：把s作用于输入端的二进制编号的高k位。

逆均匀洗牌函数：将输入端的二进制编号循环右移一位而得到所连接的输出端编号。

碟式函数蝶式互连函数：把输入端的二进制编号的最高位与最低位互换位置，便得到了输出端的编号。

蝶式变换与交换变换的多级组合可作为构成方体多级网络的基础

反位序函数反位序函数：将输入端二进制编号的位序颠倒过来求得相应输出端的编号。

移数函数移数函数：将各输入端都错开一定的位置（模N）后连到输出端。

PM2I函数 P和M分别表示加和减，2I表示2^i。该函数又称为“加减2^i”函数。 PM2I函数：一种移数函数，将各输入端都错开一定的位置（模N）后连到输出端。

PM2I互连网络共有2n个互连函数。

互连网络的结构参数与性能指标

网络通常是用有向边或无向边连接有限个结点的图来表示。结构参数互连网络的主要特性参数有：

网络规模N：网络中结点的个数。表示该网络所能连接的部件的数量。

结点度d：与结点相连接的边数（通道数），包括入度和出度。进入结点的边数叫入度。从结点出来的边数叫出度。

结点距离：对于网络中的任意两个结点，从一个结点出发到另一个结点终止所需要跨越的边数的最小值。网络直径D：网络中任意两个结点之间距离的最大值。网络直径应当尽可能地小。

等分宽度b：把由N个结点构成的网络切成结点数相同（N/2）的两半，在各种切法中，沿切口边数的最小值。线等分宽度：B＝b×w 其中：w为通道宽度（用位表示）该参数主要反映了网络最大流量。

对称性：从任何结点看到的拓扑结构都是相同的网络称为对称网络。对称网络比较容易实现，编程也比较容易。

互连网络的性能指标评估互连网络性能的两个基本指标：时延和带宽通信时延指从源结点到目的结点传送一条消息所需的总时间，它由以下4部分构成：

软件开销：在源结点和目的结点用于收发消息的软件所需的执行时间。主要取决于两端端结点处理消息的软件内核。

通道时延：通过通道传送消息所花的时间。通路时延= 消息长度/通道带宽通常由瓶颈链路的通道带宽决定。

选路时延：消息在传送路径上所需的一系列选路决策所需的时间开销。与传送路径上的结点数成正比。

竞争时延：多个消息同时在网络中传送时，会发生争用网络资源的冲突。为避免或解决争用冲突所需的时间就是竞争时延。很难预测，它取决于网络的传输状态。

网络时延通道时延与选路时延的和。

它是由网络硬件特征决定的，与程序行为和网络传输状态无关。

端口带宽对于互连网络中的任意一个端口来说，其端口带宽是指单位时间内从该端口传送到其他端口的最大信息量。

在对称网络中，端口带宽与端口位置无关。网络的端口带宽与各端口的端口带宽相同。非对称网络的端口带宽则是指所有端口带宽的最小值。

聚集带宽网络从一半结点到另一半结点，单位时间内能够传送的最大信息量。等分带宽与等分宽度对应的切平面中，所有边合起来单位时间所能传送的最大信息量。

静态互连网络

各结点之间有固定的连接通路、且在运行中不能改变的网络。线性阵列一种一维的线性网络，其中N个结点用N-1个链路连成一行。

端结点的度：1 其余结点的度：2 直径：N－1 等分宽度b=1

环和带弦环环：用一条附加链路将线性阵列的两个端点连接起来而构成。可以单向工作，也可以双向工作。

对称结点的度：2 双向环的直径：N/2 单向环的直径：N 环的等分宽度b=2

带弦环增加的链路愈多，结点度愈高，网络直径就愈小。

全连接网络

结点度：15 直径最短，为1。

循环移数网络通过在环上每个结点到所有与其距离为2的整数幂的结点之间都增加一条附加链而构成。

N=16 结点度：7 直径：2

树形和星形一棵5层31个结点的二叉树

星形

胖树形

网格形和环网形网格形

环网形

超立方体

带环立方体（简称3-CCC）

k元n-立方体网络

动态互连网络

由交换开关构成、可按运行程序的要求动态地改变连接状态的网络。总线网络由一组导线和插座构成，经常被用来实现计算机系统中处理机模块、存储模块和外围设备等之间的互连。

每一次总线只能用于一个源（主部件）到一个或多个目的（从部件）之间的数据传送。多个功能模块之间的争用总线或时分总线特点结构简单、实现成本低、带宽较窄

系统总线在处理机、I/O子系统、主存储器以及辅助存储设备（磁盘、磁带机等）之间提供了一条公用通路。系统总线通常设置在印刷电路板底板上。处理器板、存储器板和设备接口板都通过插座或电缆插入底板。

解决总线带宽较窄问题：采用多总线或多层次的总线

多总线是设置多条总线有两种做法：为不同的功能设置专门的总线重复设置相同功能的总线

多层次的总线是按层次的架构设置速度不同的总线，使得不同速度的模块有比较适合的总线连接。

交叉开关网络单级开关网络

交叉点开关能在对偶（源、目的）之间形成动态连接，同时实现多个对偶之间的无阻塞连接。带宽和互连特性最好。一个n×n的交叉开关网络，可以无阻塞地实现n!种置换。对一个n×n的交叉开关网络来说，需要n2套交叉点开关以及大量的连线。当n很大时，交叉开关网络所需要的硬件数量非常巨大。

C.mmp多处理机的互连结构

用16×16的交叉开关网络把16台PDP-11处理机与16个存储模块连在一起最多可同时实现16台处理机对16个不同存储模块的并行访问每个存储模块一次只能满足一台处理机的请求当多个请求要同时访问同一存储模块时，交叉开关就必须分解所发生的冲突，每一列只能接通一个交叉点开关。为了支持并行（或交叉）存储器访问，可以在同一行中接通几个交叉点开关。

多级互连网络多级互连网络的构成

MIMD和SIMD计算机都采用多级互连网络MIN（Multistage Interconnection Network）一种通用的多级互连网络由a×b开关模块和级间连接构成的通用多级互连网络结构每一级都用了多个a×b开关 a个输入和b个输出在理论上，a和b不一定相等，然而实际上a和b经常选为2的整数幂，即a＝b＝2^k，k≥1。

相邻各级开关之间都有固定的级间连接

各种多级互连网络的区别在于所用开关模块、控制方式和级间互连模式的不同。

控制方式：对各个开关模块进行控制的方式。级控制：每一级的所有开关只用一个控制信号控制，只能同时处于同一种状态。单元控制：每一个开关都有一个独立的控制信号，可各自处于不同的状态。部分级控制：第i级的所有开关分别用i＋1个信号控制，0≤i≤n－1，n为级数。

常用的级间互连模式：均匀洗牌、蝶式、多路洗牌、纵横交叉、立方体连接等多级立方体网络多级立方体网络包括STARAN网络和间接二进制n方体网络等。

STARgif动画AN网络采用级控制和部分级控制。采用级控制时，所实现的是交换功能；采用部分级控制时，则能实现移数功能。

间接二进制n方体网络则采用单元控制。具有更大的灵活性。

交换将有序的一组元素头尾对称地进行交换。

3级STARAN网络在各种级控制信号的情况下所实现的入出端连接以及所实现的交换函数和功能。其中：

K2k1k0：控制信号，ki（i=0，1，2）为第i级的级控制信号。从表中可以看出下面的4行中每一行所实现的功能可以从级控制信号为其反码的一行中所实现的功能加上1组8元变换来获得。

Omega网络一个8×8的Omega网络

每级由4个4功能的2×2开关构成级间互连采用均匀洗牌连接方式

一个N输入的Omega网络

有log2N级，每级用N/2个2×2开关模块，共需要Nlog2N/2个开关。每个开关模块均采用单元控制方式。不同的开关状态组合可实现各种置换、广播或从输入到输出的其它连接。

N=8的多级立方体互连网络的另一种画法

动态互联网络比较

七、多处理机

并行处理面临的挑战

并行处理面临着两个重要的挑战

程序中的并行性有限相对较大的通信开销

有限的并行性使计算机要达到很高的加速比十分困难。

多处理机中远程访问的延迟较大

在现有的机器中，处理器之间的数据通信大约需要50～1000个时钟周期。主要取决于：通信机制、互连网络的种类和机器的规模

在几种不同的共享存储器并行计算机中远程访问一个字的典型延迟

问题的解决

并行性不足：采用并行性更好的算法远程访问延迟的降低：靠系统结构支持和编程技术

在并行处理中，影响性能（负载平衡、同步和存储器访问延迟等）的关键因素常依赖于：

应用程序的高层特性如数据的分配，并行算法的结构以及在空间和时间上对数据的访问模式等。

依据应用特点可把多机工作负载大致分成两类：

单个程序在多处理机上的并行工作负载多个程序在多处理机上的并行工作负载

并行程序的计算／通信比率反映并行程序性能的一个重要的度量：计算与通信的比率

计算／通信比率随着处理数据规模的增大而增加；随着处理器数目的增加而减少。

本文发布于:2023-06-02 13:36:23，感谢您对本站的认可！

本文链接：http://www.ranqi119.com/ge/85/191609.html

上一篇：2023年初中生怀孕了该怎么办(优质4篇)

下一篇：笔记本i5处理器够用吗

标签：计算机系统结构

留言与评论（共有 0 条评论）