| High performance computing (HPC) refers primarily to the use of supercomputers to achieve significantly computing productivity. HPC have transformed a number of science and engineering disciplines. The influences of high-performance computers have extended to economy, public safety and national safety. An inevitable trend of HPC is massively parallel processing.Along with continuing increase in number and capability of the processors in massively parallel processors (MPP), there is a high demand for data transmission. Thus, high-speed and high-capacity interconnection network is required. Conventional electrical interconnection technology can not meet this requirement due to its intrinsic constrains, such as limitation on bandwidth, discontinuity of impedance, clock skew, restriction on I/O density, power dissipation and vulnerability to electro-magnetic interference (EMI). Further, this leads to a bottleneck beginning to appear in the MPP. Due to significant advantages over electrics, including inherent parallelism, high spectral and spatial bandwidth, low latency, immunity to EMI, less power consumption, and desirable topological properties, optics has received considerable attention from many researchers and is treated as a potential candidate for interconnection networks of MPP. Motivated by these comments, several issues of optical interconnection network models, including modeling method, system-level diagnosis, and optimal reconfiguration, are discussed in this thesis. The main contributions in this thesis are listed below.1: Usually, a multiprocessor system is modeled as a graph which fails to characterize those emerging optical interconnection networks. In this thesis, hypergraphs are suggested as models of the optical interconnection networks.2: The researches in optical interconnection have concentrated on optic components/ devices and network models. Compared to advancement of optic components/devices, fewer studies have been involved in optical interconnection network models. In particular, to our knowledge, the fault diagnosis of optical interconnection MPP has yet to be investigated. The self-diagnosis problem of optical interconnection MPP is formulated in terms of hypergraph in this thesis. Then, the theory of the graph-based system-level diagnosis could be interpreted to deal with the fault identification in optical interconnection MPP. 3: The system-level diagnosis of Hypermesh optical interconnection MPP is solved. We derive that the one-step diagnosability of kn-Hypermesh is n(k?1). Furthermore, by decomposing HMn,k into a family {HMn,k[Vx] : x∈{k?1,···,0} n?cn} of kn?cn disjoint subhypermeshes that are each isomorphic to HMcn,k , we get a cycle decomposition CD(HC) of HMn,k . Based on the principle of cycle decomposition, a one-step t-fault diagnosis algorithm for kn-Hypermesh also is described. The proposed algorithm is proved to be correct and runs in O(knn(k?1)) time.4: It is knowm that one optimal reconfiguration problem of intelligent optical backplane can be reduced to the optimal linear arrangement (OLA) problem, which is NP-hard. DNA computation is a promising approach to solving computationally intractable problems. Based on a DNA computational model: the Adleman-Lipton-sticker model, this thesis describes a novel algorithm for the OLA problem. For a graph with n vertices and m edges, the proposed algorithm suggests a promising solution to the OLA for it is executed in O(n3log2 n) DNA operations on tube of (nK + n + m + L + 1)-bits DNA strands, where K = ?l og 2n? and L = ?l og 2(n m)? + 1. Therefore, with the progress in molecular biology techniques, this algorithm might be able to efficiently solve medium-sized instances of the optimal reconfiguration of intelligent optical backplane.It is regarded that optical interconnection networks could be implemented and would improve significantly the performance of MPP. The future architecture of parallel computing system will be of the fashion of electrical processing combined with optical interconnection.
|
PDF Full Text Request