274
个编辑
更改
无编辑摘要
== Parallel Graph Representations ==
== Parallel Graph Representations ==
图的并行化表示
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.
The parallelization of graph problems faces significant challenges: Data-driven computations, unstructured problems, poor locality and high data access to computation ratio. 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. 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 ===
共享内存
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.
In the case of a shared memory model, the graph representations used for parallel processing are the same as in the sequential case, 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, since parallel read-only access to the graph representation (e.g. an adjacency list) is efficient in shared memory.
在共享内存模型的情况下，用于并行处理的图表示与顺序处理的方式相同，因为对图表示的并行只读访问(例如:邻接表)是共享内存的有效方法。
--[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）通读一遍 注意多余符号的问题(例如:。邻接表)
--[[用户:趣木木|趣木木]]（[[用户讨论:趣木木|讨论]]）通读一遍 注意多余符号的问题(例如:。邻接表)
=== Distributed Memory ===
=== Distributed Memory ===
分布式存储
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" />