跳到主要内容

丁致宇第二周学习报告-《并行程序设计基础》2.4-2.10

目录

正文

并行软件​

任务并行​

  1. SISD (Single Instruction Single Data)
  • 单指令单数据流：在SISD架构中，一个处理器在同一时刻执行一条指令，并且这条指令作用于单一的数据单元。这是传统的冯·诺依曼架构计算机的基础模型，每个处理单元独立完成运算任务，不具备硬件级并行性。
  1. SIMD (Single Instruction Multiple Data)
  • 单指令多数据流：SIMD架构的处理器在同一时刻执行同一条指令，但这条指令同时作用于多个（通常是向量或数组）数据单元上。这种设计广泛应用于图形处理器（GPU）、矢量处理器以及现代CPU的向量化扩展技术（如Intel的AVX、AMD的Vega SIMD等），能够高效地处理大规模数据并行问题。
  1. SIMT (Single Instruction Multiple Thread)
  • 单指令多线程：SIMT架构尤其与现代GPU的CUDA核心编程模型相关联。在NVIDIA的CUDA架构中，SIMT通过将多个线程组织成一个线程束（Warps）来实现，同一时间所有线程都会执行相同的指令，尽管每个线程可能访问不同的数据。然而，如果遇到分支指令，未命中的线程需要等待（动态调度），因此SIMT在某种程度上结合了SISD和MIMD的特点。
  1. MIMD (Multiple Instruction Multiple Data)
  • 多指令多数据流：MIMD架构的处理器 每个处理单元独立执行不同的指令，并作用于各自独立的数据集上。这种结构常见于多核CPU、分布式计算系统和一些并行处理机中，各处理单元拥有各自的控制逻辑和指令流，可以高度并行地执行不同任务，具有很高的灵活性和并发性。
  1. SPMD (Single Program, Multiple Data)
  • SPMD (Single Program, Multiple Data) 是一种并行计算模型，它描述了这样一种情况：多个处理单元（如CPU核心或GPU线程）执行同一个程序的不同副本，每个处理单元都拥有独立的本地数据集，并在全局上处理不同的数据部分。在SPMD模式下，尽管所有处理器执行的是相同的指令序列，但由于它们作用于不同的输入数据，因此可以同时完成一个大任务的不同子部分。这种模型常见于分布式和并行计算环境，比如高性能计算集群、多核系统以及GPU编程中。SPMD编程方式简化了代码编写，因为程序员只需要编写一份代码，而系统会自动将这份代码分布到多个计算资源上并行执行。它与MIMD架构有相似之处，但更强调单个程序被复制并在不同数据上独立执行的概念。例如，在MPI（Message Passing Interface）编程中，SPMD模型得到了广泛应用。

共享内存​

动态线程与静态线程​

静态线程（Static Threads）：

静态线程是在程序编译或加载时就已经确定了线程的数量和结构。程序员通常需要显式指定线程数量，并预先分配好各个线程将要执行的任务。静态线程的特点包括：

  1. 预设数量：在程序启动前就已知线程的具体数目。
  2. 生命周期长：一旦创建，线程在整个程序运行期间可能一直存在。
  3. 任务划分固定：各线程执行的任务范围在程序开始阶段就被明确界定。
  4. 资源分配提前：系统可以为每个线程预先分配固定的资源如栈空间等。

动态线程（Dynamic Threads）：

动态线程则是在程序运行过程中根据需求动态创建和销毁的。这种策略允许程序根据实际情况（如负载、数据量大小等）灵活地调整线程的数量，以优化性能和资源利用率。

  1. 按需创建：根据实际计算需求，在运行时创建新的线程，完成任务后可随时销毁。
  2. 生命周期短：动态线程可以根据任务的执行情况随时创建和结束，无需在整个程序生命周期内持续存在。
  3. 任务分配灵活：可以更灵活地分配工作任务给不同的线程，适应多变的计算环境和负载变化。
  4. 资源管理实时：系统在运行时动态地进行资源分配和回收，能够更好地利用系统资源。

不确定性​

  1. 执行顺序的不确定性：在异步并行环境中，多个任务可能在不同的时间开始，以不同的速度执行，或者在不同的时间结束。这意味着如果这些任务之间存在数据依赖性，那么它们的执行顺序可能会影响程序的最终状态。
  2. 结果的不确定性：由于执行顺序的不确定性，如果并行程序没有被正确设计以处理并发，那么程序的输出可能会因执行的不同而不同，即使输入数据是相同的。这在并发编程中被称为竞态条件（race condition）。
  3. 性能的不确定性：并行程序的性能可能受到多种因素的影响，包括任务调度策略、处理器间通信的延迟、内存访问模式等。这些因素的变化可能会导致程序性能的不确定性。
  4. 系统资源利用的不确定性：在并行系统中，系统资源（如CPU、内存、I/O）的使用可能会受到多个并发执行任务的影响。系统资源的竞争可能导致性能瓶颈，使得资源利用效率出现不确定性。

互斥锁、互斥量、锁​

在并行计算和多线程编程中，互斥锁（Mutex）、互斥量和锁这些术语经常被使用，它们通常指的是同一个概念，即用来保证多个线程或进程在访问共享资源时不会发生冲突的同步机制。

  1. 互斥锁（Mutex Lock）：

  • Mutex 是 Mutual Exclusion（互斥）的缩写。

  • 互斥锁用于保护共享资源，以防止多个线程同时访问，这可能导致数据竞争和不一致的结果。

  • 当一个线程获得了互斥锁，它就可以访问受保护的资源。在这个线程释放锁之前，其他任何试图获得这个锁的线程都会被阻塞。

  1. 互斥量（Mutex）：

  • 互斥量是实现互斥锁的对象或数据结构。

  • 在许多编程语言和操作系统中，互斥量是一个特定类型的变量，用来控制对共享资源的访问。

  • 互斥量通常具有两个基本操作：lock（或acquire）和unlock（或release）。线程首先尝试lock互斥量以获得对资源的独占访问权，完成资源操作后，线程必须unlock互斥量以允许其他线程访问资源。

  1. 锁（Lock）：

  • 锁是一个更广泛的术语，用来描述任何可以用来控制对共享资源访问的同步机制。

  • 锁可以是互斥锁，也可以是其他类型的锁，例如读写锁（允许多个读取者同时访问资源，但写入者需要独占访问）、自旋锁（线程在等待锁的释放时不断检查而不是休眠）等。

线程安全性​

线程安全性（Thread Safety）指的是在多线程环境下，代码能够安全地被多个线程同时调用而不引起任何问题，如数据损坏或不一致的结果。线程安全的代码可以正确地处理多个线程可能同时进行的读写操作，确保共享数据的完整性和一致性。

通常当一段代码不是线程安全的，通常是因为不同的线程在访问共享数据时出了问题

分布式内存​

消息传递​

分布式内存的消息传递是一种并行计算模型，其中每个进程有自己的私有内存空间，进程之间通过发送和接收消息来交换数据。这与共享内存模型不同，在共享内存模型中，所有进程共享同一块内存空间。

在消息传递模型中，进程必须显式地发送消息给其他进程，并从其他进程接收消息。消息传递通常使用库来实现，例如消息传递接口（MPI）是这种通信方式的一个常见标准。

  1. 阻塞（Blocking）：

  • 阻塞调用是指进程在发送或接收操作完成之前，不会执行后续的指令。例如，在阻塞发送操作中，进程会等待直到消息数据被复制到网络缓冲区后才继续执行；在阻塞接收操作中，进程会等待直到相应的消息到达并被处理后才继续执行。

  • 阻塞调用可以简化程序逻辑，因为在调用之后，程序员可以确信操作已经完成。

  1. 非阻塞（Non-blocking）：

  • 与阻塞调用相对的是非阻塞调用，它允许进程发起一个操作然后立即继续执行后续指令，而不必等待操作完成。

  • 非阻塞调用可以提高程序的性能，因为它允许进程在等待通信完成的同时执行其他计算任务。

  1. 广播（Broadcast）：

  • 广播是一种通信模式，在这种模式下，一个进程发送相同的消息给所有其他进程。

  • 在MPI中，广播操作可以由一个单独的调用来实现，例如MPI_Bcast函数。

  1. 规约（Reduction）：

  • 规约操作是一种将所有进程中的数据进行组合的操作，通常是为了进行某种计算，比如求和、求最大值、求最小值等。

  • 在MPI中，规约操作可以使用MPI_Reduce函数来实现。这个函数会收集所有进程的输入数据，对它们应用一个规约操作，并将结果发送到一个指定的根进程。

这些消息传递操作是分布式内存并行程序设计的基础，它们允许开发者在多个计算节点上构建复杂的并行算法，而这些计算节点可能位于不同的物理位置。

混合系统编程​

在并行计算中，混合系统编程（Hybrid Programming）是指结合使用多种并行编程模型来利用现代高性能计算系统的多层次并行性。现代系统通常包括多核处理器、多处理器节点以及可能的多节点集群，每一层都可以采用不同的并行编程技术。

混合系统编程的常见模式包括：

  1. 多线程与消息传递：

  • 在单个节点内部使用多线程模型（如OpenMP或POSIX线程）来利用多核处理器的并行性。

  • 在节点间使用消息传递模型（如MPI）来处理节点间的通信。

  1. 共享内存与分布式内存：

  • 在单个节点内部使用共享内存模型，允许所有核心访问同一内存空间。

  • 在多节点系统中使用分布式内存模型，每个节点有自己的内存空间，节点间通过网络通信。

  1. 加速器（如GPU）与CPU：

  • 使用CUDA或OpenCL等技术在加速器（如GPU）上进行并行计算。

  • 同时使用CPU进行其他计算任务，或者处理不适合在加速器上运行的代码。

混合系统编程的主要优点是能够最大化并行性能和资源利用率。例如，在一个具有多个多核处理器的集群上，可以在每个核心上运行一个线程（使用OpenMP或其他线程库），同时在集群的不同节点间使用MPI进行通信。

混合编程模型的挑战在于需要对不同的并行编程技术都有深入的了解，并且需要精心设计程序以避免复杂的同步和通信问题。此外，调试和性能调优也比单一编程模型更为复杂。

性能​

在并行计算中，加速比（Speedup）和效率（Efficiency）是衡量并行程序性能的两个关键指标。它们可以帮助我们理解并行化一个问题在时间上的节省以及资源利用的有效性。

加速比​

加速比是衡量并行算法相对于最优的串行算法的性能提升。它定义为串行执行时间与并行执行时间的比值：

S(p)=TsTp(p) S(p) = \frac{T_s}{T_p(p)}

其中：

  • S(p)S(p) 是使用 pp 个处理器时的加速比。

  • TsT_s 是最优的串行算法的执行时间。

  • Tp(p)T_p(p) 是并行算法在 pp 个处理器上的执行时间。

理论上，最佳的加速比是 pp，这意味着如果你使用 pp 个处理器，那么程序的执行时间将是单个处理器上的 1/p1/p。然而，由于通信、同步和分解开销，实际加速比往往小于 pp。

Amdahl's Law简述​

Amdahl's Law 给出了一个理论上的加速比上限，它假设程序只有一部分可以并行化。公式如下：

S(p)=1(1−f)+fp S(p) = \frac{1}{(1 - f) + \frac{f}{p}}

其中 ff 是程序中可并行化的部分。Amdahl's Law 强调了并行化的固有限制，即使是在无限数量的处理器上，加速比也受到了不可并行化部分的限制。

效率​

效率是衡量处理器利用程度的指标，定义为加速比与处理器数量的比值：

E(p)=S(p)p=Tsp⋅Tp(p)E(p) = \frac{S(p)}{p} = \frac{T_s}{p \cdot T_p(p)}

效率的理想值是 1（或者 100%），表示所有的处理器都被完全利用，没有任何浪费。在实际中，由于并行开销，效率通常会低于 1。

效率可以受到多种因素的影响，包括：

  • 通信开销：处理器之间的数据交换可以降低效率。

  • 负载不平衡：如果某些处理器忙于工作，而其他处理器空闲，则效率会降低。

  • 同步开销：等待其他处理器完成任务会造成时间浪费。

  • 串行部分：根据Amdahl's Law，程序中的串行部分限制了加速比和效率。

在设计并行程序时，开发者需要尽量减少这些开销和不平衡，以提高加速比和效率。这通常涉及算法和数据结构的优化，以及对并行计算平台的深入理解。

效率与规模的关系​

效率与规模的关系在并行计算中是一个重要的考虑因素。这种关系通常受到两个主要因素的影响：问题的规模（即工作量或数据集的大小）和并行系统的规模（即处理器的数量）。这里有几个关键的概念来描述这种关系：

  1. 可扩展性（Scalability）：一个并行程序的可扩展性是指它在增加更多的处理器来处理更大的数据集时，能够保持效率或加速比的能力。一个良好的可扩展性意味着当系统规模增加时，效率不会显著下降。
  2. 强可扩展性（Strong Scalability）：如果一个并行程序处理一个固定大小的问题，当增加处理器数量时，它能够保持每个处理器的工作量几乎不变，并且执行时间相应减少，那么这个程序具有强可扩展性。在这种情况下，效率相对稳定，因为每个处理器都有足够的工作来保持忙碌。
  3. 弱可扩展性（Weak Scalability）：如果增加处理器数量的同时也相应地增加问题的大小，以保持每个处理器上的工作量不变，那么我们考察的是弱可扩展性。理想情况下，即使问题规模和处理器数量增加，效率也应保持不变。
  4. Amdahl 定律和 Gustafson 定律：Amdahl 定律强调了程序中串行部分对加速比和效率的限制，而 Gustafson 定律则提出，在增加问题规模的情况下，整体的加速比可以通过增加并行部分的工作量来提高，从而可能保持或提高效率。

在实际中，效率通常随着处理器数量的增加而下降，原因包括：

  • 通信开销：在更多的处理器之间进行通信会增加总体开销，特别是当通信不是很好地与计算操作重叠时。

  • 负载不平衡：随着处理器数量的增加，保持所有处理器同等忙碌变得更加困难。

  • 同步延迟：更多的处理器可能意味着更频繁的同步，这会导致效率下降。

  • 资源争用：处理器可能需要共享某些资源，如内存带宽，当处理器数量增加时，这种争用可能导致性能瓶颈。

通常来说，问题的规模越大，加速比和效率就越大，因为当规模增加时，进程或者线程有更多的任务去做，用于协调进程和新城的工作所需要的相对时间变少了，所以加速比和效率就会上升。

因此，合理选择问题规模和处理器数量，以及优化并行算法和实现，对于维持高效率至关重要。

阿姆达尔定律（Amdahl's Law）是由计算机科学家吉恩·阿姆达尔（Gene Amdahl）在1967年提出的，用来描述一个程序在并行化后可能获得的最大加速比。阿姆达尔定律的核心观点是，程序的加速比受到其串行部分的限制，即使无限增加处理器数量，加速比也不可能无限增加。

阿姆达尔定律​

阿姆达尔定律的公式可以表示为：

S(p)=1(1−P)+PpS(p) = \frac{1}{(1 - P) + \frac{P}{p}}

其中：

  • S(p)S(p) 是加速比，表示程序并行化后与未并行化前执行时间的比例。

  • PP 是程序中可以并行化的部分所占的比例（0 到 1 之间）。

  • (1−P)(1 - P) 是程序中必须串行执行的部分所占的比例。

  • pp 是用于并行计算的处理器数量。

根据阿姆达尔定律，如果一个程序的10%部分是串行的，即使其他部分完全并行化，最大加速比也只能达到10倍，因为当处理器数量无限增加时，加速比趋近于串行部分的倒数（在这个例子中是1/(1 - P) = 1/0.1 = 10）。

示例​

假设我们有一个程序，它的90%可以并行化（P=0.9P = 0.9），剩下的10%必须串行执行。我们想要计算使用4个处理器时的理论加速比。

应用阿姆达尔定律：

S(4)=1(1−0.9)+0.94=10.1+0.225=10.325≈3.08S(4) = \frac{1}{(1 - 0.9) + \frac{0.9}{4}} = \frac{1}{0.1 + 0.225} = \frac{1}{0.325} \approx 3.08

这意味着即使我们使用了4个处理器，最大理论加速比也只能是3.08倍，而不是4倍。

计时​

并行程序设计是指在多处理器或多核心计算机上同时执行多个计算任务的过程。并行计算可以显著提高程序的性能，尤其是在处理大规模数据集或执行复杂计算时。以下是并行程序设计的一些基础知识和并行计算中有关计时的内容。

并行计算中的计时​

  1. 墙钟时间（Wall-clock time）：也称为实际时间或经过时间，是指完成特定任务所需的真实世界时间。
  2. CPU时间：是指处理器花费在一个任务上的时间。在并行计算中，总CPU时间可能会超过墙钟时间，因为多个处理器可能同时工作。

计时工具和方法​

为了准确测量并行程序的性能，可以使用多种计时工具和方法：

  • 硬件计时器：许多处理器提供硬件支持的计时器，可以测量指令执行的确切周期数。

  • 软件计时器：操作系统提供的计时函数，如UNIX系统中的gettimeofday或C++11中的std::chrono库。

  • 性能分析工具：如gprof、VTune、TAU等，可以提供详细的性能分析报告。

Foster方法​

在并行计算中，Foster方法是一种设计并行算法和程序的方法论。它由Ian Foster提出，旨在帮助开发者系统地将问题和算法转化为有效的并行解决方案。Foster方法包括四个主要步骤：分解（Partitioning）、通信（Communication）、聚合（Agglomeration）和映射（Mapping）。下面详细介绍这四个步骤：

分解（Partitioning）​

分解是将整个计算任务分成多个小任务的过程，这些小任务可以并行执行。分解可以基于数据或任务：

  • 数据分解：将数据集分成多个子集，每个子集由不同的处理器并行处理。例如，在矩阵乘法中，可以将矩阵分成多个子矩阵，每个子矩阵由一个处理器处理。
  • 任务分解：根据算法的不同部分创建不同的任务，每个任务执行算法的一个特定部分。例如，在流水线处理中，每个任务可能执行流水线的一个阶段。

分解的目标是最大化并行执行任务的数量，同时最小化任务之间的依赖性，以减少同步和通信的开销。

通信（Communication）​

在分解步骤之后，需要确定任务之间的通信需求。这包括确定哪些数据需要在处理器之间传输，以及这些传输何时发生。通信可以分为两类：

  • 局部通信：如果并行任务需要频繁地交换数据，它们应该在物理上相互靠近以减少通信延迟。
  • 全局通信：涉及到所有或多个任务的数据交换，如广播和集合操作，通常更昂贵，需要仔细管理。

合理设计通信策略是确保高效并行执行的关键。

聚合（Agglomeration）​

在聚合步骤中，开发者将之前分解的任务进一步组合成更大的任务块，以减少通信开销和管理的复杂性。这个步骤涉及到权衡：

  • 将小任务组合成大任务可以减少通信次数，但可能会降低并行度。
  • 聚合还可以帮助优化资源利用率，如缓存利用和内存访问模式。

聚合的目标是找到任务大小和数量的最佳平衡点，以提高程序的整体性能。

映射（Mapping）​

最后一个步骤是将聚合后的任务映射到处理器上。这个步骤需要考虑：

  • 负载平衡：确保每个处理器都有大致相等的工作量，避免某些处理器过载而其他处理器空闲。
  • 亲和性：将相关任务映射到物理位置相近的处理器上，减少通信延迟。

映射策略应该考虑到处理器的数量、性能、内存等硬件资源的限制。