FAULT RECONFIGURATION FOR THE NEAR-NEIGHBOR TASK IN A MULTISTAGE-NETWORK MIMD SYSTEM

Dynamic fault reconfiguration in an MIMD environment with a multistage interconnection network is considered. The near neighbor class of pro blems, which involve fundamental parallel processing algorithms such a s partial differential equations and low level image processing algori thms, are chosen as the target application in such an environment. It is shown that dynamic fault reconfiguration can be achieved efficientl y without any additional or modified hardware in case of (permanently) faulty processors. Two types of multistage networks we considered: ge neral multistage networks (such as Benes networks) and the Omega netwo rk. The communication time of the system with faulty processors is min imized by rearranging the order in which the fault-free processors com municate with each other. For any number of faults, a reconfigured sys tem with a general multistage network is shown to require an increase from four to five data transfers for each iteration of the near neighb or problem. For the Omega network, many faults can be handled by six d ata transfers, but in some cases up to 10 data transfers are necessary . In order to minimize the computation time of the system with faults, the data points of faulty Processors are distributed equally and in p arallel among the remaining processors. The technique used for paralle l data distribution is called Uniform Data Distribution. (C) 1994 Acad emic Press, Inc.