Built-in self test circuit for testing cache tag array and compare logic

[0001] The present invention is generally directed to a cache memory and, in particular, to a BIST circuit for testing the tag array and comparator logic of a cache memory.

[0002] The complexity of modern electronics, particularly data processors, has increased the likelihood of a manufacturing defect occurring in an integrated circuit (IC) chip. To increase the reliability of integrated circuits and to detect faulty ICs more rapidly, chip manufacturers commonly to incorporate built-in self-test (BIST) circuitry in many types of complex IC chips. BIST circuits are commonly used for memories, such as static random access memories (SRAM), dynamic random access memories (DRAM), flash RAM, and the like, and particularly cache memories. State-of-the-art chip level BIST circuitry uses a dedicated hardware controller to execute the BIST testing and to report the pass or fail result to an external device. BIST tests may be automatically generated for a given block of logic.

[0003] A BIST circuit for a cache memory typically performs some type of repetitive testing on the tag array of the cache memory. For example, a conventional BIST circuit may test one location in a tag array by “marching” Logic 1 values, Logic 0 values, and checkerboard patterns into the entry. In this type of testing, for example, Logic 1 values are shifted (i.e., “marched”) into the tag array one bit position at a time until the entire location is filled with Logic 1 values. The contents of the tag array location are tested and verified after each Logic 1 is shifted in. This procedure is repeated for Logic 0 values and for a checkerboard pattern (i.e., alternating Logic 1 and Logic 0 values). After these tests are complete, the entire test cycle is repeated for each of the remaining tag array locations.

[0004] However, while the above-described testing procedure thoroughly tests the tag array logic, conventional BIST circuits for testing cache memories fail to adequately test the remaining portions of the cache memory. Most notably, the comparator logic that determines cache hits and cache misses is not tested by conventional BIST circuitry.

[0005] Therefore, there is a need in the art for improved BIST circuitry for testing the cache memories of data processors and other large-scale integrated circuit (IC) chips. In particular, there is a need for BIST circuitry that adequately tests the comparator logic circuitry of a cache memory.

[0006] To address the above-discussed deficiencies of the prior art, it is a primary object of the present invention to provide a cache memory containing a BIST circuit capable of testing the operation of the tag array comparator circuitry. According to an advantageous embodiment of the present invention, the cache memory comprising: 1) a tag array comprising a plurality of tag entry locations, each of the tag entry locations capable of being accessed by R of the M least significant bits of an N-bit received address and capable storing an address tag comprising the (N-M) most significant bits of the N-bit received address; 2) cache hit comparison circuitry capable of comparing the (N-M) most significant bits of an N-bit received address with an address tag accessed by R of the M least significant bits of the is N-bit received address and generating a HIT signal if a match occurs; and 3) tag array test circuitry capable of testing the operation of the tag array and the cache hit comparison circuitry.

[0007] According to one embodiment of the present invention, the tag array test circuitry is capable of storing a copy of the last data written to the tag array.

[0008] According to another embodiment of the present invention, the tag array test circuitry is capable of storing a copy of the last data read from the tag array.

[0009] According to still another embodiment of the present invention, the tag array test circuitry is capable of storing an address of a tag entry location to which data was last written.

[0010] According to yet another embodiment of the present invention, the tag array test circuitry is capable of determining if R of the M least significant bits of a current received address are equal to R of the M least significant bits of the stored address of the tag entry location to which data was last written.

[0011] According to a further embodiment of the present invention, the tag array test circuitry, in response to a determination that R of the M least significant bits of a current received address are equal to R of the M least significant bits of the stored address of the tag entry location to which data was last written, is further capable of comparing the stored copy of the last data written to the tag array with data retrieved from the tag array at the current received address.

[0012] According to a still further embodiment of the present invention, the tag array test circuitry compares the stored copy of the last data written to the tag array with the data retrieved from the tag array at the current received address by determining if the HIT signal is enabled.

[0013] According to a yet further embodiment of the present invention, the tag array test circuitry, in response to a determination that R of the M least significant bits of a current received address are equal to R of the M least significant bits of the stored address of the tag entry location to which data was last written, is further capable of comparing the stored copy of the last data read from the tag array at the current received address with current data read from the tag array at the current received address.

[0014] According to still another embodiment of the present invention, the tag array test circuitry compares the stored copy of the last data read from the tag array at the current received address with the current data read from the tag array at the current received address by determining if the HIT signal is enabled.

[0015] The foregoing has outlined rather broadly the features and technical advantages of the present invention so that those skilled in the art may better understand the detailed description of the invention that follows. Additional features and advantages of the invention will be described hereinafter that form the subject of the claims of the invention. Those skilled in the art should appreciate that they may readily use the conception and the specific embodiment disclosed as a basis for modifying or designing other structures for carrying out the same purposes of the present invention. Those skilled in the art should also realize that such equivalent constructions do not depart from the spirit and scope of the invention in its broadest form.

[0016] Before undertaking the DETAILED DESCRIPTION OF THE INVENTION below, it may be advantageous to set forth definitions of certain words and phrases used throughout this patent document: the terms “include” and “comprise,” as well as derivatives thereof, mean inclusion without limitation; the term “or,” is inclusive, meaning and/or; the phrases “associated with” and “associated therewith,” as well as derivatives thereof, may mean to include, be included within, interconnect with, contain, be contained within, connect to or with, couple to or with, be communicable with, cooperate with, interleave, juxtapose, be proximate to, be bound to or with, have, have a property of, or the like; and the term “controller” means any device, system or part thereof that controls at least one operation, such a device may be implemented in hardware, firmware or software, or some combination of at least two of the same. It should be noted that the functionality associated with any particular controller may be centralized or distributed, whether locally or remotely. Definitions for certain words and phrases are provided throughout this patent document, those of ordinary skill in the art should understand that in many, if not most instances, such definitions apply to prior, as well as future uses of such defined words and phrases.

[0022] FIGS. 1 through 4, discussed below, and the various embodiments used to describe the principles of the present invention in this patent document are by way of illustration only and should not be construed in any way to limit the scope of the invention. Those skilled in the art will understand that the principles of the present invention may be implemented in any suitably arranged cache memory.

[0023] FIG. 1 illustrates selected portions of exemplary data processor 100, which comprises a cache memory containing a built-in self-test (BIST) circuit according to the principles of the present invention. Data processor 100 comprises memory management unit (MMU) 110, processor core 120, cache unit 130, and bus interface unit 140. MMU 110 contains Level 1 translation look-aside buffer (L1 TLB) 115. Processor core 120 comprises register set 122, integer unit 124, and floating point unit (FPU) 126. Cache unit 130 comprises instruction cache 132 and data cache 134. It should be understood that other forms of data processor 100 may be utilized and other modifications can be made without departing from the scope and spirit of the present invention.

[0024] According to an exemplary embodiment or the present invention, integer unit 124 in processor core 120 is a super-pipelined integer unit. Instruction cache 132 stores the most recently used instruction codes and data cache 134 stores the most recently used data. In alternate embodiment of the present invention, MMU 110 may comprise two translation look-aside buffers (TLBs), including an L1 TLB that may be direct mapped and a Level 2 (L2) TLB that may be n-way associative.

[0025] MMU 110 translates linear (or logical) addresses supplied by instruction unit 124 in processor core 120 into physical addresses (including addresses based on paging) for use by cache unit 130 and for transmission through BIU 140. Memory management procedures are preferably ×86 compatible, adhering to standard paging mechanisms. Bus interface unit (BIU) 140 provides the main bus interface to memory (not shown). During a memory cycle, a memory location is selected through the Address lines and data is passed to/from memory through the Data lines.

[0026] Processor core 120 requests instructions from cache unit 130. The processing pipeline in pipelined integer unit 124 decodes the received integer instructions. If an instruction is a multimedia extension or FPU instruction, the instruction is passed to FPU 126 for processing. As required, data is fetched from data cache 134. If the requested data is not in data cache 134, the data is accessed via BIU 140 from either an L2 cache (not shown) or system memory (not shown).

[0027] According to an exemplary embodiment of data processor 100, built-in self-test (BIST) circuits may be used to test and validate the operation of instruction cache 132 or data cache 134, or both. In accordance with the principles of the present invention, the BIST circuits perform repetitive testing of the tag arrays and the comparator circuitry of instruction cache 132 and data cache 134.

[0028] FIG. 2 illustrates selected portions of data cache 134, which contains a built-in self-test (BIST) circuit (shown in FIG. 3) according to the principles of the present invention. Those skilled in the art will appreciate that the description of data cache 134 that follows also applies to instruction cache 132, or any other type of cache memory (e.g., a Level 2 cache) that may be used in conjunction with data processor 100.

[0029] Data cache 134 comprises tag array 210, multiplexer (MUX) 220 and comparator 230. Those skilled in the art will understand that FIG. 2 illustrates only those portions of data cache 134 that are necessary to an understanding of the present invention and omits other portions that are not related to the present invention. For instance, FIG. 2 does not depict the data array of data cache 134, or other related circuitry. Also, the illustrated embodiment of data cache 134 contains only one tag array 210. Those skilled in the art will recognize that in an associative cache comprising N ways (e.g., 6 way cache), data cache 134 contains more than one tag array 134. However, illustrating and describing the testing of additional tag arrays and comparator logic would be highly repetitive and is unnecessary. It is sufficient to illustrate and describe the operation of the present invention with respect to only a single tag array 210.

[0030] In the illustrated embodiment, tag array 210 contains 128 entries, including exemplary tag entry 211 (i.e., Tag Entry 0), tag entry 212 (i.e., Tag Entry 1), tag entry 213 (i.e., Tag Entry 2) and tag entry 214 (i.e., Tag Entry 127). Each entry contains a valid bit (Vx) and a 20-bit tag value (TAGxx[31:12]).

[0031] For example, Tag Entry 0 comprises valid bit V0 and tag value TAG0[31:12], Tag Entry 1 comprises valid bit V1 and tag value TAG1[31:12], Tag Entry 2 comprises valid bit V2 and tag value TAG2[31:12], and Tag Entry 127 comprises valid bit V127 and tag value TAG127[31:12]. In alternate representation, the 20 bits in tag value TAGxx[31:12] may be represented as TAGxx[19:0].

[0032] As is well known, the lower order bits (e.g., ADDR[11:5]) of an address are used to access the upper bits (e.g., ADDR[31:12] of an address previously stored in a cache memory via MUX 220. To determine if the cache contains the data for a particular address, the tag array is checked for a matching tag entry. The lower part of the compare address, ADDR[11:5], is used to index into tag array 210 and MUX 220 selects one of the 128 tag entries. Comparator 230 compares the contents of the selected tag entry (i.e., Vx and TAGxx[31:12]) to V(IN)=1 and the upper bits of the compare address, ADDR[31:12]. If there is a match, comparator 230 enables the HIT signal (i.e., sets Hit to Logic 1). In other words, if the value of address bits [31:12] is xxx (decimal), where xxx is 000 to 128, then:
HIT=({VIN, ADDR[31:12]}={Vxx, TAGxx[31:12]})

[0033] FIG. 3 illustrates an exemplary built-in self-test (BIST) circuit for testing data cache 134 according to one embodiment of the present invention. The BIST circuit comprises register 310, register 320, multiplexer (MUX) 330, array BIST circuit 340 and compare logic BIST circuit 350. According to an exemplary embodiment, BIST circuit 340 and compare logic BIST circuit 350 may comprise well-known types of microcontrollers, state machines, application specific integrated circuit (ASIC) devices, or the like, or combinations of two or more of such well-known circuits.

[0034] As FIG. 3 illustrates, registers 310 and 320 temporarily store data entering the inputs and exiting the outputs of tag array 210. In Normal mode, MUX 330 is selected such that the Normal Control signals are applied to register 310 and the inputs of tag array 210. However, in Test mode, MUX 330 is selected such that array BIST circuit 340 and compare logic BIST circuit 350 control tag array 210.

[0035] The control and data input signals of tag array 210 are the Read, Write and Compare control signals, upper address bits ADDR[31:12], lower address bits ADDR[11:5], valid bit V(IN), and a Clock signal. The control and data output signals of tag array 210 are the Hit signal, the Valid Out signal, and tag bits TAG OUT[31:12].

[0036] The control and data input signals of array BIST circuit 340 are the Start signal, the Valid Out signal, and tag bits TAG OUT[31:12]. The control and data output signals of array BIST circuit 340 are the Read, Write, Done and Fail control signals, control bits BIST State[1:0], address bits ADDR[31:12], address bits ADDR[11:5], and valid bit V(IN).

[0037] The control and data input signals of compare logic BIST circuit 350 are the Read, Write, Hit and Start control signals, the Valid Out signal, tag bits TAG OUT[31:12], control bits BIST State[1:0], address bits ADDR IN[31:12], address bits ADDR IN[11:5], and valid bit V(IN). The control and data output signals of compare logic BIST circuit 350 are the Compare and Fail control signals, address bits ADDR OUT[31:12], and valid bit V(OUT).

[0038] To test tag array 210, array BIST circuit 340 and compare logic BIST circuit 350 read and write various patterns to each location in tag array 210 according to well-known testing principles. These patterns are walking checkerboards (i.e., 1010 . . . 1010), walking inverted checkerboards (i.e., 0101 . . . 0101), walking ones (i.e., 1111 . . . 1111) and walking zeros (i.e., 0000 . . . 0000). It should be noted that during Test mode, the valid bits in tag array 210 are treated as just another data bit as patterns are written into and read from tag array 210.

[0039] During Test mode, the COMPARE control input is set to 0. This setting prevents tag array 210 from enabling comparator 230 and generating a HIT signal. It should be noted that a tag compare operation may be done in parallel with a tag array read operation.

[0040] FIG. 4 illustrates selected portions of compare logic built-in self-test (BIST) circuit 350 in greater detail according to an exemplary embodiment of the present invention. Compare logic BIST circuit 350 comprises control state machine 410, Last Write Address register 420, comparator 430, Last Write Data register 440, Last Read Data register 450, and multiplexer (MUX) 460.

[0041] Control state machine 410 is a state machine that receives the Read, Write, Hit and Start control signals, and the control bits BIST State[1:0] from external sources. Control state machine 410 also receives the ADDR EQ signal from comparator 430. From these inputs control state machine 410 generates the Fail and Compare control signals.

[0042] The address bits ADDR IN[11:5] are inputs to Last Write Address register 420 and to one input channel of comparator 430. The other input channel of comparator 430 receives the last-written address bits ADDR IN[11:5] from Last Write Address register 420. Comparator 430 enables the ADDR EQ signal if the current value of ADDR IN[11:5] is equal to the last written value of ADDR IN[11:5] stored in Last Write Address 420.

[0043] The address bits ADDR IN[31:12] are inputs to Last Write Data register 440 and to one input channel of MUX 460. A second input channel of MUX 460 receives the last-written data bits ADDR IN[31:12] from Last Write Data register 430. The Valid Out control signal and the data bits TAG OUT[31:12] are inputs to Last Read Data register 450. A third input channel of MUX 460 receives the last-read value of the Valid Out signal and the last read data bits TAG OUT[31:12] from Last Read Data register 450.

[0044] During Test mode, when various test patterns are written and read from tag array 210, control state machine 410 keeps track of what was last written and last read from a tag entry in tag array 210 and applies the appropriate values for VIN, ADDR[31:12], and the Compare signal to tag array 210 to generate a tag comparison. Based on which pattern tests are currently being done, compare logic BIST circuit 350 expects HIT to be a 1 or 0, accordingly.

[0045] The control bits BIST State[1:0] indicate which test patterns are being used in testing tag array 210. According to an exemplary embodiment of the present invention, BIST State[1:0] control bits may have the following meanings:

[0046]

BIST State [1:0]	Test Pattern
00	Marching Checker Board
01	Marching Inverted Checker Board
10	Marching Ones
11	Marching Zeros

[0047] During the testing of tag array 210, marching patterns are written and read to each tag entry location in tag array 210. For each tag entry in tag array 210, multiple writes and reads are performed until the marching pattern has filled the tag entry.

[0048] During the Marching Checker Board patterns, the last written address and the last written data are saved in Last Write Address register 420 and Last Write Data register 440, respectively. When a read operation is done, the address of the read (i.e., ADDR IN[11:5] is compared to the last write address (i.e., ADDR IN[11:5] stored in Last Write Address register 420) by comparator 430 and if they are equal (i.e., ADDR EQ is enabled), the last written data stored in Last Write Data 440 (i.e., V(IN) and ADDR IN[31:12] are output at VOUT and ADDR OUT[31:12] via MUX 460 and are applied to tag array 210 for comparison to the contents of tag array 210. In this situation, a HIT=1 is expected.

[0049] During the Marching Ones or Zeroes patterns, the last read data and the last write address are saved in Last Read Data register 450 and Last Write Address register 420. On the next read from the same address as the write operation, the last read data is applied to VOUT and ADDR OUT[31:12] for comparison to the entry in tag array 210. There should only be a 1-bit difference between the last read data and the current read data and, therefore, the HIT output should be 0. Control state machine 410 keeps track of when HIT should be 1 and when HIT should be 0. If the value of HIT is incorrect, then the Fail control signal is enabled.

[0050] Although the present invention has been described with an exemplary embodiment, various changes and modifications may be suggested to one skilled in the art. It is intended that the present invention encompass such changes and modifications as fall within the scope of the appended claims.