CAREER: High-Performance Algorithms for Scientific Applications

Parallel computing has long offered the promise of very high performance, but it has delivered

only in a narrow range of applications. Exploiting parallelism at the level of large distributed-memory

systems is hampered by the cost of message-passing, while shared-memory systems remain mostly

small-scale. With the advent of symmetric multiprocessors (SMPs), however, shared-memory on a

modest scale is becoming an available commodity. High-performance gigabit networks allow scalable applications to run on large clusters of SMPs. Over the next five to ten years, clusters of SMPs will likely be the predominant architecture for scalable high-performance computing; however, little work has been done to date to support effective parallel computing on these SMP clusters.

Preliminary work we have conducted indicates that it is possible to improve upon current programming

methods for SMP clusters. In this career award the goal is to develop, implement, assess, and

refine algorithms for SMP clusters for irregular (e.g., string-, tree-, and graph-based) computations that

will deliver significant speedups on typical configurations of SMP clusters and scale gracefully with

the number of processors. The research will investigate new algorithms and a library of basic routines to

support irregular computations, mostly tree- and graph- based, along with new insights on how to leverage

the theoretical research in PRAM algorithms. Science-driven problems in genomics,bioinformatics, and computational ecology will provide the focus for this research.

The education component of this project includes mentoring high school and minority students, diseminating research results through talks and papers, and presenting tutorials at key conferences and

workshops. Prior mentoring has produced several individual and group teams that have won first place in both local and national competitions and mentoring will continue activities with minority groups, such as the National Society of Black Engineers and Native American Pueblo student groups.