Embedability And Fault Diagnosis Of Novel Regular Interconnection Network

Large scale multiprocessor systems need to make more improvement on processing speed,reliability and fault tolerance as big data processing and analysis of the dramatic increasing in demand of the entire world.The performance improvement of large scale multiprocessor system can be studied theoretically from the respectively topological structure of the regular interconnection network model.However,some traditional regular interconnection network models such as hypercube networks have caused the rapid increase of the hardware cost with the enlargement of the system size.So the experts and scholars have proposed some new regular network with superior performance.The Exchanged hypercube network is obtained by deleting part of edges in the network on the basis of hypercube network.Thus the exchanged hypercube has many advantages compare with hypercube networks in many performances.The core content of the research on fault tolerance and reliability of regular interconnection network is the exploration of network embedding ability and diagnosis.Fault-tolerance and diagnosis ability are also important indicators to measure the performance of rule-based interconnection network.Although the exchange hypercube network has received much attention since it has been proposed,there are still many problems worth exploring in the network embedding ability and diagnosis.The main purpose of this paper is to analyze and research the embedding ability and diagnostic ability of the new regular network,and to provide the theoretical support for the effective implementation and popularization of the new regular network.It will be helpful for the future development of the supercomputer system.In this paper,a new regular interconnection network—the exchanged hypercube network is used as the main research object.Based on the previous research results,the embedding performance of star network to exchanged hypercube network is considered.The second part is the design of the new regular interconnection network—extended exchanged hypercube network based on the exchange hypercube network.The third part is about the fault diagnosis algorithm on exchanged hypercube network or other models.The main work and innovation of this paper are as follows:1.According to the properties of exchanged hypercube network,the embedding problem of star network to exchanged hypercube network is investigated.Several embedding strategies and embedding performance of star network Sn into exchanged hypercube EH?s,t?network are given,and the following conclusions are obtained:?1?if<?,?>is a embedding mapping of the star networks Sn into exchanged hypercube networks EH?s,t?,then dilation ?N+1,wheres+t=[log₂n!]=N;?2?the star networks Sn can not be embedded into exchanged hypercube networks EH?s,t?with dilation = 1,expansion=1 where s+f+l=[flog₂!],max?s,f?<-2;?3?the star network Sn can be embedded into the exchanged hypercube network EH?s,t?with dilation<l1+l2+2,where 1<r<n,l1=[log₂r!],l2=[log₂r!]and s+t=[log₂n!]=N;?4?ifn=n1+n2+n3+n4,1?ni<n?i=l,2,3,4?,li=[log₂?ni?!],s+t=4?i=1+4n-3,then the starnetwork Sn can be embedded into the exchanged hypercube network EH?s,t?with dilation?max?li+lj+4?.The research results show that the exchanged hypercube network has good universality and fault-tolerant ability,moreover it has broad application foreground.2.In order to further improve the communication efficiency and expect good scalability of exchanged hypercube networks,a new type of regular interconnection network,named Extended Exchanged Hypercube?EEH?,is proposed in this paper.By analyzing the topological properties of EEH,it is found that it not only retains the original good characteristics of the exchanged hypercube network,but also combines the topological characteristics of other excellent networks to obtain the hierarchical,high scalability and the recursive nature owed to the predefined modules.In other words,when the number of nodes in the interconnection network is increasing,the network expansion can be done without changing the hardware configuration of the original node.3.The conditional diagnosis algorithm of the exchanged hypercube network in the PMC model is proposed by introducing the idea of group and breadth-first search.The time complexity of the algorithm is O?N2?· In addition,the strong diagnosis of the exchanged hypercube network in the MM*model is analyzed and proved,thus it is determined that the exchanged hypercube EH?s,p??2?s:? p?is strongly?s + 1?-diagnosable.This part of the research provides important reference value for the follow-up exchanged of hypercube network in other test models of diagnostic strategies and diagnostic capabilities.4.The improved genetic algorithm is applied to the classic Malek comparison model for the first time.The correctness of the algorithm is proved and the result of the experiment proves that the algorithm is effective and reliable.The implementation of this method has important theoretical and practical significance to improve the speed of fault diagnosis and diagnosis ability.The above research not only enriches the related theoretical contents of exchanged hypercube networks as one of the important new regular interconnection networks,but also provides scientific basis and new ideas for the practical system fault diagnosis methods.