HIPC 2001 Keynote Talk: Using PRAM Algorithms on a Uniform Memory Access Shared-Memory Architecture
Abstract
Shared-memory architectures with uniform memory access come very close to the PRAM, the theoretical model of parallel computing, and stand in sharp contrast to the common cluster approach. While PRAM algorithms have been devised for a large variety of combinatorial problems in graphs, strings, and geometry, none has been run successfully on a conventional parallel machine – the irregular nature of the computations cause a tremendous communication load and make the parallel machine run much more slowly than a simple workstation. Our preliminary results indicate that true shared-memory architectures, such as the Sun Enterprise 10000, run these same PRAM algorithms quite efficiently, showing effective speedups and thus opening up the possibility of leveraging over 20 years of research in PRAM algorithms for practical applications that require complex combinatorial optimization (such as sequence alignment and tree reconstruction problems that arise in genomics and bioinformatics).
Speaker Biography
David A. Bader is an Assistant Professor of Electrical & Computer Engineering at The University of New Mexico, and received his Ph.D. in Electrical Engineering in 1996 from The University of Maryland. David’s recent research experiences highlight his ability to bridge the gap between application and computer science. For example, while an NSF CISE Postdoctoral Research Associate in Experimental Computer Science, David worked closely with Earth scientists at NASA/GSFC and University of Maryland’s Geography Department to develop a high-performance system for on-demand queries of terascale remotely-sensed Earth science data, such as 4km AVHRR global coverage, used for monitoring long-term global studies of the Earth. In addition to developing some of the fastest known portable, high-performance algorithms for image segmentation and classification applications, combinatorial problems such as sorting and selection, and data communication primitives, David’s recent research has produced a new, preliminary methodology for programming UMA shared-memory machines and clusters of SMP nodes.
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.