THE DEADLOCK-FREE BEHAVIORAL ROUTING ALGORITHM ON STAR GRAPH
Shi Feng · Chinese Journal of Computers · 1998
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.