CoChat
Sign Up
Cited by 4

The DOI matches its Crossref record.

Dynamically tuned push-relabel algorithm for the maximum flow problem on CPU-GPU-Hybrid platforms

Zhengyu He, Bo Hong·2010·2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS)
DOI 10.1109/ipdps.2010.5470401
Open this paper in CoChat — free account

Abstract

The maximum flow problem is a fundamental graph theory problem with many important applications. Max-flow algorithms based on the push-relabel method are known to have better complexity bound and faster practical execution speed than others. However, existing push-relabel algorithms are designed for uniprocessors or parallel processors that support locking primitives, thus making it very difficult to apply the push-relabel technique to CUDA-based GPUs. In this paper, we present a first generic parallel push-relabel algorithm for CUDA devices. We model the parallelization efficiency of the algorithm, which reveals that, for a given input graph, the level of parallelism varies during the execution of the algorithm. To maximize the execution efficiency, we develop a dynamically tuned algorithm that utilizes both CPU and GPU by adaptively switching between the two computing units during run time. We show that algorithm finds the maximum flow with O(|V|2|E|) operations (summed over both the CPU and the GPU). Extensive experimental results show that the new algorithm is up to 2 times faster than the push-relabel algorithm by Goldberg et al.

Overview

Integrity signals

Registry

Crossref · 10.1109/ipdps.2010.5470401

Cites

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Different phases of a single application may exhibit properties which make it more suitable for execution on a particular PU.

    “Not only different applications, but even different phases of a single application may exhibit properties which make it more suitable for execution on a particular PU [He and Hong 2010;Nere et al. 2012;Shen et al. 2013]).”

    From A Survey of CPU-GPU Heterogeneous Computing Techniques (2015) · cites this paper as He and Hong 2010

Citations

Cites

No references could be resolved yet.

Research works printed but not linked: 15

  1. 10.1016/0022-0000(85)90039-X · DOI
  2. 10.1287/moor.15.3.430 · DOI
  3. 10.1145/12130.12144 · DOI
  4. hussein, 2007, On implementing graph cuts on cuda, First Workshop on General Purpose Processing on Graphics Processing Units
  5. 10.1109/CVPRW.2008.4563095 · DOI
  6. cheriyan, 1998, An analysis of the highest-level selection rule in the preflow-push max-flow algorithm, Information Processing Letters, 69, 69
  7. johnson, 1993, Network Flows and Matching: First DIMACS Implementation Challenge, 10.1090/dimacs/012 · DOI
  8. 10.1109/IPDPS.2008.4536352 · DOI
  9. goldberg, 1998, Recent developments in maximum flow algorithms (invited lecture), SWAT '98 Proceedings of the 6th Scandinavian Workshop on Algorithm Theory, 1, 10.1007/BFb0054350 · DOI
  10. 10.1109/IPDPS.2009.5161058 · DOI
  11. dinic, 1970, Algorithm for solution of a problem of maximum flow in networks with power estimation, Soviet Mathematics Doklady, 11, 1277
  12. 10.1145/321694.321699 · DOI
  13. bader, 2005, A cache-aware parallel implementation of the push-relabel network flow algorithm and experimental evaluation of the gap relabeling heuristic, PDCS '05 Proceedings of the 18th ISCA International Conference on Parallel and Distributed Computing Systems
  14. anderson, 0, On the parallel implementation of goldberg's maximum flow algorithm, SPAA '92 Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, 168
  15. karzanov, 1974, Determining the maximal flow in a network by the method of preflows, Soviet Mathematics Doklady, 15, 434

Cited by

Sorted by citations

Metadata

Authors
He, Z., & Hong, B.
Venue
2010 IEEE International Symposium on Parallel & Distributed Processing (IPDPS)
Publisher
IEEE
Published
2010-04
Pages
1-10
DOI
10.1109/ipdps.2010.5470401
Cited by
4
References
0

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review