当前板块的编号： blockIdx • 总的板块数量： gridDim • 线程 (thread) ：并行的最小单位 • 板块 (block) ：包含若干个线程 • 网格 (grid) ：指整个任务，包含若干个板块 • 从属关系：线程＜板块＜网格 • 调用语法： <<>> 区分板块和线程有点麻烦？“扁平化”他们！ • 你可能觉得纳闷，既然已经有线程可以并行了 多个线程，并行地给数组赋值 • 刚刚的 for 循环是串行的，我们可以把线 程数量调为 n ，然后用 threadIdx.x 作为 i 索引。这样就实现了，每个线程负责给数 组中一个元素的赋值。 小技巧：网格跨步循环（ grid-stride loop ） • 无论调用者指定了多少个线程 （ blockDim ），都能自动根据给定的 n 区间循环，不会越界，也不会漏掉几个元 素。 • 这样一个 的习惯，又能自动匹配不同 的 blockDim ，看起来非常方便。 从线程到板块 • 核函数内部，用之前说到的 blockDim.x + blockIdx.x + threadIdx.x 来获取线程在整个 网格中编号。 • 外部调用者，则是根据不同的 n 决定板块的 数量（ gridDim ），而每个板块具有的线程 数量（ blockDim ）则是固定的 128 。 • 因此，我们可以用 n / 128

com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 本课涵盖：稀疏矩阵、 unordered_map 、空间稀 疏网格、位运算、浮点的二进制格式、内存带宽优 化 面向人群：图形学、 CFD 仿真、深度学习编程人 员 第 0 章：稀疏矩阵 稠密数组存储矩阵 用 foreach 包装一下枚举的过程 改用 map 按行压缩（ Compressed Row Storage ） http://www.netlib.org/linalg/html_templates/node91.html 第 1 章：稀疏网格 稠密网格计算粒子经过的格点数量 改用更小的 char 存储 只用一个 bit 存储，一个 char 可以存储 8 个 bit 用 map 来存储 读取：如果不存在，则读到 0 写入：如果不存在，则创建该表项 块优化。 实际上空间局域 性正是稀疏网格 能够实现的一大 前提，稍后详细 讨论。 在 16x16 分块的基础上，只用一个 bit 存储 图片解释稀疏的好处 传统稠密二维数组 无边界稀疏分块哈希表 有了无边界的稀疏网格，再也不用担心二维数组要分配多大了。 坐标可以无限延伸，甚至可以是负数！比如 (-1,2) 等…… 他会自动在写入时分配 16x16 的子网格，称之为叶节点 (leaf node)

矢量化的话可能还是要 SOA 或 AOSOA ，比如 hw04 那种的。而 “ pos 和 vel 应该用 SOA 分开存”是没问题的。 • 而且 SOA 在遇到存储不是 vector ，而是稀疏的哈希网格之类索引有一定 开销的数据结构，可能就不适合了。这就是为什么王鑫磊最喜欢 AOSOA ：在高层保持 AOS 的统一索引，底层又享受 SOA 带来的矢量化 和缓存行预取等好处……就是随机索引比较麻烦。 其实操作系统惰性分配的特性，也是 SPGrid （ Sparsely-Paged-Grid ）得以实现的基础 ，他利用 mmap 分配比机器大得多的内存（比如 2048*2028*1024 的三维网格），然后 在里面索引，这样就相当于利用硬件的分页机制实现了稀疏数据结构，既能高效利用内存 ，随机访问和插桩又特别高效。有兴趣可以研究一下他们的论文，也用了莫顿序增强 TLB 和缓存的局域性，非常精彩。 元素。图 像处理中用到的模糊操作，也需要向上下左右扩散 w 个单位。 • 这样假如当前元素正好在二维网格的边界上，那再往外索引 w 个单位就会超出数组的界限，导致出错。对此有多种解决办法 ： 1. 使用 std::max(n, std::min(0, i)) 限制索引不要超出二维网格的 大小，但会导致难以 SIMD 矢量化。 2. 使用 (i + n) % n 让索引在边界产生回绕，但是更加低效也难

约束满足问题：这类问题的目标是找到满足所有约束条件的解。 ‧ ? 皇后：在 ? × ? 的棋盘上放置 ? 个皇后，使得它们互不攻击。 ‧ 数独：在 9 × 9 的网格中填入数字 1 ~ 9 ，使得每行、每列和每个 3 × 3 子网格中的数字不重复。 ‧ 图着色问题：给定一个无向图，用最少的颜色给图的每个顶点着色，使得相邻顶点颜色不同。 组合优化问题：这类问题的目标是在一个组合空间中找到满足某些条件的最优解。 为了更形象地展示解题步骤，我们使用一个经典问题「最小路径和」来举例。 � 给定一个 ? × ? 的二维网格 grid ，网格中的每个单元格包含一个非负整数，表示该单元格 的代价。机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角 单元格。请返回从左上角到右下角的最小路径和。 例如以下示例数据，给定网格的最小路径和为 13 。 Figure 14‑10. 最小路径和示例数据 第一步：思考每轮的决策，定义状态，从而得到 [?, ?] 。 状态 [?, ?] 对应的子问题为：从起始点 [0, 0] 走到 [?, ?] 的最小路径和，解记为 ??[?, ?] 。 至此，我们就得到了一个二维 ?? 矩阵，其尺寸与输入网格 ???? 相同。 14. 动态规划 hello‑algo.com 284 Figure 14‑11. 状态定义与 dp 表 � 动态规划和回溯过程可以被描述为一个决策序列，而状态由所有决策变量构成。它应当包含

迭代因为需要写入 pre 的同时读取 pre ，所以也要用双缓冲。 投影部分：计算未消除的散度 为了评估效果的好坏，额外加一个计算散度方差的核函数，看看是不是无散度（不可压缩流）了。 多重网格法 投影部分：多重网格实现 投影部分：红黑高斯 投影部分：计算残差 投影部分：缩小一倍 投影部分：清零数组 投影部分：扩大一倍 创建与导出 主函数：创建场景 导出 VDB ：调用接口 导出 VDB OpenVDB 在 Blender 中查看导出的结果 边界条件 边界条件：初始化 边界条件：添加判断边界的版本 边界条件：仅在第一层额外判断边界条件 进一步改进 VDB 导出：支持导出多个网格，并指定名称 进一步改进 VDB 导出： P-IMPL 模式 进一步改进 VDB 导出： F-IMPL 模式 Blender 渲染结果 改进 改进边界条件：外部边界流出而不是反弹，内部边界可以流出速度

约束满足问题：这类问题的目标是找到满足所有约束条件的解。 ‧ ? 皇后：在 ? × ? 的棋盘上放置 ? 个皇后，使得它们互不攻击。 ‧ 数独：在 9 × 9 的网格中填入数字 1 ~ 9 ，使得每行、每列和每个 3 × 3 子网格中的数字不重复。 ‧ 图着色问题：给定一个无向图，用最少的颜色给图的每个顶点着色，使得相邻顶点颜色不同。 组合优化问题：这类问题的目标是在一个组合空间中找到满足某些条件的最优解。 问题“最小路径和”来举例。 Question 给定一个 ? × ? 的二维网格 grid ，网格中的每个单元格包含一个非负整数，表示该单元格的代价。 机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角单元格。请返回 从左上角到右下角的最小路径和。 图 14‑10 展示了一个例子，给定网格的最小路径和为 13 。 图 14‑10 最小路径和示例数据 第一步：思考每轮的决策，定义状态，从而得到 状态 [?, ?] 对应的子问题为：从起始点 [0, 0] 走到 [?, ?] 的最小路径和，解记为 ??[?, ?] 。 至此，我们就得到了图 14‑11 所示的二维 ?? 矩阵，其尺寸与输入网格 ???? 相同。 第 14 章 动态规划 hello‑algo.com 314 图 14‑11 状态定义与 dp 表 Note 动态规划和回溯过程可以描述为一个决策序列，而状态由所有决策变量构成。它应当包含描述解题进

约束满足问题：这类问题的目标是找到满足所有约束条件的解。 ‧ ? 皇后：在 ? × ? 的棋盘上放置 ? 个皇后，使得它们互不攻击。 ‧ 数独：在 9 × 9 的网格中填入数字 1 ~ 9 ，使得每行、每列和每个 3 × 3 子网格中的数字不重复。 ‧ 图着色问题：给定一个无向图，用最少的颜色给图的每个顶点着色，使得相邻顶点颜色不同。 组合优化问题：这类问题的目标是在一个组合空间中找到满足某些条件的最优解。 为了更形象地展示解题步骤，我们使用一个经典问题“最小路径和”来举例。 � 给定一个 ? × ? 的二维网格 grid ，网格中的每个单元格包含一个非负整数，表示该单元格 的代价。机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角 单元格。请返回从左上角到右下角的最小路径和。 图 14‑10 展示了一个例子，给定网格的最小路径和为 13 。 图 14‑10 最小路径和示例数据 第 14 章 状态 [?, ?] 对应的子问题为：从起始点 [0, 0] 走到 [?, ?] 的最小路径和，解记为 ??[?, ?] 。 至此，我们就得到了图 14‑11 所示的二维 ?? 矩阵，其尺寸与输入网格 ???? 相同。 图 14‑11 状态定义与 dp 表 � 动态规划和回溯过程可以被描述为一个决策序列，而状态由所有决策变量构成。它应当包含 描述解题进度的所有变量，其包含了足够的信息，能够用来推导出下一个状态。

约束满足问题：这类问题的目标是找到满足所有约束条件的解。 ‧ ? 皇后：在 ? × ? 的棋盘上放置 ? 个皇后，使得它们互不攻击。 ‧ 数独：在 9 × 9 的网格中填入数字 1 ~ 9 ，使得每行、每列和每个 3 × 3 子网格中的数字不重复。 ‧ 图着色问题：给定一个无向图，用最少的颜色给图的每个顶点着色，使得相邻顶点颜色不同。 组合优化问题：这类问题的目标是在一个组合空间中找到满足某些条件的最优解。 为了更形象地展示解题步骤，我们使用一个经典问题“最小路径和”来举例。 � 给定一个 ? × ? 的二维网格 grid ，网格中的每个单元格包含一个非负整数，表示该单元格 的代价。机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角 单元格。请返回从左上角到右下角的最小路径和。 图 14‑10 展示了一个例子，给定网格的最小路径和为 13 。 图 14‑10 最小路径和示例数据 第一步：思考每轮的决策，定义状态，从而得到 状态 [?, ?] 对应的子问题为：从起始点 [0, 0] 走到 [?, ?] 的最小路径和，解记为 ??[?, ?] 。 至此，我们就得到了图 14‑11 所示的二维 ?? 矩阵，其尺寸与输入网格 ???? 相同。 第 14 章 动态规划 hello‑algo.com 316 图 14‑11 状态定义与 dp 表 � 动态规划和回溯过程可以描述为一个决策序列，而状态由所有决策变量构成。它应当包含描

约束满足问题：这类问题的目标是找到满足所有约束条件的解。 ‧ ? 皇后：在 ? × ? 的棋盘上放置 ? 个皇后，使得它们互不攻击。 ‧ 数独：在 9 × 9 的网格中填入数字 1 ~ 9 ，使得每行、每列和每个 3 × 3 子网格中的数字不重复。 ‧ 图着色问题：给定一个无向图，用最少的颜色给图的每个顶点着色，使得相邻顶点颜色不同。 组合优化问题：这类问题的目标是在一个组合空间中找到满足某些条件的最优解。 问题“最小路径和”来举例。 Question 给定一个 ? × ? 的二维网格 grid ，网格中的每个单元格包含一个非负整数，表示该单元格的代价。 机器人以左上角单元格为起始点，每次只能向下或者向右移动一步，直至到达右下角单元格。请返回 从左上角到右下角的最小路径和。 图 14‑10 展示了一个例子，给定网格的最小路径和为 13 。 图 14‑10 最小路径和示例数据 第一步：思考每轮的决策，定义状态，从而得到 状态 [?, ?] 对应的子问题为：从起始点 [0, 0] 走到 [?, ?] 的最小路径和，解记为 ??[?, ?] 。 至此，我们就得到了图 14‑11 所示的二维 ?? 矩阵，其尺寸与输入网格 ???? 相同。 第 14 章 动态规划 www.hello‑algo.com 314 图 14‑11 状态定义与 dp 表 Note 动态规划和回溯过程可以描述为一个决策序列，而状态由所有决策变量构成。它应当包含描述解题进

态的虚函数，这就是被小彭老师称为自动 虚克隆 (auto-vitrual-clone) 的大法。 Zeno 中对 OpenVDB 对象的封装 • 开源的体积数据处理库 OpenVDB 中有许多“网格”的类（可以理解为多维数组），例如： • openvdb::Vec3fGrid ， FloatGrid ， Vec3IGrid ， IntGrid ， PointsDataGrid • 我们并不 之类的任意表达式，只要语义上通过，就可以实例化。 • （把 sort 封装成虚函数，留作回家作业） Zeno 中对 OpenVDB 的类型擦除 • 结合类型擦除技术，自动虚克隆技术。 • VDBGrid 作为所有网格类的基类提供各个 操作做为虚函数， VDBGridWrapper 则是 那个实现了擦除的包装类。 Zeno 节点系统 • 节点在 Zeno 中所扮演的角色，实际上相当于函数式编程中的函数。