Implementation of a gracefully degradable binary tree in programmable multi-chip modules

A Multi-Chip Module is proposed as a packaging scheme for a binary tree processing array in order to contain the whole system in a single package. Fault tolerance is provided to the array by a pass transistor switching network in the MCM silicon substrate. The benefits of an active substrate base can offset the expense and complexity of an MCM design when it has application to many circuits. The standard interconnect pattern of binary trees would allow many binary tree applications to share such a pre-fabricated substrate. The switching network provides reconfiguration of the original tree to a gracefully degraded binary tree. The largest functioning binary tree which can be extracted from the original tree will be connected to the existing I/O pads. The algorithm used to obtain this subtree is complete and also contains a heuristic approach in its search. A simple procedure is provided to control the reconfiguration switches. The benefits of this technique over previous reconfiguration schemes involving spare processing elements is that the scheme involves a minimum of hardware and signal delay.