计算机体系结构课程笔记（四）

第六章 输入输出系统

国防科大计算机体系结构课程第六-八章笔记

6.1 存储设备

6.1.1 磁盘

• 磁盘始终占据着后备存储器的主宰地位。原因有二：
  • 磁盘一直是虚拟存储器技术的物质基础，执行程序时，磁盘用作为交换缓冲区
  • 关机时，磁盘作为操作系统和所有应用程序的非易失性的驻留介质
  • 磁盘是最重要的 I/O 设备，是存储层次中辅存的载体，发展比较平缓
• 磁盘由一组绕轴旋转的盘片组成，盘片的数量为 1~20 片
• 磁盘系统的转速一般在每分钟 3600 转到 15000 转之间，即 3600rpm~15000rpm
• 磁道（每一个盘片有 5000~30000 条磁道）。
• 扇区（每条磁道分为 100~500 个扇区）。所有磁道具有相同数目的扇区

磁盘访问时间计算

1. 寻道时间

• 若要读写扇区，磁盘控制器发出命令首先将磁头移动到包含有所需数据的磁道上，这个过程称为“寻道”，所需要的时间叫做“寻道时间”
• 最小寻道时间、最大寻道时间和平均寻道时间。常见的平均寻道时间的公布值约为 6ms 到 20ms，实际应用当中的平均寻道时间约为公布值的 25% 到 33%
  2. 旋转时间
• 所需扇区转到磁头之下所需要的时间称为旋转时间。大部分磁盘的转速在3600rpm到10,000rpm，平均延迟是磁盘转半圈的时间，所以对大部分磁盘的平均旋转时间 $T_AR=3ms~8.3ms$
  3. 传输时间
• 传输时间是指在磁头下传输一个数据块(通常是一个扇区)所需花的时间。它由块的大小、旋转速度、磁道记录密度和连接磁盘电子器件的速度确定
• 数据传输率有两个：一是从盘面到缓冲存储器的内部传输率；一是从缓冲存储器到主机的外部传输率
  • 内部数据传输率：硬盘将数据从盘片上读取出，交给硬盘上的缓冲存储器的速度。也被称作硬盘的持续传输率（Sustained Transfer Rate），它取决于硬盘转速和盘片位密度。内部传输率等于磁头相对磁盘的线速度与磁盘位密度之积。外部传输率是以内部传输率为基础的，有效地提高硬盘的内部传输率才能对磁盘性能有最直接、最明显的提升
  • 外部传输率：计算机通过磁盘接口从硬盘的缓存中将数据读出，交给相应的控制器的速度；被称为突发数据传输率（Burst Data Transfer Rate）。外部数据传输率和磁盘的接口有关，目前已有 IDE、EIDE、Ultra-EIDE、SCSI、Fast and Wide-SCSI、FC-AL 等接口。ATA-6 接口的速度已经达到 133MB/s
• 内部传输率等于记录的位密度乘以盘面旋转的线速度。外部传输率则与接口有关
  4. 控制器时间
• 控制磁盘及磁盘与主存之间数据传输，需要一系列的控制器和通道来完成
• 控制器时间是控制器在执行I/O访问时的额外开销

因此，磁盘访问时间=寻道时间+旋转时间+传输时间+控制器时间

磁盘访问时间例题
对于目前一般的磁盘而言，读或写一个 512 字节的扇区的平均时间是多少？假设此时磁盘空闲，这样没有排队延迟；公布的平均寻道时间是 9ms，传输速度是 4MB/s，转速是 7200rpm，控制器的开销是 1ms

[分析]

• 寻道时间 = 9ms
• 旋转时间 = 0.5 / 7200rpm = 4.2ms
• 传输时间 = 0.5KB / 4.0MB/s = 0.125ms
• 控制器时间 = 1ms
• 因此访问时间 = 9 + 4.2 + 0.125 + 1 = 14.3ms

磁表面记录密度

• 磁盘记录数据的密度一般用“磁表面记录密度”来表示，也就是每平方英寸上的位数：

  • 1988年前，每年增长约 29%，即 3 年翻一番；
  • ~1996年后，每年增长 60%，即 3 年翻四番。
  • ~2001年，每年增长 100%，2001 年实验室中可达每平方英寸600亿位

• 提高转速可以提高数据传输速率。旋转速度越高，数据就可以越快到达驱动器读写头能够接触的位置。目前硬盘最大转速为 15000RPM。但转速提高也带来一些弊端，例如工作噪音和发热量变大，工作状态下的抗冲击能力也有所下降等。

• 提高记录密度。目前采用的技术主要有：提高单碟容量以及改进信号处理技术。由于单碟容量越大的硬盘数据密度越高，磁头的寻道频率与移动距离可以相应的减少，从而减少了平均寻道时间，内部传输速率也得到了提高

• 在传统的纵向记录技术中，为了提高面密度以增加总的存储容量，必须压缩数据位并使其更紧密地排列在一起。然而，如果数据位太小，为其定位的磁能也会相应减小，小到一定程度后热能就可能会使其退磁，存储的数据就会丢失，这一现象被称为超顺磁性。为了避免超顺磁性效应，磁盘介质制造商一直在努力提高介质的矫顽磁性(写一个数据位所需要的‘磁场’ ) 。不过，能施加的磁场大小会受到磁头材料的限制

• 而在垂直记录技术(Perpendicular Magnetic Recording)中，盘片的磁化不像目前水平记录技术那样发生在盘片所在的平面上，而是发生在与盘片相垂直的平面上。这样一来，数据位就是指向上或向下的定向磁化区域。(在水平记录技术中，数据位的磁化是在磁盘平面上，在与磁头运动方向相同和相反的点之间翻转。)介质淀积在软磁衬底上，衬底的作用是作为写磁场返回路径的一部分并有效地生成记录磁头的镜像，这将使记录磁场增强一倍，故能达到比水平记录技术更高的记录密度。值得一提的是，垂直记录并不会因这项强化而提高功率消耗或产生更高热能，这对于对耗电与热量敏感的笔记本领域非常关键。此外，垂直记录也因为能够强化数据对于热衰退的阻抗能力从而提升硬盘可靠性。对于生产厂商来说，垂直记录技术将可延长磁盘储存装置的发展年限，对消费者来说，则可提供更高容量的硬盘容量

磁盘在后备存储器上的地位曾受到过多次考验，主要原因就是所谓“访问时间差距”问题。磁盘与 DRAM 的性能价格比差异很大。虽然 DRAM 的数据传输率约为磁盘的 50 倍，但是其访问时间却是磁盘的十万分之一

6.1.2 Flash 存储器和固态硬盘 SSD

• SSD的优点是：
  • 永久性；
  • 速度快；
  • 高传送速率和高可靠性。
• SSD的最大缺点是：
  • 有限擦写次数
    • 磨损均衡（动态、静态）
  • 成本太高，每 MB 的价格大约是磁盘价格的 50 倍

6.1.3 磁带

• 磁盘和磁带性能价格比的差异主要取决于它们的机械构成
  • 磁盘盘片具有有限的存储面积，并且存储介质被封装在每个读部件内，提供 ms 级的随机访问
  • 磁带绕在可转动轴上，一个读部件可以使用多盘磁带(没有长度限制)，但磁带需要顺序访问，每次访问都可能需要较长的反绕、退出和加载时间，等待时间较长(数秒)
• 对磁带而言，最大的优点是容量极大、技术成熟、单位价格低廉。最大的缺点是访问时间较长。这种差异恰好使得磁带成为磁盘的备份技术。
• 宽 0.38cm1.27cm;长 183m731.5m;(110G 以上）
• 磁带技术的主要受限因素是在其线速度不定，为解决该问题，提出了“螺旋扫描磁带(Helical Scan Tapes)”，使磁带保持同样的线速度，这种技术以 20 到 50 的倍数增加记录密度，螺旋扫描磁带目前已被普遍使用在视频录像设备中，大大降低了磁带和读部件的开销
• 磁带的另外一个缺点是易磨损，螺旋磁带只能使用几百遍，传统的高质量磁带则可以使用几百万遍。螺旋扫描磁头同样容易磨损，通常额定指标为连续使用 2000 小时
• 为了解除操作中的负担，同时也加速换带速度，便产生了自动磁带库。自动磁带库通过机械手自动地安装和更换磁带，相当于又提供了一个新的存储器层次，这种自动化的磁带库可在无人工干预的情况下，十几秒内访问几TB的信息
• STC 的 PowderHorn 可以处理 6000 个磁带，提供的总容量达 60TB

6.1.4 光盘

• 只读类光盘的全称为光学紧密盘(Optical Compact Disk)，简称 CD-ROM。
• 特点是：
  • 容量大(640M字节)、存储寿命长；
  • 成本低、读出设备价格便宜；
  • 便于保管、便于携带等。
• 最大问题是不能够写入。因此 CD-ROM 适于作为软件和资料的载体，基本已经替代了几年前广泛使用的软盘
• 可写类光盘包括两类：
  • 一次性写：称为可记录光盘 CD-R(CD-Recordable)，又称为 WORM 盘，出厂时是空白的，用户通过写入设备，将数据写入 CD-R 中。特性与 CD-ROM 相当，可以通过普通的 CD-ROM 读设备读出，因此特别适合于作为数据备案的存储介质。
  • 多次写：称为 WMRM(Write Many Read Many) 盘，主要采用磁光(MO)存储技术
• MO光盘的容量更大(有 600MB、1.2GB、2.4GB 等规格)、保存和使用都很方便、便于携带，最大的问题是目前盘片和读写设备的价格昂贵，且各厂家的标准不统一，因此不够普及。这种 WMRM 盘作为大型软件编制、多媒体软件产品研制过程中的备案介质是非常合适的
• 多台光盘机组合在一起有三种结构：
  • 光盘库(也叫自动换盘机，即Jukebox)
    • 光盘库是一种能自动把机框中存放的许多片光盘选出并装入光盘机进行读写的设备
    • 费用低；
    • 可兼容性及低风险；
    • 随机存取；
    • 存储寿命长、保管容易、占用空间少；
    • 具有多媒体功能
  • 光盘塔(CD-ROM Tower)
    • 优点：
      • 安装简便；易于管理；使用便利；
      • 资源共享；远程访问；
      • 寿命长；结构简单；造价也低；
      • 读取光盘速度快。
    • 缺点：
      • 容量较小；光盘塔中光盘机数量受到 SCSI 设备地址数的限制
  • 光盘阵列(CD-ROM Array)
    • 从阵列技术的基本原理来说，光盘阵列与磁盘阵列有一定的相似性。但光盘具有盘片可换、每道(柱面)只有一个读写头、寻道时间较长等特点，因此光盘阵列技术又有其特殊性

6.2 I/O 系统分析与评价

1. I/O性能与系统响应时间

• 衡量I/O系统性能的标准
  • I/O系统的容量(能连几个 USB 等)
  • 响应时间
  • 吞吐率
• 响应时间和吞吐率之间存在矛盾
  • 生产服务模型

2. Little 定律

• I/O系统的响应时间和吞吐率的计算
  • 排队论
  • 黑箱(Black Box)
• Little定律
  • 系统中的平均任务数 = 到达率×平均响应时间

3. M/M/1 排队系统

• M/M/1排队系统一般假设为：

  • 系统为一个平衡系统
  • 连续两个到达请求的时间间隔服从指数分布，其均值为平均到达时间
  • 请求的个数不受限制
  • 如果排队中有任务，服务员服务完当前任务后立即服务下一个
  • 队列无限长，FIFO 规则
  • 系统只有一个服务员

• 相关结论
  

• M/M/m 排队系统

  • 基于 M/M/1 排队系统
  • 服务员增加为 m 个
  • 相关结论

4. I/O 基准测试程序

• 使用 I/O 基准测试程序来反映响应时间和吞吐率之间的平衡关系
• TPC
  • 事务处理委员会
  • 发布 9 个事务处理基准测试程序
  • 高端商业应用中，通常采用 TPC-C 测试程序进行测试
• TPC具有一些独特的性质
  • 测试结果中给出系统的价格因素
  • TPC模拟的是实际系统
  • 测试结果经过TPC审核后才能发布
  • 吞吐率指标受到响应时间的限制
  • 通过独立的机构来维护

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

• 术语
  • 故障(fault)，可以恢复
  • 错误(error)，不能恢复，不一定使得机器停掉
  • 失效(failure)
• 故障产生原因
  • 硬件
  • 设计
  • 操作
  • 环境(温度等)
• 故障分类
  • 暂时性
  • 间歇性
  • 永久性
• 存储外设可靠性参数
  • 可靠性
  • 可用性
  • 可信性
• 提高系统可靠性的方法
  • 故障避免技术：通过合理构建系统来避免故障
  • 故障容忍技术：采取冗余措施
  • 错误消除技术：通过验证，最大限度地减少潜在的错误
  • 错误预报技术：通过分析，预报错误的出现，以便提前采取应对措施

6.3 RAID

盘阵列(RAID，即 Redundant Array of Inexpensive Disks)，即廉价磁盘冗余阵列，简称盘阵列技术

1987年，由加州大学伯克利分校的Patterson、Gibson 和 Katz 提出

既可以提高存储系统的可靠性，又可以提高存储系统的性能。这种技术可以通过使用多个磁盘驱动器（包括多个磁臂）而不是使用一个大容量的磁盘（单个磁臂）来提高磁盘的吞吐率。使用磁盘阵列可以简单地将数据分布到多个磁盘上（称为数据分块技术），这样使得一个数据的访问将导致对多个磁盘的同时访问。

盘阵列容量大、速度快、可靠性高、造价低廉。它是目前解决计算机I/O瓶颈的有效方法之一，有着广阔的发展前景

6.3.1 RAID 0

• 亦称数据分块（Striping），即把数据分布在多个盘上，实际上是非冗余阵列，无冗余信息。严格地说，它不属于 RAID 系列
  

• 优点：高性能，磁盘利用率高

• 缺点：系统可靠性差，没有冗余

6.3.2 RAID 1

• 亦称镜像盘，使用双备份磁盘
  

• 优点：I/O速度快，可靠性高

• 缺点：代价高，可扩展性不好

一个读请求可由包含请求数据的两个物理磁盘中的某一个提供，只要它的寻道时间加旋转时间延迟较小。这样 RAID 1 的读性能由镜像盘中读性能最好的磁盘决定。故在 I/O 处理中，如果是大批的读请求，RAID 1 的性能能够达到 RAID 0 性能的两倍

6.3.3 RAID 2

• 位交叉式海明编码阵列
  

• 优点：

  • 高速误差校正
  • 数据传输速率高

• 缺点：

  • 校正空间较大，盘阵列利用率较低

RAID 2 的优点是使用海明编码来进行错误检测和纠正，数据传输率高。海明校验码可以检测磁盘的 2 位错误，并纠正 1 位数据错误。对于单个读，所有磁盘同时读取，请求的数据和相关的海明校验码被传送到阵列管理器。如果出现 1 位错误，则阵列管理器可以立即识别并加以纠正，因此读取时间很短，可以达到很高的数据传输率。对于单个写，所有的数据盘和校验盘都要参加写操作。RAID 2 阵列管理器的设计比后面的 RAID 级别要简单

RAID 2 的缺点是需要多个磁盘来存放海明校验码信息，冗余磁盘数量与数据磁盘数量的对数成正比。这样，尽管 RAID 2 比 RAID 1 需要的磁盘少，RAID 2 存储容量的利用率仍然不高，尤其是在数据字长较短的情况下。另外，RAID 2 可以达到的数据传输率将受限于整个磁盘阵列中最慢的磁盘以及阵列管理器的校验速度

6.3.4 RAID 3

• 位交叉奇偶校验盘阵列，是单盘容错并行传输的阵列。即数据以位或字节交叉的方式存于各盘，冗余的奇偶校验信息存储在一台专用盘上
  

• 在RAID3中，将磁盘分组，读写要访问组中所有盘。当一个磁盘出故障时，可以通过奇偶校验磁盘中的校验和来恢复出错数据

• 优点：冗余代价低，传输速率高

• 应用领域：多媒体应用

先将分布在各个数据盘上的一组数据加起来，将和存放在冗余盘上。一旦某一个盘失效，只要将冗余盘上的和减去所有正确盘上的数据，得到的差就是失效的盘上的数据。冗余盘中的奇偶校验和通常是模 2 和。这种方法的缺点是恢复时间较长，但由于磁盘失效的可能性很小，因此还是可以接受的

6.3.5 RAID 4

• 块交叉奇偶校验盘阵列，即数据以块(块大小可变)交叉的方式存于各盘，冗余的奇偶校验信息存在一台专用盘上
  

优点：读写速度快；冗余代价低
缺点：阵列控制器复杂

由于磁盘扇区中存在错误检测信息，使得磁盘在读数据时就可以检测数据是否正确，因此只要访问的数据以扇区为单位，则每个磁盘都可以同时独立地进行这种操作。与 RAID 3 相比，RAID 4 中对一个数据的读操作是对两个磁盘的两次读操作

6.3.6 RAID 5

• 块交叉分布式奇偶校验盘阵列，即数据以块交叉的方式存于各盘，但无专用的校验盘，而是把冗余的奇偶校验信息均匀地分布在所有磁盘上
  

• 优点：

  • 冗余代价较小；
  • 读数据速率高；
  • 写数据相对较快。

• 缺点：

  • 控制器设计复杂

通过将校验信息分布到多个磁盘中，这样就不会出现 RAID 4 中冗余磁盘成为写操作的瓶颈这个问题

6.3.7 RAID 6

• 双维奇偶校验独立存取盘阵列，即数据以块(块大小可变)交叉的方式存于各盘，冗余的检、纠错信息均匀地分布在所有磁盘上。并且，每次写入数据都要访问一个数据盘和两个校验盘，可容忍双盘出错

目前的计算机实际上是将多种盘阵列技术综合使用

6.4 总线

1. 总线特点

• 优点：
  • 低成本
  • 多样性
• 缺点：
  • 可能造成设备信息交换的瓶颈，从而限制了系统中总的I/O吞吐量

总线设计存在很多技术难点，一个重要原因就是总线上信息传送的速度极大地受限于各种物理因素，如总线的长度、设备的数目、信号的强度等，这些物理因素限制了总线性能的提高。另外，对 I/O 操作的低延迟要求以及对 I/O 高吞吐量的要求也可能造成设计需求上的冲突

2. 总线设计时因考虑的因素

总线的分类

• 按设备定时方式分类：
  • 同步总线；同步总线上所有设备通过统一的总线系统时钟进行同步
  • 异步总线：设备之间没有统一的系统时钟，设备自己内部定时。设备之间的信息传送用总线发送器和接收器控制。但在传输时，异步总线需要额外的同步开销
  • 采用独立的地址和数据线、更宽的数据总线的位数以及多字数据传输块将提高总线的性能，但同时也带来了高成本

3. 总线标准

• 只要计算机和 I/O 设备的设计都满足相应的标准，那么 I/O 设备和计算机可以任意连接
• I/O 总线标准就是定义设备连接的文件

4. 常用的 I/O 总线

• 概况

• 常用的 I/O 总线标准

  • ISA
  • EISA
  • PCI：扩展主机设备(PCIE)
  • USB(含 USB 2.0)：连接各种外部设备到主机
  • IEEE 1394、……
  • RS-485/RS-232
  • CAN(汽车，卫星)
  • IIC(家电等)

• 主要影响因素：

  • 系统中各部件的工作频率
  • 传输数据和编址地址位数

5. I/O 总线的发展历程

6. 设备的连接

• I/O 设备编址方式

  • 存储器映射 I/O
  • 独立编址(有单独的访问 I/O 指令，如 in, out)

• I/O 设备控制方式

  • 程序查询
  • 中断
  • DMA(部分单片机内也开始使用这种方式)
  • I/O 处理机(包含功能较弱的通道)

• 在大型计算机系统中，采用程序控制、中断和 DMA 这三种基本的 I/O 方式来管理外围设备，会引起如下两个问题：

  • 所有外围设备的 I/O 工作全部都要由CPU来承担，CPU 的 I/O 负担很重，不能专心于用户程序的计算。低速外围设备每传送一个字符都要由 CPU 执行一段程序来完成，而高速外围设备虽然使用 DMA 方式减少了 CPU 的干预，但初始化工作仍然需要 CPU 用程序来完成

（四种设备控制方式为计组重点内容，略）

6.5 通道

• 接受 CPU 发来的 I/O 指令，根据指令要求选择一台指定的外围设备与通道相连接

• 执行 CPU 为通道组织的通道程序，从主存中取出通道指令，对通道指令进行译码，并根据需要向被选中的设备控制器发出各种操作命令

• 给出外围设备的有关地址，即进行读／写操作的数据所在的位置。如，磁盘存储器的柱面号、磁头号、扇区号等

• 给出主存缓冲区的首地址，这个缓冲区用来暂时存放从外围设备上输入的数据，或者暂时存放将要输出到外围设备中去的数据

• 控制外围设备与主存缓冲区之间数据交换的个数，对交换的数据个数进行计数，并判断数据传送工作是否结束

• 指定传送工作结束时要进行的操作。例如，将外围设备的中断请求及通道的中断请求送往 CPU 等

• 检查外围设备的工作状态，是正常或故障。根据需要将设备的状态信息送往主存指定单元保存

• 在数据传输过程中完成必要的格式变换，例如，把字拆卸为字节，或者把字节装配成字等

• 通道分为三种类型：

  • 字节多路通道：简单的共享通道，为多台低速或中速的外围设备服务。采用分时方式工作
  • 选择通道：为高速外围设备（如磁盘存储器等）服务。在传送数据期间，只能为一台高速外围设备服务，在不同的时间内可以选择不同的设备，可以在一段集中的时间内完成高速设备的传输任务，比较适合高速设备
  • 数组多路通道：为高速设备服务。时间片轮转、分时复用的思想，各台高速设备重迭操作，但是传输的单位不是字节，而是一块

6.6 I/O 与操作系统

能够使处理器性能发挥的软件是编译器，而发挥存储性能的软件是操作系统，采用哪种硬件进行 I/O 处理由操作系统决定，所以在设计 I/O 系统时还要注意操作系统的因素

• 数据不一致问题有两个方面
  • 存储器中可能不是 CPU 产生的最新数据，所以 I/O 系统从存储器中取出来使用的是陈旧数据
  • I/O 与存储器交换数据之后，在 Cache 中被 CPU 使用的可能就是陈旧数据

由于 I/O 会在两个方面导致数据不一致的问题，那么我们直接将 I/O 总线挂接在 Cache 上，这样 I/O 从 Cache 读取数据一定是最新的（无论 Cache 写策略是直写还是写回），CPU 访问数据时要先访问 Cache，因此 CPU 使用的数据也是最新的。
但是这种方式需要考虑对性能的影响。

• 写直达 Cache 可以保证存储器和 Cache 有相同的数据
  • 但是这种方式只能解决一个方面的数据不一致问题，即 CPU 读数据时仍然读取到的是 Cache 的旧数据
• 写回 Cache 则需操作系统帮助进行数据检查
• 根据 I/O 使用的存储器地址来清除 Cache 相应的块，确保 I/O 使用的数据不在 Cache 中
  • 这种方式貌似可行，但是相对来说增加了一点开销
• 地址检查过程也可以使用硬件完成

DMA 与虚拟存储器

• 使用 DMA，I/O 设备直接访问内存（物理地址），如果不使用虚拟存储器，则 DMA 使用物理地址来传输数据
• 若使用虚拟存储器，使用物理地址进行 DMA，存在以下两个问题：
  • 对于超过一页的数据，由于缓冲区使用的页面在物理存储器中不一定是连续的，传输会发生问题
  • DMA 正在存储器和帧缓冲器之间传输数据时，操作系统从存储器中移出一些页面(或重新分配)，DMA 将会在存储器中错误的页面上传输数据

允许 DMA 设备直接使用虚拟地址，在 DMA 期间由硬件将虚拟地址映射到物理地址。这样，I/O 使用的缓冲区页面在虚拟存储器中是连续的，但物理页面可以分散在物理存储器中，并且虚拟地址提供了对 I/O 操作的保护。如果使用虚拟 DMA 的进程在内存中被移动，操作系统应该能够及时地修改相应的 DMA 地址表

第七章 多处理机

一个问题:
图书馆将一批新书上架，可以有多种方式。假定将书按类上架，而将书架依据在书库中的位置分成一些组
解决办法
若由一工人单独完成，不能在要求的时间内完成任务
若由多个工人完成， 假定每次一人仅往书架上放一本书。可以采用两种不同的方式
（1）将所有的书籍平均分配给每个人去完成。这种划分方法不是太有效，原因是每个工人为了将书上架必须走遍所有的书架。
（2）将所有书架分成一些组，且平均分配给各个工人负责，同时将所有图书平均分配给每个工人去上架。如果工人发现一本书属于自己所负责的书架上，则将其放入书架。否则，将这本书传给所在书架对应的工人。这种分法对应的效率比较高
结论
将一个任务划分成一些子任务，并分配给多个工人去完成，工人们相互合作、并在需要时相互传递图书，这种协调的工作方式可较快地完成任务
并行计算就是严格地按照上述原理来完成的

并行计算相关的两个概念

1. 任务划分(task partitioning)
   将图书平均分配给所有工人为任务划分的一个例子。
2. 通信(communication)
   工人之间传递图书为子任务通信的例子。
   什么是并行计算？

并行计算是指同时对多个任务或多条指令、或对多个数据项进行处理。完成此项处理的计算机系统称为并行计算机系统，它是将多个处理器通过网络以一定的连接方式有序地组织起来

并行计算机的发展原因：

• 要获得超过单处理器的性能，最直接的方法就是把多个处理器连在一起
• 体系结构改进能否持续下去？通过复杂度和硅技术的提高得到的性能提升正在减小；
• 并行计算机应用软件已有缓慢但稳定的发展。
• 重点：中小规模的机器(处理器的个数不超过128)的多处理机设计技术

并行计算的研究内容:
(1) 并行计算机设计
(2) 有效算法的设计
(3) 评价并行算法的方法
(4) 并行计算机语言
(5) 并行编程环境与工具
(6) 并行程序的可移植性
(7) 并行计算机的自动编程

并行计算的应用领域：
(1) 天气预报
(2) 卫星数据处理
(3) 石油数据处理（连续优化问题）
(4) 调度问题
(5) VLSI设计（离散优化问题）
(6) ……

美国政府的HPCC计划公布的重大挑战性应用

1. 磁记录技术：研究静磁和交互感应以降低高密度磁盘的噪音
2. 新药设计：通过抑制人的免疫故障病毒蛋白酶的作用来研制治疗癌症与艾滋病的药物
3. 高速民航：用计算流体动力学来研制超音速喷气发动机
4. 催化作用：仿生催化剂计算机建模，分析合成过成中的酶作用
5. 燃料燃烧：通过化学动力学计算，揭示流体力学的作用，设计新型发动机
6. 海洋建模：对海洋活动与大气流的热交换进行整体海洋模拟
7. 臭氧耗损：研究控制臭氧损耗过程中的化学与动力学机制
8. 数字解析：实时临床成像、计算层析术、磁共振成像
9. 大气污染：对大气质量模型进行模拟研究，控制污染的传播，揭示其物理与化学机理
10. 蛋白质结构设计：对蛋白质组成的三维结构进行计算机模拟研究
11. 图像理解：实时绘制图像或动态
12. 密码破译：破译由长位数组成的密码，寻找该数的两个乘积因子

并行计算的应用分类

（1）计算密集型（Compute-Intensive）
这一类型的应用问题主要集中在大型科学工程计算与数值模拟（气象预报、地球物理勘探等）
（2）数据密集型 (Data-Intensive)
Internet的发展，为我们提供了大量的数据资源，但有效地利用这些资源，需要进行大量地处理，且对计算机的要求也相当高，这些应用包括数字图书馆、数据仓库、数据挖掘、计算可视化。
（3）网络密集型 (Network-Intensive)
通过网络进行远距离信息交互，来完成用传统方法不同的一些应用问题。如协同工作、遥控与远程医疗诊断等

7.1 引言

单处理机的发展正在走向尽头？
并行计算机在未来将会发挥更大的作用。

• 获得超过单处理器的性能，最直接的方法就是把多个处理器连在一起；
• 自1985年以来，体系结构的改进使性能迅速提高，这种改进的速度能否持续下去还不清楚，但通过复杂度和硅技术的提高而得到的性能的提高正在减小；
• 并行计算机应用软件已有缓慢但稳定的发展。

本章重点:中小规模的机器(处理器的个数＜100 多处理机设计的主流)

7.1.1 并行计算机体系结构的分类

1. 按Flynn分类法，可把计算机分成

• 单指令流单数据流（SISD）
• 单指令流多数据流（SIMD）
• 多指令流单数据流（MISD）
• 多指令流多数据流（MIMD）

2. MIMD已成为通用多处理机体系结构的选择，原因：

• MIMD具有灵活性
• MIMD可以充分利用商品化微处理器在性能价格比方面的优势

MIMD的优点（灵活性/COTS）

• MIMD机器分类:集中式共享存储器结构(Centralized Shared-Memory Architecture)。,也称为对称式共享存储器结构(SMP, Symmetric shared-memory MultiProcessor)机器或者UMA(Uniform Memory Access)机器。
• 分布式存储器结构的机器。支持较大数目的处理器，存储器必须分布到各个处理器上，而非采用集中式，否则存储器系统将不能满足处理器带宽的要求。系统中每个结点包含了处理器、存储器、I／O以及互连网络接口

3. MIMD机器分为两类（每一类代表了一种存储器的结构和互连策略）

• 集中式共享存储器结构

  • 这类机器有时被称为 UMA(Uniform Memory Access)机器

• 分布式存储器结构

  • 每个结点包含：处理器、存储器、I/O
  • 在许多情况下，分布式存储器结构优于采用集中式共享存储器结构。
  • 分布式存储器结构需要高带宽的互连

• 分布式存储器结构的优点

  • 如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；
  • 对局部存储器的访问延迟低

• 主要缺点

  • 处理器之间的通信较为复杂，且各处理器之间访问延迟较大

7.1.2 通信模型和存储器的结构模型

1. 两种地址空间的组织方案

• 物理上分离的多个存储器可作为一个逻辑上共享的存储空间进行编址。
  • 这类机器的结构被称为分布式共享存储器(DSM)或可缩放共享存储器体系结构。
  • DSM 机器被称为 NUMA(non-uniform memory access)机器。
• 整个地址空间由多个独立的地址空间构成，它们在逻辑上也是独立的，远程的处理器不能对其直接寻址
• 每一个处理器-存储器模块实际上是一个单独的计算机，这种机器也称为多计算机

两种方案：

• DSM：一个处理器如果具有访问权，就可以访问任何一个其他的局部存储器，
  DSM机器被称为 NUMA(Non-Uniform Memory Access)机器，这是因为其访问时间依赖于数据在存储器中的存放位置。
• 整个地址空间由多个独立的地址空间构成，它们在逻辑上也是独立的，远程的处理器不能对其直接寻址。在这种机器的不同处理器中，相同的物理地址指向不同存储器的不同单元

2. 两种通信模型

• 共享地址空间的机器（共享存储器机器）
  • 利用 Load 和 Store 指令中的地址隐含地进行数据通信
• 多个地址空间的机器
  • 通过处理器间显式地传递消息完成 (消息传递机器)
• 消息传递机器根据简单的网络协议，通过传递消息来请求某些服务或传输数据，从而完成通信

区别：

• 对于共享地址空间的机器，用 load 和 store 指令中的地址隐含地进行数据通讯，因而可称为 共享存储器机器
• 对于多个地址空间的机器，数据通讯要通过处理器间显式地传递消息完成，因而这种机器常称为 消息传递机器

例如：
一个处理器要对远程存储器上的数据进行访问或操作
(1) 发送消息，请求传递数据或对数据进行操作；
远程进程调用(RPC， remote process call)
(2) 目的处理器接收到消息以后，执行相应的操 作或代替远程处理器进行访问，并发送一个 应答消息将结果返回

对于通信机制的性能，可以通过下面三个关键的性能指标来进行衡量：

1. 通信带宽──理想状态下的通信带宽受限于处理器、存储器和互连网络的带宽。进行通信时，结点内与通信相关的资源被占用，这种占用限制了通信速度。
2. 通信延迟──理想状态下通信延迟应尽可能地小。通信延迟的构成为：
   通信延迟＝发送开销＋跨越时间＋传输延迟＋接收开销（?）

   （老师讲 “跨越时间”是指第一位数据从发送端口到接收端口所需的时间，“传输延迟”是指最后一位通信数据从发送端口到接收端口之间的延迟，我没怎么听懂，这两个有什么区别吗？这和计网里的数据包传送有什么不一样吗？）

3. 通讯延迟的隐藏──如何才能较好地将通信和计算或多次通信之间重叠起来，以实现通讯延迟的隐藏

每种通信机制各有优点，共享存储器通信主要有以下优点：
(1) 与常用的对称式多处理机使用的通信机制兼容。
(2) 当处理器通信方式复杂或程序执行动态变化时易于编程，同时在简化编译器设计方面也占有优势(都统一翻译成存储指令即可)。
(3) 当通信数据较小时，通信开销较低，带宽利用较好。
(4) 通过硬件控制的 Cache 减少了远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。

消息传递通信机制的主要优点包括：

• 硬件较简单。
• 通信是显式的，从而引起编程者和编译程序的注意，着重处理开销大的通信。
  • 当然，可在支持上面任何一种通信机制的硬件模型上建立所需的通信模式平台。
  • 在共享存储器上支持消息传递相对简单，因为发送一条消息可通过将一部分地址空间的内容复制到另一部分地址空间来实现。
  • 但在消息传递的硬件上支持共享存储器就困难得多

7.1.3 并行处理面临的挑战

1. 程序中有限的并行性

• 有限的并行性使机器要达到好的加速比十分困难
• 通过所给的例子，100 个处理器达到 80 的加速比，并行比例要达到 99.75%，即 0.25% 的串行比例影响了 20 的加速比。因此我们得到结论：串行对于并行处理的加速比具有至关重要的影响

2. 相对较高的通信开销（可通过 Amdahl 定律解释）

• 面临的第二个挑战主要是指多处理机中远程访问的较大延迟。在现有的机器中，处理器之间的数据通信大约需要 50～10000 个时钟周期

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

在并行处理中，负载平衡、同步和存储器访问延迟等影响性能的因素常依赖于高层应用特点，如应用程序中数据的分配，并行算法的结构以及数据在空间和时间上的访问模式等。

依据应用特点可把多机工作负载大致分成两类：单个程序在多处理机上的并行工作负载和多个程序在多处理机上的并行工作负载

7.2 对称式共享存储器体系结构

反映并行程序性能的一个重要的度量是计算与通信的比率。如果比值较高，就意味着应用程序中相对于每次数据通信要进行较多的计算。

通信在并行计算中的开销是很大的，因而较高的计算／通信比率十分有益。在一个并行处理环境下，当要增加处理器的数目，或增大所求解问题的规模，或者两者同时都增大时，都要对计算／通信比率的变化加以分析。

例如，在增加处理器数目的同时知道这个比率的变化，会对应用能获得的加速比有清楚的了解。

通常状况下，计算／通信比率随着处理的数据规模增大而增加，随着处理器数目的增加而降低。

用更多的处理器来求解一个固定大小的问题会导致不利因素的增加，因为处理器之间通信量加大了。

增加处理器时应该调整数据的规模，从而使通信的时间保持不变。

7.2.1 多处理机 Cache 一致性

• 多个处理器共享一个存储器。
• 当处理器规模较小时，这种机器十分经济。
• 支持对共享数据和私有数据的Cache缓存。
  • 私有数据供一个单独的处理器使用，而共享数据供多个处理器使用
• 共享数据进入Cache产生了一个新的问题：Cache 的一致性问题
  • 对共享数据，不同处理器的 Cache 都保存有对应存储器单元的内容，因而在操作中就可能产生数据的不一致，称为 Cache一致性（Coherence）问题

1. 不一致产生的原因（Cache 一致性问题）

• I／O 操作
  • Cache中的内容可能与由 I／O 子系统输入输出形成的存储器对应部分的内容不同
• 共享数据
  • 不同处理器的 Cache 都保存有对应存储器单元的内容

2. 存储器是一致的（非正式地定义）

如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的

• 存储系统行为的两个不同方面
  • 返回给读操作的是什么值
  • 什么时候才能将已写入的值返回给读操作
• 满足条件
  • 处理器 P 对 X 进行一次写之后又对 X 进行读，读和写之间没有其它处理器对 X 进行写，则读的返回值总是写进的值。（一个处理器）
  • 一个处理器对 X 进行写之后，另一处理器对X进行读，读和写之间无其它写，则读 X 的返回值应为写进的值。（多个处理器）
  • 对同一单元的写是顺序化的，即任意两个处理器对同一单元的两次写，从所有处理器看来顺序都应是相同的

假设:直到所有的处理器均看到了写的结果，一次写操作才算完成；允许处理器无序读，但必须以程序规定的顺序进行写

三条已充分地保证了一致性，什么时候才能获得写进去的值仍是一个重要的问题

7.2.2 实现一致性的基本方案

在一致的多处理机中，Cache 提供两种功能

• 共享数据的迁移
  • 降低了对远程共享数据的访问延迟
• 共享数据的复制
  • 不仅降低了访存的延迟，也减少了访问共享数据所产生的冲突

小规模多处理机不是采用软件而是采用硬件技术实现 Cache 一致性

(1) Cache 一致性协议
对多个处理器维护一致性的协议
(2) 关键：跟踪共享数据块的状态
(3) 共享数据状态跟踪技术

• 目录
  • 物理存储器中共享数据块的状态及相关信息均被保存在目录中。
• 监听
  • 每个 Cache 除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息
  • 监听：Cache 通常连在共享存储器的总线上，各个 Cache 控制器通过监听总线来判断它们是否有总线上请求的数据块
• 两种协议
  • 写作废协议
    • 在一个处理器写某个数据项之前保证它对该数据项有唯一的访问权，即在某个 CPU 往内存中写入数据时，将其他拥有该单元的拷贝全部作废，写完后其他处理器再从该内存单元中重新读取数据，此时便是新的数据
  • 写更新协议
    • 当一个处理器写某数据项时，通过广播使其它 Cache 中所有对应的该数据项拷贝进行更新
  • 写作废和写更新协议性能上的差别
    • 对同一数据的多个写而中间无读操作的情况，写更新协议需进行多次写广播操作，而在写作废协议下只需一次作废操作。
    • 对同一块中多个字进行写，写更新协议对每个字的写均要进行一次广播，而在写作废协议下仅在对本块第一次写时进行作废操作。
    • 从一个处理器写到另一个处理器读之间的延迟通常在写更新模式中较低。而在写作废协议中，需要读一个新的拷贝。

在基于总线的多处理机中，写作废协议成为绝大多数系统设计的选择

7.2.3 监听协议及其实现

• 小规模多处理机中实现写作废协议的关键利用总线进行作废操作,每个块的有效位使作废机制的实现较为容易。
• 写直达 Cache，因为所有写的数据同时被写回主存，则从主存中总可以取到最新的数据值。
• 对于写回 Cache，得到数据的最新值会困难一些，因为最新值可能在某个 Cache 中，也可能在主存中。

当某个处理器进行写数据时，必须先获得总线的控制权，然后将要作废的数据块的地址放在总线上。其它处理器一直监听总线，它们检测该地址所对应的数据是否在它们的 Cache 中。若在，则作废相应的数据块。获取总线控制权的顺序性保证了写的顺序性，因为当两个处理器要同时写一个单元时，其中一个处理器必然先获得总线控制权，之后它使另一处理器上对应的拷贝作废，从而保证了写的严格顺序性

• 在写回Cache条件下的实现技术
  • 用Cache中块的标志位实现监听过程。
  • 给每个Cache块加一个特殊的状态位说明它是否为共享。
  • 因为每次总线任务均要检查Cache的地址位，这可能与CPU对Cache的访问冲突。可通过下列两种技术之一降低冲突：
    • 复制标志位
    • 采用多级包含 Cache

7.3 分布式共享存储器体系结构

7.3.1 基于目录的 Cache 一致性

存储器分布于各结点中，所有的结点通过网络互连。访 问可以是本地的，也可是远程的。

不支持Cache一致性：

• 规定共享数据不进入Cache，仅私有数据才能保存在Cache中。
• 优点： 所需的硬件支持很少(因为远程访问存取量仅是一个字(或双字)而不是一个Cache块)
• 缺点：
  (1) 实现透明的软件 Cache 一致性的编译机制能力有限
  (2) 没有 Cache 一致性，机器就不能利用取出同一块中的多个字的,开销接近于取一个字的开销这个优点，这是因为共享数据是以 Cache 块为单位进行管理的。当每次访问要从远程存储器取一个字时，不能有效利用共享数据的空间局部性
  (3) 诸如预取等延迟隐藏技术对于多个字的存取更为有效，比如针对一个 Cache 块的预取

对远程存储器访问的巨大延迟与对本地Cache访问的短延迟相比，突出地反映出了这些缺点。例如，Cray T3E本地访问延迟为两个时钟周期，并且可被流水化，而一次远程访问则需约400个时钟周期(T3E-900, 450MHz Alpha)

解决Cache一致性问题的关键：

• 目录协议
  • 目录：用一种专用的存储器所记录的数据结构，它记录着可以进入Cache的每个数据块的访问状态、该块在各个处理器的共享状态以及是否修改过等信息。
  • 对每个结点增加目录表后的分布式存储器的系统结构
  • 而当系统的规模变大时，它又是致命的弱点。此外，监听的访问量与处理器个数的平方（N2）成正比，即使总线的带宽随系统规模线性增长（N），而实际的性能还是下降到1/N
• 目录协议的基本点
  • 在每个结点增加了目录存储器用于存放目录；
  • 存储器的每一块在目录中对应有一项；
  • 每一个目录项主要有状态和位向量两种成分。
    • 状态描述该目录所对应存储块的当前情况；
    • 位向量共有N位，其每一位对应于一个处理器的局部 Cache，用于指出该Cache中有无该存储块的拷贝
• 目录必须跟踪每个 Cache 块的状态
  • Cache 块状态有三种：
    • 共享：在一个或多个处理器上具有这个块的拷贝，且主存中的值是最新值(所有 Cache 均相同)。
    • 未缓冲：所有处理器的Cache都没有此块的拷贝。
    • 专有：仅有一个处理器上有此块的拷贝，且已对此块进行了写操作，而主存的拷贝仍是旧的。这个处理器称为此块的拥有者。
• 由于写作废操作的需要，还必须记录共享此块的处理器信息。
  • 方法：对每个主存块设置一个位向量。
  • 当此块被共享时，每个位指出与之对应的处理器是否有此块的拷贝。
  • 当此块为专有时，可根据位向量来寻找此块的拥有者。
• 宿主结点
  • 存放有存储器块和对应地址目录项的结点

7.3.2. 目录协议及其实现

基于目录的协议中，目录承担了一致性协议操作的主要功能。

• (1) 发往一个目录的消息会产生两种不同类型的动作
  • 更新目录状态
  • 发送消息满足请求服务
• (2) 目录项可能接收到三种不同的请求（注意请求的完备性）
  • 读失效
  • 写失效
  • 数据写回
• (3) 在各个状态下所接收到的请求和相应的操作
  • ①当一个块处于未缓冲状态时，对此块发出的请求及处理操作为:
  • 读失效
    • 将存储器数据送往请求方处理器，且本处理器成为此块的唯一共享结点，本块的状态转换为共享
  • 写失效
    • 将存储器数据送往请求方处理器，此块成为专有
  • ②当一个块是共享状态时，存储器中的数据是其当前最新值，对此块发出的请求及处理操作为:
    • 读失效
      • 将存储器数据送往请求方处理器，并将其加入共享集合
    • 写失效
      • 将数据送往请求方处理器，对共享集合中所有的处理器发送写作废消息，且将共享集合置为仅含有此处理器，本块的状态变为专有
  • ③当某块处于专有状态时，本块的最新值保存在共享集合指出的拥有者处理器中，从而有三种可能的目录请求
    • 读失效
      • 将“取数据”的消息发往拥有者处理器，使该块的状态转变为共享，并将数据送回目录结点写入存储器，进而把该数据返送请求方处理器，将请求方处理器加入共享集合
    • 写失效
      • 本块将有一个新的拥有者。
    • 数据写回
      • 拥有者处理器的 Cache 要替换此块时必须将其写回，从而使存储器中有最新拷贝(宿主结点实际上成为拥有者)，此块成为非共享，共享集合为空
• 对基于目录的Cache一致性的多种改进
  • 有限映射目录
  • 链式结构目录

基于目录的 Cache 一致性协议采取了“以空间换时间”的策略，减少了访问次数但增加了目录存储器，它的大小与系统规模 N 的平方成正比。
基于目录的 Cache 一致性协议是完全由硬件实现的

7.4 互连网络