在GPU上对一般图形进行并行最大枢密度匹配
Gregory Schwing1, Daniel Grosu1, Loren Schwiebert1
1Department of Computer Science, Wayne State University, Detroit, MI.
概括
本研究介绍了Micali-Vazirani算法的GPU实现,用于在一般图中实现最大枢纽性匹配. 它在稀疏的图形上实现了显著的加速度,但在更密集的图形类型上显示性能退化.
科学领域:
- 计算机科学 计算机科学
- 图形理论 图形理论
- 并行计算是一种平行计算.
背景情况:
- 在一般图形中最大核心值匹配 (MCMGG) 是一个基本的图形问题.
- 米卡利-瓦齐拉尼算法为稀疏图提供了最佳的非对称复杂性.
- 由于递归增强路径程序和图形分区要求,在GPU上并行MCMGG具有挑战性.
研究的目的:
- 建议并实施MCMGG的Micali-Vazirani算法的GPU加速版本.
- 为了应对在GPU上平行化图形匹配算法的挑战.
主要方法:
- 在GPU上实现了Micali-Vazirani算法.
- 使用线程平行宽度首次搜索用于桥边识别.
- 采用了块平行路径增强和花收缩.
- 使用基于堆的代方法来增强路径和Union-find与共享内存分配.
主要成果:
- 与串行实现相比,在非常稀疏的正则图形上实现了高达15倍的速度.
- 在更密集的正则图表上观察到高达5倍的减速.
- 在权力定律分布的克罗内克尔图表中经历了50倍的减速.
结论:
- 拟议的GPU实现显示了在特定图形结构上加速MCMGG的潜力.
- 性能高度依赖于图形的稀疏性和分布.
- 开源实现促进了基于GPU的组合图算法的进一步研究.
更多相关视频
05:12ExCYT: A Graphical User Interface for Streamlining Analysis of High-Dimensional Cytometry Data
Published on: January 16, 2019
11.4K
12:27Large-scale Reconstructions and Independent, Unbiased Clustering Based on Morphological Metrics to Classify Neurons in Selective Populations
Published on: February 15, 2017
6.9K
相关概念视频
Vector Algebra: Graphical Method
12.0K
Vectors can be multiplied by scalars, added to other vectors, or subtracted from other vectors. The vector sum of two (or more) vectors is called the resultant vector or, for short, the resultant.
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
We use the laws of geometry to construct resultant vectors, followed by trigonometry to find vector magnitudes and directions. For a geometric construction of the sum of two vectors in a plane, we follow the parallelogram rule. Suppose two vectors are at arbitrary positions. Translate either one of...
12.0K
Parallel Processing
147
The brain processes sensory information rapidly due to parallel processing, which involves sending data across multiple neural pathways at the same time. This method allows the brain to manage various sensory qualities, such as shapes, colors, movements, and locations, all concurrently. For instance, when observing a forest landscape, the brain simultaneously processes the movement of leaves, the shapes of trees, the depth between them, and the various shades of green. This enables a quick and...
147
Routh-Hurwitz Criterion II
208
In the application of the Routh-Hurwitz criterion, two specific scenarios can arise that complicate stability analysis.
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
The first scenario occurs when a singular zero appears in the first column of the Routh table. This situation creates a division by zero issues. To resolve this, a small positive or negative number, denoted as epsilon (∈), is substituted for the zero. The stability analysis proceeds by assuming a sign for ∈. If ∈ is positive, any sign change in the first...
208
Maximum Power Flow and Line Loadability
104
The maximum power flow for lossy transmission lines is derived using ABCD parameters in phasor form. These parameters create a matrix relationship between the sending-end and receiving-end voltages and currents, allowing the determination of the receiving-end current. This relationship facilitates calculating the complex power delivered to the receiving end, from which real and reactive power components are derived.
104
Ampere-Maxwell's Law: Problem-Solving
587
A parallel-plate capacitor with capacitance C, whose plates have area A and separation distance d, is connected to a resistor R and a battery of voltage V. The current starts to flow at t = 0. What is the displacement current between the capacitor plates at time t? From the properties of the capacitor, what is the corresponding real current?
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of...
To solve the problem, we can use the equations from the analysis of an RC circuit and Maxwell's version of Ampère's law.
For the first part of...
587
Second Uniqueness Theorem
994
Consider a region consisting of several individual conductors with a definite charge density in the region between these conductors. The second uniqueness theorem states that if the total charge on each conductor and the charge density in the in-between region are known, then the electric field can be uniquely determined.
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the...
In contrast, consider that the electric field is non-unique and apply Gauss's law in divergence form in the region between the conductors and the integral form to the...
994
