1681 lines
87 KiB
Markdown
1681 lines
87 KiB
Markdown
# 第5章 线程级并行：多处理机 - 章节关键原文
|
||
|
||
## 曲冠南（qgn）
|
||
|
||
### Slide 1-3：计算机构成要素与系统互连
|
||
|
||
**Slide 2**
|
||
点：包括小到CPU内部的寄存器、ALU、控制器，到存储模块、外设，乃至多处理机的计算节点，都可以视为点；
|
||
互连网络：按照一定拓扑结构和控制方式，将点连接起来。
|
||
|
||
1. 计算机构成的两个最基本的要素
|
||
|
||
**Slide 3**
|
||
系统互连
|
||
距离增加
|
||
单位时间信息量增加
|
||
|
||
**Slide 4**
|
||
静态互连网络：指处理单元间有固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变。
|
||
|
||
**Slide 5**
|
||
动态互连网络：由开关单元构成，可以按照应用程序的要求动态的改变连接组态。
|
||
各种总线
|
||
交叉开关网络
|
||
多级互连网络
|
||
|
||
### Slide 6-11：几种基本的MIMD并行机结构模型
|
||
|
||
**Slide 6**
|
||
PVP，Parallel Vector Processor, 并行向量处理机
|
||
SMP, Symmetric Multiprocessor, 对称多处理机
|
||
MPP, Massively Parallel Processor, 大规模并行处理机
|
||
DSM，Distributed Shared Memory, 分布式共享存储多处理机
|
||
COW，Cluster of Workstations, 工作站集群
|
||
|
||
2. 几种基本的MIMD并行机结构模型
|
||
|
||
**Slide 7 - PVP**
|
||
PVP
|
||
这样的系统中包含了少量的高性能专门设计定制的向量处理器VP，每个至少具有１Ｇflops的处理能力；
|
||
存储器以兆字节每秒的速度向处理器提供数据。
|
||
向量处理器VP和共享存储模块通过高带宽的交叉开关网络互连；
|
||
这样的机器通常不使用高速缓存，而是使用大量的向量寄存器和指令缓冲器；
|
||
例如：Cray90（1991年）、NECSX-4（1994年）和我国的银河１号（1983年）等都是 PVP。
|
||
|
||
PVP的物理形态逐渐在退出历史舞台，但它的"灵魂"无处不在。其核心的"向量并行处理"思想和技术，已经深度融合并演进为当今几乎所有高性能处理器（CPU、GPU）和专用加速器的基础技术，在AI、科学计算等核心领域发挥着至关重要的作用。
|
||
|
||
**Slide 8 - SMP**
|
||
SMP
|
||
ＳＭＰ系统使用商品微处理器（具有片上或外置高速缓存）；
|
||
它们经由高速总线（或交叉开关）连向共享存储器和I/O；
|
||
这种机器主要应用于商务，例如数据库、在线事务处理系统和数据仓库等；
|
||
重要的是系统是对称的，每个处理器可等同的访问共享存储器（主要从延迟的角度）、Ｉ／Ｏ设备和操作系统服务。正是对称，才能开拓较高的并行度；也正是共享存储，限制系统中的处理器不能太多（一般少于６４个），同时总线和交叉开关互连一旦作成也难于扩展。
|
||
例如：IBM R50、SGI Power Challenge、DEC Alpha服务器8400和我国的曙光１号(1993年，中国自主研制的第一台SMP架构的高性能计算机）等都是这种类型的机器。
|
||
|
||
纯粹的、作为独立大型机存在的SMP系统如今也已非常罕见。但SMP的思想和技术，同样被吸收并内化为现代计算架构的基础，例如现代每一个CPU芯片内部，都集成了多个处理核心（如16核、64核）,这本质上就是一个微型的SMP系统。
|
||
|
||
**Slide 9 - DSM**
|
||
DSM
|
||
物理上有分布在各节点中的局部存储器，但是对用户而言，系统硬件和软件提供了逻辑上单地址的编程空间。
|
||
高速缓存目录DIR用以支持分布高速缓存的一致性。
|
||
ＤＳＭ 相对于 ＭＰＰ的优越性是编程较容易。
|
||
例如：
|
||
软件DSM -- JIAJIA：中科院计算所开发的高性能软件DSM系统，在曙光集群等平台上得到了广泛应用。
|
||
硬件DSM -- SGI Origin系列：使用NUMAlink高速互连技术，将大量节点连接成一个统一的、支持缓存一致性的共享内存系统。其顶级配置可支持512个或更多处理器，峰值性能曾达到万亿次级别。
|
||
|
||
**Slide 10 - MPP**
|
||
MPP
|
||
ＭＰＰ一般是指超大型计算机系统；
|
||
处理节点采用商品微处理器；每个节点上有自己的局部存储器；采用高通信带宽和低延迟的互连网络（专门设计和定制的）进行节点互连；
|
||
能扩放至成百上千乃至上万个处理器；
|
||
它是一种异步的ＭＩＭＤ机器，程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息相互作用；
|
||
ＭＰＰ的主要应用是科学计算、工程模拟和信号处理等以计算为主的领域。
|
||
例如：Intel Paragon、Cray T3E、IntelOption Red和我国的曙光-１０００等都是这种类型的机器。
|
||
|
||
MPP是TOP500榜单上绝大多数超算的标配架构。例如：
|
||
El Capitan（2024年榜单第一）：它由数万个节点组成，每个节点内有AMD CPU和GPU，节点间通过HPE Slingshot高速互连。
|
||
神威·太湖之光（2016年问世，2016年-2017年占据榜首）：我国首台全部采用国产处理器（申威SW26010 众核处理器）、峰值性能超过10亿亿次/秒的超级计算机
|
||
|
||
**Slide 11 - COW**
|
||
COW
|
||
在有些情况下，集群往往是低成本的变形的ＭＰＰ;
|
||
ＣＯＷ 的重要界线和特征是：
|
||
①ＣＯＷ 的每个节点都是一个完整的工作站（不包括监视器、键盘、鼠标等），这样的节点有时叫作"无头工作站"，一个节点也可以是一台PC或SMP；
|
||
②各节点通过一种低成本的商品（标准）网络（如以太网、ＦＤＤＩ和 ＡＴＭ 开关等）互连（有的商用机群也使用定做的网络）；
|
||
③各节点内总是有本地磁盘，而 ＭＰＰ节点内却没有；
|
||
④节点内的网络接口是松散耦合到Ｉ／Ｏ 总线上的，而 ＭＰＰ内的网络接口是连到处理节点的存储总线上的，因而可谓是紧耦合式的；
|
||
⑤一个完整的操作系统驻留在每个节点中，而 ＭＰＰ中通常只是个微核，ＣＯＷ 的操作系统是工作站 ＵＮＩＸ，加上一个附加的软件层以支持单一系统映像、并行度、通信和负载平衡等。
|
||
Berkeley NOW、Alpha Farm、Digital Truclster等都是 ＣＯＷ 结构。
|
||
|
||
现在"COW"这个词已很少使用，它基本被更宽泛的"集群"概念吸收。
|
||
|
||
### Slide 12-13：从存储角度来看MIMD
|
||
|
||
**Slide 12**
|
||
3. 从存储角度来看MIMD
|
||
单地址空间共享存储
|
||
均匀存储访问
|
||
非均匀存储访问
|
||
多地址空间非共享存储
|
||
|
||
**Slide 13**
|
||
单地址空间共享存储
|
||
存储器可以是物理上集中的或者分布的，但是所有存储单元有统一的地址空间，并被所有的处理器所访问。
|
||
多地址空间非共享存储
|
||
所有的存储器都是私有的、仅能由其处理器所访问。
|
||
均匀存储访问
|
||
非均匀存储访问
|
||
|
||
### Slide 14-21：多处理机Cache一致性
|
||
|
||
**Slide 14**
|
||
5.2 多处理机Cache一致性
|
||
什么是多处理机的Cache一致性问题
|
||
允许共享数据进入Cache，就可能出现多个处理器的Cache中都有同一存储块的副本，当其中某个处理器对其Cache中的数据进行修改后，就会使得其Cache中的数据与其他Cache中的数据不一致。
|
||
|
||
**Slide 15 - 存储器的一致性**
|
||
存储器的一致性
|
||
如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。
|
||
若满足如下条件，称存储器是一致的
|
||
处理器P对单元X进行一次写之后又对单元X进行读，读和写之间没有其他处理器对单元X进行写，则P读到的值总是前面写进去的值。
|
||
处理器P对单元X进行写之后，另一处理器Q对单元X进行读，读和写之间无其他写，则Q读到的值应为P写进去的值。
|
||
对同一单元的写是串行化的，即任意两个处理器对同一单元的两次写，从各个处理器的角度看来顺序都是相同的。(写串行化 )
|
||
|
||
**Slide 16**
|
||
在后面的讨论中，我们假设：
|
||
直到所有的处理器均看到了写的结果，这个写操作才算完成；
|
||
处理器的任何访存均不能改变写的顺序。就是说，允许处理器对读进行重排序，但必须以程序规定的顺序进行写。
|
||
|
||
**Slide 17 - Cache功能**
|
||
在一致的多处理机中，Cache提供两种功能：
|
||
共享数据的迁移
|
||
含义：将数据从"拥有者"那里移动到"请求者"的本地Cache中。
|
||
目的：减少对远程共享数据的访问延迟，也减少了对共享存储器带宽的要求。
|
||
应用场景：写操作场景
|
||
共享数据的复制。
|
||
含义：当多个核心同时读取同一份数据时，系统允许每个核心的Cache中都保留一份该数据的副本。
|
||
目的：不仅减少了访问共享数据的延迟，也减少了访问共享数据所产生的冲突。
|
||
应用场景：读操作场景
|
||
一般情况下，小规模多处理机是采用硬件的方法来实现Cache的一致性。
|
||
|
||
**Slide 18 - Cache一致性协议**
|
||
Cache一致性协议
|
||
在多个处理器中用来维护一致性的协议。
|
||
关键：跟踪记录共享数据块的状态
|
||
两类协议（采用不同的技术跟踪共享数据的状态）
|
||
目录式协议（directory）
|
||
物理存储器中数据块的共享状态被保存在一个称为目录的地方。
|
||
监听式协议（snooping）
|
||
每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。
|
||
Cache通常连在共享存储器的总线上，当某个Cache需要访问存储器时，它会把请求放到总线上广播出去，其他各个Cache控制器通过监听总线（它们一直在监听）来判断它们是否有总线上请求的数据块。如果有，就进行相应的操作。
|
||
|
||
**Slide 19 - 写作废协议**
|
||
例 监听总线、写作废协议举例（采用写直达法）
|
||
初始状态：CPU A、CPU B、CPU C都有X的副本。在CPU A要对X进行写入时，需先作废CPU B和CPU C中的副本，然后再将p写入Cache A中的副本，同时用该数据更新主存单元X。
|
||
|
||
采用两种方法保持Cache一致性。
|
||
写作废协议 : 在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权。(作废其他的副本)
|
||
|
||
**Slide 20 - 写更新协议**
|
||
写更新协议：当一个处理器对某数据项进行写入时，通过广播使其他Cache中所有对应于该数据项的副本进行更新。
|
||
|
||
例 监听总线、写更新协议举例（采用写直达法）
|
||
假设：3个Cache都有X的副本。
|
||
当CPU A将数据p写入Cache A中的副本时，将p广播给所有的Cache，这些Cache用p更新其中的副本。由于这里是采用写直达法，所以CPU A还要将p写入存储器中的X。如果采用写回法，则不需要写入存储器。
|
||
|
||
**Slide 21 - 性能差别**
|
||
写更新和写作废协议性能上的差别主要来自：
|
||
在对同一个数据进行多次写操作而中间无读操作的情况下，写更新协议需进行多次写广播操作，而写作废协议只需一次作废操作。
|
||
在对同一Cache块的多个字进行写操作的情况下，写更新协议对于每一个写操作都要进行一次广播，而写作废协议仅在对该块的第一次写时进行作废操作即可。
|
||
写作废是针对Cache块进行操作，而写更新则是针对字（或字节）进行。
|
||
考虑从一个处理器A进行写操作后到另一个处理器B能读到该写入数据之间的延迟时间。写更新协议的延迟时间较小。
|
||
|
||
### Slide 22-34：监听协议的实现
|
||
|
||
**Slide 22**
|
||
5.2.1 监听协议的实现
|
||
1. 监听协议的基本实现技术
|
||
实现监听协议的关键有3个方面
|
||
处理器之间通过一个可以实现广播的互连机制相连。
|
||
通常采用的是总线。
|
||
当一个处理器的Cache响应本地CPU的访问时，如果它涉及全局操作，其Cache控制器就要在获得总线的控制权后，在总线上发出相应的消息。
|
||
所有处理器都一直在监听总线，它们检测总线上的地址在它们的Cache中是否有副本。若有，则响应该消息，并进行相应的操作。
|
||
写操作的串行化：由总线实现
|
||
（获取总线控制权的顺序性）
|
||
|
||
**Slide 23**
|
||
CPU发出请求后的四种情况：
|
||
（1）本地能搞定 -- ReaddHit，WriteHit
|
||
（2）本地搞不定，需要发到总线上 -- ReadMiss，WriteMiss
|
||
|
||
3. 本地搞不定要干的事情。
|
||
（1）Cache发消息到总线上：
|
||
RdMiss——读不命中
|
||
WtMiss——写不命中
|
||
（2）需要通过总线找到相应数据块的最新副本，然后调入本地Cache中。
|
||
|
||
**Slide 24**
|
||
（3）有的监听协议还增设了一条Invalidate消息，用来通知其他各处理器作废其Cache中相应的副本。
|
||
与WtMiss的区别：Invalidate不引起调块
|
||
|
||
（4）Cache需要设置啥
|
||
Cache的标识（tag）可直接用来实现监听。
|
||
作废一个块只需将其有效位置为无效。
|
||
给每个Cache块增设一个共享位
|
||
为"1"：该块是被多个处理器所共享
|
||
为"0"：仅被某个处理器所独占
|
||
块的拥有者：拥有该数据块的唯一副本的处理器。
|
||
|
||
**Slide 25 - 监听协议举例**
|
||
4. 监听协议举例
|
||
在每个结点内嵌入一个有限状态控制器。
|
||
该控制器根据来自处理器或总线的请求以及Cache块的状态，做出相应的响应。
|
||
每个数据块的状态取以下3种状态中的一种：
|
||
无效（简称I）：Cache中该块的内容为无效。
|
||
共享（简称S）：该块可能处于共享状态。
|
||
在多个处理器中都有副本。这些副本都相同，且与存储器中相应的块相同。
|
||
已修改（简称M）：该块已经被修改过，并且还没写入存储器。
|
||
（块中的内容是最新的，系统中唯一的最新副本）
|
||
|
||
前提
|
||
写作废
|
||
写回法
|
||
原子操作
|
||
|
||
"已修改" 隐含表明该块是独占的（exclusive）
|
||
|
||
**Slide 26**
|
||
下面考虑两种情况：
|
||
Invalid
|
||
Shared
|
||
Modified
|
||
Invalid
|
||
Shared
|
||
Modified
|
||
I. 请求来自处理器
|
||
II. 请求来自总线
|
||
|
||
**Slide 27 - 34（状态转换图）**
|
||
I. 请求来自处理器 – 读命中
|
||
I. 请求来自处理器 – 读缺失
|
||
I. 请求来自处理器 – 写命中
|
||
I. 请求来自处理器 – 写缺失
|
||
II. 请求来自总线 – 读缺失
|
||
II. 请求来自总线 – 写缺失
|
||
II. 请求来自总线 – 失效
|
||
|
||
（以上为状态转换图，Slide 34-37内容为空）
|
||
|
||
### Slide 253-61：目录协议
|
||
|
||
**Slide 253 - 目录协议基本思想**
|
||
5.2.2 目录协议
|
||
广播和监听的机制使得监听一致性协议的可扩放性很差。
|
||
寻找替代监听协议的一致性协议。
|
||
（采用目录协议）
|
||
目录协议
|
||
目录：一种集中的数据结构。对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息。
|
||
特点：对于任何一个数据块，都可以快速地在唯一的一个位置中找到相关的信息。这使一致性协议避免了广播操作。
|
||
位向量：记录哪些Cache中有副本。
|
||
每一位对应于一个处理器。
|
||
长度与处理器的个数成正比。
|
||
由位向量指定的处理机的集合称为共享集S。
|
||
|
||
1. 目录协议基本思想
|
||
|
||
**Slide 254 - 分布式目录**
|
||
分布式目录
|
||
目录与存储器一起分布到各结点中，从而对于不同目录内容的访问可以在不同的结点进行。
|
||
对每个结点增加目录后的分布式存储器多处理机
|
||
|
||
**Slide 255 - 目录法实现**
|
||
目录法最简单的实现方案：对于存储器中每一块都在目录中设置一项。目录中的信息量与M×N成正比。
|
||
其中：
|
||
M：存储器中存储块的总数量
|
||
N：处理器的个数
|
||
由于M=K×N， K是每个处理机中存储块的数量。目录中的信息量即为K×N×N，所以如果K保持不变，则目录中的信息量就与N2成正比。
|
||
|
||
**Slide 256**
|
||
②本地结点、宿主结点以及远程结点的关系
|
||
本地结点：发出访问请求的结点；
|
||
宿主结点：包含所访问的存储单元及其目录项的结点；
|
||
远程结点：Cache中拥有该块的副本。
|
||
宿主结点：存放有对应地址的存储器块和目录项的结点
|
||
注意：统一地址空间，地址高位为节点地址，低位为节点内存储器偏移量。
|
||
可以是同一个节点
|
||
|
||
**Slide 257 - 目录协议实例**
|
||
在基于目录的协议中，目录承担了一致性协议操作的主要功能。
|
||
本地结点把请求消息发给宿主结点中的目录，再由目录控制器有选择地向远程结点发出相应的消息。
|
||
发出的消息会产生两种不同类型的动作：
|
||
更新目录状态
|
||
使远程结点完成相应的操作
|
||
某Cache的状态转换
|
||
三状态:Invalid，Shared，Modified
|
||
触发：CPU读请求，CPU写请求，远程Cache块收到请求
|
||
在目录协议中，存储块的状态有3种：
|
||
未缓冲（uncached）：该块尚未被调入Cache。所有处理器的Cache中都没有这个块的副本。
|
||
共享(shared)：该块在一个或多个处理机上有这个块的副本，且这些副本与存储器中的该块相同。
|
||
独占(exclusive)：仅有一个处理机有这个块的副本，且该处理机已经对其进行了写操作，所以其内容是最新的，而存储器中该块的数据已过时。这个处理机称为该块的拥有者。
|
||
|
||
2. 目录协议实例
|
||
|
||
**Slide 258 - 分析思路**
|
||
分析思路
|
||
本地节点（Cache）
|
||
宿主节点（存储块）
|
||
远程节点（Cache）
|
||
获得了什么信息？
|
||
来自哪？
|
||
现态是啥？
|
||
要干啥？
|
||
次态是啥？
|
||
在结点之间发送的消息
|
||
|
||
**Slide 259 - 本地节点操作**
|
||
本地节点（Cache）分析
|
||
操作解释：
|
||
读新：本地节点想要读一块新的。
|
||
写新：本地节点想要写一块新的。
|
||
废旧：本地节点告诉宿主我不要这块了，但是不需要写回。
|
||
写回并废旧：本地节点告诉宿主我不要这块了，但是需要写回。
|
||
让宿主废别人：让宿主把别人的块废了。
|
||
|
||
**Slide 260-261 - 消息定义**
|
||
本地结点发给宿主结点（目录）的消息定义
|
||
读新 -- RdMiss（P，K）
|
||
处理机P读取地址为K的数据时不命中，请求宿主结点提供数据（块），并要求把P加入共享集。
|
||
|
||
写新 -- WtMiss（P，K）
|
||
处理机P对地址K进行写入时不命中，请求宿主结点提供数据，并使P成为所访问数据块的独占者。
|
||
|
||
说明：括号中的内容表示所带参数。
|
||
P：发出请求的处理机编号
|
||
K：所要访问的地址
|
||
|
||
让宿主废别人 -- Invalidate（K）
|
||
请求向所有拥有相应数据块副本（包含地址K）的远程Cache发Invalidate消息，作废这些副本。
|
||
|
||
写回并废旧 -- WtBack2（P，K）
|
||
用于当本地Cache中需要替换一个包含地址K的块、且该块已被修改过的情况。这个消息发给该块的宿主结点，完成两步操作：①把该块写回；②进行与MdSharer相同的操作。
|
||
|
||
废旧 -- MdSharer（P，K）
|
||
用于当本地Cache中需要替换一个包含地址K的块、且该块未被修改过的情况。这个消息发给该块的宿主结点，请求它将P从共享集中删除。如果删除后共享集变为空集，则宿主结点还要将该块的状态改变为"未缓存"（U）。
|
||
|
||
**Slide 262 - 宿主节点操作**
|
||
宿主节点分析
|
||
Invalidate（K） 作废远程Cache中包含地址K的数据块。
|
||
Fetch（K） 从远程Cache中取出包含地址K的数据块，并将之送到宿主结点。把远程Cache中那个块的状态改为"共享"。
|
||
Fetch&Inv（K）从远程Cache中取出包含地址K的数据块，并将之送到宿主结点。然后作废远程Cache中的那个块。
|
||
DReply（D）宿主节点将存储器中的数据返回给本地Cache。
|
||
|
||
**Slide 263-265 - 状态转换**
|
||
存储块的状态转换 – 收到RdMiss(P，K)
|
||
存储块的状态转换 – 收到Wtmiss
|
||
存储块的状态转换 – 收到mdsharer,wtback2,invalidate
|
||
|
||
**Slide 266 - 远程节点**
|
||
远程节点分析（Cache）
|
||
WtBack（K,D） 把远程Cache中包含地址K的数据块写回到宿主结点中， 该消息是远程结点对宿主结点发来的"Fetch(K)"或"Fetch&Inv(k)"消息的响应。
|
||
|
||
远程Cache块收到请求
|
||
收到Invalidate消息
|
||
收到Fetch&Inv，发出 WtBack
|
||
收到Fetch，发出WtBack
|
||
|
||
**Slide 268 - 目录的三种结构**
|
||
消息定义综合
|
||
|
||
**Slide 269**
|
||
不同目录协议的主要区别主要有两个
|
||
所设置的存储器块的状态及其个数不同
|
||
目录的结构
|
||
目录协议分为3类
|
||
全映像目录
|
||
有限映像目录
|
||
链式目录
|
||
|
||
3. 目录的三种结构
|
||
|
||
**Slide 270 - 全映像目录**
|
||
全映像目录
|
||
每一个目录项都包含一个N位（N为处理机的个数）的位向量，其每一位对应于一个处理机。
|
||
优点：处理比较简单，速度也比较快。
|
||
缺点：
|
||
存储空间的开销很大。
|
||
目录项的数目与处理机的个数N成正比，而目录项的大小（位数）也与N成正比，因此目录所占用的空间与N2成正比。
|
||
可扩放性很差。
|
||
|
||
当位向量中的值为"1"时，就表示它所对应的处理机有该数据块的副本；否则就表示没有。
|
||
在这种情况下，共享集合由位向量中值为"1"的位所对应的处理机构成。
|
||
|
||
举例
|
||
|
||
**Slide 271 - 有限映像目录**
|
||
有限映像目录
|
||
提高其可扩放性和减少目录所占用的空间。
|
||
核心思想：采用位数固定的目录项目
|
||
限制同一数据块在所有Cache中的副本总数。
|
||
例如，限定为常数m。则目录项中用于表示共享集合所需的二进制位数为：m×log2N。
|
||
目录所占用的空间与N× 成正比。
|
||
缺点
|
||
当同一数据的副本个数大于m时，必须做特殊处理。当目录项中的m个指针都已经全被占满，而某处理机又需要新调入该块时，就需要在其m个指针中选择一个，将之驱逐，以便腾出位置，存放指向新调入块的处理机的指针 。
|
||
|
||
有限映像目录（m＝4，N≥8的情况）
|
||
举例
|
||
|
||
**Slide 272 - 链式目录**
|
||
链式目录
|
||
用一个目录指针链表来表示共享集合。当一个数据块的副本数增加（或减少）时，其指针链表就跟着变长（或变短）。
|
||
由于链表的长度不受限制，因而带来了以下优点：既不限制副本的个数，又保持了可扩展性。
|
||
链式目录有两种实现方法
|
||
单链法
|
||
当Cache中的块被替换出去时，需要对相应的链表进行操作——把相应的链表元素（假设是链表中的第i个）删除。实现方法有以下两种：
|
||
沿着链表往下寻找第i个元素，找到后，修改其前后的链接指针，跳过该元素。
|
||
找到第i个元素后，作废它及其后的所有元素所对应的Cache副本。
|
||
双链法
|
||
在替换时不需要遍历整个链表。
|
||
节省了处理时间，但其指针增加了一倍，而且一致性协议也更复杂了。
|
||
|
||
采用单向链法的示意图
|
||
共享集＝{ P2 }
|
||
共享集＝{ P1，P4，P2 }
|
||
|
||
---
|
||
|
||
## 李宏图（lht）
|
||
|
||
### Slide 1-4：计算机构成要素与系统互连
|
||
|
||
**Slide 1**
|
||
第5章 – 线程级并行：多处理机
|
||
|
||
**Slide 2**
|
||
点：包括小到CPU内部的寄存器、ALU、控制器，到存储模块、外设，乃至多处理机的计算节点，都可以视为点；
|
||
互连网络：按照一定拓扑结构和控制方式，将点连接起来。
|
||
|
||
1. 计算机构成的两个最基本的要素
|
||
|
||
**Slide 3**
|
||
系统互连
|
||
距离增加
|
||
单位时间信息量增加
|
||
|
||
**Slide 4**
|
||
静态互连网络：指处理单元间有固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变。
|
||
|
||
### Slide 5-14：MIMD并行机结构分类
|
||
|
||
**Slide 5**
|
||
动态互连网络：由开关单元构成，可以按照应用程序的要求动态的改变连接组态。
|
||
各种总线
|
||
交叉开关网络
|
||
多级互连网络
|
||
|
||
**Slide 6**
|
||
PVP，Parallel Vector Processor，并行向量处理机
|
||
SMP，Symmetric Multiprocessor，对称多处理机
|
||
MPP，Massively Parallel Processor，大规模并行处理机
|
||
DSM，Distributed Shared Memory，分布式共享存储多处理机
|
||
COW，Cluster of Workstations，工作站集群
|
||
|
||
2. 几种基本的MIMD并行机结构模型
|
||
|
||
**Slide 7 - PVP**
|
||
PVP——并行向量处理机
|
||
这样的系统中包含了少量的高性能专门设计定制的向量处理器 VP，每个至少具有１Ｇflops的处理能力；
|
||
存储器以兆字节每秒的速度向处理器提供数据。
|
||
向量处理器VP和共享存储模块通过高带宽的交叉开关网络互连；
|
||
这样的机器通常不使用高速缓存，而是使用大量的向量寄存器和指令缓冲器；
|
||
例如：Cray90、NECSX-4和我国的银河１号等都是 ＰＶＰ。
|
||
|
||
**Slide 8 - SMP**
|
||
ＳＭＰ——对称多处理机
|
||
ＳＭＰ系统使用商品微处理器（具有片上或外置高速缓存）；
|
||
它们经由高速总线（或交叉开关）连向共享存储器和I/O；
|
||
这种机器主要应用于商务，例如数据库、在线事务处理系统和数据仓库等；
|
||
重要的是系统是对称的，每个处理器可等同的访问共享存储器、Ｉ／Ｏ设备和操作系统服务。正是对称，才能开拓较高的并行度；也正是共享存储，限制系统中的处理器不能太多（一般少于６４个），同时总线和交叉开关互连一旦作成也难于扩展。
|
||
例如：IBM R50、SGI Power Challenge、DEC Alpha服务器8400和我国的曙光１号等都是这种类型的机器。
|
||
|
||
**Slide 9 - MPP**
|
||
ＭＰＰ——大规模并行处理机
|
||
ＭＰＰ一般是指超大型计算机系统；
|
||
处理节点采用商品微处理器；每个节点上有自己的局部存储器；采用高通信带宽和低延迟的互连网络（专门设计和定制的）进行节点互连；
|
||
能扩放至成百上千乃至上万个处理器；
|
||
它是一种异步的ＭＩＭＤ机器，程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息相互作用；
|
||
ＭＰＰ的主要应用是科学计算、工程模拟和信号处理等以计算为主的领域。
|
||
例如：Intel Paragon、Cray T3E、IntelOption Red和我国的曙光-1000等都是这种类型的机器。
|
||
|
||
**Slide 10 - DSM**
|
||
ＤＳＭ——分布式共享存储多处理机
|
||
物理上有分布在各节点中的局部存储器，但是对用户而言，系统硬件和软件提供了逻辑上单地址的编程空间。
|
||
高速缓存目录DIR用以支持分布高速缓存的一致性。
|
||
ＤＳＭ 相对于 ＭＰＰ的优越性是编程较容易。
|
||
例如：Stanford DASH、Cray T3D和SGI/Cray Origin 2000等。
|
||
|
||
**Slide 11 - COW**
|
||
ＣＯＷ——工作站集群
|
||
在有些情况下，机群往往是低成本的变形的ＭＰＰ;
|
||
ＣＯＷ 的重要界线和特征是：
|
||
①ＣＯＷ 的每个节点都是一个完整的工作站（不包括监视器、键盘、鼠标等），这样的节点有时叫作"无头工作站"，一个节点也可以是一台PC或SMP；
|
||
②各节点通过一种低成本的商品（标准）网络（如以太网、ＦＤＤＩ和 ＡＴＭ 开关等）互连（有的商用机群也使用定做的网络）；
|
||
③各节点内总是有本地磁盘，而 ＭＰＰ节点内却没有；
|
||
④节点内的网络接口是松散耦合到Ｉ／Ｏ 总线上的，而 ＭＰＰ内的网络接口是连到处理节点的存储总线上的，因而可谓是紧耦合式的；
|
||
⑤一个完整的操作系统驻留在每个节点中，而 ＭＰＰ中通常只是个微核，ＣＯＷ 的操作系统是工作站 ＵＮＩＸ，加上一个附加的软件层以支持单一系统映像、并行度、通信和负载平衡等。
|
||
Berkeley NOW、Alpha Farm、Digital Truclster等都是 ＣＯＷ 结构。
|
||
|
||
**Slide 12-13：从存储角度来看MIMD**
|
||
单地址空间共享存储
|
||
存储器可以是物理上集中的或者分布的，但是所有存储单元有统一的地址空间，并被所有的处理器所访问。
|
||
多地址空间非共享存储
|
||
所有的存储器都是私有的、仅能由其处理器所访问。
|
||
均匀存储访问
|
||
非均匀存储访问
|
||
3. 从存储角度来看MIMD
|
||
|
||
从存储结构的角度
|
||
单地址空间共享存储
|
||
多地址空间非共享存储
|
||
共享存储的访问
|
||
均匀存储访问——UMA（Uniform Memory Access）
|
||
非均匀存储访问——NUMA（Nonuniform Memory Access）
|
||
|
||
**Slide 14 - UMA**
|
||
UMA
|
||
物理存储器被所有处理器均匀共享；
|
||
所有处理器访问任何存储单元取相同时间
|
||
每台处理器课带私有高速缓存
|
||
外围设备也可以一定形式共享
|
||
|
||
**Slide 15 - NUMA**
|
||
NUMA
|
||
被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间
|
||
处理器访问存储器的时间是不一样的：访问本地存储器ＬＭ 或群内共享存储器ＣＳＭ 较快，而访问外地的存储器或全局共享存储器ＧＳＭ 较慢
|
||
每台处理器照例可带私有高速缓存，且外设也可以某种形式共享
|
||
|
||
### Slide 15-19：通信机制
|
||
|
||
**Slide 15**
|
||
共享存储器通信机制
|
||
共享地址空间的计算机系统采用
|
||
处理器之间是通过用load和store指令对相同存储器地址进行读/写操作来实现的。
|
||
消息传递通信机制
|
||
多个独立地址空间的计算机采用
|
||
通过处理器间显式地传递消息来完成
|
||
消息传递多处理机中，处理器之间是通过发送消息来进行通信的，这些消息请求进行某些操作或者传送数据。
|
||
|
||
**Slide 16 - 消息传递机制**
|
||
消息传递机制
|
||
例如：一个处理器要对远程存储器上的数据进行访问或操作：
|
||
发送消息，请求传递数据或对数据进行操作；
|
||
远程进程调用(RPC， Remote Process Call)
|
||
目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返回。
|
||
同步消息传递
|
||
请求处理器发送一个消息后一直要等到应答结果才继续运行。
|
||
异步消息传递
|
||
数据发送方知道别的处理器需要数据，通信也可以从数据发送方来开始，数据可以不经请求就直接送往数据接受方。
|
||
|
||
**Slide 17 - 共享存储器通信的主要优点**
|
||
共享存储器通信的主要优点
|
||
与常用的对称式多处理机使用的通信机制兼容。
|
||
易于编程，同时在简化编译器设计方面也占有优势。
|
||
采用大家所熟悉的共享存储器模型开发应用程序，而把重点放到解决对性能影响较大的数据访问上。
|
||
当通信数据量较小时，通信开销较低，带宽利用较好。
|
||
可以通过采用Cache技术来减少远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。
|
||
|
||
**Slide 18 - 消息传递通信机制的主要优点**
|
||
消息传递通信机制的主要优点
|
||
硬件较简单。
|
||
通信是显式的，因此更容易搞清楚何时发生通信以及通信开销是多少。
|
||
显式通信可以让编程者重点注意并行计算的主要通信开销，使之有可能开发出结构更好、性能更高的并行程序。
|
||
同步很自然地与发送消息相关联，能减少不当的同步带来错误的可能性。
|
||
|
||
**Slide 19**
|
||
消息传递机制
|
||
可在支持上面任何一种通信机制的硬件模型上建立所需的通信模式平台。
|
||
在共享存储器上支持消息传递相对简单。
|
||
在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，即将存储器访问转换为消息的发送和接收。
|
||
|
||
### Slide 31-38：并行处理面临的挑战与性能评测
|
||
|
||
**Slide 31**
|
||
并行处理面临的挑战
|
||
并行处理面临着两个重要的挑战
|
||
程序中的并行性有限
|
||
相对较大的通信开销
|
||
|
||
系统加速比 =
|
||
|
||
**Slide 32 - 第一个挑战**
|
||
第一个挑战
|
||
有限的并行性使计算机要达到很高的加速比十分困难。
|
||
例： 假设想用100个处理器达到80的加速比，求原计算程序中串行部分最多可占多大的比例？
|
||
|
||
解 Amdahl定律为：
|
||
|
||
由上式可得：并行比例＝0.9975
|
||
|
||
**Slide 33 - 第二个挑战**
|
||
第二个挑战
|
||
多处理机中远程访问的延迟较大
|
||
在现有的机器中，处理器之间的数据通信大约需要50～1000个时钟周期。
|
||
主要取决于：
|
||
通信机制、互连网络的种类和机器的规模
|
||
|
||
**Slide 34 - 例题**
|
||
例题
|
||
假设有一台32台处理器的多处理机，对远程存储器访问时间为200ns。除了通信以外，假设所有其他访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器的时钟频率为2GHz，如果指令基本的CPI为0.5（设所有访存均命中Cache），求在没有远程访问的情况下和有0.2%的指令需要远程访问的情况下，前者比后者快多少?
|
||
|
||
**Slide 35 - 例题解答**
|
||
例题
|
||
解 有0.2%远程访问的机器的实际CPI为：
|
||
CPI＝基本CPI＋远程访问率×远程访问开销
|
||
＝0.5＋0.2%×远程访问开销
|
||
远程访问开销为：
|
||
远程访问时间/时钟周期时间＝200ns/0.5ns＝400个时钟周期
|
||
∴ CPI＝0.5＋0.2%×400＝1.3
|
||
因此在没有远程访问的情况下的机器速度是有0.2%远程访问的机器速度的1.3/0.5=2.6倍。
|
||
|
||
**Slide 36 - 问题的解决**
|
||
问题的解决
|
||
并行性不足： 采用并行性更好的算法
|
||
远程访问延迟的降低：靠系统结构支持和编程技术
|
||
|
||
**Slide 37 - 影响性能的因素**
|
||
影响性能的因素
|
||
在并行处理中，影响性能（负载平衡、同步和存储器访问延迟等）的关键因素常依赖于：
|
||
应用程序的高层特性
|
||
如数据的分配，并行算法的结构以及在空间和时间上对数据的访问模式等。
|
||
依据应用特点可把多机工作负载大致分成两类：
|
||
单个程序在多处理机上的并行工作负载
|
||
多个程序在多处理机上的并行工作负载
|
||
|
||
**Slide 38 - 并行程序的计算／通信比率**
|
||
并行程序的计算／通信比率
|
||
反映并行程序性能的一个重要的度量：
|
||
计算与通信的比率
|
||
计算／通信比率随着处理数据规模的增大而增加；随着处理器数目的增加而减少。
|
||
|
||
### Slide 40-67：Cache一致性
|
||
|
||
**Slide 40 - 对称式共享存储器系统结构**
|
||
对称式共享存储器系统结构
|
||
多个处理器共享一个存储器。
|
||
当处理机规模较小时，这种计算机十分经济。
|
||
近些年，能在一个单独的芯片上实现2～8个处理器核。
|
||
例如：Sun公司 2006年 T1 8核的多处理器
|
||
支持对共享数据和私有数据的Cache缓存
|
||
私有数据供一个单独的处理器使用，而共享数据则是供多个处理器使用。
|
||
共享数据进入Cache产生了一个新的问题
|
||
Cache的一致性问题
|
||
|
||
**Slide 41**
|
||
Cache一致性
|
||
多处理机的Cache一致性问题
|
||
允许共享数据进入Cache，就可能出现多个处理器的Cache中都有同一存储块的副本，
|
||
当其中某个处理器对其Cache中的数据进行修改后，就会使得其Cache中的数据与其他Cache中的数据不一致。
|
||
|
||
**Slide 42**
|
||
例如：
|
||
由两个处理器（A和B）读写引起的Cache一致性问题
|
||
|
||
**Slide 43 - 存储器的一致性**
|
||
存储器的一致性
|
||
如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。
|
||
存储系统行为的两个不同方面
|
||
What: 读操作得到的是什么值
|
||
When: 什么时候才能将已写入的值返回给读操作
|
||
需要满足以下条件
|
||
处理器P对单元X进行一次写之后又对单元X进行读，读和写之间没有其他处理器对单元X进行写，则P读到的值总是前面写进去的值。
|
||
处理器P对单元X进行写之后，另一处理器Q对单元X进行读，读和写之间无其他写，则Q读到的值应为P写进去的值。
|
||
对同一单元的写是串行化的，即任意两个处理器对同一单元的两次写，从各个处理器的角度看来顺序都是相同的。(写串行化 )
|
||
|
||
**Slide 44**
|
||
在后面的讨论中，我们假设：
|
||
直到所有的处理器均看到了写的结果，这个写操作才算完成；
|
||
处理器的任何访存均不能改变写的顺序。就是说，允许处理器对读进行重排序，但必须以程序规定的顺序进行写。
|
||
|
||
**Slide 45 - 实现一致性的基本方案**
|
||
实现一致性的基本方案
|
||
在一致的多处理机中，Cache提供两种功能：
|
||
共享数据的迁移
|
||
减少了对远程共享数据的访问延迟，也减少了对共享存储器带宽的要求。
|
||
共享数据的复制
|
||
不仅减少了访问共享数据的延迟，也减少了访问共享数据所产生的冲突。
|
||
|
||
一般情况下，小规模多处理机是采用硬件的方法来实现Cache的一致性。
|
||
|
||
**Slide 46 - Cache一致性协议**
|
||
Cache一致性协议
|
||
在多个处理器中用来维护一致性的协议。
|
||
关键：跟踪记录共享数据块的状态
|
||
两类协议（采用不同的技术跟踪共享数据的状态）
|
||
目录式协议（directory）
|
||
物理存储器中数据块的共享状态被保存在一个称为目录的地方。
|
||
监听式协议（snooping）
|
||
每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。
|
||
Cache通常连在共享存储器的总线上，当某个Cache需要访问存储器时，它会把请求放到总线上广播出去，其他各个Cache控制器通过监听总线（它们一直在监听）来判断它们是否有总线上请求的数据块。如果有，就进行相应的操作。
|
||
|
||
**Slide 47 - 两种解决Cache一致性问题的方法**
|
||
两种解决Cache一致性问题的方法
|
||
写作废协议：
|
||
在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权。(作废其他的副本)
|
||
写更新协议：
|
||
当一个处理器对某数据项进行写入时，通过广播使其他Cache中所有对应于该数据项的副本进行更新。
|
||
|
||
**Slide 48 - 写作废协议**
|
||
写作废协议
|
||
例 监听总线、写作废协议举例（采用写直达法）
|
||
初始状态：CPU A、CPU B、CPU C都有X的副本。在CPU A要对X进行写入时，需先作废CPU B和CPU C中的副本，然后再将p写入Cache A中的副本，同时用该数据更新主存单元X。
|
||
|
||
**Slide 49 - 写更新协议**
|
||
写更新协议
|
||
例 监听总线、写更新协议举例（采用写直达法）
|
||
假设：3个Cache都有X的副本。当CPU A将数据p写入Cache A中的副本时，将p广播给所有的Cache，这些Cache用p更新其中的副本。由于这里是采用写直达法，所以CPU A还要将p写入存储器中的X。如果采用写回法，则不需要写入存储器。
|
||
|
||
**Slide 50 - 性能差别**
|
||
性能差别
|
||
写更新和写作废协议性能上的差别主要来自：
|
||
在对同一个数据进行多次写操作而中间无读操作的情况下，写更新协议需进行多次写广播操作，而写作废协议只需一次作废操作。
|
||
在对同一Cache块的多个字进行写操作的情况下，写更新协议对于每一个写操作都要进行一次广播，而写作废协议仅在对该块的第一次写时进行作废操作即可。
|
||
写作废是针对Cache块进行操作，而写更新则是针对字（或字节）进行。
|
||
考虑从一个处理器A进行写操作后到另一个处理器B能读到该写入数据之间的延迟时间: 写更新协议的延迟时间较小。
|
||
|
||
### Slide 52-67：监听协议实现与MSI/MESI/MOSI协议
|
||
|
||
**Slide 52 - 监听协议的实现**
|
||
监听协议的实现
|
||
监听协议的基本实现技术
|
||
实现监听协议的关键有3个方面
|
||
处理器之间通过一个可以实现广播的互连机制相连。
|
||
通常采用的是总线。
|
||
当一个处理器的Cache响应本地CPU的访问时，如果它涉及全局操作，其Cache控制器就要在获得总线的控制权后，在总线上发出相应的消息。
|
||
所有处理器都一直在监听总线，它们检测总线上的地址在它们的Cache中是否有副本。若有，则响应该消息，并进行相应的操作 。
|
||
写操作的串行化：由总线实现
|
||
（获取总线控制权的顺序性）
|
||
|
||
**Slide 53 - Cache发送到总线上的消息**
|
||
监听协议的实现
|
||
Cache发送到总线上的消息主要有以下两种：
|
||
RdMiss——读不命中
|
||
WtMiss——写不命中
|
||
需要通过总线找到相应数据块的最新副本，然后调入本地Cache中。
|
||
写直达Cache：因为所有写入的数据都同时被写回主存，所以从主存中总可以取到其最新值。
|
||
对于写回Cache，得到数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在主存中。
|
||
（后面的讨论中，只考虑写回法Cache）
|
||
|
||
**Slide 54 - 监听协议实现**
|
||
监听协议的实现
|
||
有的监听协议还增设了一条Invalidate消息，用来通知其他各处理器作废其Cache中相应的副本。
|
||
与WtMiss的区别：Invalidate不引起调块
|
||
Cache的标识（tag）可直接用来实现监听。
|
||
作废一个块只需将其有效位置为无效。
|
||
给每个Cache块增设一个共享位
|
||
为"1"：该块是被多个处理器所共享
|
||
为"0"：仅被某个处理器所独占
|
||
块的拥有者：拥有该数据块的唯一副本的处理器。
|
||
|
||
**Slide 55 - MSI监听协议**
|
||
MSI监听协议
|
||
在每个结点内嵌入一个有限状态控制器。
|
||
该控制器根据来自处理器或总线的请求以及Cache块的状态，做出相应的响应。
|
||
每个数据块的状态取以下3种状态中的一种：
|
||
无效（简称I）：Cache中该块的内容为无效。
|
||
共享（简称S）：该块可能处于共享状态。
|
||
在多个处理器中都有副本。这些副本都相同，且与存储器中相应的块相同。
|
||
已修改（简称M）：该块已经被修改过，并且还没写入存储器。
|
||
（块中的内容是最新的，系统中唯一的最新副本）
|
||
|
||
"已修改" 隐含表明该块是独占的（exclusive）
|
||
|
||
**Slide 56 - 两种请求来源**
|
||
考虑两种情况：
|
||
Invalid
|
||
Shared
|
||
Modified
|
||
Invalid
|
||
Shared
|
||
Modified
|
||
I. 请求来自处理器
|
||
II. 请求来自总线
|
||
Invalidate
|
||
Invalidate
|
||
|
||
**Slide 57-67 - MSI状态转换**
|
||
I. 请求来自处理器 – 读命中
|
||
I. 请求来自处理器 – 读缺失
|
||
I. 请求来自处理器 – 写命中
|
||
I. 请求来自处理器 – 写缺失
|
||
II. 请求来自总线 – 读缺失
|
||
II. 请求来自总线 – 失效
|
||
II. 请求来自总线 – 写缺失
|
||
|
||
（以上为MSI协议状态转换图）
|
||
|
||
**Slide 68 - 基本MSI协议存在的问题**
|
||
基本MSI协议存在的问题
|
||
并发问题:
|
||
MSI协议假定操具有原子性：在完成一项操作的过程中，不会发生任何中间操作
|
||
例如：检测缺失，获取总线，接收响应
|
||
造成死锁和竞争的可能性
|
||
一个解决方案是：发送invalidate的处理器可以占用总线，直到其他处理器收到invalidate
|
||
问题：
|
||
一个块从一开始就不在缓存中
|
||
在读取时，块立即进入"共享"状态，尽管它可能是唯一被缓存的副本(也就是说，没有其他处理器会缓存它)
|
||
想法:
|
||
添加另一个状态，表明这是唯一的缓存副本，并且它是干净的。
|
||
|
||
**Slide 69 - MESI协议**
|
||
MESI协议
|
||
添加独占状态，表示只有一个缓存中的干净块
|
||
防止在写操作时需要写invalidate
|
||
|
||
从单一所有者状态(独占或修改)到共享状态的转换称为降级，因为这种转换剥夺了所有者修改数据的权利
|
||
从共享到单者状态(Exclusive或Modified)的转换称为升级，因为转换授予所有者(包含相应块的缓存)写入块的能力。
|
||
|
||
**Slide 70 - MESI协议状态转换**
|
||
MESI协议状态转换图
|
||
PrWr/BusRdX, PrRd (S')/BusRd, PrRd (S)/BusRd, PrWr/BusRdX, PrWr/--, BusRd/ $ Transfer, BusRd/Flush, BusRdX/Flush (all incoming)
|
||
M, E, S, I 状态
|
||
|
||
**Slide 71 - MESI降级选择**
|
||
从M降级到S还是I?
|
||
S:如果数据可能被重用(在它被另一个处理器写入之前)
|
||
I:如果数据很可能不会被重用(在它被另一个写入之前)
|
||
Cache-to-cache转移
|
||
在BusRd上，数据应该来自另一个缓存还是内存?
|
||
另一个缓存
|
||
可能会更快，如果内存很慢或高度竞争
|
||
存储器
|
||
更简单:不需要等着看另一个缓存是否先有数据
|
||
减少其他缓存的争用
|
||
要求M降级时写回
|
||
"修改"->"共享"转换时写回是否有必要?
|
||
一种可能性:所有者(O)状态(MOESI协议)
|
||
一个缓存拥有最新的数据(内存不更新)。
|
||
当所有缓存退出副本时，内存回写发生
|
||
|
||
**Slide 72**
|
||
观察：共享状态要求数据是干净的，也就是说，所有有块的缓存都有最新的副本，存储器也是如此
|
||
问题：当块处于修改状态时，当BusRd发生时需要将块写入内存
|
||
|
||
想法1：BusRd时不要从M过渡到S。将该副本作废，并将修改后的块直接提供给请求处理器，而不更新内存
|
||
想法2：从M过渡到S，但指定一个缓存作为所有者(O)，当块被撤销时，由O写回块
|
||
"共享"的意思是"共享且可能脏"
|
||
这是MOESI协议的一个版本
|
||
|
||
**Slide 73 - MOESI协议**
|
||
MOESI协议
|
||
增加拥有（Owned）状态，表示相关块由该缓存拥有，在存储器中已经过时。
|
||
MSI和MESI如果尝试共享处于"已修改"状态的块，会将其改为"共享"状态（原共享缓存和新共享缓存中都会作此修改），必须将这个块写回存储器中。
|
||
MOESI协议中，会在原缓存中将这个块的状态由"已修改"改为"拥有"，不再将其写到存储器中。
|
||
新共享这个块的其他缓存使这个块保持共享状态，只有原缓存保持"拥有"状态，表示主存副本已过期，指定缓存成为其拥有者。
|
||
拥有者需要在发生缺失时提供该块，如果替换，须将其写回存储器。
|
||
|
||
### Slide 76-97：目录协议
|
||
|
||
**Slide 76 - 目录协议基本思想**
|
||
分布式共享存储器系统结构
|
||
目录协议的基本思想
|
||
广播和监听的机制使得监听一致性协议的可扩展性很差。
|
||
寻找替代监听协议的一致性协议。
|
||
（采用目录协议）
|
||
|
||
**Slide 77 - 目录协议**
|
||
目录协议
|
||
目录：一种集中的数据结构。对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息。
|
||
特点：对于任何一个数据块，都可以快速地在唯一的一个位置中找到相关的信息。这使一致性协议避免了广播操作。
|
||
位向量：记录哪些Cache中有副本。
|
||
每一位对应于一个处理器。
|
||
长度与处理器的个数成正比。
|
||
由位向量指定的处理机的集合称为共享集S。
|
||
分布式目录
|
||
目录与存储器一起分布到各结点中，从而对于不同目录内容的访问可以在不同的结点进行。
|
||
|
||
**Slide 79 - 目录法实现方案**
|
||
目录法最简单的实现方案
|
||
对于存储器中每一块都在目录中设置一项。目录中的信息量与M×N成正比。
|
||
其中：
|
||
M：存储器中存储块的总数量
|
||
N：处理器的个数
|
||
由于M=K×N， K是每个处理机中存储块的数量，所以如果K保持不变，则目录中的信息量就与N2成正比。
|
||
|
||
**Slide 80 - 本地结点、宿主结点以及远程结点的关系**
|
||
本地结点、宿主结点以及远程结点的关系
|
||
本地结点：发出访问请求的结点
|
||
宿主结点：包含所访问的存储单元及其目录项的结点
|
||
远程结点可以和宿主结点是同一个结点，也可以不是同一个结点。
|
||
宿主结点：存放有对应地址的存储器块和目录项的结点
|
||
|
||
**Slide 81-84 - 消息定义**
|
||
在结点之间发送的消息
|
||
本地结点发给宿主结点（目录）的消息
|
||
说明：括号中的内容表示所带参数。
|
||
P：发出请求的处理机编号
|
||
K：所要访问的地址
|
||
|
||
RdMiss（P，K）
|
||
处理机P读取地址为K的数据时不命中，请求宿主结点提供数据（块），并要求把P加入共享集。
|
||
|
||
WtMiss（P，K）
|
||
处理机P对地址K进行写入时不命中，请求宿主结点提供数据，并使P成为所访问数据块的独占者。
|
||
|
||
Invalidate（K）
|
||
请求向所有拥有相应数据块副本（包含地址K）的远程Cache发Invalidate消息，作废这些副本。
|
||
|
||
宿主结点（目录）发送给远程结点的消息
|
||
Invalidate（K）
|
||
作废远程Cache中包含地址K的数据块。
|
||
Fetch（K）
|
||
从远程Cache中取出包含地址K的数据块，并将之送到宿主结点。把远程Cache中那个块的状态改为"共享"。
|
||
Fetch&Inv（K）
|
||
从远程Cache中取出包含地址K的数据块，并将之送到宿主结点。然后作废远程Cache中的那个块。
|
||
|
||
宿主结点发送给本地结点的消息
|
||
DReply（D）
|
||
D表示数据内容。
|
||
把从宿主存储器获得的数据返回给本地Cache。
|
||
|
||
远程结点发送给宿主结点的消息
|
||
WtBack（K，D）
|
||
把远程Cache中包含地址K的数据块写回到宿主结点中， 该消息是远程结点对宿主结点发来的"取数据"或"取/作废"消息的响应。
|
||
|
||
本地结点发送给被替换块的宿主结点的消息
|
||
MdSharer（P，K）
|
||
用于当本地Cache中需要替换一个包含地址K的块、且该块未被修改过的情况。这个消息发给该块的宿主结点，请求它将P从共享集中删除。如果删除后共享集变为空集，则宿主结点还要将该块的状态改变为"未缓存"（U）。
|
||
WtBack2（P，K，D）
|
||
用于当本地Cache中需要替换一个包含地址K的块、且该块已被修改过的情况。这个消息发给该块的宿主结点，完成两步操作：①把该块写回；②进行与MdSharer相同的操作。
|
||
|
||
**Slide 86 - 目录协议实例**
|
||
目录协议实例
|
||
在基于目录的协议中，目录承担了一致性协议操作的主要功能。
|
||
本地结点把请求发给宿主结点中的目录，再由目录控制器有选择地向远程结点发出相应的消息。
|
||
发出的消息会产生两种不同类型的动作：
|
||
更新目录状态
|
||
使远程结点完成相应的操作
|
||
|
||
**Slide 87 - 存储块的状态**
|
||
在目录协议中，存储块的状态有3种：
|
||
未缓冲：该块尚未被调入Cache。所有处理器的Cache中都没有这个块的副本。
|
||
共享：该块在一个或多个处理机上有这个块的副本，且这些副本与存储器中的该块相同。
|
||
独占：仅有一个处理机有这个块的副本，且该处理机已经对其进行了写操作，所以其内容是最新的，而存储器中该块的数据已过时。
|
||
这个处理机称为该块的拥有者。
|
||
|
||
**Slide 88 - 目录的状态转换及相应的操作**
|
||
目录的状态转换及相应的操作
|
||
对于从本地结点发来的请求，目录所进行的操作包括：
|
||
向远程结点发送消息以完成相应的操作。这些远程结点由共享集合指出；
|
||
修改目录中该块的状态；
|
||
更新共享集合。
|
||
目录可能接收到5种不同的请求
|
||
读不命中 （针对请求数据）
|
||
写不命中（针对请求数据）
|
||
作废（写命中时）（针对请求数据）
|
||
从共享集合中删除（针对替换数据）
|
||
本地数据写回（针对替换数据）
|
||
（假设这些操作是原子的）
|
||
|
||
**Slide 99-101 - 目录状态转换详细**
|
||
当一个块处于未缓存状态时，对该块发出的请求及处理操作为：
|
||
RdMiss（读不命中）
|
||
将所要访问的存储器数据送往请求方处理机，且该处理机成为该块的唯一共享结点，本块的状态变成共享。
|
||
WtMiss（写不命中）
|
||
将所要访问的存储器数据送往请求方处理机，该块的状态变成独占，表示该块仅存在唯一的副本。其共享集合仅包含该处理机，指出该处理机是其拥有者。
|
||
|
||
当一个块处于共享状态时，其在存储器中的数据是当前最新的，对该块发出的请求及其处理操作为：
|
||
RdMiss
|
||
将存储器数据送往请求方处理机，并将其加入共享集合。
|
||
WtMiss
|
||
将数据送往请求方处理机，对共享集合中所有的处理机发送作废消息，且将共享集合改为仅含有该处理机，该块的状态变为独占。
|
||
Invalidate
|
||
对共享集合中除请求方以外的所有的处理机发送作废消息，且将共享集合改为仅含有该处理机，该块的状态变为独占。
|
||
MdSharer
|
||
将请求方处理机从共享集合中删除，如果共享集合变为空，该块的状态变为未缓冲。
|
||
|
||
当某块处于独占状态时，该块的最新值保存在共享集合所指出的唯一处理机（拥有者）中。 有三种可能的请求：
|
||
RdMiss
|
||
将"取数据"的消息发往拥有者处理机，将它所返回给宿主结点的数据写入存储器，并进而把该数据送回请求方处理机，将请求方处理机加入共享集合。
|
||
此时共享集合中仍保留原拥有者处理机（因为它仍有一个可读的副本）。
|
||
将该块的状态变为共享。
|
||
WtMiss
|
||
该块将有一个新的拥有者。
|
||
给旧的拥有者处理机发送消息，要求它将数据块送回宿主结点写入存储器，然后再从该结点送给请求方处理机。
|
||
同时还要把旧拥有者处理机中的该块作废。把请求处理机加入共享者集合，使之成为新的拥有者。
|
||
该块的状态仍旧是独占。
|
||
WtBack2（写回）
|
||
当一个块的拥有者处理机要从其Cache中把该块替换出去时，必须将该块写回其宿主结点的存储器中，从而使存储器中相应的块中存放的数据是最新的（宿主结点实际上成为拥有者）；
|
||
该块的状态变成未缓冲，其共享集合为空。
|
||
|
||
### Slide 91-97：目录的三种结构
|
||
|
||
**Slide 91**
|
||
不同目录协议的主要区别主要有两个
|
||
所设置的存储器块的状态及其个数不同
|
||
目录的结构
|
||
目录协议分为3类
|
||
全映像目录
|
||
有限映像目录
|
||
链式目录
|
||
|
||
3. 目录的三种结构
|
||
|
||
**Slide 92 - 全映像目录**
|
||
全映像目录
|
||
每一个目录项都包含一个N位（N为处理机的个数）的位向量，其每一位对应于一个处理机。
|
||
优点：处理比较简单，速度也比较快。
|
||
缺点：
|
||
存储空间的开销很大。
|
||
目录项的数目与处理机的个数N成正比，而目录项的大小（位数）也与N成正比，因此目录所占用的空间与N2成正比。
|
||
可扩放性很差。
|
||
|
||
当位向量中的值为"1"时，就表示它所对应的处理机有该数据块的副本；否则就表示没有。
|
||
在这种情况下，共享集合由位向量中值为"1"的位所对应的处理机构成。
|
||
|
||
**Slide 94 - 有限映像目录**
|
||
有限映像目录
|
||
提高其可扩放性和减少目录所占用的空间。
|
||
核心思想：采用位数固定的目录项目
|
||
限制同一数据块在所有Cache中的副本总数。
|
||
例如，限定为常数m。则目录项中用于表示共享集合所需的二进制位数为：m×log2N。
|
||
目录所占用的空间与N× 成正比。
|
||
缺点
|
||
当同一数据的副本个数大于m时，必须做特殊处理。当目录项中的m个指针都已经全被占满，而某处理机又需要新调入该块时，就需要在其m个指针中选择一个，将之驱逐，以便腾出位置，存放指向新调入块的处理机的指针。
|
||
|
||
**Slide 95**
|
||
有限映像目录（m＝4，N≥8的情况）
|
||
举例
|
||
|
||
**Slide 96 - 链式目录**
|
||
链式目录
|
||
用一个目录指针链表来表示共享集合。当一个数据块的副本数增加（或减少）时，其指针链表就跟着变长（或变短）。
|
||
由于链表的长度不受限制，因而带来了以下优点：既不限制副本的个数，又保持了可扩展性。
|
||
链式目录有两种实现方法
|
||
单链法
|
||
当Cache中的块被替换出去时，需要对相应的链表进行操作——把相应的链表元素（假设是链表中的第i个）删除。实现方法有以下两种：
|
||
沿着链表往下寻找第i个元素，找到后，修改其前后的链接指针，跳过该元素。
|
||
找到第i个元素后，作废它及其后的所有元素所对应的Cache副本。
|
||
双链法
|
||
在替换时不需要遍历整个链表。
|
||
节省了处理时间，但其指针增加了一倍，而且一致性协议也更复杂了。
|
||
|
||
**Slide 97**
|
||
采用单向链法的示意图
|
||
共享集＝{ P2 }
|
||
共享集＝{ P1，P4，P2 }
|
||
|
||
---
|
||
|
||
## 谭婧炜佳（tjwj）
|
||
|
||
### Slide 1-3：本章内容
|
||
|
||
**Slide 1**
|
||
计算机系统结构第5章 线程级并行
|
||
授课教师：谭婧炜佳
|
||
jtan@jlu.edu.cn
|
||
|
||
**Slide 2**
|
||
本章内容
|
||
多处理机概述
|
||
分类
|
||
性能评测
|
||
Cache一致性
|
||
一致性问题
|
||
监听式协议
|
||
目录式协议
|
||
|
||
### Slide 4-14：多处理器背景与分类
|
||
|
||
**Slide 4 - 摩尔定律**
|
||
摩尔定律
|
||
单位面积的晶体管数量每两年增加一倍。
|
||
|
||
**Slide 6 - 从单处理器到多处理器**
|
||
从单处理器到多处理器
|
||
自20世纪50年代末、60年代初出现第一批晶体管计算机以来，单处理器性能的增长速度在1986年至2003年期间达到最高峰。
|
||
之后，摩尔定律放缓，豋纳德缩放比例定律失效
|
||
2004年，Intel公司宣布放弃高性能单处理器项目，转向多核的研发。
|
||
2006年开始，功耗墙问题导致处理器频率极限约为4GHz。
|
||
|
||
**Slide 7 - 多处理器的分类**
|
||
多处理器的分类
|
||
MIMD已成为通用多处理机系统结构的选择，原因：
|
||
MIMD具有灵活性；
|
||
MIMD可以充分利用商品化微处理器在性能价格比方面的优势。
|
||
根据存储器的组织结构 ，把现有的MIMD机器分为两类：
|
||
集中式共享存储器结构
|
||
分布式存储器多处理机
|
||
|
||
**Slide 8 - 集中式共享存储器结构**
|
||
集中式共享存储器结构
|
||
最多由几十个处理器构成。
|
||
各处理器共享一个集中式的物理存储器。
|
||
|
||
**Slide 9**
|
||
集中式共享存储器结构
|
||
这类机器有时被称为
|
||
SMP机器（Symmetric shared-memory MultiProcessor）对称多处理器
|
||
对称：所有处理器都能够平等的访问存储器
|
||
现有的多核心芯片都是SMP
|
||
UMA机器（Uniform Memory Access） 一致存储器访问
|
||
一致：所有处理器访问存储器的延迟都是一致的
|
||
|
||
**Slide 10-11 - 分布式存储器多处理机**
|
||
分布式存储器多处理机
|
||
存储器在物理上是分布的。
|
||
每个结点包含：
|
||
处理器
|
||
存储器
|
||
I／O
|
||
互连网络接口
|
||
在许多情况下，分布式 存储器结构优于集中式 共享存储器结构。
|
||
|
||
分布式存储器多处理机
|
||
将存储器分布到各结点有两个优点
|
||
如果大多数的访问是针对本结点的局部存储器，则可降低对存储器和互连网络的带宽要求；
|
||
对本地存储器的访问延迟时间小。
|
||
最主要的缺点
|
||
处理器之间的通信较为复杂，且各处理器之间访问延迟较大。
|
||
簇：超级结点
|
||
每个结点内包含个数较少（例如2～8）的处理器；
|
||
处理器之间可采用另一种互连技术（例如总线）相互连接形成簇。
|
||
|
||
**Slide 12-14 - 存储器系统结构**
|
||
存储器系统结构
|
||
大规模多处理机中存储器在物理上分布在各个处理节点中，但是在逻辑地址空间的组织方式及处理器之间通信的实现方法上，有两种方案：
|
||
共享地址空间
|
||
独立地址空间
|
||
|
||
共享地址空间
|
||
物理上分离的所有存储器作为一个统一的共享逻辑空间进行编址。
|
||
任何一个处理器可以访问该共享空间中的任何一个单元（如果它具有访问权），而且不同处理器上的同一个物理地址指向的是同一个存储单元。
|
||
这类计算机被称为
|
||
分布式共享存储器系统 （DSM: Distributed Shared-Memory)
|
||
NUMA机器 （NUMA: Non-Uniform Memory Access)
|
||
|
||
独立地址空间
|
||
把每个结点中的存储器编址为一个独立的地址空间，不同结点中的地址空间之间是相互独立的。
|
||
整个系统的地址空间由多个独立的地址空间构成
|
||
每个结点中的存储器只能由本地 的处理器进行访问，远程的处理 器不能直接对其进行访问。
|
||
每一个处理器-存储器模块实际 上是一台单独的计算机
|
||
现在这种机器多以集群的形式存在
|
||
|
||
### Slide 15-19：通信机制
|
||
|
||
**Slide 15**
|
||
通信机制
|
||
共享存储器通信机制
|
||
共享地址空间的计算机系统采用
|
||
处理器之间是通过用load和store指令对相同存储器地址进行读/写操作来实现的。
|
||
消息传递通信机制
|
||
多个独立地址空间的计算机采用
|
||
通过处理器间显式地传递消息来完成
|
||
消息传递多处理机中，处理器之间是通过发送消息来进行通信的，这些消息请求进行某些操作或者传送数据。
|
||
|
||
**Slide 16 - 消息传递机制**
|
||
消息传递机制
|
||
例如：一个处理器要对远程存储器上的数据进行访问或操作：
|
||
发送消息，请求传递数据或对数据进行操作；
|
||
远程进程调用(RPC， Remote Process Call)
|
||
目的处理器接收到消息以后，执行相应的操作或代替远程处理器进行访问，并发送一个应答消息将结果返回。
|
||
同步消息传递
|
||
请求处理器发送一个消息后一直要等到应答结果才继续运行。
|
||
异步消息传递
|
||
数据发送方知道别的处理器需要数据，通信也可以从数据发送方来开始，数据可以不经请求就直接送往数据接受方。
|
||
|
||
**Slide 17 - 共享存储器通信的主要优点**
|
||
共享存储器通信的主要优点
|
||
与常用的对称式多处理机使用的通信机制兼容。
|
||
易于编程，同时在简化编译器设计方面也占有优势。
|
||
采用大家所熟悉的共享存储器模型开发应用程序，而把重点放到解决对性能影响较大的数据访问上。
|
||
当通信数据量较小时，通信开销较低，带宽利用较好。
|
||
可以通过采用Cache技术来减少远程通信的频度，减少了通信延迟以及对共享数据的访问冲突。
|
||
|
||
**Slide 18 - 消息传递通信机制的主要优点**
|
||
消息传递通信机制的主要优点
|
||
硬件较简单。
|
||
通信是显式的，因此更容易搞清楚何时发生通信以及通信开销是多少。
|
||
显式通信可以让编程者重点注意并行计算的主要通信开销，使之有可能开发出结构更好、性能更高的并行程序。
|
||
同步很自然地与发送消息相关联，能减少不当的同步带来错误的可能性。
|
||
|
||
**Slide 19**
|
||
消息传递机制
|
||
可在支持上面任何一种通信机制的硬件模型上建立所需的通信模式平台。
|
||
在共享存储器上支持消息传递相对简单。
|
||
在消息传递的硬件上支持共享存储器就困难得多。所有对共享存储器的访问均要求操作系统提供地址转换和存储保护功能，即将存储器访问转换为消息的发送和接收。
|
||
|
||
### Slide 20-29：MIMD并行机结构分类
|
||
|
||
**Slide 20**
|
||
计算机构成的两个最基本的要素
|
||
点：包括小到CPU内部的寄存器、ALU、控制器，到存储模块、外设，乃至多处理机的计算节点，都可以视为点；
|
||
互连网络：按照一定拓扑结构和控制方式，将点连接起来。
|
||
|
||
**Slide 22 - 静态互连网络**
|
||
静态互连网络：指处理单元间有固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变。
|
||
|
||
**Slide 23 - 动态互连网络**
|
||
动态互连网络：由开关单元构成，可以按照应用程序的要求动态的改变连接组态。
|
||
各种总线
|
||
交叉开关网络
|
||
多级互连网络
|
||
|
||
**Slide 24 - 并行处理机体系结构分类**
|
||
并行处理机体系结构分类
|
||
PVP，Parallel Vector Processor，并行向量处理机
|
||
SMP，Symmetric Multiprocessor，对称多处理机
|
||
MPP，Massively Parallel Processor，大规模并行处理机
|
||
DSM，Distributed Shared Memory，分布式共享存储多处理机
|
||
COW，Cluster of Workstations，工作站集群
|
||
|
||
**Slide 25 - PVP**
|
||
PVP：Parallel Vector Processor, 并行向量处理机
|
||
这样的系统中包含了少量的高性能专门设计定制的向量处理器VP，每个至少具有1 Gflops的处理能力；
|
||
存储器以兆字节每秒的速度向处理器提供数据。
|
||
向量处理器VP和共享存储模块通过高带宽的交叉开关网络互连；
|
||
这样的机器通常不使用高速缓存，而是使用大量的向量寄存器和指令缓冲器；
|
||
例如：Cray90、NECSX-4和我国的银河１号等都是 PVP。
|
||
|
||
**Slide 26 - SMP**
|
||
SMP: Symmetric Multiprocessor, 对称多处理机
|
||
SMP系统使用商品微处理器（具有片上或外置高速缓存）；
|
||
它们经由高速总线（或交叉开关）连向共享存储器和I/O；
|
||
这种机器主要应用于商务，例如数据库、在线事务处理系统和数据仓库等；
|
||
重要的是系统是对称的，每个处理器可等同的访问共享存储器、I/O设备和操作系统服务。正是对称，才能开拓较高的并行度；也正是共享存储，限制系统中的处理器不能太多（一般少于64个），同时总线和交叉开关互连一旦作成也难于扩展。
|
||
例如：IBM R50、SGI Power Challenge、DEC Alpha服务器8400和我国的曙光１号等都是这种类型的机器。
|
||
|
||
**Slide 27 - MPP**
|
||
MPP: Massively Parallel Processor, 大规模并行处理机
|
||
MPP一般是指超大型计算机系统；
|
||
处理节点采用商品微处理器；每个节点上有自己的局部存储器；采用高通信带宽和低延迟的互连网络（专门设计和定制的）进行节点互连；
|
||
能扩放至成百上千乃至上万个处理器；
|
||
它是一种异步的MIMD机器，程序系由多个进程组成，每个都有其私有地址空间，进程间采用传递消息相互作用；
|
||
MPP的主要应用是科学计算、工程模拟和信号处理等以计算为主的领域。
|
||
例如：Intel Paragon、Cray T3E、IntelOption Red和我国的曙光-1000等都是这种类型的机器。
|
||
|
||
**Slide 28 - DSM**
|
||
DSM: Distributed Shared Memory, 分布式共享存储多处理机
|
||
物理上有分布在各节点中的局部存储器，但是对用户而言，系统硬件和软件提供了逻辑上单地址的编程空间。
|
||
高速缓存目录DIR用以支持分布高速缓存的一致性。
|
||
DSM相对于MPP的优越性是编程较容易。
|
||
例如：Stanford DASH、Cray T3D和SGI/Cray Origin 2000等。
|
||
|
||
**Slide 29 - COW**
|
||
COW: Cluster of Workstations, 工作站集群
|
||
在有些情况下，集群往往是低成本的变形的MPP;
|
||
COW的重要界线和特征是：
|
||
①COW的每个节点都是一个完整的工作站（不包括监视器、键盘、鼠标等），这样的节点有时叫作"无头工作站"，一个节点也可以是一台PC或SMP；
|
||
②各节点通过一种低成本的商品（标准）网络（如以太网、FDDI和ATM开关等）互连（有的商用机群也使用定做的网络）；
|
||
③各节点内总是有本地磁盘，而MPP节点内却没有；
|
||
④节点内的网络接口是松散耦合到I/O总线上的，而MPP内的网络接口是连到处理节点的存储总线上的，因而可谓是紧耦合式的；
|
||
⑤一个完整的操作系统驻留在每个节点中，而MPP中通常只是个微核，COW的操作系统是工作站 UNIX，加上一个附加的软件层以支持单一系统映像、并行度、通信和负载平衡等。
|
||
Berkeley NOW、Alpha Farm、Digital Truclster等都是COW结构。
|
||
|
||
### Slide 31-38：并行处理面临的挑战与性能评测
|
||
|
||
**Slide 31**
|
||
并行处理面临的挑战
|
||
并行处理面临着两个重要的挑战
|
||
程序中的并行性有限
|
||
相对较大的通信开销
|
||
|
||
系统加速比 =
|
||
|
||
**Slide 32 - 第一个挑战**
|
||
第一个挑战
|
||
有限的并行性使计算机要达到很高的加速比十分困难。
|
||
例： 假设想用100个处理器达到80的加速比，求原计算程序中串行部分最多可占多大的比例？
|
||
|
||
解 Amdahl定律为：
|
||
|
||
由上式可得：并行比例＝0.9975
|
||
|
||
**Slide 33 - 第二个挑战**
|
||
第二个挑战
|
||
多处理机中远程访问的延迟较大
|
||
在现有的机器中，处理器之间的数据通信大约需要50～1000个时钟周期。
|
||
主要取决于：
|
||
通信机制、互连网络的种类和机器的规模
|
||
|
||
**Slide 34 - 例题**
|
||
例题
|
||
假设有一台32台处理器的多处理机，对远程存储器访问时间为200ns。除了通信以外，假设所有其他访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器的时钟频率为2GHz，如果指令基本的CPI为0.5（设所有访存均命中Cache），求在没有远程访问的情况下和有0.2%的指令需要远程访问的情况下，前者比后者快多少?
|
||
|
||
**Slide 35 - 例题解答**
|
||
例题
|
||
解 有0.2%远程访问的机器的实际CPI为：
|
||
CPI＝基本CPI＋远程访问率×远程访问开销
|
||
＝0.5＋0.2%×远程访问开销
|
||
远程访问开销为：
|
||
远程访问时间/时钟周期时间＝200ns/0.5ns＝400个时钟周期
|
||
∴ CPI＝0.5＋0.2%×400＝1.3
|
||
因此在没有远程访问的情况下的机器速度是有0.2%远程访问的机器速度的1.3/0.5=2.6倍。
|
||
|
||
**Slide 36 - 问题的解决**
|
||
问题的解决
|
||
并行性不足： 采用并行性更好的算法
|
||
远程访问延迟的降低：靠系统结构支持和编程技术
|
||
|
||
**Slide 37 - 影响性能的因素**
|
||
影响性能的因素
|
||
在并行处理中，影响性能（负载平衡、同步和存储器访问延迟等）的关键因素常依赖于：
|
||
应用程序的高层特性
|
||
如数据的分配，并行算法的结构以及在空间和时间上对数据的访问模式等。
|
||
依据应用特点可把多机工作负载大致分成两类：
|
||
单个程序在多处理机上的并行工作负载
|
||
多个程序在多处理机上的并行工作负载
|
||
|
||
**Slide 38 - 并行程序的计算／通信比率**
|
||
并行程序的计算／通信比率
|
||
反映并行程序性能的一个重要的度量：
|
||
计算与通信的比率
|
||
计算／通信比率随着处理数据规模的增大而增加；随着处理器数目的增加而减少。
|
||
|
||
### Slide 40-75：Cache一致性
|
||
|
||
**Slide 40 - 对称式共享存储器系统结构**
|
||
对称式共享存储器系统结构
|
||
多个处理器共享一个存储器。
|
||
当处理机规模较小时，这种计算机十分经济。
|
||
近些年，能在一个单独的芯片上实现2～8个处理器核。
|
||
例如：Sun公司 2006年 T1 8核的多处理器
|
||
支持对共享数据和私有数据的Cache缓存
|
||
私有数据供一个单独的处理器使用，而共享数据则是供多个处理器使用。
|
||
共享数据进入Cache产生了一个新的问题
|
||
Cache的一致性问题
|
||
|
||
**Slide 41**
|
||
Cache一致性
|
||
多处理机的Cache一致性问题
|
||
允许共享数据进入Cache，就可能出现多个处理器的Cache中都有同一存储块的副本，
|
||
当其中某个处理器对其Cache中的数据进行修改后，就会使得其Cache中的数据与其他Cache中的数据不一致。
|
||
|
||
**Slide 42**
|
||
例如：
|
||
由两个处理器（A和B）读写引起的Cache一致性问题
|
||
|
||
**Slide 43 - 存储器的一致性**
|
||
存储器的一致性
|
||
如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。
|
||
存储系统行为的两个不同方面
|
||
What: 读操作得到的是什么值
|
||
When: 什么时候才能将已写入的值返回给读操作
|
||
需要满足以下条件
|
||
处理器P对单元X进行一次写之后又对单元X进行读，读和写之间没有其他处理器对单元X进行写，则P读到的值总是前面写进去的值。
|
||
处理器P对单元X进行写之后，另一处理器Q对单元X进行读，读和写之间无其他写，则Q读到的值应为P写进去的值。
|
||
对同一单元的写是串行化的，即任意两个处理器对同一单元的两次写，从各个处理器的角度看来顺序都是相同的。(写串行化 )
|
||
|
||
**Slide 44**
|
||
在后面的讨论中，我们假设：
|
||
直到所有的处理器均看到了写的结果，这个写操作才算完成；
|
||
处理器的任何访存均不能改变写的顺序。就是说，允许处理器对读进行重排序，但必须以程序规定的顺序进行写。
|
||
|
||
**Slide 45 - 实现一致性的基本方案**
|
||
实现一致性的基本方案
|
||
在一致的多处理机中，Cache提供两种功能：
|
||
共享数据的迁移
|
||
减少了对远程共享数据的访问延迟，也减少了对共享存储器带宽的要求。
|
||
共享数据的复制
|
||
不仅减少了访问共享数据的延迟，也减少了访问共享数据所产生的冲突。
|
||
|
||
一般情况下，小规模多处理机是采用硬件的方法来实现Cache的一致性。
|
||
|
||
**Slide 46 - Cache一致性协议**
|
||
Cache一致性协议
|
||
在多个处理器中用来维护一致性的协议。
|
||
关键：跟踪记录共享数据块的状态
|
||
两类协议（采用不同的技术跟踪共享数据的状态）
|
||
目录式协议（directory）
|
||
物理存储器中数据块的共享状态被保存在一个称为目录的地方。
|
||
监听式协议（snooping）
|
||
每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。
|
||
Cache通常连在共享存储器的总线上，当某个Cache需要访问存储器时，它会把请求放到总线上广播出去，其他各个Cache控制器通过监听总线（它们一直在监听）来判断它们是否有总线上请求的数据块。如果有，就进行相应的操作。
|
||
|
||
**Slide 47 - 两种解决Cache一致性问题的方法**
|
||
两种解决Cache一致性问题的方法
|
||
写作废协议：
|
||
在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权。(作废其他的副本)
|
||
写更新协议：
|
||
当一个处理器对某数据项进行写入时，通过广播使其他Cache中所有对应于该数据项的副本进行更新。
|
||
|
||
**Slide 48 - 写作废协议**
|
||
写作废协议
|
||
例 监听总线、写作废协议举例（采用写直达法）
|
||
初始状态：CPU A、CPU B、CPU C都有X的副本。在CPU A要对X进行写入时，需先作废CPU B和CPU C中的副本，然后再将p写入Cache A中的副本，同时用该数据更新主存单元X。
|
||
|
||
**Slide 49 - 写更新协议**
|
||
写更新协议
|
||
例 监听总线、写更新协议举例（采用写直达法）
|
||
假设：3个Cache都有X的副本。当CPU A将数据p写入Cache A中的副本时，将p广播给所有的Cache，这些Cache用p更新其中的副本。由于这里是采用写直达法，所以CPU A还要将p写入存储器中的X。如果采用写回法，则不需要写入存储器。
|
||
|
||
**Slide 50 - 性能差别**
|
||
性能差别
|
||
写更新和写作废协议性能上的差别主要来自：
|
||
在对同一个数据进行多次写操作而中间无读操作的情况下，写更新协议需进行多次写广播操作，而写作废协议只需一次作废操作。
|
||
在对同一Cache块的多个字进行写操作的情况下，写更新协议对于每一个写操作都要进行一次广播，而写作废协议仅在对该块的第一次写时进行作废操作即可。
|
||
写作废是针对Cache块进行操作，而写更新则是针对字（或字节）进行。
|
||
考虑从一个处理器A进行写操作后到另一个处理器B能读到该写入数据之间的延迟时间: 写更新协议的延迟时间较小。
|
||
|
||
### Slide 52-75：监听协议实现与MSI/MESI/MOSI协议
|
||
|
||
**Slide 52 - 监听协议的实现**
|
||
监听协议的实现
|
||
监听协议的基本实现技术
|
||
实现监听协议的关键有3个方面
|
||
处理器之间通过一个可以实现广播的互连机制相连。
|
||
通常采用的是总线。
|
||
当一个处理器的Cache响应本地CPU的访问时，如果它涉及全局操作，其Cache控制器就要在获得总线的控制权后，在总线上发出相应的消息。
|
||
所有处理器都一直在监听总线，它们检测总线上的地址在它们的Cache中是否有副本。若有，则响应该消息，并进行相应的操作 。
|
||
写操作的串行化：由总线实现
|
||
（获取总线控制权的顺序性）
|
||
|
||
**Slide 53**
|
||
监听协议的实现
|
||
Cache发送到总线上的消息主要有以下两种：
|
||
RdMiss——读不命中
|
||
WtMiss——写不命中
|
||
需要通过总线找到相应数据块的最新副本，然后调入本地Cache中。
|
||
写直达Cache：因为所有写入的数据都同时被写回主存，所以从主存中总可以取到其最新值。
|
||
对于写回Cache，得到数据的最新值会困难一些，因为最新值可能在某个Cache中，也可能在主存中。
|
||
（后面的讨论中，只考虑写回法Cache）
|
||
|
||
**Slide 54**
|
||
监听协议的实现
|
||
有的监听协议还增设了一条Invalidate消息，用来通知其他各处理器作废其Cache中相应的副本。
|
||
与WtMiss的区别：Invalidate不引起调块
|
||
Cache的标识（tag）可直接用来实现监听。
|
||
作废一个块只需将其有效位置为无效。
|
||
给每个Cache块增设一个共享位
|
||
为"1"：该块是被多个处理器所共享
|
||
为"0"：仅被某个处理器所独占
|
||
块的拥有者：拥有该数据块的唯一副本的处理器。
|
||
|
||
**Slide 55 - MSI监听协议**
|
||
MSI监听协议
|
||
在每个结点内嵌入一个有限状态控制器。
|
||
该控制器根据来自处理器或总线的请求以及Cache块的状态，做出相应的响应。
|
||
每个数据块的状态取以下3种状态中的一种：
|
||
无效（简称I）：Cache中该块的内容为无效。
|
||
共享（简称S）：该块可能处于共享状态。
|
||
在多个处理器中都有副本。这些副本都相同，且与存储器中相应的块相同。
|
||
已修改（简称M）：该块已经被修改过，并且还没写入存储器。
|
||
（块中的内容是最新的，系统中唯一的最新副本）
|
||
|
||
"已修改" 隐含表明该块是独占的（exclusive）
|
||
|
||
**Slide 56 - 两种请求来源**
|
||
考虑两种情况：
|
||
Invalid
|
||
Shared
|
||
Modified
|
||
Invalid
|
||
Shared
|
||
Modified
|
||
I. 请求来自处理器
|
||
II. 请求来自总线
|
||
Invalidate
|
||
Invalidate
|
||
|
||
**Slide 57-67 - MSI状态转换**
|
||
（MSI协议状态转换图，内容与lht类似）
|
||
|
||
**Slide 68 - 基本MSI协议存在的问题**
|
||
基本MSI协议存在的问题
|
||
并发问题:
|
||
MSI协议假定操具有原子性：在完成一项操作的过程中，不会发生任何中间操作
|
||
例如：检测缺失，获取总线，接收响应
|
||
造成死锁和竞争的可能性
|
||
一个解决方案是：发送invalidate的处理器可以占用总线，直到其他处理器收到invalidate
|
||
问题：
|
||
一个块从一开始就不在缓存中
|
||
在读取时，块立即进入"共享"状态，尽管它可能是唯一被缓存的副本(也就是说，没有其他处理器会缓存它)
|
||
想法:
|
||
添加另一个状态，表明这是唯一的缓存副本，并且它是干净的。
|
||
|
||
**Slide 69 - MESI协议**
|
||
MESI协议
|
||
添加独占状态，表示只有一个缓存中的干净块
|
||
防止在写操作时需要写invalidate
|
||
|
||
从单一所有者状态(独占或修改)到共享状态的转换称为降级，因为这种转换剥夺了所有者修改数据的权利
|
||
从共享到单者状态(Exclusive或Modified)的转换称为升级，因为转换授予所有者(包含相应块的缓存)写入块的能力。
|
||
|
||
**Slide 70**
|
||
MESI协议状态转换图
|
||
|
||
**Slide 71 - MESI降级选择**
|
||
从M降级到S还是I?
|
||
S:如果数据可能被重用(在它被另一个处理器写入之前)
|
||
I:如果数据很可能不会被重用(在它被另一个写入之前)
|
||
Cache-to-cache转移
|
||
在BusRd上，数据应该来自另一个缓存还是内存?
|
||
另一个缓存
|
||
可能会更快，如果内存很慢或高度竞争
|
||
存储器
|
||
更简单:不需要等着看另一个缓存是否先有数据
|
||
减少其他缓存的争用
|
||
要求M降级时写回
|
||
"修改"->"共享"转换时写回是否有必要?
|
||
一种可能性:所有者(O)状态(MOESI协议)
|
||
一个缓存拥有最新的数据(内存不更新)。
|
||
当所有缓存退出副本时，内存回写发生
|
||
|
||
**Slide 72**
|
||
观察：共享状态要求数据是干净的，也就是说，所有有块的缓存都有最新的副本，存储器也是如此
|
||
问题：当块处于修改状态时，当BusRd发生时需要将块写入内存
|
||
|
||
想法1：BusRd时不要从M过渡到S。将该副本作废，并将修改后的块直接提供给请求处理器，而不更新内存
|
||
想法2：从M过渡到S，但指定一个缓存作为所有者(O)，当块被撤销时，由O写回块
|
||
"共享"的意思是"共享且可能脏"
|
||
这是MOESI协议的一个版本
|
||
|
||
**Slide 73 - MOESI协议**
|
||
MOESI协议
|
||
增加拥有（Owned）状态，表示相关块由该缓存拥有，在存储器中已经过时。
|
||
MSI和MESI如果尝试共享处于"已修改"状态的块，会将其改为"共享"状态（原共享缓存和新共享缓存中都会作此修改），必须将这个块写回存储器中。
|
||
MOESI协议中，会在原缓存中将这个块的状态由"已修改"改为"拥有"，不再将其写到存储器中。
|
||
新共享这个块的其他缓存使这个块保持共享状态，只有原缓存保持"拥有"状态，表示主存副本已过期，指定缓存成为其拥有者。
|
||
拥有者需要在发生缺失时提供该块，如果替换，须将其写回存储器。
|
||
|
||
### Slide 76-126：目录协议
|
||
|
||
**Slide 76**
|
||
分布式共享存储器系统结构
|
||
目录协议的基本思想
|
||
广播和监听的机制使得监听一致性协议的可扩展性很差。
|
||
寻找替代监听协议的一致性协议。
|
||
（采用目录协议）
|
||
|
||
**Slide 77 - 目录协议**
|
||
目录协议
|
||
目录：一种集中的数据结构。对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息。
|
||
特点：对于任何一个数据块，都可以快速地在唯一的一个位置中找到相关的信息。这使一致性协议避免了广播操作。
|
||
位向量：记录哪些Cache中有副本。
|
||
每一位对应于一个处理器。
|
||
长度与处理器的个数成正比。
|
||
由位向量指定的处理机的集合称为共享集S。
|
||
分布式目录
|
||
目录与存储器一起分布到各结点中，从而对于不同目录内容的访问可以在不同的结点进行。
|
||
|
||
**Slide 79 - 目录法实现方案**
|
||
目录法最简单的实现方案
|
||
对于存储器中每一块都在目录中设置一项。目录中的信息量与M×N成正比。
|
||
其中：
|
||
M：存储器中存储块的总数量
|
||
N：处理器的个数
|
||
由于M=K×N， K是每个处理机中存储块的数量，所以如果K保持不变，则目录中的信息量就与N2成正比。
|
||
|
||
**Slide 80 - 本地结点、宿主结点以及远程结点的关系**
|
||
本地结点、宿主结点以及远程结点的关系
|
||
本地结点：发出访问请求的结点
|
||
宿主结点：包含所访问的存储单元及其目录项的结点
|
||
远程结点可以和宿主结点是同一个结点，也可以不是同一个结点。
|
||
宿主结点：存放有对应地址的存储器块和目录项的结点
|
||
|
||
**Slide 81-84 - 消息定义**
|
||
在结点之间发送的消息
|
||
本地结点发给宿主结点（目录）的消息
|
||
说明：括号中的内容表示所带参数。
|
||
P：发出请求的处理机编号
|
||
K：所要访问的地址
|
||
|
||
RdMiss（P，K）
|
||
处理机P读取地址为K的数据时不命中，请求宿主结点提供数据（块），并要求把P加入共享集。
|
||
|
||
WtMiss（P，K）
|
||
处理机P对地址K进行写入时不命中，请求宿主结点提供数据，并使P成为所访问数据块的独占者。
|
||
|
||
Invalidate（K）
|
||
请求向所有拥有相应数据块副本（包含地址K）的远程Cache发Invalidate消息，作废这些副本。
|
||
|
||
宿主结点（目录）发送给远程结点的消息
|
||
Invalidate（K）
|
||
作废远程Cache中包含地址K的数据块。
|
||
Fetch（K）
|
||
从远程Cache中取出包含地址K的数据块，并将之送到宿主结点。把远程Cache中那个块的状态改为"共享"。
|
||
Fetch&Inv（K）
|
||
从远程Cache中取出包含地址K的数据块，并将之送到宿主结点。然后作废远程Cache中的那个块。
|
||
|
||
宿主结点发送给本地结点的消息
|
||
DReply（D）
|
||
D表示数据内容。
|
||
把从宿主存储器获得的数据返回给本地Cache。
|
||
|
||
远程结点发送给宿主结点的消息
|
||
WtBack（K，D）
|
||
把远程Cache中包含地址K的数据块写回到宿主结点中， 该消息是远程结点对宿主结点发来的"取数据"或"取/作废"消息的响应。
|
||
|
||
本地结点发送给被替换块的宿主结点的消息
|
||
MdSharer（P，K）
|
||
用于当本地Cache中需要替换一个包含地址K的块、且该块未被修改过的情况。这个消息发给该块的宿主结点，请求它将P从共享集中删除。如果删除后共享集变为空集，则宿主结点还要将该块的状态改变为"未缓存"（U）。
|
||
WtBack2（P，K，D）
|
||
用于当本地Cache中需要替换一个包含地址K的块、且该块已被修改过的情况。这个消息发给该块的宿主结点，完成两步操作：①把该块写回；②进行与MdSharer相同的操作。
|
||
|
||
**Slide 86 - 目录协议实例**
|
||
目录协议实例
|
||
在基于目录的协议中，目录承担了一致性协议操作的主要功能。
|
||
本地结点把请求发给宿主结点中的目录，再由目录控制器有选择地向远程结点发出相应的消息。
|
||
发出的消息会产生两种不同类型的动作：
|
||
更新目录状态
|
||
使远程结点完成相应的操作
|
||
|
||
**Slide 87 - 存储块的状态**
|
||
在目录协议中，存储块的状态有3种：
|
||
未缓冲：该块尚未被调入Cache。所有处理器的Cache中都没有这个块的副本。
|
||
共享：该块在一个或多个处理机上有这个块的副本，且这些副本与存储器中的该块相同。
|
||
独占：仅有一个处理机有这个块的副本，且该处理机已经对其进行了写操作，所以其内容是最新的，而存储器中该块的数据已过时。
|
||
这个处理机称为该块的拥有者。
|
||
|
||
**Slide 88 - 目录的状态转换及相应的操作**
|
||
目录的状态转换及相应的操作
|
||
对于从本地结点发来的请求，目录所进行的操作包括：
|
||
向远程结点发送消息以完成相应的操作。这些远程结点由共享集合指出；
|
||
修改目录中该块的状态；
|
||
更新共享集合。
|
||
目录可能接收到5种不同的请求
|
||
读不命中 （针对请求数据）
|
||
写不命中（针对请求数据）
|
||
作废（写命中时）（针对请求数据）
|
||
从共享集合中删除（针对替换数据）
|
||
本地数据写回（针对替换数据）
|
||
（假设这些操作是原子的）
|
||
|
||
**Slide 99-101 - 目录状态转换详细**
|
||
（内容与lht类似，此处省略）
|
||
|
||
### Slide 127-133：目录的三种结构
|
||
|
||
**Slide 127**
|
||
目录的三种结构
|
||
不同目录协议的主要区别主要有两个
|
||
所设置的存储器块的状态及其个数不同
|
||
目录的结构
|
||
根据目录的结构，目录协议可分为3类
|
||
全映像目录、有限映像目录、链式目录
|
||
|
||
**Slide 128 - 全映像目录**
|
||
全映像目录
|
||
每一个目录项都包含一个N位（N为处理机的个数）的位向量，其每一位对应于一个处理机。
|
||
优点：处理比较简单，速度也比较快。
|
||
缺点：
|
||
存储空间的开销很大。
|
||
目录项的数目与处理机的个数N成正比，而目录项的大小（位数）也与N成正比，因此目录所占用的空间与N2成正比。
|
||
可扩放性很差。
|
||
|
||
**Slide 129**
|
||
全映像目录
|
||
当位向量中的值为"1"时，就表示它所对应的处理机有该数据块的副本；否则就表示没有。
|
||
在这种情况下，共享集合由位向量中值为"1"的位所对应的处理机构成。
|
||
|
||
**Slide 130 - 有限映像目录**
|
||
有限映像目录
|
||
提高其可扩放性和减少目录所占用的空间。
|
||
核心思想：采用位数固定的目录项目
|
||
限制同一数据块在所有Cache中的副本总数。
|
||
例如，限定为常数m。则目录项中用于表示共享集合所需的二进制位数为：m×log2N。
|
||
目录所占用的空间与N× 成正比。
|
||
缺点
|
||
当同一数据的副本个数大于m时，必须做特殊处理。当目录项中的m个指针都已经全被占满，而某处理机又需要新调入该块时，就需要在其m个指针中选择一个，将之驱逐，以便腾出位置，存放指向新调入块的处理机的指针。
|
||
|
||
**Slide 131**
|
||
有限映像目录（m＝4，N≥8的情况）
|
||
举例
|
||
|
||
**Slide 132 - 链式目录**
|
||
链式目录
|
||
用一个目录指针链表来表示共享集合。当一个数据块的副本数增加（或减少）时，其指针链表就跟着变长（或变短）。
|
||
由于链表的长度不受限制，因而带来了以下优点：既不限制副本的个数，又保持了可扩展性。
|
||
链式目录有两种实现方法
|
||
单链法: 当Cache中的块被替换出去时，需要对相应的链表进行操作——把相应的链表元素（假设是链表中的第i个）删除。实现方法有以下两种：
|
||
沿着链表往下寻找第i个元素，找到后，修改其前后的链接指针，跳过该元素。
|
||
找到第i个元素后，作废它及其后的所有元素所对应的Cache副本。
|
||
双链法
|
||
在替换时不需要遍历整个链表。
|
||
节省了处理时间，但其指针增加了一倍，而且一致性协议也更复杂了。
|
||
|
||
**Slide 133**
|
||
链式目录
|
||
采用单向链法的示意图
|
||
共享集＝{ P2 }
|
||
共享集＝{ P1，P4，P2 } |