地下水质量计算的并行算法
在科学计算中，我们经常处理大量数据，需要大量的计算机时间。因此，研究并行和分布式算法是计算机发展时代的一项重要需求。在本文中，我讨论了求解抛物线偏微分方程形式的工程力学问题的算法实现，特别是地下水中污染物迁移和扩散的问题。问题的算法是在运行 Linux 的异构计算机网络中实现的。因此，我们将获得一个分布式网络，其中包括多台计算机形式的多个处理器。这台多计算机形成了一个 并行虚拟机 (PVM)。为 PVM 系统开发应用程序遵循了传统的分布式内存多处理器编程范式，例如 nCUBE 或 Intel 系列多处理器。这种范式可以细分为两类
主从（主机-节点）模型，其中一个单独的 控制 程序（称为主程序）负责进程生成、初始化、结果收集和显示以及函数计时。从程序执行实际计算；它们的工作负载由主程序分配（静态或动态），或者它们自己执行分配。
仅节点模型，其中单个程序的多个实例执行，一个进程（通常是手动启动的进程）除了参与计算外，还承担非计算职责。
在本文中，我们应用并行算法来计算地下水污染物质资源的扩散 S(t,x,y)，使用以下方程。这是拟线性方程形式的演化问题
图 1
其中变量定义如下
- s：环境的海绵系数
- K：渗透系数
- L：弥散度
- z = z(t,x,y)：地下水自由表面
- zd = zd(x,y)：导向面
- Q = Q(t,x,y)：污染物质资源
我们使用差分方法离散化问题。因此，我们将获得两个三对角线性方程组。使用这些方程，我们可以计算得到时间点为 (n+0.25)Dt 和 (n+0.50)Dt 时的污染浓度 Sn+0.25、Sn+0.50。并行算法的流程图如图 1 所示。
图 1. 流程图
值 Sn+0.25 和 Sn+0.50 在构成共享或本地内存多处理器的虚拟机的两个处理器上同时计算。
PVM 是一个可移植的消息传递编程系统，旨在连接独立的宿主机以形成“虚拟机”，这是一个单一、可管理的计算资源。虚拟机可以由物理位置偏远的各种类型的主机组成。PVM 应用程序可以由任意数量的独立进程或组件组成，这些进程或组件可以用 C/C++ 和 FORTRAN 的混合编写。该系统可移植到各种架构，包括工作站、多处理器、超级计算机和 PC。最常见的 PVM 平台是 UNIX，目前它在 30 多个不同的平台上运行。
在主从模型中，主程序生成并指导多个从程序执行计算。PVM 不限于此模型。例如，任何 PVM 任务都可以在机器上启动进程；然而，主从模型是一种有用的编程范式，并且易于说明。主程序调用 pvm_mytid，作为第一个 PVM 调用，它将此任务注册到 PVM 系统中。然后，它调用 pvm_spawn 以在 PVM 中其他机器上执行给定数量的从程序。主程序包含一个在 PVM 中广播消息的示例。主程序向从程序广播启动的从程序数量以及所有从程序 tid（任务 ID）的列表。每个从程序调用 pvm-tid 以确定其在虚拟机中的任务 ID，然后使用从主程序广播的数据创建从 0 到 nproc 减 1 (nproc-1) 的唯一排序，其中 nproc 是从进程的数量。随后，pvm_send 和 pvm_recv 用于在进程之间传递消息。完成后，所有 PVM 程序都调用 pvm_exit，以允许 PVM 断开与进程的任何套接字，刷新 I/O 缓冲区并跟踪当前正在运行的进程。
SPMD（单程序多数据）模型仅包含单个程序，没有主程序指导计算。此类程序有时称为无主机程序。然而，所有进程仍然需要最初启动。用户启动程序的第一个副本；通过检查 pvm_parent，第一个副本可以确定它不是由 PVM 生成的，因此可以知道自己是第一个副本。然后，它生成自身的多个副本并将 tid 数组传递给它们。此时，每个副本都是相等的，并且可以与其他进程协作处理其数据分区。使用 pvm_parent 阻止从 PVM 控制台启动 SPMD 程序，因为 pvm_parent 将返回控制台的 tid。这种类型的 SPMD 程序必须从 UNIX 提示符启动。
对于我们的程序，我们使用了主从编程模型。主程序生成从程序的副本到另一个处理器以计算 Sn+0.25，并自行计算 Sn+0.50。当两个处理器都完成计算后，主程序将计算总和 Sn+1 = 0.5(Sn+0.25 + Sn+0.50)。当最终步长时间完成时，程序将完成。计算 Sn+0.25 和 Sn+0.25 的并行计算进度如图 2 所示。
图 2. 并行计算的进度
线性系统方程也存在于主程序和从程序中，因此我们还使用主从编程模型通过二阶线性递推求解三对角系统。可以实现霍纳算法以在 O(log2n) 中运行在单个点评估度为 n 的多项式。如果我们使用三对角矩阵 LDU 分解的顺序算法，我们将在 O(n) 中运行它。
