问为什么图形处理很难分布式？

EN

图操作的交换性和结合性是主要的障碍。这两个属性决定了一个算法是否可并行化。在您链接的页面中，作者陈述了以下内容：

更新是可交换和关联的，因此允许可扩展的实现7。

实际上，7处引用的论文是一篇PhD论文，它很好地解释了这一点：

本文方法的核心是这个可伸缩的交换性规则:在任何情况下，当几个操作互换时-这意味着无法使用接口区分它们的执行顺序-它们有一个在这些操作期间无冲突的实现-这意味着没有内核写入由另一个内核读取或写入的缓存线。从经验上讲，无冲突的操作是可扩展的，所以这种实现是可扩展的。或者，更简洁地说，只要接口操作相互通信，它们就可以以一种可伸缩的方式实现。这条规则很直观:当操作互换时，它们的结果(返回值和对系统状态的影响)与顺序无关。因此，交换操作之间的通信是不必要的，消除它将产生一个无冲突的实现。在现代共享内存多核上，无冲突操作可以完全从每个核心缓存执行，因此无冲突实现的性能将随着核心数量的增加而线性扩展。

例如，cartesian graph product是一种交换和结合操作，可以以任何顺序计算得到的顶点，使得并行化在这种情况下很容易。然而，大多数图操作都缺少这两个属性中的一个或两个。