Coarse grained parallel algorithms

申请人提出的粗粒度多计算机（CGM）模型提供了一个简单实用的模型来分析并行算法的性能，特别是处理器集群的性能。CGM模型引起了相当大的关注（例如Algorithmica的两个特刊），申请人一直处于研究的前沿，表明通过使用CGM算法可以在理论上和实践中实现显着的速度提高。在上一个资助期间，我们提供了并行外部存储器的通用算法解决方案（解决了ACM计算战略方向研讨会上提出的挑战），我们提出了用于基本图问题，计算几何和动态规划的高效CGM算法。我们构建了第一个并行软件原型，它可以以每小时超过1tb的速度构建数据立方体，这是数据仓库/OLAP的中心数据结构。我们对并行k顶点覆盖的CGM算法的研究导致了第一个并行软件原型，该软件可以在超过1000个序列的输入数据集的多个序列比对中识别错误的基因组或蛋白质序列。以下是下一个资助期拟议研究的主要重点。(1)并行缓存：我们建议扩展我们的并行外部存储器解决方案，以研究利用多个并行缓存的高效可扩展的CGM算法。(2)并行MDX查询：为了对大型多维数据集的分析提供并行支持，我们建议在并行数据立方体构建方法中添加一套完整的支持数据立方体并行MDX查询的CGM算法和软件原型。(3)生物信息学的平行固定参数可追溯性：我们建议对生物信息学中具有固定参数可追溯性的np完全问题进行可能的并行CGM算法（和软件原型）的全面研究。(4)平行蛋白质相互作用预测：我们提出了一种高效、可扩展、实用的CGM算法和软件原型来预测两种蛋白质之间相互作用的概率问题。

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.