Study On The Shortest Path Algorithm And Parallel Path Algorithm In The Star Graph Interconnection Networks

The appealing good properties such as regularity, symmetry, scalability, short diameter, small storage pace for nodes etc. of the star graph have made this topology a right candidate for multiprocessor system prototype topology, and then the star graph has become the new target for the practice researchers. As the choice of routing path is a direct reflection of the star graph interconne-ction network performance, the study on the routing has been a hot topic, for the above reason, this paper study the routing path in star graph based on exploring the topology characteristics, specifically includes the following two aspects:1. In the star graph interconnection network, to send messages from the source node to destination node, the choice of the path between them will affect the time it takes to send the messages, therefore, in order to improve the transmission efficiency, the path between them should be chosen as short as possible, to find the shortest path algorithm between any two nodes is particularly important, in order to solver this problem, the shortest path algorithm between two arbitrarily nodes is given in this paper, and compared it with existing methods which is already in the references, the results showed that the method presented in this paper more direct and convenient.2. With the increasing size of multi-processor systems, the probability of node and link failures in the system is also increased, and when there are large amounts of data messages which are needed to be transmitted between any two nodes in star network, in order to transmit the messages in a short time, improve the efficiency of transmission, also to guarantee the normal transmission of messages when there appear node failures or link failures in the network, for the problem, a new method was given for finding parallel routings between any two distinct nodes in the star networks from the perspective of group theory, and focus on the relevant properties of cycle permutation. because when finding the routings, the method discuss the problem under different conditions, thus ensuring the upper bound of the set for the length of all parallel routings is the shortest in all conditions, and also ensuring the algorithm is effective and optimal.