Coarse grained parallel algorithms

粗粒度并行算法

• 批准号: 9173-2006
• 负责人: Dehne, Frank
• 金额: $ 3.13万
• 依托单位: Carleton University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=364635
• 关键词: 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 模型引起了相当大的关注（例如 Algorithmica 的两期特刊），并且申请人一直处于研究的前沿，表明通过使用 CGM 算法，无论在理论上还是在实践中都可以实现显着的速度改进。在上一个资助期间，我们为并行外部存储器提供了通用算法解决方案（解决了 ACM 计算战略方向研讨会上提出的挑战），并针对基本图问题、计算几何和动态规划提出了高效的 CGM 算法。我们构建了第一个并行软件原型，可以以每小时超过 1 TB 的速度构建数据立方体（数据仓库/OLAP 的中央数据结构）。我们对并行 k 顶点覆盖的 CGM 算法的研究产生了第一个并行软件原型，该原型可以在具有超过 1000 个序列的输入数据集的多个序列比对中识别错误的基因组或蛋白质序列。以下是下一资助期拟议研究的主要内容。 (1) 并行缓存：我们建议将并行外部存储器的解决方案扩展到研究利用多个并行缓存的高效且可扩展的 CGM 算法。 (2)并行MDX查询：为了为大型多维数据集的分析提供并行支持，我们建议在并行数据立方体构建方法中添加一整套支持数据立方体并行MDX查询的CGM算法和软件原型。 (3) 生物信息学的并行固定参数易处理性：我们建议对生物信息学中固定参数易处理的 NP 完全问题的可能并行 CGM 算法（和软件原型）进行全面研究。 (4)并行蛋白质相互作用预测：我们建议针对预测两种蛋白质之间相互作用的概率问题开发一种高效、可扩展且实用的CGM算法和软件原型。