Los Alamos Invited Talk: The Productive Use of High-End Computers

Abstract

In this talk, we present a new framework for measuring the productivity of high-end systems, propose new performance metrics, and describe our novel methodology for designing irregular parallel algorithms for high-end systems (such as combinatorial optimization problems that arise in bioinformatics and computational biology) that offers significant promise for exploiting deep memory hierarchies. Our results for several basic 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, including spanning tree, ear decomposition, minimum spanning forest, maximum flow, and expression evaluation, and are developing a library of fundamental routines for discrete optimization (especially in computational biology) on shared-memory systems. For example, the minimum spanning tree (MST) is one of the most studied combinatorial problems with practical applications in VLSI layout, wireless communication, and distributed networks, recent problems in biology and medicine such as cancer detection, medical imaging, and proteomics, and national security and bioterrorism such as detecting the spread of toxins through populations in the case of biological/chemical warfare. Our new implementation for MST, on symmetric multiprocessors such as IBM’s p690/Regatta and Sun’s Enterprise servers, achieves good speedups over a wide range of input graphs with regular and irregular structures, when compared with the best sequential implementation.

David A. Bader

Distinguished Professor and Director of the Institute for Data Science

David A. Bader is a Distinguished Professor in the Department of Computer Science at New Jersey Institute of Technology.