Reconfigurable Multipipelines for Vector Supercomputers

Supercomputers typically use pipelines in their processors for achieving high performance. These pipelines consist of several stages and many such identical pipelines are used in vector supercomputers for doing vector operations. This paper addresses the problem of recovering multipipelines in the presence of faulty stages. The stages are assumed to be organized in rows and columns. We alternate the pipeline stages with reconfiguring circuitry which is used for bypassing the faulty stages. The pipelines are configured by programming the switches in a distributed manner using fault information available locally. The reprogrammability of the switches enables us to tolerate dynamic faults. Our configuration algorithm is optimal in the sense that it recovers the maximum number of pipelines under any fault pattern. Probabilistic bounds on the delay (the number of bypassed faulty stages) and yield (the number of nonfaulty pipelines recovered) and derived. We show that the maximum signal delay in any of the pipelines is θ(logm), where m is the initial number of pipelines. Furthermore, a constant fraction of these pipelines can be recovered with our scheme, as opposed to an exponentially decreasing number when no reconfiguration is used. Our reconfiguration scheme can also be used for providing faulttolerant buses on a wafer.