Research On The Properties Of The Exchanged Crossed Cube

A high performance computer is a computer system,which can process massive data and large-scale application.It is becoming more and more important in the areas of ed-ucation,scientific research,oil exploration,weather forecast and so on.In recent years,with the development of high performance computer technology,the number of processors in the system increases,and the size of the interconnection network which is used for the processors connection also expanded accordingly.The performance of parallel computers,largely relies on the properties of the interconnection network.That is why the study of the interconnection networks and their properties is a key subject of parallel computing.One of the most influent indicator of an interconnection network is the graph embed-ding ability.As a typical network topology,paths and cycles have the advantages of simple structure,small communication cost,small degree and so on.They have been widely used in parallel computing.Therefore,it is an important subject to study the paths and cycles embedding in interconnection networks.However,it is an NP hard problem to embed paths and cycles of any possible lengths into an interconnection network.From the perspective of embedding,the Hamiltonian property of the interconnection network can be viewed as a special case of the paths and cycles embedding.It has important applications in data com-munication.If multi-cast routing algorithm in an interconnection network uses Hamiltonian path or Hamiltonian cycle,it can effectively reduce or avoid congestion and deadlock.In addition,the Hamiltonian properties are also significant in fault diagnosis of interconnection networks,so it is important to study the Hamiltonian properties of interconnection networks.With the size of multiprocessor systems become larger and larger,it is unavoidable that the processors or communication links in such a system become faulty.This brings about the system's reliability and usability issues.The solution to this problem is fault-tolerant technology,and fault diagnosis is a key step in fault-tolerant processing.The diagnosis is the process of identifying the faulty vertex or communication link in a system.And it can improve the reliability and availability of the system without increasing additional system hardware costs and maintenance costs.Therefore,it is an significant subject to study the fault diagnosis of interconnection networks.The(s + t + 1)-dimensional exchanged crossed cube,denoted as ECQ(s,t),combines the strong points of the exchanged hypercube and the crossed cube.It has been proven that ECQ(s,t)has more attractive properties than other variations of the fundamental hypercube in terms of smaller diameter,the fewer edges,and expandability,etc.And it can support large scale interconnection network.Embeddability,diagnosability,and faulty tolerance of the ECQ network can be used in high performance computing and other fields to provide a theoretical basis.Therefore,it has important theoretical and application value.The major contributions in this thesis are listed as follows.1.The ECQ network is proved to have good Hamiltonian property:(1)We prove that there exists not only a Hamiltonian path but also a path of less than 1 than Hamiltonian path between any two distinct vertices in ECQ(s,t),where s ? 2 and t ?3,and s ? t.(2)We design an algorithm to construct a Hamiltonian path in ECQ(s,t)with the time complexity O(N log N),where N is the number of vertices in ECQ(s,t).(3)Based on(2),we design an algorithm to construct a Hamiltonian cycle in ECQ(s,t)with the time complexity O(N log N),where N is the number of vertices in ECQ(s,t).(4)We prove that ECQ(s,t)is(s-2)-faulty Hamiltonian-connected and(s-1)-faulty Hamiltonian?2.We prove that the ECQ network has good embeddability:(1)ECQ(s,t)contains an l-cycle of every length l from 4 to 2s+t+1 except that ECQ(2,3)and ECQ(3,3)do not contain a cycle of length 9 where s ?2 and t ?3.(2)If s ? 3 and t ? 3,for any two distinct vertices x and y,and any integer l with[s+1/2]+[t+1/2]+ 5?l?2s+t-1,a path of length l can be embedded between x and y with dilation 1 in ECQ(s,t).Note that the diameter of ECQ(s,t)is[s+1/2]+[t+1/2]+2.(3)If s?3 and t>4,for any two distinct vertices x,y ? V(ECQ(s,t),and any integer l with[s+1/2]+[t+1/2]+4?l?2s+t+1-1,there exists an<x,y>-path of length l between x and y in ECQ(s,t).3.We prove that the ECQ network has good fault tolerability:If 1 ? s? t,the diagnosabilities of the ECQ(s,t)are both 2s under the PMC model and the MM*model by using the pessimistic diagnosis strategy.To sum up,in the same dimension,although the ECQ network only has about one half edges of the crossed cube network,it still maintains the the Hamiltonian property,pancyclic-ity and panconnectivity to a large extent.In addition to the fact that the ECQ network has a smaller communication delay than the exchanged hypercube network,its diagnosis-ability is still the same as that of the exchanged hypercube network under the same conditions.