摘要：Two pass routing scheme is described for communication in a multiprocessor system
employing a unique-path multistage interconnection network in the presence of faults in
the network. It is capable of tolerating all single faults and many multiple faults in all
except the first and last stages of the network. The routing scheme is useful for
tolerating both permanent as well as intermittent faults in the network. The hardware
over head for implementing the scheme is very small and no time-penalty is paid in the
fault-free case.
While a multiple-path interconnection network is capable of tolerating any single fault,
the knowledge of the fault's location is required before it can adapt itself. An approach
of on line single-fault detection is given. Based on a new fault-model, a system wide
diagnostic procedure is developed to effectively detect and locate a single fault
throughout a fault tolerant network as that proposed in (6). The model is realistic and
has potential usefulness as a tool for modeling faulty states of larger switching elements
(e.g., n x n switching elements, n > 2). Networks under diagnosis behave in a
distributed control manner, i.e., a tag needed for establishing a path is conveyed by the
same resources (switching elements and links) as those for transmitting data. Test
vectors for appropriately setting switching elements when the procedure is conducted
are presented. Faults are classified into two different groups each of which is dealt with
separately to ease our diagnostic procedure.
