Engineering Papers⌕ Search

Engineering topics

Azad, Md Ariful

Publications and source records attributed to Azad, Md Ariful.

Evaluation of Graph Analytics Frameworks Using the GAP Benchmark Suite

The analysis of connected data is an increasingly important application in high-performance computing. Such analyses can reveal fraudulent patterns in financial transactions, optimize telecommunications networks, predict information flow in social networks, etc. However, the landscape of graph analytics is highly diverse. Graph algorithms stress processor architectures differently, and no one graph can represent all topologies. Consequently, no single approach or framework is expected to be optimal for all graph analytics problems. To help make sense of this diverse landscape, we evaluated four approaches to graph analytics: GraphBLAS, Galois, BGL17, GraphIt; and compare them against hand-tuned implementations that take advantage of hardware features on our test platform. Graph- BLAS formulates graph analytics as sparse linear algebra. Galois provides syntactic constructs for data parallelism over irregular data structures. BGL17 is a generic C++ template library for implementing graph algorithms. GraphIt provides a domain- specific language to describe and optimize graph algorithms. We use the GAP Benchmark Suite to establish baseline performance and guide the side-by-side evaluation of each framework. GAP consists of 30 tests: six graph analytics algorithms (breadth- first search, single-source shortest path, PageRank, betweenness centrality, connected components, and triangle counting) run on five graphs, each with different topological characteristics (e.g., high diameter, skewed degree distribution, high average degree). High-performance reference implementations are included for each benchmark algorithm. Because a graph can be loaded into memory a number of ways (e.g., flat file on disk, compressed sparse format, data frames, retrieved from SQL or NoSQL databases), our evaluation focused on computational performance rather than I/O. Our results show the relative strengths of each framework.

Graph algorithms, Benchmarking, shared-memory prog↗

Parallel Maximum Cardinality Matchings via Tree-Grafting

This software implements a new algorithm and its shared-memory parallelization for computing maximum cardinality matchings in bipartite graphs. The algorithm searches for augmenting paths via specialized breadth-first searches (BFS) from multiple source vertices, hence creating more parallelism than single source algorithms.

Buluc, Aydin↗

Codesign Lessons Learned from Implementing Graph Matching on Multithreaded Architectures

Co-design of algorithms and architectures is an effective way to address the performance of irregular applications on multithreaded architectures. We explore the interplay between algorithm design and architectural features using graph matching as a case study. We present the key lessons that we have learnt as a means to influence co-design of algorithms and architecture for execution of data-intensive irregular workloads.

matching, graph algorithms, multithreaded architec↗

On Parallel Push-Relabel based Algorithms for Bipartite Maximum Matching

We study multithreaded push-relabel based algorithms for computing maximum cardinality matching in bipartite graphs. Matching is a fundamental combinatorial (graph) problem with applications in a wide variety of problems in science and engineering. We are motivated by its use in the context of sparse linear solvers for computing maximum transversal of a matrix. We implement and test our algorithms on several multi-socket multicore systems and compare their performance to state-of-the-art augmenting path-based serial and parallel algorithms using a testset comprised of a wide range of real-world instances. Building on several heuristics for enhancing performance, we demonstrate good scaling for the parallel push-relabel algorithm. We show that it is comparable to the best augmenting path-based algorithms for bipartite matching. To the best of our knowledge, this is the first extensive study of multithreaded push-relabel based algorithms. In addition to a direct impact on the applications using matching, the proposed algorithmic techniques can be extended to preflow-push based algorithms for computing maximum flow in graphs.

Push-relabel, matching, bipartite↗

Multithreaded Algorithms for Maximum Matching in Bipartite Graphs

Abstract—We design, implement, and evaluate algorithms for computing a matching of maximum cardinality in a bipartite graph on multi-core and massively multithreaded computers. As computers with larger number of slower cores dominate the commodity processor market, the design of multithreaded algorithms to solve large matching problems becomes a necessity. Recent work on serial algorithms based on searching for augmenting paths for this problem have shown that their performance is sensitive to the order in which the vertices are processed for matching. In a multithreaded environment, imposing a serial order in which vertices are considered for matching would lead to loss of concurrency and performance. But this raises the question: Would parallel matching algorithms on multithreaded machines improve performance over a serial algorithm? We answer this question in the affirmative. We report efficient multithreaded implementations of two key algorithms (Hopcroft- Karp based on breadth-first-search, and Pothen-Fan based on depth-first-search) and their variants, combined with the Karp- Sipser initialization algorithm. We report extensive results and insights using three shared-memory platforms (a 48-core AMD Opteron, a 32-core Intel Nehalem, and a 128-processor Cray XMT) on a representative set of real-world and synthetic graphs. To the best of our knowledge, this is the first extensive study of augmentation-based parallel algorithms for bipartite cardinality matching.

Azad, Md Ariful↗