22 KiB
第5章 线程级并行：多处理机 - 各老师章节总结
曲冠南（qgn）
授课主线概述
曲冠南老师的授课以"计算机构成要素"开篇，首先建立"点+互连网络"的基本框架，进而展开对多种MIMD并行机结构模型的详细介绍。他重点讲解了多处理机的存储结构分类，随后深入到Cache一致性这一核心主题，系统阐述了监听协议和目录协议两类一致性协议的工作原理。
知识要点总结
一、计算机构成要素与系统互连
老师首先指出计算机构成有两个最基本的要素：一是"点"，包括从CPU内部的寄存器、ALU、控制器到存储模块、外设乃至多处理机的计算节点；二是"互连网络"，按照一定拓扑结构和控制方式将点连接起来。
在此基础上，老师介绍了静态互连网络和动态互连网络的概念。静态互连网络指处理单元间有固定连接的一类网络，在程序执行期间这种点到点的链接保持不变。动态互连网络由开关单元构成，可以按照应用程序的要求动态改变连接组态，包括各种总线、交叉开关网络和多级互连网络。
二、MIMD并行机结构模型
老师详细讲解了五种基本的MIMD并行机结构模型：
PVP（并行向量处理机）：包含少量高性能专门设计定制的向量处理器VP，每个至少具有1Gflops的处理能力。向量处理器VP和共享存储模块通过高带宽的交叉开关网络互连。这种机器通常不使用高速缓存，而是使用大量的向量寄存器和指令缓冲器。例如Cray90、NECSX-4和我国的银河1号等。
SMP（对称多处理机）：使用商品微处理器，经由高速总线（或交叉开关）连向共享存储器和I/O。系统是对称的，每个处理器可等同地访问共享存储器、I/O设备和操作系统服务。正是对称，才能开拓较高的并行度；也正是共享存储，限制系统中的处理器不能太多（一般少于64个）。例如IBM R50、SGI Power Challenge、DEC Alpha服务器8400和我国的曙光1号等。
MPP（大规模并行处理机）：一般指超大型计算机系统，处理节点采用商品微处理器，每个节点上有自己的局部存储器，采用高通信带宽和低延迟的互连网络进行节点互连。能扩展至成百上千乃至上万个处理器，是一种异步的MIMD机器。例如Intel Paragon、Cray T3E和我国的曙光-1000等。
DSM（分布式共享存储多处理机）：物理上有分布在各节点中的局部存储器，但对用户而言系统提供了逻辑上单地址的编程空间。高速缓存目录DIR用以支持分布高速缓存的一致性。DSM相对于MPP的优越性是编程较容易。例如Stanford DASH、SGI Origin系列等。
COW（工作站集群）：每个节点都是一个完整的工作站，各节点通过低成本的商品网络互连，各节点内总有本地磁盘，而MPP节点内却没有。一个完整的操作系统驻留在每个节点中，而MPP中通常只是个微核。
三、从存储角度看MIMD
老师从存储结构角度将MIMD分为单地址空间共享存储和多地址空间非共享存储两大类。共享存储又分为均匀存储访问（UMA）和非均匀存储访问（NUMA）。
四、Cache一致性问题
老师重点讲解了多处理机Cache一致性问题的本质：允许共享数据进入Cache，就可能出现多个处理器的Cache中都有同一存储块的副本，当其中某个处理器对其Cache中的数据进行修改后，就会使得其Cache中的数据与其他Cache中的数据不一致。
关于存储器的一致性，老师指出如果对某个数据项的任何读操作均可得到其最新写入的值，则认为这个存储系统是一致的。存储器一致性需要满足三个条件：写后读的顺序性、读后写的顺序性、以及写串行化。
在一致的多处理机中，Cache提供两种功能：一是共享数据的迁移，将数据从"拥有者"那里移动到"请求者"的本地Cache中；二是共享数据的复制，当多个核心同时读取同一份数据时，系统允许每个核心的Cache中都保留一份该数据的副本。
五、Cache一致性协议
老师介绍了两类协议：目录式协议和监听式协议。目录式协议中物理存储器中数据块的共享状态被保存在一个称为目录的地方。监听式协议中每个Cache除了包含物理存储器中块的数据拷贝之外，也保存着各个块的共享状态信息。
解决Cache一致性问题的方法有两种：写作废协议和写更新协议。写作废协议在处理器对某个数据项进行写入之前，保证它拥有对该数据项的唯一的访问权（作废其他的副本）。写更新协议当一个处理器对某数据项进行写入时，通过广播使其他Cache中所有对应于该数据项的副本进行更新。
老师详细分析了写更新和写作废协议性能上的差别：在对同一个数据进行多次写操作而中间无读操作的情况下，写更新协议需进行多次写广播操作，而写作废协议只需一次作废操作；在对同一Cache块的多个字进行写操作的情况下，写更新协议对于每一个写操作都要进行一次广播，而写作废协议仅在对该块的第一次写时进行作废操作即可。
六、监听协议的实现
老师讲解了监听协议的基本实现技术，实现监听协议的关键有三个方面：处理器之间通过一个可以实现广播的互连机制相连（通常采用的是总线）；当一个处理器的Cache响应本地CPU的访问时，如果它涉及全局操作，其Cache控制器就要在获得总线的控制权后，在总线上发出相应的消息；所有处理器都一直在监听总线。
监听协议中每个数据块的状态有三种：无效（I）、共享（S）和已修改（M）。老师通过状态转换图详细展示了各种请求来源（来自处理器或来自总线）下的状态转换过程。
七、目录协议
老师指出广播和监听的机制使得监听一致性协议的可扩放性很差，因此需要采用目录协议来替代。目录是一种集中的数据结构，对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息。
目录协议中存储块的状态有三种：未缓冲（uncached）、共享（shared）和独占（exclusive）。老师详细讲解了本地结点、宿主结点和远程结点的关系，以及各种消息的定义和作用。
八、目录的三种结构
老师介绍了目录协议的三种结构：
全映像目录：每一个目录项都包含一个N位的位向量，其每一位对应于一个处理机。优点是处理比较简单，速度也比较快；缺点是存储空间的开销很大，目录所占用的空间与N²成正比，可扩放性很差。
有限映像目录：核心思想是采用位数固定的目录项目，限制同一数据块在所有Cache中的副本总数。目录所占用的空间与N×log₂N成正比。缺点是当同一数据的副本个数大于m时，必须做特殊处理。
链式目录：用一个目录指针链表来表示共享集合。由于链表的长度不受限制，因而既不限制副本的个数，又保持了可扩展性。链式目录有单链法和双链法两种实现方法。
李宏图（lht）
授课主线概述
李宏图老师的授课以完整的章节目录结构开篇，系统性地覆盖了多处理机的各个方面。老师从计算机构成要素讲起，详细介绍了并行处理机体系结构的五种分类模型，随后深入到并行处理面临的挑战（Amdahl定律和通信延迟），再过渡到通信机制，最后重点讲解Cache一致性协议（监听协议和目录协议），并补充了MSI/MESI/MOESI等进阶协议内容。
知识要点总结
一、计算机构成要素
老师指出计算机构成有两个最基本的要素：一是"点"，包括从CPU内部的寄存器、ALU、控制器到存储模块、外设乃至多处理机的计算节点；二是"互连网络"，按照一定拓扑结构和控制方式将点连接起来。
静态互连网络指处理单元间有固定连接的一类网络，在程序执行期间这种点到点的链接保持不变。动态互连网络由开关单元构成，可以按照应用程序的要求动态改变连接组态。
二、MIMD并行机结构分类
老师详细介绍了五种基本的MIMD并行机结构模型：PVP、SMP、MPP、DSM、COW，讲解与曲冠南老师基本一致，并补充了存储结构角度的分类：单地址空间共享存储（包括UMA和NUMA）、多地址空间非共享存储。
集中式共享存储器结构（SMP/UMA）：最多由几十个处理器构成，各处理器共享一个集中式的物理存储器。物理存储器被所有处理器均匀共享，所有处理器访问任何存储单元取相同时间。
分布式存储器多处理机：存储器在物理上是分布的，每个结点包含处理器、存储器、I/O和互连网络接口。将存储器分布到各结点有两个优点：降低对存储器和互连网络的带宽要求，访问本地存储器的延迟时间小。主要缺点是处理器之间的通信较为复杂，且访问延迟较大。
三、并行处理面临的挑战
老师指出并行处理面临着两个重要的挑战：一是程序中的并行性有限，二是相对较大的通信开销。
第一个挑战：有限的并行性使计算机要达到很高的加速比十分困难。老师给出了典型例题：假设想用100个处理器达到80的加速比，求原计算程序中串行部分最多可占多大的比例？根据Amdahl定律计算可得并行比例约为0.9975。
第二个挑战：多处理机中远程访问的延迟较大，在现有的机器中，处理器之间的数据通信大约需要50～1000个时钟周期，主要取决于通信机制、互连网络的种类和机器的规模。
老师给出了一个典型例题：假设有一台32台处理器的多处理机，对远程存储器访问时间为200ns，处理器的时钟频率为2GHz，基本CPI为0.5，求在没有远程访问和有0.2%指令需要远程访问两种情况下速度的比率。解答：远程访问开销为400个时钟周期，实际CPI为1.3，速度比为2.6倍。
四、通信机制
老师介绍了两种通信机制：
共享存储器通信机制：共享地址空间的计算机系统采用，处理器之间通过load和store指令对相同存储器地址进行读/写操作来实现通信。优点是与常用对称式多处理机使用的通信机制兼容，易于编程，当通信数据量较小时通信开销较低，可以通过采用Cache技术减少远程通信的频度。
消息传递通信机制：多个独立地址空间的计算机采用，通过处理器间显式传递消息来完成通信。优点是硬件较简单，通信是显式的，更容易搞清楚何时发生通信以及通信开销是多少。
同步消息传递：请求处理器发送一个消息后一直要等到应答结果才继续运行。异步消息传递：数据发送方知道别的处理器需要数据，通信可以从数据发送方开始，数据可以不经请求就直接送往数据接受方。
五、Cache一致性问题
老师详细讲解了多处理机Cache一致性问题的定义：允许共享数据进入Cache，就可能出现多个处理器的Cache中都有同一存储块的副本，当其中某个处理器对其Cache中的数据进行修改后，就会使得其Cache中的数据与其他Cache中的数据不一致。
存储器的一致性需要满足三个条件：写后读的顺序性、读后写的顺序性、写串行化。
在一致的多处理机中，Cache提供两种功能：共享数据的迁移和共享数据的复制。一般情况下，小规模多处理机采用硬件方法来实现Cache的一致性。
六、Cache一致性协议
老师介绍了监听式协议和目录式协议两类协议，以及写作废协议和写更新协议两种解决方法。
写更新和写作废协议的性能差别：在对同一个数据进行多次写操作而中间无读操作的情况下，写更新协议需进行多次写广播操作，而写作废协议只需一次作废操作；在对同一Cache块的多个字进行写操作的情况下，写更新协议对于每一个写操作都要进行一次广播，而写作废协议仅在对该块的第一次写时进行作废操作即可。
七、监听协议实现
老师详细讲解了监听协议的基本实现技术、实现监听协议的关键三个方面、Cache发送到总线上的消息（RdMiss和WtMiss）、Invalidate消息的作用，以及MSI监听协议的三种状态（Invalid、Shared、Modified）。
老师通过状态转换图详细展示了MSI协议的工作过程，包括请求来自处理器和请求来自总线两种情况下的各种状态转换。
八、MSI/MESI/MOESI协议演进
老师介绍了从MSI协议到MESI协议再到MOESI协议的演进过程。
MSI协议存在的问题：并发问题（假定操作具有原子性，可能造成死锁和竞争）；块从一开始就不在缓存中时，读取会立即进入"共享"状态，尽管它可能是唯一被缓存的副本。
MESI协议：添加独占状态（E），表示只有一个缓存中的干净块。从单一所有者状态到共享状态的转换称为降级；从共享到单一所有者状态的转换称为升级。
MOESI协议：增加拥有（Owned）状态，表示相关块由该缓存拥有，在存储器中已经过时。MOESI协议避免了在原缓存中将块写回存储器，提高了性能。
九、目录协议
老师详细讲解了目录协议的基本思想：目录是一种集中的数据结构，对于存储器中的每一个可以调入Cache的数据块，在目录中设置一条目录项，用于记录该块的状态以及哪些Cache中有副本等相关信息。这使一致性协议避免了广播操作。
分布式目录将目录与存储器一起分布到各结点中，从而对于不同目录内容的访问可以在不同的结点进行。
目录法最简单的实现方案中，目录中的信息量与M×N成正比（M为存储块总数量，N为处理器个数），如果K保持不变，则目录中的信息量就与N²成正比。
老师详细讲解了本地结点、宿主结点（Home结点）和远程结点的关系，以及各种消息的定义：RdMiss、WtMiss、Invalidate、Fetch、Fetch&Inv、DReply、WtBack、MdSharer、WtBack2。
十、目录的三种结构
老师介绍了三种目录结构：
全映像目录：每一个目录项都包含一个N位的位向量。优点是处理比较简单，速度也比较快；缺点是存储空间开销很大，目录所占用的空间与N²成正比，可扩放性很差。
有限映像目录：核心思想是采用位数固定的目录项目，限制同一数据块在所有Cache中的副本总数。目录所占用的空间与N×log₂N成正比。缺点是当同一数据的副本个数大于m时，必须做特殊处理。
链式目录：用一个目录指针链表来表示共享集合。既不限制副本的个数，又保持了可扩展性。分为单链法和双链法两种实现方法。
谭婧炜佳（tjwj）
授课主线概述
谭婧炜佳老师的授课以"从单处理器到多处理器"的历史演进开篇，引入摩尔定律和功耗墙等背景知识，然后系统性地展开对多处理器分类、存储结构、通信机制的讲解。老师尤其重视从应用和性能角度分析并行处理面临的挑战，详细讲解了Cache一致性协议（监听协议和目录协议），最后补充了MSI/MESI/MOESI协议演进和目录的三种结构。
知识要点总结
一、多处理器背景
老师从历史演进角度引入主题：单处理器性能的增长速度在1986年至2003年期间达到最高峰。之后摩尔定律放缓， Dennard Scaling失效。2004年Intel公司宣布放弃高性能单处理器项目，转向多核的研发。2006年开始，功耗墙问题导致处理器频率极限约为4GHz。
摩尔定律：单位面积的晶体管数量每两年增加一倍。
MIMD成为通用多处理机系统结构选择的原因：MIMD具有灵活性；MIMD可以充分利用商品化微处理器在性能价格比方面的优势。
二、多处理器的分类
老师将MIMD机器根据存储器组织结构分为两类：集中式共享存储器结构和分布式存储器多处理机。
集中式共享存储器结构：最多由几十个处理器构成，各处理器共享一个集中式的物理存储器。这类机器被称为SMP（对称多处理器）或UMA（一致存储器访问）。
分布式存储器多处理机：存储器在物理上是分布的，每个结点包含处理器、存储器、I/O和互连网络接口。将存储器分布到各结点的优点：降低对存储器和互连网络的带宽要求，访问本地存储器的延迟时间小。主要缺点是处理器之间的通信较为复杂，延迟较大。
簇（超级结点）：每个结点内包含个数较少（例如2～8）的处理器，处理器之间可采用另一种互连技术相互连接形成簇。
三、存储器系统结构
老师从逻辑地址空间组织方式将多处理机分为：共享地址空间（DSM/NUMA）和独立地址空间。
共享地址空间：物理上分离的所有存储器作为一个统一的共享逻辑空间进行编址。任何处理器可以访问该共享空间中的任何一个单元，不同处理器上的同一个物理地址指向同一个存储单元。
独立地址空间：每个结点中的存储器编址为独立的地址空间，整个系统的地址空间由多个独立的地址空间构成。现在这种机器多以集群的形式存在。
四、通信机制
老师介绍了两种通信机制，与其他老师内容一致：
共享存储器通信机制：处理器之间通过load和store指令对相同存储器地址进行读/写操作来实现通信。优点是易于编程，与常用对称式多处理机使用的通信机制兼容，当通信数据量较小时通信开销较低。
消息传递通信机制：通过处理器间显式传递消息来完成通信。优点是硬件较简单，通信是显式的，同步很自然地与发送消息相关联。
五、并行处理机体系结构分类
老师详细介绍了五种基本的MIMD并行机结构模型（PVP、SMP、MPP、DSM、COW），讲解内容与其他老师基本一致。
六、并行处理面临的挑战
老师指出并行处理面临两个重要挑战：程序中的并行性有限和相对较大的通信开销。
第一个挑战：有限的并行性使计算机要达到很高的加速比十分困难。典型例题：用100个处理器达到80的加速比，求原计算程序中串行部分最多可占多大的比例？根据Amdahl定律可得并行比例约为0.9975。
第二个挑战：多处理机中远程访问的延迟较大，处理器之间的数据通信大约需要50～1000个时钟周期。
老师给出了典型例题：32台处理器的多处理机，远程存储器访问时间200ns，时钟频率2GHz，基本CPI=0.5，求在没有远程访问和有0.2%指令需要远程访问两种情况下的速度比。解答：远程访问开销400个时钟周期，实际CPI=1.3，速度比=2.6倍。
问题的解决：并行性不足采用并行性更好的算法解决；远程访问延迟的降低靠系统结构支持和编程技术。
影响性能的因素：在并行处理中，影响性能的关键因素常依赖于应用程序的高层特性，如数据的分配、并行算法的结构以及在空间和时间上对数据的访问模式等。
计算/通信比率：反映并行程序性能的一个重要度量，随着处理数据规模的增大而增加，随着处理器数目的增加而减少。
七、Cache一致性问题
老师详细讲解了多处理机Cache一致性问题的定义、存储器一致性的定义和三个必要条件、以及实现一致性的基本方案。
Cache提供两种功能：共享数据的迁移和共享数据的复制。一般情况下，小规模多处理机采用硬件方法来实现Cache的一致性。
八、Cache一致性协议
老师介绍了监听式协议和目录式协议两类协议，以及写作废协议和写更新协议两种解决方法，详细分析了两种协议的性能差别。
九、监听协议实现
老师详细讲解了监听协议的基本实现技术、实现监听协议的关键三个方面、MSI监听协议的三种状态（Invalid、Shared、Modified），以及各种状态转换图。
十、MSI/MESI/MOESI协议演进
老师介绍了从MSI协议到MESI协议再到MOESI协议的发展过程。
MESI协议：添加独占状态（E），表示只有一个缓存中的干净块，防止在写操作时需要写invalidate。升级和降级的概念。
MOESI协议：增加拥有（Owned）状态，表示相关块由该缓存拥有，在存储器中已经过时。避免了不必要的写回操作，提高系统性能。
十一、目录协议
老师详细讲解了目录协议的基本思想、目录与存储器的分布方式、目录法实现方案、存储块的三种状态（未缓冲、共享、独占）。
老师详细讲解了本地结点、宿主结点和远程结点的关系，以及各种消息的定义和作用。包括：RdMiss、WtMiss、Invalidate、Fetch、Fetch&Inv、DReply、WtBack、MdSharer、WtBack2等。
老师还详细展示了目录的状态转换图，以及各种情况下的Cache块状态转换（CPU读、CPU写、远程Cache块收到请求）。
十二、目录的三种结构
老师介绍了三种目录结构及其各自的特点：
全映像目录：优点是处理简单、速度快；缺点是存储空间开销大，目录所占用的空间与N²成正比，可扩放性差。
有限映像目录：核心思想是限制同一数据块在所有Cache中的副本总数。目录所占用的空间与N×log₂N成正比。
链式目录：用目录指针链表表示共享集合，既不限制副本个数，又保持可扩展性。分为单链法和双链法两种实现方法。