Research On Communication Performance Of BC Interconnection Networks

With the development of parallel and distributed system, the number of processors hasincreased rapidly in the past decades. Including so many processors, the performance ofinterconnection networks becomes more and more important in modern parallel computers.Besides, in such a system, the faulty nodes problem must be taken into account and thesystem should continue to work even with several faulty nodes.Hypercube is a kind of popular interconnection networks. It has a superior nature: then-dimensional hypercube Q_n has diameter n, which is logarithm-level with respect to thenode number of Q_n. However, by changing some links, various hypercube variants havebeen proposed. These variants typically have diameter about a half that of Q_n. BijectiveConnection graphs (in brief, BC graphs) are a family of hypercube variants, which containshypercubes and most of the hypercube variants. The BC graphs provide a new method tostudy hypercube and hypercube variants.In this paper, we prove that in an n-dimensional BC graph Xn, the upper bound ofrestricted fault diameter is n +「log(|F_n| + 1)」. Besides, we give an unicast algorithm and abroadcast algorithm for the BC graph with restricted fault nodes set. Under the conditionthat each node has at least one fault-free neighbor, these algorithm guarantee to work ifthe number of faulty node is less than 2n-2. Moreover, we prove that both the length ofthe reliable path obtained by the unicast algorithm and the height of the reliable spanningtrees obtained by the broadcast algorithm will be less than n+「log(|F_n|+1)」+3. Finally, wesimulate these algorithms on some well known or randomly generated BC graphs to estimatethe performance of these algorithms.It was proved that, the upper bound of the diameter of an n-dimensional BC graph isn. And the smallest diameter of all the known BC graphs is「(n+1)/2」. In this paper, we find anew BC graphs called spined cubes and prove that the n-dimensional spined cube has thediameter「n/3」+ 3 for any integer n with n≥14. It is the first time in literature that a BCgraph with such a small diameter is presented.