Reconfiguration and performance of distributed memory parallel systems

Parallel computers are increasingly in demand in many scientific and engineering applications. For a large parallel system, the probability of fault occurrence can be high. Thus, fault-tolerance becomes an important issue in designing such systems. In this thesis, we first consider reconfiguring faulty hypercube and mesh systems so as to utilize as many fault-free nodes as possible after reconfigurations. To achieve this reconfiguration goal, a faulty hypercube is reconfigured into a maximal incomplete subcube, while a faulty mesh is reconfigured into a maximal incomplete submesh, called a convex submesh. To verify the advantages of our proposed reconfiguration schemes, various extensive simulations are carried out. The simulation results show that the subsystems reconfigured using our schemes are often much larger than those reconfigured according to prior schemes.; To study the actual performance levels of the reconfigured incomplete systems, we then conduct various experiments for hypercube systems on the Intel iPSC/860 (a distributed-memory parallel machine with the hypercube topology). To measure the performance of an incomplete hypercube system, we map applications developed on a complete hypercube onto an incomplete system, following the techniques employed by a complete hypercube. Our experimental results show that it is indeed possible to achieve better performance on an incomplete system than on its complete counterpart (with fewer nodes).; Finally, a fully adaptive routing algorithm for wormhole-routed meshes is developed. Routing is an important aspect of a distributed-memory machine because system performance depends critically on the efficiency of message routing. Unlike other fully adaptive routing algorithms, our proposed algorithm achieves full adaptivity without requiring any extra hardware support (i.e., adding virtual channel(s) to each physical channel). Deadlock freedom is guaranteed by disallowing certain packet(s), when necessary, to wait for any outgoing channel(s). Our simulation results show that the proposed scheme outperforms the west-first (a partially adaptive routing algorithm) for various network traffic patterns.