Multi-level tracking of in-use state of cache lines

Patent metadata

Field	Value
Publication number	US-9348591-B2
Application number	US-201113992729-A
Country	US
Kind code	B2
Filing date	Dec 29, 2011
Priority date	Dec 29, 2011
Publication date	May 24, 2016
Grant date	May 24, 2016

Abstract

This disclosure includes tracking of in-use states of cache lines to improve throughput of pipelines and thus increase performance of processors. Access data for a number of sets of instructions stored in an instruction cache may be tracked using an in-use array in a first array until the data for one or more of those sets reach a threshold condition. A second array may then be used as the in-use array to track the sets of instructions after a micro-operation is inserted into the pipeline. When the micro-operation retires from the pipeline, the first array may be cleared. The process may repeat after the second array reaches the threshold condition. During the tracking, an in-use state for an instruction line may be detected by inspecting a corresponding bit in each of the arrays. Additional arrays may also be used to track the in-use state.

First claim

What is claimed is:

1. A computer-implemented method comprising:
pointing an array selector to a first array;
tracking an in-use state of a plurality of instructions in the first array until the tracked in-use state of the plurality of instructions reaches a threshold condition;
redirecting the array selector to a second array;
inserting a marker operation into a pipeline;
tracking another in-use state of the plurality of instructions in the second array at least while the marker operation is in the pipeline;
clearing the in-use state of the plurality of instructions in the first array in response to retirement of the marker operation from the pipeline; and
allocating an entry storage in the plurality of instructions based at least in part on the in-use state tracked by the first and second arrays.

2. The method as recited in claim 1 , wherein the detecting whether to allocate the entry storage in the plurality of instructions uses a binary OR operation of corresponding bits in the first and second arrays to detect whether a bit is in the in-use state.

3. The method as recited in claim 1 , wherein the tracking of the in-use state of the plurality of instructions in the second array continues at least until (i) the tracked in-use state of the plurality of instructions in the second array reaches the threshold condition and (ii) the in-use state of the plurality of instructions in the first array are cleared.

4. The method as recited in claim 1 , wherein the marker includes a physical identifier that indicates which array is to be cleared following retirement of the marker.

5. The method as recited in claim 1 , wherein the in-use state tracks access data in an in-use array as a hit or a fill associated with one of the plurality of instructions.

6. The method as recited in claim 1 , wherein the tracking another in-use state of the plurality of instructions in the second array occurs until the tracked in-use state of the plurality of instructions reaches the threshold condition; and further comprising:
redirecting the array selector to a third array; and
inserting another marker operation into the pipeline.

7. An apparatus comprising:
a storage unit having at least a first array and a second array having a plurality of entries to store an in-use array corresponding to a plurality of instructions, the in-use array indicating an in-use state for corresponding instructions;
a first logic to detect when the in-use array stored in the first array reaches a threshold condition;
a second logic to track the in-use array in the first array until the in-use array in the first array reaches the threshold condition;
a third logic to, when the in-use array of the first array reaches the threshold condition, perform acts including:
insert a marker operation into a pipeline,
track the in-use array in the second array, and
clear the in-use array from the first array in response to a retirement of the marker operation from the pipeline; and

a fourth logic to allocate an entry storage in one of the plurality of instructions based at least in part on the in-use array in the first and second arrays that track the in-use state of the plurality of entries.

8. The apparatus as recited in claim 7 , wherein the third logic further is to update an active array pointer from the first array to the second array prior to tracking the in-use array in the second array.

9. The apparatus as recited in claim 7 , wherein the in-use array indicates a hit or a fill associated with one of the plurality of instructions.

10. The apparatus as recited in claim 7 , wherein the marker includes a physical identifier that indicates which array is to be cleared following retirement of the marker.

11. The apparatus as recited in claim 7 , wherein the fourth logic is to detect whether to allocate the entry storage in the plurality of instructions using a binary OR operation of corresponding bits in the first and second arrays to detect whether a bit is in the in-use state.

12. The apparatus as recited in claim 7 , wherein the third logic is to track the in-use state of the plurality of instructions in the second array at least until (i) the tracked in-use state of the plurality of instructions in the second array reaches the threshold condition and (ii) the in-use state of the plurality of instructions in the first array are cleared.

13. The apparatus as recited in claim 7 , wherein the first logic is to detect when the in-use array stored in the second array reaches a threshold condition; and wherein the second logic tracks the in-use array in the second array until the in-use array in the second array reaches the threshold condition.

14. The apparatus as recited in claim 13 , wherein the third logic, when the second logic detects that the in-use array of the second array reaches the threshold condition, is to perform acts including:
insert another marker operation into the pipeline, and
track the in-use array in a third array.

Assignees

• Kim Ilhyun
• Koren Chen
• Farcy Alexandre J
• Hinton Robert L
• Khor Choon Wei
• Rappoport Lihu
• Intel Corp

Inventors

• Kim Ilhyun
• Koren Chen
• Farcy Alexandre J
• Hinton Robert L
• Khor Choon Wei
• Rappoport Lihu

Classifications

• G06F9/3814 Primary

  Implementation provisions of instruction buffers, e.g. prefetch buffer; banks · CPC title

• G06F9/30079 Primary

  Pipeline control instructions, e.g. multicycle NOP · CPC title

• G06F9/30047

  Prefetch instructions; cache control instructions · CPC title