图计算这几年被提得越来越多从社交关系链分析、推荐系统里的用户行为图到风控场景中的资金流转网络底层都绕不开图这种数据结构。但真正动手做过图计算的人都知道它和传统的矩阵运算、向量计算完全不是一个路数访存随机、局部性差、数据规模一大就疯狂跨节点通信CPU和内存之间的带宽成了最硬的瓶颈。我接触过几个做图计算加速的团队几乎所有人最后都会撞到同一堵墙——算力明明还有富余时间全耗在数据搬运上了。这篇内容就围绕针对图计算的近数据计算架构这个方向把内存计算在这类场景下的研究进展、架构取舍、实操中容易踩的坑结合我自己的理解和实践掰开揉碎讲清楚。适合做体系结构、图计算系统、存储层次优化的同学参考也适合想搞清楚近数据计算到底解决了什么问题的工程同学入门。1. 图计算为什么天然和传统内存架构犯冲1.1 图计算的访存模式随机、稀疏、不可预测要理解近数据计算为什么在图计算里这么受关注得先把图计算的访存特征说透。图计算的核心操作是沿着边遍历顶点无论是BFS、PageRank还是连通分量本质都是从一个顶点出发找到它的邻居再读邻居的属性或继续扩展。问题在于图的顶点编号和它的物理存储位置之间几乎没有关系——你访问完顶点0下一个可能是顶点100万再下一个可能是顶点37。这种随机性让缓存几乎失效预取器也基本抓瞎。对比一下就很清楚。矩阵乘法里数据是按行或按块连续访问的硬件预取能提前把下一块数据拉进缓存缓存命中率可以做到很高。而图计算里一次遍历的下一跳地址要等当前顶点的邻居列表读出来才知道这是典型的指针追逐pointer chasing每一跳都得等内存返回。实测数据里图遍历场景下最后一级缓存LLC的缺失率经常在50%以上有些稀疏图甚至能到80%。这意味着大部分时间CPU都在等内存算力单元空转。更麻烦的是稀疏性。真实图里绝大多数顶点的度数很低少数超级顶点度数极高比如社交网络里某些大V。这种幂律分布导致负载极度不均做并行的时候一个线程可能瞬间处理几百万条边另一个线程几十条就完事了。这种不均衡进一步放大了访存的不确定性让静态的优化策略很难奏效。1.2 冯诺依曼瓶颈在图场景下被放大经典的冯诺依曼架构里计算单元和内存是分离的数据要通过总线来回搬。这个搬运开销在计算密集场景下还能被算力掩盖但在图计算这种访存密集场景下就彻底暴露了。业内常说的内存墙在图计算里表现得尤其刺眼一次简单的邻居读取可能要花上百个时钟周期等内存而真正做加法或比较只需要一两个周期。我做过一个粗略的估算在一个典型的图遍历内核里有效计算指令占总指令流的比例经常不到10%剩下90%都是地址计算、加载、等待。也就是说你花大价钱堆的算力九成时间在等饭吃。这就是为什么单纯提升主频或者加核对图计算的加速效果非常有限——瓶颈根本不在算而在搬。近数据计算Near-Data Computing有时也叫近存计算的思路就是针对这个矛盾既然搬运贵那就别搬了把计算挪到数据旁边去。这个思路听起来简单但落地时有大量架构层面的取舍下面几节会逐一拆开。1.3 一个容易混淆的点近数据计算不等于存内计算这里必须澄清一个常见误解。很多资料把近数据计算和存内计算In-Memory Computing / Processing-in-Memory混着说其实两者有区别。存内计算通常指在存储单元内部直接做计算比如用忆阻器、SRAM交叉阵列做模拟计算计算和存储物理上融为一体。近数据计算则宽松得多指的是把计算单元放到离数据近的地方比如放在DRAM芯片的逻辑层、放在3D堆叠的底层die、或者放在存储控制器旁边数据不需要搬到CPU就能处理。对图计算来说近数据计算是更现实的选择。原因很直接图计算需要的是灵活的地址跳转和复杂的控制逻辑比如判断顶点是否被访问过、更新距离值这些用模拟存内计算做起来非常别扭而放在DRAM旁边的逻辑单元里用数字电路实现就自然得多。所以下面讨论的架构主要落在近数据计算这个范畴。2. 近数据图计算架构的几种主流形态2.1 基于3D堆叠DRAM的逻辑层计算这是目前研究里最常见的一类。3D堆叠DRAM比如HBM系列把多层DRAM die堆在一个逻辑die上面中间用硅通孔TSV连接。传统用法里这个逻辑die只做接口转换把数据往CPU送。近数据计算的思路是既然逻辑die本来就在数据旁边为什么不在这里塞几个简单的处理单元这类架构的典型做法是在逻辑层放一组轻量级的PEProcessing Element每个PE负责一部分存储体bank附近的数据处理。图计算的任务被拆成在存储体附近能做完的部分和必须回CPU做的部分。比如顶点度数统计、边的过滤、局部聚合这类操作完全可以在逻辑层完成只把聚合后的少量结果送回CPU。有研究显示把PageRank的局部贡献计算下沉到逻辑层跨总线的数据量能降一个数量级。但这里有个硬约束逻辑层的面积和功耗预算非常紧张。TSV占地方散热也难所以PE不能做得太复杂通常只有简单的ALU和少量寄存器指令集也很精简。这就决定了它只能处理规则、简单、可流水的局部计算复杂的图算法控制流还是得靠主机。设计时的核心权衡就是下沉多少计算才能既显著减少数据搬运又不让逻辑层变成新的瓶颈。2.2 存储控制器旁的计算卸载相比3D堆叠这个方案改动更小、更容易落地。思路是在内存控制器Memory Controller旁边加一个协处理器或者加速单元数据从DRAM读出来、还没上总线之前先在这个单元里过一遍。对于图计算可以做的是读过滤比如遍历时只需要度数大于阈值的顶点那就在控制器旁先把不满足条件的过滤掉只把有用的数据送上总线。这种架构的好处是对现有系统侵入性小不需要改DRAM颗粒主板层面加个单元就行。缺点是它能看到的视野有限——内存控制器通常只管一个通道跨通道的图操作比如一个顶点的邻居分散在多个通道它协调不了。所以它更适合做单通道内的局部过滤和预聚合全局性的图遍历还是得靠上层调度。我在一个模拟环境里对比过这两种形态3D堆叠方案的理论带宽收益更高但工程复杂度和成本也高得多控制器旁方案收益中等但改造成本低适合渐进式演进。实际选型要看你的图规模和数据分布——如果图大到必须跨多节点那单机内的近数据优化收益会被通信开销稀释这时候控制器旁方案性价比反而更好。2.3 近数据架构下的图分区策略调整这一点很多人会忽略近数据计算不是简单地把计算挪个位置就完事它会反过来影响你的图分区策略。传统图计算里分区主要考虑负载均衡和跨分区边数最小化。但在近数据架构下分区还要考虑数据放在哪个存储体/哪个通道因为计算单元是绑定在特定存储位置旁边的。换句话说分区粒度要和近数据计算单元的粒度对齐。如果PE是按bank组织的那分区最好也按bank来切让每个PE处理本地数据避免跨bank访问。这就带来一个新问题图的自然社区结构和物理存储布局往往对不上强行按物理布局分区会切碎图的局部性增加跨分区边。所以近数据图计算的分区本质是在物理局部性和图局部性之间找平衡。实践中一个可行的做法是两阶段分区先按图的社区结构做逻辑分区再在逻辑分区内部按物理bank做二次映射尽量让一个社区的数据落在少数几个bank里。这个映射可以离线算好运行时按映射表调度。代价是需要维护一张映射表增加了元数据开销但对大图来说这笔开销是值得的。3. 把图算法拆开哪些能下沉哪些不能3.1 可下沉计算的判定标准不是所有图计算都适合下沉到近数据单元。我总结了一个简单的判定框架主要看三条数据局部性、控制复杂度、归约友好度。数据局部性指的是这个操作是否只依赖本地存储的数据。比如统计某顶点的邻居数只需要读这个顶点的邻接表天然局部适合下沉。计算全图的最短路径每一轮都要全局同步就不适合整体下沉只能把单轮内的局部扩展下沉。控制复杂度指的是操作的分支和循环是否规则。近数据单元的指令能力弱复杂分支处理起来效率低。像BFS里判断邻居是否已访问并决定是否入队这种带条件的分支如果下沉需要PE有足够的条件判断能力设计上要权衡。归约友好度指的是下沉后的结果能否高效汇总。如果每个PE算出的部分结果需要复杂的跨PE合并那下沉的收益就被抵消了。理想情况是每个PE输出一个可简单相加或取最值的标量主机端做最终归约。用这个框架过一遍常见图算法结论大致如下图算法/操作数据局部性控制复杂度归约友好度下沉建议顶点度数统计高低高完全下沉边过滤/条件筛选高低高完全下沉PageRank单轮贡献中低高局部下沉BFS单层扩展中中中部分下沉连通分量低高低谨慎下沉全图最短路径低高低不下沉这张表不是绝对的具体还要看图的规模和硬件能力但作为一个快速判断的起点很实用。3.2 PageRank的局部下沉实操拆解拿PageRank举例因为它是最典型的可局部下沉算法。标准PageRank每一轮要做的是对每个顶点把它当前的rank值按出度均分给邻居然后每个顶点收集邻居传来的贡献求和再做阻尼衰减。这个收集邻居贡献求和就是典型的局部归约——每个顶点的贡献只来自它的邻居如果邻居数据都在同一个近数据单元附近那这个求和完全可以在本地做完。具体下沉时逻辑层PE的工作流是这样的读入本地的边列表和邻居rank值对每条边算一个贡献值累加到本地顶点的累加器里一轮结束后把每个顶点的新rank写回。主机端只负责发起轮次、做全局的阻尼计算和收敛判断。这样跨总线的数据从每轮全图的边数据降到每轮全图的顶点rank值数据量能降一到两个数量级因为边数通常远大于顶点数。这里有个实操细节要注意累加器的精度。近数据单元的寄存器资源有限如果用低精度浮点累加多轮迭代后误差会累积。我的经验是局部累加用定点数或者较高精度的浮点写回时再转成目标精度这样既省资源又控误差。另外超级顶点的贡献值可能很大累加器要留够位宽否则会溢出——这个坑我在模拟时踩过一个度数几十万的顶点直接把16位累加器干溢出了结果全错。3.3 BFS下沉的边界为什么只能做一半BFS比PageRank难下沉原因在于它的前沿frontier是动态增长的而且下一层要访问哪些顶点取决于当前层的结果。这种跨轮次的依赖让完全下沉不现实。但单层内的扩展是可以下沉的给定当前层的前沿顶点集合让近数据单元去读这些顶点的邻居做是否已访问的过滤输出下一层的前沿候选。难点在于是否已访问这个状态怎么维护。如果访问标记放在主机内存那每次判断都要跨总线查下沉就白做了。所以可行的做法是把访问标记也放到近数据单元本地每个PE维护自己负责的那部分顶点的标记位。但这样又带来一致性问题一个顶点可能被多个PE的邻居指向标记要同步。实践中常用的是本地标记轮末合并即每个PE本地记录自己发现的候选轮末统一去重合并。这会引入一定的冗余计算但换来了本地判断的低延迟整体是划算的。我实测过一个中等规模图的BFS纯主机方案和单层扩展下沉方案对比后者在跨总线数据量上降了约60%但因为轮末合并有开销端到端加速只有30%左右。这个数字说明下沉的收益不是线性的合并和同步的成本会吃掉一部分。设计时一定要把合并开销算进去别只看数据量下降就以为加速会等比例来。4. 落地时绕不开的三个工程难题4.1 编程模型怎么让程序员愿意用近数据架构最大的落地障碍往往不是硬件而是编程模型。你让程序员手动把图算法拆成主机部分和近数据部分还要管数据布局、同步、合并几乎没人愿意干。所以研究里很大一块精力花在怎么把这种拆分自动化或者半自动化。目前比较务实的路子是提供领域特定抽象给图计算定义一套原语比如本地邻接遍历本地归约前沿过滤程序员用这些原语写算法编译器负责把原语映射到近数据单元或主机。这样程序员不用关心底层是3D堆叠还是控制器旁只描述我要做什么局部操作。代价是灵活性受限遇到原语覆盖不到的操作就得回退到主机性能打折。另一个思路是标注式程序员在现有代码上标注哪些循环适合下沉工具链自动生成两套代码。这种方式对现有代码侵入小但标注的准确性依赖程序员对硬件的理解容易标错。我的看法是短期内标注式更容易被接受长期看领域原语更优雅但需要生态积累。4.2 数据一致性近数据单元的写回时机近数据单元在本地改了数据什么时候写回主存、怎么保证和主机看到的一致这是个实打实的工程问题。图计算里很多操作是读-改-写比如更新顶点的rank或距离值如果近数据单元和主机同时持有同一份数据的副本就会冲突。常见的解法是所有权划分把数据按顶点范围切分每个范围明确归某个近数据单元或主机所有只有所有者能写其他方只能读。这样避免了写冲突但读的时候可能读到旧值需要版本号或者轮次屏障来保证读到的是当前轮的数据。图计算天然是轮次同步的BFS一层一轮PageRank一轮所以用轮次屏障比较自然每轮结束设一个屏障屏障前所有写回完成屏障后大家读到的都是新值。要注意的是屏障的开销。轮次太多、每轮数据量又小的话屏障同步的成本会占比很高。所以下沉的粒度要选好别把算法切得太碎。我一般建议单轮下沉的工作量至少能掩盖屏障开销的几倍否则不如合并几轮一起做。4.3 负载不均超级顶点怎么处理前面提过图的幂律分布超级顶点是近数据架构的噩梦。一个度数几十万的顶点它的邻接表可能横跨多个存储体处理它的时候负责的那一个PE会严重拖后腿其他PE早早干完等着。这种长尾直接拉低了整体利用率。应对办法有几个。一是超级顶点单独处理预处理时识别出度数超过阈值的顶点把它们的邻接表单独存、单独调度可以拆到多个PE上并行处理或者干脆回主机用专门的内核处理。二是动态任务窃取PE干完自己的活后去偷别的PE的任务但这要求PE之间能通信增加了架构复杂度。三是边切分把超级顶点的边打散到多个PE每个PE处理一部分边最后归约这其实就是把顶点并行变成边并行。我个人倾向第一种因为实现简单、可预测。预处理阶段扫一遍度数分布定个阈值比如度数是平均度数的100倍以上把这些顶点拎出来走特殊路径。代价是预处理多一遍扫描但图计算通常要迭代很多轮这点预处理开销摊薄后可以忽略。5. 一些实测经验和选型建议5.1 模拟器验证比直接上硬件靠谱近数据架构的硬件不好搞大多数团队起步都是靠模拟器。我的建议是先用周期级模拟器把访存行为和收益摸清楚再考虑硬件。常见的做法是基于gem5这类框架加上DRAM模型和近数据单元的扩展跑真实的图数据集比如公开的社交图、路网图看跨总线数据量、PE利用率、端到端时间这几个指标。模拟时容易犯的错是模型太理想化。比如假设PE和存储体之间零延迟、假设带宽无限这样跑出来的收益会虚高。一定要把TSV带宽、PE的指令延迟、屏障同步开销都建模进去哪怕参数是估的也比不建强。我见过有团队模拟出来加速10倍一上FPGA原型就剩2倍差距全在没建模的开销上。5.2 数据集选择直接影响结论图计算的性能对图的结构极其敏感。用随机图比如Erdős–Rényi跑出来的结论和用真实社交图跑出来的可能完全相反因为随机图没有幂律分布、没有社区结构访存模式均匀得多。做近数据架构评估一定要用有代表性的真实图社交网络图看超级顶点、路网图看低度数高局部性、网页链接图看幂律。至少覆盖两三种结构结论才站得住。另外图的规模也要注意。小图能整个塞进缓存近数据计算的收益体现不出来图太大又要跨节点单机近数据的收益被通信稀释。比较合适的评估区间是单机内存装得下但缓存装不下这个范围这时候近数据计算的收益最明显。5.3 别忽视元数据开销近数据架构为了管理数据布局、所有权、版本需要维护不少元数据映射表、标记位、版本号、累加器。这些元数据本身也占存储、也要访存。小规模实验里元数据开销不明显规模一大就暴露了。我建议在设计早期就把元数据的内存预算算进去一般控制在数据总量的5%以内比较健康超过10%就要重新审视设计是不是太复杂了。举个具体的例子如果每个顶点要维护一个访问标记位、一个版本号、一个本地累加器假设顶点数是N那元数据就是N乘以若干字节。对于十亿级顶点的图这就是几个GB的开销不能不算。优化方向包括位压缩标记位打包、按需分配累加器只在活跃轮次分配等。6. 写在最后的几点个人体会做这个方向断断续续有段时间了最大的感受是近数据计算不是银弹它的收益高度依赖数据搬运占比这个前提。如果你的图算法本身计算密集比如带复杂权重计算的变种或者图小到能进缓存那近数据架构的复杂度就不划算。它真正发光的地方是那种图大到装不下缓存、算法以遍历和局部归约为主、跨总线数据量是主要瓶颈的场景。另一个体会是架构研究和算法研究必须一起做。单纯改硬件不知道上层算法怎么用很容易设计出理论很美、实际用不上的单元单纯改算法不碰硬件又突破不了内存墙。近数据图计算的价值恰恰在于它逼着两边坐下来一起想哪些计算真的必须靠近数据哪些可以挪走边界在哪里。这个边界不是拍脑袋定的得靠模拟、靠实测、靠对真实图结构的理解一点点磨出来。最后一个实操建议如果你要入门这个方向别一上来就啃架构论文先拿一个真实的图数据集在普通机器上把BFS或PageRank跑一遍用性能分析工具看看时间到底花在哪——是计算、是访存、还是同步。把这个profile吃透你再看近数据架构的各种设计就会明白每个设计决策在解决哪个具体的痛点而不是一堆抽象的名词。