Diagnosability And Fault Toleranceof Someoptical Interconnection Networks

With the increasing size of multicomputers, the possibility of the presence of faultyprocessors in such systems is becoming increasingly large, leading to a dramatic drop intheir reliability. For the purpose of ensuring that such a system can work properly, it iscritical to locate its faulty elements in a timely and accurate fashion. Sytem-level faultdiagnosis is recognized as an effective approach to automatically identifying faultyelements in parallel computing systems; its core idea is to perform mutual tests amongprocessors and then to locate faulty processors by analyzing the collection of all testoutcomes.Compared to traditional electrical networks, optical networks have some appealingproperties, ranging from extremely high bandwidth, to extremely low powerconsumption and extremely low latency. As a result, optical networks are widelyregarded as the next-generation mainstream interconnection networks for parallelprocessing. An optical network can be represented by a graph, where each noderepresents the collection of one processor, its local memory and its associated opticalrouter; two nodes are connected by an edge if a direct optical link can be establishedbetween their corresponding optical routers.Fault-tolerant and diagnosing capabilities are important indicators of performanceof interconnection networks. The main objective of this thesis is to examine the faulttolerance and diagnosability of some typical optical networks. The main contributionsare presented as follow.(1) Multi-mesh hypercubes are a class of promising optical interconnectiontopologies, which integrate the positive features of both hypercubes and meshes, andmeanwhile, circumvent the poor scalability of hypercubes and the large diameter ofmeshes. The thesis addresses the diagnosability of multi-mesh hypercube. First, thediagnosability, strong diagnosability and conditional diagnosability for a multi-meshhypercube are determined under the comparison model, respectively. As a result, thecondtional diagnosability is three times as many as the diagnosability or strongdiagnosability. Second, the diagnosability, strong diagnosability and conditionaldiagnosability for a multi-mesh hypercube are determined under the PMC model,respectively. As a consequence, the condtional diagnosability is four times as many asthe diagnosability or strong diagnosability. It can be concluded that, ignoring some small-probability events, the self-diagnosing capability of multi-mesh hypercubes canbe enhanced significantly.(2) Hypermeshes are another class of appealing optical interconnection topologies;it was reported that hypermeshes are especially suited to serving as the underlyingnetwork for on-chip multiprocessor systems. This thesis considers the fault toleranceand diagnosability of the hypermesh optical interconnection networks. First, the faulttorlerance for hypermeshes is studied. Second, the g-good-neighbor conditionaldiagnosability is determined under the PMC model. Compared to the classicaldiagnosability and the conditional diagnosability, this diagnosis measure remarkablyimproves the self-diagnosing capability of hypermeshes.(3) Based on the features of optical communications, the notion of enhancedoptical interconnection is introduced. On this basis, the r-diameter and r-connectivityfor optical networks, which are natural generalizations of the conventional diameter andconnectivity, are defined, respectively. Finally, the r-diameter and r-connectivity ofenhanced hypercubes are determined. It is observed that the proposed enhancedcommunication pattern for optical networks can markedly reduce the maximumcommunication delay and tremendously enhance the fault tolerance.(4) Finally, we give an outlook for further study, as well as a systematic summaryof this work.This work clearly shows that optical networks also enjoy outstanding fault tolerance andself-diagnosing capability as well as technical advantages. Hence, optical networkswould find widespread applications in parallel computing.