RHL网络中不相交并行计算结构的嵌入研究

Disjoint parallel computing architectures, including disjoint binomial-like spanning trees, disjoint Hamilton paths and disjoint Hamilton cycles, play important roles in improving reliability and efficiency of data transmission on interconnection networks. Restricted hypercube-like networks include several variants of hypercube which have features superior to those of hypercube. In this project, we will conduct research on embedding of disjoint parallel computing architectures in RHL networks. DBST are a set of disjoint spanning trees isomorphic to binomial-like tree. However, in existing works about embedding DBST in RHL networks, only disjoint spanning trees can be embedded into some RHL networks such as parity cubes, etc. Furthermore, these existing works above lack the research on architecture of trees. On the embedding DHP(DHC) in RHL networks, there are only some results on locally twisted cubes. And the methods in the existing works can not be applicable to all the RHL networks and are loss of the research on application. In this project, firstly we will conduct research on the method of embedding a set of DBST in several special RHL networks. And then we will provide a general method of embedding DBST in RHL networks and algorithms of embedding DHP(DHC) in RHL networks. Moreover, we will not only investigate the theoretical problems, but also use simulating experimentation to test the correctness of all embedding methods. Finally, we will apply DBST to the design of multi-path routing in feature space of human contact network.

不相交类二项树（DBST）、不相交哈密尔顿路（DHP）和不相交哈密尔顿圈（DHC）这些不相交并行计算结构在提高互连网络数据传输的可靠性和效率方面有重要的作用，局限类超立方体(RHL)网络包含若干个性质优越的超立方体变型。本项目将研究在RHL网络上不相交并行计算结构的嵌入问题。DBST是同构于类二项树的一组不相交生成树，但在现有RHL网络的研究中，只有奇偶立方体等可以嵌入不相交生成树，但是缺乏对树的结构的研究；关于RHL网络上DHP（DHC）的嵌入，也只有局部扭立方体等网络上有相应的研究成果；并且现有的方法不适用于所有的RHL网络且缺乏有关的应用研究。本项目拟首先研究在特殊RHL网络上嵌入一组DBST的方法，进而给出在RHL网络上嵌入DBST的通用方法以及DHP（DHC）的嵌入算法，而且将做模拟实验来验证所有嵌入方法的正确性，并将DBST应用在人类联系网络的特征空间中用于多路径路由的设计。

不相交类二项树（DBST）、不相交路径（圈）这些不相交并行计算结构在提高互连网络数据传输的可靠性和效率方面有重要的作用，局限类超立方体(RHL)网络包含若干个性质优越的超立方体变型。本项目主要研究在RHL 网络上不相交并行计算结构的嵌入问题，主要研究成果如下：（1）在扭立方体上提出了划分点集和同构规则的概念，解决了扭立方上DBST的嵌入问题；（2）在奇偶立方体上提出了一个嵌入DBST的算法，并证明算法的正确性和时间复杂度；（3）通过划分点和邻接子树的概念，在奇偶立方体上提出了并行嵌入n棵以任意顶点为根的DBST的算法；（4）定义了邻接拉丁方，在此基础上，给出了一个在n维扭立方体上嵌入n棵以任意顶点为根的DBST的并行算法；（5）完成了在交替组图和DCell网络上不相交路径的研究；（6）将研究结果扩展应用到了数据中心网络中。另外，我们还研究了奇偶立方体、莫比乌斯立方体上完全二叉树的嵌入问题。项目取得了一系列研究成果，发表了多篇论文，其中SCI检索3篇，EI检索4篇，且多篇论文在评审中。申请国家发明专利3项，获得软件著作权4项。协助指导4名硕士研究生，项目负责人获得博士学位，并晋升为副教授。同时，项目组成员积极参与国内外学术交流，其中项目负责人在澳大利亚阿德莱德大学计算机学院访学一年。