项目已开源！访问 GitHub（github.com/latentcat/graphpu）以获取 GraphPU 源码、下载软件（Windows / macOS）
本科的时候，在课上学习过巴拉巴西关于无尺度网络的相关研究，对复杂网络、社交网络产生了浓厚的兴趣。当时我爬取了自己微信的一千个好友的朋友圈点赞数据，在 Mathematica 里绘制了一副好友关系网络。
其中最神奇的是，在 Mathematica 的可视化中，我的好友被分成了一个个颜色组，当我去检查每个聚团里的好友名字时发现，这些聚团恰好分别是我的小学初中同学、高中同学、大学同学、网友和单独认识的好友。而输入图可视化的数据里并没有类似的标签，只有某节点给某节点点赞的数据。
这让我对图可视化产生了兴趣，我开始好奇更大型的图会长什么样，比如 10 亿微信用户所形成的网络是什么形状的？和几亿小红书、微博的有什么不同？
这样的好奇驱使我和我的几位同学，@CPunisher、@Shichen、@KiriNoMizumi 开发了 GraphPU，一个可以可视化百万节点的 3D GPU 加速的图可视化工具。
有许多图可视化的软件，比如 Gephi、Cytoscape、上面提到的 Mathematica，但他们通常无法处理一万节点以上的图数据，这是因为他们的分布模拟算法通常基于 CPU 多线程，这不仅会导致模拟时有大量的串行依赖，还会在渲染的时候有大量的数据在 CPU、内存、显存、GPU 之间传输，这会带来大量的帧延时。
除此之外，这些软件的目的通常是帮助数据科学家进行具体的分析和研究，所以通常只在 2D 空间模拟分布，但我希望观众对图的理解更加直观，所以我需要能在三维空间中实时模拟、实时渲染。
我在 Unity 中完成了原型的搭建。Unity 对 Compute Shader 有很好的抽象封装，可以很灵活的进行算法的开发和调试。
经过一个月的爆肝，我的到了下面这些非常惊艳的可视化图像。
随着开发逐渐深入，Unity 的问题逐渐体现，比如不容易开发工具 UI、有极为严格的帧锁定。
最后我选择了在 Rust 里构建 GraphPU。下面是其中的一些截图。
在颇为惊艳的视觉效果后，是一系列可以说极其变态的优化。没有这些技术方案，GraphPU 可能只能做到 0.1FPS，而不是 60FPS。
图可视化的核心在于两种力的计算：代表斥力的电子力和代表引力的弹簧力，两种力相互作用，最终使的图分布在空间中一个稳定的状态。
而要能在 GPU 中计算弹簧力（本质上是一个稀疏矩阵），需要计算每个节点被施加的弹簧力的总和，这就涉及到 GPU 的一个特性了，即当有多个 GPU 线程同时对一个数据进行运算时，极可能出现同时读同时写的情况，就导致当有多个线程往一个节点累加弹簧力，同时读的结果都是 0，最后写入的结果可能只是其中一个弹簧力的值。
要解决这个问题，就需要对每个节点的 x、y、z 三个维度进行浮点数原子加法，所谓原子加法，就是在进行加法的时候锁定这个数值不允许其他线程访问，在写入完成后解锁。大多数 GPU 程序都有提供整数类型的原子加法，而浮点数原子加法，需要依靠软件模拟。
Unity 中，用户编写的 HLSL shader 会在 ShaderLab 中被送入 HLSLcc，编译为 Metal、OpenGL 等后端的 shader 程序。而在 Rust wgpu 中，shader 的翻译工作由 naga 进行。
而由于 WebGPU、WGSL 标准处于草稿状态，迭代频率高，naga 尚未针对 WGSL 的最新标准中的 atomicCompareExchangeWeak 进行实现，即传入三个参数，返回包含原始值与是否改变布尔值的结构体。且当时 atomicExchange 在 Metal 端存在 bound check 的错误。
因此，我们将 wgpu 依赖从 Rust crate 迁移至本地，并进行了定制开发。使用类似 HLSL 的标准编写了 atomicCompareExchangeWeak 函数，并确保其在 Metal、Vulkan 端有效。
这样的实践让我们对 shader 编译器产生了更细致的了解，也算是涨经验了。
虽然浮点数原子加法对弹簧力计算有用，但当图的规模变大，有可能出现有非常多的边连在同一个节点的情况，那么这一个节点的弹簧力计算就存在着大量的串行依赖，复杂度就来到了 O(n)。因此，我们发明了一种针对弹簧力的归并加法，可以极大程度加速弹簧力的计算。
归并加法是一种常见的 GPU 累加运算算法，通过两两相加、逐渐归并加速累加运算。而在我们的算法中，如何对于每个节点分别进行归并计算是一个大的难题，因此我们设计了一套排序和对齐的方法，使这个流程变得无比的搞笑。
经过优化后，假如一个节点连接着 100 万条边，模拟的速度可以提升六十倍以上。
在整个图可视化算法中，最重要的部分，就是节点与节点之间的电子力计算，电子与电子两两交互、电子力“无处不在”，复杂度为实打实的 O(n^2)。而 Barnes-Hut 算法，通过构建 Barnes-Hut 树（一种类似四叉树、八叉树的结构），可以在 N-body 模拟（电子力其实就是反向的万有引力）中，将距离较远、影响较小的节点进行归并，得到作用力的近似值，从而极大的加速模拟过程，将 O(n^2) 的复杂度降为 O(n log n)。
而在 Barnes-Hut 的经典实现中，算法几乎都是在 CPU 上完成的，最大的原因是 Barnes-Hut 树在构建时会使用递归的方法，而 GPGPU 中没有递归的概念（除非使用 CUDA 之类的），只能通过循环、数据驱动的方式来模拟。
因此，实现一个 GPU 并行的 Barnes-Hut 算法非常复杂，我们为了实现写了 1000 行的 compute shader，而且这些算法极难调试，遇到的问题不计其数。
最后，我们在渲染上也下了一些功夫，我们用双调归并解决了粒子深度排序，用离屏渲染的方法做了鼠标和粒子的 raycast 交互，并用控制器的交互，完成了我们毕设现场的布置。
这是一个耗时很长、跨度很大的项目，几乎完全不考虑商业转化、完全兴趣时间投入。很感谢 @CPunisher 和 @Shichen、@KiriNoMizumi 的共同努力，项目已经在 github.com/latentcat/graphpu 开源，并能下载 Windows / macOS 的可执行程序，欢迎大家点赞收藏～
谢谢！
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。