Approximate weighted matching on emerging manycore and multithreaded architectures

Abstract

Graph matching is a prototypical combinatorial problem with many applications in high-performance scientific computing. Optimal algorithms for computing matchings are challenging to parallelize. Approximation algorithms are amenable to parallelization and are therefore important to compute matchings for large-scale problems. Approximation algorithms also generate nearly optimal solutions that are sufficient for many applications. In this paper we present multithreaded algorithms for computing half-approximate weighted matching on state-of-the-art multicore (Intel Nehalem and AMD Magny-Cours), manycore (Nvidia Tesla and Nvidia Fermi), and massively multithreaded (Cray XMT) platforms. We provide two implementations: the first uses shared work queues and is suited for all platforms; and the second implementation, based on dataflow principles, exploits special features available on the Cray XMT. Using a carefully chosen dataset that exhibits characteristics from a wide range of applications, we show scalable performance across different platforms. In particular, for one instance of the input, an R-MAT graph (RMAT-G), we show speedups of about $32$ on $48$ cores of an AMD Magny-Cours, $7$ on $8$ cores of Intel Nehalem, $3$ on Nvidia Tesla and $10$ on Nvidia Fermi relative to one core of Intel Nehalem, and $60$ on $128$ processors of Cray XMT. We demonstrate strong as well as weak scaling for graphs with up to a billion edges using up to 12,800 threads. We avoid excessive fine-tuning for each platform and retain the basic structure of the algorithm uniformly across platforms. An exception is the dataflow algorithm designed specifically for the Cray XMT. To the best of the authors' knowledge, this is the first such large-scale study of the half-approximate weighted matching problem on multithreaded platforms. Driven by the critical enabling role of combinatorial algorithms such as matching in scientific computing and the emergence of informatics applications, there is a growing demand to support irregular computations on current and future computing platforms. In this context, we evaluate the capability of emerging multithreaded platforms to tolerate latency induced by irregular memory access patterns, and to support fine-grained parallelism via light-weight synchronization mechanisms. By contrasting the architectural features of these platforms against the Cray XMT, which is specifically designed to support irregular memory-intensive applications, we delineate the impact of these choices on performance.

Keywords

approximation dataflow GPU graph algorithms manycore matching multicore weighted matching

Get full access to this article

View all access options for this article.

References

Abou-Rjeili

Karypis

(2006) Multilevel algorithms for partitioning power-law graphs. In Proceedings of the 20th International Parallel and Distributed Processing Symposium, 2006 (IPDPS 2006).

Agarwal

Petrini

Pasetto

Bader

(2010) Scalable graph exploration on multicore processors. In Proceedings of the 2010 ACM/IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC'10). Washington, DC: IEEE Computer Society, pp. 1–11.

Asanovic

Bodik

Catanzaro

. (2006) The Landscape of Parallel Computing Research: A View from Berkeley. Technical report, Electrical Engineering and Computer Sciences, University of California at Berkeley.

Avis

(1983) A survey of heuristics for the weighted matching problem. Network 13: 475–493.

Bader

Madduri

(2006) Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2. In Proceedings of the 2006 International Conference on Parallel Processing (ICPP '06). Washington, DC: IEEE Computer Society, pp. 523–530.

Bader

Madduri

(2008) SNAP, small-world network analysis and partitioning: an open-source parallel graph framework for the exploration of large-scale networks. In Proceedings of the 2008 International Parallel and Distributed Processing Symposium (IPDPS 2008), Miami, FL.

Belongie

Malik

Puzicha

(2002) Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence 24: 509–522.

Catalyurek

Feo

Gebremedhin

Halappanavar

Pothen

(2011). Multithreaded algorithms for graph coloring. Submitted to a journal. Invited presentation at SIAM Conference on Computational Science and Engineering (CSE11).

Chakrabarti

Faloutsos

(2006) Graph mining: laws, generators, and algorithms. ACM Computer Surveys 38: 2.

10.

Cong

Bader

(2007) Techniques for Designing Efficient Parallel Graph Algorithms for SMPs and Multicore Processors. lecture notes in computer science, vol. 4742. Berlin: Springer, pp. 137–147.

11.

Drake

Hougardy

(2003) A simple approximation algorithm for the weighted matching problem. Information Processing Letters 85: 211–213.

12.

Duff

Koster

(1999) The design and use of algorithms for permuting large entries to the diagonal of sparse matrices. SIAM Journal of Matrix Analysis Applications 20: 889–901.

13.

Feo

Harper

Kahan

Konecny

(2005) ELDORADO. In CF '05: Proceedings of the 2nd Conference on Computing Frontiers. New York: ACM Press, pp. 28–34.

14.

Halappanavar

(2009) Algorithms for Vertex-weighted Matching in Graphs. PhD thesis, Old Dominion University, Norfolk, VA.

15.

Harish

Narayanan

(2007) Accelerating large graph algorithms on the GPU using CUDA. In Proceedings of the 14th International Conference on High Performance Computing (HiPC'07). Berlin: Springer-Verlag, pp. 197–208.

16.

Hendrickson

Berry

(2008) Graph analysis with high-performance computing. Computing in Science and Engineering 10(2): 14–19.

17.

Hoepman

J-H

(2004) Simple distributed weighted matchings. Computing Research Repository (CoRR) cs.DC/0410047.

18.

Hong

Kim

Oguntebi

Olukotun

(2011) Accelerating CUDA graph algorithms at maximum warp. In : Calin Cascaval and Pen-Chung Yew (eds) Proceedings of the 16th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPOPP 2011, San Antonio, TX, USA, February 12--16. ACM pp. 267–276.

19.

Karypis

Kumar

(1995) Analysis of multilevel graph partitioning. In Supercomputing '95: Proceedings of the 1995 ACM/IEEE Conference on Supercomputing (CDROM). New York: ACM Press, p. 29.

20.

Katz

Kider

Jr (2008) All-pairs shortest-paths for large graphs on the GPU. In Proceedings of the 23 rd ACM SIGGRAPH/EUROGRAPHICS Symposium on Graphics Hardware (GH '08). Aire-la-Ville, Switzerland: Eurographics Association, pp. 47–55.

21.

Demmel

(1998) Making sparse Gaussian elimination scalable by static pivoting. In Supercomputing '98: Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM). Washington, DC: IEEE Computer Society, pp. 1–17.

22.

Lovasz

(1986) Matching Theory (North-Holland Mathematics Studies). Amsterdam: Elsevier Science Ltd.

23.

Lumsdaine

Gregor

Hendrickson

Berry

(2007) Challenges in parallel graph processing. Parallel Processing Letters 17: 5–20.

24.

Luo

Wong

Hwu

W-m

(2010) An effective GPU implementation of breadth-first search. In Proceedings of the 47th Design Automation Conference (DAC '10). New York: ACM Press, pp. 52–55.

25.

Manne

Bisseling

(2007) A parallel approximation algorithm for the weighted maximum matching problem. In The Seventh International Conference on Parallel Processing and Applied Mathematics, pp. 708–717.

26.

Molka

Hackenberg

Schone

Muller

(2009) Memory performance and cache coherency effects on an Intel Nehalem multiprocessor system. In PACT '09: Proceedings of the 2009 18th International Conference on Parallel Architectures and Compilation Techniques. Washington, DC: IEEE Computer Society, pp. 261–270.

27.

Monien

Preis

Diekmann

(2000) Quality matching and local improvement for multilevel graph-partitioning. Parallel Computing 26: 1609–1634.

28.

Nieplocha

Márquez

Feo

. (2007) Evaluating the potential of multithreaded platforms for irregular scientific computations. In CF '07: Proceedings of the 4th International Conference on Computing Frontiers. New York: ACM Press, pp. 47–58.

29.

Pinar

Chow

Pothen

(2006) Combinatorial algorithms for computing column space bases that have sparse inverses. Electronic Transactions on Numerical Analysis 22: 122–145.

30.

Pothen

Fan

C-J

(1990) Computing the block triangular form of a sparse matrix. ACM Transactions on Mathematical Software 16: 303–324.

31.

Preis

(1999) Linear time

\frac{1}{2}

-approximation algorithm for maximum weighted matching in general graphs. In 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 259–269.

32.

Schenk

Wächter

Hagemann

(2007) Matching-based preprocessing algorithms for the solution of saddle-point problems in large-scale nonconvex interior-point optimization. Computer Optimization Application 36: 321–341.

33.

Schrijver

(2003) Combinatorial Optimization - Polyhedra and Efficiency. New York: Springer.

34.

Yoo

Chow

Henderson

McLendon

Hendrickson

Catalyurek

(2005) A scalable distributed parallel breadth-first search algorithm on BlueGene/L. In Proceedings of the 2005 ACM/IEEE Conference on Supercomputing (SC '05). Washington, DC: IEEE Computer Society, p. 25.