通过并行性优化性能
在本文中，我们将通过一个例子，探讨如何在对称多处理（共享内存）以及分布式内存环境中，将串行算法转换为具有更高性能的算法。为了完成这项任务，我们将分三个阶段开发一个简单的应用程序：串行版本、多线程版本和分布式多线程版本。
除了并行编程的理论方面，我们还将讨论编程时遇到的一些实际问题。我们选择用 C++ 实现所有示例，并分别使用 POSIX 线程 (pthreads) 和 MPI 库进行对称多处理和分布式处理。
在我们的实现中，我们选择用一个对象来表示数字范围，该对象具有计数其范围内素数数量的能力（见列表 1）。
这是一个编译和使用程序的示例
bash$ g++ -o primes primes.cpp bash$ ./primes 0 10000 There were 1229 primes.
为了提高我们的示例在对称多处理 (SMP) 机器上的速度，我们需要使用线程。我们希望坚持前一个示例中的设计，这意味着我们需要找到一种方法，使每个对象都有自己的执行线程。不幸的是，混合使用 C++ 和 pthreads 并非易事，因为 pthread_create() 期望一个使用 C 风格链接而不是 C++ 链接的函数。我们通过创建一个辅助类和一个静态成员函数来解决这个问题（见列表 2）。
CountPrimes 对象的其余实现部分保持不变。有三点需要注意：1) Threaded 类是一个抽象类。2) entry() 函数是一个静态成员函数，这意味着它了解 Threaded 类的详细信息，但不与特定实例绑定。因此，它不会经过名称修饰，并且可以用作 C 风格的函数。这是我们将传递给 pthread_create() 的函数指针，以及指向要线程化的对象的指针。3) run() 成员函数是 纯虚函数，因此必须由任何从 Threaded 派生的类来实现。此函数将是派生类的主执行点，其返回值将表示计算结果。在我们的 CountPrimes 类中，此函数只是计算范围的总数并返回它。
我们希望保留串行实现的用法形式，因此只添加一个额外的参数来控制将要生成以完成任务的线程数。因为我们事先不知道需要多少对象（线程），所以我们将动态分配它们（见列表 3）。
此示例中还有一些更细微之处，因此我们将更详细地介绍代码。首先，我们将默认线程数设置为 2，然后检查用户是否指定了另一个值。我们创建一个 pthread_t 的动态数组来存储线程 ID，然后创建一个指向 CountPrimes 对象的指针的动态数组。这很重要，因为我们需要用不同的范围实例化每个对象。实际上，我们无法创建 CountPrimes 对象的静态数组，因为没有默认构造函数。此设计迫使我们正确使用该对象。
接下来是一个循环，它将生成各个线程，并为它们分配各自要检查的数字范围。请注意，我们在此处没有尝试负载均衡。我们稍后会回到这个概念。重要的一点是，每个 CountPrimes 对象都是动态实例化的，并且它的指针存储在上面创建的数组中。线程实际上是通过 thread_create() 生成的。我们将指向 entry 成员函数的指针和指向对象本身的指针传递给它。生成的线程的 ID 存储在线程 ID 数组中。
接下来，我们通过在线程 ID 上使用 pthread_join() 来等待线程完成计算它们的总数。因为我们在 run() 中动态分配了返回值的空间，所以我们必须在此处释放它。每个线程的总数都添加到 count 中。
最后，CountPrimes 对象被释放，线程 ID 数组和计数器对象指针数组也被释放。这是一个编译和使用程序的示例
bash$ g++ -o primes_threaded primes_threaded.cpp bash$ ./primes_threaded 0 10000 4 There were 1229 primes.
消息传递接口 (MPI) 是用于实现分布式程序的标准 API。使用 MPI 有许多优点，但主要优点是程序在源代码级别上是兼容的，而与所使用的特定 MPI 实现无关。在接下来的讨论中，我们将假设可以安装正确配置的局域网多计算机 (LAM)，以及来自圣母大学的 MPI 实现（请参阅“资源”部分）。
分布式编程中使用的一种非常常见的模型是主/从模型。在此模型中，有一个称为“主”进程，它创建工作并将工作分发给“从”进程。“从”进程向“主”进程响应其已完成的工作，并在有更多工作时请求更多。这种概念上简单的模型非常适用于不需要大量同步且其“从”进程可以完全自主的问题。这些类型的问题通常被称为 易于并行化。
为了在我们线程实现的基础上构建，我们需要决定如何根据主/从模型重新制定我们的实现，并添加对 MPI 的必要调用，以便分发我们的问题并收集结果。列表 4 显示了对 main() 的更改。
我们需要在分布式程序的开头调用 MPI_Init()，以便连接到多计算机。接下来的两个函数调用建立我们的等级和将参与计算的计算机总数。
MPI 将在多计算机中的每台计算机上启动相同的程序。这就是为什么我们需要在运行时确定我们的等级，以便我们可以决定我们是主进程还是从进程。根据我们的等级，我们调用 master() 或 slave()。
在我们完成计算后，我们必须调用 MPI_Finalize() 来释放我们与多计算机的连接。
我们的 slave() 函数只接受一个参数，即要使用的线程数。这使我们能够充分利用集群中 SMP 机器的处理能力。
从进程的目的是坐下来等待工作，执行工作，然后返回结果。它将继续这样做，直到收到没有更多工作要做的信号，此时它将返回（见列表 5）。
slave() 函数中的大部分代码与我们的线程示例中的 main() 类似。唯一的区别是从进程如何获取它应该在其中计数素数的边界以及如何返回这些结果。
从进程进入一个无限循环，等待来自主进程的工作，它通过 MPI_Recv() 获取工作。此函数获取主进程发送的两个 longs，并将它们存储在 bounds 数组中。从进程从主进程接收后，检查消息的状态，以查看工作是否完成（KILL 消息），如果是，则返回。否则，我们重命名变量，以便我们可以使用与线程版本完全相同的代码。剩下的唯一步骤是通过 MPI_Send() 将我们的结果发送回主进程。在这里，我们发送回一个 long，其中包含此从进程找到的计数。
主进程的工作稍微复杂一些，因为它必须决定如何分解要发送给从进程的工作以及如何收集结果。主进程的第一部分将初始工作单元发送给从进程，并等待结果返回。当主进程收到结果时，如果仍有工作要做，则向同一进程发送另一个工作单元。在没有更多工作要发送出去之后，再次轮询每个进程以获取任何剩余结果，然后告诉每个从进程退出（见列表 6）。
make_work() 函数负责决定何时完成工作以及如何分解工作。我们选择了一个简单的顺序模型，其中块的大小由 STEP_SIZE 确定（见列表 7）。
STEP_SIZE 变量是控制机器之间负载均衡的关键。如果它太大，则某些机器可能保持空闲，而少数机器处理范围高端的数字。如果它太小，则会产生过多的通信开销。这些因素通常更容易通过实验来确定。这些细节将在“性能”部分中进一步探讨。
MPI 程序使用 mpicc 或 mpiCC 编译，具体取决于您分别编译的是 C 代码还是 C++ 代码。要运行分布式程序，您必须首先通过 lamboot 引导多计算机，然后可以使用 mpirun 命令运行您的程序。当您完成 MPI 会话时，可以使用 wipe 关闭多计算机
bash$ mpiCC -O -o primes_mpi primes_mpi.cpp -lpthread bash$ lamboot LAM 6.3.2/MPI 2 C++/ROMIO - University of Notre Dame bash$ mpirun -O -np 16 primes_mpi -- 0 10000000 There were 664579 primes. bash$ wipe
如果您在成功运行 lamboot 时遇到困难，可以使用 recon 命令来验证可能导致您遇到麻烦的原因。如果 recon 失败，则可能是您无法在远程计算机上运行命令而不输入密码。如果您正在使用 ssh，请确保已将 LAMRSH 设置为反映这一点
bash$ export LAMRSH=`which ssh`mpicc 的参数与您通常直接传递给编译器的参数基本相同。一个例外是 mpicc 和 mpirun 的 -O 参数，它指定多计算机是同构的，并且不需要执行字节序转换。mpirun 的 -np 参数指定要启动的进程数（通常是多计算机中的节点数）。双破折号 (--) 之后的所有参数都作为参数传递给正在运行的主程序。
为了证明并行编程的有效性，我们必须证明我们程序的并行版本的运行时间（挂钟时间）更短。一般来说，除非问题是粗粒度的并且需要很少的同步，否则不可能获得每个节点 100% 的性能提升。
我们的测试是在一个包含 16 个双 PIII 700MHz 处理器和 384MB RAM 的集群上进行的。我们运行该程序以计算 0 到 10,000,000 之间的素数数量。以下是我们迄今为止开发的三个版本的程序的运行时间
单节点串行实现：6:29.28 秒。
单节点多线程实现：3:24.24 秒。
16 节点分布式（和多线程）实现：11.05 秒。
这些结果表明，我们获得了每个处理器性能的线性增长（比串行版本快 32 倍）。
编程多计算机时遇到的最大问题之一是使每台计算机以及 SMP 计算机中的每个处理器尽可能繁忙。我们希望避免在等待另一台计算机或处理器上执行的另一个计算的结果时，让多台机器处于空闲状态。这种精细的技巧被称为 负载均衡。
虽然对负载均衡的完整讨论超出了本文的范围，但我们可以检查我们正在解决的特定问题的一些属性，以尝试了解如何提高我们的性能。在我们的示例中执行大部分计算的单个函数是 is_prime() 函数。由于其性质，其时间与输入数字的大小成正比。考虑一下当使用两个线程时，我们如何在线程实现中分解问题：我们将一半的数字发送到一个线程，另一半的数字发送到另一个线程。这是本质上不平衡的，因为我们按顺序划分数字。具有较低一半数字的线程将比具有较高一半数字的线程完成得早得多，因此一个处理器将处于空闲状态。至少有两种方法可以解决这个特定问题：在划分数字范围时，我们可以将每隔一个数字发送到每个线程，或者我们可以简单地使用更多线程，这将把问题分解成更小的块，并更多地依赖内核线程调度程序来平衡负载。这仅在调度花费的时间超过分解问题带来的收益的某个点上才有效。
在分布式实现中，我们使用了一种更强大的负载均衡方法来向机器发送作业：向每台机器发送较小的工作块，并且仅在它们完成初始工作后才向它们发送新工作。我们仍然需要稍微担心我们发送的工作块的大小（由我们实现中的 STEP_SIZE 变量控制），否则我们将增加我们的网络流量而不会提高我们的吞吐量。可以使用类似的方法来平衡线程，但为了清楚起见，没有使用。
