共享内存并行Edmonds Blossom算法用于一般图形中的最大枢纽性匹配
Gregory Schwing1, Daniel Grosu1, Loren Schwiebert1
1Department of Computer Science, Wayne State University, Detroit, MI.
概括
这项研究优化了Edmonds Blossom算法,以实现更快的图形匹配. 与粗粒锁定并行处理显著减少了各种图形类型的运行时间,提高了复杂网络分析的效率.
科学领域:
- 计算机科学 计算机科学
- 图形理论 图形理论
- 算法优化的算法优化
背景情况:
- 埃德蒙兹花朵算法是寻找一般图形中最大匹配的基本方法.
- 使用深度先搜索的现有实现本质上是串行的,并且可以是计算密集的.
- 需要更快,更高效的算法来进行图形匹配,特别是在大型和复杂的网络中.
研究的目的:
- 开发一个更快,并行实现的Edmonds Blossom算法.
- 通过代码简化和并行化技术来研究可实现的性能增长.
- 在不同类型的图表上评估算法的有效性,包括随机和现实世界的网络.
主要方法:
- 实现了Edmonds Blossom算法,使用了精简的串行方法.
- 通过使用粗粒度锁定在算法代中提取计算来引入并行性.
- 在随机正规图和现实世界的图形上测试了优化的算法,其密度和社区结构各不相同.
主要成果:
- 精简的串行实现速度比以前的通用图形匹配代码快3-5倍.
- 与粗粒度锁定并行实现了随机正规图的四倍运行时间减少和现实世界图的两倍减少.
- 社区结构的稀疏图表显示,八个线程的速度减慢了三倍,但这是通过在平均度大于四的图表上的边际加速度来克服的.
结论:
- 埃德蒙兹花朵算法的并行粗粒锁定实现显示了显著的性能改进.
- 这种方法有效地从基于增强路径的算法中提取并行性.
- 研究结果表明,这种并行实现可能适用于类似的基于图形的算法和复杂网络分析.
更多相关视频
相关概念视频
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
Theorems of Pappus and Guldinus: Problem Solving
720
Pappus and Guldinus's theorems are powerful mathematical principles that are used for finding the surface area and volume of composite shapes. For example, consider a cylindrical storage tank with a conical top. Finding the surface area or volume can be challenging for such complex shapes. These theorems are particularly useful in calculating the volume and surface area of such systems. Here, the cylindrical storage tank with a conical top can be broken down into two simple shapes: a...
720
Wilcoxon Signed-Ranks Test for Matched Pairs
109
The Wilcoxon signed-rank test for matched pairs evaluates the null hypothesis by combining the ranks of differences with their signs. It essentially tests whether the median of the differences in a population of matched pairs is zero. Since the test incorporates more information than the sign test, it generally yields more trustable conclusions. This test also does not require the data to follow a normal distribution, but two conditions must be met for it to be applicable: (1) the data must...
109
Woodward–Hoffmann Selection Rules and Microscopic Reversibility
3.0K
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
3.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
Sign Test for Matched Pairs
119
The sign test for matched pairs offers a robust method for comparing two paired samples, often for the effects of an intervention in one of them. This method is very useful in situations where the underlying distribution of the data is unknown. The test compares two related samples—often pre- and post-treatment measurements on the same subjects—to determine if there are significant differences in their median values.
To conduct the sign test, we first calculate the differences in...
To conduct the sign test, we first calculate the differences in...
119


