System and method for store fusion

Described herein is a system and method for store fusion that fuses small store operations into fewer, larger store operations. The system detects that a pair of adjacent operations are consecutive store operations, where the adjacent micro-operations refers to micro-operations flowing through adjacent dispatch slots and the consecutive store micro-operations refers to both of the adjacent micro-operations being store micro-operations. The consecutive store operations are then reviewed to determine if the data sizes are the same and if the store operation addresses are consecutive. The two store operations are then fused together to form one store operation with twice the data size and one store data HI operation.

BACKGROUND

A processor generally has associated with it an instruction pipeline which includes fetching, decoding (or dispatching) and executing stages. The decoding stage retrieves an instruction from a fetch queue. If the fetched instruction is a store operation, queue entries are allocated in arithmetic logic unit (ALU) scheduler queues (ALSQs), address generation scheduler queues (AGSQs) and store queues (STQs). Conventional processors perform one store operation per cycle. In an effort to increase the instructions per cycle (IPC), some processors use a two-store commit architecture. This is done at the cost of additional control logic on the die area and increased power usage.

DETAILED DESCRIPTION

Processors generally operate pursuant to an instruction pipeline which includes fetching, decoding (or dispatching) and executing stages. The decoding or dispatching stage retrieves an instruction from a fetch queue. If the fetched instruction is a store micro-operation, queue entries are allocated in arithmetic logic unit (ALU) scheduler queues (ALSQs), address generation scheduler queues (AGSQs) and store queues (STQs). Each store micro-operation is performed independently and conventional processors perform one store micro-operation per cycle.

Described herein is a system and method for store fusion that fuses small store micro-operations into fewer, larger store micro-operations. In particular, the system detects that adjacent micro-operations are consecutive store micro-operations. The consecutive store micro-operations are then reviewed to determine if the data sizes are the same and if the store micro-operation addresses are consecutive. The consecutive store micro-operations are fused together to form one store micro-operation with twice the data size and two store data micro-operations, one for each of the two stores, if the above conditions are met. This increases performance by saving STQ and AGSQ queue entries, and saves power by decreasing the number of address generations, store pipe flows and store commits that write to cache, for example. The store fusion system and method effectively realizes much of the IPC gain of a two-store per cycle architecture without the disadvantages of a two-store-commit which include, for example, added complexity, increased power requirement, and added difficulty in achieving higher frequency of operation.

FIG. 1is a high level block and flow diagram of a core processing unit105of a processor100in accordance with certain implementations. The core processing unit105includes a decoder unit110which provides micro-operations (shown as micro-ops inFIG. 1) to a scheduler and execution unit (SCEX)115. The decoder unit110includes a branch predictor120connected to a cache122and a micro-op cache124. The cache122is further connected to a decoder126. The decoder126and the micro-op cache124are connected to a micro-op queue128, which dispatches operations via a dispatch logic129. A store fusion detection logic (SFDL)128is connected to dispatch logic129.

The SCEX115includes an integer SCEX130and a floating point SCEX132, both of which are connected to a cache134. The cache134is further connected to a L2 cache136, LDQs138and STQs140. The integer SCEX130includes an integer renamer150which is connected to a scheduler151, which includes arithmetic logic unit (ALU) scheduler queues (ALSQs)152and address generation unit (AGU) scheduler queues (AGSQs)154. The scheduler151, and in particular the ALSQs152and AGSQs154, are further connected to ALU0-ALU3156and AGU0-AGU1158, respectively. A pair of multiplexers M0and M1157and a store data interface159connects ALU0and ALU1to STQs140and ALU2and ALU3to STQs140. The LDQs138and STQs140are connected to the scheduler151via path180to send deallocation signals. The integer SCEX130also includes an integer physical file register160. The floating point SCEX132includes a floating point renamer170, which is connected to a scheduler172. The scheduler172is further connected to multipliers174and adders176. The floating point SCEX132also includes a floating point physical file register178.

A pipelined processor requires a steady stream of instructions to be fed into the pipeline. The branch predictor120predicts which set of micro-operations are fetched and executed in the pipelined processor. These micro-operations are fetched and stored in cache122, which in turn are decoded by the decoder126. The micro-op cache124caches the micro-operations from the branch predictor120as the decoder126decodes the micro-operations from the cache122. The micro-op queue128stores and queues up the micro-operations from the decoder126and micro-op cache124for purposes of dispatching the micro-operations for execution via the dispatch logic129.

In conventional pipeline architecture, each micro-operation is dispatched and handled independently. This may lead to inefficient processing under certain cases. For example, a store micro-operation includes three components: a load/store operation that is directed to a store queue; an address generation operation that is directed to a AGSQ; and a store data operation that is directed to a ALSQ. Each store micro-operation therefore uses three queue entries and associated processing to complete the store micro-operation.

In accordance with an implementation, the SFDL128determines whether adjacent micro-operations are consecutive store micro-operations. The SFDL128also confirms whether the consecutive store micro-operations have the same data size and are accessing consecutive addresses. In an implementation, the SFDL128checks the addressing mode of each of the store micro-operations. For example for a 4 byte store micro-operation, an addressing mode of the first store micro-operation may use a base register R with a displacement of +4 and an addressing mode of the second store micro-operation may use a base register R with a displacement of +8. In this case, the addresses for the first store micro-operation and the second store micro-operation would be consecutive. That is, the same registers are being used with consecutive constants or offsets for the displacement. In an implementation, the displacement can be positive or negative.

In the event that the store micro-operations have the same data sizes and use consecutive addresses, the SFDL128fuses the consecutive store micro-operations into one store micro-operation with two times the data size. In particular, the store micro-operation with the lower address is converted from a store micro-operation with data size x to a store micro-operation with data size 2x and the store micro-operation with the higher address is converted from a store micro-operation with data size x to a store data HI micro-operation where the load/store micro-operation and address generation micro-operation components are suppressed. That is, the store data HI micro-operation only uses a queue entry in the ALSQ152. Queue entries in the STQ140and AGSQ154are not needed as store fusion leverages the greater STQ bandwidth that is available for larger data size store micro-operations in the store micro-operation with data size 2x.

In order to maintain age-ordered operation or in-order queues, every store micro-operation is associated with a particular store queue entry or store queue identifier. That store queue entry is assigned to the store micro-operation at dispatch in program order (e.g., a store micro-operation might be assigned to store queue entry 0, and the next store micro-operation in the program order would be assigned to store queue entry 1, the next store micro-operation in the program order would be assigned to store queue entry 2, and so on). The SFDL128uses this information to set the same store queue entry number in both the store micro-operation with data size 2x and the store data HI micro-operation. In addition, the SFDL128and dispatch logic129sets the micro-operation type in the store data HI micro-operation to indicate that this data is the high part of the store micro-operation with data size 2x. The ALU0-ALU3156uses the micro-operation type to understand what needs to be done with the data in the store data HI micro-operation.

Once the SFDL128has fused the consecutive store micro-operations as described herein, the dispatch logic129dispatches the store micro-operation with data size 2x and the store data HI micro-operation to the ALSQs152and AGSQs154, as appropriate. The ALSQs152and AGSQs154issue the store micro-operation with data size 2x and the store data HI micro-operation to ALU0-ALU3156, as appropriate. The ALU0-ALU3156sends a control bit(s) via the store fusion control interface159to the STQs140to indicate that the data in the store data HI micro-operation is to be written in the higher or upper part of the store data field. That is, the control bit(s) indicates that the data in the store data HI micro-operation needs to be shifted when stored. The data in the store micro-operation with data size 2x is written in the lower part of the store data field. The STQs140perform the required writes. In an implementation, a store load forward operation can be executed once both the store micro-operation with data size 2x and the store data HI micro-operation have delivered their data.

In an illustrative example, consider the following two instructions:

In a conventional architecture, the above two instructions become two store micro-operations:

In accordance with the store fusion method and system, the two store micro-operations would become:

mov.o[rbx + 8], r8stdatahi.qr9
where the first micro-operation is a 128 bit store micro-operation and the second micro-operation is a store data only micro-operation. As described herein, the control bit(s) passed from the ALU(s) to the STQ(s) indicates to the STQ(s) to put the data from the store data only micro-operation in the upper 64b of the STQ(s). This is an example of a positive displacement.

In another positive address direction illustrative example, the instructions may be a MOV dword [addr] instruction followed by a MOV dword [addr+4] instruction. In this instance, the first store micro-operation stores to a lower address than the second store micro-operation and the two 4 byte store micro-operations are fused into one 8 byte store micro-operation. In particular, the first store micro-operation does use an AGSQ or STQ queue entry or token and is converted to a store micro-operation with a data size of 64 bits. The store data micro-operation component of the second store micro-operation may have an opcode value (that is functionally similar to a mov) to indicate that it is fused LO store data. The second store micro-operation does not use an AGSQ or STQ queue entry or token and is converted to a store data only micro-operation. The store data only micro-operation may have an opcode value (that is functionally similar to a shift-left-immediate with an immediate value of 32) to indicate that it is fused HI store data.

In another illustrative example, a negative address direction may be used. For example, a PUSH32b instruction followed by another PUSH32b instruction or a MOV dword [addr] followed by a MOV dword [addr-4] instruction. In this instance, the second store micro-operation stores to a lower address than the first store micro-operation and the two 4 bytes store micro-operations are fused into one 8 byte store micro-operation. In particular, the first store micro-operation does not use an AGSQ or STQ queue entry or token and is converted to a store data only micro-operation. The store data only micro-operation may have an opcode value (that is functionally similar to a shift-left-immediate with an immediate value of 32) to indicate that it is fused HI store data. The second store micro-operation does use an AGSQ or STQ queue entry or token and is converted to a store micro-operation with a data size of 64 bits. The store data micro-operation component of the second store micro-operation may have an opcode value (that is functionally similar to a mov) to indicate that it is fused LO store data. In another example the instructions may be a PUSH64b instruction followed by another PUSH64b instruction or a MOV qword [addr] followed by a MOV qword [addr-8] instruction. This operates similarly except that the data size is doubled from 64 bits to 128 bits.

There are additional considerations or changes in pipeline processing with respect to store fusion. A retire unit, as shown as retire unit208inFIG. 2, does not signal a store-retire indication on the store data only operation. Stores in the retire queue208normally have a “store” bit that is used by the retire hardware to indicate how many stores have retired (become non-speculative) in a cycle. Suppressing this store-retirement indication for the store data only operation in a fused store can be achieved by simply not setting the “store” bit in its retire queue entry.

Exception handling also changes for fused stores. It is possible that one of the stores should take an architectural or micro-architectural exception, such as a page fault or trap. However, with fused stores, the exception logic doesn't see the stores as independent operations since the exception logic can only detect an exception on the single fused store. The exception logic cannot determine which store architecturally should have taken the exception. This is handled by requiring that the fused store micro-operations are dispatched as an atomic group with an extra bit in the retire queue, for example retire queue208, indicating a fused store operation. Should a fault or trap occur on the fused store operation, the exception is converted into a resync fault and the instructions are re-executed, and on this re-execution, the store fusion mechanism is temporarily disabled for one dispatch cycle so that they are dispatched without fusing. If the exception recurs, it will now be handled in a conventional manner.

There are additional considerations when implementing store fusion with memory renaming. Without taking these considerations into account, this can result in lost opportunities for memory renaming. For example, without store fusion, a load instruction that exactly matches an older store instruction to the same address would be able to be successfully memory-renamed to the older store. However, with store fusion, the older store may be fused as the HI part of a fused store. The load address would not exactly match the fused store's address, and the normal memory-renaming logic will cause the load to fail memory-renaming, resulting in the memory-renamed load taking a resync-fault, causing loss of performance. This is resolved in an implementation by having the fused store micro-operation act as if it were a real store for the purpose of memory renaming, but remembering that it was the HI part of a fused store using an additional HI store bit in the memory-renaming tracking structure (known as a memfile) for the store data HI micro-operation indicating that it is HI part of a fused store. When a load gets memory-renamed to a HI fused store, the memfile passes that HI store bit to the load with its memory renamed STQ ID information. The load uses the HI store bits on all of the stores in the memfile to adjust its renamed STQ ID to point to the correct store (since HI stores don't occupy a STQ entry). Additionally, when renaming is verified, the load's HI store bit is used to check that the load's address is equal to the store's address+load data size instead of exactly matching. This means that the load exactly matched the address of the upper half of the fused store, and so memory renaming was correct and successful.

FIG. 2is a high level block diagram of the interfaces between dispatch logic201, SFDL Op 0/1-SFDL Op 4/5202and an integer scheduler/execution unit200in accordance with certain implementations. In particular, micro-operations Op0-Op5 are dispatched via associated dispatch slots in a dispatch logic201to the integer scheduler/execution unit200and a SFDL Op 0/1-SFDL Op 4/5202is connected to the dispatch logic201to determine store fusion candidates.

The integer scheduler/execution unit200includes an integer renamer/mapper203which is connected to ALSQ0-ALSQ3204, AGSQ0-AGSQ1206and a retire queue208. The ALSQ0-ALSQ3204and AGSQ0-AGSQ1206are further connected to forwarding multiplexors210, which in turn are connected to ALU0-ALU3212and AGU0-AGU1214, respectively. The ALU0-ALU3212are connected to STQs218via a pair of multiplexers M0and M1213and a store data interface232. The AGU0-AGU1214are connected to LDQs216and STQs218and retire queue208. The integer scheduler/execution unit200also includes a physical file register220which is connected to ALU0-ALU3212, LDQs216and STQs218. The LDQs216and STQs218are connected to AGSQ0-AGSQ1206via path230to send deallocation signals and to retire queue208.

Similar toFIG. 1, micro-operations are examined by the SFDL Op 0/1-SFDL Op 4/5202to determine whether adjacent micro-operations are consecutive store micro-operations. Adjacent micro-operations refers to micro-operations flowing through adjacent dispatch slots and consecutive store micro-operations refers to both of the adjacent micro-operations being store micro-operations. In particular, SFDL Op 0/1 determines a store fusion candidate from micro-operations 0 and 1, SFDL Op 1/2 determines a store fusion candidate from micro-operations 1 and 2, SFDL Op 2/3 determines a store fusion candidate from micro-operations 2 and 3, SFDL Op 3/4 determines a store fusion candidate from micro-operations 3 and 4, and SFDL Op 4/5 determines a store fusion candidate from micro-operations 4 and 5. Each of SFDL Op 0/1-SFDL Op 4/5202also confirms whether the consecutive store micro-operations have the same data size and are accessing consecutive addresses as described herein. The SFDL logic operates mostly in parallel, checking pairs of adjacent micro-operations independently for store fusion eligibility. However, priority is applied such that the oldest micro-operations are fused with higher priority. Furthermore, once a micro-operation is part of a fused store, that micro-operations is ineligible to participate in store fusion for the next-oldest SFDL block. For example, imagine three store micro-operations, dispatched in Op 0, Op 1, and Op 2, all to consecutive bytes (consecutive addresses). Both SFDL Op 0/1 and SFDL Op 1/2 would determine that their respective operations are able to be fused. SFDL Op 0/1 takes priority and fuses Op 0 and Op 1 into a fused store operation. Because Op 1 was part of an older fused store, it is ineligible to be fused with Op 2, so SFDL Op 1/2 is not allowed to fuse Op 1 and Op2 into a fused store operation.

Each of SFDL Op 0/1-SFDL Op 4/5202fuses the appropriate store micro-operations into a store micro-operation with two times the data size and a store data HI micro-operation where the load/store micro-operation and address generation micro-operation components are suppressed and only a queue entry in the ALSQ0-ALSQ3204is needed. As stated herein, each SFDL Op 0/1-SFDL Op 4/5202sets a same STQ218queue entry number in both the store micro-operation with data size 2x and the store data HI micro-operation and sets the micro-operation type in the store data HI micro-operation to indicate that this data is the high part of the store micro-operation with data size 2x.

Once each SFDL Op 0/1-SFDL Op 4/5202has fused the consecutive store micro-operations as needed, the dispatch logic201dispatches the store micro-operation with data size 2x and the store data HI micro-operation to the ALSQ0-ALSQ3204and AGSQ0-AGSQ1206, as appropriate. The ALSQ0-ALSQ3204and AGSQ0-AGSQ1206issue the store micro-operation with data size 2x and the store data HI micro-operation to ALU0-ALU3212. The ALU0-ALU3212sends a control bit(s) via the store data interface232to the STQs218to indicate that the data in the store data HI micro-operation is to be written in the higher or upper part of the store data field. The STQs218perform the required writes.

FIG. 3is a high level block and flow diagram of a load-store/data cache (LSDC) unit300in accordance with certain implementations and functions as described herein forFIGS. 1 and 2. The LSDC unit300includes a LDQ302, a STQ304, a load 0 (L0) picker306and a load 1 (L1) picker308. The STQ304gets data from ALUs (not shown) along with control bit(s) via a store data interface305which indicates that the data in a store data HI micro-operation needs to be shifted when stored. The LO picker306is connected to a translation lookaside buffer (TLB) and micro-tag access pipeline 0 (TLB0)310and a data cache access pipeline (data pipe 0)312. The L1 picker308is connected to a translation lookaside buffer (TLB) and micro-tag access pipeline 1 (TLB1)314and a data cache access pipeline (data pipe 1)316. The TLB0310and TLB1314are further connected to L1/L2 TLB318, a page walker323, and micro-tag array319, which in turn is connected to a miss address buffer (MAB)320, and assists in reading data from a cache322. The data pipe 0312and data pipe 1316are connected to the cache322. The STQ304is connected to a pre-fetcher324and a store pipe picker326, which in turn is connected to a store pipeline (STP)328. The STP328is also connected to the L1/L2 TLB318and the micro-tag array319. The STQ304is further connected to a store commit pipeline330, which in turn is connected to a write combining buffer (WCB)332and the cache322.

FIG. 4is a flow diagram400of a method for store fusion in accordance with certain implementations. Micro-operations are dispatched via a dispatch logic (step402). A store fusion detection logic detects whether adjacent micro-operations are consecutive store micro-operations (step404). Adjacent micro-operations refers to micro-operations flowing through adjacent dispatch slots and the consecutive store micro-operations refers to both of the adjacent micro-operations being store micro-operations. If the adjacent micro-operations are not consecutive store micro-operations, then review the next set of dispatched micro-operations (step402). If the adjacent micro-operations are consecutive store micro-operations, then the store fusion detection logic determines whether the consecutive store micro-operations have the same data size (step406). If the consecutive store micro-operations are not the same size, then review the next set of dispatched micro-operations (step402). If the consecutive store micro-operations are the same size, then the store fusion detection logic determines whether the consecutive store micro-operations are accessing consecutive addresses (step408). If the consecutive store micro-operations are not accessing consecutive addresses, then review the next set of dispatched micro-operations (step402). If the consecutive store micro-operations are accessing consecutive addresses, then the store fusion detection logic determines if an older micro-operation of the two micro-operations under consideration are part of an older fused store operation (step410). If part of older store fusion, no store fusion is done (step412) and review the next set of dispatched micro-operations (step402). If not part of older fused store operation, the store fusion detection logic fuses the consecutive store micro-operations into a store micro-operation with two times the data size and a store data HI micro-operation (step414).

The store fusion detection logic sets a same store queue entry number in both the store micro-operation with data size 2x and the store data HI micro-operation (step416). The store fusion detection logic and dispatch logic sets a micro-operation type in the store data HI micro-operation to indicate to the ALUs that this data is the high part of the store micro-operation with data size 2x (step418). ALUs send control bit(s) to the STQs so that the data in the store data HI micro-operation is shifted when stored (step420). The data in the store micro-operation with data size 2x is written in the lower part of the store data field (step422). The order of operations is illustrative only and other orders can be used.

FIG. 5is a block diagram of an example device500in which one or more portions of one or more disclosed examples are implemented. The device500includes, for example, a head mounted device, a server, a computer, a gaming device, a handheld device, a set-top box, a television, a mobile phone, or a tablet computer. The device500includes a compute node or processor502, a memory504, a storage506, one or more input devices508, and one or more output devices510. The device500also optionally includes an input driver512and an output driver514. It is understood that the device500includes additional components not shown inFIG. 5.

The compute node or processor502includes a central processing unit (CPU), a graphics processing unit (GPU), a CPU and GPU located on the same die, or one or more processor cores, wherein each processor core may be a CPU or a GPU. The memory504is located on the same die as the compute node or processor502, or is located separately from the compute node or processor502. In an implementation, the memory504includes a volatile or non-volatile memory, for example, random access memory (RAM), dynamic RAM, or a cache.

The input driver512communicates with the compute node or processor502and the input devices508, and permits the compute node or processor502to receive input from the input devices508. The output driver514communicates with the compute node or processor502and the output devices510, and permits the processor502to send output to the output devices510. It is noted that the input driver512and the output driver514are optional components, and that the device500will operate in the same manner if the input driver512and the output driver514are not present.

In general, a method for fusing store micro-operations includes determining whether adjacent micro-operations are consecutive store micro-operations. The adjacent micro-operations refers to micro-operations flowing through adjacent dispatch slots and the consecutive store micro-operations refers to both of the adjacent micro-operations being store micro-operations. A determination is made as to whether the consecutive store micro-operations have same data size and are accessing consecutive addresses. The consecutive store micro-operations are fused into a store micro-operation with twice the data size and a store data only micro-operation. In an implementation, a same store queue entry number is set for the store micro-operation with twice the data size and the store data only micro-operation. In an implementation, a micro-operation type is set in the store data only micro-operation to indicate that data in the store data only micro-operation is an upper data part with respect to the store micro-operation with twice the data size. In an implementation, at least one control bit is sent to a store queue to facilitate shifting of the data when stored. In an implementation, the data in the store micro-operation with twice the data size is stored in a lower part of a store data field and data in the store data only micro-operation is stored in an upper part of the store data field. In an implementation, the store data only micro-operation suppresses use of store queue entries and address generation queue entries. In an implementation, an addressing mode of is reviewed of each of the consecutive micro-operations. In an implementation, the consecutive store micro-operation having a lower address is converted to the store micro-operation with twice the data size. In an implementation, the consecutive store micro-operation having a higher address is converted to the store data only micro-operation. In an implementation, a store-retire indication is suppressed with respect to the store data only micro-operation. In an implementation, an occurrence of an exception with respect to at least one of the store micro-operation with twice the data size and the store data only micro-operation results in re-execution of the adjacent micro-operations without fusing. In an implementation, a high store bit is set in a memory-renaming tracking structure for the store data only micro-operation and the high store bit is used to determine store queue entry.

In general, a processor for fusing store micro-operations includes a dispatch logic configured to dispatch micro-operations and a store fusion detection logic connected to the dispatch logic. The store fusion detection logic is configured to determine whether adjacent micro-operations are consecutive store micro-operations, wherein the adjacent micro-operations refers to micro-operations flowing through adjacent dispatch slots and the consecutive store micro-operations refers to both of the adjacent micro-operations being store micro-operations, determine whether the consecutive store micro-operations have same data size, determine whether the consecutive store micro-operations are accessing consecutive addresses and fuse the consecutive store micro-operations into a store micro-operation with twice the data size and a store data only micro-operation. In an implementation, the dispatch logic and the store fusion detection logic are configured to set a same store queue entry number for the store micro-operation with twice the data size and the store data only micro-operation. In an implementation, the dispatch logic and the store fusion detection logic are configured to set a micro-operation type in the store data only micro-operation to indicate that data in the store data only micro-operation is an upper data part with respect to the store micro-operation with twice the data size. In an implementation, the processor includes a store queue and an arithmetic logic unit in communication with the store queue. The arithmetic logic unit configured to send at least one control bit to the store queue to facilitate shifting of the data when stored. In an implementation, the data in the store micro-operation with twice the data size is stored in a lower part of a store data field and data in the store data only micro-operation is stored in an upper part of the store data field. In an implementation, the store data only micro-operation suppresses use of store queue entries and address generation queue entries. In an implementation, the consecutive store micro-operation having a lower address is converted to the store micro-operation with twice the data size and the consecutive store micro-operation having a higher address is converted to the store data only micro-operation. In an implementation, a store-retire indication is suppressed with respect to the store data only micro-operation and wherein an occurrence of an exception with respect to at least one of the store micro-operation with twice the data size and the store data only micro-operation results in re-execution of the adjacent micro-operations without fusing.