274
个编辑
更改
无编辑摘要
== Parallel Graph Representations ==
== Parallel Graph Representations ==
图的并行化表示
图的并行化表示<br>
The parallelization of graph problems faces significant challenges: Data-driven computations, unstructured problems, poor locality and high data access to computation ratio.<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> The graph representation used for parallel architectures plays a significant role in facing those challenges. Poorly chosen representations may unnecessarily drive up the communication cost of the algorithm, which will decrease its [[scalability]]. In the following, shared and distributed memory architectures are considered.
The parallelization of graph problems faces significant challenges: Data-driven computations, unstructured problems, poor locality and high data access to computation ratio.<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> The graph representation used for parallel architectures plays a significant role in facing those challenges. Poorly chosen representations may unnecessarily drive up the communication cost of the algorithm, which will decrease its [[scalability]]. In the following, shared and distributed memory architectures are considered.
=== Shared memory ===
=== Shared memory ===
共享内存
共享内存<br>
In the case of a [[shared memory]] model, the graph representations used for parallel processing are the same as in the sequential case,<ref name=":0">{{Cite book|last=Sanders|first=Peter|url=https://www.springer.com/gp/book/9783030252083|title=Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer International Publishing|isbn=978-3-030-25208-3|language=en}}</ref> since parallel read-only access to the graph representation (e.g. an [[adjacency list]]) is efficient in shared memory.
In the case of a [[shared memory]] model, the graph representations used for parallel processing are the same as in the sequential case,<ref name=":0">{{Cite book|last=Sanders|first=Peter|url=https://www.springer.com/gp/book/9783030252083|title=Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox|last2=Mehlhorn|first2=Kurt|last3=Dietzfelbinger|first3=Martin|last4=Dementiev|first4=Roman|date=2019|publisher=Springer International Publishing|isbn=978-3-030-25208-3|language=en}}</ref> since parallel read-only access to the graph representation (e.g. an [[adjacency list]]) is efficient in shared memory.
=== Distributed Memory ===
=== Distributed Memory ===
分布式存储
分布式存储<br>
In the [[distributed memory]] model, the usual approach is to [[Graph partition|partition]] the vertex set <math>V</math> of the graph into <math>p</math> sets <math>V_0, \dots, V_{p-1}</math>. Here, <math>p</math> is the amount of available processing elements (PE). The vertex set partitions are then distributed to the PEs with matching index, additionally to the corresponding edges. Every PE has its own [[Subgraph (graph theory)|subgraph]] representation, where edges with an endpoint in another partition require special attention. For standard communication interfaces like [[Message Passing Interface|MPI]], the ID of the PE owning the other endpoint has to be identifiable. During computation in a distributed graph algorithms, passing information along these edges implies communication.<ref name=":0" />
In the [[distributed memory]] model, the usual approach is to [[Graph partition|partition]] the vertex set <math>V</math> of the graph into <math>p</math> sets <math>V_0, \dots, V_{p-1}</math>. Here, <math>p</math> is the amount of available processing elements (PE). The vertex set partitions are then distributed to the PEs with matching index, additionally to the corresponding edges. Every PE has its own [[Subgraph (graph theory)|subgraph]] representation, where edges with an endpoint in another partition require special attention. For standard communication interfaces like [[Message Passing Interface|MPI]], the ID of the PE owning the other endpoint has to be identifiable. During computation in a distributed graph algorithms, passing information along these edges implies communication.<ref name=":0" />
In the distributed memory model, the usual approach is to partition the vertex set <math>V</math> of the graph into <math>p</math> sets <math>V_0, \dots, V_{p-1}</math>. Here, <math>p</math> is the amount of available processing elements (PE). The vertex set partitions are then distributed to the PEs with matching index, additionally to the corresponding edges. Every PE has its own subgraph representation, where edges with an endpoint in another partition require special attention. For standard communication interfaces like MPI, the ID of the PE owning the other endpoint has to be identifiable. During computation in a distributed graph algorithms, passing information along these edges implies communication.
In the distributed memory model, the usual approach is to partition the vertex set <math>V</math> of the graph into <math>p</math> sets <math>V_0, \dots, V_{p-1}</math>. Here, <math>p</math> is the amount of available processing elements (PE). The vertex set partitions are then distributed to the PEs with matching index, additionally to the corresponding edges. Every PE has its own subgraph representation, where edges with an endpoint in another partition require special attention. For standard communication interfaces like MPI, the ID of the PE owning the other endpoint has to be identifiable. During computation in a distributed graph algorithms, passing information along these edges implies communication.
在分布式存储模型中，常用的方法是将图的顶点集合 < math > v </math > 分解为 < math > p </math > 集合 < math > v0，dots，v { p-1} </math > 。这里，< math > p </math > 是可用处理元素(PE)的数量。然后，顶点集合分区被分配到具有匹配索引的 pe 中，并附加到相应的边上。每个 PE 都有自己的子图表示法，其中带有另一个分区中端点的边需要特别注意。对于像 MPI 这样的标准通信接口，拥有其他端点的 PE 的 ID 必须是可识别的。在分布式图算法的计算过程中，沿着这些边传递信息意味着通信。
在分布式存储模型中，常用的方法是将图的顶点集合<math>v</math> 分解为<math>p</math> 集合 <math> v0，dots，v { p-1} </math> 。这里，<math>p</math> 是可用处理元素(PE)的数量。然后，顶点集合分区被分配到具有匹配索引的 pe 中，并附加到相应的边上。每个 PE 都有自己的子图表示法，其中带有另一个分区中端点的边需要特别注意。对于像 MPI 这样的标准通信接口，拥有其他端点的 PE 的 ID 必须是可识别的。在分布式图算法的计算过程中，沿着这些边传递信息意味着通信。