Dissertation > Excellent graduate degree dissertation topics show

Research on Communication Performance of BC Interconnection Networks

Author: ZhouWuJun
Tutor: FanJianXi
School: Suzhou University
Course: Computer Software and Theory
Keywords: Interconnection network diameter fault-tolerance condition connectivity
CLC: TP338.6
Type: Master's thesis
Year: 2011
Downloads: 13
Quote: 0
Read: Download Dissertation

Abstract


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.

Related Dissertations

  1. Technology of Blood Vessel Diameter Measurement Automatic Based on Digital Image Processing,R310
  2. Bored of Pressure Relief Mechanism and a Reasonable Argument,TD324
  3. Optimization Study on Pipeline of Deep-sea Mining System,TD424
  4. Research on the Containment Measure of Set Long-term Segment in a Special Kind of Region,O186.5
  5. The Research and Implementation of Offline Charging Collection Function in IP Multimedia Subsystem,TN915.09
  6. Research and Implementation of the Integrated Test Tool for HSS,TP311.52
  7. The Research on the Diameter of Double Loop Networks,TP393.02
  8. Service Description and Dynamic Substitution Using Formal Method,TP393.09
  9. Online Visual Detect System and Key Technology of Glass Bottles,TP274.4
  10. The Research of Active Anti-vibration System for Measuring Diameter of Steel Tube,TP274
  11. Study on the Structure of Small Diameter Vascular Stent by Using Composited Nanofiber with Recombinant Spider Silk and Polymers,R318.08
  12. Study on the Inner Diameter Measuring System of Stern Tube Front Bearing Pedestal and Steel Casting,U664.21
  13. Ice and the role of non-simultaneous destruction of the structure of the numerical simulation,U657
  14. Numerical Analysis of Kinematic Mediums and Experimental Research of Medium Size in Ball Mill,TD453
  15. Research on Measure Method of the Precision of Large-Diameter Straight Welded Pipe,TG806
  16. Edge Fault Tolerance of Super Edge Connectivity for Several Families of Interconnection Networks,O157.5
  17. The diameter of FIG minimum eigenvalue,O157.5
  18. The Numerical Simulation and Experimental Research of Icing Mechanism of Typical Ice-shaped,V211.74
  19. Study of Laser Diffracton Diameter Gauge Based on FPGA,O436.1
  20. The Relationship between Atherogenic Index of Plasma, Central Aortic Pressure and Nonvalvular Atrial Fibrillation,R541.75

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Electronic digital computer (not a continuous role in computer ) > A variety of electronic digital computer > Parallel computer
© 2012 www.DissertationTopic.Net  Mobile