A Multi-Level Parallel Implementation of a Program for Finding Frequent Patterns in a Large Sparse Graph

Steve Reinhardt and George Karypis
12th International Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS'07), 2007
Download Paper
Graphs capture the essential elements of many
problems broadly defined as searching or
categorizing. With the rapid increase of data
volumes from sensors, many application disciplines
need to process larger graphs quickly. This paper
presents the results of parallelizing with OpenMP an
algorithm that finds, in a single large labeled
undirected sparse graph, the connected subgraphs
with a given minimum number of edge-disjoint
embeddings. Parallelism is exploited at two levels in
the algorithm. The lack of a priori knowledge of the
extent of parallelism for a given input required use of
a dynamic, multi-level approach based on the
proposed OpenMP taskq/task extensions. The
parallel implementation required the addition of 21
directives and about 50 accompanying lines of code,
in an original code of about 15,000 lines.
Experimental results show excellent speed-up to 30
processors for the graphs used, with a best speed-up
of 26.1 compared to the serial version. The
taskq/task constructs show promise for problems
exhibiting unstructured parallelism.
Research topics: Graph mining | Parallel processing