Dynamic Parallel and Distributed Graph Cuts
Graph-cuts are widely used in computer vision. In order to speed up the optimization process and improve the scalability for large graphs, Strandmark and Kahl introduced a splitting method to split a graph into multiple subgraphs for parallel computation in both shared and distributed memory models. However, this parallel algorithm (parallel BK-algorithm) does not have a polynomial bound on the number of iterations and is found non-convergent in some cases due to the possible multiple optimal solutions of its sub-problems. To remedy this non-convergence problem, in this work we first introduce a merging method capable of merging any number of those adjacent sub-graphs which could hardly reach an agreement on their overlapped region in the parallel BK algorithm. Based on the pseudo-boolean representations of graph cuts,our merging method is shown able to effectively reuse all the computed flows in these sub-graphs. Through both the splitting and merging, we further propose a dynamic parallel and distributed graph-cuts algorithm with guaranteed convergence to the globally optimal solutions within a predefined number of iterations. In essence, this work provides a general framework to allow more sophisticated splitting and merging strategies to be employed to further boost performance. Our dynamic parallel algorithm is validated with extensive experimental results.
Code (0)
등록된 구현이 없습니다.
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
D3-GNN: Dynamic Distributed Dataflow for Streaming Graph Neural Networks
Graph Neural Network (GNN) models on streaming graphs entail algorithmic challenges to continuously capture its dynamic state, as well as systems challenges to optimize latency, memory, and throughput during both inferen…
Graph Neural NetworkAWAPart: Adaptive Workload-Aware Partitioning of Knowledge Graphs
Large-scale knowledge graphs are increasingly common in many domains. Their large sizes often exceed the limits of systems storing the graphs in a centralized data store, especially if placed in main memory. To overcome …
Knowledge GraphsveScale: Consistent and Efficient Tensor Programming with Eager-Mode SPMD
Large Language Models (LLMs) have scaled rapidly in size and complexity, requiring increasingly intricate parallelism for distributed training, such as 3D parallelism. This sophistication motivates a shift toward simpler…
Armada: Memory-Efficient Distributed Training of Large-Scale Graph Neural Networks
We study distributed training of Graph Neural Networks (GNNs) on billion-scale graphs that are partitioned across machines. Efficient training in this setting relies on min-edge-cut partitioning algorithms, which minimiz…
CollaPipe: Adaptive Segment-Optimized Pipeline Parallelism for Collaborative LLM Training in Heterogeneous Edge Networks
The increasing demand for intelligent mobile applications has made multi-agent collaboration with Transformer-based large language models (LLMs) essential in mobile edge computing (MEC) networks. However, training LLMs i…