.png){kind=icon}
返回
How good is recursive bisection?
.png){kind=icon}
PRE
AI
DOI：10.1137/S1064827593255135.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The most commonly used p-way partitioning method is recursive bisection (RB). It first divides a graph or a mesh into two equal-sized pieces, by a ''good'' bisection algorithm, and then recursively divides the two pieces. Ideally, we would like to use an optimal bisection algorithm. Because the optimal bisection problem that partitions a graph into two equal-sized subgraphs to minimize the number of edges cut is NP-complete, practical RE algorithms use more efficient heuristics in place of an optimal bisection algorithm. Most such heuristics are designed to find the best possible bisection within allowed time. We show that the RE method, even when an optimal bisection algorithm is assumed, may produce a pa ay partition that is very far way from the optimal one. Our negative result is complemented by two positive ones: first we show that for some important classes of graphs that occur in practical applications, such as well-shaped finite-element and finite-difference meshes, RE is within a constant factor of the optimal one ''almost always.'' Second, we show that if the balance condition is relaxed so that each block in the p-way partition is bounded by 2n/p, where n is the number of vertices of the graph, then a modified RE finds an approximately balanced p-way partition whose cost is within an O(log p) factor of the cost of the optimal p-way partition.
Keyword:
communication cost
data and computation mapping an parallel machines
load balancing
mesh partitioning
parallel processing
recursive bisection
scalable parallel algorithms
well-shaped finite-element and finite-difference meshes
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
2.6
论文数:
5.1K
被引数:
1.8W
机构
暂无机构信息
引用论文
.png){kind=icon}
Dynamic transition in current-driven disordered flux-line lattice in single-crystal of Bi-2212电流驱动下Bi-2212单晶中无序磁通线晶格的动态转变
PREAI
分享收藏Ac Susceptibility Responses of Superconductors: Cryogenic Aspects, Investigation of Inhomogeneous Systems and of the Equilibrium Mixed State交流磁化率响应：超导体的低温特性、不均匀系统及平衡混合态的研究
PREAI
分享收藏
查看更多内容