Feo, John T | Search NASA

DOE OSTI2012

Approximate Weighted Matching On Emerging Manycore and Multithreaded Architectures

Graph matching is a prototypical combinatorial problem with many applications in computer science and scientific computing, but algorithms for computing optimal matchings are challenging to parallelize. Approximate matching algorithms provide an alternate route for parallelization, and in many contexts compute near-optimal matchings for large-scale graphs. We present sharedmemory parallel implementations 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 implementation uses shared work queues, and is suited to all these platforms; the second implementation is based on dataflow principles, and exploits the architectural features of the Cray XMT. Using a carefully chosen dataset that exhibits characteristics from a wide range of real-world 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 good weak and strong scaling for graphs with up to a billion edges using up to 12, 800 threads. Given the breadth of this work, we focus on simplicity and portability of software rather than excessive fine-tuning for each platform. To the best of our knowledge, this is the first such large-scale study of the half-approximate weighted matching problem on shared-memory 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.

Halappanavar, Mahantesh↗

DOE OSTI2012

A Novel Multithreaded Algorithm For Extracting Maximal Chordal Subgraphs

Chordal graphs are triangulated graphs where any cycle larger than three is bisected by a chord. Many combinatorial optimization problems such as computing the minimum fill-in, the size of the maximum clique and the chromatic number are NP-hard on general graphs but have polynomial time solutions on chordal graphs. In this paper, we present a novel multithreaded algorithm to extract a maximal chordal subgraph from a general graph. Our algorithm is based on an iterative approach where each thread can asynchronously update a subset of edges that are dynamically assigned to it. We implement our algorithm on two different multithreaded architectures – Cray XMT, a massively multithreaded platform, and AMD Magny-Cours, a shared memory multicore platform. In addition to the proof of correctness, we present the performance of our algorithm using a testset of carefully generated synthetical graphs with up to half-a-billion edges and real world networks from gene correlation studies. We demonstrate that our algorithm achieves high scalability for all inputs on both types of architectures.

Halappanavar, Mahantesh↗

DOE OSTI2012

Multithreaded Algorithms for Graph Coloring

Graph algorithms are challenging to parallelize when high performance and scalability are primary goals. Low concurrency, poor data locality, irregular access pattern, and high data access to computation ratio are among the chief reasons for the challenge. The performance implication of these features is exasperated on distributed memory machines. More success is being achieved on shared-memory, multi-core architectures supporting multithreading. We consider a prototypical graph problem, coloring, and show how a greedy algorithm for solving it can be e*ectively parallelized on multithreaded architectures. We present in particular two di*erent parallel algorithms. The first relies on speculation and iteration, and is suitable for any shared-memory, multithreaded system. The second uses data ow principles and is targeted at the massively multithreaded Cray XMT system. We benchmark the algorithms on three di*erent platforms and demonstrate scalable runtime performance. In terms of quality of solution, both algorithms use nearly the same number of colors as the serial algorithm.

Catalyurek, Umit V↗