层次网络的嵌入限制连通性及子网排除问题研究

项目名称： 层次网络的嵌入限制连通性及子网排除问题研究

项目编号： No.U1304601

项目类型： 联合基金项目

立项/批准年度： 2014

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

项目作者： 杨玉星

作者单位： 河南师范大学

项目金额： 30万元

中文摘要： 海量数据的处理和复杂问题的解决对并行计算机系统性能的要求愈来愈高；并行计算机系统的性能主要取决于其互连网络的性质。针对目前度量网络连通性的参数均未考虑“子网嵌入”的问题，结合层次网络中对子网嵌入的实际需求，课题提出层次网络中两个新的连通性度量参数，即嵌入限制连通度和嵌入限制边连通度；拟研究嵌入限制（边）连通度和其它连通性度量参数之间的关系；设计层次网络中嵌入限制点割和嵌入限制边割的求解算法；计算层次网络的嵌入限制（边）连通度。为了更好地度量层次网络的容错能力，课题拟研究层次网络的“子网排除”问题，设计求解层次网络的“子网排除点割”和“子网排除边割”的有效算法，据此计算层次网络的子网排除数，并探究层次网络的嵌入限制连通性和子网排除问题之间的关系，为并行计算机系统的互连网络的设计和选择提供理论依据。

中文关键词： 并行计算机系统；互连网络；容错；连通度；子网排除

英文摘要： Mass data processing and complex problem solving have higher and higher demands for performance of parallel computer systems, and the interconnection network determines the performance of a parallel computer system. The current parameters to evaluate the connectivity of hierarchical interconnection networks do not consider the demands of embedding subnets into the components of the graph which obtained by removing faulty vertices or faulty edges from the original interconnection networks. To compensate for this shortcoming, we present two new parameters, the k-restricted vertex connectivity and the k-restricted edge connectivity of a hierarchical interconnection network. We will investigate the relationships among the above two parameters and other connectivities of recursive interconnection networks, and explore algorithms to find their k-restricted vertex cuts and k-restricted edge cuts of hierarchical interconnection networks. In addition, the k-restricted vertex connectivity and k-restricted edge connectivity of hierarchical interconnection networks will be derived. In order to measure the fault tolerance of some hierarchical interconnection networks, we plan to research the subnet preclusion problem, and design effective algorithms to find k-dimensional subnet preclusion vertex cuts and k-dimensional subnet

英文关键词： parallel computer systems；interconnection networks；fault tolerance；connectivity；subnetworks preclusion