第17 章 并行处理

在微操作层面上，多个控制信号同时产生。

指令流水线已经存在很长一段时间，至少在取指和执行是重叠的。对于超标量计算机，在一个处理器中多个执行单元，它们并行执行一个程序中多条指令。

计算机设计人员寻求越来越多的并行机会，一般都是为了提高性能，有时是为了提高可用性。本章将介绍一些重要的并行组织结构方法。首先，讨论对称多处理器smp。在smp结构中，多个处理器共享一个公共内存，引出高速缓存一致性问题。接着介绍多线程处理器和片上多处理器。然后，介绍集群，它是由多个相互独立的计算机以合作的方法组织在一起。集群越来越多地用于支持超过单个smp能力的工作负载。另一种使用多处理器的方式是非均匀存储访问numa计算机。

17.1 多处理器结构

17.1.1 并行处理器系统的类型

Flynn提出4类计算机系统：

        1.SISD：单个处理器执行一个指令流，操作单个内存中保存的数据。单处理器属于这类。

        2.SIMD：单个机器指令以锁步为基础控制多个处理单元的同时执行。每个处理单元都有一个相关联的数据存储器。因此，指令由不同处理器在不同数据集上执行。向量和数组处理器属于这类。

        3.MISD：一个数据序列被传递给一组处理器，每个处理器都执行一个不同的指令序列。这个结构在商业上没有实现。

        4.MIMD：一组处理器同时在不同的数据集上执行不同的指令序列。SMP，集群和NUMA系统都属于这类。

在MIMD结构中，处理器是通用的，每个处理器都能处理执行相应数据转换所需的所有指令。按照处理器通信方式，MIMD进一步划分。如果处理器之间共享一个公共内存，那么每个处理器都访问共享内存中的程序和数据，完成通信，被称为smp。smp典型特征是对于每个处理器来说，对任何内存区域的存储器访问时间都大致相同。而numa中处理器对内存不同区域的存储器访问时间是不同的。

独立的单处理器或者smp的集合可以互联形成集群。计算机之间的通信是通过固定路径或一些网络设施进行的。

17.2 并行组织形式

smp组织结构的特点如下：

        1. 具有2个或以上的功能相当的类似处理器；
        2. 这些处理器共享系统内存和io设施，通过总线或者其他内部连接方式进行互联，因此每个处理器的存储访问时间大致相同。
        3. 所有处理器都可以通过相同的通道或为同一设备提供不同通道来共享访问io设备。
        4. 所有处理器都可以执行相同功能。（因此是对称的）。
        5. 系统由一个集成的操作系统控制，它在作业、任务、文件和数据元素层面提供处理器及其程序之间的交互。

1~4点事不言自明的。5说明了与松耦合系统的对比。在后者，交互的物理单元通常是消息或完整文件。在smp中，单个数据元素可以构成一级交互，且进程之间可以进行高度协作。

与单处理器组织结构相比，smp组织结构具有以下潜在优势：性能、可用性、增量扩展和可伸缩性。注意这些优势是潜在的，而不是确定的。操作系统必须提供工具和功能来利用smp系统中的并行性。smp另一个吸引人的特点在于：多处理器的存在对用户来说是透明的。操作系统负责调度单个处理器上的线程或进程，以及处理器之间的同步。

17.2.1 组织结构

每个处理器都是独立的，包括控制单元，alu，寄存器，一般还包括一级或者多级缓存。每个处理器都可以通过某种形式的互连机制来访问共享内存和io设备。处理器通过内存（在公共数据区留下消息和状态消息）。处理器还可以直接交换信号。内存通常是有组织的，以便可以同时对不同的内存块进行多次访问。

分时总线是构建smp最简单的机制。其结构和接口基本上与使用总线互联的单处理器系统相同。总线包括控制总线、地址总线和数据总线。为了方便从io子系统到处理器的dma传输，提供以下功能：

        1.寻址：必须区分总线上模块，以确定数据的源和目的。
        2.仲裁：任何io模块都能暂时充当“主模块”。提供了一种机制来对总线控制权的竞争请求进行仲裁，此机制使用某种优先级方案。
        3.分时：当一个模块控制总线，其他模块会被锁住，如果有需要，它们必须挂起操作直到实现总线访问。

总线结构吸引人的特性：
        1.简单：这是最简单的多处理器组织结构方式，每个处理器的物理接口、寻址、仲裁和分时逻辑都与单处理器系统保持一致。
        2.灵活：一般很容易通过把更多处理器连接到总线上来扩展系统。
        3.可靠：总线本质是一种无源介质，其上连接的任何设备的故障都不应导致整个系统的故障。

总线的主要缺点是性能：所有的内存访问都需要经过公共总线，以及周期时间限制了系统的速度。要提高性能，最好是给每个处理器配备高速缓存，这显著降低了总线访问的数量。但引出了缓存一致性问题。为了防止出现这种情况，在发生写操作时，必须通知其他处理器，通常是由硬件来完成，而不是操作系统来完成。

17.2.2 多处理器操作系统设计考量

多处理器操作系统必须能提供多道程序系统的全部功能，以及适应多处理器的其他功能。其关键的设计问题包括：
        1.同时并发进程：os例程需要重入，以允许多个处理器同时执行相同的os代码。当多个处理器执行相同或者不同的os部分时，必须正确管理os表格和管理结构，以避免死锁或者无效操作。
        2.调度：任何处理器都可以执行调度，所以必须避免冲突。调度器必须将就绪进程分配给可用处理器。
        3.同步：对共享地址或io资源的多个活跃进程来说，必须注意提供有效的同步。同步是一种强制互斥和事件排序的工具。
        4.内存管理：包括单处理器机器发现的所有问题。此外，操作系统还需要利用可用的硬件并行性来获得最佳性能。必须协调不同处理器上的分页机制，以便在几个处理器共享页面或段时确保其一致性并决定如何替换页面。
        5.可靠性和容错：操作系统在面对处理器故障时，应该提供适当的降级功能。调度器和操作系统的其他部分必须识别处理器的丢失，并相应地重构管理表。

17.3 高速缓存一致性和mesi协议

高速缓存一致性问题的实质在于：相同的数据的多个副本可以同时存在于不同的高速缓存中。如果处理器被允许自由地更新自己的副本，那么就会导致不一样的内存视图。

对于任何高速缓存一致性协议，目标都是让最近使用过的局部变量进入适当的高速缓存，并在进行大量读写时留在那里，同时使用该协议维护共享变量的一致性，这些共享变量可能同时存在于多个高速缓存中。

实现方法一般分为软件方法和硬件方法，而采用的策略是同时包含软件和硬件的元素。

17.3.1 软件解决方法

软件高速缓存一致性方案试图通过编译器和操作系统来解决这个问题，从而避免额外的硬件电路和逻辑。软件实现方法很有吸引力：检测潜在问题的开销从运行时转变为编译时，设计复杂度从硬件转移到软件。缺点：编译器通常必须做出保守决定，使得高速缓存利用率低下。

给予编译器的一致性机制对代码进行分析，以确定那些数据可能会对缓存不安全，并相应地对这些数据项进行标记。然后，操作系统或者硬件就会组织不可缓存的数据项被缓存。最简单的方法是组织任何共享变量被缓存，但这太保守了，因为只有写访问才会导致一致性问题。更有效的方法是分析代码，确定共享变量的安全期。

17.3.2 硬件解决方案

给予硬件的解决方案通常被称为高速缓存一致性协议，可以在运行时动态识别潜在的不一致情况。优点：因为仅在实际出现时才解决问题，所以可以更有效地使用高速缓存，其性能高于软件方法，以及该过程对程序员和编译器是透明的，从而减轻了软件开发人员的负担。

硬件方案在许多细节上有所不同，包括数据行的状态信息保存在那里，如何组织这些信息、在哪里执行一致性以及执行机制。通常硬件方案分为两类：目录协议和监听协议。

        1.目录协议：收集并维护副本所在位置的信息。通常，有一个中央控制器作为主存控制器的一部分，还有一个目录保存在主存中。该目录包含关于各种本地高速缓存内容的全局状态信息。当单个高速缓存控制器发出请求时，中央控制器检查并发出必要的命令，以在主存和高速缓存之间或高速缓存之间进行数据传输。它还负责更新状态信息，因此，每一个会影响数据行全局状态的本地行为都必须报告给中央控制器。

中央控制器维护关于那些处理器拥有数据行副本的信息。在一个处理器可以写一个数据行的本地副本之前，它必须从控制器请求对改行的独占访问。在授权独占访问之前，控制器向所有拥有该数据行缓存副本的处理器发送一个消息，强制每个处理器将其副本置为无效。在每个处理器接收确认信息后，控制器就向发送请求的处理器授权独占访问。当另一个处理器尝试读取该数据行时，它将向控制器发送一个缺失通知。然后，控制器会向拥有该数据行的处理器发出命令，要求该处理器执行对主存的写回。现在，拥有该数据行和发请求的处理器可以通过共享该数据行。

目录方案存在中央控制器瓶颈以及各种缓存控制器与中央控制器之间通信开销的缺点。但是，它在涉及多总线或其他复杂互联方案的大型系统中是有效的。

        2.监听协议：把维护高速缓存一致性的责任分布给多处理器中所有的缓存控制器。高速缓存必须识别自身数据行何时与其他缓存共享，当在一个共享行上执行更新操作时，必须通过广播机制通知给其余缓存。

监听协议非常适合基于总线的多处理器，因为共享总线能提供简单的广播和监听方法。但是，本地高速缓存的一个主要目的是避免总线访问，所以必须注意广播和监听所需总线通信的增加会不会抵消使用本地高速缓存带来的好处。

监听协议开发了两种基本方法：写无效和写更新。对于写无效协议，同一时间可以有多个读者，但只有一个写者。当某一个高速缓存想要对数据行进行写操作时，它首先发出一个通知，使得其他缓存中的该行无效，从而让该行独占写。一旦该行变成独占的，拥有者处理器就可以执行廉价的本地写操作，直到其他处理器也需要该行。

对于写更新协议，可以同时存在多个写者和多个读者。当一个处理器想要更新一个共享行时，被更新的字也分发给所有其他的处理器，包括该行的高速缓存就可以对其进行更新。

两种方法都不存在于一种优于另外一种的情况。性能取决于本地高速缓存的数量和内存读写的模式。有些系统采用了自适应协议，包括写无效和写更新机制。

17.3.3 MESI协议

MESI：
        1.修改M：高速缓存中的数据行已经修改（与主存不同），且仅在该缓存中可用。
        2.独占E：高速缓存中的数据行与主存相同，且不存在于任何其他的缓存中。
        3.共享S：高速缓存中的数据行与主存相同，且可能存在于任何其他的缓存中。
        4.无效I：高速缓存中的数据行不含有效数据。

17.4 多线程和芯片多处理器

设计人员可从2个方面来提高性能：提高时钟频率和增加处理器时钟内执行的指令数。首先使用流水线，然后在超标量架构中使用多个并行指令流水线来提高IPC。对于流水线和多流水线设计，最主要的问题是最大限度地利用每个流水段。为了提高吞吐量，设计了诸如按照不同于指令流中出现的顺序执行某些指令，以及执行可能永远都不需要的指令。

另一个方法是多线程，它允许在不增加复杂度和能耗的情况下实现高度的指令级并行。实际上，指令流被分为几个更小的流，称为线程。

17.4.1 隐式和显式线程

进程包含2个关键特征：

        1.资源所有权：一个进程包含一个虚拟地址空间来存放进程映像，即定义进程的程序、数据、栈和属性的集合。有时可能会分配对资源的控制或所有权、比如主存、io通道、io设备和文件。

        2.调度/执行：进程的执行遵循一个或多个程序的执行路径（跟踪）。这个执行可能与其他进程的执行进行交叉。因此，进程有执行状态（运行，就绪等）和调度优先级，是有操作系统调度和分派的实体。

进程切换：通过保存第一个进程的所有控制顺序、寄存器和其他信息。并用第二个进程的信息来替换它们，从而把处理器从第一个进程切换到第二个进程的操作。

线程：进程内可分配的工作单元。它包括处理器上下文（包含程序计数器和栈指针）和它自己的栈数据区（用于启动子例程分支）。线程是顺序执行的，且是可中断的，所有处理器可以转向另一个线程。

线程切换：在同一进程内，处理器切换到另一个线程上操作。成本比切换进程低很多。

线程关心调度和执行，而进程关系调度/执行和资源所有权。一个进程中的多个线程共享同样的资源。这就是线程切换比进程消耗时间少得多的原因。

用户级线程（对应用程序可见）和内核级线程（对操作系统可见）是有区别的，这两种线程都可以成为显式线程。

显式多线程并发执行指令，要么是在共享流水线上交错执行，要么是在并行流水线上并行执行。隐式多线程是指并发执行从单个顺序中提取的多线程，这些隐式多线程可以由编译器静态定义，也可以由硬件动态定义。

17.4.2 显式多线程

多线程处理器至少要为并发执行的每个执行线程提供单独的程序计数器。通常，取指是在线程的基础上进行的。处理器单独处理每个线程，可以使用许多技术来优化单线程执行，包括分支预测、寄存器重命名和超标量技术。当线程级并行与指令级并行相结合时，可能会大大提升性能。

广义地说，有4种主要的多线程方法：
        1.交错多线程（细粒度线程）：处理器一次处理2个或多个线程上下文，每个时钟周期都从一个线程切换到另一个线程。如果一个线程由于数据依赖或内存延迟而阻塞的话，那么就跳过该线程并执行一个就绪线程。
        2.阻塞多线程（粗粒度线程）：一个线程的指令被依次执行，直到发生可能导致延迟的事件，比如高速缓存缺失。这个事件导致切换到另一个线程，该方法在按序处理器上有效。
        3.同时多线程（SMT）：指令同时从多个线程发射到超标量处理器的执行单元。它把宽大的超标量指令发射容量与多线程上下文的使用结合起来。
        4.芯片多处理器：在单个芯片上实现多核，每个内核处理器单独的线程。优点是可以有效地利用芯片上可用逻辑区域，而不是依赖于不断流水线设计的复杂性，被称为多核。

对于粗/细粒度线程而已，来自不同线程的指令不会同时执行。相反，处理器能够使用一组寄存器和其他的上下文信息快速地从一个线程切换到另一个线程，避免由于高速缓存缺失和其他延迟事件带来的巨大损失。SMT方法涉及使用重复的执行单元，真正地同时并行来自不同线程的指令。芯片多处理器还允许同时执行来自不同线程的指令。

多线程和流水线组合形式：

        1.单线程标量：传统risc和cisc机器中发现的简单流水线，没有多线程；
        2.交错多线程标量：最容易实现的多线程方法，在每个时钟周期从一个线程切换到另一个线程，流水段可以保持完全占用。硬件必须能在周期之间从一个线程上下文切换到另一个线程上下文。
        3.阻塞多线程标量：单线程被执行，直到延迟事件发生，该事件阻塞停止流水线，此时，处理器切换到另一个线程。尽管交错多线程似乎比阻塞多线程提供了更好的处理器利用率，但是，牺牲单线程性能和多个线程竞争高速缓存资源，增加了给定线程的高速缓存缺失的概率。
        4.超标量：这是处理器中提供并行性的最强大的方法。注意在某些周期内并不是所有可用发射槽都被使用。在这些周期中，发射的指令数小于最大指令数，被称为水平损失。在其他周期内，不使用发射槽，被称为垂直损失。
        5.交错多线程超标量：在每个周期内，从一个线程发射尽可能多的指令。如前所述，使用这种技术消除了线程切换带来的潜在延迟。但是，任何给定周期发射的指令书仍然受限于任何给定线程内存在的依赖性。
        6.阻塞多线程超标量：在任何周期都可能发射只来自一个线程的指令，且使用阻塞多线程。
        7.超长指令集（VLIW）：把多个指令放到一个字中。通常，VLIW由编译器构建，它把可以并行执行的操作放到同一个字中。
        8.交错/阻塞多线程VLIW：与超标量版本效率差不多。
        9.同时多线程：如果一个线程具有高度指令级并行性，那么它在某些周期内能够填充所有的水平槽。在其他周期内，可能会发射来自2个或多个线程的指令。如果有足够的线程处于活跃状态，一般就可以在每个周期发射最大数量的指令，从而提供较高的效率。
        10.芯片多处理器：每个内核都分配了一个线程。与SMT具有相同发射指令的芯片多处理器无法实现相同的指令级并行，因为芯片多处理器不能通过发射其他线程指令的方法来隐藏延迟。另一方面，在相同的指令发射的能力下，芯片多处理器的性能优于超标量处理器，因为超标量处理器的水平损失大。此外，芯片多处理器的每个内核都可以使用多线程。

17.5 集群

集群是除对称多处理器之外，另一种提供高性能和高可用的方法，对服务器应用尤其具有吸引力。

集群的4大优点：
        1.绝对可扩展性：远远超过最大的独立机器的能力。
        2.增量可扩展性：随着需求的增长进行扩展，而不需要进行大的升级。以便把现有的小系统替换成更大的系统。
        3.高可用性：因为集群中的每个节点都是独立的计算机。所以，一个节点的故障并不意味着服务丢失。容错是软件自动处理的。
        4.优越的性价比：通过使用商品构建块，可以以更低的成本将计算能力与大型计算机相当或更大的集群组合在一起。

17.5.2 用于集群的操作系统设计问题

1.故障管理：取决于使用的集群方法，主要分为高可用集群和容错集群；高可用集群提供了所有资源都处于服务状态，如果发生故障，将由集群的另一台计算机提供服务。容错集群确保所有资源始终可用。这是通过使用冗余共享磁盘以及备份来提交事务和提交已完成事务的机制来实现的。

2.负载均衡：负载均衡工具会自动将任务从一个成员迁移到另一个成员中。

3.并行计算：

        a.并行编译器：在编译时确定应用程序的那些部分可以并行执行，然后将它们拆分以分配给集群中不同的计算机。性能取决于问题的性质和编译器的设计，很难实现。

       b. 并行化应用程序：编写在集群上运行的任务，并根据需要，使用消息传递在集群节点之间传送数据，可能是使用集群最佳方法。

        c.参数计算：程序本质是执行次数非常多的算法或程序，且每次都是用不同的另一种启动条件或参数。

17.5.5 集群和SMP比较

两者都提供了高需求应用的多处理结构。

SMP优点：比集群更容易管理和配置。从单处理到smp所需的主要改变是调度器函数。比同类集群占用更少的物理空间，消耗更少的能源。比集群更成熟且稳定。

集群优点：在增量扩展和绝对扩展方法远远优于smp。可用性也非常出色，轻松地使系统的所有组件都具有高度冗余性。

17.6 非均匀内存一致

numa：存储器访问时间按照被访问的主存区域而不同。对于不同处理器，远离处理器内存区域比较慢，靠近处理器内存区域比较快。

17.6.1 动机

对于smp而言，可以使用的处理器数量实际上是有限的。有效的高速缓存方案可以减少任何处理器与主存之间的总线交流。随着处理器数量的增加，总线交流也会增加。此外，总线被用于交换高速缓存一致性的信号，这进一步了负担。在某些情况下，总线会成为性能瓶颈。一般smp的处理器数量限制在16~64个。

smp的处理器限制是集群系统开发背后的驱动动机之一。实际上，集群中的一致性是在软件中而不是在硬件中维护的。每个节点的私有内存影响性能，为了实现最大性能，软件必须适应环境。numa实现大规模多处理器的同时又保留了smp风格。

numa的目标允许多个处理器节点（每个节点都有自己的总线或其他内部互连系统）的同时，维护透明的系统级内存。

17.6.3 numa的优点和缺点

cc-numa的主要优点是：它可以在比smp更高的并行级上提供有效的性能，不需要重大的软件改变。对于多个numa节点，任何单个节点的总线流量仅限于总线能够处理的需求。但是，如果许多内存访问是针对远程节点的，那么性能就会开始下降。不过我们有理由相信这种性能下降是可以避免的。首先，使用L1和L2高速缓存的目的旨在最小化所有内存访问，包括远程访问。其次，如果软件具有良好的空间局部性，并且使用了虚拟存储器，那么应用所需数据将驻留在有限数量的常用页面上，这些页面会被加载到本地内存上。最后，可以通过在操作系统中包含页迁移机制来增强虚拟存储器方案。

即使解决了远程访问导致性能下降的问题，cc-numa仍然有2个缺点。首先，cc-numa并不像smp那样透明，把操作系统和应用程序从smp迁移到cc-numa系统需要改变软件。这包括之前提过的页面分配，进程分配和操作系统的负载均衡。第二个问题是可用性。

17.7 云计算

17.7.1 云计算要素

云计算由5个基本特征，3个服务模型和4个部署模型组成。云计算的5个基本特征包括：
        1.广泛的网络访问：功能通过网络模块提供，并通过标准机制来访问。
        2.快速弹性：云计算根据服务需求来扩展或减少资源。
        3.可度量的服务：通过某种适合服务类型（例如，存储、处理、带宽和活动用户账户）的抽象级别上利用度量功能自动控制和优化资源的使用。可以监视、控制和报告资源使用情况，为被使用服务的提供者和消费者提供透明性。
        4.按需自助服务：使用者根据需要自动提供计算能力，如服务时间和网络存储，而无需与每个服务提供者进行人工交互。由于服务是按需提供，因此资源不是it基础设施的永久部分。
        5.资源池：提供者的资源被汇集起来，使用多租户模型为多个使用者提供服务，根据使用者需求动态地分配和再分配不同的物理和虚拟资源。

3种服务模型：
        1.软件既服务saas：以软件的形式向使用者提供服务，在云中运行，并在云中可访问。
        2.平台既服务paas：以平台形式向使用者提供服务，使用者的应用程序可以在平台上运行。
        3.基础设施既服务laas：向使用者提供底层云基础设施的访问。

4种部署模型：
        1.公有云：可供公众或者大型行业团体使用，由销售云服务的组织拥有。优点是成本，订阅者仅为其所需资源和服务付费，并可根据需要进行调整，订阅者大大减少了管理开销。缺点是安全性。
        2.私有云：在组织内部it环境中实现的云基础设施。选择私有云的关键动机是安全性。
        3.社群云：具有私有云和公有云的特征。和私有云一样，社群云对任何订阅者都不开放。和公有云一样，云资源在许多独立组织之间共享。
        4.混合云：云基础设施由2个或多个云组成。      文章来源地址https://www.toymoban.com/news/detail-435361.html

到了这里，关于第17 章 并行处理的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！