Coarse grained parallel algorithms

粗粒度并行算法

• 批准号: 9173-2006
• 负责人: Dehne, Frank
• 金额: $ 3.13万
• 依托单位: Carleton University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2008
• 资助国家: 加拿大
• 起止时间: 2008-01-01 至 2009-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=389920
• 关键词: Coarse; grained; parallel; algorithms

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.

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