Fault Diagnosis Of Parallel Computers And Routing And Wavelength Assignment For WDM Networks

High performance parallel computers are one of the main tools of solvinglarge-scale computational problems, which have found widespread applications invarious scientific and engineering areas.The communication between processors in a massively parallel processing systemis the major bottleneck of the overall performance of the system. With the increasingsize of such systems, the requirement for high bandwidth is also increasing. Opticalinterconnection networks posses extremely high bandwidth, extremely low powerconsumption and extremely low time delay, optical networks, and, hence, are regardedas a promising alternative to traditional electrical interconnection networks. Wavelengthdivision multiplexing (WDM) networks consist of an important class of opticalnetworks; its core idea is to divide the bandwidth of a single optical fiber into multiplecommunication channels, thus carrying multiple signals with different wavelengthssimultaneously through the optical fiber. It is well known that the wavelengths availablein a WDM network are invaluable resources. The so-called routing and wavelengthassignment (RWA) problem aims to realize a prescribed communication pattern on aWDM network. This thesis addresses the problem of how to realize some typicalcommunications on some typical WDM networks. The main contributions are presentedbelow.1) The maximum subgraph of a ternary n-cube induced by mvertices isdetermined.2) Based on the above results, the minimum numbers of wavelengths required forrealizing a bidirectional and unidirectional ternaryn-cube communication pattern on alinear array and mesh of the same size are determined, respectively, and thecorresponding wavelength assignment schemes are described. A feasible wavelengthassignment scheme for realizing a bidirectional ternaryn-cube communication patternon a ring of the same size is also suggested.3) In the case that a bidirectional ternaryn-cube communication pattern would runrepeatedly in its dimensional order, the number of wavelengths required for realizingsuch a communication pattern is determined. As a result, the wavelength resourcesconsumed by such a communication pattern are reduced greatly.With the increasing size of parallel processing systems, it becomes unavoidable that there are failures in such systems. As a result, it is critical to locate faulty units insuch systems in an efficient and accurate way. The so-called system-level diagnosis isan effective approach to the identification of faults in paralle computers; its core idea isto conduct mutual tests among processors and, then, to locate faulty processors based onthe test outcomes. The diagnosability is an important notion in system-level diagnosis,which measures the self-diagnosing capability of a parallel system. One important taskin system-level diagnosis is to determine the diagnosabilities of the interconnectionnetworks underlying parallel computers. The g-good-neighbor conditionaldiagnosability is a recently proposed notion, where it is assumed that every node has atleast g good neighbors. Compared to the ordinary diagnosability, the theg-good-neighbor conditional diagnosability can, under proper assumptions, significantlyenhance the self-diagnosing capability of a parallel system.Ternary n-cubes are a class of typical interconnection topologies. The contributionof this thesis is to determine the g-good-neighbor conditional diagnosability of ternaryn-cube.