星形图上无死锁的路径算法  

THE DEADLOCK-FREE BEHAVIORAL ROUTING ALGORITHM ON STAR GRAPH

作　　者：石凤仙[1] 熊鹏荣 周玉林 朱洪[3] 

机构地区：[1]上海电力学院基础部,上海200090 [2]上饶师范专科学校数学系,上饶334001 [3]复旦大学计算机系,上海200433

出　　处：《计算机学报》1998年第10期946-951,共6页Chinese Journal of Computers

基　　金：国家自然科学基金

摘　　要：星形图具有许多良好的拓扑性质，是一种有可能替代传统的超立方体的并行计算互联网络的模型．在本文中，作者针对在星形图这样一种高度规则的网络中，可能产生死锁的问题，对星形图上无死锁的路径算法进行了研究．首先利用星形图中匹配基的性质，给出了从Sn（B）到Sk的正规映射的定义，然后提出了星形图上的两个无死锁受限条件，最后证明了一个满足无死锁受限条件的路径算法．作者还提出了星形图上路径算法的最小无死锁受限条件等，有待于进一步研究．In this paper, star graph is introduced. Star graph has many superiortopological properties, such as vertex symmetry and edge symmetry, short diame-ter,regular and reliable and so on. The n-Star graph, denoted by Sm, is one of thegraph networks that have been recently proposed as attractive alternatives to thetraditional hypercube topology for interconnecting processors in parallel computers.lt is known that deadlock can be prevented by routing restriction in some highlyregular networks. This paper studies deadlock-free behavioral routing algorithm onstar graph. First, this paper defines k-dimensional matched bases in star graph,and defines a regular projection from S.(B) to Sk on the basis of the properties ofthe matched bases. Then two of the deadlock-free routing restrictions on star graphare presented. Finally, a algorithm of the deadlock-free routing restrictions isproved- This paper also indicated that the minimum deadlock-free routing restric-tions on star graph is an open problem.

关 键 词：星形图 死锁 置换圈 匹配基 算法 

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