Parallel Maximum Matching algorithms on Multithreaded Platforms

Parallel Maximum Matching algorithms on Multithreaded Platforms Ariful Azad – Purdue University Mahantesh Halappanavar- PNNL John Feo - PNNL Alex Pothen – Purdue University Outline ! Background ! Algorithms ! Experiment and Results ! Future work A Graph ! A graph G is a pair (V, E) ! V is a set of vertices ! E, a set of edges, represents a binary relation on V ! Bipartite and non-bipartite ! Weighted and un-weighted a b c a’ b’ c’

a b c d weight A Matching ! A matching M is a subset of edges such that no two edges in M are incident on the same vertex ! A maximum matching has maximum number of edges a b c a’ b’ c’ a b c d matched a b c a’ b’ c’ a b c d Application: Maximum Matching a b c d e a’ b’ c’ d’ e’ Interns Projects Manager Goal: Assign projects to interns such that maximum projects can be done in the summer Restriction: Each intern can get at most one project, each project can be assigned to at most one intern Application: Maximum Matching a b c d e a’ b’ c’ d’ e’ Interns Projects Manager Goal: Assign projects to interns such that maximum projects can be done in the summer Restriction: Each intern can get at most one project, each project can be assigned to at most one intern Other Applications ! Sparse matrix computations ! Matrix preconditioning ! Block Triangular Form ! Multilevel Graph Algorithms ! Graph partitioners ! Graph clustering ! Scheduling Problem ! High speed network switching ! Facility scheduling problem ! Bioinformatics ! Homology detection ! Structural alignment Accomplishments ! Parallel implementation of five cardinality matching algorithms using OpenMP (similarly in XMT). ! Extend BFS based and Hopcroft-Karp algorithm for better parallel performance. ! Understanding three different architectures and fine tuning the algorithms for best performance on them. Focus: Unweighted Bipartite Graph A basic algorithm a b a’ b’ a b a’ b’ a b a’ b’ Initial Matching Find Augmenting Path Increase Matching and Continue Algorithms with Augmenting path search ! BFS/DFS based algorithm: ! Find a maximal set of vertex disjoint augmenting paths of any length (DFS; DFS+Lookahead; BFS) ! Augment along these paths, and repeat ! Advanced Algorithm (Hopcroft-Karp): ! Find a maximal set of vertex disjoint augmenting paths of shortest length (BFS+DFS) ! Augment along these paths, and repeat For G=(V,E), |V|=n, |E|=m Augmenting Paths in Parallel • Two strategies: – Level Parallel (BFS): Search for paths from all unmatched vertices in parallel, a level at a time – Source parallel (DFS): Each thread starts from an unmatched vertex to find a path Source Parallel Level Parallel T 1 T 2 T 1 T 2 T 1 T 2 T 1 T 2 T 1 T 2 Level parallel construction (HK) a...

Website: www.cs.purdue.edu | Filesize: -
No of Page(s): 23
Download Parallel Maximum Matching algorithms on Multithreaded Platforms.pdf