超立方体多处理机系统中基于扩展最优通路矩阵的容错路由  

A Fault-Tolerant Routing Strategy Based on Extended Optimal Path Matrices in Hypercube Multi-Computers

作　　者：田绍槐[1] 

机构地区：[1]湖南税务高等专科学校,长沙410116

出　　处：《计算机学报》2002年第1期87-92,共6页Chinese Journal of Computers

基　　金：湖南省教育厅科技项目基金资助

摘　　要：该文在高峰等文章的基础上 ,提出了针对超立方体结构多处理机系统的扩展最优通路矩阵 (ExtendedOptimal Path Matrices,EOPMs)的概念 ,并给出了一个建立 EOPMs的算法和基于 EOPMs的容错路由算法 ,证明了基于 EOPMs的容错路由算法是基于扩展安全向量 (ESVs) [1 3] 和基于最优通路矩阵 (OPMs) [1 4] 容错路由算法的扩展 .与原文相比 ,该算法的存储开销与 OPMs相同 ,但记录的最优通路的信息 ,包含了原文所记录的最优通路的信息 。Hypercube network is a common multi computers network. With the increasing size of a multi computers network system, fault possibility of computers and their link increases. Thus it becomes more significant to seek for better fault tolerant routing strategy so as to record more optimal path information to realize more effective fault tolerant routing when faults occur in a multi computers system. Many significant researches are done on the fault tolerant routing design of hypercube multi computers systems.Wu J. proposed the Safety Vectors (SVs) concept and an SVs based fault tolerant routing algorithm in 1998; Gao F. et al. modified the definition of SVs, proposed the concept of Extended Safety Vectors (ESVs) and an ESVs based fault tolerant routing algorithm, used matrices to denote link faults precisely, and proposed the Optimal Path Matrices(OPMs) concept and an OPMs based fault\|tolerant routing algorithm in 2000; The algorithms are more powerful in optimal path searching and will record more optimal path information than the SVs algorithm. On the basis of the algorithms, this essay modifies the definition of OPMs, and proposes the concept of Extended Optimal Path Matrices (EOPMs) in hypercube multi computers. It proposes both an algorithm in creating EOPMs and a fault tolerant routing algorithm based on EOPMs. EOPMs can be regarded as an extension of ESVs and OPMs. The optimal path information recorded by ESVs and OPMs algorithms is now included in the optimal path information recorded by EOPMs algorithm. EOPMs algorithm consumes the same amount of system memory resource as the OPMs algorithm. Compared with algorithms based on ESVs and OPMs, this EOPMs based algorithm is an improvement in optimal path searching capacity. When faults exist, this algorithm still ensures that messages between the nodes of sources and destinations can be transmitted along an existent optimal path.

关 键 词：容错路由 扩展最优通路矩阵 多处理机系统 超立方体结构 

分 类 号：TP338[自动化与计算机技术—计算机系统结构]