ACM SIGPLAN Notices · 2018 · 11 citations · 32 references
ComputingComputer EngineeringComputer ScienceInterconnection NetworksParallel AlgorithmsParallel ComputingCommunication OverheadData ParallelismParallel ArchitecturesParallel Computing SystemsScalable Algorithm DesignCommunication-avoiding AlgorithmsCommunication-avoiding ReductionGraph ProcessingMinimum CutParallel Graph AlgorithmsScalable Graph AlgorithmsScalable Parallel AlgorithmsSupercomputer Architecture
We present novel scalable parallel algorithms for finding global minimum cuts and connected components, which are important and fundamental problems in graph processing. To take advantage of future massively parallel architectures, our algorithms are communication-avoiding : they reduce the costs of communication across the network and the cache hierarchy. The fundamental technique underlying our work is the randomized sparsification of a graph: removing a fraction of graph edges, deriving a solution for such a sparsified graph, and using the result to obtain a solution for the original input. We design and implement sparsification with O (1) synchronization steps. Our global minimum cut algorithm decreases communication costs and computation compared to the state-of-the-art, while our connected components algorithm incurs few cache misses and synchronization steps. We validate our approach by evaluating MPI implementations of the algorithms on a petascale supercomputer. We also provide an approximate variant of the minimum cut algorithm and show that it approximates the exact solutions well while using a fraction of cores in a fraction of time.
32
Collective dynamics of ‘small-world’ networks
Duncan J. Watts, Steven H. Strogatz · Nature · 1998 · 43.2K citations
Statistical mechanics of complex networks
Réka Albert, Albert-Ĺaszló Barabási · Reviews of Modern Physics · 2002 · 20.6K citations · Full text
P. Erdős, A. Rényi · Publicationes Mathematicae Debrecen · 2022 · 5.2K citations
A bridging model for parallel computation
Leslie G. Valiant · Communications of the ACM · 1990 · 3.7K citations · Full text
Satu Elisa Schaeffer · Computer Science Review · 2007 · 1.6K citations