Diagnosability Of Expanded K-ary N-cubes With Missing Edges Under The PMC Model And The MM~* Model

The technological competition between the great powers is intensifying,and the development of supercomputers is particularly important.Supercomputers are mainly constructed through multiprocessor systems.There are tens of thousands of processor nodes in supercomputing systems.They are interconnected to form interconnections.The topology of the network.However,as the number of processor nodes increases,the unreliable probability in the system will increase exponentially and even geometrically as compared to a uni-processor system.The unreliable probability will directly affect the credibility of the entire system.Therefore,in order to promote and apply multi-processor computer systems,its reliability must be solved,especially in terms of diagnosability.The faulty processor in the system is identified and replaced by a non-faulty processor to ensure the reliability of the computer system.This process is called fault diagnosable.The maximum number of faulty processors that can be diagnosised by the system is defined as the diagnostic degree,which plays an important role in measuring the reliability and fault tolerance of the interconnected network.In traditional system-level fault diagnosis research,it is generally assumed that the neighboring vertices set of any processor in a computer system may fail at the same time.In fact,the probability of such a fault situation in a large multiprocessor system is very small.And the quality of the diagnostic capability directly determines the performance of the interconnection network.In order to more accurately analyze the diagnostic nature of the multiprocessor system,we need to At the node level and not just at the entire system level.The PMC model is to complete the system diagnosis by allowing two adjacent processors to test each other.This is the earliest system-level fault diagnosis model.The MM model sends the same task to its two adjacent vertices through a vertice,and then compares the results of their reply to complete the system diagnosis.The MM*model adds stricter conditions on this basis,which is,each vertice must test any pair of adjacent vertices comparison reply results to achieve system diagnosis.In this paper,the PMC model and the MM*model are used to analyze the local diagnosability properties and the strong local diagnosability properties of the expanded k ary n cubes XQnk,thus improving research on the diagnosability capabilities of expanded k ary n cubes XQnk.The following is the main content of this paper:In the first chapter,we briefly introduce research background and research status,some concepts of graph theory,the definitions of expanded k-ary n-cubes XQnk,and also two famous fault diagnosis models,i.e.,PMC model and MM*model.In the second chapter,we prove that the diagnosability of expanded k-ary n-cubes with missing edges under the PMC model is 4n-4.(n?2,even k?6).In the third chapter,we prove that the diagnosability of expanded k-ary n-cubes with missing edges under the MM*model is 4n-5(k=6),4n-4(k?8).Finally,we conclude the thesis with summary and propose some considerable problems.