David A. Bader
IEEE Fellow
AAAS Fellow
College of Computing
Georgia Tech
Atlanta, GA 30332



High-Performance Algorithm Engineering for Large-Scale Graph Problems and Computational Biology

Many large-scale optimization problems rely on graph theoretic solutions; yet high-performance computing has traditionally focused on regular applications with high degrees of locality. We describe our novel methodology for designing and implementing irregular parallel algorithms that attain significant performance on high-end computer systems. Our results for several fundamental graph theory problems are the first ever to achieve parallel speedups. Specifically, we have demonstrated for the first time that significant parallel speedups are attainable for arbitrary instances of a variety of graph problems and are developing a library of fundamental routines for discrete optimization (especially in computational biology) on shared-memory systems.

Phylogenies derived from gene order data may prove crucial in answering some fundamental questions in biomolecular evolution. High-performance algorithm engineering offers a battery of tools that can reduce, sometimes spectacularly, the running time of existing approaches. We discuss one such such application, GRAPPA, that demonstrated over a billion-fold speedup in running time (on a variety of real and simulated datasets), by combining low-level algorithmic improvements, cache-aware programming, careful performance tuning, and massive parallelism. We show how these techniques are directly applicable to a large variety of problems in computational biology.

Publication History

Versions of this paper appeared as:
  1. D.A. Bader, ``High-Performance Algorithm Engineering for Large-Scale Graph Problems and Computational Biology,'' Proc. 4th International Workshop on Efficient and Experimental Algorithms (WEA), Lecture Notes in Computer Science, 3503:16-21, May 2005.

Download this report in Adobe PDF


Last updated: July 14, 2011


Computational Biology

Parallel Computing