AU567251B2 - Self repair large scale integrated circuit - Google Patents

Description

"SELF REPAIR LARGE SCALE INTEGRATED CIRCUIT"

INTRODUCTION

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, dispaly 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 number of authors including

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

(2) Whitehouse H.J. and Speiser J.M. , "Sonar applications of systolic array technology", IEEE EASCON, Washington, D.C., Nov, 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,

Jan, 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, Jan, 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 INVENTION

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 processed follows the vertical and horizontal rows to maintain a selected topography, characterised by; means to detect a nonfunctional 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.

THE DRAWINGS

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 SPE,

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

(a) showing an (N+1) x N array

(b) showing an (N+2) x N array, and

(c) showing a further (N+2) x N array, FIG. 7 shows an array with two dimensional redundancy,

FIG. 8 shows a graphical comparison of system reliability for a 32 x 32 element array showing in the full line graph of a non redundant 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.

A SONAR SIGNAL-PROCESSING SYSTEM

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

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

f = exp(-i 2πpq/N) (1)

describe an NxN matrix F of Fourier coefficients.

If N sensor array samples in row order define an NxN 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.

IMPLEMENTATION

Whitehouse and Speiser, referred to earlier, describe an SAP consisting of elements which perform in- place inner product accummulation 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.

A SYSTOLIC CONFIGURABLE ARRAY PROCESSOR

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_ij d_ι+1,j : i=1 ,...,N-1 : J=1,...,N} defines the vertical paths {d_ij d_{i, j}.₊₁ : 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_ij d_i+r,j+1 : i=1, ..., (n-r): j=1,...,(N-1):r=1,...,k} {d_ij d_i-r,j+1 : i=(r-1),...,N:j=1,...,(N-1):r=1,...,k}

and

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 that SPE functionality can be flagged by the element itself.

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

The input data path is determined by the pq^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_1j d_0,j+1}, {d_N,j d_N,j+1}

are directed out of the array and are hardware initialised to return "busy" signals. These paths force the correct initial structure. Failure of the pq^th SPE causes "busy" signals to be returned to all input processors. The data path d_p-1,qd_{p + 1 , q} is then activated to by-pass the column element.

If no output data path is available to the pq^th element due to SPE failures, that element also "fails". This is a system failure condition which propagates back to the edge of the array and is reported to the supervisor. This dynamic structure is capable of both bypassing a failed SPE and also restoring the SPE to the active structure if functionality is regained.

FAULT DETECTION IN A SCAP

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

A B = C ( 2 )

where a_ij = 0, j>2 and b_ij = 0, i>2, is complete in two pipelined cycles. The accumulated inner product terms c_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)x100 %. 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.

RELIABILITY ANALYSIS

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

i.e. f(t_f = λ exp(-λt_f) (3)

is the failure time density distribution and

F(t_f) = 1 - exp (-λt_f) (4)

is the failure time distribution function, where t_f> 0. The probability that an element will be functioning at- time t is defined as the reliability, r(t)

i.e. r(t) = P[t_f > t] = 1 - F(t) = exp(-λt) (5)

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 x 1 column at time t is binomially distributed and is given by

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

P₁(dt) = nλdt (7)

Thus the probability for column failure in this interval is

and the column failure density function is

Expressed as a function of r(t),

The probability that a column has not failed at time t is its reliability R(t), i.e.

Substituting a = n and b-1 = m-n

Using Luke (7), 8.2.3 equations (1) and (3),

Where 2F₁ (.,.;.;.) is the usual Gauss Hypergeometrie function. For the minimun redundancy condition of one elment,

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

INCREASED RELIABILITY STRUCTURES

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 in the restriction to even order as an odd order matrix can be augmented with zeroes to satisfy this requirement. FIG. 4(a) shows the implementation 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 x N and N x K matrix product. The execution time is N + J + K - 2 cycles on a cellular array of dimensions J x k.

Partitioning the matrices in equation (2) gives

[A] [B₁B₂] = [C₁C₂] (16)

The two partitioned matrix products C₁ and C₂ can be computed in parallel on two N/2 x N cellular arrays, each computing the product of an N x N with an N x 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

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.

TWO-DIMENSIONAL REDUNDANCY

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_ij d_i,j+2 :i=1,..,n;j=1 ,..,(n-2)}

allows the introduction of redundancy in two dimensions as shown in FIG. 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 x 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.

AN IMPLEMENTATION

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 arid 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;

CONTROL I/P DATA PATH

INPUTS SELECT DEC INC FAIL

0 0 0 A1

1 0 0 A0

0 1 0 A2

1 1 0 A1

0 0 1 X

1 0 1 A0

0 1 1 X

1 1 1 A2 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 biassed 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.

Claims

CLAIMS:

1. The method of self repair of large scale integrated circuit modules (LSI or VLSI) in which 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;

(a) establishing the functionality of each SPE,

(b) bypassing any unfunctional SPE by directing the data path of any row to a near SPE in the next row, and

(c) directing the data path from the said near SPE back to the original row to maintain the original topography.

2. The method of claim 1 in which a test signal, which detects a non-functioning SPE in the particular row, is injected into the row and an algorithm trigers divertion of the data to the SPE in the next row and back to the next SPE in the row from which the data was diverted.

3. The method of claim 1 or 2 in which the VLI has rows of initially redundant SPI's to increase the number of replacement SPI's available for a selected number of usable rows.

4. The method of claim 1 or 2 in which SPI's in any edge row divert the data to give a busy signal to indicate non-functioning of the edge row.

5. The method according to any one of claims 1, 2, 3 or 4 wherein the functionality of an SPE is caused to be flaged by the element itself as a result of a comparison of a reference value with an inner product accumulation to allow testing a flaged element.

6. A method of self repair of large scale integrated circuit modules substantially as described.

7. A self repair large scale integrated circuit module (LSI or VLSI) in which a series of systolic processing elements (SPE's) are arranged as arrays of rows normal to each other and 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;

(a) means to detect a non-functional SPE in a selected row, and

(b) means to divert the data path around the non-functioning SPE by diverting the data path to a functional SPE in the next row adjacent to the non-functioning SPE and back to the next SPE in the said selected row whereby to maintain the original topography.

8. A self repair large scale integrated circuit module according to claim 7 characterised by an algorithm biasing the said paths, and by a test signal which detects a non-functional SPE in a selected row and diverts the said path to a near SPE in the next row and back to the said selected row.

9. A self repair large scale integrated circuit module according to claim 7 in which the said large scale integrated circuit has at least a redundant row of SPE's to increase the number of SPE's available for replacement of non-functional SPE's.

10. A self repair large scale circuit module such as an LSI or a CLSI in which a series of systolic processing elements (SPE's) are arranged in arrays of rows normal to each other and 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;

(a) at least an extra row of SPE's vertically or horizontally,

(b) an algorithm biasing the said paths to normally follow said rows,

(c) a test signal which detects a non-functional SPE in a selected row, and (d) means triggered by the said test signal arranged to divert the said path under control of the said algorithm to around the said non- functioning SPE through an SPE in the next row adjacent to the said non-functional SPE, said diversion occurring from the SPE spatially before the non-functioning SPE to the SPE spatially following the non-functioning SPE whereby to maintain the original topography.

11. A self repair large scale integrated circuit module according to claim 10 further characterised by means at the edge rows of SPE's to initiate an operator warning signal if the data path is diverted out of the said module.

12. A self repair large scale integrated circuit module constructed and operating substantially as described and illustrated.