RECONFIGURABLE TREE ARCHITECTURES FOR GRACEFULLY DEGRADABLE VLSI SYSTEMS

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