An information dispersal approach to issues in parallel processing
Michael O. Rabin, Yuh‐Dauh Lyuu · 1990
Efficient schemes for the following issues in parallel processing are presented: fast communication, low congestion, fault tolerance, simulation of ideal parallel computation models, synchronization in asynchronous networks, low sensitivity to variations in component speed, and on-line maintenance. All our schemes employ Rabin's information dispersal idea. We also develop an efficient information dispersal algorithm (IDA) based on the Fast Fourier Transform and an IDA-based voting scheme to enforce fault tolerance. Let N denote the size of the network. We present a randomized communication scheme, FSRA (for Fault-tolerant Subcube Routing Algorithm), that routes in 2$\cdot$log N + 1 time using only constant size buffers and with probability of success 1 - $N\sp{\Theta({\rm log}N)}$. (All log's are to the base 2.) FSRA also tolerates O(N) random link failures with high probability. Similar results are also obtained for the de Bruijn and the butterfly networks (without fault tolerance in the latter case). FSRA is employed to simulate, without using hashing, a class of CRCW PRAM (Concurrent-Read Concurrent-Write Parallel Random Access Machine) programs with a slowdown of O(logN) with almost certainty if combining is used. A fault-tolerant simulation scheme for general CRCW PRAM programs is also presented. A simple acknowledgement synchronizer can make all our routing schemes in this dissertation run on asynchronous networks without loss of efficiency. We further show that speed of any component--be it a processor or a link--has only linear impact on the run-time of FSRA; that is, the extra delay in run-time is only proportional to the drift in the component's delay and is independent of the size of the network. On-line maintainability makes the machine more available to the user. We show that, under FSRA, a constant fraction of the links can be disabled with essentially no impact on the routing performance. This result immediately suggests several efficient maintenance procedures. Based on the above results, a fault-tolerant parallel computing system, called HPC (for hypercube parallel computer), is sketched at the end of this dissertation.