A fault tolerant multiplier which utilizes a plurality of full adder rows has the ability to permanently deselect a row when a fault is detected in its initial testing. An extra row is provided to allow this deselection and transfer gates are provided between each row to shift the sum and carry logic on to the next row at the point of the deselected row and all rows therebeyond.
A parallel multiplier consists of a systolic array of AND gates and full adders organized in stages so that each stage generates a partial product, adds it to the preceding partial products, and furnishes the sum to the next stage. A control circuit is provided that disables the outputs of each stage of the array until the operation in the particular stage is completed. The disabling of outputs reduces power consumption.
A processing element may be used either separately or in an array of similar processing elements for performing concurrent data processing calculations. The processing element includes a multiported memory unit for storing data to be processed by any of a plurality of function units which are connected to the multiported memory unit. The multiported memory unit includes a number of data storage slots for storing data words to be processed and the results of said processing. Each function unit performs a calculation having as its inputs one or or more data words from the multiported memory unit. The result of this calculation is stored back in the multiported memory unit. The transfer of data to and from the function units is accomplished by use of the ports on said multiported memory unit. The data manipulated by the processing element is controlled by specifying a correspondence between data storage slots, memory input ports and memory output ports.
A method and apparatus are presented for tolerating up to k faults in a d-dimensional mesh architecture based on the approach of adding spare components (nodes) and extra links (edges) to a given target mesh where m spare nodes (m.gtoreq.k) are added and the maximum number of links per node (degree of the mesh) is kept small. The resulting architecture can be reconfigured, without the use of switches, as an operable target mesh in the presence of up to k faults, regardless of their distribution. According to one aspect of the invention, given a d-dimensional mesh architecture having N=n.sub.1 .times.n.sub.2 .times.. . . .times.n.sub.d nodes, the fault-tolerant mesh can be represented by a diagonal or circulant graph having N+m-k nodes, where m.gtoreq.k. This graph has the property that given any set of k or fewer faulty nodes, the remaining graph, after the performance of a pre-determined node renaming process, is guaranteed to contain as a subgraph the graph corresponding to the target mesh M so long as d.gtoreq.2 and n.sub.d .gtoreq.3. The invention also relates to a method and apparatus for efficiently locating a healthy target mesh in the presence of up to k faulty network components, given a fault-tolerant mesh constructed in accordance with the teaching set forth herein.
A method is disclosed, for use with a multiprocessing hardware mesh architecture including nodes and a network of interconnections between the nodes, for defining and implementing a target logical mesh architecture utilizing a given subset of the nodes and the interconnections of the hardware architecture. Typically, the hardware mesh architecture includes redundant nodes and interconnections, sot hat the target logical mesh architecture may be defined from the hardware architecture several different ways. As a consequence, the target logical mesh architecture may be defined even in the presence of faulty nodes or interconnections in the hardware architecture. Frequently, the logical mesh is defined in terms of some regular pattern of interconnections. The method of the invention facilitates the definition of the desired logical mesh architecture from the hardware architecture, given the possibility that one or more faults are present, by initially defining logical blocks of nodes from among the functional nodes of the hardware architecture. Then, functional edges between the nodes defined within the logical blocks are defined as logical interconnections between the nodes of the logical blocks, such that the logical blocks, with the interconnections, are structurally consistent with portions of the logical mesh. Finally, additional edges are defined as logical interconnections between nodes in different logical blocks, these additional edges also being consistent with the structure of the logical mesh. The result is that the logical mesh has been fully defined from functional nodes and interconnections in the hardware architecture.
A method and apparatus are presented for tolerating up to k faults in d-dimensional mesh architectures based on the approach of adding spare components (nodes) and extra links (edges) to a given target mesh where exactly k spare nodes are added and the number of links per node (degree of the mesh) is kept to a minimum. The resulting architecture can be reconfigured, without the use of switches, as an operable target mesh in the presence of up to k faults. According to one aspect of the invention, given a d-dimensional mesh architecture M having N=n.sub.1 .times.n.sub.2 x . . . x n.sub.d nodes, the fault tolerant mesh can be represented by a circulant graph having exactly N+k nodes. This graph has the property that given any set of k or fewer faulty nodes, the remaining graph, after the performance of a predetermined node renaming process, is guaranteed to contain as a subgraph the graph corresponding to target mesh M so long as d.gtoreq.2 and n.sub.d .gtoreq.3. The invention also relates to a method and apparatus for efficiently locating a healthy "target mesh" in the presence of up to k faulty network components, given a fault tolerant mesh constructed in accordance with the teachings set forth herein.
