论文部分内容阅读
著名的OTIS网络(也叫Swapped网络)和最近出现的Biswapped网络均可用来构建大规模并行分布式系统的互连网络。Biswapped网络可以看做是OTIS网络的一种扩张，因而这两种网络呈现出很多类似的拓扑特性，且因Biswapped网络具有更好的对称性，导致其性能更好，其上的算法也更为简单。这两类网络都提供以任意图为因子网络构建更大规模网络的一般方式，所得组合网络能继承因子网络很多优良特性，并且它们的许多算法也往往能从因子网络的相应算法直接导出。一个组合网络的性质和算法具有一定通用性，因此研究OTIS网络和Biswapped网络的拓扑性质和算法具有重要的理论与实际意义。 图的最小支配集问题和最小连通支配集问题存并行分布计算中有着重要的应用价值，这是因为在一个并行分布式系统中，网络的可靠性、路由、容错性、资源分配及利用可以归结为这些控制集问题。由于计算上它们都属于NP难问题，因此常常采用启发式算法来求其次最优解。 OTIS网络和Biswapped网络都是将若干个具有相同结构的模块采用某种特殊的规则互连起来而形成，因而从数学上看它们是具有一定特殊结构的图。这意味着，与一般图相比，OTIS网络和Biswapped网络上的最小支配集问题和最小连通支配集问题应有更有效的算法。遵循研究组合网络的一般思路(即研究如何由因子网络的特性和算法导出组合网络的相应特性和算法)来研究OTIS网络和Biswapped网络的最小支配集和最小连通支配集的有效构造算法。 本论文的主要工作如下： (1)根据因子网络的(连通)支配集，OTIS网络的模块性，以及OTIS网络的各模块间特殊的互连规则，构造OTIS网络的(连通)支配集的有效算法，并对算法的性能进行理论分析和实验验证。 (2)借鉴研究OTIS网络(连通)支配集算法的思路，以及Biswapped网络的模块性和特殊的互连规则，构造Biswapped网络的(连通)支配集的有效算法，并对算法的性能进行理论分析和实验验证。 (3)对本论文设计的构造算法进行分析，得到OTIS网络和Biswapped网络的支配数和连通支配数的上下界，这比将OTIS网络和Biswapped网络作为一般图来看得到的(连通)支配集的界要更紧。