# Patent

## Title
Software read and write tracing using hardware elements

## Abstract

A method is provided for determining the location of faulty components in a computer memory array on a chip and for providing a software repair procedure. According to the method, the location of faulty components in a computer memory array is determined by successively reading and writing to locations in the array according to an algorithm. If a faulty component is detected, it is determined whether a spare component in a spare memory array on the chip is available. If a spare component is available, a spare component is designated to correspond to the faulty component. A look up table on the same chip stores information representing the location of the faulty component associated with information representing the location of the corresponding spare component. The method may also include, testing the memory array by successively reading and writing to locations on the memory array according to an algorithm, during which step, when a faulty component with which a spare component is associated is addressed, the look up table is used to identify the spare component corresponding to the faulty component, and the spare component is addressed.

## Background
This invention relates to computer memories, and in particular to built-in self-test techniques for embedded memories.

Computer memory arrays on chips involve a very large number of individual cells. For dynamic random access memories, the number of cells is very large. As a result, even small defect rates arising out of the manufacturing process result in an unacceptably low yield. Test procedures are applied to DRAM chips, usually on wafer-by-wafer basis. Every chip on each wafer is tested on specialized equipment, which identifies the locations of defective cells. Location information is then supplied to a controller for a laser repair device, which achieves a hardware fix. The repaired wafer is then tested again.

Such test and repair procedures are expensive because of the need to employ specialized test and repair equipment.

In SRAM chips, and other chips with embedded logic, repairs are not ordinarily carried out. The size of arrays in SRAM chips and other such chips has been small enough that, even without repairs, acceptable yield is obtained. Also, because SRAM chips are generally more specialized and manufactured in smaller quantities, the cost of configuring laser repair machines must be averaged over a relatively small number of wafers, when compared to DRAM chips.

In chips with embedded memories, it has become possible to have test procedures carried out by logic on the chip, known as built-in self-test units. The built-in self-test units for SRAM chips carry out a verification process resulting in a simple indication of whether there is a defect in the memory array. As defective chips are simply discarded, no additional information is required.

However, array size in SRAM chips is steadily increasing. Accuracy in manufacturing techniques is not increasing sufficiently rapidly to maintain yields. Furthermore, additional components, which were formerly in separate devices, are also being added to SRAM chips. The added components increase functionality of the chips, and are sometimes referred to as a system on a chip. These devices mean that individual chips are much more expensive, making discarding faulty chips undesirable.

According to an aspect of the invention, a method is provided for determining the location of faulty components in a computer memory array on a chip and for providing a software repair procedure. According to the method, the location of faulty components in a computer memory array is determined by successively reading and writing to locations in the array according to an algorithm. If a faulty component is detected, it is determined whether a spare component in a spare memory array on the chip is available. If a spare component is available, a spare component is designated to correspond to the faulty component. A look up table on the same chip stores information representing the location of the faulty component associated with information representing the location of the corresponding spare component. The method may also include, testing the memory array by successively reading and writing to locations on the memory array according to an algorithm, during which step, when a faulty component with which a spare component is associated is addressed, the look up table is used to identify the spare component corresponding to the faulty component, and the spare component is addressed.

FIG. 1 is a block diagram of a device according to the present invention.

FIG. 2 is a more detailed block diagram of a device according to the present invention.

FIG. 3 is a flow diagram showing steps in a method according to the present invention.

FIG. 4 is a flow diagram showing steps in a method according to the present invention.

Referring now to FIG. 1, there is shown a high level block diagram of a memory device and associated devices. The components shown on the block diagram are all on a substrate, normally a silicon chip. These components are all components of what is generally referred to as the memory block of a memory device. There is shown a static read only memory (SRAM) 10, a data in selector 14, an address selector 18, a repair control unit 22, and a test and repair unit 26. Data input line 30 couples an input side of data in selector 14 to other devices. Data input line 30 may be, for example, a 16-bit line. Test data line 34 couples an output of test and repair unit 26 to an input side of data in selector 14. Test data line 34 is preferable of the same bandwidth as data input line 30. Memory input line 38 couples an output of data in selector 14 to memory 10. Address input line 42 couples address selector 18 to other devices. Address input line 42 may be a 16-bit line. Test address line 46 couples an output of test and repair unit 26 to address selector 18. Address input line 50 couples an output of address selector 18 to memory 10. Second address input line 54 couples repair control unit 22 to other devices. Second address input line 54 may be a 7-bit line. Repair control unit output line 58 couples an output of repair control unit 22 to memory 10. Data output line 62 couples an output of memory 10 to other devices, through branch 63, and to test and repair unit 26, through branch 64. Data output line 62 may be 16-bit line.

Referring now to FIG. 2, there is shown a block diagram of test and repair unit 26, which may also be referred to as built-in self-repair (BISR) and self-test unit. Test and repair unit 26 is depicted with various devices surrounding memory unit 10. Test and repair unit 26 is seen to include BISR controller 70, BISR address generator 75, BISR data generator 80, and BISR output data evaluator and repair 85. The components of test and repair unit 26 may also be referred to as memory test hardware. BISR controller 70 is coupled through data line 88 to BISR data generator 80. BISR controller 70 is coupled through data line 90 to BISR address generator 75. BISR controller 70 is coupled through a data line to address selector 18, which is a multiplexor in this embodiment. BISR controller 70 is also coupled to read/write and chip select selector 92. An output of BISR data generator 80 is coupled to repair control unit 22 though multiplexor 94. The output of BISR data generator 80 is also coupled to data in selector 14, which is a multiplexor. An output of BISR address generator 75 is coupled, through multiplexor 96 to reconfiguration control unit 22. Multiplexor 96 selects between signals from BISR address generator 75 and external address signals. Multiplexor 98 is provided intermediate BISR address generator 75 and multiplexor 96. Multiplexor 98 permits testing of both repair control unit 22 and memory unit 10 using addresses output by BISR address generator 75. The output of BISR address generator 75 is also coupled to address selector 18.

Memory unit 10 includes input and output devices as set forth in more detail below with respect to FIG. 3. Read/write and chip select selector 92 is coupled through line 72 to an output of BISR controller 70. Read/write and chip select selector 92 is also coupled, through line 73, to an external source of read/write and chip select signals. It will be understood that BISR controller 70 is adapted to provide on line 72 signals emulating read/write and chip select signals. Address selector 18 is coupled, as noted, to BISR address generator 75, and to an external address bus (not shown). Data in selector 14 is coupled both to an output of BISR data generator 80 and to an external data bus (not shown).

As for the inputs of repair control unit 22, multiplexor 94 is also coupled to an output of BISR output data evaluator and repair 85. Multiplexor 96 is coupled to an external address bus, as is address selector 18. BISR controller 70 is also directly coupled to reconfiguration control unit 22. An output of reconfiguration control unit 22 is coupled to repair address decoder 102, to RCU output data evaluator 104, and to BISR output data evaluator and repair 85.

It will be understood from FIG. 2 and the above description that BISR controller 70 provides the logic for self-repair and self-test device 26.

BISR controller 70 is a suitable programmable device, such as several finite state machines and associated control signals. Microcontrollers could also be employed.

The steps in the testing process will now be described with reference to FIG. 3. The first step is an algorithmic test on repair control unit 22, as shown by block 120 labeled CONDUCT ALGORITHMIC TEST ON REPAIR CONTROL UNIT. This step is carried out by BISR controller 70 providing signals to BISR address generator 75 and BISR data generator 80 to carry out an algorithmic test on repair control unit 22. The algorithmic test consists of alternately writing to and reading from the cells in repair control unit 22 according to a predefined algorithm. The algorithm may be, by way of example, a 17n or 17-step algorithm. An algorithm known as Algorithm B is an example of such an algorithm. RCU output data evaluator 104 receives output data from repair control unit 22 during this test. RCU output data evaluator 104 is designed simply to determine whether or not there are any faults detected during the algorithmic test. BISR controller 70 provides control data to RCU output data evaluator 104. RCU output data evaluator 104 compares data received from repair control unit 22 to control data received from BISR controller 70. RCU output data evaluator 104 then reports the result of the test, i.e., whether or not a discrepancy, and therefore a fault, has been detected, to BISR controller 70. As shown by decision block 125, labeled FAULTS DETECTED?, if faults are detected in repair control unit 22, the conclusion is that the chip is unrepairable, as shown by ending block 130, labeled UNREPAIRABLE. In that event, the test is ended.

If no faults are detected in repair control unit 22, the next step depends on whether the retention tests are to be skipped, as shown by decision block 135, labeled SKIP RETENTION TESTS? Retention tests determine whether data is retained in memory cells over an extended period of time. Retention tests generally involve writing a known pattern to a memory, waiting a preselected period of time, reading the data stored in memory, writing the complement of the known pattern, waiting the preselected period of time again, and reading the data stored in memory. If there is any discrepancy between the data written to the memory in either step and the data read from the memory, the memory is failing to retain data, usually as the result of manufacturing errors. As the preselected period of time is ordinarily measured in minutes or hours, retention tests are only conducted when completely necessary, such as on the initial testing of the chip following manufacturing. In the field, because of the delay in using the memory resulting from the need to wait for the preselected period of time, retention testing is not desirable. Also, retention faults ordinarily arise from manufacturing defects, and do not ordinarily develop in memories after manufacture. Therefore, the value of retention testing in the field is limited. The BFC signal to BISR controller 70 indicates whether or not the retention test is to be skipped. If the retention test is not being skipped, then the next step is to conduct a retention test on repair control unit 22, as shown by block 140, labeled CONDUCT RETENTION TEST ON REPAIR CONTROL UNIT. A retention test is conducted under the control of BISR controller 70 by BISR data generator 80 providing data to repair control unit 22 and BISR address generator 75 providing address information for the data. RCU output data evaluator 104 is used by BISR controller 70 to check for retention test results indicating a retention fault.

If the retention tests are being conducted, the next step is conducting a retention test on memory 10, as shown by block 145, labeled CONDUCT RETENTION TEST ON MEMORY. BISR controller 70 initiates the retention test on memory 10 by providing suitable instructions to BISR address generator 75 and BISR data generator 80. Data is output to BISR output data evaluator and repair 85.

If both retention tests are successful, the testing proceeds to testing of RCU output data evaluator 104 and BISR output data evaluator and repair 85, as shown by block 150, labeled TEST EVALUATORS. As can be seen from FIG. 3, the step of testing of RCU output data evaluator 104 and BISR output data evaluator and repair 85 is also the step immediately following the algorithmic test on repair control unit 22, if the retention tests are not being conducted. A walk and address test is conducted on BISR output data evaluator and repair 85 and RCU output data evaluator 104 by BISR controller 70.

The next step is to initialize repair control unit 22 by storing 0's in all of its memory locations, as shown by block 155, labeled STORE ALL 0'S IN REPAIR CONTROL UNIT. This step is carried out by BISR controller 70 providing suitable instructions to BISR data generator 80 to generate 0's and BISR address generator 75 to designate all memory addresses in repair control unit 22.

After completion of the foregoing step, the next step is the execution of an algorithmic test on main memory only of memory 10 and the updating of repair control unit 22 with data reflecting mapping between defective cells in main memory and corresponding spare cells in one or more spare memories of memory 10. This process is shown by block 160, labeled WITH REPAIR CONTROL UNIT LOCKED OUT, CONDUCT ALGORITHMIC TEST ON MAIN MEMORY ONLY AND UPDATE REPAIR CONTROL UNIT. This step is explained in detail below with reference to FIG. 4. During this step, BISR controller 70 provides control signals to BISR address generator 75 and BISR data generator 80 to perform an algorithmic test on the main memory 10. BISR output data evaluator and repair 85 evaluates the data received from memory 10. BISR output data evaluator and repair 85 sends a signal to BISR controller 70 indicating whether or not the data is faulty. The information as to whether or not the output data is faulty is employed by the algorithm to decide the next step. If the output data, as indicated by the signal from BISR output data evaluator and repair 85 is not faulty, then there is no need to update repair control unit 22, and the algorithm proceeds to the next address. If the output data is faulty, then the algorithm proceeds to a repair branch, discussed in detail below with reference to FIG. 4. During this testing step, repair control unit 22 is locked out. This is accomplished by BISR controller 70 sending a suitable signal to address multiplexor 98. As a result, the testing is carried out proceeding through the entire main memory. Any allocations of spare memory cells are disregarded during this step. No testing is carried out on the spare memory block or blocks in memory 10.

During the foregoing step, the chip may be declared unrepairable for a variety of reasons, as discussed in more detail below with reference to FIG. 4. In that event, the testing process is stopped. If the foregoing step of algorithmic testing of the main memory and allocation of spares is completed, the next step is to determine whether repair control unit 22 has been updated. This is shown in FIG. 3 by decision block 165, labeled WAS REPAIR CONTROL UNIT UPDATED? If repair control unit 22 was not updated, then the testing is completed, as shown by the line marked NO leading from block 160 to block 195, labeled END.

If repair control unit 22 was updated, then the next step is to commence conducting an algorithmic test of memory 10 with repair control unit 22 activated. BISR controller 70 causes BISR data generator 80 and BISR address generator 75 to conduct an algorithmic test on memory 10. During this step, an appropriate signal is provided by BISR controller 70 to multiplexor 98 so that repair control unit 22 is activated. The same algorithmic test as is conducted on the main memory is preferably used. This step is indicated in FIG. 3 by block 170, labeled WITH REPAIR CONTROL UNIT ENGAGED, COMMENCE ALGORITHMIC TEST ON MAIN MEMORY AND ALLOCATED SPARES. As this test proceeds, faults may be detected in cells in the spare memory blocks. As will be recalled, no general test of the cells of the spare memory blocks is conducted. As many of the cells in a spare memory block are not allocated and therefore not used, the test procedure would be unnecessarily prolonged by testing every cell in the spare memory blocks.

During this step, if no faults are detected, the test is at an end. This is indicated by decision block 175, labeled FAULT DETECTED?, and the line labeled NO leading from decision block 175 to block 190, labeled END. If any faults are detected, new spare cells will be required. Accordingly, the algorithm determines if any new spare cells are available, as indicated by decision block 180, labeled SPARES REMAINING? If no spares are available, the algorithm determines that the chip is unrepairable, as indicated by the line labeled NO leading from block 180 to block 130, labeled UNREPAIRABLE. If spares are remaining, new spare cells are allocated to replace cells in the spare memory array that are found to have faults. If the allocation algorithm identifies an available new spare cell, then repair control unit 22 is updated, and the algorithmic test is restarted. This is indicated in FIG. 3 by block 185, labeled UPDATE REPAIR CONTROL UNIT. The process then returns to conducting the algorithmic test on the main memory and the allocated spares with the repair control unit engaged, as indicated by the line leading from block 185 to block 170. This process continues until the entire memory array is tested, with the repair control unit engaged, thereby testing allocated spare cells, and no faults are found. Alternatively, the process ends when the allocation algorithm determines that no spare cells are available. The test process is then concluded. BISR controller 70 then provides a signal indicating whether the memory chip is usable.

Referring now to FIG. 4, the allocation algorithm will be explained in greater detail. The algorithm set forth in FIG. 4 is carried out by BISR controller 70. The algorithm has generally two functions. The first function is to determine whether or not a spare component is available. The second function, invoked after the first function determines that a spare component is available, is the allocation of a spare component in the spare memory block. As part of the process, the address of the faulty component, and the address of the allocated spare component, are stored in suitable association with one another in repair control unit 22. In FIG. 4, block 400, labeled REPAIR BRANCH, indicates the commencement of the repair process. The repair process commences after completion of the algorithmic test. The algorithmic test is carried out on an address-by-address basis. The information identified by the algorithmic test is carried. The algorithm is capable of identifying the location of the fault to the degree of detail desired. For example, if spares are allocated on a cell-by-cell basis, the algorithm must be capable of specifying the address of the faulty cell. If spares are allocated on a bit-by-bit basis, then the algorithm need only specify the bit and column that contains the fault. In block 410, the information is the number of faults, and the bit and column numbers of the faults. The algorithm then determines whether the number of faults exceeds the number of faults repairable at the address, as indicated by block 415. For example, the algorithm may be configured to relate to a main memory block that is divided into a number of sub-blocks, and in which the number of faulty bits in each word that can be replaced in each sub-block is equal to the number of spare memory blocks. This may alternatively be stated as no more than one bit in each spare memory block may be assigned to any one main memory sub-block.

A line marked YES leads from block 415 to block 455, labeled UNREPAIRABLE. This If the number of faults exceeds the number of faults repairable at the address, the fault is unrepairable.

If the number of faults does not exceed the number of faults repairable at the address, then the next step is to determine whether the available spares have already been allocated in repair control unit 22. To do this, in this configuration, BISR controller 70 sends suitable signals to repair control unit 22 to look up the bits that designate the column in question. This step is indicated by block 425, labeled HAS FAULTY COLUMN BEEN PREVIOUSLY IDENTIFIED AS FAULTY?. In this step, the algorithm determines only whether the 7-bit addresses are the same.

If the faulty column has been previously identified as faulty, the next step depends on whether the algorithm is in replace when done mode, or replace immediately mode. Replace when done mode refers to the process conducted with repair control unit 22 locked out. Replace immediately mode refers to the process conducted with repair control unit 22 engaged. In replace immediately mode, the replacement column is marked as faulty, as indicated by block 430. In replace when done mode, the algorithm determines whether the newly identified fault is the same as the previously-identified fault, i.e., whether the previously identified fault and the newly-identified fault are in the same sub-block. This step is illustrated in FIG. 4 by block 435, labeled SAME FAULTS? If the faults are in the same sublock, then a fault that was previously corrected by assignment of a corresponding spare address has been detected. As indicated by the line labeled YES leading from block 435 to block 440, labeled PROCEED TO NEXT ADDRESS, if this is the case, then the repair branch is completed. The test algorithm will then proceed to the next address in sequence.

In the event that the faulty column was not previously identified as faulty, or if the algorithm is in replace immediately mode, or if the algorithm is in replace when done mode and the newly-identified fault is different from the previously-identified fault, the next step is to determine whether the number of faults and allocated spares exceed the limit of available spares. This is indicated by block 445. If the number of faults and allocated spares exceeds the limit of available spares, the fault is unrepairable, as indicated by the line marked YES leading from decision block 445 to block 455. If the number of faults and allocated spares does not exceed the limit, then the algorithm proceeds to the step of allocating spares, and entering the fault and spare information into repair control unit 22, as indicated by block 460.

Allocation of spares is carried out by simply finding the next available column in the appropriate spare memory block. Preferably, spares are allocated on a rotation basis through the spare memory blocks so that the number of allocated spare columns is approximately the same in all spare memory blocks.

When allocation and entering of the information is completed, the next step depends on whether the algorithm is in replace when done mode or replace immediately mode. In replace immediately mode, the entire memory, including the spares, is retested immediately. Accordingly, as indicated by block 465, the process is reinitialized. In replace when done mode, the process proceeds to block 440, labeled PROCEED TO NEXT ADDRESS. This indicates that the repair branch is complete and the testing algorithm proceeds to the next address.

The foregoing method provides a fast evaluation of the main memory array, and of the spare memory array only to the extent required. As the method is relatively fast, the self-test (excluding the retention tests) can be carried out each time the device to which the memory pertains is activated.

It will be understood that various changes in the details, materials and arrangements of the parts which have been described and illustrated above in order to explain the nature of this invention may be made by those skilled in the art without departing from the principle and scope of the invention as recited in the following claims.

## Claims

1. A method for determining the location of faulty components in a computer memory array on a chip and for providing a software repair procedure, comprising the steps of: array by successively reading and writing to locations in the array according to an algorithm; component in a spare memory array on the chip is available; correspond to the faulty component; and location of the faulty component associated with information representing the location of the corresponding faulty component.

2. The method of claim 1, further comprising the step of: reading and writing to locations on the memory array according to an algorithm, during which step, when a faulty component with which a spare component is associated is addressed, using said look up table to identify the spare component corresponding to said faulty component, and addressing said corresponding spare component.

3. The method of claim 2, further comprising the steps of, when a faulty spare component is detected, designating a replacement spare component, if available, for the faulty component associated with the faulty spare component, and repeating said step (e) for all of said memory array.

4. The method of claim 1, wherein said step (a) comprises using a device on the chip to control said steps of reading and writing.

5. The method of claim 1, where said step (a) comprising reading and writing to said memory array using a 17n algorithm.

6. The method of claim 5, wherein said 17n algorithm is Algorithm B.

7. The method of claim 1, further comprising, prior to said step (a), the step of successively reading and writing to a device for storing said look-up table to test said look-up table storage device.

8. The method of claim 1, wherein said components are cells.

9. The method of claim 8, wherein spare cells are arranged in spare columns of the same length as main columns, and said spare columns are provided in a selected number of spare blocks, each addressed by a single multiplexor.

10. The method of claim 9, further comprising the step of determining, after a faulty cell is detected and its address located, whether there are more faults in the row of said faulty cell than the number of address blocks.

11. The method of claim 10, further comprising the step of determining, whether there are any available spare addresses that may correspond to the address of the faulty cell.

12. The method of claim 11, further comprising the step of, if a spare is available, incrementing a counter so that the next required spare is on a different multiplexor.

13. Apparatus for determining the location of faulty components in a computer memory array on a chip and for providing a software repair procedure, comprising: in the memory array, and, based on data read from said memory array, determining the location of faulty components in said array; said test apparatus being adapted to, if a faulty component is detected, determine whether a spare component in a spare memory array on the chip is available, and for designating a spare component to correspond to the faulty component; and representing the location of the faulty component associated with information representing the location of the corresponding spare component designated by said memory test apparatus.