HIPS Invited Talk
``Using PRAM Algorithms on a Uniform Memory Access
Shared-Memory Architecture''
by David Bader (University of New Mexico, USA)
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.