6

High-Performance Phylogenetic Inference

Software tools based on the maximum likelihood method and Bayesian methods are widely used for phylogenetic tree inference. This article surveys recent research on parallelization and performance optimization of state-of-the-art tree inference tools. …

Benchmarking for Graph Clustering and Partitioning

Engineering Algorithms for Computational Biology

High Performance Algorithm Engineering for Large-Scale Problems

Algorithm engineering refers to the process required to transform a pencil-and-paper algorithm into a robust, efficient, well tested, and easily usable implementation. Thus it encompasses a number of topics, from modeling cache behavior to the …

Sorting Signed Permutations by Reversal (Reversal Distance)

Benchmarking for Graph Clustering and Partitioning

Evaluating Multicore Processors and Accelerators for Dense Numerical Computations

In this chapter, we empirically evaluate fundamental design trade-offs among current multicore processors and accelerator technologies and their impact on dense numerical computations. The main objectives of this work are to understand the …

Parallel Community Detection for Massive Graphs

Tackling the current volume of graph-structured data requires parallel tools. We extend our work on analyzing such massive graph data with a massively parallel algorithm for community detection that scales to current data sizes, clustering a …

Parallel community detection for massive graphs

Computational Challenges in Emerging Combinatorial Scientific Computing Applications

In this chapter, we describe several novel uses of combinatorial techniques that have found widespread use in realms outside traditional scientific computing. The “emerging” scientific disciplines of social and technological network analysis and …

Fundamental Questions in the Analysis of Large Graphs

Graphs are a general approach for representing information that spans the widest possible range of computing applications. They are particularly important to computational biology, web search, and knowledge discovery. As the sizes of graphs increase, …

Graph Algorithms

Hybrid Programming With SIMPLE

Large-Scale Network Analysis

Centrality analysis deals with the identification of critical vertices and edges in real-world graph abstractions. Graph-theoretic centrality heuristics such as betweenness and closeness are widely used in application domains ranging from social …

Spanning Tree, Minimum Weight

SWARM: A Parallel Programming Framework for Multicore Processors

S oftW are and A lgorithms for R unning on M ulti-core (SWARM) is a portable open-source parallel library of basic primitives for programming multicore processors. SWARM is built on POSIX threads that allows the user to use either the already …

Combinatorial Algorithm Design on the Cell/B.E. Processor

Combinatorial algorithms play a subtle, yet important, role in traditional scientific computing. Perhaps the most well-known example is the graph partitioning formulation for load-balanced parallelization of scientific simulations. Partitioning …

Designing Fast Fourier Transform for the IBM Cell Broadband Engine

The Cell Broadband Engine (or the Cell/B.E.) [6, 16, 17, 34] is a novel high-performance architecture designed by Sony, Toshiba, and IBM (STI), primarily targeting multimedia and gaming applications. The Cell/B.E. consists of a traditional …

The Case of the Fast Financial Feed

Traditional scientific HPC applications running on high-end computing platforms are not the only class of applications dependent on the availability of high-performance communication services. As Chapter 12 points out, many classes of enterprise …

Engineering Algorithms for Computational Biology

High Performance Algorithm Engineering for Large-scale Problems

Algorithm engineering refers to the process required to transform a pencil-and-paper algorithm into a robust, efficient, well tested, and easily usable implementation. Thus it encompasses a number of topics, from modeling cache behavior to the …

Sorting Signed Permutations by Reversal (Reversal Distance)

Design of Multithreaded Algorithms for Combinatorial Problems

Graph theoretic and combinatorial problems arise in several traditional and emerging scientific disciplines such as VLSI design, optimization, databases, and computational biology. Some examples include phylogeny reconstruction [65,66], …

Efficient Parallel Graph Algorithms for Shared-memory Multiprocessors

Graph theoretic and combinatorial problems arise in several traditional and emerging scientific disciplines such as VLSI design, optimization, databases, and computational biology. Some examples include phylogeny reconstruction [65,66], …

Multithreaded Algorithms for Processing Massive Graphs

In this chapter, we consider the applicability of a non-traditional massively multithreaded architecture, the Cray MTA-2 [13], as a platform for graph algorithms. Graph-theoretic problems have emerged as a prominent computational workload in the …

High-Performance Algorithms for Phylogeny Reconstruction with Maximum Parsimony

All biological disciplines are united by the idea that species share a common history. These relationships are crucial to the understanding of biological evolution and biological mechanisms in medical and pharmaceutical research. The evolutionary …

High-Performance Phylogeny Reconstruction Under Maximum Parsimony

This chapter contains sections titled: Introduction Maximum Parsimony Exact MP: Parallel Branch and Bound MP Heuristics: Disk-Covering Methods Summary and Open Problems References

Parallel Algorithm Design for Branch and Bound

Large and/or computationally expensive optimization problems sometimes require parallel or high-performance computing systems to achieve reasonable running times. This chapter gives an introduction to parallel computing for those familiar with serial …

Algorithm Engineering for Parallel Computation

The emerging discipline of algorithm engineering has primarily focused on transforming pencil-and-paper sequential algorithms into robust, efficient, well tested, and easily used implementations. As parallel computing becomes ubiquitous, we need to …