A general index mapping technique for array reconfiguration
Fausto Distante, M.G. Sami, Renato Stefanelli · 2003
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.>