Parallel computing on interconnection networks and for sequence analysis

互连网络上的并行计算和序列分析

• 批准号: 170168-2011
• 负责人: Qiu, Ke
• 金额: $ 1.31万
• 依托单位: Brock University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=569553
• 关键词: Parallel; computing; interconnection; networks; sequence

My research is concerned with designing efficient parallel algorithms. Specifically, I will concentrate on (1) parallel algorithms and data structures, and (2) combinatorial/graph theoretical properties of interconnection networks. Both fundamental and application algorithms will be considered. Fundamental algorithms are algorithms that many applications use frequently. They include routing algorithms, broadcasting (and its variations) and various other data communication algorithms. As for applications, various problems will be considered, e.g., the traditional combinatorial ones such as sorting and searching, graph algorithms and algorithms in computational geometry, as well as algorithms for sequence comparison/analysis in bioinformatics. The underlining topology for a machine is important to the design of system software such as message passing interface, application algorithms, communication primitives, and thus, the overall performance of the system. We will investigate the topological/combinatorial properties of some of the networks such as Cayley graphs so that we can take advantage of these properties in designing efficient routing/communication algorithms and parallel application algorithms. Another interesting and important aspect of interconnection networks is their combinatorial properties such as the Whitney numbers of the second kind for the poset associated with the graphs (also known as the surface area). These numbers have applications in computing various bounds for data communications, average distances, and transmissions of graphs. In addition, such a study may have applications in genome rearrangement since the vertex set of a Cayley graph is a set of permutations and the vertices may represent genomes and mutations from one genome to another is equivalent to routing on certain Cayley graphs.

我的研究涉及设计高效的并行算法。具体来说，我将专注于（1）并行算法和数据结构，以及（2）互连网络的组合/图理论属性。 基础算法和应用算法都会被考虑。基本算法是许多应用程序经常使用的算法。它们包括路由算法、广播（及其变体）和各种其他数据通信算法。在应用方面，会考虑各种问题，例如排序和搜索等传统的组合问题，图算法和计算几何中的算法，以及生物信息学中的序列比较/分析算法。 机器的底层拓扑对于系统软件的设计非常重要，例如消息传递接口、应用算法、通信原语以及系统的整体性能。我们将研究一些网络（例如凯莱图）的拓扑/组合属性，以便我们可以利用这些属性来设计高效的路由/通信算法和并行应用算法。互连网络的另一个有趣且重要的方面是它们的组合属性，例如与图相关的偏序集的第二类惠特尼数（也称为表面积）。这些数字可用于计算数据通信、平均距离和图形传输的各种界限。此外，这样的研究可能在基因组重排方面有应用，因为凯莱图的顶点集是一组排列，并且顶点可以代表基因组，并且从一个基因组到另一个基因组的突变相当于在某些凯莱图上的路由。