Reduced power load/store queue searching by comparing subsets of address bits and enabling second subset comparison based on first subset comparison result

A comparison circuit can reduce the amount of power consumed when searching a load queue or a store queue of a microprocessor. Some embodiments of the comparison circuit use a comparison unit that performs an initial comparison of addresses using a subset of the address bits. If the initial comparison results in a match, a second comparison unit can be enabled to compare another subset of the address bits.

CROSS REFERENCE TO RELATED APPLICATIONS

This application claims the priority benefit of Chinese patent application number 200810246370.8, filed on Dec. 25, 2008, entitled “REDUCED POWER LOAD/STORE QUEUE SEARCHING MECHANISM,” which is hereby incorporated by reference to the maximum extent allowable by law.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The techniques described herein relate generally to microprocessors, and some embodiments in particular relate to reducing power consumption in a load queue and/or a store queue.

2. Discussion of Related Art

Some superscalar microprocessors are capable of executing instructions out of order to improve performance. However, one concern with executing instructions out of order is that a data hazard can be created when different instructions access the same memory location. For example, if a later instruction is executed out of order prior to an earlier instruction, and both instructions access the same memory location, there is a danger that these instructions may process the wrong data to produce an incorrect result.

To address the potential problems of out of order execution, some superscalar processors implement both a load queue and a store queue. In some implementations, a load queue is a data structure that stores addresses and data for completed load instructions that have retrieved data from memory for use by the microprocessor core. In some implementations, a store queue is another data structure that stores addresses and data for store instructions that transfer data from the microprocessor core to memory. The load queue and store queue may maintain the information about load and store instructions until there is no longer the possibility of a data hazard. The load queue and/or store queue may be implemented in the core of a superscalar microprocessor as dedicated data structures for storing information about load instructions and/or store instructions. In some implementations, the load queue and store queue may each be implemented as a dedicated set of registers.

A load queue and store queue can enable a superscalar processor to perform a variety of techniques for improving performance and avoiding data hazards, including techniques such as store-to-load data forwarding, memory disambiguation, and in-order store retirement. Previously, store-to-load data forwarding and memory disambiguation used fully associative, age-prioritized searches of the store queue or load queue to determine whether these queues had an entry that accessed a particular location in memory.

SUMMARY OF THE INVENTION

Some embodiments relate to a comparison circuit that compares a first address with a second address, where the second address is stored in a load queue and/or store queue of a microprocessor. The comparison circuit includes first and second comparison units. The first comparison unit compares a first subset of bits of the first address with a corresponding second subset of bits of the second address to produce a first comparison result indicating whether the first subset of bits is equal to the second subset of bits. The second comparison unit is coupled to the first comparison unit to receive the first comparison result. The second comparison unit is enabled and disabled based on the first comparison result. When the second comparison unit is enabled, the second comparison unit compares a third subset of bits of the first memory address with a corresponding fourth subset of bits of the second address.

Some embodiments relate to a method of comparing a first address with a second address, where the second address is stored in a load queue and/or store queue of a microprocessor. A first subset of bits of the first address is compared with a corresponding second subset of bits of the second address. When the first subset of bits is equal to the second subset of bits, a third subset of bits of the first address is compared with a corresponding fourth subset of bits of the second address.

DETAILED DESCRIPTION

As discussed above, prior techniques for searching a microprocessor load queue or store queue used fully associative searches to determine whether a queue had an entry that accessed a particular physical address in memory. In these prior search techniques, an entire memory address was compared with all of the addresses in the load queue or store queue to determine whether there was a matching entry. Each bit of the searched memory address was compared with each bit of the addresses in the queue. However, upon simulation and study of load queue and store queue searches, it has been appreciated that most searches of load queues and store queues do not result in finding an address that matches the searched address. Also, comparing the entire searched address with all of the addresses in the queue can consume a significant amount of power.

In some embodiments, a search of a load queue and/or store queue includes an initial partial comparison of the searched address with the addresses in the queue. This partial comparison can enable early identification of addresses that do not match so that full comparisons of non matching addresses are reduced, which can reduce power consumption in the load queue and/or store queue.

For example, in a first comparison stage, a subset of the bits of the searched address can be compared with the corresponding bits of each address in the queue to determine if any potentially matching addresses are stored in the queue. If the subset of bits matches the corresponding bits of an address in the queue, then the address in the queue is a potential match to the searched address, and the remaining bits of the potentially matching address can be checked in another stage to determine whether the address in the queue fully matches the searched address. Some or all of the addresses in the queue may be eliminated from consideration as potential matches when one or more of the address bits are determined not to match in the first comparison stage. When an addresses in the queue is determined to be unequal to the searched address in the initial comparison stage, it is not necessary to compare further bits of this address with the searched address. The number of bit-wise comparisons performed during the search can be decreased by using an initial comparison stage to filter the queue addresses for potential matches and eliminate non-matching addresses from consideration. Reducing the number of bit-wise comparisons performed during the search can advantageously enable reducing power consumption when searching a load queue and/or a store queue.

As discussed above, a superscalar processor can search for entries in the load queue and/or store queue when performing various operations such as memory disambiguation and load-to-store data forwarding. For example, the load queue can be searched to determine whether there are any pending load instructions corresponding to a particular memory address. When a store instruction is ready to be executed, its address may be used to search the load queue to determine whether there are any mis-speculative load instructions. This search may be performed in an address calculation stage, write-back stage, commit stage and/or any other suitable processing stage. If any mis-speculative load instructions are found, then those load instructions may be re-executed to load the more recent data. However, it has been appreciated that prior techniques for searching load queues and store queues consumed a significant amount of power.

FIG. 1shows an example of a load queue1and a comparison circuit2that can determine whether load queue1includes a searched address3, according to some embodiments. Load queue1stores multiple entries4corresponding to load instructions, and each entry4may include a corresponding address5and age information6. Address5may represent the physical memory address of a location in memory accessed by the corresponding load instruction. Address5can be a binary number having any suitable number of bits, such as thirty-two bits, for example, and searched address3may have the same number of bits. Age information6may represent the age of the corresponding load instruction.

As discussed above, the load queue1may be searched to determine whether there are any entries4having an address5that matches the searched address3. In some embodiments, comparison circuit2receives the searched address3and the addresses5of the entries4in the load queue. Comparison circuit2can compare the searched address3with all of the addresses5in the load queue to determine whether there are one or more matching addresses. In some embodiments, comparison circuit2compares the searched address3with an address5of the load queue using two or more comparison stages, as discussed in further detail below with respect toFIG. 2. For example, a subset of the bits of the searched address3may be compared with the corresponding bits of address5in a first comparison stage to determine whether address5potentially matches searched address3. For any addresses5that are determined to potentially match the searched address3, these potentially matching addresses may be further compared with the searched address3in one or more additional comparison stages.

In some circumstances, searches may be filtered based on the age of an instruction. For example, if there is a store instruction that accesses an particular address, the load queue may be searched to determine whether there are any load instructions accessing this address that are younger than the store instruction, to determine whether there are any mis-speculative load instructions. Comparison circuit2may receive age information7corresponding to the searched address3, and age information6corresponding to each load instruction of the load queue1. When searching for mis-speculative instructions, circuit2may use the age information6,7to filter the results of the address comparison to only addresses that are younger than the age represented by age information7. However, it should be appreciated that any suitable age-related filtering may be performed, if desired, as the techniques described herein are not limited to performing age-related filtering.

FIG. 2shows a circuit portion10of comparison circuit2, according to some embodiments, for comparing an address5of the load queue1with a searched address3. For clarity, only a portion of comparison circuit2is shown inFIG. 2.FIG. 2shows circuit portion10of comparison circuit2that can compare the searched address3with a single address5in the load queue1. However, comparison circuit2may include additional circuitry, in some embodiments. For example, if there are N entries4in the load queue, then comparison circuit2may include N versions of circuit portion10for comparing the respective addresses5of these entries with the searched address3.

In the example shown inFIG. 2, the searched address3has thirty-two bits, although it should be appreciated that addresses of any suitable number of bits may be used. As illustrated inFIG. 2, searched address3has twenty-four most significant bits and eight least significant bits. In the first comparison stage, bit-wise comparison unit11compares the eight least significant bits of the searched address3with the eight least significant bits of address5to determine whether address5potentially matches the searched address3. Bit-wise comparison unit11may be a comparator that performs a bit-wise comparison of the bits of the addresses based on their respective positions in addresses3and5. For example, the least significant bit of searched address3may be compared with the least significant bit of address5, the second least significant bit of searched address3may be compared with the second least significant bit of address5, etc. Bit-wise comparison unit11can generate an output with a logic signal indicating whether the eight least significant bits of the searched address3are all equal to the eight least significant bits of address5of the load queue. As shown inFIG. 2, the output signal of bit-wise comparison unit11may be sent to an enabling input of bit-wise comparison unit12. If bit-wise comparison unit11determines that the least significant bits of addresses3and5are all equal, then the output of bit-wise comparison unit11may have a high logic level that enables bit-wise comparison unit12to perform a second stage of comparison. Bit-wise comparison unit12may be a comparator that compares the addresses3and5in a second stage of comparison by performing a bit-wise comparison of the remaining twenty-four most significant bits of searched address3with the twenty-four most significant bits of address5. If the twenty-four most significant bits match, bit-wise comparison unit12may output a signal with a high logic level. In this example, the outputs of bit-wise comparison units11and12are sent to first and second inputs of AND gate13which determines whether all of the bits of searched address3match all of the bits of address5. If all of the bits match, AND gate13receives two logic high signals from bit-wise comparison units11and12, and AND gate13may produce an output signal with a high logic level to indicate that addresses3and5match entirely. If bit-wise comparison unit11determines that the least significant bits do not match, then bit-wise comparison unit11outputs a signal with a low logic level to disable bit-wise comparison unit5, which can advantageously reduce power consumption for the load queue search. When the subset of bits does not match in the first stage, the low logic level from bit-wise comparison unit11is received by the AND gate13which produces an output signal with a low logic level to indicate that the addresses do not match.

Comparison circuit2may include N versions of circuit10that each compare a respective address5of the load queue with the searched address3. Advantageously, some of the addresses5in the load queue may be eliminated from the search by bit-wise comparison unit11during the first stage of comparison. In this example, for the addresses5that are eliminated from the search in the first stage, only eight bits of the address are compared rather than the full thirty-two bits. In some circumstances, a significant number of addresses in the load queue can be eliminated from consideration in the first stage of comparison, such as 95% of the addresses, for example. As a result, the amount of power needed to perform load queue searches can be reduced. In some circumstances, the dynamic power consumption of the load queue can be reduced by about 50%, however, the amount of power saved can be higher or lower depending on the particular circumstances.

A variety other implementations of comparison circuit2are possible. For example, althoughFIG. 2is discussed in the context of a load queue, comparison circuit2may be used to compare addresses for a store queue, as discussed further below with respect toFIG. 4. Other variations are also possible. In the example ofFIG. 2, circuit10performs two comparison stages, however, more than two comparison stages can be performed in some embodiments, such as three stages or more. Different numbers of bits may be compared, as the techniques described herein are not limited to comparing a particular number of bits in a stage. Furthermore, these techniques are not limited to comparing the least significant bits first, as any suitable bits may be compared first, and any suitable grouping of bits may be used.

FIG. 3shows comparison circuit2in further detail, including a plurality of circuits10for comparing different addresses5in the load queue1with searched address3. In some embodiments, each entry4in the load queue may have a corresponding circuit portion10for comparing the corresponding address5with the searched address3. Each of these circuit portions10may be the same or they may be different, as the techniques described herein are not limited to using the same circuit portion10for each entry4in the load queue. In some embodiments, all of the addresses in the load queue may be compared with the searched address3in parallel, as shown inFIG. 3.

As shown in the example ofFIG. 3, in some embodiments the searched address3may be received from the store queue of the microprocessor to check whether there are any load instructions that use the same memory address as a store instruction. The load queue1may be searched for any entries4having an address5that is the same as the searched address3of a store instruction in the store queue, using the techniques described herein to compare address5in the queue with searched address3. As discussed above, load queue may searched in connection with performing any of a variety of techniques such as memory disambiguation and store-to-load data forwarding, for example.

FIG. 3also shows that age information6(rob_id) can be used to filter the result of the address comparison, as discussed above with respect toFIG. 1. Comparison circuit2may receive the age information7for a store instruction having a corresponding entry in the store queue. An age comparison circuit15may check whether an entry in the load queue1is younger than the store instruction based on the age information6and7. For example, when searching for mis-speculative load instructions, age comparison circuit15may filter out addresses that do not correspond to a load instruction that is younger than the store instruction. If the age (rob_id A) of the load queue entry is greater than the age of the store instruction (rob_id B), the age comparison circuit15may produce a logic signal that disables the output of first comparison unit11. As a result, the output of the first comparison unit may be a low logic level that disables the second comparison unit12. Thus, in this example, even if all of the subset of bits match, this entry may be filtered out of the search by the age comparison circuit15. For entries that are not filtered out of the search, if the age of the load queue entry is less than the age of the store instruction then the comparison circuit15may produce a logic signal that enables the output of the first comparison unit11.

FIG. 4shows an example of a store queue20that can be searched for an address using comparison circuit2, according to some embodiments. Comparison circuit2may compare the addresses of store queue20with searched address3using similar techniques to those discussed above with respect to load queue1and comparison circuit2. Store queue20may be searched in any of a variety of circumstances. For example, a search of store queue20may be performed when a target address for a load instruction is calculated. If a matching entry is found in store queue20for a later load instruction, the data from the store instruction can be forwarded to the load instruction to that the data is available more quickly. Because there may be more than one store instruction that accesses the same address, a priority selector21may be used to select the most recent store instruction older than the load instruction, based on age information.

As discussed above with respect to load queue1, the use of comparison circuit2can save a significant amount of power in the store queue20. In some circumstances, the dynamic power consumption of the store queue20can be reduced by about 24%. However the amount of power saved can be higher or lower depending on the particular circumstances.