A general index mapping technique for array reconfiguration

Author

Distante, F. ; Sami, M.G. ; Stefanelli, R.

Author_Institution

Dept. of Electron., Politecnico di Milano, Italy

fYear

1988

fDate

7-9 June 1988

Firstpage

559

Abstract

The reconfiguration of rectangular arrays is considered from a novel, totally general point of view (that can be immediately extended to an array connectivity besides the rectangular one). The only constraint specifically taken into account is that of interconnection locality, represented through the adjacency domain of any given cell in the array; reconfiguration is described as index-mapping. A coverage table is used to represent such index mapping: it is seen that its solution coincides with that of a complete matching problem, and existing algorithms to this purpose are analyzed to identify the best-suited ones. Complexity bounds for the interconnection networks supporting reconfiguration are then determined, and they are seen to be dependent only on the adjacency domain chosen, not on the dimensions of the array. The results are pertinent to the problem of the fault tolerance of VLSI and WSI arrays.<>

Keywords

VLSI; cellular arrays; logic design; VLSI arrays; WSI arrays; adjacency domain; array connectivity; coverage table; fault tolerance; index mapping technique; interconnection locality; interconnection network complexity bounds; rectangular array reconfiguration; Algorithm design and analysis; Capacity planning; Fault diagnosis; Fault tolerance; Logic arrays; Multiprocessor interconnection networks; Performance evaluation; Silicon; Upper bound; Very large scale integration;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1988., IEEE International Symposium on

Conference_Location

Espoo, Finland

Type

conf

DOI

10.1109/ISCAS.1988.14988

Filename

14988