Self Repair Large Scale Integrated Circuit

The sonar signal processing task is characterised by high input/output data rates together with desired computational loads which exceed the capacity of currently available main-frame computers. Adaptive algorithms for various tasks such as beam-forming, filtering, display enhancement, etc. are widely discussed in the journal literature such as the journal of the Acoustical Society of America. These are needed in a real-world environment as they have the potential to significantly enhance the performance of sonar systems in terms of target detection and tracking. However, they increase the computing load by orders of magnitude. Hard wired implementations of some processors with abilities to go some way towards meeting the desired computing load, are constrained in size by a lack of space on the mobile platforms on which they are installed.

The necessary consequence of these conflicting requirements is the matching of software algorithms to efficient hardware realisations. In the past this has implied dedicated hardware as mentioned above. Such hardware is not easily reconfigurable in the event of a fault. Failure in part of the system implies the manual replacement of that part. The necessary operator intervention both for fault diagnosis and part replacement is unacceptable in todays environment.

Current work in the area of high performance, special-purpose computer systems indicates that future sonar processors will have systolic architectures. Software will be implemented on multidimensional VLSI arrays of systolic processing elements (SPE's) where each element is connected to its nearest neighbours only. Descriptions of such architectures, together with applications and performance, have been given by a numer of authors including

(1) Kung H. T., "Why systolic architectures?", COMPUTER, 15, 1, January, 1982,

(2) Whitehouse H. J. and Speiser J. M., "Sonar applications of systolic array technology", IEEE EASCON, Washington, D.C., November, 1981,

(3) Mead C. A. and Conway L. A., "Introduction to VLSI systems", Addison-Wesley, Reading, Mass., 1980,

(4) Snyder L., "Introduction to the configurable, highly parallel computer", COMPUTER, 15, 1, January, 1982, and

(5) Bertram J. F., Ramseyer R. R. and Heins J. M., "Fifth generation digital sonar signal processing", IEEE Journal of Oceanic Engineering, October, 1977.

Consideration of the advantages of this approach to the sonar signal processing problem leads to a necessary consideration of the implications for system reliability. As noted by Snyder L., "Introduction to the configurable, highly parallel computer", COMPUTER, 15, 1, January, 1982, the implementation of a configurable systolic array processor (SAP) leads to a fault tolerant architecture.

In this specification consideration is given to a particular systolic configurable array processor (SCAP) which in the application environment allows the processor to possess a limited self-repair characteristic which does not require operator intervention or down-time in the event of a failure in one or more of its elements. A tentative analysis of the system fault tolerance is provided. For less critical applications it is noted that such an architecture can effectively increase the yield percentage in the production of VLSI dice.

The system of this invention generally comprises a module having a series of elements arranged in rows normal to each other with the sequential paths between elements biased in such a way that normally the data being processed follows the vertical and horizontal rows but should one of the elements be unfunctional either through breakdown of the element or the elements being busy, a secondary path is established to an available element in the next row and from this back to follow the row of the initial element through the chip.

A method of this invention comprises a series of systolic processing elements (SPE's) arranged in rows normal to each other, have sequential paths between elements biased so that normally the data being processed follows the vertical and horizontal rows to maintain a selected topography, characterised by the steps of; establishing the functionality of each SPE, bypassing any unfunctional SPE by directing the data path of any row to a near SPE in the next row, and directing the data path from the said near SPE back to the original row to maintain the original topography.

The processor comprises an LSI or VLSI in which a series of systolic processing elements (SPE's) are arranged to arrays rows normal to each other and have sequential paths between elements biased so that normally the data being procesed follows the vertical and horizontal rows to maintain a selected topography, characterised by; means to detect a monfunctional SPE in a selected row, and means to divert the data path around the nonfunctioning SPE by diverting the data path to a functional SPE in the next row adjacent to the nonfunctioning SPE and back to the next SPE in the said selected row whereby to maintain the original topography.

FIG. 1 is a schematic view indicating a module in which rows of elements in which two elements are inoperative and in which the changed flow paths are illustrated,

FIG. 2 represents a basic sonar system,

FIG. 3 shows an inner product accumulation element,

FIG. 4 shows how Matrix-Matrix multiplication occurs,

FIG. 5 is a table showing processors, priority and row data paths associated with the pq.sup.th SPE,

FIG. 6 shows partitioned systolic arrays for increased speed and reliability,

(a) showing an (N+1).times.N array

(b) showing an (N+2).times.N array, and

(c) showing a further (N+2).times.N array,

FIG. 7 shows an array with two dimensional redundancy,

FIG. 8 shows a graphical comparison of system reliability for a 32.times.32 element array showing in the full line graph of a nonredundant condition, in chain line a reliability structure of FIG. 6 (a) and in dotted lines a reliability structure for FIGS. 6(b) and 6(c),

FIG. 9 corresponds to FIG. 1 but shows a two dimensional redundancy,

FIG. 10 shows a systolic processing element with data path switching and control detailed,

FIG. 11 shows control and data path interconnections between systolic processing elements, and

FIG. 12 shows, in "stick" notation, an NMOS VLSI implementation of the multiplexer where the "don't cares" have been assigned to minimise gating logic.

Referring first to FIG. 1 of the drawings, horizontal rows H and vertical rows V are shown, each containing at the intersections of the rows systolic processing elements SPE, which rows include two nonfunctioning elements SPE1 and SPE2 showing the flow-paths established by the algorithm through biasing of the paths, the signal fed into the paths including a test signal which detects an unworkable or busy element in the particular row and then causes diversion to the next workable element and back again to the row without destroying the terminal sequence of the paths. The lower SPE's are redundant so far as a normal horizontal row array is concerned.

Because there can be a number of redundant elements in such a system it will be realised that whereas replacement of the chip or the element would otherwise be necessary, the present invention allows the function of the chip to continue using alternate elements available for the processing procedure.

Consider the basic sonar system given broadly in FIG. 2.

The computationally intensive component in this system is the beamformer. Let

describe an N.times.N matrix F of Fourier coefficients.

If N sensor array samples in row order define an N.times.N matrix A, then FA is a matrix whose columns are the Discrete Fourier Transforms (DFT) of each sensor output. The matrix FAF is then the two dimensional DFT of A and performs the beamforming function. A beamformer can then be implemented by an architecture which executes full matrix multiplication.

Whitehouse and Speiser, referred to earlier, describe an SAP consisting of elements which perform inplace inner product accumulation as shown in FIG. 3.

Data flow for a matrix-matrix multiplication executed in this processor is shown in FIG. 4. The computation is completed in 3N-2 cycles, and pipelining can achieve near to complete utilisation.

Failure of any processing element in the processor as so far discussed results in failure of the system. However a structure can be considered which allows reliability to be attained through SPE redundancy. A systolic architecture can be defined in terms of the data paths between processors.

{d.sub.ij d.sub.i+l,j : i=1, . . . , N-1: j=1, . . . , N} defines the vertical paths

{d.sub.ij d.sub.i,j+1 : i=1, . . . , N: j=1, . . . , N-1} defines the horizontal paths

in the above architecture. Independent buses can be implemented on any path for the transfer of both input and output data.

For redundancy this basic structure can be expanded with additional initially redundant paths defined by

{d.sub.ij d.sub.i+r, j+1 : i=1, . . . , (n-r): j=1, . . . , (N-1): r=1, . . . , k}

{d.sub.ij d.sub.i-r, j+1 : i=(r-1), . . . , N: j=1, . . . , (N-1): r=1, . . . , k} and

{d.sub.ij d.sub.i+2, j : i=1, . . . , (N=2): j=1, . . . , N}

These paths allow k redundant SPE's to be included in each column. The failure of up to k SPE's then causes system errors only until a fault detection and data path reconfiguration process has been completed. Failed SPE's are bypassed in such a way as to retain the original topology, and no throughput degradation is incurred. Implementation difficulties limit the maximum number of redundant elements which may be incorporated in this way. As k increases, circuit complexity in the data paths increases and can exceed the complexity of the SPE. To ensure that data path reliability is much greater than SPE reliability, we therefore consider an implementation with the minimum possible redundancy of one. For correct system operation it is necessary to define data path selection procedures which enable each SPE to transfer data and results to a correctly functioning adjacent SPE. It is shown later than SPE functionality can be flagged by the element itself.

Possible row data paths for the pq.sup.th SPE are detailed in the table, of FIG. 5.

The input data path is determined by the pq.sup.th SPE sending an acknowledgement to a request for service from the highest priority requesting processor, and a "busy" signal to the remaining two processors. The output data path is that which is directed to the lowest priority available output processor. Data paths from edge array elements {d.sub.1j d.sub.0, j+1 }, {d.sub.N, j d.sub.N, j+1 } are directed out of the array and are hardware intialised to return "busy" signals. These paths force the correct initial structure. Failure of the pq.sup.th SPE causes "busy" signals to be returned to all input processors. The data path d.sub.p-1, q d.sub.p+1, q is then activated to by-pass the column element.

If no output data path is available to the pq.sup.th element due to SPE failures, that element also "fails". This dynamic structure is capable of both bypassing a failed SPE and also restoring the SPE to the active structure if functionality is regained.

An implementation methodology for online performance monitoring and fault detection and location for modular sonar signal processors is briefly discussed in Bartram, J. F., Ramseyer R. R. and Heines J. M., referred to earlier herein. A supervisory element which controls the functioning of any module also executes regular diagnostic algorithms on the modules and reports to the system controller. An equivalent diagnostic technique can be considered for a cellular array of SPE's.

If each SPE is designed with a diagnostic mode where it flags the result of a comparison of a reference value with an inner product accumulation, the functionality of each array element can be tested. The matrix product

where a.sub.ij =0, j>2 and b.sub.ij =0, i>2, is complete in two pipelined cycles. The accumulated inner product terms c.sub.ij of the resultant matrix, if correct, demonstrate the correct functioning of both data paths and SPE's. If a diagnostic mode bit is added to each of the data paths in one dimension, a complete diagnostic algorithm can propagate through the array in a systolic manner. If performed after every full matrix multiplication, performance is degraded by only (2/N).times.100%. The use of augmented matrices enables redundant elements to be tested also. The failure of any SPE will then be notified to the supervisor by the failure of the row of redundant elements to accept data. The failure of two rows indicate system failure.

Consider an m.times.n array of SPE's with m>n. The active elements initially form an n.times.n matrix with m-n rows of "hot" spares. All elements are assumed independent. The time to failure, t.sub.f, of each element is a sample from an exponential distribution. i.e.

is the failure time density distribution and

is the failure time distribution function, where t.sub.f >0.

The probability that an element will be functioning at time t is defined as the reliability, r(t) ##EQU1## A column will fail, and will cause the system to fail when only n-1 elements remain active in it. The probability that exactly n elements remain in an m.times.1 column at time t is binomially distributed and is given by ##EQU2##

The probability of failure of one of the remaining n independent elements in the time interval (t,t+dt) is

Thus the probability for column failure in this interval is ##EQU3## and the column failure density function is ##EQU4## Expressed as a function of r(t), ##EQU5##

The probability that a column has not failed at time t is its reliability R(t), i.e. ##EQU6## Substituting a=n and b-1=m-n ##EQU7## Using Luke (7), 8.2.3 equations (1) and (3), ##EQU8## Where .sub.2 F.sub.1 (.,.;.;.) is the usual Gauss Hypergeometric function. For the minimum redundancy condition of one element,

The reliability of n columns and hence the system reliability is then

The system reliability defined by equation (15) can be improved. Accepting the limitation of one redundant element per column, we now examine ways in which the task can be decomposed to allow an increased system redundancy.

Consider the product of two matrices of even order n. There is no loss of generality of the restriction to even order as an odd order matrix can be augmented with zeroes to satisfy this requirement. FIG. 4(a) shows the implementaton of this multiplication on the cellular array with one redundant element per column. The non-pipelined execution time for this structure is 3n-2 cycles.

Whitehouse defines the non-pipelined execution time of non square arrays in terms of a J.times.N and N.times.K matrix product. The execution time is N+J+K-2 cycles on a cellular array of dimensions J.times.k.

Partitioning the matrices in equation (2) gives

The two partitioned matrix products C.sub.1 and C.sub.2 can be computed in parallel on two N/2.times.N cellular arrays, each computing the product of an N.times.N with an N.times.N/2 matrix. Computation time is reduced to 5N/2-2 cycles and it is clear that a restructuring of the array in 6(a) allows a doubling of the percentage of redundant SPE's. The restructured array is shown in FIG. 6(b).

System reliability is given by

A further partitioning gives ##EQU9## Implementation of this partitioning is shown in FIG. 6(c). Execution time is again reduced and is 2N-2 cycles. Redundancy and reliability are identical to that of 6(b), but the time to detect fault conditions is minimised.

So far the implementation of a one dimensional redundancy philosophy to a particular data path architecture has been discussed. Increasing the formal data paths in this architecture with

{d.sub.ij d.sub.i, j+2 : i=1, . . . , n; j=1, . . . , (n-2)}

allows the introduction of redundancy in two dimensions as shown in FIGS. 7, 8 and 9. Analysis and discussion of this structure is not included but it is noted that the partitioning of (18) results in a structure with the highest percentage redundancy, the highest reliability and the fastest non-pipelined computation time.

In FIG. 9 four nonfunctional SPE's, SPE3 to SPE6 and the left hand SPE's at the module edge are redundant so far as a vertical row array function is concerned.

FIG. 8 compares the reliabilities of the implementations given in FIGS. 6(a), (b) and (c) on a 32.times.32 element primary array with a nonredundant system. The ability of these architectures to operate with no performance degration has significant implications for the production of future VLSI dice. Production costs can be minimised by allowing production faults to be present, but made transparent to the user by self configurable architectures.

FIG. 10 shows a systolic processing element. The data lines allow the element to perform a multiply-accumulate function on coefficients which are passed through orthogonal rows and columns of such elements. FIG. 2 shows the interconnection of data and control paths for a particular element in an array. The control signals involve fewer protocols than are required in the general case, but allow a high density VLSI implementation.

Initialisation of data paths and control signals is by a master reset line which sets the state of all elements to "failed". In this state every element accepts data from the A1 data input. Activation of a test mode by an instruction associated with the input data then determines the functionality of the element and sets the "fail" flag. All control signals are updated only at the completion of the test phase and are transmitted only to adjacent elements. The functional data paths used by subsequent operations are established by the propagation of this test mode across and down the array. Selection of the input data path is by a multiplexer controlled by combinatorial logic. Inputs to the combinatorial logic circuit are obtained directly from the status outputs of the elements directly above and to the left of the element. Neglecting the reset condition, the truth table for the input data path multiplexer is as follows;

where x indicates a "don't care".

"System fail" is a flag which propagates to the edge of the array if more than one element in a column fails. This is a condition which can not be resolved with only one redundant element, and the system will have failed.

Once established by a test mode, the data paths remain stable until an element failure is detected by a subsequent test mode. A reconfiguration of the active paths then occurs to restore system functionality. Horizontal data paths are biased to bypass a failed element and elements in the vertical path force data to bypass them if they are in the "failed" state. Recovery of an element is possible as data is still available to the failed element for it to perform all subsequent tests. A successful test will clear the "fail" flag and cause a restoration of the data paths. This feature of the implementation allows recovery from "soft" errors which do not recur when another test is made.