TBB 7.被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 调度，共享内存， barrier 9.并行算法实战： reduce ， scan ，矩阵乘法等 10.存储大规模三维数据的关键：稀疏数据结构 11.物理仿真实战：邻居搜索表实现 pbf 流体求解 12.C++ 在 ZENO 中的工程实践：从 primitive 说起 13.结业典礼：总结所学知识与优秀作业点评 什么是 xmm 系列寄存器？ • xmm 寄存器有 128 位宽。 • 可以容纳 4 个 float ，或 2 个 double 。 • 刚才的案例中只用到了 xmm 的低 32 位 用于存储 1 个 float 。 addss 是什么意思？ • 可以拆分成三个部分： add ， s ， s 1. add 表示执行加法操作。 2. 第一个 s 表示标量 (scalar) ，只对 xmm 的容器：我是说，内存分配在堆上的容器 • 存储在堆上（妨碍优化）： • vector, map, set, string, function, any • unique_ptr, shared_ptr, weak_ptr • 存储在栈上（利于优化）： • array, bitset, glm::vec, string_view • pair, tuple, optional, variant 存储在栈上无法动态扩充大小，这就是

blockDim ，看起来非常方便。 从线程到板块 • 核函数内部，用之前说到的 blockDim.x + blockIdx.x + threadIdx.x 来获取线程在整个 网格中编号。 • 外部调用者，则是根据不同的 n 决定板块的 数量（ gridDim ），而每个板块具有的线程 数量（ blockDim ）则是固定的 128 。 • 因此，我们可以用 n / 128 作为 gridDim CUDA 源码生效，这样可以混合其他 .cpp 文件也不会发生 gcc 报错的情况了。。 如何捕获外部变量？ • 如果试图用 [&] 捕获变量是会出错的，毕 竟这时候捕获到的是堆栈（ CPU 内存）上 的变量 arr 本身，而不是 arr 所指向的内 存地址（ GPU 内存）。 如何捕获外部变量？ • 你可能会想，是不是可以用 [=] 按值捕获 ，这样捕获到的就是指针了吧？ • 错了，不要忘了我们第二课说过， 错了，不要忘了我们第二课说过， vector 的拷贝是深拷贝（绝大多数 C++ 类都是深 拷贝，除了智能指针和原始指针）。这样 只会把 vector 整个地拷贝到 GPU 上！ 而不是浅拷贝其起始地址指针。 如何捕获外部变量？ • 正确的做法是先获取 arr.data() 的值到 arr_data 变量，然后用 [=] 按值捕获 arr_data ，函数体里面也通过 arr_data 来访问 arr 。

内部引入了一片极小的存储 器——虽然小，但是读写速度却特别快。这片小而快的 存储器称为缓存（ cache ）。 • 当 CPU 访问某个地址时，会先查找缓存中是否有对应的 数据。如果没有，则从内存中读取，并存储到缓存中； 如果有，则直接使用缓存中的数据。 • 这样一来，访问的数据量比较小时，就可以自动预先加 载到这个更高效的缓存里，然后再开始做运算，从而避 免从外部内存读写的超高延迟。 宽。三级缓存也装不下，那就取决于主内存 的带宽了。 • 结论：要避免 mem-bound ，数据量尽量足 够小，如果能装的进缓存就高效了。 L2: 256 KB L3: 12 MB 缓存的工作机制：读 • 缓存中存储的数据结构： • struct CacheEntry { • bool valid; • uint64_t address; • char data[64]; • }; 架构中每个条目的存储 64 字节的数据，这个条目 又称之为缓存行（ cacheline ）。 • 当访问 0x0048~0x0050 这 4 个字节时，实际会导致 0x0040~0x0080 的 64 字节数据整个被读取到缓存中。 • 这就是为什么我们喜欢把数据结构的起始地址和大小对齐到 64 字节，为的是不要浪费缓存行的存储空间。 缓存的工作机制：写 • 缓存中存储的数据结构：

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2 目录 目录 外部模板 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 尖括号 这两个关键字实现了类型推导，让编译器来操心变量的类型。这 使得 C++ 也具有了和其他现代编程语言一样，某种意义上提供了无需操心变量类型的使用习惯。 auto auto 在很早以前就已经进入了 C++，但是他始终作为一个存储类型的指示符存在，与 register 并 存。在传统 C++ 中，如果一个变量没有声明为 register 变量，将自动被视为一个 auto 变量。而随着 18 2.3 类型推导 第 2 章语言可用性的强化 态服务，进而大幅优化运行期的性能。因此模板也被很多人视作 C++ 的黑魔法之一。 外部模板 传统 C++ 中，模板只有在使用时才会被编译器实例化。换句话说，只要在每个编译单元（文件）中 编译的代码中遇到了被完整定义的模板，都会实例化。这就产生了重复实例化而导致的编译时间的增加。 并且，我们没有办法通知编译器不要触发模板的实例化。 为此，C++11 引入了外部模板，扩充了原来的强制编译器在特定位置实例化模板的语法，使我们能

1 章：添加源文件 一个 .cpp 源文件用于测试 CMake 中添加一个可执行文件作为构建目标 另一种方式：先创建目标，稍后再添加源文件 如果有多个源文件呢？ 逐个添加即可 使用变量来存储 建议把头文件也加上，这样在 VS 里可以出现在“ Header Files” 一栏 使用 GLOB 自动查找当前目录下指定扩展名的文件，实现批量添加源文件 启用 CONFIGURE_DEPENDS 可以看到第二次的输出少了很多，这是因为 CMake 第一遍需要检测编译器 和 C++ 特性等比较耗时，检测完会把结果存储到缓存中，这样第二遍运行 cmake -B build 时就可以直接用缓存的值，就不需要再检测一遍了。 如何清除缓存？删 build 大法了解一下 然而有时候外部的情况有所更新，这时候 CMake 里缓存的却是旧的值，会导致一系列问题。 这时我们需要清除缓存，最简单的办法就是删除 -B build 来启动 图形界面编辑各个缓存选项。 • 当然，直接用编辑器打开 build/CMakeCache.txt 修改后保存也是可以的。 • CMakeCache.txt 用文本存储数据，就是可供用 户手动编辑，或是被第三方软件打开并解析的。 缓存变量到底该如何更新？暴力解决：删 build 大法 用万能的“删 build 大法”当然是可以的。这样重新执行的时候缓存变量不存在，

DogObject 继承自 IObject ，他 们实现了 eatFood 这个虚函数，实现了多态。 • 注意这里解构函数（ ~IObject ）也需要是虚函数 ，否则以 IObject * 存储的指针在 delete 时只 会释放 IObject 里的成员，而不会释放 CatObject 里的成员 string m_catFood 。所以 这里的解构函数也是多态的，他根据类型的不同 return zzz; }() • 可以在表达式层面里插入一个语句块，本 质上是立即求值的 lambda 表达式（内部 是分号级别，外部是逗号级别）。 • 在函数体内也可以这样： • [&]{ xxx; yyy; return zzz; }() • 来在语句块内使用外部的局部变量。 带有构造函数和解构函数的类 • 实际上，只需定义一个带有构造函数和解构函 数的类（这里的 Helper ），然后一个声明该类 const &desc); • 则 func(Descriptor(...)); • 与 func({...}); • 等价（ C++11 起）。 Zeno 中一切节点的基类 • 输入输出全部存储在节点的 inputs 和 outputs 成员变量上。 • inputBounds 表示他连接在哪个节点的哪 个端口上，比如 {“PrimitiveCreate”, “prim”} 就表示这个端口连接了

计算机如何表达字符 • 众所周知，计算机只能处理二进制 整数，字符要怎么办呢？ • 于是就有了 ASCII 码表，他规定， 每个英文字符（包括大小写字母、 数字、特殊符号）都对应着一个整 数。在计算机里只要存储这个的整 数，就能代表这个字符了。 • 例如 32 代表空格， 48 代表 ‘ 0’ ， 65 代表 ‘ A’ ， 97 代表 ‘ a’…… • 32~126 这些整数就用于是表示这些 可显示字符 ≥ s.size() 时，会抛出 std::out_of_range 异常终止程序。使用 gdb 等调试 器就可以在出这个异常的时候暂停，帮你调试错误 （ BV1kP4y1K7Eo ）。也可以从外部函数 catch 住这个异常（以 后再讲）。 • 而 [] 则不会抛出异常，他只是简单地给字符串的首地址指针和 i 做个加法运算，得到新的指针并解引用。如果你给的 i 超过了字符 串大小 i ≥ 和 string 其实都是胖指针。 • string 和 vector 内部都有三个成员变量： ptr, len, capacity 。 • 前两个 [ptr, len] 其实就是表示实际有效范围（存储了字符的）的胖指针。 • 而 [ptr, capacity] 就是表示实际已分配内存（操作系统认为的）的胖指针。 • struct vector { • char *ptr; • size_t

TBB 7.被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 调度，共享内存， barrier 9.并行算法实战： reduce ， scan ，矩阵乘法等 10.存储大规模三维数据的关键：稀疏数据结构 11.物理仿真实战：邻居搜索表实现 pbf 流体求解 12.C++ 在 ZENO 中的工程实践：从 primitive 说起 13.结业典礼：总结所学知识与优秀作业点评 用了工作窃取法来分配任务： 当一个线程 t1 做完自己队列里全部的工 作时，会从另一个工作中线程 t2 的队列 里取出任务，以免 t1 闲置浪费时间。 • 因此内部 for 循环有可能“窃取”到另一个 外部 for 循环的任务，从而导致 mutex 被重复上锁。 解决 1 ：用标准库的递归锁 std::recursive_mutex 解决 2 ：创建另一个任务域，这样不同域之间就不会窃取工作 直接读写，避免了从主内存读写的超高延迟。 • 下次课会进一步深入探讨访存优化，详细剖析 这个案例，那么下周六 14 点敬请期待。 第 6 章：并发容器 std::vector 扩容时会移动元素 • std::vector 内部存储了一个指针，指向一段容量 capacity 大于等于其 size 的内存。 • 众所周知， push_back 会导致 size 加 1 ，但 当他看到容量 capacity 等于当前 size

最终得到了可行的找零方 案。从数据结构与算法的角度看，这种方法本质上是“贪心”算法。 小到烹饪一道菜，大到星际航行，几乎所有问题的解决都离不开算法。计算机的出现使得我们能够通过编程 将数据结构存储在内存中，同时编写代码调用 CPU 和 GPU 执行算法。这样一来，我们就能把生活中的问题 转移到计算机上，以更高效的方式解决各种复杂问题。 Tip 如果你对数据结构、算法、数组和二分查找等概 具有可行性，能够在有限步骤、时间和内存空间下完成。 ‧ 各步骤都有确定的含义，在相同的输入和运行条件下，输出始终相同。 1.2.2 数据结构定义 数据结构（data structure）是计算机中组织和存储数据的方式，具有以下设计目标。 ‧ 空间占用尽量少，以节省计算机内存。 第 1 章 初识算法 hello‑algo.com 14 ‧ 数据操作尽可能快速，涵盖数据访问、添加、删除、更新等。 ‧ 数据结构与算法的关系 如图 1‑4 所示，数据结构与算法高度相关、紧密结合，具体表现在以下三个方面。 ‧ 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及操作数据的方法。 ‧ 算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息，结合算法才能解决特定问题。 ‧ 算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键。 图 1‑4 数据结构与算法的关系

最终得到了可行的找零方 案。从数据结构与算法的角度看，这种方法本质上是“贪心”算法。 小到烹饪一道菜，大到星际航行，几乎所有问题的解决都离不开算法。计算机的出现使得我们能够通过编程 将数据结构存储在内存中，同时编写代码调用 CPU 和 GPU 执行算法。这样一来，我们就能把生活中的问题 转移到计算机上，以更高效的方式解决各种复杂问题。 � 如果你对数据结构、算法、数组和二分查找等概念仍感到一知半解，请继续往下阅读，本书将 具有可行性，能够在有限步骤、时间和内存空间下完成。 ‧ 各步骤都有确定的含义，在相同的输入和运行条件下，输出始终相同。 1.2.2 数据结构定义 「数据结构 data structure」是计算机中组织和存储数据的方式，具有以下设计目标。 ‧ 空间占用尽量少，以节省计算机内存。 第 1 章 初识算法 hello‑algo.com 14 ‧ 数据操作尽可能快速，涵盖数据访问、添加、删除、更新等。 ‧ 数据结构与算法的关系 如图 1‑4 所示，数据结构与算法高度相关、紧密结合，具体表现在以下三个方面。 ‧ 数据结构是算法的基石。数据结构为算法提供了结构化存储的数据，以及操作数据的方法。 ‧ 算法是数据结构发挥作用的舞台。数据结构本身仅存储数据信息，结合算法才能解决特定问题。 ‧ 算法通常可以基于不同的数据结构实现，但执行效率可能相差很大，选择合适的数据结构是关键。 图 1‑4 数据结构与算法的关系