The goal of this Career project is to apply techniques from parallel computing and computational geometry to develop theoretically sound and practically efficient parallel algorithms for a class of irregular scientific applications and to infuse the resulting knowledge into parallel computing and computational science programs. The main goal of the research is to develop parallel algorithms and software for scientific applications that depend upon interactions between entities (such as particles, atoms) located in two or three dimensional space. To achieve this goal, a two- pronged strategy will be used: Firstly, efficient parallel solutions will be developed for specific applications. Secondly, general techniques useful for parallelizing irregular applications that depend on multidimensional point sets will be investigated. Two specific applications, considered to be Grand Challenge problems by the High Performance Computing and Communications (HPCC) Subcommittee, will be studied: The N-body problem and Protein Accessible Surface Area Calculations. The N- body problem is to simulate the motion of particles under the influence of mutual force fields based on an inverse square law. N-body computations are useful in such diverse fields as astrophysics, plasma physics, molecular and fluid dynamics, computer graphics and numerical complex analysis. Protein Accessible Surface Area calculations are used to study the structure of proteins, an important problem in computational molecular biology. The access patterns required by many scientific applications that depend on distribution of particles/atoms can be abstracted into primitive queries on multidimensional point sets. General techniques for efficient parallel execution of such applications will be investigated and software to aid programming such applications will be developed. Education Plan: The main goal of the education plan is to develop curriculum in parallel computing and computational science at New Mexico State University and to train students to apply computer science principles in solving important scientific applications on future generation computing systems. A course in parallel computing has already been developed and a textbook on algorithm design for parallel computers is being written. Additional courses in parallel computing will be developed and introduced. It is intended to develop curriculum and establish a new computational science program on campus. The results of the proposed research will be integrated into courses in parallel computing and computational science.
