TWI534621B - Prefetcher, method of prefetch data, computer program product and microprocessor - Google Patents

Description

Prefetch unit, data prefetching method, computer program product, and microprocessor

The present invention relates to a cache memory for a general microprocessor, and more particularly to a cache memory for prefetching data to a microprocessor.

In the case of recent computer systems, in the case of a cache miss, the microprocessor will access the system memory for one or two more times than the microprocessor accesses the cache. An order of magnitude. Therefore, in order to increase the cache hit rate, the microprocessor integrates prefetching techniques to check for recent recent data access patterns and attempts to predict which data is the next program. Access to objects, and the benefits of prefetching are well known.

However, Applicants have noted that the access patterns of certain programs are not detectable by the prefetching units of conventional microprocessors. For example, Figure 1 shows the access mode of the second-level cache memory (L2 Cache) when the executed program includes a sequence of storage operations via memory, and the time depicted in the figure is the time The memory address. As can be seen from Fig. 1, although the general trend is to increase the memory address over time, that is, from the upward direction, in many cases, the specified access memory address can be lower than the previous time. Non-total trend, Make it different from the actual predicted results of the conventional prefetch unit.

Although the overall trend is moving in one direction for a relatively large number of samples, there are two reasons why a conventional prefetch unit may be in a chaotic situation when faced with a small sample. The first reason is that the program accesses the memory according to its architecture, whether it is caused by algorithmic features or poor programming. The second reason is that when the pipelines and queues of the out-of-order microprocessor core are executed under normal functions, the memory access is often performed in a different program order than that generated.

Therefore, a data prefetching unit is required to efficiently perform data prefetching for the program, which must take into account that when a memory access instruction (action) is performed in a small time window (time windows), it does not appear obvious. No clear trend, but there is a clear trend when reviewing with a larger sample size.

The invention discloses a microprocessor comprising a first level cache memory, a second level cache memory and a prefetch unit. The prefetching unit is configured to detect a direction and a state of a recent access request appearing in the second level cache memory, and prefetch the plurality of cache lines to the second level cache according to the direction and the mode. Receiving, from the first-level cache memory, one of the access requirements received by the first-level cache, wherein the address is associated with a cache line, and the cache associated with the direction is determined. One or more cache lines outside the line are indicated by the pattern and cause one or more cache lines to be prefetched into the first level cache.

The invention discloses a data prefetching method for prefetching data to a first level cache memory of a microprocessor having a second level cache memory. The data prefetching method includes detecting a direction and a form of a recent access request appearing in the second level cache memory, and prefetching the plurality of cache lines to the second level according to the direction and the mode. Taking in the memory; receiving, from the first-level cache memory, one of the access requirements received by the first-level cache, wherein the address is associated with a cache line; determining the relevant in the direction One or more cache lines pointed out by the modality outside the cache line; and causing one or more cache lines to be prefetched into the first level cache.

The invention discloses a computer program product encoded on at least one computer readable medium and adapted for use in a computing device, the computer program product comprising a computer readable program code. The computer readable program code is stored in a computer readable medium for defining a microprocessor. The computer readable program includes a first code, a second code, and a third code. The first code is used to define a first level cache device. The second code is used to define a second level cache device. a third code for defining a prefetching unit, wherein the prefetching unit is configured to detect a direction and a state of a recent access request appearing in the second level cache memory, and according to the direction and the mode, Pre-fetching the plurality of cache lines into the second-level cache memory, from the first-level cache memory, receiving one of the access requirements of the first-level cache memory, wherein the address is A cache line associated with one or more cache lines indicated by the aspect other than the cache line associated with the direction, and causing one or more cache lines to be prefetched to the first level cache In memory.

100‧‧‧Microprocessor

102‧‧‧ instruction cache memory

104‧‧‧ instruction decoder

106‧‧‧Scratchpad alias table

108‧‧‧Reservation station

112‧‧‧Execution unit

132‧‧‧Other execution units

134‧‧‧Load/storage unit

124‧‧‧Prefetching unit

114‧‧‧Retirement unit

116‧‧‧First level data cache memory

118‧‧‧Second level cache memory

122‧‧‧ Busbar interface unit

162‧‧‧Virtual Hash Table

198‧‧‧伫

172‧‧‧First-level data search indicator

178‧‧‧First level data sample address

196‧‧‧First level data memory address

194‧‧‧Spse prediction cache line address

192‧‧‧ Cache line configuration requirements

188‧‧‧Cache line information

354‧‧‧Memory Block Virtual Hashing Address Bar

356‧‧‧Status Bar

302‧‧‧ Block Bit Mask Register

303‧‧‧block number register

304‧‧‧Minimum indicator register

306‧‧‧Maximum indicator register

308‧‧‧Minimum change counter

312‧‧‧Maximum change counter

314‧‧‧ total counter

316‧‧‧Intermediate indicator register

318‧‧‧Period matching counter

342‧‧‧ Directional register

344‧‧‧Spread register

346‧‧‧like periodic register

348‧‧‧ modal area register

352‧‧‧Search indicator register

332‧‧‧ hardware unit

322‧‧‧Control logic

328‧‧‧Pre-request requirements queue

324‧‧‧Extraction indicator

326‧‧‧Advance indicator

2002‧‧‧Hatch Virtual Address Library

2102A‧‧‧ Core A

2102B‧‧‧ Core B

2104‧‧‧Highly reactive prefetching unit

2106‧‧‧Shared highly reactive prefetch unit

Figure 1 shows the execution of a sequence of storage operations via memory. In the formula, a schematic diagram of the access state of the second-level cache memory.

Figure 2 is a block diagram of a microprocessor of the present invention.

Figure 3 is a detailed block diagram of the prefetching unit of Figure 2 of the present invention.

Figure 4 is a flow chart showing the operation of the microprocessor of Figure 2 of the present invention and, in particular, the prefetching unit of Figure 3.

Figure 5 is a flow chart showing the operation of the steps of Figure 4 of the prefetching unit of Figure 3 of the present invention.

Figure 6 is a flow chart showing the operation of the steps of Figure 4 of the prefetching unit of Figure 3 of the present invention.

Figure 7 is a flow chart showing the operation of the prefetch request queue of Figure 3 of the present invention.

Figure 8 is a diagram showing two pattern access points of a memory block of the present invention for indicating a bounding box prefetching unit of the present invention.

Figure 9 is a block diagram showing an example of the operation of the microprocessor shown in Figure 2 of the present invention.

Fig. 10 is a block diagram showing an operation example of the microprocessor shown in Fig. 2 of the example of the ninth embodiment of the present invention.

Fig. 11 is a block diagram showing an operation example of the microprocessor shown in Fig. 2 of the example of the ninth and tenth drawings of the present invention.

Figure 12 is a block diagram of a microprocessor in accordance with another embodiment of the present invention.

Figure 13 is a flow chart showing the operation of the prefetching unit shown in Fig. 12 of the present invention.

Figure 14 is a flow chart showing the operation of the prefetch unit shown in Fig. 12 of the step of Fig. 13 of the present invention.

Figure 15 is a block diagram of a microprocessor having a bounding frame prefetching unit in accordance with another embodiment of the present invention.

Figure 16 is a block diagram of a virtual hash table of Figure 15 of the present invention.

Figure 17 is a flow chart showing the operation of the microprocessor of Figure 15 of the present invention.

Figure 18 is a diagram showing the contents of the virtual hash table of Figure 16 of the present invention in accordance with the operation of the prefetch unit as illustrated by the example of Figure 17.

Fig. 19 (collectively, Figs. 19A and 19B) is a flow chart showing the operation of the prefetching unit of Fig. 15 of the present invention.

Figure 20 is a block diagram of a hash entity address to a hash virtual address pool used in the prefetch unit of Figure 15 in accordance with another embodiment of the present invention.

Figure 21 is a block diagram of a multi-core microprocessor of the present invention.

The methods of making and using various embodiments of the present invention are discussed in detail below. However, it is to be noted that many of the possible inventive concepts provided by the present invention can be implemented in various specific ranges. These specific examples are merely illustrative of the methods of making and using the invention, but are not intended to limit the scope of the invention.

Bounding box prefetcher

Broadly speaking, the solution to the above problem can be explained in the following description. When all accesses (instructions, actions, or requirements) of a memory are represented on a single map, a set of all accesses (instructions, actions, or requirements) can be circled by a bounding box. When the additional access requirements are also indicated on the same map, these access requirements can also be rounded and bounded by the bounding box. The first picture in Figure 8 shows two accesses (instructions or actions) to a memory block. The X-axis of Figure 8 indicates the time sequence of instruction access, and the Y-axis indicates access with 4 KB blocks. The index of the 64-bit cache line. First, the first two accesses are depicted: the first access system accesses the cache line 5, and the second access request is fast. Take line 6 for access. The bounding box shown in the figure will circle the two points representing the access requirements.

Furthermore, a third access request occurs on the cache line 7, and the bounding box becomes larger so that a new point representing the third access requirement can be bounded internally. As new accesses continue to occur, the bounding box must expand with the X axis, and the upper edge of the bounding box also expands with the Y axis (this is an upward example). The history of the movement of the upper and lower edges of the bounding box above will be used to determine whether the trend of accessing the state is up, down or not.

In addition to tracking the top and bottom edges of the bounding box to determine a trend direction, it is also necessary to track individual access requirements, as events that require one or two cache lines to skip are frequently encountered. Therefore, in order to avoid prefetching events that may be skipped by the cache line, once an up or down trend is detected, the prefetch unit will use additional criteria to determine the cache line to prefetch. Since the access requirement trends are rearranged, the prefetch unit displays these access history records in a delete time record. This action is performed by a marking bit in a bit mask, each bit corresponding to a cache line of a memory block, and when a particular block is When accessing, the bit of the corresponding bit mask will be set. Once the access requirements for the memory block have reached a sufficient number, the prefetch unit will use a bit mask (where the bit mask does not have an indication of the access time order) and is based on the larger The access point of view (generalized large view) accesses the entire block, rather than making prefetch decisions based only on the time of access, based on a smaller view of the small (small view) and the conventional prefetch unit.

Figure 2 is a block diagram of a microprocessor 100 of the present invention. The microprocessor 100 includes a pipeline having a plurality of levels, and the pipeline also includes Various functional units. The pipeline includes an instruction cache 102, the instruction cache 102 is coupled to an instruction decoder 104; the instruction decoder 104 is coupled to a register alias table (RAT); a register The alias table 106 is coupled to a reservation station 108 (reservation station); the reservation unit 108 is coupled to an execution unit 112; finally, the execution unit 112 is coupled to a retirement unit 114. The instruction decoder 104 can include an instruction translator for translating a macro instruction (e.g., a macro instruction of an x86 architecture) into a macro of a reduced instruction set computer RISC of the microprocessor 100. Set instructions. The reservation station 108 generates and transmits instructions to the execution unit 112 for causing the execution unit 112 to execute in a non-sequential manner. The retirement unit 114 includes a reorder buffer for performing the retirement of the instructions in accordance with the program sequence. The execution unit 112 includes a load/store unit 134 and other execution units 132, such as an integer unit, a floating point unit, a branch unit, or a single instruction multiple data. Single Instruction Multiple Data (SIMD) unit. The load/store unit 134 is configured to read the data of the first level data cache 116 and write the data to the first level data cache 116. A second level cache memory 118 serves as a backup of the first level data cache memory 116 and the instruction cache memory 102. The second level cache memory 118 is used to read and write system memory via a bus interface unit 122. The bus interface unit 122 is a bus 100 and a bus (for example, a local bus). Or an interface between memory buss. The microprocessor 100 also includes a prefetch unit 124 for prefetching data from the system memory to the second level cache 118 and/or The primary data cache memory 116.

Fig. 3 is a detailed block diagram of the prefetch unit 124 of Fig. 2. The prefetch unit 124 includes a block bit mask register 302. Each bit in the block bit mask register 302 corresponds to a cache line of a memory block, wherein the block number of the memory block is stored in a block number register 303. In other words, the block number register 303 stores the upper address bits of the memory block. When the value of one of the bits in the block bit mask register 302 is true (true value), it indicates that the corresponding cache line has been accessed. Initializing the block bit mask register 302 will cause all bit values to be false. In one embodiment, the size of the memory block is 4 KB and the size of the cache line is 64 bytes. Therefore, the block bit mask register 302 has a capacity of 64 bits. In some embodiments, the size of the memory block can also be the same as the size of the physical memory page. However, the size of the cache line can be of various other different sizes in other embodiments. Moreover, the size of the memory area maintained on the block bit mask register 302 is changeable and does not need to correspond to the size of the physical memory page. More specifically, the size of the memory area (or block) maintained on the block bit mask register 302 can be any size (the multiple of two is best) as long as it has enough cache lines. It is good for pre-fetching direction and pattern detection.

The prefetch unit 124 can also include a min pointer register 304 and a max pointer register 306. The minimum indicator register 304 and the maximum indicator register 306 are respectively used to continuously point to the lowest and highest accessed in the memory block after the prefetch unit 124 starts tracking the access of a memory block. Cache index (index). The prefetch unit 124 further includes a minimum change counter 308 and a maximum change counter 312. The minimum change counter 308 and the maximum change counter 312 are respectively used to calculate the number of times the minimum indicator register 304 and the maximum indicator register 306 are changed after the prefetch unit 124 starts tracking the access of the memory block. The prefetch unit 124 also includes a total counter 314 for calculating the total number of cache lines that have been accessed after the prefetch unit 124 begins tracking the access of the memory block. The prefetch unit 124 also includes an intermediate indicator register 316 for pointing to the index of the intermediate prefetch memory line of the memory block after the prefetch unit 124 starts tracking the access of the memory block (eg The count value of the minimum index register 304 and the average of the count values of the maximum change counter 312). The prefetch unit 124 also includes a direction register 342, a state register 344, a state cycle register 346, a state area register 348, and a search index register 352, each of which The function is as follows.

The prefetch unit 124 also includes a period match counter 318 (period match counter). Each cycle match counter 318 maintains a count value for one of the different cycles. In one embodiment, the periods are 3, 4, and 5. The period refers to the number of bits left/right of the intermediate indicator register 316. The count value of the period match counter 318 is updated after each memory access of the block is made. When the block bit mask register 302 indicates that the access to the left of the intermediate indicator register 316 matches the access to the right of the intermediate indicator register 316 during the cycle, the prefetch unit 124 then increments The period associated with this period matches the count value of counter 318. More detailed application and operation of the period matching counter 318 will be described in particular in the fourth and fifth figures below.

The prefetch unit 124 also includes a prefetch request queue 328, an extraction A pointer 324 (pop pointer) and a push pointer 326 (push pointer). The prefetch request queue 328 includes a loop queue having a number of entries, each of which is used to store the operations of the prefetch unit 124 (especially with respect to Figures 4, 6, and 7). Take the request. The push indicator 326 indicates the next assigned entry in the prefetch request queue 328. The extraction indicator 324 indicates that the next item will be removed from the prefetch request queue 328. In an embodiment, because the prefetch request may end in an out of order, the prefetch request queue 328 may populate the completed item in a non-sequential manner. In one embodiment, the size of the prefetch request queue 328 is determined by the number of pipeline pipelines in the pipeline that are intended to enter the second stage cache memory 118, thus The number of items in the prefetch request queue 328 is at least as many as the number of pipelines in the second level cache 118. The prefetch request will be maintained until the end of the second level cache memory 118. At this point in time, the request may be one of three results, as described in more detail in Figure 7, ie hit in second. The level cache memory 118, replay, or advance a fill queue entry to prefetch the required data from the system memory.

Prefetch unit 124 also includes control logic 322 that controls the various components of prefetch unit 124 to perform their functions.

Although FIG. 3 only shows a set of hardware units 332 associated with an active memory block (block bit mask register 302, block number register 303, minimum indicator register) 304, maximum indicator register 306, minimum change counter 308, maximum change counter 312, total counter 314, intermediate indicator register 316, state cycle register 346, sample area register 348, and The search indicator register 352), but the prefetch unit 124 can include a plurality of hardware units 332 as shown in FIG. 3 for tracking access of a plurality of active memory blocks.

In one embodiment, the microprocessor 100 also includes one or more highly reactive prefetch units (not shown) that are highly reactive pre-fetch units in very small time samples. Different algorithms are used for access and cooperate with the prefetch unit 124, as explained below. Since the prefetch unit 124 described herein analyzes the number of larger memory accesses (compared to the highly reactive prefetch unit), it will tend to use a longer time to start prefetching a new memory region. Block (described below), but more accurate than highly reactive prefetch units. Thus, using the highly reactive prefetch unit to operate simultaneously with the prefetch unit 124, the microprocessor 100 can have a faster reaction time for the highly reactive prefetch unit and high precision of the prefetch unit 124. Additionally, prefetch unit 124 can monitor requirements from other prefetch units and use these requirements in its prefetch algorithm.

Figure 4 is a flow chart showing the operation of the microprocessor 100 of Figure 2, and in particular the operation of the prefetch unit 124 of Figure 3. The process begins in step 402.

In step 402, prefetch unit 124 receives a load/store memory access request for accessing a memory address. In one embodiment, the prefetch unit 124 distinguishes between the load memory access request and the memory memory access request when determining which cache lines are prefetched. In other embodiments, the prefetch unit 124 does not discriminate between loading and storing when determining which cache lines are prefetched. In one embodiment, the prefetch unit 124 receives the memory access request output by the load/store unit 134. Prefetch unit 124 can receive memory from different sources Access requirements, such sources include, but are not limited to, load/store unit 134, first level data cache memory 116 (eg, one of the first level data caches 116 generated by the dispatch request, in the load / When the storage unit 134 accesses the first level data cache 116, and/or other sources, for example, the microprocessor 100 performs a different prefetch algorithm from the prefetch unit 124 to prefetch data. Other prefetching units (not shown). The flow proceeds to step 404.

In step 404, the control logic 322 determines whether to access the memory of an active block based on the comparison memory access address and the value of each block number register 303. That is, the control logic 322 determines whether the hardware unit 332 shown in FIG. 3 has been assigned to the memory block associated with the memory address specified by the memory access request. If yes, go to step 406.

In step 406, control logic 322 dispatches hardware unit 332 shown in FIG. 3 to the associated memory block. In an embodiment, control logic 322 dispatches hardware unit 332 in a round-robin manner. In other embodiments, control logic 322 maintains the least-recently-used information for hardware unit 332 that has not been used for the longest time, and is a least-recently-used method that has not been used for the longest time. The basis is assigned. Additionally, control logic 322 initializes the assigned hardware unit 332. In particular, the control logic 322 clears all bits of the block bit mask register 302, populates the level bits above the memory access address into the block number register 303, and clears the minimum. The index register 304, the maximum indicator register 306, the minimum change counter 308, the maximum change counter 312, the total counter 314, and the period match counter 318 are zero. The flow proceeds to step 408.

In step 408, control logic 322 accesses the address based on the memory. The hardware unit 332 is updated as described in FIG. The flow proceeds to step 412.

In step 412, the hardware unit 332 examines the total counter 314 to determine whether the program has sufficient access requirements for the memory block to detect an access pattern. In one embodiment, control logic 322 determines whether the count value of total counter 314 is greater than a predetermined value. In an embodiment, the predetermined value is 10, however, there are many variations of the predetermined values, and the present invention is not limited thereto. If sufficient access requirements have been fulfilled, the flow proceeds to step 414; otherwise the flow ends.

In step 414, control logic 322 determines if the access request specified in block bit mask register 302 has a significant trend. That is, control logic 322 determines whether the access request has a significantly upward trend (access address increase) or a downward trend (access address reduction). In one embodiment, control logic 322 determines whether the access request has a significant trend based on whether the difference between the minimum change counter 308 and the maximum change counter 312 is greater than a predetermined value. In one embodiment, the predetermined value is 2, while in other embodiments the predetermined value may be other values. When the count value of the minimum change counter 308 is greater than the count value of the maximum change counter 312, there is a clear downward trend; conversely, when the count value of the maximum change counter 312 is greater than the count value of the minimum change counter 308, There is a clear upward trend. When a significant trend has occurred, proceed to step 416, otherwise the process ends.

In step 416, control logic 322 determines if there is an apparent pattern period winner in the access request specified by block cipher mask register 302. In one embodiment, the control logic 322 determines whether there is an apparent transition period based on whether the difference between the one of the period matching counters 318 and the count value of the other period matching counters 318 is greater than a predetermined value. Family. In one embodiment, the predetermined value is 2, while in other embodiments the predetermined value may be other values. The update action of the period match counter 318 will be detailed in FIG. When there is a clear pattern of winners, the flow proceeds to step 418; otherwise, the process ends.

In step 418, control logic 322 fills in direction register 342 to indicate the apparent directional trend as determined by step 414. In addition, control logic 322 fills in state cycle register 346 with the clear winning pattern period (N) detected in step 416. Finally, control logic 322 populates the apparent register 344 with the apparent winner modality period detected in step 416. That is, the control logic 322 masks the intermediate indicator register 316 of the scratchpad 302 to the right or left N bits (matched as described in step 518 of FIG. 5) with the block bit to fill in the temporary state. 344. The flow proceeds to step 422.

In step 422, the control logic 322 begins prefetching the non-fetched cache line in the memory block according to the detected direction and the mode (as shown in FIG. 6). Said). The process ends at step 422.

Fig. 5 is a flow chart showing the operation of step 408 shown in Fig. 4 by the prefetch unit 124 shown in Fig. 3. The flow begins in step 502.

In step 502, control logic 322 increments the count value of total counter 314. The flow proceeds to step 504.

In step 504, the control logic 322 determines whether the current memory access address (in particular, the index value of the memory block of the cache line associated with the most recent memory access address) is greater than the maximum index temporary storage. The value of 306. If so, the flow proceeds to step 506; otherwise, the flow proceeds to step 508.

In step 506, control logic 322 updates the maximum indicator register 306 with the index value of the memory block of the cache line associated with the most recent memory access address and increments the count value of the maximum change counter 312. The flow proceeds to step 514.

In step 508, control logic 322 determines whether the index value of the memory block of the cache line associated with the most recent memory access address is less than the value of minimum indicator register 304. If so, the flow proceeds to step 512; if not, the flow proceeds to step 514.

In step 512, control logic 322 updates the minimum indicator register 304 with the index value of the memory block of the cache line associated with the most recent memory access address and increments the count value of the minimum change counter 308. The flow proceeds to step 514.

In step 514, control logic 322 calculates an average of minimum indicator register 304 and maximum indicator register 306 and updates intermediate indicator register 316 with the calculated average. The flow proceeds to step 516.

In step 516, the control logic 322 checks the block bit mask register 302 and cuts it into the left and right N bits, centered on the intermediate indicator register 316, where N is the match counter for each cycle. 318 related bits. The flow proceeds to step 518.

In step 518, control logic 322 determines whether the N-bit to the left of intermediate indicator register 316 matches the N-bit to the right of intermediate indicator register 316. If so, the flow proceeds to step 522; if not, the flow ends.

In step 522, control logic 322 increments the count value of period match counter 318 having an N cycle. The process ends at step 522.

Figure 6 is a flow chart showing the operation of the prefetch unit 124 of Figure 3 to perform step 422 of Figure 4. The flow begins in step 602.

In step 602, the control logic 322 initializes the state cycle register 346 of the intermediate indicator register 316 that is outside the detection direction, the search index register 352 and the patch location. 348 is initialized. That is, control logic 322 initializes search index register 352 and aspect area register 348 to add/subtract between intermediate indicator register 316 and detected period (N). After the value. For example, when the value of the intermediate indicator register 316 is 16, N is 5, and the trend shown by the direction register 342 is upward, the control logic 322 will search the indicator register 352 and the sample area register 348. Initialized to 21. Thus, in this example, for comparison purposes (described below), the 5-bits of the mode register 344 can be placed in bits 21 through 25 of the block bit mask register 302. The flow proceeds to step 604.

In step 604, the control logic 322 tests the bit in the block buffer mask 302 in the direction register 342 and the corresponding bit in the mode register 344 (the bit is located in the sample). The state area register 348 is used to mask the temporary buffer in the corresponding block, and is used to predict whether to prefetch the corresponding cache line in the memory block. The flow proceeds to step 606.

In step 606, control logic 322 predicts if the tested cache line is needed. When the bit of the mode register 344 is true, the control logic 322 predicts what the cache line needs, and the mode predictor will access the cache line. If the cache line is required, the flow proceeds to step 614; otherwise, the flow proceeds to step 608.

In step 608, control logic 322 is based on direction register 342. Whether the end of the block bit mask register 302 has been reached, it is determined whether there are other untested cache lines in the memory block. If there are no untested cache lines, the process ends; otherwise, the flow proceeds to step 612.

In step 612, control logic 322 increments/decreases the value of direction register 342. In addition, if the direction register 342 has exceeded the last bit of the mode register 344, the control logic 322 will update the sample area register 348 with the new value of the direction register 342, for example, to temporarily pause the pattern. The register 344 is shifted to the position of the direction register 342. The flow proceeds to step 604.

In step 614, control logic 322 determines if the required cache line has been prefetched. When the bit of the block bit mask register 302 is true, the control logic 322 determines that the desired cache line has been prefetched. If the desired cache line has been prefetched, the flow proceeds to step 608; otherwise, the flow proceeds to step 616.

In decision step 616, if the direction register 342 is down, the control logic 322 determines from the minimum indicator register 304 whether the cache line under consideration is more than a predetermined value (the default value is 16 in one embodiment). Or if the direction register 342 is up, the control logic 322 determines from the maximum indicator register 306 whether the cache line being considered has more than a predetermined value. If the control logic 322 is true at the above determination, the flow ends; otherwise, the flow proceeds to decision step 618. It should be noted that if the cache line is significantly larger than (away from) the minimum indicator register 304/maximum indicator register 306, the process ends, but this does not mean that the prefetch unit 124 will not prefetch the memory block. The other cache lines, because according to the steps of FIG. 4, subsequent accesses to the cache line of the memory block will also trigger more prefetch actions for the memory block.

In step 618, control logic 322 determines prefetch request queue 328 Is it full? If the prefetch request queue 328 is full, the flow proceeds to step 622, otherwise the flow proceeds to step 624.

In step 622, control logic 322 stalls until prefetch request queue 328 is non-full. The flow proceeds to step 624.

In step 624, control logic 322 advances an entry to prefetch request queue 328 to prefetch the cache line. The flow proceeds to step 608.

Figure 7 is a flow chart showing the operation of the prefetch request queue 328 of Figure 3. The process begins in step 702.

In step 702, one of the prefetch requests advanced to the prefetch request queue 328 is allowed to be accessed in step 624 (where the prefetch request is used to access the second level cache 118) And proceed to the pipeline of the second level cache memory 118. The flow proceeds to step 704.

In step 704, the second level cache memory 118 determines whether the cache line address hits the second level cache memory 118. If the cache line address hits the second level cache memory 118, the flow proceeds to step 706; otherwise, the flow proceeds to decision step 708.

In step 706, since the cache line is already prepared in the second level cache 118, there is no need to prefetch the cache line and the flow ends.

In step 708, control logic 322 determines if the response of second level cache 118 has to be re-executed for this prefetch request. If so, the flow proceeds to step 712; otherwise, the flow proceeds to step 714.

In step 712, the prefetch request for the prefetch cache line is re-pushed into the prefetch request queue 328. The process ends at step 712.

In step 714, the second level cache 118 advances a request One of the microprocessors 100 is filled into a fill queue (not shown) for requiring the busbar interface unit 122 to read the cache line into the microprocessor 100. The process ends at step 714.

Fig. 9 is a diagram showing an example of the operation of the microprocessor 100 of Fig. 2. As shown in FIG. 9, after ten accesses to a memory block, the block bit masks the scratchpad 302 (the asterisk at the one-bit position indicates access to the corresponding cache line) The minimum change counter 308, the maximum change counter 312, and the contents of the total counter 314 in the first, second, and tenth accesses. In Fig. 9, the minimum change counter 308 is referred to as "cntr_min_change", the maximum change counter 312 is referred to as "cntr_max_change", and the total counter 314 is referred to as "cntr_total". The position of the intermediate indicator register 316 is indicated by "M" in Fig. 9.

Since the first access to address 0x4dced300 (as in step 402 of FIG. 4) is performed on the cache line on index 12 in the memory block, control logic 322 masks the set block bit. The bit 12 of the mask register 302 (step 408 of Figure 4) is as shown. Additionally, control logic 322 will update minimum change counter 308, maximum change counter 312, and total counter 314 (steps 502, 506, and 512 of FIG. 5).

Since the second access to the address 0x4ced260 is performed on the cache line located on the index 9 in the memory block, the control logic 322 masks the bit 9 of the register 302 according to the set block bit, such as The figure shows. Additionally, control logic 322 will update the count value of minimum change counter 308 and total counter 314.

In the third to tenth accesses (the addresses of the third to ninth access are not illustrated, and the tenth access address is 0x4dced6c0), the control logic 322 blocks the block bits according to The hood register 302 performs the appropriate element settings as shown. Additionally, control logic 322 updates the count values of minimum change counter 308, maximum change counter 312, and total counter 314 for each access update.

At the bottom of Fig. 9, the control logic 322 matches the contents of the counter 318 after the execution of steps 514 through 522 in each memory access performed ten times. In FIG. 9, the period matching counter 318 is referred to as "cntr_period_N_matches", where N is 1, 2, 3, 4 or 5.

As in the example shown in FIG. 9, although the criteria of step 412 are met (the total counter 314 is at least ten) and the criteria of step 416 are met (the period matching counter 318 of period 5 is at least greater than 2 than all other period matching counters 318), However, the criteria of step 414 are not met (the difference between the minimum change counter 308 and the block bit mask register 302 is less than 2). Therefore, the prefetch operation will not be performed within this memory block at this time.

The bottom of Fig. 9 also shows the states from the periods 3, 4, and 5 to the right and left sides of the intermediate indicator register 316 in periods 3, 4, and 5.

Figure 10 is a flow chart showing the operation of the example shown in Figure 9 of the microprocessor 100 of Figure 2. Figure 10 depicts information similar to Figure 9, but with the exception of the eleventh and twelfth accesses to the memory block (the address of the twelfth access is 0x4dced760). As shown, it conforms to the criteria of step 412 (the total counter 314 is at least ten), the criteria of step 414 (the difference between the minimum change counter 308 and the block bit mask register 302 is at least 2), and the steps The criteria of 416 (the period match counter 318 of cycle 5 is at least greater than 2 in the cycle 5 count than all other cycles match counter 318). Therefore, according to step 418 of FIG. 4, the control logic 322 populates the direction register 342 (to indicate that the direction trend is upward), and the state cycle register 346 (fill in the number) Value 5), the mode register 344 (using the state "**" or "01010"). Control logic 322 also performs prefetch prediction for the memory block in accordance with steps 422 and 6 of FIG. 4, as shown in FIG. Figure 10 also shows control logic 322 in operation of step 602 of Figure 6, direction register 342 at bit 21 position.

Figure 11 is a flow chart showing the operation of the microprocessor 100 of Figure 2 continuing the examples of Figures 9 and 10. Figure 11 depicts each of the twelve different examples (the tables are labeled 0 through 11) by way of example through step 604 through step 616 of Figure 6 until the cache line of the memory block is predicted by the prefetch unit 124 to find the need. The operation of the pre-fetched memory block. As shown, in each of the examples, the value of direction register 342 is incremented according to step 612 of FIG. As shown in FIG. 11, in the examples 5 and 10, the modal area register 348 is updated according to step 612 of FIG. As shown in Examples 0, 2, 4, 5, 7, and 10, since the bit in the direction register 342 is false, the pattern indicates that the cache line on the direction register 342 will not be needed. . The figure further shows that in the examples 1, 3, 6 and 8, since the bit of the mode register 344 is true in the direction register 342, the mode register 344 indicates that the direction is temporarily stored. The cache line on device 342 will be needed, however the cache line is ready to be fetched, as indicated by the block bit mask register 302 being true. Finally, as shown, in the example 11, since the bit of the mode register 344 is true in the direction register 342, the mode register 344 indicates the direction register 342. The cache line will be needed, but since the bit of the block bit mask register 302 is false, the cache line has not been fetched. Accordingly, control logic 322 advances a prefetch request to prefetch request queue 328 in accordance with step 624 of FIG. 6 for prefetching the cache line at address 0x4dced800, which corresponds to the mask in the block bit mask. Bit 32 of the memory 302.

In one embodiment, one or more of the predetermined values described may be by an operating system (eg, via a model specific register (MSR)) or via a microprocessor 100 fuses. Programming is performed in which the fuse can be blown during the production of the microprocessor 100.

In one embodiment, the size of the block bit mask register 302 can be reduced to save power and die die real estate. That is, the number of bits in each block bit mask register 302 will be less than the number of cache lines in a memory block. For example, in one embodiment, the number of bits per block masking buffer 302 is only half the number of cache lines included in the memory block. The block bit mask register 302 only tracks access to the upper half block or the lower half block, and the half of the memory block is accessed first, and an additional bit is used to indicate the memory. Whether the lower half or the upper half of the body block is accessed first.

In an embodiment, the control logic 322 does not test the upper and lower N bits of the intermediate indicator register 316 as described in step 516/518, but includes a serial engine, one or two bit scan areas at a time. The block bit masks the register 302 for finding a pattern with a period greater than a maximum period (5 bits as previously described).

In one embodiment, if no significant directional trend is detected at step 414, or a significant morphological period is not detected at step 416, and the count value of the total counter 314 reaches a predetermined threshold (to indicate When most of the cache lines in the memory block have been accessed, control logic 322 continues to execute and prefetches the remaining cache lines in the memory block. The predetermined threshold value is a relatively high percentage of the number of cache memories of the memory block, such as a block. The bit masks the value of the bit of the scratchpad 302.

Combine the second level cache memory with the prefetch unit of the first level data cache

Modern microprocessors include cache memory with a hierarchical structure. Typically, a microprocessor includes a small and fast first-level data cache memory and a larger but slower second-level cache memory, as in the first level data cache of FIG. 2, respectively. The memory 116 and the second level cache memory 118. A cache memory having a hierarchical structure facilitates prefetching data to the cache memory to improve the hit rate of the cache memory. Since the first level data cache memory 116 is faster, the preferred condition is prefetching data to the first level data cache memory 116. However, since the memory capacity of the first level data cache memory 116 is small, the cache memory hit rate may actually be poor and slow, because if the prefetch unit incorrectly prefetches data into the first level data cache memory Body 116, when it is finally found that these data are not needed, it will be replaced by other required information. Therefore, the selection of the first level data cache memory 116 or the second level cache memory 118 is loaded, and whether the prefetch unit can correctly predict whether the data is required or not. Since the first level data cache memory 116 is required to be smaller in size, the first level data cache memory 116 tends to have a smaller capacity and thus has a lower accuracy; conversely, due to the second level cache memory label And the size of the data array makes the size of the first-level cache memory prefetching unit appear small, so a second-level cache memory prefetching unit can have a larger capacity and thus has better accuracy.

The advantage of the microprocessor 100 in the embodiment of the present invention is that a load/store unit 134 is used as the second level cache memory 118 and the first level resource. The basis for the prefetching of the memory 116 is required. Embodiments of the present invention improve the accuracy of the load/store unit 134 (second level cache memory 118) for application to resolve the above-described prefetching into the first level data cache memory 116. Moreover, the embodiment also uses a single body of logic to process the target of the prefetch operation of the first level data cache memory 116 and the second level cache memory 118.

Figure 12 shows a microprocessor 100 in accordance with various embodiments of the present invention. The microprocessor 100 of Fig. 12 is similar to the microprocessor 100 of Fig. 2 and has additional features as described below.

The first level data cache memory 116 provides a first level data memory address 196 to the prefetch unit 124. The first level data memory address 196 is a physical address for loading/storing access to the first level data cache memory 116 by the load/store unit 134. That is, the prefetch unit 124 performs eavesdrops as the load/store unit 134 accesses the first level data cache 116. The prefetch unit 124 provides the same state prediction cache line address 194 to the first level data cache memory 116, and the sample prediction cache line address 194 is the address of the cache line, which is fast. The line take-up prefetching unit 124 predicts that the load/store unit 134 is about to request the first level data cache memory 116 based on the first level data memory address 196. The first level data cache memory 116 provides a cache line configuration request 192 to the prefetch unit 124 for requesting cache lines from the second level cache memory 118, and the addresses of the cache lines are stored in伫 198. Finally, the second level cache memory 118 provides the requested cache line data 188 to the first level data cache memory 116.

The prefetch unit 124 also includes a first level data search indicator 172. And the first level of data sample address 178, as shown in Figure 12. The use of the first level data search indicator 172 and the first level data sample address 178 is related to Figure 14 and is described below.

Fig. 13 is a flow chart showing the operation of the prefetch unit 124 of Fig. 12. The flow begins in step 1302.

In step 1302, the prefetch unit 124 receives the first level data memory address 196 of FIG. 12 from the first level data cache memory 116. The flow proceeds to step 1304.

In step 1304, the prefetch unit 124 detects that a memory block (eg, a page) falls into the cache line prefetched by the prefetch unit 124 for the previously measured access mode, and Pre-fetching these cache lines from the system memory has begun to enter the second level cache memory 118 as described in relation to Figures 1 through 11. In detail, prefetch unit 124 maintains a block number register 303 that specifies the base address of the memory block to which the detected access mode is prefetched. The prefetch unit 124 detects whether the first level data memory address 196 falls in the memory area by detecting whether the bit of the block number register 303 matches the corresponding bit of the first level data memory address 196. In the block. The flow proceeds to step 1306.

In step 1306, starting from the first level data memory address 196, the prefetch unit 124 looks for the next two cache lines in the detected access direction detected in the memory block. The cache lines are related to the previously detected access directions. A more detailed execution of step 1306 will be described in subsequent Figure 14. The flow proceeds to step 1308.

In step 1308, the prefetch unit 124 provides the physical address of the next two cache lines to the first level data cache 116 in step 1306. The cache line address 194 is predicted for the aspect. In other embodiments, the number of cache line addresses provided by prefetch unit 124 may be more or less than two. The flow proceeds to step 1312.

In step 1312, the first level data cache 116 advances the address provided in step 1308 to queue 198. The flow proceeds to step 1314.

In step 1314, whenever the queue 198 is non-empty, the first level data cache 116 takes the next address out of the queue 198 and issues a cache line configuration request 192 to The secondary cache memory 118 is used to obtain the cache line at the address. However, if one of the addresses in the queue 198 has appeared in the first level data cache 116, the first level data cache 116 will dump the address and discard the second level cache. Body 118 requires its cache line. The second level cache memory 118 then provides the requested cache line data 188 to the first level data cache memory 116. The process ends at step 1314.

Fig. 14 is a flow chart showing the operation of the prefetch unit 124 shown in Fig. 12 in accordance with step 1306 of Fig. 13. The operation described in Fig. 14 is in the case where the direction of the sample is detected as upward in Fig. 3. However, if the detected direction is downward, the prefetch unit 124 can also be used to perform the same function. The operations of steps 1402 to 1408 are for placing the mode register 344 in FIG. 3 in an appropriate position in the memory block, so that the prefetch unit 124 starts from the first level data memory address 196. The mode searches for the next two cache lines, and copies the state 344 of the state register 344 on the memory block as needed. The flow begins in step 1402.

In step 1402, the prefetch unit 124 is similar to step 6 in step Step 602 initializes the search index register 352 and the mode area register 348, and initializes the first picture in FIG. 12 by using the sum of the state cycle register 346 and the intermediate indicator register 316 of FIG. The level data search indicator 172 and the first level data sample address 178. For example, if the value of the intermediate indicator register 316 is 16 and the phase period register 346 is 5, and the direction of the direction register 342 is upward, the prefetch unit 124 initializes the first level data search indicator 172 and The first level of data sample addresses 178 to 21. The flow proceeds to step 1404.

In step 1404, the prefetch unit 124 determines whether the first level data memory address 196 falls into the state of the state register 344 having the currently specified position. The current starting position of the mode is according to step 1402. Determined and updated according to step 1406. That is, the prefetch unit 124 determines the value of the appropriate bits of the first level data memory address 196 (ie, removes the bits of the acknowledgment memory block, and is used to specify the bit in the cache line). Whether the byte of the byte offset is greater than or equal to the value of the first level data search indexer 172, and whether it is less than or equal to the first level data search indexer 172 and the state cycle register 346. The sum of the values added. If the first level data memory address 196 falls into the state of the state register 344, the flow proceeds to step 1408; otherwise, the flow proceeds to step 1406.

In step 1406, the prefetch unit 124 increments the values of the first level data search indexer 172 and the first level data sample address 178 according to the state cycle register 346. According to the operation described in step 1406 (and subsequent step 1418), if the first level data search indexer 172 has reached the end of the memory block, the search ends. The flow returns to step 1404.

In step 1408, the prefetch unit 124 will search for the first level data. The value of the counter 172 is set to the offset of the memory page of the cache line associated with the first level data memory address 196. The flow proceeds to step 1412.

In step 1412, the prefetch unit 124 tests the bits in the modal register 344 in the first level data search indexer 172. The flow proceeds to step 1414.

In step 1414, prefetch unit 124 determines if the bit tested in step 1412 is set. If the bit tested in step 1412 is set, the flow proceeds to step 1416; otherwise, the flow proceeds to step 1418.

In step 1416, prefetch unit 124 marks the cache line predicted by state register 344 in step 1414 as ready to transmit the physical address to first level data cache 116 as the same. The state predicts the cache line address 194. The process ends at step 1416.

In step 1418, the prefetch unit 124 increments the value of the first level data search indicator 172. In addition, if the first level data search indexer 172 has exceeded the last bit of the mode register 344, the prefetch unit 124 updates the first level data search with the new value of the first level data search indicator 172. The value of the indicator 172, that is, the position of the shift state register 344 to the new first level data search indexer 172. The operations of steps 1412 through 1418 are repeated until the two cache lines (or other predetermined values of the cache line) are found. The process ends at step 1418.

The advantage of pre-fetching the cache line to the first level data cache 116 in a micro-bypass manner in FIG. 13 is required for the first level data cache 116 and the second level memory 118. The change is small. However, in other embodiments, the prefetch unit 124 may not provide the mode prediction cache line address 194 to the first The primary data cache memory 116. For example, in an embodiment, the prefetch unit 124 directly requests the bus interface unit 122 to retrieve the cache line from the memory, and then writes the received write cache line to the first level data cache. 116. In another embodiment, the prefetch unit 124 requests and obtains a cache line from the second level cache 118 for providing data to the prefetch unit 124 (if a miss is used, the cache is fetched from the memory) Line) and write the received cache line to the first level data cache 116. In other embodiments, the prefetch unit 124 requests a cache line from the second level cache memory 118 (if a miss line is used to retrieve the cache line from the memory), which directly writes the cache line The primary data cache memory 116.

As described above, embodiments of the present invention have the benefit of having a single prefetch unit 124 as the basis for the prefetching needs of both the second level cache memory 118 and the first level data cache memory 116. Although the blocks shown in Figures 2, 12, and 15 (discussed below) are different blocks, the prefetch unit 124 may be spatially arranged adjacent to the tag and data column of the second level cache memory 118. The location of (data array) and conceptually includes second level cache memory 118, as shown in FIG. Embodiments allow prefetch unit 124 to have a larger spatial arrangement to increase its accuracy and its large space requirements to apply a single logic to process first level data cache memory 116 and second level cache memory 118. The prefetching operation solves the problem that the prior art can only prefetch data to the first-level data cache memory 116 having a smaller capacity.

Bounding box prefetch unit with reduced warm-up penalty across spreads

The prefetching unit 124 of the present invention can detect a memory area A more complex access pattern (eg, a physical memory page) on a block (eg, a physical memory page), which is generally undetectable by a conventional prefetch unit. For example, the prefetch unit 124 can detect a program that is accessing a memory block according to the same state, even if the out-of-order execution pipeline of the microprocessor 100 does not The order of the program commands re-orders the memory access. In general, this may cause the conventional prefetch unit not to detect the memory access pattern without causing prefetching. This is because the prefetch unit 124 only considers efficient access to the memory block, and the time order is not a point of consideration.

However, in order to satisfy the ability to identify more complex access patterns and/or reorder access patterns, the prefetch unit 124 of the present invention may take a longer time to detect than conventional prefetch units. The access mode is measured as follows, "warm-up time". Therefore, a method of reducing the warm-up time of the prefetch unit 124 is required.

The prefetch unit 124 is configured to predict whether a program that was previously accessing a memory block by an access mode has crossover a new memory that is actually adjacent to the old memory block. Block, and predict whether this program will continue to access this new memory block according to the same pattern. In response to this, the prefetch unit 124 uses the appearance, direction, and other relevant information from the old memory block to speed up the detection of the access state in the new memory block, ie, reduce the warm-up time.

A block diagram of a microprocessor 100 having a prefetch unit 124 is shown in FIG. The microprocessor 100 of Fig. 15 is similar to the microprocessor 100 of Figs. 2 and 12 and has other characteristics as described below.

As described in relation to FIG. 3, the prefetch unit 124 includes a plurality of hardware units 332. Each hardware unit 332 further includes a memory block hashed virtual address of memory (HVAMB) 354 and a status bar 356 as compared to FIG. In the process of initializing the dispatched hardware unit 332 in step 406 described in FIG. 4, the prefetch unit 124 fetches the physical block number in the block number register 303 and places the physical block After the block code is translated into a virtual address, the physical block code is translated into a virtual address (the hash is virtualized according to the same hashing algorithm performed in step 1704 described in the subsequent FIG. The address is stored and the result of its hash calculation is stored in the memory block virtual hash address field 354. Status bar 356 has three possible values: inactive, active, or probationary, as described below. The prefetch unit 124 also includes a virtual hash table (VHT) 162. For a detailed description of the organization and operation of the virtual hash table 162, please refer to the following descriptions of FIGS. 16 to 19.

As shown in Fig. 16, the virtual hash table 162 of Fig. 15 is shown. The virtual hash table 162 includes a plurality of items, preferably organized into a queue. Each entry includes a valid bit (not shown) and three columns: a negative 1 hash virtual address 1602 (HVAM1), an unmodified hash virtual address 1604 (HVAUN), and a positive 1 hash. Virtual address 1606 (HVAP1). Please refer to the subsequent Figure 17 for the manner in which the above fields are filled out to generate these values.

Figure 17 is a flow chart showing the operation of the microprocessor 100 of Figure 15. The flow begins in step 1702.

In step 1702, the first level data cache memory 116 is received. A load/store request from one of the load/store units 134 whose load/store requirements include a virtual address. The flow proceeds to step 1704.

In step 1704, the first level data cache 116 performs a hash function (function) on the selected bit of the hash address received in step 1702 to generate an unmodified hash virtual address 1604 (HVAUN). ). In addition, the first level data cache memory 116 adds a memory block size (MBS) to the bit selected by the hash address received in step 1702 to generate a total value and add The total value performs a hash function to generate a positive 1 hash virtual address 1606 (HVAP1). In addition, the first level data cache memory 116 subtracts the size of the memory block from the bit selected by the hash address received in step 1702 to generate a difference and perform a hash on the difference. Function to generate a negative 1 hash virtual address 1602 (HVAM1). In one embodiment, the memory block size is 4 KB. In one embodiment, the virtual address is 40 bits, and the virtual address bits 39:30 and 11:0 are ignored by the hash function. The remaining 18 virtual address bits are "dealt", and if there is already information, it is handled by the hash bit position. The idea is that the lower bits of the virtual address have the highest degree of entropy and the higher bits have the lowest degree of chaos. Processing in this way ensures that the entropy level is more consistent across the hashed bits. In one embodiment, the remaining 18 bits of the virtual address are hashed to 6 bits according to the method of Table 1 below. However, in other embodiments, different hashing algorithms may also be considered; in addition, embodiments may consider not using a hashing algorithm if there is a performance dominates space and design considerations for power consumption. The flow proceeds to step 1706.

Assign hash[5]=VA[29]^VA[18]^VA[17];

In step 1706, the first level data cache memory 116 provides the unmodified hash virtual address (HVAUN) 1604, the positive 1 hash virtual address (HVAP1) 1606, and the negative 1 hash virtual address generated in step 1704. (HVAM1) 1602 to prefetch unit 124. Flow proceeds to step 1708.

In step 1708, the prefetch unit 124 selects with the unmodified hash virtual address (HVAUN) 1604, the positive 1 hash virtual address (HVAP1) 1606, and the negative 1 hash virtual address (HVAM1) 1602 received in step 1706. The virtual hash table 162 is updated. That is, if the virtual hash table 162 already includes a new unmodified hash virtual address 1604 (HVAUN), positive 1 hash virtual address 1606 (HVAP1), and negative 1 hash virtual address 1602 (HVAM1), The fetch unit 124 then discards the update virtual hash table 162. Conversely, prefetch unit 124 will unmodified hash virtual address 1604 (HVAUN), positive 1 hash virtual address 1606 (HVAP1), and negative 1 hash virtual in a first-in-first-out manner. The address 1602 (HVAM1) advances to the topmost item of the virtual hash table 162 and marks the promoted item as valid. The process ends at step 1708.

As shown in FIG. 18, the virtual hash table 162 of FIG. 16 is operated after the load/store unit 134 of the prefetch unit 124 operates according to the description of FIG. 17, wherein the load/store unit 134 is adapted to the program. Execution, has always been Advancing the two memory blocks (labeled A and A+MBS) in the upper direction and entering a third memory block (labeled A+2*MBS) in response to the prefetch of the filled virtual hash table 162 Unit 124. In detail, the virtual hash table 162 from the end of the two items of the project includes a hash of the A-MBS in the negative 1 hash virtual address (HVAM1) 1602, and a hash in the unmodified hash virtual address (HVAUN) 1604 A. And the hash of the A+MBS in the 1st hashed virtual address (HVAP1) 1606; the virtual hash table 162 is a hash of the A project of the negative 1 hash virtual address (HVAM1) 1602 from the end of a project, in the unmodified hash The hash of the A+MBS of the virtual address (HVAUN) 1604 and the hash of the A+2*MBS of the positive 1 hash virtual address (HVAP1) 1606; the item of the virtual hash table 162 at the end (ie the item promoted at the most recent time) ) A hash of A+MBS included in the negative 1 hash virtual address (HVAM1) 1602, a hash of A+2*MBS in the unmodified hash virtual address (HVAUN) 1604, and a positive 1 hash virtual address (HVAP1) 1606 A+3*MBS hash.

The operation flowchart of the prefetch unit 124 of Fig. 5 is shown in Fig. 19 (consisting of Fig. 19A and Fig. 19B). The flow begins in step 1902.

In step 1902, the first level data cache 116 transmits a new allocation request (AR) to the second level cache 118. The new configuration requirement requires a new memory block. That is to say, the prefetch unit 124 determines that the memory block associated with the configuration request is new, that is, the memory block associated with the new configuration request has not been configured. That is, the prefetch unit 124 has not recently encountered a configuration requirement for a new memory block. In one embodiment, the configuration requirements are a failure to load/store the first level data cache 116 and are subsequently requested by the second level cache 118 The requirements generated by the same cache line. In an embodiment, the configuration requirement is to specify a physical address, and one of the virtual addresses associated with the physical address is translated from the physical address. The first level data cache memory 116 is based on a hash function (ie, the same hash function as step 1704 of FIG. 17), and hashes the virtual address associated with the physical address of the configuration request to generate one of the configuration requirements. The virtual address (HVAAR) has been hashed and the hashed virtual address of the configuration requirement is provided to the prefetch unit 124. The flow proceeds to step 1903.

In step 1903, prefetch unit 124 is assigned a new hardware unit 332 to the new memory block. If there are idle hardware units 332 present, prefetch unit 124 configures an idle hardware unit 332 for the new memory block. Otherwise, in one embodiment, prefetch unit 124 configures a least recently used hardware unit 332 for the new memory block. In one embodiment, the prefetch unit 124 inactivates the hardware unit 332 once the prefetch unit 124 has pre-sampled all of the cache lines of the memory block indicated by the state. In one embodiment, the prefetch unit 124 has the ability to pin the hard unit 332 so that it is not reset even if it is a least recently used hardware unit 332. For example, if the prefetch unit 124 detects that the memory block has been accessed for a predetermined number of times according to the mode, the prefetch unit 124 has not completed all prefetching of the entire memory block according to the mode. The prefetch unit 124 can fix the hardware unit 332 associated with the memory block so that it is not suitable for being reset even if it is a least recently used hardware unit 332. In an embodiment, the prefetch unit 124 maintains the relative period of each hardware unit 332 (from the original configuration), and when its age reaches a predetermined period threshold, the prefetch unit 124 will fail the hard Body unit 332. In another embodiment, if the prefetch unit 124 (by subsequent steps 1904 to 1926) detects a virtual Adjacent memory blocks, and prefetching of the memory blocks from the virtual neighbors has been completed, and the prefetch unit 124 selectively reuses the hardware units 332 in the virtual adjacent memory blocks. A new hardware unit 332 is not configured. In this embodiment, the prefetch unit 124 selectively initializes various storage elements of the reusable hardware unit 332 (eg, the direction register 342, the mode register 344, and the sample area register 348) so that Maintain the information available for storage within it. Flow proceeds to step 1904.

In step 1904, prefetch unit 124 compares the negative 1 hash virtual address 1602 (HVAM1) and the positive 1 hash virtual address of each of the hashed virtual address (HVAAR) and virtual hash table 162 generated in step 1902. 1606 (HVAP1). The prefetch unit 124 operates in accordance with steps 1904 through 1922 to determine whether an active memory block is virtually adjacent to a new memory block. The prefetch unit 124 operates in accordance with steps 1924 through 1928 for predictive memory. Whether the physical access will continue to enter the new memory block from the virtual adjacent active memory block according to the previously detected access mode and direction, to reduce the warm-up time of the prefetch unit 124, The prefetch unit 124 is enabled to prefetch new memory blocks faster. Flow proceeds to step 1906.

In step 1906, prefetch unit 124 determines whether the hashed virtual address (HVAAR) matches any of the virtual hash table 162 based on the comparison performed in step 1904. If the hash virtual address (HVAAR) matches one of the virtual hash tables 162, the flow proceeds to step 1908; otherwise, the flow proceeds to step 1912.

In step 1908, the prefetch unit 124 sets a candidate direction flag (canddate_direction flag) to a value to indicate the upward direction. Process Proceed to step 1916.

In step 1912, prefetch unit 124 determines whether the hashed virtual address (HVAAR) matches any of the virtual hash table 162 based on the comparison performed by step 1908. If the hash virtual address (HVAAR) matches one of the virtual hash tables 162, the flow proceeds to step 1914; otherwise, the flow ends.

In step 1914, the prefetch unit 124 sets the candidate direction flag (canddate_direction flag) to a value to indicate the downward direction. The flow proceeds to step 1916.

In step 1916, prefetch unit 124 sets a candidate hash register (not shown) to one of the unmodified hash virtual addresses 1604 (HVAUN) of virtual hash table 162 determined in step 1906 or 1912. Value. The flow proceeds to step 1918.

In step 1918, the prefetch unit 124 compares the candidate hashes (candidate_hva) with the memory block virtual hash address field (HVAMB) 354 of each active memory block in the prefetch unit 124. The flow proceeds to step 1922.

In step 1922, prefetch unit 124 determines whether the candidate hash (candidate_hva) matches any of the memory block virtual hash address fields (HVAMB) 354, based on the comparison performed by step 1918. If the candidate hash (candidate_hva) matches a memory block virtual hash address field (HVAMB) 354, the flow proceeds to step 1924; otherwise, the flow ends.

In step 1924, prefetch unit 124 has determined that the matching active memory block found at step 1922 is indeed virtually adjacent to the new memory block. Thus, prefetch unit 124 compares the candidate directions (as specified by step 1908 or 1914) with The direction register 342 matching the active memory block is used to predict whether the memory access will continue to enter a new one from the virtual adjacent active memory block according to the previously detected access mode and direction. Memory block. In detail, if the candidate direction is different from the direction register 342 of the virtual adjacent memory block, the memory access is unlikely to continue from the virtual adjacent according to the previously detected access mode and direction. The active memory block has entered a new memory block. The flow proceeds to step 1926.

In step 1926, the prefetch unit 124 determines whether the candidate direction matches the direction register 342 matching the active memory block according to the comparison method performed in step 1924. If the candidate direction matches the direction register 342 matching the active memory block, the flow proceeds to step 1928; otherwise, the flow ends.

In step 1928, the prefetch unit 124 determines whether the new reset request received at step 1902 is directed to the one of the matching virtual adjacent active memory blocks detected in step 1926 has been temporarily stored. The cache line predicted by 344. In an embodiment, in order to perform the determination of step 1928, the prefetch unit 124 effectively switches and copies the modal register 344 of the virtual adjacent active memory block according to the state cycle register 346. The modal location region register 348 continues in the virtual adjacent memory block to maintain the continuity of the pattern 334 in the new memory block. If the new configuration request is to match one of the cache memories associated with the profile register 344 of the active memory block, the flow proceeds to step 1934; otherwise, the flow proceeds to step 1932.

In step 1932, the prefetch unit 124 initializes and fills in the new hardware unit 332 (configured in step 1903) according to steps 406 and 408 of FIG. 4, which is expected to be finally associated with the fourth to sixth figures. Method, detecting new records Recall the new look of the block access, and this will require warm-up time. The process ends at step 1932.

In step 1934, the prefetch unit 124 predicts that the access request will continue to enter the new memory block based on the state register 344 and the direction register 342 that match the virtual adjacent active memory block. Therefore, the prefetch unit 124 fills in the new hardware unit 332 in a manner similar to step 1932, but will be slightly different. In detail, the prefetch unit 124 fills the direction register 342, the mode register 344, and the state cycle register 346 with corresponding values from the hardware unit 332 of the virtual adjacent memory block. In addition, the new value of the mode region register 348 is determined by continuing to switch to the value of the increased state cycle register 346 until it crosses into a new memory block to provide a temporary state of storage. The 344 continues to enter the new memory block, as described in step 1928. Furthermore, the status bar 356 in the new hardware unit 332 is used to mark the new hardware unit 332 as a probationary. Finally, the search indicator temporary store 352 is initialized to be searched by the beginning of a memory block. The flow proceeds to step 1936.

In step 1936, prefetch unit 124 continues to monitor access requests that occur in the new memory block. If the prefetch unit 124 detects that at least a predetermined number of subsequent access requests to the memory block is a memory cache line predicted by the mode register 344, then the prefetch unit 124 causes the hardware unit 332 The status bar 356 transitions from probationary to active, and then begins prefetching from the new memory block as described in FIG. In one embodiment, the predetermined number of access requests is two, although other embodiments may be considered for other predetermined quantities. The process ends at step 1936.

As shown in Fig. 20, it is used by the prefetch unit 124 shown in Fig. 15. One of the hashed physical address-to-hashed virtual address thesaurus 2002. The hash entity address to hashed virtual address library 2002 includes an array of items. Each item includes a physical address (PA) 2004 and a corresponding hash virtual address (HVA) 2006. The corresponding hash virtual address 2006 is the result of hashing the virtual address translated into the physical address 2004. The prefetch unit 124 fills in the items of the hash entity address to the hash virtual address base 2002 by eavesdropping on the most recent pair of virtual/physical addresses of the pipeline spanning the load/store unit 134. In another embodiment, in step 1902 of FIG. 19, the first level data cache memory 116 does not provide a hashed virtual address (HVAAR) to the prefetch unit 124, but only provides the entity associated with the configuration request. Address. The prefetch unit 124 looks for the entity location in the hash entity address to the hash virtual address pool 2002 to find a matching entity address (PA) 2004 and obtains the associated hash virtual address (HVA) 2006, which will be The other part of Figure 19 becomes a hashed virtual address (HVAAR). Addressing the hash entity address to the hash virtual address library 2002 includes the need for the prefetch unit 124 to alleviate the hash virtual address required by the first level data cache 116 to provide configuration requirements, thereby simplifying the first level of data. The interface between the memory 116 and the prefetch unit 124 is taken.

In one embodiment, each item of the hash entity address to the hash virtual address pool 2002 includes a hash entity address instead of the physical address 2004, and the prefetch unit 124 will cache the memory from the first level. The configuration received by 116 requires the physical address to be hashed into a hashed physical address to search for the hashed physical address to the hashed virtual address base 2002 to obtain the appropriate corresponding hash virtual address (HVA) 2006. This embodiment allows a smaller hashed entity address to be hashed to the virtual address pool 2002, but requires additional time to hash the physical address.

As shown in Fig. 21, a multi-core microprocessor 100 according to an embodiment of the present invention is shown. The multi-core microprocessor 100 includes two cores (denoted as core A2102A and core B2102B), which may be considered entirely as core 2102 (or single core 2102). Each core has an element 12 or 15 similar to the single core microprocessor 100 as shown in FIG. Additionally, each core 2102 has a highly reactive prefetch unit 2104 as previously described. The two cores 2102 share the second level cache memory 118 and the prefetch unit 124. In particular, each core 2012 first level data cache memory 116, load/store unit 134, and highly reactive prefetch unit 2104 are coupled to the shared second level cache memory 118 and pre Take unit 124. In addition, a shared highly reactive prefetch unit 2106 is coupled to the second level cache memory 118 and the prefetch unit 124. In one embodiment, the highly reactive prefetch unit 2104/shared highly reactive prefetch unit 2106 prefetches only the next adjacent cache line after the memory access associated with the cache line.

In addition to monitoring the memory access of the load/store unit 134 and the first level data cache 116, the prefetch unit 124 can also monitor the highly reactive prefetch unit 2104/shared highly reactive prefetch. The memory access generated by unit 2106 is used to make a prefetch decision. Prefetch unit 124 can monitor memory accesses from different combined memory access sources to perform the different functions described herein. For example, the prefetch unit 124 can monitor a first combination of memory accesses to perform the phase closure function described in FIGS. 2 through 11, and the prefetch unit 124 can monitor a second combination of memory accesses to perform The related functions described in Figures 12 through 14 and the prefetch unit 124 can monitor a third combination of memory accesses to perform the associated functions described in Figures 15 through 19. In an embodiment, the shared prefetch unit 124 has difficulty monitoring the load/store unit 134 of each core 2102 due to time constraints. behavior. Therefore, the shared prefetch unit 124 indirectly monitors the behavior of the load/store unit 134 via the traffic generated by the first level data cache 116 as its load/store miss. result.

Various embodiments of the invention have been described herein, but those skilled in the art should understand that these embodiments are only by way of example and not limitation. Variations in form and detail may be made by those skilled in the art without departing from the spirit of the invention. For example, the software can enable the functions, fabrication, modeling, simulation, description, and/or testing of the apparatus and method described in the embodiments of the present invention, and can also be through a general programming language (C, C++), Hardware Description Languages (HDL) (including Verilog HDL, VHDL, etc.), or other available programming languages. The software can be configured on any known computer usable medium such as tape, semiconductor, disk, or optical disc (eg CD-ROM, DVD-ROM, etc.), internet, wired, wireless, or other communication medium. Among the transmission methods. The apparatus and method embodiments of the present invention can be included in a semiconductor intellectual property core, such as a microprocessor core (implemented in HDL), and converted into hardware of an integrated circuit product. Furthermore, the apparatus and method of the present invention are implemented by a combination of a hardware and a soft body. Therefore, the invention should not be limited to the disclosed embodiments, but is defined by the scope of the appended claims. In particular, the present invention can be implemented in a microprocessor device for use in a general purpose computer. In the following, the present invention is not limited to the scope of the present invention, and any one of ordinary skill in the art can make a slight difference without departing from the spirit and scope of the present invention. The scope of protection of the present invention is defined by the scope of the appended claims.

Various embodiments of the invention have been described herein, but those skilled in the art should understand that these embodiments are only by way of example and not limitation. Variations in form and detail may be made by those skilled in the art without departing from the spirit of the invention. For example, the software can enable the functions, fabrication, modeling, simulation, description, and/or testing of the apparatus and method described in the embodiments of the present invention, and can also be through a general programming language (C, C++), Hardware Description Languages (HDL) (including Verilog HDL, VHDL, etc.), or other available programming languages. The software can be configured on any known computer usable medium such as tape, semiconductor, disk, or optical disc (eg CD-ROM, DVD-ROM, etc.), internet, wired, wireless, or other communication medium. Among the transmission methods. The apparatus and method embodiments of the present invention can be included in a semiconductor intellectual property core, such as a microprocessor core (implemented in HDL), and converted into hardware of an integrated circuit product. Furthermore, the apparatus and method of the present invention are implemented by a combination of a hardware and a soft body. Therefore, the invention should not be limited to the disclosed embodiments, but is defined by the scope of the appended claims. In particular, the present invention can be implemented in a microprocessor device for use in a general purpose computer. In the following, the present invention is not limited to the scope of the present invention, and any one of ordinary skill in the art can make a slight difference without departing from the spirit and scope of the present invention. The scope of protection of the present invention is defined by the scope of the appended claims.

100‧‧‧Microprocessor

102‧‧‧ instruction cache memory

104‧‧‧ instruction decoder

106‧‧‧Scratchpad alias table

108‧‧‧Reservation station

112‧‧‧Execution unit

132‧‧‧Other execution units

134‧‧‧Load/storage unit

124‧‧‧Prefetching unit

114‧‧‧Retirement unit

116‧‧‧First level data cache memory

118‧‧‧Second level cache memory

122‧‧‧ Busbar interface unit

Claims (29)

A microprocessor includes: a first level cache memory; a second level cache memory; and a prefetch unit configured to: detect the most recent memory present in the second level cache memory Taking a direction and a state of the request, and pre-fetching the plurality of cache lines into the second-level cache memory according to the above direction and the mode; receiving the first level from the first-level cache memory The cache memory receives one of the access requirements, wherein the address is associated with a cache line; determining one or more of the cache lines after the associated direction is indicated by the pattern a cache line; and causing one or more of the cache lines to be prefetched into the first level cache. The microprocessor of claim 1, wherein the pre-fetching unit detects a memory in order to detect the direction and the appearance of the recent access request in the second-level cache memory. In the above direction and mode of the body block, the memory block is a set of memory ranges accessible by the microprocessor; in order to determine the cache line associated with the direction, the pattern is Pointing at one or more cache lines, the prefetching unit: placing the above-mentioned state to the memory block, so that the address is located in the above manner; In the above direction, the search is started from the above address until one of the cache lines indicated by the above-mentioned state is encountered. The microprocessor of claim 2, wherein: the above aspect comprises a sequence of cache lines; wherein the address is located in the above state in order to place the above-mentioned state to the memory block, The prefetching unit is configured to shift the above state to the memory block by the above sequence. The microprocessor of claim 2, wherein the address of the recent access request of the memory block of the memory block that appears in the second-level cache memory is a function of time rather than monotony Increase and decrease sexually. The microprocessor of claim 4, wherein the address of the recent access request of the memory block appearing in the second level cache memory is non-contiguous. The microprocessor of claim 1, further comprising: a plurality of cores; wherein the second level cache memory and the prefetch unit are shared by the core; and each of the cores comprises the first level A distinct instantiation of cache memory. The microprocessor of claim 1, wherein the prefetching unit provides one or more of the above ones in order to cause the one or more cache lines to be prefetched into the first level cache. The address of the line is taken to the first level cache memory, wherein the first level cache system is used to request the one or more cache lines from the second level cache. The microprocessor of claim 7, wherein the first level cache includes a queue for storing the address received from the prefetch unit. The microprocessor of claim 1, wherein the prefetching unit is from one of the microprocessors in order to cause the one or more cache lines to be prefetched into the first level cache. The bus interface unit requires one or more cache lines, and then provides the above-mentioned required cache line to the first level cache. The microprocessor of claim 1, wherein the prefetching unit is cached from the second level in order to cause the one or more cache lines to be prefetched into the first level cache. One or more of the above cache lines are required in the memory. The microprocessor of claim 10, wherein the prefetching unit subsequently supplies the requested cache line to the first level cache line. The microprocessor of claim 10, wherein the second level cache system is subsequently provided to the first level cache line for the required cache line. The microprocessor of claim 1, wherein the step of detecting the direction and the pattern by the prefetching unit comprises: maintaining one of the largest memory blocks when receiving the recent access request. a address and a minimum address, and a change count value of the maximum address and the minimum address; maintaining the above-mentioned recent access request, maintaining the memory block above Determining a history of one of the most recently accessed cache lines associated with the access address; and determining the direction based on the count value; and determining the pattern based on the history record. The microprocessor of claim 13, wherein the step of determining the direction according to the counting value comprises: when a difference between the change count value of the maximum address and the change count value of the minimum address is greater than When a predetermined value is determined, the direction is determined to be upward; and when the difference between the change count value of the minimum address and the change count value of the maximum address is greater than the predetermined value, the direction is determined to be downward. The microprocessor of claim 13, wherein: the history record comprises a one-dimensional mask for indicating a recently accessed cache line associated with the access address of the memory block; When receiving the access request, the prefetching unit further includes the following steps: calculating an intermediate indicator of the most recently accessed cache line in the bit mask; and when the bit is masked in the above The N-bit on the left side of the intermediate indicator is matched with the N-bit of the above-mentioned bit mask on the right side of the above-mentioned intermediate indicator, and is added to each of a plurality of different bit periods for the above-mentioned bit period. A match counter count value, where N is the number of bits in the bit period described above. The microprocessor of claim 15, wherein the step of determining the access mode according to the bit mask comprises: Detecting whether a difference between the matching counter associated with one of the bit periods and the matching counter associated with the other of the bit periods is greater than a predetermined value; and determining that the bit mask is in the middle The access pattern specified by one of the N bits of the indicator, where N is the number of bits of one of the bit periods, and the associated matching counter of the one of the bit periods has the same bit The difference between the relevant matching counters possessed by the other of the meta-periods is greater than the predetermined value described above. A data prefetching method for prefetching data to a first level cache memory of a microprocessor having a second level cache memory, wherein the data prefetching method comprises: detecting occurrence in the second The direction and the state of the most recent access request in the cache memory, and prefetching the plurality of cache lines into the second level cache according to the above direction and the pattern; Taking a memory, receiving an address of one of the access requirements received by the first-level cache, wherein the address is associated with a cache line; determining the cache line associated with the direction is One or more cache lines as indicated by the pattern; and causing one or more of the cache lines to be prefetched into the first level of cache memory. The data pre-fetching method of claim 17, wherein the detecting the presence of the direction and the state of the recent access request in the second-level cache memory includes detecting a memory Body block In the above direction and mode, the memory block is a set of memory ranges accessible by the microprocessor; determining one or more points indicated by the above state after the cache line associated with the direction The steps of the cache line include: placing the above-mentioned state to the memory block such that the address is located in the above-mentioned state; and starting in the above direction, starting from the above address until the above-mentioned mode is encountered One of the cache lines pointed out. The data prefetching method according to claim 18, wherein the aspect includes the order of one of the cache lines, and the step of placing the above-mentioned state to the memory block, so that the address is located in the above manner The method includes transferring the above-described aspect to the memory block by the above sequence. The data prefetching method of claim 18, wherein the address of the recent access request of the memory block that appears in the second level cache memory is a function of time rather than Increasingly and decreasing monotonously. The data prefetching method according to claim 20, wherein the address of the recent access request of the memory block appearing in the second level cache memory may be discontinuous. The data prefetching method according to claim 17, wherein the microprocessor further includes a plurality of cores, and the second level cache memory and the prefetch unit are shared by the core, and each of the cores is An example of one of the above first-level cache memories is different. For example, the data pre-fetching method described in claim 17 of the patent application, which results in The step of prefetching one or more cache lines to the first level cache memory, including one of the microprocessor prefetch units for providing the address of the one or more cache lines to the foregoing The first-level cache memory, wherein the first-level cache memory system is configured to request the one or more cache lines from the second-level cache memory. The data prefetching method of claim 17, wherein the step of causing the one or more cache lines to be prefetched to the first level cache memory comprises one of the microprocessor prefetch units And providing the address of the one or more cache lines to the first level cache memory, wherein the first level cache memory is used by one of the microprocessor bus interface units to request the one Or a plurality of cache lines, and then one or more cache lines of the above requirements are provided to the first level cache. The data prefetching method of claim 17, wherein the step of causing the one or more cache lines to be prefetched to the first level cache memory comprises: using the prefetch unit The one or more cache lines are required in the second level cache. The method of prefetching data according to claim 25, wherein the step of causing the one or more cache lines to be prefetched to the first level cache memory comprises the step of using the prefetch unit One or more cache lines are required to be subsequently provided to the first level cache line described above. The data prefetching method described in claim 25, further comprising the second level cache memory system for subsequently providing the requested one or more cache lines to the first level cache line. A computer program product encoded on at least one computer readable medium, And the computer program product includes: a computer readable program code stored in the computer readable medium for defining a microprocessor, the computer readable program comprising: a first code For defining a first level cache memory device; a second code for defining a second level cache memory device; and a third code for defining a prefetch unit to enable the The prefetching unit is configured to: detect a direction and a state of a recent access request appearing in the second-level cache memory, and prefetch the plurality of cache lines to the second according to the direction and the manner Level Cache memory; receiving, from the first level cache memory, one of the access requirements received by the first level cache memory, wherein the address is associated with a cache line; One or more cache lines indicated by the above-described state after the cache line associated with the above direction; and causing the one or more cache lines to be prefetched into the first level cache. The computer program product of claim 28, wherein the at least one computer readable medium is selected from a disc, tape or other magnetic, optical or electronic storage medium and a network, line, wireless or Other communication media.