封面

---

简介：本课程缺少8259、8253、8255等芯片的讲述，建议b站搜索车向泉微机原理（最后几p）自行观看
  

---

一、高速缓冲存储器

1. 原理

系统全由硬件实现，比主存访问速度快很多

1.1 理论依据

时间局部性：某位置若被访问，则近期内很可能又被访问
空间局部性：某位置若被访问，则临近的位置也可能被访问

1.2 构成

小容量高速存储器、相联存储器构成的存储表、替换管理模块

1.3 工作过程

cpu访问主存时，先访问相联存储表，若发现要访问的信息就在cache中（命中），通过存储表将地址转换为cache地址，从cache中读出信息。若未命中，则cpu从主存中读取信息，同时将该信息替换cache中的某一块（为提高效率，通常将cache和主存分成容量相等的块）

2. 映射方式

1.1 全相联映射

主存

主存分块
主存地址为主存块号+块内地址
主存的任何一块可装入cache的任何一块中

相联存储器

相联存储器有和cache块数相同的单元（相联存储器的单元地址和cache块号一一对应）
相联存储器中每个单元存储主存的某个块号

cache

cpu访问时，查询存储器，如果要访问的块号就在存储器的某个单元中（命中），cache地址=单元地址+块内地址，用该地址访问cache

优点

灵活性（主存任意块都可装入cache任意块，全部装满后才需要替换）

缺点

要求相联存储器容量最大
地址变换机构最复杂（比较检索式需要全部检索相联存储器才能获得cache块号）

1.2 直接映射：

主存

将主存按照每区为cache的容量分区，并在每个区内分块。主存中块号相同的块只能装入cache中相同块号的块。
（如：主存第一区0号块和第二区0号块只能装入cache中第0块）
主存地址为主存区号+块号+块内地址

相联存储器

相联存储器有和cache块数相同的单元
相联存储器每个单元存储主存区号

cache

cpu访问时，查询存储器，比较地址为要访问的块号的单元，若该单元存储的区号和要访问的主存区号相同，则命中cache地址=要访问的块号+块内地址

优点

地址变换简单（只需要以主存地址的块号访问存储器）

缺点

效率低（不允许不同区的相同块号同时出现，可能会出现频繁替换的情况，所以更适合用于大容量cache）

1.3 组相联映射：

组相联映射是组间直接映射而组内块全相联映射，结合了直接映射和全相联映射

主存

主存先按cache容量分区，区内分组，组内分块
主存地址为主存区号+组号+块号+块内地址

相联存储器

相联存储器和cache一样分组分块
相联存储器存储主存区号+块号

cache

cache和主存一样分组分块
cpu访问时，在存储器中对应组查询，若能在该组中找到某个单元存储的信息和要访问区号+块号相同，则命中，cache地址=组号+单元地址+块内地址

3. 替换算法

1. 随机替换RAND：随机函数发生器产生需要替换的块号，命中率低
2. 先进先出算法FIFO：将最先装入cache的块替换，命中率低
3. 近期最少使用算法LRU：将近期最少使用的块替换。对每块设置一个计数器，某块命中时，将该块计数器清零，其它块计数器加一，替换时将计数值最大的块替换。命中率更高
4. 最不经常使用算法LFU：将一段时间里访问次数最少的块替换。对每块设置一个计数器，某块命中时，该块计数器加一。需要替换时将计数值最小的块替换，并将所有块计数器清零
5. 最优替换算法OTP：将最长时间不会被访问的块替换。该算法要求已知访问的顺序，替换时在访问序列中查找最长时间会被访问的块，将其替换。该算法不可实现，可用于衡量其他算法

4. 主存cache一致性

cache内容是主存的复制，所以cache要和主存内容保持一致，采用方法有:

1. 全写法：
   当cpu写cache命中时，数据写入cache时的同时写入主存。未命中时，直接对主存修改，而后将主存内容调入cache。速度慢
2. 写回法：
   cpu写cache命中时，只将数据写入cache，只有当cache中被修改过的块替换出去时才写回主存。未命中时，将相应主存块直接调入cache，然后对cache修改。速度快，但存在替换前不一致问题

5. 性能

1. 命中率H：
   H=命中次数/访问总次数
2. 理论命中率：
   H=1-S^-0.5^
   S为cache容量
3. 平均访问周期T：
   T=H * Tc+(1-H) * (Tc+Tx)
   Tc为cache访问周期
   Tm为主存访问周期
   Tx=n * Tm，n代表cache以n个字（节）为一块
4. 加速比Sp：Sp=Tm/T
5. 存储器平均价格C：
   C=(C1 * S1+C2 * S2)/(S1+S2)
   S1，S2为主存与cache容量
   C1，C2为主存与cache单位价格
6. 总失效率：
   总失效率=一级cache失效率 * 二级cache失效率
   失效率即为未命中率

二、流水线

1. 基本概念

流水线技术是将重复的处理过程分解为若干子过程，且每个子过程可以与其它子过程同时执行

1. 每个子过程需要的时间应尽可能相等
2. 每个子过程称为流水线的级/段
3. 级的数量为流水线深度
4. 第一个任务从进入到流出的时间叫做通过时间，在此之后每个时钟周期（拍）就流出一个结果
5. 流水线适合于大量重复过程

时空图：用于描述流水线的图，横坐标代表时间，纵坐标为事件/指令/任务

2. 分类

2.1 按使用级别（系统层次）分

1. 系统级流水线/宏流水线：
   由多个处理机组成流水线，每个处理机完成任务的一部分
2. 处理机级流水线：
   由多个部件组成流水线，流水线位于处理机内部
3. 部件级流水线：
   由多个微程序控制单元组成，流水线位于部件内部

2.2 按功能数

1. 单功能流水线：只含一种功能
2. 多功能流水线

2.3 按功能连接

1. 静态流水线：流水线同一时间内只能按同一种功能的连接方式工作。如流水线有A、B两功能，同一时间要么按AB这样的方式工作，要么按BA方式工作
2. 动态流水线：同一时间可以实现多种功能的连接。效率更高、实现麻烦（需要硬件能够识别当前在完成哪一种连接方式）

2.4 按反馈功能

1. 线性流水线：没有反馈回路
2. 非线性流水线：有反馈回路，可以根据反馈来决定下一步进行哪个功能

2.5 按出入顺序

1. 顺序流水线：任务输入顺序和流出顺序相同
2. 乱序流水线

3. 流水线存在问题—相关

相关：相邻任务因存在某种制约、依赖、影响，使任务之间有了某种关联，其以影响了流水线性能，甚至影响流水线正常工作

3.1 结构相关

结构相关指资源冲突，无法满足同时重叠执行两个任务，如取指令和取数据，都要访问主存。

解决方法

1. 增加资源副本：如设计数据存储器和指令存储器
2. 延迟/暂停流水线：插入流水线气泡（气泡只占用资源但没有实际操作
3. 改变资源：改变资源使它们能并发使用

3.2 数据相关

数据相关指某任务需要用到另一个任务的结果，因而不能重叠执行

分类：

1. 先写后读相关：要求写完之后读，如果在写还在执行的时候读就会出现错误
2. 先读后写相关：要求读完之后写，如果在读之前写了就会出现错误
3. 先写后写相关：要求第一个写比第二个写先执行，如果第二个写先执行就会出现错误

解决方法

1. 直通技术（定向技术）：在流水线之间设置直接连接通路，把相关的任务的前一个任务的结果直接送给后一个任务，后一个任务就无需从资源里读数据，没有冲突
2. 增加专用硬件：
   使用互锁硬件，互锁硬件检测是否有数据相关，如果有就使流水线停顿，直到相关消失
3. 利用编译器（流水线调度）：编译器对指令重新排序或插入空指令

3.3 控制相关

控制相关/全局性相关是指存在分支转移等指令，会打乱流水线指令顺序

解决方法

1. 冻结流水线：当检测到分支指令，就在转移前保存或删除紧随分支指令之后的指令，确定出新的PC值后，再填充流水线
2. 预取分支目标：当条件分支指令被识别时，分支目标被预取，保存到分支指令被执行，如果分支跳转，已取到的指令可立即执行
3. 多流：在条件分支的两路上同时取指令，并将指令保存到分支指令被执行的时候，分支指令执行时，真的执行通路即刻可以获得
4. 循环缓冲器：保存最近获取的n条顺序的指令，分支发生时，先检查分支目标是否在缓冲其中
5. 分支预测：
   1. 静态分支预测：
      1. 预测分支不会发生：在知道分支结果之前，流水线流动分支指令和紧随其后指令，如果分支预测失败，流水线正常执行，如果预测成功，用空操作代替已经取得的指令，并到目标地址重新取指令。如果程序中大多数条件是用于出错检测，那么这种机制合理，因为出错的概率是小的
      2. 预测分支总是发生：一旦分支转移成功，从目标地址取指令。如果程序包含较多循环，那么这种机制有利。
      3. 由编译器预测：编译器预测条件转移，认为会转移时将指令某位置1，硬件遇到这样的指令就按照指示采取行动
   2. 动态分支预测：见书p201 文字表述过于麻烦
6. 延迟分支：将跳转指令前的某些指令放到延迟槽，判断条件跳转后，将延迟槽执行完后在执行跳转
   限制条件：被移动指令和移动过程中经过的指令不相关且被移动指令不破坏条件

4. 性能

4.1 CPI

每条指令所需要的平均时钟周期
带相关的CPI：
=理想CPI+相关造成的停顿周期数/指令数
=理想CPI+相关造成的停顿周期数 * 相关指令频度

4.2 吞吐率TP

单位时间内流水线完成的任务数
根据时空图计算，可以将时空图分为第一个任务完成前和完成后，完成后每个时间周期就完成一个任务

4.3 最大吞吐率TPmax

流水线在达到稳定状态时的吞吐率

1. 若各段时间相等：假设每段时钟周期为t，则TPmax=1/t
2. 各段时间不等：TPmax=1/max{ti}

提高最大吞吐率的方法：

1. 细分瓶颈（耗时最长的段）：将瓶颈再细分为若干个小段
2. 重复：增加一个和瓶颈一样的段，使它们并行工作

4.4 加速比S

代表比原来性能提升了多少
S=不采用流水线完成任务时间/采用流水线完成任务时间
S=流水线深度/CPI

4.5 效率E

流水线有工作时空的占比
E=任务覆盖的面积/任务开始到结束时空图的总面积

E与S关系 E=S/m，m为流水线段数

5. 提高流水线性能

5.1 提高指令级并行

指令级并行是指当指令不相关时，它们能在流水线中重叠执行

5.1.1 乱序执行

乱序执行是指跳过存在相关的指令去执行不相关的指令，使顺序被打乱但结果不变。乱序执行会导致中断不准确

5.1.2 寄存器重命名

对寄存器重命名，有效减少先写后读，先写后写相关

5.1.3 推测执行

在不知道是否需要执行前就执行代码的技术，核心思想是允许指令乱序执行，但是要求指令按序提交，并在提交前阻止不可恢复的动作。指令提交之前不会实际更新寄存器，发现预测错误时，处理器撤销推测的动作。该方法能够保证精确的中断和异常

5.2 多指令流出技术

5.2.1 超标量处理机

处理器内有多条流水线，这些流水线能并行处理，流水线数量称为度。处理n条指令的时间等于一条流水线处理n/度条指令时间。相对性能最高

5.2.2 超流水线处理机

普通流水线一个时钟周期只能流出一条指令，而超流水线处理机把一个时钟周期划分为更小的段（划分段数称为度），使一个时钟周期能流出更多条指令（每一段都流出一条指令）。相对性能最低，由于指令启动延时大，条件转移损失大

5.2.3 超标量超流水线处理机

结合二者，相对性能中等

5.2.4 超长指令字处理机

采用并行编译技术（软件实现），将能够并行执行的不相关的多条指令组合在一起，构成一条位数超长的指令

三、输入输出系统

1. 总线

总线：连接在两个以上数字系统元器件的信息通路

1.1 分类

1.1.1 片内总线

芯片内部各功能元件的连接线
典型片内总线：
如AMBA、Wishbone

1.1.2 元件级总线

电路板内各元器件的连接

1.1.3 内总线（系统总线）

电路板的连接。直接影响计算机性能

典型内总线：

1. PC/XT总线：最早的以8088为CPU的系统总线
2. ISA总线：16位，包含24个地址线、16个数据线
3. EISA总线：32位，适用于32位CPU
4. PCI总线：
   并行传输方式
   总线设备工作独立于CPU
   高性能
   即插即用
   支持多主控设备
5. PCIE总线：与PCI相比：
   串行传输方式，每个通道独享带宽
   支持双向传输和数据分通道传输
   点到点互联、交换技术，降低复杂性、开发设计成本，提高了性价比

1.1.4 外总线（通信总线）

计算机与外设或计算机系统之间的连接。

典型外总线：

1. RS-232C：串行外总线，传送距离远，结构简单
2. SCSI总线：
   并行外总线
   面向服务器、磁盘阵列等高端存储器
   传输速率高，提高CPU效率
   支持多任务
   不支持热插拔
3. SAS总线：
   兼容性好
   点对点架构
   全双工设计
   支持热插拔
4. ATA总线：
   并行总线
   通常用于PC硬盘、光盘等外设接口
5. SATA总线：
   串行总线，对ATA的改进
6. 通用串行总线USB：
   定义四个信号：Vusb(+5V)，GND，D+（信号正端），D-（信号负端），这四个信号用四芯电缆进行传送
   支持即插即用、热插拔
   扩展性好，可靠性高，标准统一
   可通过总线供电
7. IEEE-1394：
   串行总线
   即插即用、热插拔
   支持同步异步传输

1.2 结构

单总线结构
双总线结构
多总线结构

1.3 传送方式

1. 串行传送
2. 并行传送
3. 同步传送：同步总线包括一个公用的时钟，和一个固定的协议，该协议用于通信。同步方式不需要应答，实现方便，但每个设备以相同的频率工作，总线速度由慢设备决定。总线不宜过长
4. 异步传送：异步总线使用握手协议通信。允许总线周期可变

1.4 性能：

位宽： 总线能同时传送的二进制数据的位数，即数据总线的位数
工作频率：以Mhz为单位
带宽（数据传输速率）：单位时间内总线上传输的数据量，总线带宽=总线工作频率×每个时钟周期传送的数据次数×总线位宽/8。单位为MB/s

注意：计算总线传输n位数据需要的时间别忘了额外加上传输地址的时间

1.5 总线仲裁

决定哪个设备可以使用总线

1.5.1 集中式仲裁：

使用集中的仲裁器
串行总线仲裁（链式查询）
并行总线冲裁（独立请求）
计数器查询仲裁（轮询）
见书P268，文字表述过于麻烦

1.5.2 分布式仲裁

不需要集中的冲裁器，每个主设备有自己的仲裁号和仲裁器。
当请求总线时，设备把它们的仲裁号发送到仲裁总线上，每个仲裁器将从仲裁总线上得到其它仲裁号，和自己的仲裁号比较，如果仲裁总线上的号大，则它的请求不予相应。可见仲裁号越大优先级越高

2. 存储器设备

2.1 磁表面存储器

如磁盘和磁带

2.1.1 原理

用磁状态保存二进制信息，记录时将二进制信息变化为电流进而实现磁记录层上磁场的变化。方式有：

1. 归零制RZ：数据0代表负电流脉冲，1代表正电流脉冲，两个数据间电流归零
2. 不归零制NRZ：在数据发生变化时电流改变
3. 见1不归零制NRZ1：遇到数据1时电流改变
4. 调频制FM：写入每个数据都要将电流翻转，且遇到数据1时，电流中心再翻转
5. 改进调频制MFM：写入1时，电流中心翻转，遇到连续两个或以上0，每位电流翻转一次
6. 调相制PM：用电流方向表示0/1，如电流中心从0到1（正方向）代表1

2.1.2 性能

1. 自同步能力R：从磁道中读出的脉冲序列中提取时钟周期的难易程度
   R=最小磁化翻转间隔/最大磁化翻转间隔
2. 编码效率（记录密度）n：
   n=位密度/最大磁化翻转密度
   =1/记录1位二进制编码需磁化方向最大改变次数

2.2硬磁盘存储器

2.2.1 结构

1. 记录面：磁盘中可记录信息的磁介质表面
2. 磁道：记录面上若干个同心闭合圆环
3. 扇区：磁道分为的若干段。第一个扇区为主引导扇区，存储主引导记录和磁盘分区表

2.2.2 数据格式

1. 标志区：每一扇区的开始，包含磁道号+磁头号+扇区号+CRC校验码
2. 数据区：存放数据和校验码
3. 间隙：用于缓冲

2.2.3 性能

1. 道密度：沿磁盘半径方向，单位长度内磁道的数目
2. 位密度：磁道圆周上单位长度存储的二进制位数
3. 存储容量：磁盘能存储的二进制信息总量，有以下两种：
   1. 非格式化容量=位密度×内圈磁道周长×每个记录面上的磁道数×记录面数
   2. 格式化容量=每个扇区的字节数×每道的扇区数×每个记录面上的磁道数×记录面数
4. 寻道时间：磁头从某一位置移动到指定位置所需时间。是个常数，通常为几ms
5. 等待时间：指待读取的扇区转到磁头下方所需时间，一般选用磁盘旋转一周所用时间的一半，通常为几ms
6. 平均存取时间：其等于寻道时间+等待时间
7. 转速：硬盘内驱动电机主轴的旋转速度
8. 数据传输速率：单位时间内读写的字节数。数据传输速率=每个扇区的字节数×每道扇区数×磁盘转速

2.2.4 磁盘阵列RAID技术

一般在SCSI磁盘驱动器上实现。RAID提供了专用服务器中接入多个磁盘时，以磁盘阵列的方式组成一个超大容量、响应速度快、可靠性高的存储子系统。其有六种标准

1. 冗余无校验的磁盘阵列RAID0：至少需要两个硬盘，读写速度最快，但安全性不高
2. 镜像磁盘阵列RAID1：增加镜像磁盘机使得安全性高、可靠性强、快速恢复数据 ，但磁盘冗余，利用率50%
3. 并行海明纠错阵列RAID2：采用海明冗余纠错码，可靠性高、可确定出错硬盘，但磁盘冗余，开销大
4. 奇偶校验并行为交错阵列RAID3
5. …

3. 输入输出技术

输入输出技术实现了外设的输入输出，其要满足数据传输速率尽可能高且不丢失数据
开销尽可能小，充分利用硬件资源

输入输出地址编制方式：

1. 统一编址：外设地址和内存地址统一安排在内存地址空间，即把内存地址分配给外设。用于内存和用于外设的指令一样。优点：可以用访问寄存器指令直接访问IO。缺点：IO占用寄存器空间、指令长度比单独IO指令长，执行时间长
2. 独立编址：外设和内存地址相互独立，各自有自己的寻址空间。用于内存和用于外设的指令不一样

3.1 程序控制方式

多用于慢速的外设

3.1.1无条件传送方式

在需要的时刻让CPU直接与外设进行输入输出操作。实现简单，只需要提供接口和相应的输入输出指令

3.1.2 查询传送方式

利用程序不断询问外部设备的状态，根据它们所处的状态来实现数据的输入和输出。适用于不总是准备好的外设，但降低了CPU效率，无法对突发事件及时响应

3.2 中断方式

提高了CPU效率，能对突发事件及时响应

3.2.1 中断概念

中断源：引起中断的事件
内部中断源：处理机内部的中断事件。如浮点数运算上溢等
外部中断源：外设的中断事件。如外设请求输入输出
中断优先级控制解决的问题：不同优先级中断源同时提出请求，先响应高优先级、CPU正在进行中断服务时，更高优先级的中断提出请求

3.2.2 中断向量表

向量地址=中断向量码（中断类型码）×4（每一个中断占四个字节）
偏移地址IP=向量地址加一内容+向量地址的地址内容
段地址CS=向量地址内容加三+向量地址加二的地址内容

3.2.3 中断过程（以外不可屏蔽中断INTR为例）

1. 中断请求：外部设备产生一个有效的中断请求信号，保持到CPU发现，响应后撤销请求
2. 中断承认：满足以下四个条件，中断请求才会被承认
   1. 一条指令执行结束
   2. CPU处于开启中断状态
   3. 没有复位、保持、非屏蔽中断请求等优先级高于该请求的请求发生
   4. 开中断指令、中断返回指令等特殊指令执行完还需要执行另外的一条指令后才能响应请求
3. 断点保护：
   中断事件处理结束后必须回到被中断的程序，因此必须进行断点保护。一部分为CPU硬件自动保存断点的部分信息，另一部分为程序设计者完成（保护中断要用到的所有寄存器）。通常用压入堆栈的方法实现
4. 中断源识别：两种方式：
   1. 软件查询：利用输入接口将多个中断源的状态读入，逐个查询
   2. 中断向量法：给每个中断源分配一个特定的中断服务程序的入口地址（中断向量）
5. 中断处理：一般根据预先确定的程序实现
6. 断点恢复：恢复程序设计者保护的中断要用到的所有寄存器，通常由弹出堆栈指令完成
7. 中断返回：中断返回是一条IRET指令，命令CPU恢复CPU硬件自动保存断点的部分信息

3.3 DMA方式

无论是查询方式还是中断方式，CPU都需要花费时间执行指令，为提高传输速率引入直接存储器存取DMA方法
DMA原理就是从CPU中获取总线控制权
有三种方式

3.3.1 CPU停止工作方式

DMA发送请求，使CPU放弃总线控制权

3.3.2 周期挪用方式

1. 固定周期挪用：如CPU取指令后需要对指令进行分析，这段（固定）时间不占用系统总线，可分给DMA使用
2. 周期延长：延长CPU机器周期，供给DMA使用。如遇到慢设备时，读写周期就会增加，多余的等待设备时间可以用于DMA

3.3.3 CPU与DMA交替分时工作

将时间分片，一片给CPU使用，一片给DMA使用。由于DMA只是偶尔使用，不是每时每刻进行，所以此方式不如另外两种方式（DMA需要工作时才占用总线）

3.4 通道方式

通道是一个特殊功能的处理器，它有自己的指令和程序专门负责输入输出的传输控制，这样CPU只负责数据处理，通道负责传输控制，二者分时使用内存，实现并行
有三种方式

3.4.1 选择通道

通道可连接多台设备，但设备不能同时工作。数据传送以数据块为单位。会造成长时间等待的问题

3.4.2 数组多路通道

通道可连接多个设备，允许同时工作，但只允许一台设备传输。当某设备进行数据传送时，通道只为该设备服务。当设备需要等待完成某些辅助操作时，通道暂时挂起该设备，去执行其他设备

3.4.3 字节多路通道

连接大量低速外设。允许同时工作，且允许同时传输。以字节为单位，一个设备传送完一个字节，即可为另一个设备传送一个字节

四、多机系统

1. 多机系统思想

多机系统利用并行处理提高计算机性能，它包括两个含义：

1. 同时性（两个或以上事件同一时间发生）
2. 并发性（两个或以上事件在同一时间间隔内发生）

并行处理方法

1. 时间重叠：时间并行技术，使多个子任务同时使用系统中不同功能的部件。如流水线
2. 资源重复：空间并行技术，大量重复设置硬件资源，使多个子任务同时使用系统中相同功能的部件。如多核处理器
3. 时间重复加资源重复：结合时间并行和空间并行。
4. 资源共享：软件方式，通过操作系统调度，使多个任务轮流使用同一设备。如共享存储器

2. 并行计算机分类

2.1 单指令流单数据流SISD

一个时刻只能做一件事情
模式有：

2.1.1 指令级并行

指令按照流水线进行

2.1.2 芯片多线程

CPU可以在多个线程之间切换，是虚拟的多处理器

2.1.3 单片多处理器

同一个芯片设置两个及以上处理器内核，允许同时进行

2.2 单指令流多数据流SIMD

相同的指令以并行的方式应用于不同的数据流，实现数据流的并行
模式有：

2.2.1 向量计算机

采用共享内存结构，所有加法运算由一个高度流水的加法器实现

2.2.2 阵列计算机

由许多在不同数据集上执行同样指令、完成同样功能的完全相同的处理器组成

2.3 多指令流单数据流MISD

多条指令同时在一个数据上进行操作，目前还没有这类的机器

2.4 多指令流多数据流MIMD

实现线程级并行，同时有多个CPU执行不同操作，每个处理器获取自己的指令并对自己的数据进行操作处理
模式有：

2.4.1 集中共享存储器结构（多处理器）

所有处理器共享公共内存，有三种模式：

1. 一致性存储器访问计算机UAM：通过共享总线通信，CPU访问共享内存时间一致
2. 非一致性存储器访问计算机NUAM：共享内存被分组并分布到每个处理器。这使得远程内存访问时间比本地内存长
3. 基于cache的存储器访问计算机：cache可以在不同处理器间移动而非固定

2.4.2 分布式存储器结构（多计算机）

实际上由多个独立计算机组成，不共享内存，每个CPU有自己的私有内存，其它CPU不能访问

3. 多机互联网络

多机互联网络用于连接系统中的计算机，互联网络对多机系统性能而言至关重要

3.1 互联函数

互联函数用于表示互连网络的输入端号和输出端号的关系

3.1.1 表示方式

1. 对应表示法：
   [0 1 … N-1]
   [f(0) f(1) … f(N-1)]
   代表输入N对应输出f(N-1)
2. 函数表示法：
   f(Xn-1Xn-2…X0)=XaXb…Xi
   其中Xn-1Xn-2…X0是输入X序号的二进制表示，根据XaXb…Xi可得到输出Y序号的二进制表示
   代表输入X和输入Y对应
3. 循环表示法：
   (XaXbXc…Xi)
   代表输入Xa对应输出Xb，输入Xb对应输出Xc，…，前一个X和后一个X对应

3.1.2 基本互联函数

1. 恒等置换:r(Xn-1Xn-2…Xi…X0)=Xn-1Xn-2…Xi…X0
2. 交换置换：h(Xn-1Xn-2…Xi…X0)=Xn-1Xn-2…Xi…¬X0
3. 方体置换：Ci(Xn-1Xn-2…Xi…X0)=Xn-1Xn-2…¬Xi…X0
4. 均匀洗牌置换：σ(Xn-1Xn-2…Xi…X0)=Xn-2Xn-3…Xi…X0Xn-1
5. 逆均匀洗牌置换：σ^-1(Xn-1Xn-2…Xi…X0)=X0Xn-1Xn-2…Xi…X1
6. 加减2ⁱ置换：
   PM2_+i(X)=（X+2ⁱ）modM
   PM2_-i(X)=（X-2ⁱ）modM
   其中M时输入/输出设备数
7. 蝶形置换：β(Xn-1Xn-2…Xi…X0)=X0Xn-2…Xi…X1Xn-1

3.2 静态互联网络

1. 线性阵列：每个节点和它左右节点连接
2. 二维网络：每个节点和它上下左右节点连接
3. 树形：每个节点和它父亲以及两个孩子连接
4. n-超立方：每个立方体顶点由n个节点组成
5. 全互联网络：每个节点和其他节点都连接

3.3 动态互联网络

1. 总线：结构简单，但存在总线仲裁、中断处理等问题

2. 交叉开关网络：利用开关阵列，控制不同开关打开关闭，实现任意输入输出端的连接。
   2×2开关模块的四种控制状态：

   1. 直送：0入0出，1入1出
   2. 上播：0入输出0和1，1入输出悬空
   3. 下播：1入输出0和1，0入输出悬空
   4. 交叉：0入1出，1入0出

   具备四种功能的乘坐四功能模块，具备1和4功能的称为二功能模块

3. 多级互联网络：对交叉开关网络的改进，用小规模的交叉开关模块互相串并联构成多级交叉开关网络，减少设备量

4. 多级均匀洗牌网络：又叫omega网络，寻址过程为，0：消息从开关上输出线输出，1消息从开关下输出线输出

4. 多机系统实例

4.1 对称多处理机SMP

有一致性存储访问模型和非一致性存储访问模型两种

4.1.1 特点

1. 由两个及以上相同的处理机构成
2. 多个处理机通过总线或其它互联方式连接
3. 如果是一致性存储访问模型，那么多个处理器共享同一主存储器
4. 所有的处理机通过通道共享IO设备
5. 每个处理机完成相同的功能，在一个集中的操作系统统一管理下工作

4.1.2 优点

1. 对称性
2. 单地址空间，易编程
3. 高速缓存且一致，数据局部性
4. 低通信延迟

4.1.3 问题

1. 欠可靠，总线、存储器或OS失效会使整个系统崩溃
2. 竞争加剧
3. 不可扩放，限制了处理器数量

4.2 大规模并行机MPP

由成百上千个处理器组成的大规模计算机系统，每个节点是独立的计算单元，规模可变，高速互联网络，高带宽低延迟，只有微内核，成本高，用于科学计算

4.3 工作站集群COW

分布式存储，每个节点都是一个完整的计算机，有自己的磁盘和操作系统。普通总线通信
投资风险小、系统结构灵活，可扩展性强，成本低，用于中小型并行任务

4.4 网格GRID

利用互联网把广泛分布的资源连成一个逻辑整体，即一台虚拟超级计算机，实现资源共享

5. 性能

加速比S：
并行系统的加速比是指并行算法比串行算法的执行加快了多少倍

Amdahl定律：
S=1/(f+(1-f)/p)
其中：
f是串行分量的比例（应用中的不可并行化部分和问题规模之比）
p是处理机数

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 21009200039@stu.xidian.edu.cn