CN107122256B - The high-performance on piece caching fault-tolerant architecture of dynamic repairing - Google Patents

Abstract

The patent of the present invention proposes a dynamically patched high-performance on-chip cache fault-tolerant structure, which can deal with intermittent bit failures and permanent failures in a timely, efficient, and low-cost manner. Through a fault-sensitive replacement mechanism, new faults can be tolerated at any time to ensure the normal operation of the cache, and then according to the status of the cache block being accessed, the faulty sub-block can be dynamically repaired to reduce the performance impact of the fault on the cache.

Description

Dynamically patched high-performance on-chip cache fault-tolerant architecture

Technical field

The patent of the present invention relates to a cache fault-tolerant architecture for repairing intermittent and permanent errors, especially a high-performance on-chip cache fault-tolerant architecture that can be dynamically repaired.

Background technique

Not only the permanent faults caused by missed detection and wear and aging will affect the reliability of the chips after leaving the factory, but also the gaps that are difficult to detect before leaving the factory, occur randomly in time, have a fixed position, last for a certain period, but are recoverable Bit failure also has a serious impact on the reliability of the chip after leaving the factory. Efficient error correction for transient faults Error detection codes also face the problem of high delay overhead when dealing with intermittent bit failures, and will weaken the handling of transient faults, causing multi-bit faults. Some cache architectures currently proposed to deal with permanent faults, such as sub-block disabling schemes, conflict-free repair schemes, etc., are all based on static bypass or replacement methods, which need to handle faults when the system is started or the voltage frequency is adjusted. These methods are not processed in time, and cannot effectively deal with intermittent bit failures that occur randomly in time.

Contents of the invention

This patent proposes a dynamically patched high-performance on-chip cache fault-tolerant architecture, which can handle intermittent bit failures and permanent failures in a timely, efficient, and low-overhead manner. Through a fault-sensitive replacement mechanism, new faults can be tolerated at any time to ensure the normal operation of the cache, and then according to the status of the cache block being accessed, the faulty sub-block can be dynamically repaired to reduce the performance impact of the fault on the cache.

This cache structure, as shown in Figure 1, has the following characteristics:

In this cache line structure, a cache block contains several sub-blocks. The structure of the cache block mainly includes the sub-block failure field, whether the cache block is disabled, the sub-block offset adjustment counter field, and the pointer field pointing to the repair array, indicating whether the data has been modified. Domain, the domain that maintains the replacement state, and a label that identifies the domain. The actual mapped sub-block offset is obtained by adding the sub-block offset and the intra-block offset.

1. Marking bit: indicates the label of the cache block.

2. Sub-block fault bitmap field: Indicates the sub-block fault status of each cache block, including several bits, corresponding to several sub-blocks, if the sub-block is a faulty sub-block, set this bit to distinguish it from a normal sub-block. The modified field is filled at the initial stage of the system, and updated when the voltage frequency is dynamically adjusted. It can be updated in time according to the result of the parity check. If bit faults are found continuously for many times, it can be considered that intermittent bit failures have occurred, so that the SFM field can be modified in time.

3. Whether the cache is disabled field: Indicates whether the cache block is disabled. If there is no continuous fault-free sub-block in a cache block, the cache block is disabled, and the value of this field is set to distinguish it from normal availability.

4. Whether the data is modified field: Indicates whether the data is modified, if modified, modify the field, otherwise it remains unchanged.

5. Sub-block offset adjustment field: used to adjust the actual mapping offset position of the sub-block. Its size can represent the number of sub-blocks

6. Pointer field to patch array: used to point to patch array

7. Replacement flag: record the situation of replacement

The present invention proposes a fault sensitive mechanism algorithm, which is divided into two cases of true hit and false hit, as shown in Fig. 2 and Fig. 3 respectively:

When a true hit occurs:

Step 1: Select the cache block v at the bottom of the replacement stack as the removal block, the cache request is R, and a certain block Sblock(R) is k.

Step 2: Judgment ((k+counter C(v))MOD SN) sub-block is fault-free, i.e. B(v)[(k+C(v))MODSN] numerical check, if there is no fault then go to step 3. If there is a fault, go to step 4

Step 3: The value of the counter C remains unchanged. Skip to step 5.

Step 4: Adjust the counter C of the cache block, stop the adjustment when the value of SFM(v)[(k+NewC(v))MOD SN] indicates no fault, and set the counter value to NewC.

Step 5: The requested data can be placed into a non-faulty subblock of cache block v. The promotion strategy similar to LRU adjusts the replacement state of the cache block in the stack, and the cache block v is promoted to the top of the stack.

When a false hit occurs:

Step 1: Select the cache block fv at the bottom of the replacement stack as the removal block

Step 2: judge whether fv contains expansion data, and if so, write back. Go to step 3 when done

Step 3: Adjust the counter value of fv such that the B(fv)[RSblockfv(R)] value represents a no-fault state

Step 4: Carry out missing case processing.

Step 5: According to the promotion strategy, promote fv to the top of the stack, and update the order of other cache lines in the stack in turn.

The fault-tolerant cache architecture of this cache structure, its overall architecture is shown in Figure 7:

The contents indicated by the reference numerals in the figure are: 1. Flag identification, 2. Sub-block fault bitmap field, 3. Whether to disable the cache field, 4. Whether to modify the data field, 5. The sub-block offset adjustment count field is currently 000 , 6. The pointer field pointing to the repair array is currently 000101, 7. Replacement status bit, 8. Partition identification, 00 is a free unit, 01 is a start unit, 10 is an intermediate unit, and 11 is an end unit.

In the tag field of the cache block, the pointer field to the patch array stores the first address of the patch unit. The repair unit is provided by an array, which is an independently addressable single module, which contains several units. Each unit is mainly composed of two parts, the flag field and the data field, and the flag field part contains several bits. Combination means that (1) the unit is free and is not allocated to repair the faulty sub-block. (2) Indicates that the unit is the start unit of the patch section. (3) Indicates that this unit is the end unit of the repair section. (4) indicates that the unit is a repair constituent unit. All faulty sub-blocks of a cache block are repaired, because the cache blocks that are considered worthy of repair are all cache blocks with relatively high reuse. Moreover, the repair unit for repairing a cache block is continuously allocated in the array at one time, forming a repair section. The flag field of the start unit of the patch section is assigned a value to indicate case (1), the flag field of an end unit is assigned a value of case (3), and the flag field of an intermediate unit is assigned a value of case (4).

The present invention provides a dynamic repair mechanism process, which is divided into false hits, true hits and missing three situations, as shown in Figure 4, Figure 5, and Figure 6 respectively:

On a false hit:

Assume that the false-miss cache block is fv, and the number of its faulty sub-blocks is k.

Step 1: Check if there are k consecutive free cells in this special array, if not, the program ends. Otherwise go to step 2

Step 2: Adjust the counter to ensure that the newly requested data is placed in the fault-free sub-block of the cache block fv. If k continuous free units are found, then these k continuous free units form a patch section, and then store the start address of the patch section into a field of the cache block fv (assumed to be A), and set the patch section respectively Flag fields for individual cells.

Step 3: reload the data from the backup storage, part of the data is placed in the non-faulty sub-block of the cache block fv, and the other part of the data is placed in the repair unit in turn through the pointer of the A domain, and the order is according to the partiality of the faulty sub-block Arrange from small to large.

On true hit:

Suppose the hit cache block is v.

Step 1: Assemble the requested data according to the value of a field (assumed to be A). Check whether there is a corresponding repair unit in the cache block, if so, it means that the requested data is stored in the non-faulty sub-block of the cache block v. If not, it means that there is a corresponding repair unit in the cache block, and the starting address of the repair unit is recorded in the A field. According to the value of the A field, the corresponding repair unit can be directly addressed and accessed according to the mark in the flag field. Quickly find all patched units at once.

2. Part of the data is read from the fault-free sub-block of the cache block v, and part of the data is directly read from the repair unit and placed in the built-in register, and then assembled according to the value of a certain field (assumed to be B) and the value of the counter , forming a complete data block.

When missing:

Step 1. According to the value of a certain field (assumed to be B) and the value of the counter, the requested data is placed in the fault-free sub-block of the cache block.

Step 2. When a cache block is selected as a sacrifice cache block by the sensitive mechanism algorithm, if the cache block has been modified, it needs to be written back first. Check the value of a field (assumed to be A), if there is a repair unit marked, then after writing back, the corresponding repair unit needs to be reclaimed, that is, the flag fields of these units are set to an idle state.

The beneficial effect of the present invention is that the delay overhead is low, and the impact on the average hit access time and cache performance is small. In the face of different bit failure rates, the fluctuation of performance is small, and it can also work efficiently under a higher failure probability to ensure stable performance. The special array only needs 0.26KB to 0.5KB of storage space, which can effectively repair the 32KB L1 cache when the bit failure rate reaches 0.01, and compared with the non-faulty cache, the performance drops within 1%, so that the L1 cache can be as low as Work efficiently with a supply voltage of 400 millivolts.

Description of drawings

FIG. 1 is a structural diagram of a cache block tag field of the present cache structure.

Figure 2 is the algorithm flow chart when a false hit occurs in the fault sensitive mechanism algorithm

Figure 3 is the algorithm flow chart of the fault-sensitive mechanism algorithm when a true hit occurs

Figure 4 is the algorithm flow chart when a false hit occurs during the dynamic repair mechanism process

Figure 5 is the algorithm flow chart when a true hit occurs in the process of dynamic patching mechanism

Figure 6 is the algorithm flow chart when the dynamic repair mechanism process is missing

Figure 7 is a schematic diagram of the fault-tolerant cache architecture of this cache structure

Figure 8 is a schematic diagram of the contents of the initial cache line of the cache structure, the reliability state identifier Line-Status of the cache line, and the value of the corresponding counter

Detailed ways

The following example specifically illustrates the sensitive mechanism algorithm:

Suppose an ordinary cache group with an associativity of 4 in the L1 cache, that is, a cache group contains four cache lines, the contents of the initial cache line, the reliability status indicator Line-Status of the cache line, and the corresponding counter values are shown in the figure 8. Each cache line is composed of a tag part and a data part. The tag part includes a flag flag bit, a subblock fault bitmap field, a cache disabled field, a data modified field, a subblock offset adjustment field, and a pointer field to a repair array. , to replace the flag bit, the data part uses 8-byte continuous space as a sub-block, and a cache group contains 8 sub-blocks. The content of the initial cache line is that the 3rd and 5th sub-blocks of the first cache line are faulty, the 5th and 6th sub-blocks of the second cache line are faulty, the 3rd sub-block of the third cache line is faulty, and the fourth cache line is faulty. Subblocks 3, 7, and 8 of the row are faulty. The corresponding counter values are 001 in the first row, 010 in the second row, 000 in the third row, and 001 in the fourth row. Let field a be the third subblock of the fourth cache line, field b be the fifth subblock of the second cache line, field c be the sixth subblock of the third cache line, and field d be the third subblock of the first cache line Sub-block, e field is the fourth sub-block of the second cache line. The SFM field values corresponding to each cache line are 00101000, 00001100, 00100000 and 00100001 respectively. When a cache request R1 occurs, data g is requested, and the request is missing. Assume that the offset of the sub-block mapped to the cache line from the request address is 7, first look for a candidate removal block, and the algorithm will choose to replace the cache line L4 at the bottom of the stack. If Line4 contains bloated data, write back to Line4. Since the B field (L4)[7] and B field (L4)[8] are both equal to 1, it is a faulty sub-block. Therefore, the counter of the cache line L4 is set to 2, according to the formula , a block of RSblock(R) is equal to (7+2)MOD 8, which is equal to 1, the requested data g is actually stored in the sub-block with an offset of 1, and then Line4 is promoted to the top of the stack according to the promotion strategy, and other caches in the stack Rows are sequentially updated in their order. Next, when cache request R2 occurs, data e is requested, and data e has been placed in Line3 along with requested data b, but data e is placed in the faulty sub-block, so when data e is requested, a false hit. The algorithm treats a false hit as a miss, and the candidate eviction block selects the cache line where the false hit occurred. However, directly reloading the data block into the cache line will cause the requested valid data to be placed in the faulty sub-block, so the counter of the cache line needs to be adjusted first. For cache line Line3, since Sblock(e) is equal to 4 and SFM(L3)[4] is equal to "0", the counter can be set to 0 so that RSblock(e) is equal to 4, and data e is placed in the non-faulty sub-block middle. For the update of the replacement state after the false hit, according to the up strategy, the replacement state of all cache lines remains unchanged.

When cache request R3 arrives, data b is requested again, but cache request R2 causes 80 false hits, so that cache line Line3 is loaded again, and the counter is adjusted so that data b is placed in the faulty sub-block, so data b is requested Also resulted in false hits. The algorithm's processing of request R3 will cause the counter to be set to 1 again, data b can be accessed, and data e is placed in the faulty sub-block. Therefore, accessing data e and accessing data b causes frequent false hits in the cache block Line3, and the data block Line3 is repeatedly loaded into the L1 cache, resulting in thrashing of false hits.

Claims (3)

1. a high-performance on-chip cache fault-tolerant framework of dynamic patching, is characterized in that: a cache block comprises several sub-blocks, and the structure of the cache block has newly increased domain, and described sub-block and described domain comprise: (1) a flag marking bit, used to represent the label of the cache block; (2) Sub-block failure bitmap domain, used to indicate the sub-block failure status of each cache block, including several bits, corresponding to several sub-blocks, if the sub-block is a faulty sub-block, then this bit is set to be consistent with the normal sub-block To distinguish, this field is filled at the initial stage of the system, updated when the voltage frequency is dynamically adjusted, and can be updated in time according to the result of the parity check. If bit failures are found continuously for many times, it can be considered that intermittent bit failures have occurred, so as to modify the described subblock fault bitmap field; (3) Whether the cache is disabled field is used to indicate whether the cache block is disabled. If there is no continuous non-faulty sub-block in a cache block, the cache block is disabled, and the value of this field is set to be normal and available. distinguish; (4) Whether the data is modified field is used to indicate whether the data is modified, if modified, the field is modified, otherwise it remains unchanged; (5) The sub-block offset adjustment field is used to adjust the actual mapping offset position of the sub-block, and its size can indicate the number of sub-blocks; (6) A pointer field pointing to the patching array, used to point to the patching array; and (7) Replacement flag, used to record the situation of replacement; The actual mapped sub-block offset is obtained by adding the sub-block offset and the intra-block offset. 2. the high-performance on-chip cache fault-tolerant architecture of a kind of dynamic repair according to claim 1, is characterized in that: described architecture is through a fault-sensitive replacement mechanism, tolerates the fault that takes place newly at any time, guarantees cache normal operation, and described The fault-sensitive replacement mechanism is based on the least recently used (Least Recently Used: LRU) replacement algorithm, considering data reuse and sub-block failure status, and adjusting the counter of the cache block according to the new cache fault-tolerant architecture, so that the requested data can be placed In the fault-free sub-block, the replacement algorithm is divided into two cases of true hit and false hit: (1) When a true hit occurs, the steps of the replacement algorithm include: Step 1: Select the cache block v at the bottom of the replacement stack as the removal block, the cache request is R, and a block Sblock(R) is k; Step 2: Judging that the sub-block of ((k+counter C(v))MOD SN) is fault-free, that is, check the value of B(v)[(k+C(v))MOD SN], if there is no fault, go to Step 3, if there is a fault, go to step 4; Step 3: The value of counter C remains unchanged, skip to step 5; Step 4: Adjust the counter C of the cache block, stop the adjustment when the value of SFM(v)[(k+NewC(v))MOD SN] indicates no fault, and set the counter value to NewC; Step 5: The requested data is placed in the fault-free sub-block of the cache block v, and the promotion strategy similar to LRU is used to adjust the replacement state of the cache block in the stack, and the cache block v is promoted to the top of the stack; (2) When a false hit occurs, the replacement algorithm steps include: Step 1: Select the cache block fv at the bottom of the replacement stack as the removal block; Step 2: Determine whether fv contains dirty data, if so, write back, and go to step 3 after completion; Step 3: adjust the counter value of fv, so that the value of B(fv)[RSblockfv(R)] represents a no-fault state; Step 4: Carry out missing situation processing; Step 5: According to the promotion policy, promote fv to the top of the stack, and update the order of other cache lines in the stack in turn. 3. the high-performance on-chip cache fault-tolerant framework of a kind of dynamic repair according to claim 2, is characterized in that: described dynamic repair fault sub-block is for the cache block of faulty sub-block, finds continuous The space uses a domain A and a domain B in the cache fault-tolerant architecture of this cache structure to replace the faulty sub-block, and releases the replacement block of the repair space after the cache block is used. The process of dynamically repairing the faulty sub-block Divided into false hits, true hits and missing three cases, respectively: (1) When a false hit occurs, the step of dynamically repairing the faulty sub-block comprises: Assume that the cache block where the false miss occurs is fv, and the number of its faulty sub-blocks is k; Step 1: Check if there are k consecutive free cells in this special array, if not, the program ends, otherwise go to step 2; Step 2: Adjust the counter to ensure that the newly requested data is placed in the fault-free sub-block of the cache block fv. If k consecutive free units are found, the k consecutive free units form a repair section, and then the repair section's The start address is stored in field A of the cache block fv, and the flag field of each unit of the repair section is set respectively; Step 3: Reload the data from the backup storage, part of the data is placed in the non-faulty sub-block of the cache block fv, and the other part of the data is placed in the repair unit in turn through the pointer of the domain A, and the order is according to the partiality of the faulty sub-block Move from small to large; (2) When a true hit occurs, the steps of dynamically repairing the faulty sub-block include: Suppose the hit cache block is v; Step 1: Assemble the requested data according to the value of field A, and check whether there is a corresponding repair unit in the cache block. If so, it means that the requested data is stored in the non-faulty sub-block of cache block v; if not, then it means There is a corresponding repair unit in the cache block, and the starting address of the repair unit is recorded in field A. According to the value of field A, directly address and access the corresponding repair unit, and quickly find all repair unit; Step 2: Read a part of data from the fault-free sub-block of the cache block v, read a part of the data directly from the repair unit and put it into the built-in register, and then assemble it according to the value of domain B and the value of the counter to form a complete data block; (3) When missing occurs, the step of dynamically repairing the faulty sub-block includes: Step 1: According to the value of field B and the value of the counter, the requested data is placed in the non-faulty sub-block of the cache block; Step 2: When a cache block is selected as a victim cache block by the replacement algorithm of the fault-sensitive replacement mechanism, if the cache block has been modified, it needs to be written back first, check the value of field A, if it is marked as repaired Units, after writing back, the corresponding patched units are reclaimed, that is, the flag fields of these units are set to an idle state.