Grant: Discovery Grants Program - Individual

The Coarse Grained Multicomputer (CGM) model, which was proposed by the applicant, provides a simple and practical model to analyze the performance of parallel algorithms, in particular for processor clusters. The CGM model has attracted considerable attention (e.g. two special issues of Algorithmica) and the applicant has been at the forefront of research showing that significant speed improvements can be achieved, theoretically AND in practice, through the use of CGM algorithms. During the last funding period, we provided a general algorithmic solution for parallel external memories (solving a challenge posed at the ACM Workshop on Strategic Directions in Computing), and we presented efficient CGM algorithms for fundamental graph problems, Computational Geometry and dynamic programming. We built the first parallel software prototype that can build data cubes, a central data structure for data warehousing/OLAP, at a rate of more than one TB per hour. Our study of CGM algorithms for parallel k-vertex cover led to the first parallel software prototype that can identify erroneous genome or protein sequences in multiple sequence alignments for input data sets with more than 1000 sequences. The following are the main thrusts of the proposed research for the next funding period. (1) Parallel caches: We propose to extend our solutions for parallel external memories towards the study of efficient and scalable CGM algorithms that utilize multiple, parallel caches. (2) Parallel MDX queries: In order to provide parallel support for the analysis of large multidimensional data sets, we propose to add to our parallel data cube construction methods a full set of CGM algorithms and software prototypes that support parallel MDX queries on data cubes. (3) Parallel fixed parameter tractability for bioinformatics: We propose to conduct a comprehensive study of possible parallel CGM algorithms (and software prototypes) for NP-complete problems in bioinformatics that are fixed parameter tractable. (4) Parallel protein interaction prediction: We propose to develop an efficient, scalable and practical CGM algorithm and software prototype for the problem of predicting the probability of an interaction between two proteins.