Providing coherent merging of committed store queue entries in unordered store queues of block-based computer processors

Providing coherent merging of committed store queue entries in unordered store queues of block-based computer processors is disclosed. In one aspect, a block-based computer processor provides a merging logic circuit communicatively coupled to an unordered store queue and cache memory. The merging logic circuit is configured to select a first store queue entry in the unordered store queue, and read its memory address, an age indicator, and a data value. The age indicator and the data value are stored in merged data bytes within a merged data buffer. The merging logic circuit then locates a remaining store queue entry having a memory address identical to the first selected store queue entry, and reads its age indicator and data value. Based on the age indicator and one or more age indicators of the merged data bytes within the merged data buffer, the data value is merged into the merged data buffer.

BACKGROUND

I. Field of the Disclosure

The technology of the disclosure relates generally to unordered store queues in block-based computer processors.

Modern out-of-order (OOO) computer processors, which support processing of computer program instructions in an order other than a program order of the computer program instructions, provide a structure referred to as a store queue. The store queue stores information regarding store operations (e.g., their associated memory addresses and data) to allow correct memory ordering to be maintained in the block-based computer processor. For example, store instructions may be dispatched out of program order, even though they affect the same memory address. In this scenario, the store queue enables the block-based computer processor to resolve the order in which the store instructions should be processed in order to maintain data coherency and consistency. In some OOO processors, the same queue may be used to store and process both load and store operations, and thus may be referred to as a load/store queue (LSQ).

In a conventional store queue (implemented as, e.g., a circular buffer), the physical order of store queue entries in the store queue represents the relative order in which the store instructions associated with the store queue entries are decoded. In some circumstances, however, it may be desirable to employ an “unordered” store queue, which allows entries for store instructions to be allocated out-of-order (e.g., at execution of each instruction rather than at decoding) into any available store queue entry within the store queue. This may be advantageous in some situations by reducing the time that a store queue entry spends in the store queue, and by allowing the store queue to be banked based on address.

However, an unordered store queue may pose challenges in “draining” committed store queue entries (i.e., outputting the contents of the committed store queue entries to a memory or cache and de-allocating the committed store queue entries, after the associated store instructions have been committed). In particular, a block-based computer processor may permit a large number of store instructions within a single instruction block to be committed en masse. In situations where multiple store instructions write to the same memory address, the store instructions must be presented to the memory system in order, so that other threads do not observe out-of-order writes to the memory address. Iterating through each store instruction in the instruction block to commit and drain the store instructions in order would reduce the ability of the block-based computer processor to commit and drain multiple instructions in parallel. Thus, it is desirable to provide a high-performance mechanism for committing and draining blocks of store instructions that write to the same memory address, while maintaining coherency and consistency, in an unordered store queue.

SUMMARY OF THE DISCLOSURE

Aspects disclosed in the detailed description include providing coherent merging of committed store queue entries in unordered store queues of block-based computer processors. In this regard, in one aspect, a block-based computer processor provides a merging logic circuit that is communicatively coupled to an unordered store queue and a cache memory. To drain the unordered store queue, the merging logic circuit first selects a committed store queue entry in the unordered store queue corresponding to a committed store instruction. In some aspects, selection of the committed store queue entry may be arbitrary, while some aspects may provide that a committed store queue entry corresponding to an oldest pending instruction block may be selected. A memory address, an age indicator, and a data value of the committed store queue entry are read, and the age indicator and the data value are stored in one or more merged data bytes within a merged data buffer. The merging logic circuit then locates any remaining committed store queue entries having a memory address identical to the first selected committed store queue entry. If a remaining committed store queue entry having an identical memory address is located, its age indicator and data value are read by the merging logic circuit, and are merged into the merged data buffer based on the age indicator and one or more age indicators of the one or more merged data bytes within the merged data buffer. In some aspects, merging data into the merged data buffer may also be based on byte masks indicating valid data within the data values read from the unordered store queue. Once all remaining committed store queue entries having a memory address identical to the first selected committed store queue entry have been read and merged, the one or more merged data bytes are output from the merged data buffer to the cache memory. In this manner, the committed store queue entries corresponding to a same memory address may be efficiently and coherently merged and provided to memory.

In another aspect, a block-based computer processor is provided. The block-based computer processor comprises a cache memory, and an unordered store queue comprising a plurality of store queue entries. The block-based computer processor also comprises a merging logic circuit that is communicatively coupled to the unordered store queue and the cache memory, and that comprises a merged data buffer for storing a plurality of merged data bytes. The merging logic circuit is configured to select a first committed store queue entry of the plurality of store queue entries of the unordered store queue. The merging logic circuit is further configured to read a memory address, a first age indicator, and a first data value from the first committed store queue entry. The merging logic circuit is also configured to store the first age indicator and the first data value in one or more merged data bytes of the plurality of merged data bytes of the merged data buffer. For each remaining committed store queue entry of the plurality of store queue entries of the unordered store queue having an identical memory address as the first committed store queue entry, the merging logic circuit is additionally configured to read a second age indicator and a second data value from the remaining committed store queue entry. The merging logic circuit is further configured to merge the second data value into the one or more merged data bytes of the plurality of merged data bytes of the merged data buffer, based on the second age indicator and one or more age indicators of the one or more merged data bytes. The merging logic circuit is also configured to output the plurality of merged data bytes of the merged data buffer to the cache memory.

In another aspect, a block-based computer processor is provided. The block-based computer processor comprises a means for selecting a first committed store queue entry of a plurality of store queue entries of an unordered store queue. The block-based computer processor further comprises a means for reading a memory address, a first age indicator, and a first data value from the first committed store queue entry. The block-based computer processor also comprises a means for storing the first age indicator and the first data value in one or more merged data bytes of a plurality of merged data bytes of a merged data buffer. For each remaining committed store queue entry of the plurality of store queue entries of the unordered store queue having an identical memory address as the first committed store queue entry, the block-based computer processor additionally comprises a means for reading a second age indicator and a second data value from the remaining committed store queue entry. The block-based computer processor further comprises a means for merging the second data value into the one or more merged data bytes of the plurality of merged data bytes of the merged data buffer, based on the second age indicator and one or more age indicators of the one or more merged data bytes. The block-based computer processor also comprises a means for outputting the plurality of merged data bytes of the merged data buffer to a cache memory.

In another aspect, a method for coherently merging committed store queue entries in an unordered store queue of a block-based computer processor is provided. The method comprises selecting a first committed store queue entry of a plurality of store queue entries of the unordered store queue. The method further comprises reading a memory address, a first age indicator, and a first data value from the first committed store queue entry. The method also comprises storing the first age indicator and the first data value in one or more merged data bytes of a plurality of merged data bytes of a merged data buffer. For each remaining committed store queue entry of the plurality of store queue entries of the unordered store queue having an identical memory address as the first committed store queue entry, the method additionally comprises reading a second age indicator and a second data value from the remaining committed store queue entry. The method further comprises merging the second data value into the one or more merged data bytes of the plurality of merged data bytes of the merged data buffer, based on the second age indicator and one or more age indicators of the one or more merged data bytes. The method also comprises outputting the plurality of merged data bytes of the merged data buffer to a cache memory.

DETAILED DESCRIPTION

Aspects disclosed in the detailed description include providing coherent merging of committed store queue entries in unordered store queues of block-based computer processors. In this regard, in one aspect, a block-based computer processor provides a merging logic circuit that is communicatively coupled to an unordered store queue and a cache memory. To drain the unordered store queue, the merging logic circuit first selects a committed store queue entry in the unordered store queue corresponding to a committed store instruction. In some aspects, selection of the committed store queue entry may be arbitrary, while some aspects may provide that a committed store queue entry corresponding to an oldest pending instruction block may be selected. A memory address, an age indicator, and a data value of the committed store queue entry are read, and the age indicator and the data value are stored in one or more merged data bytes within a merged data buffer. The merging logic circuit then locates any remaining committed store queue entries having a memory address identical to the first selected committed store queue entry. If a remaining committed store queue entry having an identical memory address is located, its age indicator and data value are read by the merging logic circuit, and are merged into the merged data buffer based on the age indicator and one or more age indicators of the one or more merged data bytes within the merged data buffer. In some aspects, merging data into the merged data buffer may also be based on byte masks indicating valid data within the data values read from the unordered store queue. Once all remaining committed store queue entries having a memory address identical to the first selected committed store queue entry have been read and merged, the one or more merged data bytes are output from the merged data buffer to the cache memory. In this manner, the committed store queue entries corresponding to a same memory address may be efficiently and coherently merged and provided to memory.

Before discussing a merging logic circuit for providing coherent merging of committed store queue entries in an unordered store queue of a block-based computer processor, exemplary elements and operation of an exemplary block-based computer processor are described. In this regard,FIG. 1illustrates an exemplary block-based computer processor100that is based on a block-based instruction set architecture (ISA), and that is configured to execute a sequence of instruction blocks. In some aspects, the block-based computer processor100may comprise one of multiple block-based computer processor cores (not shown), each executing separate sequences of instruction blocks and/or coordinating to execute a single sequence of instruction blocks. The block-based computer processor100may access a shared Level 2 (L2) cache102for receiving instruction blocks for execution and/or for storing data resulting from instruction block execution. In aspects in which the block-based computer processor100comprises one of multiple block-based computer processor cores, a core interconnection network104may be employed for inter-core communications. The block-based computer processor100may encompass any one of known digital logic elements, semiconductor circuits, processing cores, and/or memory structures, among other elements, or combinations thereof. Aspects described herein are not restricted to any particular arrangement of elements, and the disclosed techniques may be easily extended to various structures and layouts on semiconductor dies or packages.

In exemplary operation, a Level 1 (L1) instruction cache106of the block-based computer processor100may receive instruction blocks (e.g., instruction blocks108(0)-108(N) for execution from the shared L2 cache102. It is to be understood that, at any given time, the block-based computer processor100may be processing more or fewer instruction blocks than the instruction blocks108(0)-108(N) illustrated inFIG. 1. A block predictor110determines a predicted execution path of the instruction blocks108(0)-108(N). In some aspects, the block predictor110may predict an execution path in a manner analogous to a branch predictor of a conventional out-of-order (OOO) processor. A block sequencer112orders the instruction blocks108(0)-108(N), and forwards the instruction blocks108(0)-108(N) to one of one or more instruction decode stage(s)114for decoding.

After decoding, the instruction blocks108(0)-108(N) are held in an instruction buffer116of an instruction processing circuit118pending execution. An instruction scheduler120distributes instructions (not shown) of the active instruction blocks108(0)-108(N) to one of one or more execution units122of the block-based computer processor100. As non-limiting examples, the one or more execution units122may comprise an arithmetic logic unit (ALU) and/or a floating-point unit. The one or more execution units122may provide results of instruction execution to a load/store unit124. In the example ofFIG. 1, the load/store unit124provides an unordered store queue126, in which store instructions (not shown) and their associated data may be held for processing. In some aspects, the unordered store queue126may comprise a load/store queue (LSQ), in which both load instructions and store instructions are stored. As each store instruction in the unordered store queue126is processed, the execution results may be stored in a cache memory128. According to some aspects, the cache memory128may comprise an L1 data cache (not shown).

The one or more execution units122may additionally or alternatively store execution results in a physical register file130. The physical register file130, in some aspects, comprises multiple physical registers (not shown) that provide named physical storage locations for data values. Some aspects may provide that the physical register file130may be implemented by fast static Random Access Memory (RAM) having dedicated read and write ports, as a non-limiting example.

As noted above, the load/store unit124of the block-based computer processor100ofFIG. 1employs the unordered store queue126to hold store instructions. The use of the unordered store queue126allows entries for store instructions to be allocated out-of-order (e.g., at execution of each store instruction rather than at decoding) into any available store queue entry (not shown) within the unordered store queue126. This may enable the unordered store queue126to reduce the time that a store queue entry remains in the unordered store queue126, and enable the unordered store queue126to be banked based on address. However, “draining” the unordered store queue126(i.e., outputting the contents of the committed store queue entries to the cache memory128and de-allocating the committed store queue entries) may pose challenges for the block-based computer processor100. In a conventional processor, multiple committed store queue entries having a same memory address (not shown) are presented to the cache memory128in order, so that other executing threads (not shown) do not observe out-of-order writes to the memory address. However, because the block-based computer processor100may permit a large number of store instructions within a single instruction block108(0)-108(N) to be committed en masse, it is desirable to provide a high-performance mechanism for committing and draining committed store queue entries having the same memory address, while maintaining memory coherency and consistency.

In this regard,FIG. 2illustrates a merging logic circuit200that provides coherent merging of committed store queue entries in an unordered store queue202. In the example ofFIG. 2, a load/store unit204having functionality corresponding to the load/store unit124ofFIG. 1is shown. The load/store unit204is communicatively coupled to the cache memory128ofFIG. 1, as indicated by bidirectional arrow206. The load/store unit204includes the merging logic circuit200, and further includes the unordered store queue202, which in some aspects may correspond to the unordered store queue126ofFIG. 1.

The unordered store queue202provides a plurality of store queue entries208(0)-208(X). For purposes of illustration, three (3) store queue entries208(0),208(1), and208(X) are shown in the example ofFIG. 2. However, it is to be understood that in some aspects the unordered store queue202may include more store queue entries208(0)-208(X) than illustrated herein.

Each of the store queue entries208(0)-208(X) ofFIG. 2corresponds to a store instruction (not shown) that has been executed by the block-based computer processor100ofFIG. 1. Accordingly, each of the store queue entries208(0)-208(X) includes multiple data fields for storing data associated with the executed store instructions. These data fields include committed indicators (“COM”)210(0)-210(X), memory addresses (“ADDR”)212(0)-212(X), age indicators (“AGE IND”)214(0)-214(X), data values216(0)-216(X), byte masks218(0)-218(X), and valid indicators219(0)-219(X), each of which is described in greater detail below.

The committed indicators210(0)-210(X) indicate whether the corresponding store queue entries208(0)-208(X) represent committed entries within the unordered store queue202. In some aspects, each of the committed indicators210(0)-210(X) comprises a one-bit flag. In such aspects, the committed indicators210(0)-210(X) may be set to a value of one (1) to indicate that the corresponding store queue entry208(0)-208(X) is committed (e.g., when an instruction block containing instructions associated with the store queue entries208(0)-208(X)), or may be set to a value of zero (0) to indicate that the corresponding store queue entry208(0)-208(X) is not yet committed.

The memory addresses212(0)-212(X) of the store queue entries208(0)-208(X) each indicate a memory location to which a store instruction associated with the corresponding store queue entry208(0)-208(X) is attempting to write. There may be more than one store queue entry208(0)-208(X) in the unordered store queue202having identical memory addresses212(0)-212(X). For instance, in the example ofFIG. 2, the store queue entries208(0) and208(X) have memory addresses212(0) and212(X) of 0x1234, indicating that the store instructions associated with both of the store queue entries208(0) and208(X) are writing to the same memory address 0x1234.

The store queue entries208(0)-208(X) further include respective age indicators214(0)-214(X), which provide a mechanism for the merging logic circuit200to determine a relative age of each of the store queue entries208(0)-208(X). InFIG. 2, it is assumed that lower values of the age indicators214(0)-214(X) correspond to older store queue entries208(0)-208(X). Thus, the store queue entry208(1) having an age indicator214(1) with a value of seven (7) is the oldest of the store queue entries208(0)-208(X), while the store queue entry208(X) having an age indicator214(X) with a value of fifteen (15) is the youngest. In some aspects, the age indicators214(0)-214(X) may each comprise an indication of a phase in which the store instruction associated with the corresponding store queue entry208(0)-208(X) is executing, a core on which the store instruction associated with the corresponding store queue entry208(0)-208(X) is executing, and/or an instruction block within which the store instruction associated with the corresponding store queue entry208(0)-208(X) is executing.

The data values216(0)-216(X) of the store queue entries208(0) represent the actual data to be written to the cache memory128by the store instructions associated with the store queue entries208(0)-208(X). In some aspects, the data values216(0)-216(X) may comprise a double word of sixty-four (64) bits. However, it is to be understood that the store instructions associated with the store queue entries208(0)-208(X) may comprise instructions that operate on a smaller portion of the data values216(0)-216(X), such as byte store instructions and/or word store instructions having addresses that are aligned to a 64-bit boundary, as a non-limiting example. As a result, the data values216(0)-216(X) may include sets220(0)-220(X) of valid data bytes to be written. These sets220(0)-220(X) of valid data bytes within the data values216(0)-216(X) are indicated by the byte masks218(0)-218(X) corresponding to the data values216(0)-216(X). For example, the byte mask218(0) indicates that the first four (4) bytes of the data value216(0) (corresponding to the set220(0)) contains valid data. As a further non-limiting example, the memory addresses212(0)-212(X) corresponding to store queue entries208(0)-208(X) may be aligned to a 64-bit boundary, with the byte masks218(0)-218(X) indicating which bytes within the 64-bit aligned words are written by the corresponding store instructions.

The valid indicators219(0)-219(X) indicate whether the corresponding store queue entries208(0)-208(X) contain valid data. In some aspects, each of the valid indicators219(0)-219(X) comprises a one-bit flag. In such aspects, the valid indicators219(0)-219(X) may be set to a value of one (1) to indicate that the corresponding store queue entry208(0)-208(X) is valid, or may be set to a value of zero (0) to indicate that the corresponding store queue entry208(0)-208(X) is invalid. The load/store unit204may then reallocate the store queue entries208(0)-208(X) having valid indicators219(0)-219(X) set to zero (0) to store data for newly committed store instructions (not shown).

To provide coherent merging of the store queue entries208(0)-208(X) in the unordered store queue202, the merging logic circuit200includes a merged data buffer222. The merged data buffer222includes a plurality of merged data bytes224(0)-224(7), which are associated with age indicators226(0)-226(7) and valid indicators228(0)-228(7). The merged data bytes224(0)-224(7) may store data that has been merged from two (2) or more store queue entries208(0)-208(X) having identical memory addresses212(0)-212(X). Each of the age indicators226(0)-226(7) stores the value of the age indicators214(0)-214(X) of the youngest store queue entry208(0)-208(X) whose data is stored in the corresponding merged data byte224(0)-224(7). The valid indicators228(0)-228(7) indicate whether the corresponding merged data byte224(0)-224(7) stores valid data. Some aspects may provide that each of the valid indicators228(0)-228(7) comprises a one-bit flag that may be set to a value of one (1) to indicate that the corresponding merged data byte224(0)-224(7) stores valid data, or may be set to a value of zero (0) to indicate that the corresponding merged data byte224(0)-224(7) is unused or stores invalid data. It is to be understood that while the merged data buffer222inFIG. 2provides eight (8) merged data bytes224(0)-224(7), some aspects may provide more or fewer merged data bytes224(0)-224(7) than illustrated herein.

To illustrate exemplary operations by the merging logic circuit200and exemplary communications flows among the unordered store queue202, the merging logic circuit200, and the cache memory128ofFIG. 2for selecting, merging, and outputting store queue entries208(0)-208(X),FIGS. 3A-3Care provided. For the sake of clarity, elements ofFIG. 2are referenced in describingFIGS. 3A-3C. InFIG. 3A, the merging logic circuit200first selects one of the store queue entries208(0)-208(X) for processing. The selected store queue entry208(0)-208(X) may be referred to herein as a “first store queue entry208(0)-208(X).” In some aspects, the selection of one of the store queue entries208(0)-208(X) may be arbitrary or pseudo-random. Some aspects may provide that the merging logic circuit200may select one of the store queue entries208(0)-208(X) corresponding to an oldest pending instruction block (not shown). This may facilitate reuse and reallocation of the store queue entries208(0)-208(X) by ensuring that the store queue entries208(0)-208(X) associated with older instruction blocks are processed first.

In the example ofFIG. 3A, the merging logic circuit200has selected the store queue entry208(X), with a memory address212(X) of 0x1234, for processing. Accordingly, the merging logic circuit200reads the memory address212(X), the age indicator214(X), and the data value216(X) of the store queue entry208(X) from the unordered store queue202. In some aspects, the merging logic circuit200also reads the byte mask218(X), which, as noted above, indicates the set220(X) of valid data bytes within the data value216(X). The merging logic circuit200then stores the age indicator214(X) and the data value216(X) of the store queue entry208(X) in the age indicators226(2)-226(5) and the merged data bytes224(2)-224(5), respectively, of the merged data buffer222. Note that the merged data bytes224(2)-224(5) occupy locations within the merged data buffer222corresponding to the location of the set220(X) of valid data bytes within the data value216(X), as indicated by the byte mask218(X). The merging logic circuit200also sets the valid indicators228(2)-228(5) of the merged data bytes224(2)-224(5) corresponding to the set220(X) of valid data bytes within the data value216(X) to indicate a valid state. Here, the valid indicators228(2)-228(5) are set to a value of one (1), indicating that the merged data bytes224(2)-224(5) currently hold valid data. According to some aspects, after reading the memory address212(X), the age indicator214(X), and the data value216(X) of the store queue entry208(X), the merging logic circuit200may invalidate the store queue entry208(X) (e.g., by setting the valid indicator219(X) to a value of zero (0)).

Referring now toFIG. 3B, the merging logic circuit200next determines whether any other store queue entries208(0)-208(X) having a memory address212(0)-212(X) that is identical to the memory address212(X) of the store queue entry208(X) remain within the unordered store queue202. As seen inFIG. 3B, the store queue entry208(0) also has a memory address212(0) of 0x1234, which matches the memory address212(X) of the store queue entry208(X). Accordingly, the merging logic circuit200reads the age indicator214(0) and the data value216(0) of the store queue entry208(0). Some aspects may provide that the merging logic circuit200also reads the byte mask218(0) indicating the set220(0) of valid data bytes within the data value216(0) of the store queue entry208(0). In some aspects, after reading the age indicator214(0) and the data value216(0) of the store queue entry208(0), the merging logic circuit200may invalidate the store queue entry208(0) (e.g., by setting the valid indicator219(0) to a value of zero (0)).

The merging logic circuit200next merges the data value216(0) into one or more of the merged data bytes224(0)-224(7) of the plurality of merged data bytes224(0)-224(7) of the merged data buffer222, based on the age indicator214(0) and the age indicators226(0)-226(7) of the merged data bytes224(0)-224(7). To perform the merging, the merging logic circuit200may perform a byte-by-byte evaluation of the bytes of the data value216(0) and the corresponding merged data bytes224(0)-224(7). In some aspects, the merging logic circuit200may first determine whether a byte of the data value216(0) contains valid data (based on the byte mask218(0), as a non-limiting example). If a byte of the data value216(0) does not contain valid data (such as the last four (4) bytes of the data value216(0)), then no change is made to the contents of the corresponding merged data bytes224(0)-224(7).

However, if a byte of the data value216(0) does contain valid data (such as the first four (4) bytes of the data value216(0)), the merging logic circuit200in some aspects may determine whether the corresponding merged data bytes224(0)-224(7) contain valid data, based on the valid indicators228(0)-228(7). For merged data bytes224(0)-224(7) that do not contain valid data, the merging logic circuit200may store the corresponding bytes of the set220(0) of valid data bytes within the data value216(0) in the merged data bytes224(0)-224(7). For example, the merging logic circuit200may determine that the merged data bytes224(0) and224(1), corresponding to the first two (2) bytes of the set220(0) of valid data bytes within the data value216(0), do not contain valid data. Accordingly, the merging logic circuit200stores the values “01” and “23” from the first two (2) data bytes of the set220(0) in the merged data bytes224(0) and224(1), respectively. The merging logic circuit200also stores the age indicator214(0) in the age indicators226(0) and226(1) of the merged data bytes224(0) and224(1), respectively, and sets the valid indicators228(0) and228(1) to a value of one (1).

For merged data bytes224(0)-224(7) that already contain valid data, the merging logic circuit200compares the age indicator214(0) of the store queue entry208(0) with the age indicators226(0)-226(7) of the merged data bytes224(0)-224(7). If the age indicator214(0) and the age indicators226(0)-226(7) indicate that the merged data bytes224(0)-224(7) are older than the data value216(0), the merging logic circuit200stores the corresponding bytes of the data value216(0) in the merged data bytes224(0)-224(7), and also stores the age indicator214(0) in the corresponding age indicators226(0)-226(7) Otherwise, the merging logic circuit200retains the data stored in the merged data bytes224(0)-224(7). In the example ofFIG. 3B, the merging logic circuit200determines that the merged data bytes224(2) and224(3) already contain valid data. Thus, the merging logic circuit200compares the age indicator214(0) and the age indicators226(2) and226(3) of the merged data bytes224(2) and224(3). The age indicator214(0), having a value of eleven (11), indicates that the store queue entry208(0) is older than the merged data bytes224(2) and224(3), which have corresponding age indicators226(2) and226(3) with a value of fifteen (15). As a result, the merging logic circuit200retains the values already stored in the merged data bytes224(2) and224(3) rather than storing the values of the last two (2) data bytes of the set220(0) in the merged data bytes224(2) and224(3).

Processing of the store queue entries208(0)-208(X) by the merging logic circuit200continues in this manner until there are no remaining store queue entries208(0)-208(X) having a memory address212(0)-212(X) that is identical to the memory address212(X) of the store queue entry208(X). As seen inFIG. 3C, both of the store queue entries208(0),208(X) having memory addresses212(0),212(X) of 0x1234 have been merged into the merged data buffer222of the merging logic circuit200. Accordingly, the merging logic circuit200outputs the merged data bytes224(0)-224(7) to the cache memory128. In some aspects, additional performance improvement may be realized by selecting a next store queue entry208(0)-208(X) for processing in parallel with outputting the merged data bytes224(0)-224(7) to the cache memory128.

In some aspects, the unordered store queue202may be a “banked” store queue, in which subsets of the store queue entries208(0)-208(X) are housed in separate banks. Such a banked store queue may be useful for providing unaligned memory accesses, as a non-limiting example. In this regard,FIG. 4illustrates an exemplary aspect of the load/store unit204that includes an unordered store queue202providing a plurality of banks400(0)-400(Z). The merging logic circuit200in the example ofFIG. 4provides a plurality of bank-associated merging logic circuits401(0)-401(Z), each of which is associated with a corresponding bank400(0)-400(Z). The bank-associated merging logic circuits401(0)-401(Z) may be configured to select and merge store queue entries from the respective banks400(0)-400(Z) concurrently. To select a bank-associated merging logic circuit401(0)-401(Z) to drain to the cache memory128(i.e., to output merged data bytes) at a given time, an arbiter circuit402may be provided. The arbiter circuit402may select a bank-associated merging logic circuit401(0)-401(Z) based on considerations such as bank usage, ready status, and/or processor performance, as non-limiting examples.

FIGS. 5A-5Dare flowcharts that illustrate an exemplary process for providing coherent merging of store queue entries208(0)-208(X) by the merging logic circuit200ofFIG. 2. Elements ofFIG. 2are referenced in describingFIGS. 5A-5Dfor the sake of clarity. InFIG. 5A, operations begin with the merging logic circuit200selecting a first store queue entry208(X) of a plurality of store queue entries208(0)-208(X) of the unordered store queue202(block500). In this regard, the merging logic circuit200may be referred to herein as “a means for selecting a first committed store queue entry of a plurality of store queue entries of an unordered store queue.” In some aspects, operations of block500for selecting the first committed store queue entry208(X) may comprise selecting the first store queue entry208(X) corresponding to an oldest pending instruction block (block502). Accordingly, the merging logic circuit200may be referred to herein as “a means for selecting the first store queue entry corresponding to an oldest pending instruction block.”

The merging logic circuit200next reads a memory address212(X), a first age indicator214(X), and a first data value216(X) from the first store queue entry208(X) (block504). The merging logic circuit200may thus be referred to herein as “a means for reading a memory address, a first age indicator, and a first data value from the first committed store queue entry.” According to some aspects, the operations of block504for reading the first data value216(X) may further comprise reading a first byte mask218(X) indicating a first set220(X) of valid data bytes within the first data value216(X) (block506). In this regard, the merging logic circuit200may be referred to herein as “a means for reading a first byte mask indicating a first set of one or more valid bytes within the first data value.” Some aspects may provide that the merging logic circuit200invalidates the first store queue entry208(X) after reading the memory address212(X), the first age indicator214(X), and the first data value216(X) from the first store queue entry208(X) (block508). Accordingly, the merging logic circuit200may be referred to herein as “a means for invalidating the first store queue entry after reading the memory address, the first age indicator, and the first data value from the first store queue entry.”

The merging logic circuit200then stores the first age indicator214(X) and the first data value216(X) in one or more merged data bytes224(2),224(3) of the plurality of merged data bytes224(0)-224(7) of the merged data buffer222(block510). The merging logic circuit200may thus be referred to herein as “a means for storing the first age indicator and the first data value in one or more merged data bytes of a plurality of merged data bytes of a merged data buffer.” In some aspects, operations of block510for storing the first age indicator214(X) and the first data value216(X) in the one or more merged data bytes224(2),224(3) may include setting a valid indicator228(2),228(3) of the one or more merged data bytes224(2),224(3) of the plurality of merged data bytes224(0)-224(7) of the merged data buffer222corresponding to the first set220(X) of valid data bytes within the first data value216(X) to indicate a valid state, based on the first byte mask218(X) (block512). In this regard, the merging logic circuit200may be referred to herein as “a means for setting a valid indicator of the one or more merged data bytes of the plurality of merged data bytes of the merged data buffer corresponding to the first set of one or more valid bytes within the first data value to indicate a valid state, based on the first byte mask.” Processing then resumes at block514ofFIG. 5B.

Referring now toFIG. 5B, the merging logic circuit200determines whether a store queue entry208(0) having a memory address212(0) identical to the memory address212(X) of the first store queue entry208(X) remains in the unordered store queue202(block514). If no remaining store queue entry208(0) having a memory address212(0) identical to the memory address212(X) of the first store queue entry208(X) exists in the unordered store queue202, processing resumes at block516ofFIG. 5D. However, if the merging logic circuit200locates a remaining store queue entry208(0), the merging logic circuit200reads a second age indicator214(0) and a second data value216(0) from the remaining store queue entry208(0) (block518). The merging logic circuit200may thus be referred to herein as “a means for reading a second age indicator and a second data value from the remaining store queue entry.” In some aspects, operations of block518for reading the second data value216(0) from the remaining store queue entry208(0) may further comprise reading a second byte mask218(0) indicating a second set220(0) of valid data bytes within the second data value216(0) (block520). In this regard, the merging logic circuit200may be referred to herein as “a means for reading a second byte mask indicating a second set of one or more valid bytes within the second data value.” Some aspects may provide that the merging logic circuit200invalidates the remaining store queue entry208(0) after reading the second age indicator214(0) and the second data value216(0) from the remaining store queue entry208(0) (block522). Accordingly, the merging logic circuit200may be referred to herein as “a means for invalidating each remaining store queue entry after reading the second age indicator and the second data value from the remaining store queue entry.” Processing then resumes at block524ofFIG. 5C.

InFIG. 5C, the merging logic circuit200merges the second data value216(0) into one or more merged data bytes224(0)-224(3) of the plurality of merged data bytes224(0)-224(7) of the merged data buffer222, based on the second age indicator214(0) and one or more age indicators226(0)-226(3) of the one or more merged data bytes224(0)-224(3) (block524). The merging logic circuit200may thus be referred to herein as “a means for merging the second data value into the one or more merged data bytes of the plurality of merged data bytes of the merged data buffer, based on the second age indicator and one or more age indicators of the one or more merged data bytes.” In some aspects, operations of block524for the merging logic circuit200merging the second data value216(0) into the one or more merged data bytes224(0)-224(3) may comprise the following operations. The merging logic circuit200may determine whether each of the one or more merged data bytes224(0)-224(3) of the plurality of merged data bytes224(0)-224(7) contains valid data, based on the valid indicator228(0)-228(3) for the merged data byte224(0)-224(3) (block526). In this regard, the merging logic circuit200may be referred to herein as “a means for determining, based on a valid indicator for each of the one or more merged data bytes of the plurality of merged data bytes of the merged data buffer corresponding to the second set of one or more valid bytes within the second data value, whether the merged data byte contains valid data.” It is to be understood that the merging logic circuit200makes this determination independently for each of the one or more merged data bytes224(0)-224(3), and thus some of the merged data bytes224(0)-224(3) may be determined to contain valid data while others may be determined to contain invalid data. If the merging logic circuit200determines that the one or more merged data bytes224(0)-224(3) do not contain valid data, the merging logic circuit200may store the corresponding bytes of the second set220(0) of valid data bytes within the second data value216(0) in the merged data byte224(0)-224(3) (block528). Accordingly, the merging logic circuit200may be referred to herein as “a means for storing the corresponding byte of the second set of one or more valid bytes within the second data value in the merged data byte.”

However, if the merging logic circuit200determines at decision block526that the one or more merged data bytes224(0)-224(3) do contain valid data, the merging logic circuit200next determines whether the one or more merged data bytes224(0)-224(3) is older than the second data value216(0), based on the second age indicator214(0) and one or more age indicators226(0)-226(3) of the one or more merged data bytes224(0)-224(3) (block530). The merging logic circuit200may thus be referred to herein as “a means for determining, based on the second age indicator and the one or more age indicators of the one or more merged data bytes, whether the one or more merged data bytes is older than the second data value.” If the one or more merged data bytes224(0)-224(3) is older than the second data value216(0), the merging logic circuit200may store the second data value216(0) in the one or more merged data bytes224(0)-224(3) (block532). In this regard, the merging logic circuit200may be referred to herein as “a means for storing the second data value in the one or more merged data bytes.” If the merging logic circuit200determines at decision block530that the second data value216(0) is older than the one or more merged data bytes224(0)-224(3), the merging logic circuit200may retain the one or more merged data bytes224(0)-224(3) in the merged data buffer222(block534). Processing then returns to block514ofFIG. 5B, where the merging logic circuit200processes the remaining store queue entries208(0)-208(X), if any.

InFIG. 5D, the merging logic circuit200outputs the plurality of merged data bytes224(0)-224(7) of the merged data buffer222to the cache memory128(block516). Accordingly, the merging logic circuit200may be referred to herein as “a means for outputting the plurality of merged data bytes of the merged data buffer to a cache memory.” In aspects in which the load/store unit204provides multiple banks400(0)-400(Z) and corresponding bank-associated merging logic circuits401(0)-401(Z), the arbiter circuit402of the merging logic circuit200may select one of the banks400(0)-400(Z) from which to output the plurality of merged data bytes. In some aspects, the merging logic circuit200, in parallel with the operations of block516, may also select a next first committed store queue entry208(0)-208(X) of the plurality of store queue entries208(0)-208(X) of the unordered store queue202(block536).

Providing coherent merging of store queue entries in unordered store queues of block-based computer processors according to aspects disclosed herein may be provided in or integrated into any processor-based device. Examples, without limitation, include a set top box, an entertainment unit, a navigation device, a communications device, a fixed location data unit, a mobile location data unit, a mobile phone, a cellular phone, a smart phone, a tablet, a phablet, a computer, a portable computer, a desktop computer, a personal digital assistant (PDA), a monitor, a computer monitor, a television, a tuner, a radio, a satellite radio, a music player, a digital music player, a portable music player, a digital video player, a video player, a digital video disc (DVD) player, a portable digital video player, and an automobile.

In this regard,FIG. 6illustrates an example of a processor-based system600that can employ the merging logic circuit (MLC)200illustrated inFIGS. 2 and 3A-3C. In this example, the processor-based system600includes one or more central processing units (CPUs)602, each including one or more processors604. The one or more processors604may comprise the block-based computer processor100ofFIG. 1. The CPU(s)602may be a master device. The CPU(s)602may have cache memory606coupled to the processor(s)604for rapid access to temporarily stored data. The CPU(s)602is coupled to a system bus608and can intercouple master and slave devices included in the processor-based system600. As is well known, the CPU(s)602communicates with these other devices by exchanging address, control, and data information over the system bus608. For example, the CPU(s)602can communicate bus transaction requests to a memory controller610as an example of a slave device.

Other master and slave devices can be connected to the system bus608. As illustrated inFIG. 6, these devices can include a memory system612, one or more input devices614, one or more output devices616, one or more network interface devices618, and one or more display controllers620, as examples. The input device(s)614can include any type of input device, including but not limited to input keys, switches, voice processors, etc. The output device(s)616can include any type of output device, including, but not limited to, audio, video, other visual indicators, etc. The network interface device(s)618can be any devices configured to allow exchange of data to and from a network622. The network622can be any type of network, including, but not limited to, a wired or wireless network, a private or public network, a local area network (LAN), a wireless local area network (WLAN), a wide area network (WAN), a BLUETOOTH™ network, and the Internet. The network interface device(s)618can be configured to support any type of communications protocol desired. The memory system612can include one or more memory units624(0-N).

The CPU(s)602may also be configured to access the display controller(s)620over the system bus608to control information sent to one or more displays626. The display controller(s)620sends information to the display(s)626to be displayed via one or more video processors628, which process the information to be displayed into a format suitable for the display(s)626. The display(s)626can include any type of display, including, but not limited to, a cathode ray tube (CRT), a liquid crystal display (LCD), a plasma display, etc.