代数图论和最优化方法及其在网络拓扑结构与算法中的应用

并行分布处理是当代计算机科学技术的主要研究领域之一。本项目研究并行分布处理中的几个基本问题及其在网络虚拟拓扑设计的应用,着重用代数图论和最优化方法来统一处理并行计算机拓扑结构,路由算法和负载分配以及在网络虚拟拓扑设计中的应用问题，使之能统一指导并行计算机系统与网络的设计与建造。我们知道，并行计算机的性能瓶颈主要是互连处理机之间的通讯延迟，因此并行计算机互连结构与通讯算法的研究是极其重要的。另一方面，为了充分利用并行计算机的处理能力，需要优良的资源分配方案，如何合理和透明地在处理机之间重新分配系统负载的研究也是十分重要的。第三, 一般网络的虚拟拓扑设计中广泛采用了并行计算机互连结构.主要研究内容有：基于陪集图的并行计算机互连结构与路由算法的一般理论；并行处理中负载分配研究的代数图论与最优化方法；并行计算机互连拓扑在网络虚拟拓扑设计中的应用。这些研究将对并行分布处理与网络的发展起促进作用.

我们已在互连结构与通讯算法及虚拟化的研究中取得了一系列重要的新成果，这些成果有的是在与国际著名专家的合作中完成的。继续已在进行的研究工作，以代数，图论和最优化方法为工具，以Cayley图和陪集图为模型，一致处理并行计算机互连结构、路由算法和负载分配方案以及一般网络虚拟拓扑设计的问题。特别是重点研究对等网络的虚拟拓扑(覆盖)设计的问题。.在2011年里，通过在计算机上进行模拟计算，进一步验证新得到的互连结构的拓扑性质、通讯算法和负载分配方案及一般网络虚拟拓扑设计原理，特别是重点验证新的互连结构作为网络虚拟拓扑是否可行，进一步改进已有的方法，主要是Cayley图小世界模型和图广义同态的方法。.然后在2012年里，完善已建立的方法，特别是Cayley图小世界模型和图广义同态的方法，使之能为设计新的并行计算机和网络互连结构和好的并行分布式算法提供理论指导。得到的理论成果已在国际权威杂志（SCI检索）上发表。