A Simple Scheme for a Fault Tolerant DADO Machine

Binary tree multiprocessors, such as DADO, have many favorable advantages for hardware implementation. For example, binary trees are planar requiring linear area (VLSI implementations require area which is proportional to the number of processing elements) and are not pin-limited (off chip connections remain constant as device dimensions scale down and more processors are implemented on the chip). One often cited problem for binary trees, however, is that trees are not fault tolerant. In this brief note, we detail a simple method which guarantees operation of a binary tree machine after two successive faults, as well as a 50% chance of proper operation after a third successive fault. This scheme requires no extraordinary engineering changes and very simple software to support proper operation of the machine. The binary tree organization is thus maintained