更改

图问题的并行化面临着重大的挑战: 数据驱动的计算、非结构化问题、局部性差和计算数据访问率高。<ref name=":1">{{Cite book|last=Bader|first=David|url=http://www.ams.org/conm/588/|title=Graph Partitioning and Graph Clustering|last2=Meyerhenke|first2=Henning|last3=Sanders|first3=Peter|last4=Wagner|first4=Dorothea|date=January 2013|publisher=American Mathematical Society|isbn=978-0-8218-9038-7|series=Contemporary Mathematics|volume=588|language=en|doi=10.1090/conm/588/11709}}</ref><ref>{{Cite journal|last=LUMSDAINE|first=ANDREW|last2=GREGOR|first2=DOUGLAS|last3=HENDRICKSON|first3=BRUCE|last4=BERRY|first4=JONATHAN|date=March 2007|title=CHALLENGES IN PARALLEL GRAPH PROCESSING|url=http://dx.doi.org/10.1142/s0129626407002843|journal=Parallel Processing Letters|volume=17|issue=01|pages=5–20|doi=10.1142/s0129626407002843|issn=0129-6264}}</ref> 用于并行架构的图表示在面对这些挑战时扮演着重要的角色。选择的表示方式不当可能会增加不必要的算法连接代价，从而降低算法的可扩展性。接下来的段落中，我们将着重探讨共享和分布式的内存架构。

图问题的并行化面临着重大的挑战: 数据驱动的计算、非结构化问题、局部性差和计算数据访问率高。<ref name=":1">{{Cite book|last=Bader|first=David|url=http://www.ams.org/conm/588/|title=Graph Partitioning and Graph Clustering|last2=Meyerhenke|first2=Henning|last3=Sanders|first3=Peter|last4=Wagner|first4=Dorothea|date=January 2013|publisher=American Mathematical Society|isbn=978-0-8218-9038-7|series=Contemporary Mathematics|volume=588|language=en|doi=10.1090/conm/588/11709}}</ref><ref>{{Cite journal|last=LUMSDAINE|first=ANDREW|last2=GREGOR|first2=DOUGLAS|last3=HENDRICKSON|first3=BRUCE|last4=BERRY|first4=JONATHAN|date=March 2007|title=CHALLENGES IN PARALLEL GRAPH PROCESSING|url=http://dx.doi.org/10.1142/s0129626407002843|journal=Parallel Processing Letters|volume=17|issue=01|pages=5–20|doi=10.1142/s0129626407002843|issn=0129-6264}}</ref> 用于并行架构的图表示在面对这些挑战时扮演着重要的角色。选择的表示方式不当可能会增加不必要的算法连接代价，从而降低算法的可扩展性。接下来的段落中，我们将着重探讨共享和分布式的内存架构。

===  分布式存储 distributed memory===

===  分布式存储 distributed memory===

在分布式存储模型中，常用的方法是将图的顶点集合<math>V</math> 分解为<math>p</math> 集合 <math> Vo,\dots,V{ p-1}</math> 。这里，<math>p</math> 是可用处理元素 processing elements（PE）的数量。然后，顶点集合分区被分配到具有匹配索引的 PE 中，并附加到相应的边上。每个 PE 都有自己的子图表示法，其中带有另一个分区中端点的边需要特别注意。对于像 MPI 这样的标准通信接口，拥有其他端点的 PE 的 ID 必须是可识别的。在分布式图算法的计算过程中，沿着这些边传递信息意味着连接通信。<ref name=":0" />

在分布式存储模型中，常用的方法是将图的顶点集合<math>V</math> 分解为<math>p</math> 集合 <math> Vo,\dots,V{ p-1}</math> 。这里，<math>p</math> 是可用处理元素 processing elements（PE）的数量。然后，顶点集合分区被分配到具有匹配索引的 PE 中，并附加到相应的边上。每个 PE 都有自己的子图表示法，其中带有另一个分区中端点的边需要特别注意。对于像 MPI 这样的标准通信接口，拥有其他端点的 PE 的 ID 必须是可识别的。在分布式图算法的计算过程中，沿着这些边传递信息意味着连接通信。<ref name=":0" />

2D分区: 每个处理器都有一个邻接矩阵的子矩阵。假设处理器在一个矩形<math>p = p_r \times p_c</math> 中对齐，其中 <math>p_r</math>和<math>p_c</math>是每行和每列中处理元素的数量。然后每个处理器得到维数<math>(n/p_r)\times(n/p_c)</math> 的邻接矩阵。这可以可视化为矩阵中的棋盘格模式。<ref name=":2" />因此，每个处理单元只能在同一行和列中具有 PE 的输出边。这将每个 PE 的通信伙伴的数量限制为 <math>p_r + p_c - 1</math> 出<math>p = p_r \times p_c</math>可能的伙伴

2D分区: 每个处理器都有一个邻接矩阵的子矩阵。假设处理器在一个矩形<math>p = p_r \times p_c</math> 中对齐，其中 <math>p_r</math>和<math>p_c</math>是每行和每列中处理元素的数量。然后每个处理器得到维数<math>(n/p_r)\times(n/p_c)</math> 的邻接矩阵。这可以可视化为矩阵中的棋盘格模式。<ref name=":2" />因此，每个处理单元只能在同一行和列中具有 PE 的输出边。这将每个 PE 的通信伙伴的数量限制为<math>p = p_r \times p_c</math>可能伙伴中的 <math>p_r + p_c - 1</math>个。

==参见==

==参见==