Reconfigurable tree architectures for gracefully degradable vlsi systems

Several families of reconfigurable tree-like architectures, suitable for VLSI implementation, are presented. Such architectures are based on interconnection patterns consisting of complete binary trees with spare links added (between a node and its grandfather and/or cousin) according to various criteria. The aim is to dynamically reconfigure them as (nonbinary) trees. The total silicon area required by these architectures is only a constant factor higher than that of a complete binary tree. They can bear multiple faults in processing elements and/or links and still function with an acceptable performance degradation. An analytical method for evaluating the average performance degradation in the presence of faults is presented. Some basic procedure paradigms that can be easily performed on all the proposed architectures are given. Such paradigms can be effectively used in several applications, including linear programming, dictionary machines, and relational database processing. © 1994 Academic Press, Inc.