Research On Bufferless Optical Interconnection Networks For High Performance Computer

As an important method for solving large-scale computational problems, more and more high performance computers (HPCs) have been adopted by nearly every fileds of scientific and engineering projects. The scale of parallel HPCs keeps expanding increasingly, and the urgent demand for even much higher performance has never slowed down in accordance with the development of HPC technologies. At present, improvements of the computing nodes as well as the optimization of interconnect networks are two main approaches to boost HPC's performance. Computing nodes need more efficient communication when a HPC scales larger, which requires even more support of the interonnect networks. How to design a high-bandwidth, low-latency and high-throughput interconnect network and how to improve its efficiency have become the key problems of HPC researchers.The electrical interconnection networks based on copper wires exhibit some disadvantages such as low bandwidth, high power dissipation, poor immunity against EMI and low-density as data transfer rate becomes higher, which are the key bottlenecks to improve its performance. Optical interconnection network is a new method for connecting thousands of computing nodes together within a HPC. It has many advantages such as higher bandwidth, lower power dissipation, higher immunity against EMI and lower packet delay, which are incomparable with its electrical competitor. Therefore optical interconnection network has become a hotspot in the study of high speed interconnection networks for HPCs. However, current technology lacks the ability of buffering and processing optical signals. In traditional practice, O/E and E/O conversions are used for buffering signals and performing routing procedures, which introduce a large amount of overheads. Aiming at lowering the overheads of optical interconnection networks and improving its efficiency, this dissertation focuses on the study of high speed bufferless optical interconnect networks for HPC, and put forward a new optical interconnection network model named Bufferless Optical Interconnection Network (BOIN). A BOIN network needs neither O/E and E/O conversion nor optical buffering on intermediate nodes, which can overcome the efficiency problems in current optical interconnection networks. Besides studying its routing algorithms and fault-tolerance capacities, this dissertation also gives out a performance model to evaluate the performance of BOIN network. The main contributions of this dissertation are listed below.1. To overcome the traditional deficiency of optical signals buffering and direct logic processing, a new optical interconnection network architecture ? BOIN ? was put forward, within which O/E and E/O conversion and optical buffers on intermediate nodes are avoided. In a BOIN network, O/E and E/O conversion are unnecessary, because optical data packets travel along optical links all the time while routing decisions on intermediate nodes are made according to the synchronized electrical control packets. This dissertation studied on the optical link protocols and methods for port collision avoidance, put forward a livelock-free and deadlock-free routing algorithm, and proved its correctness. Each packet in BOIN will arrive at the destination node within a limited period according to this routing algorithm. The upperbound of delay time is determined by the network size.2. To evaluate the performance of a BOIN network, this dissertation analysized the flow characteristics of each optical link in therory and established a mathematical performance model. Performance metrics such as the average transmission delay, throughput and so on, are derived by solving the model. We also studied the conditions BOIN should meet under which the BOIN network can achieve the optimal performance in a certain network size. The simulation results show that the performance model can describe the characteristics of BOIN, which provides a foundation for network optimization.3. The BOIN network is a new kind of high speed opto-electric interconnection network for high performance computers. How to boost its efficiency is a key aspect of this dissertation. Several optimization techniques were put forward in this dissertation such as starvation avoiding routing algorithm and BOIN2 network structure which can improve the throughput and link utilization of the network. BOIN2 network can perform much better while a little more hardware resources are added. We studied the routing algorithms of BOIN2 network and proved that similar to the BOIN network, the BOIN2 network also has the characteristics such as livelock-free, deadlock-free and transmission delay upperbounds. Simulation results proved the effectiveness of such optimization techniques. They lay a good fundation for large-scale parallel computer design.4. In large-scale parallel interconnect networks, the capability of fault tolerance is very critical for the networks performance. This dissertation also established a fault-tolerant BOIN (FT-BOIN) network to overcome the node failure problems in the BOIN network. The reachability and the properties of the FT-BOIN network are studied, and the sufficient and necessary condition of two nodes can reach each other is put forward. Basing on the analysis, we give out several routing algorithms with different fault-tolerance capability and complexity. It shows that the FT-BOIN network has a quite good fault tolerance, and can perform nonblocking routing between a pair of reachable nodes even if many intermediate nodes fail.In conclusion, this dissertation focused on the design of high speed interconnect networks within the high performance computers. It performed thorough study on the bufferless optical interconnect network ? BOIN, explored its topology, link protocols, routing algorithms and performance model. Effective performance optimization techniques based on the model and fault tolerant routing methods were also put forward. These study results not only provide an effective solution for overcoming problems of practical high speed interconnect networks, but also contribute a great deal to parallel computer system architecture and interconnect network design.