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. …

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 …

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 …

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 …

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 …

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, …

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 …

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 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 …

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 …

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 …

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 …

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], …

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], …

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 …

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 …

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

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 …

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 …