Systolic Array Interconnection Method
Original Publication Date: 1985-Mar-01
Included in the Prior Art Database: 2005-Feb-18
Given a grid of interchangeable nodes, some of which are known to be defective, this is a heuristic method for interconnecting a subset of the remaining (good) nodes to form a topologically square (or other regular) lattice, with interconnection lengths nowhere exceeding by more than one grid unit the link lengths for a lattice with no defective nodes. Consider a square lattice (for example) of interchangeable nodes. Some of the nodes are identified as defective. We wish to construct a systolic array in which nodes are interconnected to form a topologically square lattice of given dimensions and such that the largest (Manhattan) distance between two directly interconnected nodes is two grid units. A 'spare' node is defined as one that would not have been used for interconnection if no nodes had been defective.