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

项目名称： RHL网络中不相交并行计算结构的嵌入研究

项目编号： No.61303205

项目类型： 青年科学基金项目

立项/批准年度： 2014

项目学科： 自动化技术、计算机技术

项目作者： 王岩

作者单位： 苏州大学

项目金额： 22万元

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

中文关键词： 互连网络；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 in

英文关键词： Interconnection Network；RHL Network；Disjoint Binomial-like Trees；Disjoint Paths；Algorithm