A New Parallel Computer Network

Interconnection networks are fundamental parts of parallel processing systems. However,it is very difficult to find some kinds of interconnecting networks to suit with every parallelprocessing system, because it is a multi-target optimization problem for designinginterconnection network systems. There are many kinds of interconnection networks have beenposed and designed.Petersen graph, 3-regular and 2-diameter, is suitable to the interconnecting networks'structure, so it is widely applied and modeled in designing interconnection networks. ButPetersen graph can not be applied to design interconnection networks directly, because of thelimited size of nodes, 10.Based on Petersen graph, a new interconnection networks, GP(n,k) for n≥3 and1 ≤ k ≤[(n-1)/2 is present, and the properties of GP(n,k) are discussed. Compared with theother interconnection networks which are based on Petersen graph, GPN is simple in topology.The scale of GP(n,k) is decided by the parameter n , and the connection style is decided byparameter k.In this paper, all the works are following:(1) Based on the Petersen graph, a new interconnection networks, GP(n,k), is proposed.The node dgree in GP(n,k) is 3 ,and the diameter is not greater than [n/2k] + [k/2] +3 forn≥6. In addition, Some conclusions about diameter of several kinds of GP(n,k) are obtained.① The diameter of GP (i² ,i) is i +1 for all i≥3. If each kind of network has same numberof nodes, GP (i² ,i)'s diameter is 1/3 of 2—D Mesh's and 2/3 of 2—D Torus's when the numberof nodes is large enough. ② The diameter of GP ( 2^{2 m},2^m) is 2 m +1 for all m≥2. ③ Thediameter of GP ( 2^{2 m+1} ,2^m)is (3/2)2^m +1. If each kind of networks has same number of nodes,GP ( 2^{2 m+1} ,2^m)'s diameter is 3/8 of 2—D Mesh's and 3/4 of 2—D Torus's if the number ofnodes is large enough. By analyzing GP(n,k)' s topology and compared with the diameters of2-D Mesh and 2-D Torus, it is known that GP(n,k) has simple topology and small diameters.(2) As a basic operation of interconnection networks, the routing algorithm is also animportant aspect on affecting the efficiency of parallel processing communication. In this paper,some kinds of routing algorithms on GP (i 2 ,i) are designed, which include point-to-pointrouting, one-to-all routing and all-to-all routing. These algorithms are efficiency: ① In thepoint-to-point routing algorithm: it is need i+1 steps, even in the worst situations.② In theone-to-all routing algorithm: it is need 2 ?i 2?+3 steps when source point on Cn. Otherwise, it isneed 2 ?i 2?+2 steps. ③all-to-all routing algorithm: it is need 4i -2 steps.(3) The all optical ring networks is one of the most important optical networks. Manypopular interconnection networks can be embedded in all optical ring networks. Thewavelength assignment algorithms are proposed when GP(n,k) are embedded in the all opticalring networks. At last, the wavelength assignment numbers is k+2+(n mod k) for each GP(n,k) when it is embedded in all optical ring.