L. 洪水 困兽¶

分数：80 分

背景¶

你是一名游戏开发者，正在开发一款名为《洪水 困兽》的游戏。在《洪水 困兽》的游戏中，玩家将被置于一个动态变化的环境中。这个环境由一系列的地形组成，包括山丘、森林、河流和洞穴。随着游戏的进行，洪水将逐渐淹没这些地形，玩家需要引导小狗在洪水到来之前找到安全的地方。

小狗的移动速度会受到地形的影响。例如，在山丘上，小狗的移动速度会降低，但是可以获得更好的视野；在森林中，小狗可以躲避洪水，但是视野会受到限制；在河流中，小狗的移动速度会增加，但是方向控制会变得困难。此外，游戏中还有一些特殊的地形，如瀑布和漩涡，它们会对小狗的移动产生特殊的影响。玩家需要利用这些地形的特性，制定出逃离洪水的策略。

游戏的目标是让小狗在洪水淹没整个环境之前逃离出来。每次成功逃离，游戏的难度将会增加，洪水的速度会变快，地形会变得更加复杂。玩家需要不断地挑战自己，提高自己的策略和操作技巧，才能在游戏中取得更高的分数。

为了增加游戏的真实性，你决定在游戏中采用优越的粒子-网格混合方法进行流体模拟。这一过程大致如下图所示：

你的游戏引擎中已经实现了流体模拟，但是由于流体模拟的计算量较大，导致游戏的帧率较低。你想着：一帧能玩五帧流畅，于是直接发布了游戏，并在最低运行需求中写下了：CPU: AMD EPYC 9654 。

粒子-网格混合方法（PIC/FLIP, APIC）是计算机图形学流体仿真中十分流行的算法。纯粒子方法难以保证流体的不可压条件，纯网格方法难以精确表示和追踪流体的几何信息；而粒子-网格混合方法在一定程度上综合了二者的优点。

PIC/FLIP 的算法流程可简化为以下步骤：

• 粒子运动（advection）
• 粒子将速度转换到网格（particle2grid）
• 在网格上施加重力（external force）
• 在网格上求解流体不可压条件（projection）（bottleneck）
• 网格将速度转换到粒子（grid2particle）

从离散化速度场的角度，粒子方法用粒子存储速度，网格方法用格点存储速度，混合方法的关键步骤就是在两种存储速度的格式之间转换，即 particle2grid 和 grid2particle 。

直到有一天你的玩家给你发了一张这个图片：

你意识到你应当优化你的游戏，并把最低硬件要求降低至 CPU: Intel Xeon 8358 了。

你强迫自己仔细阅读了游戏引擎的代码，发现其中实现了粒子-网格混合方法的 particle2grid 过程，但是它是单线程的；然而，这一步的计算量非常大，这使得游戏渲染时无法达到流畅的帧率。因此，你决定将 particle2grid 过程并行化，以进一步提高游戏性能。

你计划使用多线程技术来实现这个目标。每个线程将负责处理一部分粒子，将它们的速度转换到网格上。这样，你可以在多个处理器核心上同时进行计算，大大减少了 particle2grid 过程的总计算时间。

然而，多线程编程并不简单。你需要确保所有线程都能正确地访问和修改共享数据，而不会发生数据竞争或者其他并发问题。此外，你还需要使用一个有效的线程调度策略，以确保所有线程都能得到充分的计算资源。为了解决这些问题，你决定使用一些并行编程的工具和技术，例如 OpenMP 。

你知道这将是一个挑战，但你也相信，只要你能成功实现这个并行化的 particle2grid 过程，你的游戏《洪水 困兽》就能达到流畅的帧率，给玩家带来更好的游戏体验。

任务描述¶

我们提供了一个 Handout，提供了串行版本代码和测试数据。你需要在 Handout 的基础上，使用 OpenMP 实现并行化的 particle2grid 过程。以下是对这一过程算法的详细介绍。

背景网格¶

流体模拟经常采用 Marker-And-Cell (MAC) 网格。对于二维的情况，速度总是存储在边中心。下图 $u$ 表示沿 $x$ 轴的横向速度，$v$ 表示沿 $y$ 轴的纵向速度；其余部分的速度使用插值得到；速度的 $x、y$ 轴分量分别从 $u$ 和 $v$ 两个不同的背景网格插值得到。

算法过程¶

在算法过程中，每一个粒子携带的信息会通过插值的形式赋值到网格格点。

本题中我们使用最简单的双线性插值格式，格点最终的速度值是 插值总速度/插值总权重 。

注意到，每个粒子速度的 $x、y$ 分量是分别插值到 $u、v$ 两个不同的背景网格。Handout 中代码已给出索引 $u、v$ 格点和计算权重的代码。输入数据来自流体模拟，保证不发生越界访问。

同时我们注意到，同一个网格会有多个粒子。这意味着直接并行这个过程会出现写入冲突。

评分标准¶

你的程序将采用与 Handout 中相同的方式编译运行，运行时分配单节点 64 个核心。我们会使用超级快速文件系统，所以你不会特别需要优化输入输出部分。对于选手的输出数据，我们允许合理范围的浮点误差。评测程序将会对你的程序进行多组测试，每组测试都会有一个测试样例。每组测试的给分情况见下表。其中第一个参数是 resolution，格点一共是 $resolution \times resolution$ 个。第二个参数是 num_marker ，意思是平均每点粒子数。

附件路径¶

• Handout