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

THE DEADLOCK-FREE BEHAVIORAL ROUTING ALGORITHM ON STAR GRAPH

星形图具有许多良好的拓扑性质，是一种有可能替代传统的超立方体的并行计算互联网络的模型．在本文中，作者针对在星形图这样一种高度规则的网络中，可能产生死锁的问题，对星形图上无死锁的路径算法进行了研究．首先利用星形图中匹配基的性质，给出了从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.