Age management logic

A system, method and computer program product for maintaining an age and validity of entries in a structure associated with a processor is disclosed. An age tracking matrix is created for the structure. Each row of the age tracking matrix corresponds to an entry of the structure and each column of the age tracking matrix corresponds to an entry of the structure. When initiating an entry: a row corresponding to the entry is determined and a field in the determined row that is on a diagonal of the matrix is marked. For each other field in the determined row, the values that are in a diagonal field that is in a same column of the field are copied into the field. A relative age of the entries is determined by counting a number of marked fields in a column of the age tracking matrix.

BACKGROUND

Embodiments of the present invention relate to maintaining an age order of entries in a processor, and more specifically, to maintaining an age management matrix including age and validity information of entries.

Within a microprocessor, it is often necessary to track age information about processor instructions or instruction addresses using entries in a queue-like structure. One such queue-like structure is a speculatively updated branch predictor which tracks multiple occurrences of process branches in a processor pipeline using speculatively updated branch prediction states prior to completion of the occurrences. Similar structures include issue queues for determining which instructions to issue in an out-of-order design, and fetch queues for determining which instruction addresses or data operand addresses to fetch from a cache or search for in a branch predictor. When attempting to predict a direction (taken vs. not-taken) of a most recent occurrence of a branch, it is necessary to select information from a youngest entry in the speculatively updated structure corresponding to that branch. Age management information entered into the structure should be maintained when entries are added and invalidated. Maintaining age management information is particularly challenging when there can be multiple additions and invalidations per cycle and when invalidations can occur in any order. Current structures employ time-consuming and resource-consuming methods for maintaining and tracking age entries. More efficient methods are needed for managing age ordering information incorporating both age and validity for timing-critical applications.

SUMMARY

According to an embodiment of the present invention, a method of maintaining an age and validity of entries in a structure associated with a processor, includes: creating an age tracking matrix for the structure, wherein each row of the age tracking matrix corresponds to an entry of the structure and each column of the age tracking matrix corresponds to an entry of the structure; for each entry, upon initiation of the entry: determining a row corresponding to the entry, marking a field in the determined row that is on a diagonal of the matrix, and for each other field in the determined row, copy to the field the values that are in a diagonal field that is in a same column of the field; determining a youngest entry of the structure by counting a number of marked fields in a column of the age tracking matrix; and performing an action at the processor using the youngest entry.

According to another embodiment of the present invention, a system for maintaining an age and validity of entries in a structure associated with a processor, the system including: a memory having computer readable instructions; and one or more processors for executing the computer readable instructions, the computer readable instructions including: creating an age tracking matrix for the structure, wherein each row of the age tracking matrix corresponds to an entry of the structure and each column of the age tracking matrix corresponds to an entry of the structure; for each entry, upon initiation of the entry: determining a row corresponding to the entry, marking a field in the determined row that is on a diagonal of the matrix, and for each other field in the determined row, copy to the field the markings that are in a diagonal field that is in a same column of the field; determining a youngest entry in the structure by counting a number of marked fields in a column of the age tracking matrix; and performing an action at the processor using the youngest entry.

According to yet another embodiment of the present invention, a computer program product for maintaining an age and validity of entries in a structure associated with a processor, the computer program product including a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to perform: creating an age tracking matrix for the structure, wherein each row of the age tracking matrix corresponds to an entry of the structure and each column of the age tracking matrix corresponds to an entry of the structure; for each entry, upon initiation of the entry: determining a row corresponding to the entry, marking a field in the determined row that is on a diagonal of the matrix, and for each other field in the determined row, copy to the field the markings that are in a diagonal field that is in a same column of the field; determining a youngest entry in the structure by counting a number of marked fields in a column of the age tracking matrix; and performing an action at the processor using the youngest entry.

DETAILED DESCRIPTION

Embodiments of the present invention provide a system and method for determining an age dependent valid entry in a structure containing a plurality of entries in a time-efficient manner. One example of a structure for which an associated age tracking matrix can be used is a speculatively updated branch predictor which tracks multiple occurrences of process branches in a processor pipeline using speculatively updated branch prediction states prior to completion of the occurrences. In various embodiments, the structure can be a speculative branch prediction table, an issue queue, a cache/branch prediction array index queue, etc. The disclosure employs the use of an age tracking matrix that allows reading of ages along the columns and rows of the matrix. Rows of the matrix are assigned to a selected entry and are marked accordingly when its assigned entry is initiated. The method by which rows are filled in upon initiation automatically sets up the columns of the matrix to indicate which entry is the youngest. The method of removing an invalidated entry further maintains information on the youngest entry in the matrix. Therefore, the youngest entry can be determined via a quick binary operation on the columns of the matrix. Age determination is thus quicker and requires less processor time. When the entries are processes or branches of a job, the youngest entry can be provided to a branch predictor which can perform its branch predictions based on the youngest entry.

One example of a structure for which an associated age tracking matrix can be used is a speculatively updated branch predictor which tracks multiple occurrences of process branches in a processor pipeline using speculatively updated branch prediction states prior to completion of the occurrences. Branch prediction is used in microprocessors to predict a direction (taken vs. not-taken) and sometimes a target address of predicted taken branches. This prediction occurs prior to executing the branch instructions and determines the actual branch direction and target address. By predicting this information early, the processor is able to execute along the predicted path while waiting for a branch outcome to be resolved, thereby more efficiently using processor resources and achieving higher performance.

A conventional Branch History Table (BHT) is a table of 2-bit counters associated with branch instruction addresses in a program. Each counter can be in one of 4 possible states: 0 “strongly not-taken”, 1 “weakly not-taken”, 2 “weakly taken”, and 3 “strongly taken”. Given a prediction for a particular state, if that occurrence of the branch is resolved taken, the state is incremented by 1 (saturating at the maximum value of 3 if already at 3). Similarly if that occurrence of the branch is resolved not-taken, the state is decremented by 1 (saturating at 0 if already at 0). The BHT is updated non-speculatively once an occurrence of a branch instructions completes after the branch direction and target address have been determined and all older instructions in the program have completed. This delay between predicting branches and updating state in the BHT implies that many occurrences of the same branch can be predicted and can be in flight prior to completion of an oldest occurrence.

A speculative branch history table (SBHT) can be used to track speculatively updated BHT state information for branches in flight. This is a fully associative structure with entries allocated upon predicting a branch (in a state requiring a state change under the assumption that the prediction is correct), and upon resolving a branch and learning that its direction prediction was incorrect. Entries are invalidated when their corresponding branches complete. Entries are also invalidated whenever their corresponding branch instructions get flushed out of the pipeline upon realizing they are on a wrong path—for example as the result of an earlier mal-predicted branch direction or target.

The present invention allows efficient tracking of validity and age ordering of the entries in the speculative BHT structure. Specifically, upon making a branch prediction, the present invention can be used to indicate which entry to select—namely the youngest valid entry in the SBHT corresponding the branch instruction being predicted. The present invention can be used for tracking age and validity for any structure associated with a microprocessor. Other examples of such structures are issue queues for determining which instructions to issue in an out-of-order design, and fetch queues for determining which instruction addresses or data operand addresses to fetch from a cache or search for in a branch predictor.

FIG. 1illustrates a processing system100for processing entries in a structure102using an age tracking matrix106according to an exemplary embodiment of the present invention. In many operations, the structure102includes multiple entries, indicated as M entries. Processor104performs operations on the entries of the structure102. The processor104also operates an age tracking matrix106, as disclosed herein. The age tracking matrix106can be used to track the ages and validity of entries of the structure102in order to improve the performance of the processor, reduces the time and energy requirements. The size of the age tracking matrix106is M×M, where M is the number of entries in structure102

FIG. 2shows an exemplary age tracking matrix200that is used to track entries in the structure102associated with a processor (e.g., processor104inFIG. 1) in one embodiment of the present invention. The age tracking matrix200(also referred to herein as “AgeMatrix”) can be a binary matrix, having either ‘0’ or ‘1’ as values in its fields. In the embodiment shown inFIG. 2, an initialized AgeMatrix200is shown having only ‘0’ field value in its fields (i.e., no entries of the structure102are currently being tracked). The AgeMatrix200is an M×M matrix where ‘M’ is greater than or equal to a total number of entries contained in the structure102. A field value in the AgeMatrix200is indicated by AgeMatrix(i,j), wherein the first index (“i”) indicates a row of the matrix and the second index (“j”) indicates a column of the matrix. Each row of the AgeMatrix200corresponds to one of the entries of structure102. For example, in one embodiment, row 1 corresponds to entry 1, row 2 corresponds to entry 2, row 3 corresponds to entry 3, and row M corresponds to entry M. Additionally, each column of the AgeMatrix200corresponds to one of the entries of structure102. For example, column 1 corresponds to entry 1, column 2 corresponds to entry 2, column 3 corresponds to entry 3, and column M corresponds to entry M. The construction of AgeMatrix200is such that an entry in structure102that corresponds to the mthrow of AgeMatrix200also corresponds to the mthcolumn of AgeMatrix200. Thus, fields for which the row index and the column index are the same occur along diagonal202and are referred to herein as “diagonal fields” of AgeMatrix200.FIG. 2shows an initialized AgeMatrix200which is populated with ‘0’ in each field (i.e., AgeMatrix(i,j)=‘0’ for all i,j).

FIGS. 3-6illustrate a method of populating the AgeMatrix200in a manner that allows the operator or processor to track youngest and oldest entries in a time-saving and energy-saving manner. In the AgeMatrix200, tracking the age of an entry in a structure includes the manipulation of field values in rows and columns corresponding to the entry. The dimensions of AgeMatrix200are constant during the age tracking process. Additionally, rows and columns corresponding to structure entry remain fixed within the AgeMatrix200and are not moved around when the structure entry is initiated or cancelled. Thus, many time-consuming and energy-consuming procedures, such as swapping algorithms, are avoided. WhileFIG. 2shows a generalized AgeMatrix200that is M×M in dimension,FIGS. 3-6show only the tracking of only four structure entries for illustrative purposes. Thus, the AgeMatrix200is a 4×4 matrix inFIGS. 3-6.

FIG. 3illustrates a method for tracking a first structure entry in the AgeMatrix200when the first structure entry is initiated. When a structure entry is initiated, the row in AgeMatrix200corresponding to the structure entry is located or determined. Then, a two-step procedure is followed to populate the fields of the determined row. These two steps can be performed separately or concurrently. In a first step, the field that is a diagonal field in the corresponding row is filled in with a ‘1’ or similar binary entry value. In other words AgeMatrix(n,n)=‘1’, where ‘n’ is the index of the corresponding row. In a second step, the field values in the other diagonal fields are copied to the fields in the corresponding row, such that the field value in a diagonal field for a selected column is copied to a field in the corresponding row that is in the same selected column. In other words, the copying process {AgeMatrix (i,i)→ AgeMatrix(n,i)} is performed, where ‘n’ is the index of the corresponding row. This procedure for populating the corresponding row is illustrated inFIG. 3, which shows row 4 (corresponding to entry 1) being populated. Therefore, when initiating the structure entry corresponding to row 4, in the first step the diagonal field302of row 4 is filled with ‘1’ (AgeMatrix(4,4)=‘1’). In the second step: the diagonal field314corresponding to row 1, column 1 is copied to the field304that is in row 4 (i.e., AgeMatrix(1,1)→ AgeMatrix(4,1)); the diagonal field316corresponding to row 2, column 2 is copied to the field306of row 2, column 2 (i.e., AgeMatrix(2,2)→ AgeMatrix(4,2)); and the diagonal field318corresponding to row 3, column 3 is copied to field308in row 4, column 3 (i.e., AgeMatrix(3,3)→ AgeMatrix(4,3)). This copying process is also illustrated by arrows324,326and328. Arrow324illustrates the copying step of AgeMatrix (1,1)→ AgeMatrix(4,1). Arrow326illustrates the step of AgeMatrix (2,2)→ AgeMatrix(4,2). Arrow328illustrates the step of AgeMatrix (3,3)→ AgeMatrix(4,3). Since no other structure entry are currently running, this copying step yields only ‘0’ values being copied into the fields304,306and308.

FIG. 4illustrates initiating a second structure entry in the AgeMatrix200after the first structure entry has been initiated. The second structure entry corresponds to row 2. In the first step, AgeMatrix(2,2) (field402) is filled with field value ‘1’. In the second step, the value in diagonal field AgeMatrix (1,1) is copied to AgeMatrix(2,1), the value in diagonal field AgeMatrix(3,3) is copied to AgeMatrix(2,3) and the value in diagonal field AgeMatrix(4,4) is copied to AgeMatrix(2,4). These copying steps are indicated by arrows404,406and408, respectively. Since the first structure entry has previously been initiated, this leads to a ‘1’ value being copied into AgeMatrix(2,4).

FIG. 5illustrates initiating a third structure entry in the AgeMatrix200after the first structure entry and second structure entry have been initiated. The third structure entry corresponds to row 1. (Note, the third entry also corresponds to column 1.) In the first step, AgeMatrix(1,1) (field502) is filled with field value ‘1’. In the second step, the value in diagonal field AgeMatrix(2,2) is copied to AgeMatrix(1,2), the value in diagonal field AgeMatrix(3,3) is copied to AgeMatrix(1,3) and the value in diagonal field AgeMatrix(4,4) is copied to AgeMatrix(1,4). These copying steps are indicated by arrows504,506and508, respectively. Since the first structure entry and second structure entry have been initiated previously, a ‘1’ value is copied into AgeMatrix(1,2) and a ‘1’ value is copied into AgeMatrix(1,4).

FIG. 6illustrates initiating a fourth structure entry in the AgeMatrix200after the first, second and third structure entries have been initiated. The fourth structure entry corresponds to row 3. (Note, the fourth structure entry also correspond to column 3.) In the first step, AgeMatrix(3,3) (field602) is filled with field value ‘1’. In the second step, the value in diagonal field AgeMatrix(1,1) is copied to AgeMatrix(3,1), the value in diagonal field AgeMatrix(2,2) is copied to AgeMatrix(3,2) and the value in diagonal field AgeMatrix(4,4) is copied to AgeMatrix(3,4). These copying steps are indicated by arrows604,606and608, respectively. Since the first, second and third structure entry have been initiated previously, ‘1’ values are into AgeMatrix(3,1), AgeMatrix(3,2) and AgeMatrix(3,4).

FIGS. 3-6may now be reviewed to illustrate how oldest and youngest entries are determined use AgeMatrix200. The youngest structure entry corresponds to the column that has only one ‘1’ value in the column, with all other values in the column being ‘0’. A calculation referring to as a ‘OneHot’ calculation can be applied to each column in order to determine which column is in this state, and therefore which structure entry is the youngest. The oldest structure entry corresponds to the row that has only one ‘1’ value in the row, with all other values in the row being ‘0’. The ‘OneHot’ calculation can be applied to each row in order to determine which row is in this state, and therefore which structure entry is the oldest.

Referring back toFIG. 3, performing a OneHot calculation on each row indicates that Row 4 has only one ‘1’ value and that Column 4 has only one ‘1’ value. This indicates that structure entry 1 (corresponding to row 4) is the oldest structure entry being run and that structure entry 1 (corresponding to column 4) is also the youngest structure entry. This is evident in the fact that structure entry 1 is the only structure entry being run.

Referring now toFIG. 4, performing a OneHot calculation on each row indicates that Row 4 (corresponding to structure entry 1) has only one ‘1’ value. Therefore, structure entry 1 is the oldest structure entry being run. A OneHot calculation on each column indicates that Column 2 (corresponding to structure entry 2) is has only one ‘1’ value. Therefore, structure entry 2 is the youngest structure entry being run.

Referring now toFIG. 5, performing a OneHot calculation on each row indicates that Row 4 (corresponding to structure entry 1) has only one ‘1’ value. Therefore, structure entry 1 is the oldest structure entry being run. A OneHot calculation on each column indicates that Column 1 (corresponding to structure entry 3) is has only one ‘1’ value. Therefore, structure entry 3 is the youngest structure entry being run.

Referring now toFIG. 6, performing a OneHot calculation on each row indicates that Row 4 (corresponding to structure entry 1) has only one ‘1’ value. Therefore, entry 1 is the oldest structure entry being run. A OneHot calculation on each column indicates that Column 3 (corresponding to structure entry 4) is has only one ‘1’ value. Therefore, structure entry 4 is the youngest structure entry being run.

It is to be noted that the second youngest structure entry can also be tracked using a calculation that determines which column has only two occurrences of a ‘1’ value. Similarly, the second oldest structure entry can be tracked using a calculation that determines which row has only two occurrences of a ‘1’ value.

FIGS. 7-8illustrate operations of the AgeMatrix200when a structure entry is invalidated or otherwise cancelled from the AgeMatrix200. When a structure entry is invalidated, ‘0’ values are placed in the fields of each row corresponding to the structure entry and of each column corresponding to the structure entry. InFIG. 7, the structure entry 2 (corresponding to row 2 and to column 2) is removed from the age matrix shown inFIG. 6by placing ‘0’ in all of the fields of row 2 and all of the fields of column 2. Using the OneHot calculations illustrated inFIGS. 3-6, it is evident that structure entry 1 (corresponding to row 4) is still the oldest structure entry and structure entry 4 (corresponding to column 3) remains the youngest structure entry.

FIG. 8illustrates cancellation of another structure entry from AgeMatrix200. The structure entry 4 (corresponding to row 3 and to column 3) is removed from the age matrix shown inFIG. 7by placing ‘0’ in all of the fields of row 3 and all of the fields of column 3. Using the OneHot calculations disclosed herein, it is evident that structure entry 1 (corresponding to row 4) is still the oldest structure entry and structure entry 3 (corresponding to column 1) is now the youngest structure entry.

The use of AgeMatrix200to track structure entry ages simplifies the logic used in determining structure entry ages. Additionally, management of the AgeMatrix200is simplified. The number of procedural steps required to maintain the AgeMatrix200is significantly fewer than the steps required for maintenance of other age tracking methods. Invalidation of structure entries is also performed by a simple method of changing the values of fields for the row and column corresponding to the structure entry, rather than removing or shifting a field entry for the structure entry. Since there is no shifting of field entries, the AgeMatrix200requires less dynamic power consumption. Additionally, the method can be scaled to any size project or any number or types of structures. Age order can be maintained for multiple structure entries and branch addresses. The youngest structure entry in the AgeMatrix200can be provided to a branch history table to allow the table to perform a branch prediction using the youngest structure entry.

FIG. 9illustrates a block diagram of a computer system900for use in implementing a system or method according to some embodiments. The systems and methods described herein may be implemented in hardware, software (e.g., firmware), or a combination thereof. In some embodiments, the methods described may be implemented, at least in part, in hardware and may be part of the microprocessor of a special or general-purpose computer system900, such as a personal computer, workstation, minicomputer, or mainframe computer.

In some embodiments, as shown inFIG. 9, the computer system900includes a processor905, memory910coupled to a memory controller915, and one or more input devices945and/or output devices940, such as peripherals, that are communicatively coupled via a local I/O controller935. These devices940and945may include, for example, a printer, a scanner, a microphone, and the like. Input devices such as a conventional keyboard950and mouse955may be coupled to the I/O controller935. The I/O controller935may be, for example, one or more buses or other wired or wireless connections, as are known in the art. The I/O controller935may have additional elements, which are omitted for simplicity, such as controllers, buffers (caches), drivers, repeaters, and receivers, to enable communications.

The processor905is a hardware device for executing hardware instructions or software, particularly those stored in memory910. The processor905may be a custom made or commercially available processor, a central processing unit (CPU), an auxiliary processor among several processors associated with the computer system900, a semiconductor based microprocessor (in the form of a microchip or chip set), a microprocessor, or other device for executing instructions. The processor905includes a cache970, which may include, but is not limited to, an instruction cache to speed up executable instruction fetch, a data cache to speed up data fetch and store, and a translation lookaside buffer (TLB) used to speed up virtual-to-physical address translation for both executable instructions and data. The cache970may be organized as a hierarchy of more cache levels (L1, L2, etc.).

The memory910may include one or combinations of volatile memory elements (e.g., random access memory, RAM, such as DRAM, SRAM, SDRAM, etc.) and nonvolatile memory elements (e.g., ROM, erasable programmable read only memory (EPROM), electronically erasable programmable read only memory (EEPROM), programmable read only memory (PROM), tape, compact disc read only memory (CD-ROM), disk, diskette, cartridge, cassette or the like, etc.). Moreover, the memory910may incorporate electronic, magnetic, optical, or other types of storage media. Note that the memory910may have a distributed architecture, where various components are situated remote from one another but may be accessed by the processor905.

The instructions in memory910may include one or more separate programs, each of which comprises an ordered listing of executable instructions for implementing logical functions. In the example ofFIG. 9, the instructions in the memory910include a suitable operating system (OS)911. The operating system911essentially may control the execution of other computer programs and provides scheduling, input-output control, file and data management, memory management, and communication control and related services.

Additional data, including, for example, instructions for the processor905or other retrievable information, may be stored in storage920, which may be a storage device such as a hard disk drive or solid state drive. The stored instructions in memory910or in storage920may include those enabling the processor to execute one or more aspects of the systems and methods of this disclosure.

The computer system900may further include a display controller925coupled to a display930. In some embodiments, the computer system900may further include a network interface960for coupling to a network965. The network965may be an IP-based network for communication between the computer system900and an external server, client and the like via a broadband connection. The network965transmits and receives data between the computer system900and external systems. In some embodiments, the network965may be a managed IP network administered by a service provider. The network965may be implemented in a wireless fashion, e.g., using wireless protocols and technologies, such as WiFi, WiMax, etc. The network965may also be a packet-switched network such as a local area network, wide area network, metropolitan area network, the Internet, or other similar type of network environment. The network965may be a fixed wireless network, a wireless local area network (LAN), a wireless wide area network (WAN) a personal area network (PAN), a virtual private network (VPN), intranet or other suitable network system and may include equipment for receiving and transmitting signals.

Systems and methods according to this disclosure may be embodied, in whole or in part, in computer program products or in computer systems900, such as that illustrated inFIG. 9.

Technical effects and benefits include the use of simplified age management logic. The invention provides an easy invalidation procedure for multiple and/or concurrent entries. Furthermore, no shifting of entries (i.e., rows, columns) is performed, leading to less dynamic power consumption. Youngest and oldest entries can be tracked as well as second youngest and second oldest entries. The built-in redundancy of the age tracking matrix can be useful in Reliability, Availability and Serviceability protection. In other words, there can only be one column/row which is identified as youngest/oldest using the OneHot calculation. Age order can be maintained for multiple branch addresses.