互连网络的连通性和诊断度

Mass data processing and complex problem solving have higher and higher demands for performance of parallel computer systems. The interconnection network determines the performance of a parallel computer system. In the design of an interconnection network, one of the most fundamental considerations is the connectivity and diagnosability of the network. This project is to study the new connectivity and new diagnosability problems of the network. Firstly, we plan to give and prove the g-good-neighbor connectivity and diagnosability of some well-known networks. We plan to to give and prove the g- extra connectivity and diagnosability of some well-known networks. We plan to improve the concept of natural diagnosability of networks, to give and prove the natural connectivity and diagnosability of some networks. For a naturally diagnosable system, we plan to give an algorithm of parallel computer systems, which can effectively identify the set of faulty processors. We plan to improve the concept of strong connectivity of networks, to give and prove the strong connectivity of some networks..The expected results of this project will provide theoretical basis for engineers when designing or selecting underlying interconnection networks for parallel computer systems.

海量数据的处理和复杂问题的解决对并行计算机系统性能的要求愈来愈高；互连网络对并行计算机系统的性能起着决定性的作用。连通性和可诊断性是设计互连网络时的一个基本考虑。本项目拟研究网络的新连通性和新可诊断度问题。拟给出和证明一些著名网络的g好邻连通度和诊断度；拟给出和证明一些著名网络的g限制连通度和诊断度；拟完善网络的自然诊断度概念和给出和证明一些网络的自然连通度和诊断度，对于一个自然可诊断的系统，拟给出一种算法，可以有效地识别出所有故障处理器。 拟完善网络的强连通度概念和求一些网络的强连通度。为并行计算机系统的互连网络的设计和选择提供理论依据。

海量数据的处理和复杂问题的解决对并行计算机系统性能的要求愈来愈高；互连网络对并行计算机系统的性能起着决定性的作用。本项目在科学出版社出版专著一部，发表学术论文49篇，其中在《Theoretical Computer Science》、《Discrete Applied Mathematics》、《The Computer Journal》等国内外SCI收录的刊物上发表论文25篇；在《Journal of Interconnection Networks》等国内外EI收录的刊物上发表论文14篇。互连网络的连通性和诊断度是两个重要的研究课题。在这个项目中，给出和证明了网络的g好邻（g限制）t可诊断转化为数学问题的修正的充分必要条件。网络的g好邻诊断度是刻画在g好邻的条件下能找到最多故障处理器的个数。在这个项目中，给出和证明了网络alternating group graph，exchanged hypercube，arrangement graph，bubble-sort graph，expanded k-ary n-cube和wheel graph等的g好邻诊断度或自然诊断度。网络的g限制诊断度是刻画在g限制的条件下能找到最多故障处理器的个数。在比较模型里是一个困难的数学问题。在这个项目中，给出和证明了网络hyper petersen graph，crossed cube，locally twisted cube，nest graph等的g限制诊断度。网络的局部诊断度和上面的两种诊断度不同是刻画每个点的诊断度。在这个项目中，给出和证明了网络arrangement graph，expanded k-ary n-cube，bubble-sort star graph，nest graph，alternating group graph等的局部诊断度。网络的连通度、高阶连通度、超连通度和强连通度是网络的基本参数，求它们有一定的难度。在这个项目中，给出和证明了网络godan graph, wheel graph，alternating group graph，crossed cube, bubble-sort star graph，leaf-sort graph等的高阶或超或强连通度。上面的研究成果，为工程师设计网络提供了理论依据。