由于具有正则性、对称性、可嵌入性、并行性和可扩展性等优良特性,星形图(Star Graph)和超立方体(Hypercube)互联网络受到了研究者们的广泛关注,成为并行计算机互联网络中的重要拓扑结构。随着现在的并行计算机互联网络规模越来越大,网络中出现处理机故障或处理机间的链路故障的可能性也越来越大;这就使得并行计算机互联网络的容错性及其研究也变得越来越重要,因此,设计具有较好容错性的路由算法对并行计算机互联网络有着重要意义。 到目前为止,人们已经对星形图和超立方体互联网络的拓扑特性及其容错模型与容错路由算法方面分别进行了深入的研究,并基于星形图和超立方体互联网络的拓扑特性分别建立了一些容错模型及其容错路由算法,但是仍有许多问题有待研究。本文研究星形图互联网络的受限条件的无死锁路径算法和超立方体互联网络的安全通路容错算法。 在对星形图互联网络的拓扑特性及其容错模型与容错路由算法方面,针对星形图中可能产生死锁的问题,本文对星形图上无死锁的路径算法进行了研究,得到了星形图上的二类最小无死锁受限条件,并给出了一个满足该二类最小无死锁受限条件的无死锁路径算法。此外,本文还提出了星形图上两类基于单缓冲和双缓冲技术的无死锁受限条件,并给出了相应的无死锁路径算法。 在对超立方体互联网络的拓扑特性及其容错模型与容错路由算法方面,本文首先综述了目前国内、国际上在超立方体互联网络研究方面所做的主要研究工作,并基于已有的一些研究成果,提出了一种新的超立方体互联网络的容错模型及其容错路由算法:即基于安全通路向量的容错模型SPV(Safety Path Vectors)及其容错路由算法。与基于最优通路矩阵的容错模型OPM(Optimal Path Matrix)以及基于扩展最优通路矩阵的容错模型EOPM(Extended Optimal Path Matrix)及其容错路由算法相比较,SPV的存储开销指数级低于OPM和EOPM的存储开销,而且SPV能记录到OPM和EOPM无法记录到的最优通路信息。