Dagstuhl Seminar: 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).

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.