从稀疏数据结构到量化数据类型 by 彭于斌（ @archibate ） 往期录播： https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 本课涵盖：稀疏矩阵、 unordered_map 、空间稀 疏网格、位运算、浮点的二进制格式、内存带宽优 化 面向人群：图形学、 形怪状也不会浪费内存。 这些被写入的部分被称为激活元素 (active element) ，反之则是未激活 (inactive) 。 这就是稀疏的好处，按需分配，自动扩容。 分块则是利用了我们存储的数据常常有着空间局域性的特点，减轻哈希表的压 力，同时在每个块内部也可以快乐地 SIMD 矢量化， CPU 自动预取之类的。 第 2 章：位运算 稀疏的好处：坐标可以是负数 这样即使坐标为负数，或 是负数，则得到的模也是负数。 Python 的 % 就没问题 • 7 % 4 = 3 • -7 % 4 = 1 • Python 的模运算 a % b 的值始终是 [0, b) 区间内的正数，非常方便。 对稀疏数据结构造成的问题 • 如果这里的 x 是负数，则 x % B 也是负数，会造成对 m_block 的越界访问。 • 因此 % 会返回负数对 CFD 用户来说是个很大的坑点，很多人想当然地用 % 做循环边界，

新一代分布式高性能图数据库的构建 北京海致星图科技有限公司 2023-06-18 沈游人 数据库与大数据专场 海致简介—企业级知识图谱开创者 专业顶尖技术团队支撑 超 700 人团队，其中 80% 为技术人员，创始团队在完成全球第一个中文知 识图谱网站研发后，探索知识图谱技术在企业领域的应用。 2021 年，海致院 士专家工作站成立，站内清华大学计算机博士生占比达 90% 以上。 企业级数据解决方案专家 为建行、工行、交行、招行、上交所、深交所、中国人寿等 70+ 银行证券保险 企业、公安部、上海市公安局、武汉市公安局等 100+ 公安机构，国家电网、 国信通产业集团等电力能源行业提供数据智能产品解决方案及长期服务。 海致专注为政府、金融、能源等客户提供大数据处理、分析、挖掘服务，在互 联网技术基础上，打造专业、易用的企业级大数据实战应用产品及解决方案。 北京中关村总部 专注于数据智能技术赋能中国数字经济发展 海致高性能图计算院士专家工作站 郑纬民 - 海致科技首席科学家 中国工程院院士、清华大学计算机科学与技术系教 授、中国计算机学会前理事长，中国计算机系统结构 的学科带头人，我国高性能计算和存储系统等方面的 泰斗和先行者。 2021 年 3 月 25 日，海致科技与清华大学计算机科学与技术系共同建设高性能图计算院士专家工作站 。 高性能图计算是高

性能优化 之 无分支编程 Branchless Programming by 彭于斌（ @archibate ） 两种代码写法：分支 vs 三目运算符 两种使用方式：排序 vs 不排序 测试结果（均为 gcc -O3 ） 测试结果可视化 图表比较：分支 vs 无分支 分支 无分支 0 0.01 0.02 0.03 耗时（越低越好） 乱序 有序 • 传统的分支方法实现的 传统的分支方法实现的 uppercase ，对于 排序过的数据明显比乱序时高效。 • 无分支的方法对于乱序和有序的数据一样 高效，性能吊打了传统的分支方法。 • 对于传统分支的做法，为什么排序了的更 高效？既然无分支更高效，我要怎样优化 才能让我的程序变成无分支的呢？那就来 看本期性能优化专题课吧！ 分支预测成败对性能的影响 排序为什么对有分支的版本影响那么大 为什么需要流水线 • 为了高效， CPU 等待烧完开水才开始刷牙，而是针对性地为“没烫伤”的那个剧本优化。把刷牙、看比站和烧 开水同时进行，但刷牙、看比站在烧完开水前都处于“虚”的状态，也就是虽然在做但是不写 到日记里（提前执行数学计算，但不实际写回数据到内存）。直到烧完开水确认没有被烫伤 后，才实际把刷牙、看比站的操作写到日记本里（ CPU 确认执行这条分支，才会真正写回 内存，产生副作用）。 洗脸 刷牙 烧开水 吃饭 看比站 拉粑粑 5

• 等价于： • const K &k = tmp.first; • V &v = tmp.second; • 其实，就算遍历时不修改，还是建议加引用，在 K 和 V 类型尺寸很大时，可以节省性能 。 • 因为引用最多只有 8 字节（指针的大小），而他指向的 V 可能是非常大的（比如 string 类型在栈上的空间就要消耗 32 字节，更不用说可能堆上还有），深拷贝一下要花费不少 时间。 map 中的 堆空间 执行你这段代码 的栈空间 & ( 深拷贝，浪费时间 ) v （假如非常大的话） • 其实，就算遍历时不修改，还是建议加引用，在 K 和 V 类型尺寸很大时，可以节省性能 。 • 因为引用最多只有 8 字节（指针的大小），而他指向的 V 可能是非常大的（比如 string 类型在栈上的空间就要消耗 32 字节，更不用说可能堆上还有），深拷贝一下要花费不少 时间。

生成器； MacOS 系统默认是 Xcode 生成器。 • 可以用 -G 参数改用别的生成器，例如 cmake -GNinja 会生成 Ninja 这个构建系统的构 建规则。 Ninja 是一个高性能，跨平台的构建系统， Linux 、 Windows 、 MacOS 上都可 以用。 • Ninja 可以从包管理器里安装，没有包管理器的 Windows 可以用 Python 的包管理器安 装： • 事实上， MSBuild 是单核心的构建系统， Makefile 虽然多核心但因历史兼容原因效率一 般。 • 而 Ninja 则是专为性能优化的构建系统，他和 CMake 结合都是行业标准了。 Ninja 和 Makefile 简单的对比 性能上： Ninja > Makefile > MSBuild Makefile 启动时会把每个文件都检测一遍， 浪费很多时间。特别是有很多文件，但是实 CMAKE_BUILD_TYPE 是 CMake 中一个特殊的变量，用于控制构建类型，他的值可以 是： • Debug 调试模式，完全不优化，生成调试信息，方便调试程序 • Release 发布模式，优化程度最高，性能最佳，但是编译比 Debug 慢 • MinSizeRel 最小体积发布，生成的文件比 Release 更小，不完全优化，减少二进制体积 • RelWithDebInfo 带调试信息发布，生成的文件比

global 可以调 用 device ； device 可以调用 device 。 声明为内联函数 • 注意， inline 在现代 C++ 中的效果是声明一个函数为 weak 符号，和性能优化意义上的内联无关。 • 优化意义上的内联指把函数体直接放到调用者那里去。 • 因此 CUDA 编译器提供了一个“私货”关键字： __inline__ 来 声明一个函数为内联。不论是 CPU world! 打印了三遍！ • 原来，三重尖括号里的第二个参数决定着启动 kernel 时所用 GPU 的线程数量。 • GPU 是为并行而生的，可以开启很大数量的 线程，用于处理大吞吐量的数据。 获取线程编号 • 可以通过 threadIdx.x 获取当前线程的编 号，我们打印一下试试看。 • 这是 CUDA 中的特殊变量之一，只有在 核函数里才可以访问。 • 可以看到线程编号从 要指定板块的数量，只需调节三重尖括号里第一个 参数即可。我们这里调成 2 。总之： • <<< 板块数量，每个板块中的线程数量 >>> • 可以看到这里我们启动了两个板块，各有 3 个线程 ，都打印了一样的数据。 获取板块编号和数量 • 板块的编号可以用 blockIdx.x 获取。 • 板块的总数可以用 gridDim.x 获取。 • 可以看到这里执行了两个板块，每个板块 又有三个线程，总共有

并行能减轻计算瓶颈，但不减轻内存瓶颈，故后者是优化的重点 。 浮点加法的计算量 • 冷知识：并行地给浮点数组每个元素做一次加法反而更慢。 • 因为一次浮点加法的计算量和访存的超高延迟相比实在太少了。 • 计算太简单，数据量又大，并行只带来了多线程调度的额外开销 。 • 小彭老师经验公式： 1 次浮点读写 ≈ 8 次浮点加法 • 如果矢量化成功（ SSE ）： 1 次浮点读写 ≈ 32 次浮点加法 • 如果 CPU CPU 计算能力越强，相 对之下来不及从内存读写数据，从而越容 易 mem-bound 。 1 2 4 6 8 10 0 50 100 150 200 250 300 350 funcA funcB funcC 内存信息查看工具： dmidecode • 可以看到小彭老师电脑上插了 2 块内存，频率都是 2667 MHz ，数据的宽度是 64 位（ 8 字节）。 • 理论极限带宽 a ，实际搬运 了 2048 MB 的数据。 • 花费了 0.0656 秒。 • 因此带宽是 31198 MB/s 。 • 和理论带宽 42672 MB/s 相差不多，符合我的预期 。 第 2 章：缓存与局域性 针对不同数据量大小的带宽测试 • 我们试试看 a 不同的大小，对带宽有什么影响。 针对不同数据量大小的带宽测试（续） • 可见数据量较小时，实际带宽甚至超过了 理论带宽极限

学 C++ 从 CMake 学起 by 彭于斌（ @archibate ） 高性能并行编程与优化 - 课程大纲 • 分为前半段和后半段，前半段主要介绍现代 C++ ，后半段主要介绍并行编程与优化。 1.课程安排与开发环境搭建： cmake 与 git 入门 2.现代 C++ 入门：常用 STL 容器， RAII 内存管理 3.现代 C++ 进阶：模板元编程与函数式编程 4.编译器如何自动优化：从汇编角度看 被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 调度，共享内存， barrier 9.并行算法实战： reduce ， scan ，矩阵乘法等 10.存储大规模三维数据的关键：稀疏数据结构 11.物理仿真实战：邻居搜索表实现 pbf 流体求解 12.C++ 在 ZENO 中的工程实践：从 primitive 说起 13.结业典礼：总结所学知识与优秀作业点评 I 硬件要求： bombela/backward-cpp - 实现了 C++ 的堆栈回溯便于调试 7. google/googletest - 谷歌单元测试框架 8. google/benchmark - 谷歌性能评估框架 9. glfw/glfw - OpenGL 窗口和上下文管理 10.libigl/libigl - 各种图形学算法大合集 fmt - 使用这个神奇的格式化库 • fmt::format

往期录播： https://www.bilibili.com/video/BV1fa411r7zp 课程 PPT 和代码： https://github.com/parallel101/course 高性能并行编程与优化 - 课程大纲 • 分为前半段和后半段，前半段主要介绍现代 C++ ，后半段主要介绍并行编程与优化。 1.课程安排与开发环境搭建： cmake 与 git 入门 2.现代 C++ 被忽视的访存优化：内存带宽与 cpu 缓存机制 8.GPU 专题： wrap 调度，共享内存， barrier 9.并行算法实战： reduce ， scan ，矩阵乘法等 10.存储大规模三维数据的关键：稀疏数据结构 11.物理仿真实战：邻居搜索表实现 pbf 流体求解 12.C++ 在 ZENO 中的工程实践：从 primitive 说起 13.结业典礼：总结所学知识与优秀作业点评 I 硬件要求： • 可为何直到今天也生产不出 10GHz 的芯片？ • 结论：狭义的摩尔定律没有失效。但晶体管数 量的增加，不再用于继续提升单核频率，转而 用于增加核心数量。单核性能不再指数增长！ 你醒啦？免费午餐结束了！ 指望靠单核性能的增长带来程序性 能提升的时代一去不复返了，现在 要我们动动手为多核优化一下老的 程序，才能搭上摩尔定律的顺风车 。 神话与现实： 2 * 3GHz < 6GHz •