Reconfiguration techniques in the presence of faulty interconnections

A general fault model in which interconnection links as well as processing elements may be faulty is discussed. The general architecture is a rectangular array with a switched-bus interconnection network in which bus segments are the elementary interconnection units. An algorithm that permits the creation of interconnection paths as a catenation of fault-free links is presented. The algorithm is optimum, i.e. given a fault distribution it finds a solution whenever the interconnection structure can support it under given initial constraints. The complexity of the algorithm is evaluated; some criteria for its simplification are discussed