Hierarchical metadata predictor with periodic updates

A system includes a hierarchical metadata predictor and a processing circuit. The hierarchical metadata predictor includes a first-level metadata predictor and a second-level metadata predictor. The processing circuit is configured to perform a plurality of operations including storing new or updated metadata into the first-level metadata predictor and searching the first-level metadata predictor for a metadata prediction. Responsive to finding the metadata prediction in the first-level metadata predictor, the metadata prediction is output corresponding to an entry of the first-level metadata predictor that is a hit. One or more entries of the first-level metadata predictor that are non-hits are periodically written to the second-level metadata predictor. The first-level metadata predictor is updated based on locating the metadata prediction in the second-level metadata predictor.

BACKGROUND

The present invention relates to computer systems, and more particularly, to a hierarchical metadata predictor with periodic updates.

Various predictors can be incorporated in a pipelined high-frequency microprocessor. Predictors can track various types of metadata for predictions, such as making branch instruction predictions. With respect to branch instructions, metadata prediction can be used to predict the direction (taken vs. not taken) and the target address of each branch instruction. This can allow processing to continue along a predicted path of a branch rather than having to wait for the outcome of the branch to be determined. A penalty is incurred if a branch is predicted incorrectly. A pipelined branch predictor takes several cycles to make a prediction.

Traditionally, branch prediction is used to steer the flow of instructions down a processor pipeline along the most likely path of code to be executed within a program. Branch prediction uses historical information to predict whether or not a given branch will be taken or not taken, such as predicting which portion of code included in an IF-THEN-ELSE structure will be executed based on which portion of code was executed in the past. The target of the branch that is expected to be the first taken branch is then fetched and speculatively executed. If it is later determined that the prediction was wrong, then the speculatively executed or partially executed instructions are discarded and the pipeline starts over with the instruction proceeding to branch with the correct branch path, incurring a delay between the branch and the next instruction to be executed. Branch prediction structures have limited storage capacity and are constrained by access and search times.

SUMMARY

According to a non-limiting embodiment, a system includes a hierarchical metadata predictor and a processing circuit. The hierarchical metadata predictor includes a first-level metadata predictor and a second-level metadata predictor. The processing circuit is configured to perform a plurality of operations including storing new or updated metadata into the first-level metadata predictor and searching the first-level metadata predictor for a metadata prediction. Responsive to finding the metadata prediction in the first-level metadata predictor, the metadata prediction is output corresponding to an entry of the first-level metadata predictor that is a hit. One or more entries of the first-level metadata predictor that are non-hits are periodically written to the second-level metadata predictor. The first-level metadata predictor is updated based on locating the metadata prediction in the second-level metadata predictor.

According to a non-limiting embodiment, a method includes storing, by a processing circuit, new or updated metadata into a first-level metadata predictor of a hierarchical metadata predictor. The processing circuit can search the first-level metadata predictor for a metadata prediction. Responsive to finding the metadata prediction in the first-level metadata predictor, the metadata prediction corresponding to an entry of the first-level metadata predictor that is a hit can be output. Periodically one or more entries of the first-level metadata predictor that are non-hits can be written to a second-level metadata predictor of the hierarchical metadata predictor. The first-level metadata predictor can be updated based on locating the metadata prediction in the second-level metadata predictor.

According to a non-limiting embodiment, a computer program product includes a computer readable storage medium having program instructions embodied therewith. The program instructions are executable by a processing circuit to perform a plurality of operations including storing new or updated metadata into a first-level metadata predictor of a hierarchical metadata predictor and searching the first-level metadata predictor for a metadata prediction. Responsive to finding the metadata prediction in the first-level metadata predictor, the metadata prediction corresponding to an entry of the first-level metadata predictor that is a hit can be output. Periodically one or more entries of the first-level metadata predictor that are non-hits can be written to a second-level metadata predictor of the hierarchical metadata predictor. The first-level metadata predictor can be updated based on locating the metadata prediction in the second-level metadata predictor.

DETAILED DESCRIPTION

Turning now to an overview of technologies that are more specifically relevant to aspects of the invention, in computer systems, metadata prediction can be implemented using a plurality of structures in one or more processors. A branch target buffer (BTB) is a structure that stores branch and target information for branch prediction, as one example of metadata prediction. Other structures, such as a branch history table (BHT), pattern history table (PHT), and multiple target table (MTT), can be included to store additional information used for branch direction and target prediction, as other examples of metadata prediction.

A BTB can be searched in parallel to and independently from instruction fetching to find upcoming branches, in which case it is called “lookahead branch prediction”. Alternatively, the BTB can be accessed simultaneously with or after fetching instructions and determining instruction boundaries in order to provide a prediction for each encountered branch instruction, in which case it is called “synchronous branch prediction”. In either case, the performance benefit of the BTB is a function of the accuracy of the prediction provided by the BTB and the latency to access the BTB.

Branches can be stored in BTBs and other structures as a function of a branch instruction address. Some bits of the branch instruction address can be used to index tables, and additional bits can be used as tags within the entries to reduce aliasing.

As with instruction and data caches, metadata predictors can be organized in a hierarchical way with several structures with various capacities and latencies. Unlike instruction and data caches, there is additional flexibility in the design considerations of metadata caches since prediction metadata can be wrong. Metadata predictors can be tagless or partially tagged. Further, metadata predictors can be allowed to contain duplicate data. Metadata hierarchies may not be strictly exclusive or inclusive across each level.

One approach to implementing a hierarchical metadata predictor includes using an intermediate structure, such as a BTB preload table (BTBP), which can be searched in parallel with a first-level BTB and serve as a filter to prevent hits from other levels of the hierarchy from creating duplicates in the first-level BTB. A BTBP can also serve as a victim buffer for predictions evicted out of the first-level BTB. While a BTBP can provide a number of advantages, the BTBP may consume a large quantity of resources, such as physical space and power, which can limit the availability of those resources for other structures within a processor.

Turning now to an overview of the aspects of the invention, one or more embodiments of the invention address the above-described shortcomings of the prior art by performing semi-inclusive hierarchical metadata prediction that allows a hierarchical metadata predictor to be periodically updated in multiple levels of prediction structures. Periodic updates can provide an efficient way of updating prediction information in one or more higher levels of the hierarchy. The hierarchical metadata predictor may use read-before-write directories to prevent duplication. Update policies, such as overwriting least-recently-used (LRU) entries, and events triggering writes to LRU states to make entries most-recently-used in the various hierarchies can encourage inclusivity within the hierarchical metadata predictor.

The above-described aspects of the invention address the shortcomings of the prior art by incorporating a hierarchical metadata predictor in a processing system. Managing installation, updates, and movement of entries between multiple levels of a hierarchical metadata predictor can enable a semi-inclusive structure for metadata prediction as further described herein. Technical effects and benefits can include eliminating intermediate predictor structures, such as a BTBP, to free chip area and power for other structures or larger predictor structure sizes.

Turning now to a more detailed description of aspects of the present invention,FIG. 1depicts computer system100, which is an example of a system that includes embodiments of the present invention. Computer system100includes communications fabric102, which provides communications between computer processor(s)104including metadata predictors105and predictor control107, memory106, persistent storage108, communications unit110, input/output (I/O) interface(s)112, and cache116. Communications fabric102can be implemented with any architecture designed for passing data and/or control information between processors (such as microprocessors, communications and network processors, etc.), system memory, peripheral devices, and any other hardware components within a system. For example, communications fabric102can be implemented with one or more buses.

Memory106and persistent storage108are computer readable storage media. In this embodiment, memory106includes random access memory (RAM). In general, memory106can include any suitable volatile or non-volatile computer readable storage media. Cache116is a fast memory that enhances the performance of processors104by holding recently accessed data and data near accessed data from memory106. Cache116can be distributed within and/or external to processors104and may include instructions (e.g., Icache) and/or data (e.g., Dcache).

Program instructions and data used to practice embodiments may be stored in persistent storage108for execution by one or more of the respective processors104via cache116and one or more memories of memory106. In an embodiment, persistent storage108includes a magnetic hard disk drive. Alternatively, or in addition to a magnetic hard disk drive, persistent storage108can include a solid state hard drive, a semiconductor storage device, read-only memory (ROM), erasable programmable read-only memory (EPROM), flash memory, or any other computer readable storage media that is capable of storing program instructions or digital information.

Communications unit110, in these examples, provides for communications with other data processing systems or devices. In these examples, communications unit110includes one or more network interface cards. Communications unit110may provide communications through the use of either or both physical and wireless communications links. Program instructions and data used to practice embodiments may be downloaded to persistent storage108through communications unit110.

I/O interface(s)112allows for input and output of data with other devices that may be connected to each computer system. For example, I/O interface112may provide a connection to external devices118such as a keyboard, keypad, a touch screen, and/or some other suitable input device. External devices118can also include portable computer readable storage media such as, for example, thumb drives, portable optical or magnetic disks, and memory cards. Software and data used to practice embodiments of can be stored on such portable computer readable storage media and can be loaded onto persistent storage108via I/O interface(s)112. I/O interface(s)112also connect to a display120. Display120provides a mechanism to display data to a user and can be, for example, a computer monitor.

Metadata predictors105and predictor control107can include one or more sets of hardware logic components capable of making and storing predictions for the location of branches, direction of branches, and other such information for an instruction stream of the processor(s)104, for example, as processing circuitry of the processor(s)104. Example embodiments of the metadata predictors105and predictor control107are further described herein in reference toFIGS. 2-6.

FIG. 2depicts a system200including a hierarchical metadata predictor205as an embodiment of the metadata predictors105ofFIG. 1and a hierarchical predictor control207as an embodiment of the predictor control107ofFIG. 1. The example hierarchical metadata predictor205ofFIG. 2includes a first-level metadata predictor204and a second-level metadata predictor206. The system200can also include auxiliary structures to support prediction, such as various target tables, history tables, indexing controls, and the like. The hierarchical predictor control207controls access and updates of entries in the first-level metadata predictor204and the second-level metadata predictor206. In an exemplary embodiment, the first-level metadata predictor204is a primary predictor, and the second-level metadata predictor206is a secondary predictor. The hierarchical predictor control207can handle various events, such as an install208, an update210, a search212, and/or other events (not depicted). Results of the search212can result in outputting of a metadata prediction214, such as a predicted branch instruction address, branch direction, or other such metadata associated with patterns of instruction execution.

Each of the first-level metadata predictor204and second-level metadata predictor206can be set associative, including multiple sets of entries. The second-level metadata predictor206is a higher-level cache of metadata prediction information. The capacity of the second-level metadata predictor206can be greater than the capacity of the first-level metadata predictor204to store entries. The first-level metadata predictor204can cover a larger or equal to footprint than an instruction cache of the cache116ofFIG. 1. For purposes of explanation, examples of the hierarchical metadata predictor205and hierarchical predictor control207are described with respect to branch prediction using multiple levels of BTBs. Although the example ofFIG. 2depicts a two-level hierarchy, it will be understood that embodiments can include additional levels.

A general example of a BTB entry is depicted inFIG. 3as BTB entry300(also referred to as entry300), which can include a branch address tag302and a predicted target address306. With continued reference toFIGS. 1-3, the branch address tag302can be used to locate an entry within a BTB row310, where each of the first-level metadata predictor204and second-level metadata predictor206ofFIG. 2can include multiple BTB rows310and multiple set associative BTB entries per BTB row310. The first-level metadata predictor204and second-level metadata predictor206can have different numbers of BTB rows310and columns (also referred to as “ways”) relative to each other. The BTB rows310can be indexed with instruction address bits. For example, bits 48:58 of a 64-bit address may be used as an index per BTB row310. Additional address bits can be stored as tag bits (e.g., branch address tag302) within each entry300. Each BTB entry300can include other branch prediction information (not depicted), such as a branch direction to indicate whether the associated branch was taken or not taken.

In an exemplary embodiment, a search address corresponding to a restart of instruction fetching in processors104ofFIG. 1can be sent to the hierarchical predictor control207as search212, and the hierarchical predictor control207can thereafter operate asynchronously from instruction fetching until the next restart. When looking for branch predictions, the first-level metadata predictor204is read and can provide a branch prediction as the metadata prediction214if it contains an entry with a branch address tag302matching the search address. The first-level metadata predictor204provides input to the hierarchical predictor control207to determine whether a match or “hit” is located based on the search address. If a match is found, the hierarchical predictor control207can output a predicted target address and/or branch direction as the metadata prediction214. If a match is not found, sequential searching of the first-level metadata predictor204can continue over a search range before declaring a miss (i.e., a non-hit) and taking further action through the second-level metadata predictor206.

The search range of the first-level metadata predictor204can be established by the hierarchical predictor control207. In embodiments, the hierarchical predictor control207can determine a predicted stream length between an instruction address and a taken branch ending an instruction stream. The first-level metadata predictor204can be searched for a branch prediction in one or more entries300in a search range bounded by the instruction address and the predicted stream length. A search of the second-level metadata predictor206can be triggered based on failing to locate the branch prediction in the search range. Branch prediction information found in the second-level metadata predictor206can be used directly by the hierarchical predictor control207to make a metadata prediction214directly. Alternatively, such prediction information can be treated as a bulk preload of likely to be useful information that is written into the first-level metadata predictor204for future use but not used immediately and directly from the second-level metadata predictor206.

FIG. 4is a block diagram illustrating a write control400for the hierarchical metadata predictor205ofFIG. 2according to a non-limiting embodiment of the present invention. New metadata, from surprise branches encountered in processors104, or from architected preload instructions, or any other source, can be installed as surprise installs408into both the first-level metadata predictor204and second-level metadata predictor206. Write queues402and write pipelines404can hold the data until access to write ports of the first-level metadata predictor204and/or second-level metadata predictor206is available.

For example, more incoming write requests can occur than write ports exist on the first-level metadata predictor204and/or second-level metadata predictor206. Further, there may be limitations on whether or not simultaneous writes and reads can occur, resulting in a delay of writes. Upon a new install, if least-recently-used (LRU) information is being maintained due to the structures being organized in a set-associative way, the newly installed entries can be made most-recently-used (MRU) in both levels of the hierarchy. Whenever hits are found in the second-level metadata predictor206and are to be written into the first-level metadata predictor204, the hits can also be written into write queues402.

For writes queues402holding writes going into the first-level metadata predictor204, they can be organized as a single queue for all sources of writes, or a set of queues divided by source. Priority logic can choose which writes to take out of the write queues402on a particular cycle and put into the write pipeline404. As an example, a single write can be chosen per cycle. For installs, the write pipeline404can index the first-level metadata predictor204directory for reading. The directory can contain a subset of the full entry information—specifically validating information and the tags required to determine hit vs miss. Therefore, it is not necessary to read all entry content. This can be performed to check whether or not the information to install already exists in the first-level metadata predictor204to avoid duplication. There can be dedicated read ports for performing reads, or the same read ports used for regular searching can be used with arbitration logic to decide on a particular cycle about how to use each read port. If the data being searched for in the first-level metadata predictor204directory already exists, then no write would occur. Otherwise, the new data can be written in the first-level metadata predictor204. With LRU replacement algorithms, the least-recently used entry can be replaced. For some types of write requests, such as dynamic updates410, where prediction information is being updated for branches that were predicted from the first-level metadata predictor204, the logic of the hierarchical predictor control207can assume that the branch is already present in the first-level metadata predictor204and skip read-before-write duplicate checking process.

FIG. 5is a block diagram illustrating a periodic update control500for the hierarchical metadata predictor205ofFIG. 2according to a non-limiting embodiment of the present invention. The periodic update control500is described with respect toFIGS. 1-5. Search logic502may search the first-level metadata predictor204. Searching of the first-level metadata predictor204can be performed in an asynchronous lookahead manner from the rest of the pipeline of processors104or may be performed in-line with instruction fetching, or decode, or any other stage in the processor pipeline. Searching, by search logic502, can result in periodically writing non-hits into the second-level metadata predictor206and making MRU in the second-level metadata predictor206at that time through update selection504. The search logic502and update selection504can be part of the hierarchical predictor control207.

The first-level metadata predictor204can track a location (e.g., index, column/way) in the second-level metadata predictor206in which a corresponding branch exists. Index information can be a function of the already existing/known index and tag information of the first-level metadata predictor204. Second-level metadata predictor206column information may be maintained for this purpose. Update selection504logic can determine when and which branch information to write into the second-level metadata predictor206.

There are many ways the update selection504logic can be implemented. For example, change bits can be maintained in the first-level metadata predictor204indicating when content has changed and needs to be written. A set of approaches can maintain a non-hit counter506indicative of how often valid non-hits are encountered. Once a counter threshold508has been reached, a periodic update can be performed. When performing a periodic update, information at risk for being evicted from the first-level metadata predictor204can be selected. One way to do this can include reading the first-level metadata predictor204LRU with the search logic502and choosing an LRU column without a hit in a row being currently accessed. Alternatively, without having to read the first-level metadata predictor204LRU, a current first-level metadata predictor204column selection state can be selected that steps through the first-level metadata predictor204columns and gets incremented upon hitting the counter threshold508or another threshold. Upon hitting the counter threshold508a valid non-hit can be selected in a specified column, if there is one. Otherwise, a fixed order can be used to select from that point, i.e., search the columns in order starting from the “current column selection state”. Alternatively, if the current column does not contain a valid non-hit, the update selection504may choose to not refresh anything and wait until there is a valid non-hit in that column. Upon updating, if LRU is maintained in the second-level metadata predictor206, the entry being refreshed can be made MRU. Periodic refreshes can ensure that up to date prediction information is maintained in the second-level metadata predictor206. Further, entries can be kept active in the second-level metadata predictor206after they have been evicted from the first-level metadata predictor204by making them MRU at around the time of eviction.

Performing periodic updating/refresh at search time instead of at actual eviction time of the first-level metadata predictor204may not require an extra read to get the victim data. Entries may already be read at search time, so it can be more efficient to do an update at that time.

Turning now toFIG. 6, a flow diagram of a process600is generally shown in accordance with an embodiment. The process600is described with reference toFIGS. 1-6and may include additional steps beyond those depicted inFIG. 6. The process600can be performed by a processing circuit of the processors104ofFIG. 1, that may include, for example, the hierarchical predictor control207ofFIG. 2. The example ofFIG. 6is described in reference to one or more entries of the hierarchical metadata predictor205. Notably, when the first-level metadata predictor204and the second-level metadata predictor206are implemented as a set associative caches, each search can have multiple potential hits or misses across a multi-way row, such as row310ofFIG. 3.

At block610, a processing circuit of system200can store new or updated metadata into a first-level metadata predictor204, such as a BTB1. At block620, a processing circuit of the system200can search the first-level metadata predictor204for a metadata prediction214. At block630, if the metadata prediction214is found, the process600can advance to block640. At block640, responsive to finding the metadata prediction214in the first-level metadata predictor204, the system200can output the metadata prediction214corresponding to an entry of the first-level metadata predictor204that is a hit. At block630, if the metadata prediction214is not found, the process600can advance to block650. At block650, the system200can periodically write one or more entries of the first-level metadata predictor204that are non-hits to the second-level metadata predictor206. Block650may also be performed periodically based on a periodic check635regardless of whether a search results in a hit at block630. At block660, the system200can update the first-level metadata predictor204based on locating the metadata prediction214in the second-level metadata predictor206.

The one or more entries of the first-level metadata predictor204that are non-hits can be selected for writing to the second-level metadata predictor206based on using a non-hit counter506to compare with a counter threshold508and stepping through a plurality of columns of the first-level metadata predictor204based on the non-hit counter506reaching the counter threshold508. Alternatively, the one or more entries of the first-level metadata predictor204that are non-hits can be selected for writing to the second-level metadata predictor206based on a least-recently-used indicator associated with the one or more entries.

In embodiments, a new or updated entry of the first-level metadata predictor204can be set as most-recently-used for tracking aging of entries for replacement. The entry of the first-level metadata predictor204can include the hit as most-recently used based on finding the metadata prediction214in the first-level metadata predictor204. The one or more entries written to the second-level metadata predictor206can be set as most-recently used.

In embodiments, branch instruction prediction data associated with one or more surprise branches can be installed into the first-level metadata predictor204and the second-level metadata predictor206. A plurality of entries including the branch instruction prediction data associated with one or more surprise branches can be set as most-recently-used in the first-level metadata predictor204and/or the second-level metadata predictor206.

In embodiments, the second-level metadata predictor206can be set for the metadata prediction. Queuing any hit for writing into the first-level metadata predictor204can be performed through the write queues402. A read-before-write check of the first-level metadata predictor204can be performed based on data in the write queues402and directory information of the first-level metadata predictor204to prevent duplicate installs of metadata in the first-level metadata predictor204.