Intel® Parallel Computing Center at Purdue University

Purdue University logo

Principal Investigator:

Alex Pothen portrait

Alex Pothen is a professor of computer science at Purdue University. He led the founding of the Combinatorial Scientific Computing (CSC) research community, which now holds biennial conferences organized through the Society for Industrial and Applied Mathematics (SIAM). He directed the CSCAPES Institute, a pioneering multi-institutional research center for developing parallel graph algorithms on leadership-class supercomputers. He is currently involved in the Exascale Computing Project of the U.S. Department of Energy. He is an editor of the Journal of the ACM, and was editor of SIAM Review and SIAM Books. He has mentored more than twenty PhD students and postdoctoral scholars. He is a Fellow of SIAM.

Description:

We consider a paradigm for designing parallel algorithms for computing significant subgraphs of graphs through approximation algorithms. Algorithms for solving these problems exactly are impractical for massive graphs, and possess little concurrency.

We explore this paradigm by considering a matching problem and an edge cover problem. Given natural number b(v) for every vertex v in a graph, a maximum weight b-matching is a set of edges M such that at most b(v) edges in M have v as an endpoint, and subject to this restriction, the sum of weights of the edges in M is maximum. Similarly a minimum weight edge cover in the graph is a set of edges C such that at least b(v) edges in C have v as an endpoint.

Algorithms for solving these problems exactly require only polynomial time, but they are still impractical on massive graphs. Approximation algorithms can deliver solutions that are guaranteed to be within than a constant factor of the optimal solution, and can do so in time nearly linear in the size of the graph. However, these algorithms do not have much parallelism, and hence we explore the design of new approximation algorithms with high levels of concurrency.

For b-matching, we have designed a b-Suitor algorithm that is based on vertices making proposals to match to their neighbors. This is related to a Suitor algorithm for computing 1-matchings designed by Fredrik Manne and Mahantesh Halappanavar. This algorithm is also related to the classical Gale-Shapley algorithm for the Stable Matching problem. Our implementations show that the b-Suitor algorithm is currently the fastest algorithm on serial, shared memory and distributed memory computers.

The b-edge cover problem has a Greedy approximation algorithm with an approximation ratio of three / two; however, here the effective weight of edges need to be dynamically updated, which limits the concurrency severely. We have reduced this problem to one of computing a b’-matching for a suitable value of b’(v), and this avoids the dynamic weight update problem. However, this is accomplished with a worse approximation ratio of two. The minimum weight b-edge cover problem is also rich in the space of approximation algorithms, and we consider nine such algorithms in this project. We are implementing the new approximation algorithms on a multicore shared-memory and distributed memory multiprocessors.

The b-edge cover problem and b-matching problem have applications in graph-based semi-supervised machine learning ad well as adaptive data anonymization problems. We are exploring the effectiveness of these algorithms and comparing them to earlier approaches.

Publications:

Related Website:

For more complete information about compiler optimizations, see our Optimization Notice.