性能优化 之 无分支编程 Branchless Programming by 彭于斌（ @archibate ） 两种代码写法：分支 vs 三目运算符 两种使用方式：排序 vs 不排序 测试结果（均为 gcc -O3 ） 测试结果可视化 图表比较：分支 vs 无分支 分支 无分支 0 0.01 0.02 0.03 耗时（越低越好） 乱序 有序 • 传统的分支方法实现的 uppercase uppercase ，对于 排序过的数据明显比乱序时高效。 • 无分支的方法对于乱序和有序的数据一样 高效，性能吊打了传统的分支方法。 • 对于传统分支的做法，为什么排序了的更 高效？既然无分支更高效，我要怎样优化 才能让我的程序变成无分支的呢？那就来 看本期性能优化专题课吧！ 分支预测成败对性能的影响 排序为什么对有分支的版本影响那么大 为什么需要流水线 • 为了高效， CPU 的内部其实是一个流水 让不占用相同资源的任务同时进行，这也是 CPU 流水线的初衷。但理想是美好的，现实 是骨感的，对于程序来说，指令不只是一个 个简单的任务，有时候我们需要做判断，来 决定要执行的具体任务，这就是分支，在汇 编语言中体现为条件跳转指令。 • 例如我们这里给任务清单加一个，如果烧开 水时被烫伤，则直接去医院的特殊任务。 • 特点：一旦触发去医院这个支线，则后面的 任务都不用做了，直接跳过。

CUDA 开启的 GPU 编程 by 彭于斌（ @archibate ） 往期录播： https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 前置条件 • 学过 C/C++ 语言编程。 • 理解 malloc/free 之类的概念。 • 熟悉 STL 中的容器、函数模板等。 blockIdx + threadIdx 三维的板块和线程编号 • CUDA 也支持三维的板块和线程区间。 • 只要在三重尖括号内指定的参数改成 dim3 类型即可。 dim3 的构造函数就是接受三 个无符号整数（ unsigned int ）非常简单 。 • dim3(x, y, z) • 这样在核函数里就可以通过 threadIdx.y 获取 y 方向的线程编号，以此类推。 那二维呢？ 。这样 分配出来的地址，不论在 CPU 还是 GPU 上都是一模一样的，都可以访问。而 且拷贝也会自动按需进行（当从 CPU 访 问时），无需手动调用 cudaMemcpy ，大 大方便了编程人员，特别是含有指针的一 些数据结构。 注意不要混淆 • 主机内存 (host) ： malloc 、 free • 设备内存 (device) ： cudaMalloc 、 cudaFree

TBB 开启的并行编程之旅 by 彭于斌（ @archibate ） 往期录播： https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 高性能并行编程与优化 - 课程大纲 • 分为前半段和后半段，前半段主要介绍现代 C++ ，后半段主要介绍并行编程与优化。 1 cmake 与 git 入门 2.现代 C++ 入门：常用 STL 容器， RAII 内存管理 3.现代 C++ 进阶：模板元编程与函数式编程 4.编译器如何自动优化：从汇编角度看 C++ 5.C++11 起的多线程编程：从 mutex 到无锁并行 6.并行编程常用框架： OpenMP 与 Intel TBB 7.被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 并发：某互联网公司购置了一台单核处理 器的服务器，他正同时处理 4 个 HTTP 请求，如果是单线程的 listen-accept 循环 ，则在处理完 A 的请求之前， B 的请求 就无法处理，造成“无响应”现象。 C 的请 求进来，则还得继续排队…… • 每个请求开启一个线程来处理，这样处理 A 用户的同时还可以继续监听 B 用户发 来的请求，及时响应，改善用户体验。 • 并行：某图形学爱好者购置了一台

C++ 进阶：模板元编程 by 彭于斌（ @archibate ） 往期录播： https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 高性能并行编程与优化 - 课程大纲 • 分为前半段和后半段，前半段主要介绍现代 C++ ，后半段主要介绍并行编程与优化。 1.课程安排与开发环境搭建： cmake 与 git 入门 2.现代 C++ 入门：常用 STL 容器， RAII 内存管理 3.现代 C++ 进阶：模板元编程与函数式编程 4.编译器如何自动优化：从汇编角度看 C++ 5.C++11 起的多线程编程：从 mutex 到无锁并行 6.并行编程常用框架： OpenMP 与 Intel TBB 7.被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 以上（ GPU 专题） 为什么需要模板函数（ template ） • 避免重复写代码。 • 比如，利用重载实现“将一个数乘以 2” 这个 功能，需要： 为什么面向对象在 HPC 不如函数式和元编程香了？ 这个例子要是按传统的面向对象思想，可能是这样： 令 Int, Float, Double 继承 Numeric 接口类并实现 ，其中 multiply(int) 作为虚函数。然后定义： Numeric

高性能并行编程与优化 - 课程大纲 • 分为前半段和后半段，前半段主要介绍现代 C++ ，后半段主要介绍并行编程与优化。 1.课程安排与开发环境搭建： cmake 与 git 入门 2.现代 C++ 入门：常用 STL 容器， RAII 内存管理 3.现代 C++ 进阶：模板元编程与函数式编程 4.编译器如何自动优化：从汇编角度看 C++ 5.C++11 起的多线程编程：从 mutex mutex 到无锁并行 6.并行编程常用框架： OpenMP 与 Intel TBB 7.被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 调度，共享内存， barrier 9.并行算法实战： reduce ， scan ，矩阵乘法等 10.存储大规模三维数据的关键：稀疏数据结构 11.物理仿真实战：邻居搜索表实现 pbf 流体求解 12.C++ 在 ZENO 中的工程实践：从 函数体内 的运算推迟到 future 的 get() 被调用时。 也就是 main 中的 interact 计算完毕后。 • 这种写法， download 的执行仍在主线程 中，他只是函数式编程范式意义上的异步 ，而不涉及到真正的多线程。可以用这个 实现惰性求值（ lazy evaluation ）之类。 std::async 的底层实现： std::promise • 如果不想让

LANGUAGES 字段 • project( 项目名 LANGUAGES 使用的语言列表 ...) 指定了该项目使用了哪些编程语言。 • 目前支持的语言包括： • C ： C 语言 • CXX ： C++ 语言 • ASM ：汇编语言 • Fortran ：老年人的编程语言 • CUDA ：英伟达的 CUDA （ 3.8 版本新增） • OBJC ：苹果的 Objective-C （ 3 3.16 版本新增） • OBJCXX ：苹果的 Objective-C++ （ 3.16 版本新增） • ISPC ：一种因特尔的自动 SIMD 编程语言（ 3.18 版本新增） • 如果不指定 LANGUAGES ，默认为 C 和 CXX 。 https://cmake.org/cmake/help/latest/command/project.html 常见问题： LANGUAGES 接的麻烦 add_library 无参数时，是静态库还是动态库 ? 会根据 BUILD_SHARED_LIBS 这个变量的值决定是动态库还是静态库。 ON 则相当于 SHARED ， OFF 则相当于 STATIC 。 如果未指定 BUILD_SHARED_LIBS 变量，则默认为 STATIC 。 因此，如果发现一个项目里的 add_library 都是无参数的，意味着你可以用 ： cmake

字节）所花费的时间。 • 根据计算： 125/64*4≈8 • 即从主内存读取一次 float 花费 8 个 cycle ， 符合小彭老师的经验公式。 • “right” 和“ wrong” 指的是分支预测是否成功。 多少计算量才算多？ • 看右边的 func ，够复杂了吧？也只是勉勉强强超过一 点内存的延迟了，但在 6 个物理核心上并行加速后， 还是变成 mem-bound 了。 • 加速比： float = 64 字节（缓存行大小），一个缓存行预取一遍就够了。 • 如何每隔 16 次 x++ 才执行 _mm_prefetch 一次呢？暴力通过 if (x % 16) 判断吗？不行，涉及到分支也太低效了！ • 这时可以先将外层循环改为针对另一个变量， xBase 的跨步为 16 的循环，即 xBase += 16 。然后内部先执行一次 _mm_prefetch ，再弄一个小循环遍历 y) 也是 YX 序的没问题，但是 a(y, x) 相当于一个 XY 序的二维数组，从而在内存看来访存是跳 跃的，违背了空间局域性。因为每次跳跃 了 nx ，所以只要缓存容量小于 nx 就无 法命中。 矩阵转置优化：循环分块 • 解决方法当然还是循环分块。即 YXyx 序 。 • 这样只需要块的大小 blockSize^2 小于缓 存容量，即可保证全部命中。 图片直观感受矩阵转置的循环分块

高性能并行编程与优化 - 课程大纲 • 分为前半段和后半段，前半段主要介绍现代 C++ ，后半段主要介绍并行编程与优化。 1.课程安排与开发环境搭建： cmake 与 git 入门 2.现代 C++ 入门：常用 STL 容器， RAII 内存管理 3.现代 C++ 进阶：模板元编程与函数式编程 4.编译器如何自动优化：从汇编角度看 C++ 5.C++11 起的多线程编程：从 mutex mutex 到无锁并行 6.并行编程常用框架： OpenMP 与 Intel TBB 7.被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 调度，共享内存， barrier 9.并行算法实战： reduce ， scan ，矩阵乘法等 10.存储大规模三维数据的关键：稀疏数据结构 11.物理仿真实战：邻居搜索表实现 pbf 流体求解 12.C++ 在 ZENO 中的工程实践：从 这个名字是一个函数，不是一个变量或者类的名字：这样当我写下 hello() 的时候，他知道我是想调用 hello 这个函数，而不是创建一个叫 hello 的类的对 象。 • 其实， C++ 是一种强烈依赖上下文信息的编程语言，举个例子： • vector < MyClass > a; // 声明一个由 MyClass 组成的数组 • 如果编译器不知道 vector 是个模板类，那他完全可以把 vector 看做一个变量名，把

高性能并行编程与优化 - 课程大纲 • 分为前半段和后半段，前半段主要介绍现代 C++ ，后半段主要介绍并行编程与优化。 1.课程安排与开发环境搭建： cmake 与 git 入门 2.现代 C++ 入门：常用 STL 容器， RAII 内存管理 3.现代 C++ 进阶：模板元编程与函数式编程 4.编译器如何自动优化：从汇编角度看 C++ 5.C++11 起的多线程编程：从 mutex mutex 到无锁并行 6.并行编程常用框架： OpenMP 与 Intel TBB 7.被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 调度，共享内存， barrier 9.并行算法实战： reduce ， scan ，矩阵乘法等 10.存储大规模三维数据的关键：稀疏数据结构 11.物理仿真实战：邻居搜索表实现 pbf 流体求解 12.C++ 在 ZENO 中的工程实践：从 github.io/) - [C++ 并发编程实战 ](https://www.bookstack.cn/read/Cpp_Concurrency_In_Action/README.md) - [ 因特尔 TBB 编程指南 ](https://www.inf.ed.ac.uk/teaching/courses/ppls/TBBtutorial.pdf) - [ 并行体系结构与编程 (CMU 15-418)](https://www