Designing practically efficient parallel algorithms with rigorously analyzed run time guarantees seems to be difficult for a large class of problems, commonly known as irregularly structured problems. The solutions for such problems typically depend on run time workload monitoring and dynamic load balancing, and the run time is often critically dependent on the particular instance of the problem being solved with no easy way to guarantee optimal, worst-case run times. The goal of the proposed research is to design theoretically rigorous and practically efficient parallel algorithms for selected irregular applications and to develop software to demonstrate their effectiveness. Research will also be conducted in developing distributed tree data structures and software libraries to support these and other irregular applications. Three important classes of applications will be studied: grid and particle based methods in scientific computing, sequence alignment problems in computational biology, and computing aggregates on multidimensional data cubes in data mining. The work in scientific computing will be focused on providing spatial data structure support for problems such as molecular dynamics, adaptive mesh refinement and multigrid methods. Several computationally intensive irregular problems in sequence homology detection will be studied including spliced sequence alignments for gene discovery, multiple sequence alignments to discover protein motifs and full genome comparisons for comparative genomics. The third application area is computation of aggregates on multidimensional data. Using techniques from computational geometry, efficient parallel algorithms for computing aggregates and answering queries on sparse, multidimensional data sets will be developed. The goal is to discover common underlying themes to provide a unifying way to address seemingly disparate problem areas. For example, spatial distribution of the data or the geometrical structure of the problem domain is the source of irregularity for most of the problems considered. Similarly, tree data structures are often the backbone of parallel algorithms for many irregularly structured problems.
The broader impacts of the proposed research include fundamental contributions to solving irregularly structured problems, a major theme of research in parallel processing. Student participation in research is pursued using multiple strategies - graduate students through direct funding under the project, undergraduate students via senior design projects, female students through Iowa State's Women in Science and Engineering program, and minority students through collaboration with a minority serving institution.
