Parallel computing on interconnection networks and for sequence analysis

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

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.