# US 11,113,068 B1 · Performing flush recovery using parallel walks of sliced reorder buffers (SROBs)

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,113,068 B1
- Document ID: US11113068B1
- Status: Granted
- Kind: B1
- Application number: 16/986,650
- Filed: 2020-08-06
- Granted: 2021-09-07
- Earliest claimed: 2020-08-06
- Assignees: Microsoft Technology Licensing, LLC
- Applicants: Microsoft Technology Licensing, LLC
- Inventors: Yusuf Cagatay Tekmen; Rodney Wayne Smith; Kiran Ravi Seth; Shivam Priyadarshi
- Web page: https://patentgrep.com/patent/US11113068B1

## CPC

- G06F 9/3861: {Recovery, e.g. branch miss-prediction, exception handling (error detection or correction G06F11/00)}
- G06F 9/3856: {Reordering of instructions, e.g. using queues or age tags}
- G06F 9/3863: {using multiple copies of the architectural state, e.g. shadow registers}
- G06F 9/384: {Register renaming}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Performing flush recovery using parallel walks of sliced reorder buffers (SROBs) is disclosed herein. In one exemplary embodiment, a register mapping circuit provides a rename mapping table (RMT) comprising RMT entries representing logical register number (LRN) to physical register number (PRN) mappings. The register mapping circuit also provides an SROB comprising multiple SROB slices that each corresponds to a respective LRN. Each SROB slice tracks uncommitted instructions that write to the LRN corresponding to that SROB slice, and maintains those instructions in program order with respect to each other. Upon detecting an uncommitted instruction writing to an LRN, the register mapping circuit allocates an SROB slice entry in the SROB slice corresponding to the LRN. When an pipeline flush from a target instruction occurs, the register mapping circuit restores RMT entries of the RMT to their prior mapping states based on parallel walks of the SROB slices of the SROB.

## Claims

### Claim 1

A register mapping circuit in a processor device, the register mapping circuit comprising:
a rename map table (RMT) comprising a plurality of RMT entries each representing a mapping of a logical register number (LRN) among a plurality of LRNs to a physical register number (PRN) among a plurality of PRNs; and
a reorder buffer (ROB) comprising a plurality of ROB entries;
a sliced reorder buffer (SROB) subdivided into a plurality of SROB slices each comprising a plurality of SROB slice entries, wherein each SROB slice is configured to track only uncommitted instructions that write to a respective LRN among the plurality of LRNs;
the register mapping circuit configured to:
detect, within an execution pipeline of the processor device, an uncommitted instruction comprising a write instruction to a destination LRN among the plurality of LRNs;
allocate, to the uncommitted instruction, an SROB slice entry among the plurality of SROB slice entries of an SROB slice corresponding to the destination LRN among the plurality of SROB slices of the SROB;
receive an indication of a pipeline flush from a target instruction within the execution pipeline; and
responsive to receiving the indication of the pipeline flush, restore the plurality of RMT entries to a corresponding plurality of prior mapping states, based on sequential accesses, performed in parallel, of the plurality of SROB slices corresponding to LRNs of the plurality of RMT entries.

### Claim 2 (depends on 1)

The register mapping circuit of claim 1, wherein:
the plurality of RMT entries comprises a respective plurality of program order identifiers; and
the register mapping circuit is configured to restore the plurality of RMT entries to the corresponding plurality of prior mapping states further based on the plurality of program order identifiers of the plurality of RMT entries.

### Claim 3 (depends on 1)

The register mapping circuit of claim 1, wherein:
the register mapping circuit is further configured to allocate the plurality of ROB entries to a corresponding plurality of uncommitted instructions in the execution pipeline of the processor device, wherein the plurality of uncommitted instructions comprises the uncommitted instruction.

### Claim 4 (depends on 3)

The register mapping circuit of claim 3, wherein a count of the plurality of SROB slice entries of each SROB slice among the plurality of SROB slices of the SROB equals a count of the plurality of ROB entries.

### Claim 5 (depends on 3)

The register mapping circuit of claim 3, wherein:
a count of the plurality of SROB slice entries of each SROB slice among the plurality of SROB slices of the SROB is less than a count of the plurality of ROB entries; and
the register mapping circuit is further configured to allocate the SROB slice entry by being configured to:
determine that no SROB slice entry among the plurality of SROB slice entries of the SROB slice is available for allocation; and
responsive to determining that no SROB slice entry among the plurality of SROB slice entries of the SROB slice is available for allocation:
initiate a stall of the execution pipeline of the processor device; and
allocate the SROB slice entry responsive to resolution of the stall.

### Claim 6 (depends on 3)

The register mapping circuit of claim 3, wherein:
a count of the plurality of SROB slice entries of each SROB slice of the plurality of SROB slices of the SROB is less than a count of the plurality of ROB entries; and
the register mapping circuit is further configured to allocate the SROB slice entry by being configured to:
determine that no SROB slice entry among the plurality of SROB slice entries of the SROB slice is available for allocation; and
responsive to determining that no SROB slice entry among the plurality of SROB slice entries of the SROB slice is available for allocation, allocate an oldest SROB slice entry.

### Claim 7 (depends on 6)

The register mapping circuit of claim 6, wherein the register mapping circuit is configured to restore the plurality of RMT entries to the corresponding plurality of prior mapping states by being configured to:
determine, while performing a walk of the SROB slice, that overwritten contents of the oldest SROB slice entry are necessary for flush recovery; and
responsive to determining that the overwritten contents of the oldest SROB slice entry are necessary for flush recovery, restore the plurality of RMT entries to the corresponding plurality of prior mapping states further based on a walk of the ROB.

### Claim 8 (depends on 3)

The register mapping circuit of claim 3, wherein:
the register mapping circuit further comprises a partially serial ROB (PSROB);
a count of the plurality of SROB slice entries of each SROB slice of the plurality of SROB slices of the SROB is less than a count of the plurality of ROB entries; and
the register mapping circuit is further configured to allocate the SROB slice entry by being configured to:
determine that no SROB slice entry among the plurality of SROB slice entries of the SROB slice is available for allocation; and
responsive to determining that no SROB slice entry among the plurality of SROB slice entries of the SROB slice is available for allocation:
evict an oldest SROB slice entry of the plurality of SROB slice entries of the SROB slice to the PSROB; and
allocate the oldest SROB slice entry.

### Claim 9 (depends on 8)

The register mapping circuit of claim 8, wherein the register mapping circuit is configured to restore the plurality of RMT entries to the corresponding plurality of prior mapping states by being configured to:
determine, while performing a walk of the SROB slice, that overwritten contents of the evicted oldest SROB slice entry are necessary for flush recovery; and
responsive to determining that the overwritten contents of the evicted oldest SROB slice entry are necessary for flush recovery, restore the plurality of RMT entries to the corresponding plurality of prior mapping states further based on a walk of the PSROB.

### Claim 10

A method for performing flush recovery using parallel walks of sliced reorder buffers (SROBs), the method comprising:
detecting, by a register mapping circuit of a processor device, an uncommitted instruction within an execution pipeline of the processor device, the uncommitted instruction comprising a write instruction to a destination logical register number (LRN) among a plurality of LRNs, wherein the register mapping circuit comprises a reorder buffer (ROB);
allocating, to the uncommitted instruction, an SROB slice entry among a plurality of SROB slice entries of an SROB slice corresponding to the destination LRN among a plurality of SROB slices of an SROB of the processor device, wherein each SROB slice of the plurality of SROB slices is configured to track only uncommitted instructions that write to a respective LRN among the plurality of LRNs;
receiving an indication of a pipeline flush from a target instruction within the execution pipeline; and
responsive to receiving the indication of the pipeline flush, restoring a plurality of rename map table (RMT) entries of an RMT to a corresponding plurality of prior mapping states, based on sequential accesses, performed in parallel, of the plurality of SROB slices corresponding to LRNs of the plurality of RMT entries.

### Claim 11 (depends on 10)

The method of claim 10, wherein:
the plurality of RMT entries comprises a respective plurality of program order identifiers; and
restoring the plurality of RMT entries to the corresponding plurality of prior mapping states is further based on the plurality of program order identifiers of the plurality of RMT entries.

### Claim 12 (depends on 10)

The method of claim 10, further comprising allocating a plurality of reorder buffer (ROB) entries of the ROB to a corresponding plurality of uncommitted instructions in the execution pipeline of the processor device, wherein the plurality of uncommitted instructions comprises the uncommitted instruction.

### Claim 13 (depends on 12)

The method of claim 12, wherein a count of the plurality of SROB slice entries of each SROB slice among the plurality of SROB slices of the SROB equals a count of the plurality of ROB entries.

### Claim 14 (depends on 12)

The method of claim 12, wherein:
a count of the plurality of SROB slice entries of each SROB slice among the plurality of SROB slices of the SROB is less than a count of the plurality of ROB entries; and
allocating the SROB slice entry comprises:
determining that no SROB slice entry among the plurality of SROB slice entries of the SROB slice is available for allocation; and
responsive to determining that no SROB slice entry among the plurality of SROB slice entries of the SROB slice is available for allocation:
initiating a stall of the execution pipeline of the processor device; and
allocate the SROB slice entry responsive to resolution of the stall.

### Claim 15 (depends on 12)

The method of claim 12, wherein:
a count of the plurality of SROB slice entries of each SROB slice of the plurality of SROB slices of the SROB is less than a count of the plurality of ROB entries; and
allocating the SROB slice entry comprises:
determining that no SROB slice entry among the plurality of SROB slice entries of the SROB slice is available for allocation; and
responsive to determining that no SROB slice entry among the plurality of SROB slice entries of the SROB slice is available for allocation, allocating the oldest SROB slice entry.

### Claim 16 (depends on 15)

The method of claim 15, wherein restoring the plurality of RMT entries to the corresponding plurality of prior mapping states comprises:
determining, while performing a walk of the SROB slice, that overwritten contents of the oldest SROB slice entry are necessary for flush recovery; and
responsive to determining that the overwritten contents of the oldest SROB slice entry are necessary for flush recovery, restoring the plurality of RMT entries to the corresponding plurality of prior mapping states further based on a walk of the ROB.

### Claim 17 (depends on 12)

The method of claim 12, wherein:
a count of the plurality of SROB slice entries of each SROB slice of the plurality of SROB slices of the SROB is less than a count of the plurality of ROB entries; and
allocating the SROB slice entry comprises:
determining that no SROB slice entry among the plurality of SROB slice entries of the SROB slice is available for allocation; and
responsive to determining that no SROB slice entry among the plurality of SROB slice entries of the SROB slice is available for allocation:
evicting an oldest SROB slice entry of the plurality of SROB slice entries of the SROB slice to a partially serial ROB (PSROB); and
allocating the oldest SROB slice entry.

### Claim 18 (depends on 17)

The method of claim 17, wherein restoring the plurality of RMT entries to the corresponding plurality of prior mapping states comprises:
determining, while performing a walk of the SROB slice, that overwritten contents of the evicted oldest SROB slice entry are necessary for flush recovery; and
responsive to determining that the overwritten contents of the evicted oldest SROB slice entry are necessary for flush recovery, restoring the plurality of RMT entries to the corresponding plurality of prior mapping states further based on a walk of the PSROB.

### Claim 19

A non-transitory computer-readable medium, having stored thereon computer-executable instructions that, when executed by a processor device, cause the processor device to:
detect an uncommitted instruction within an execution pipeline of the processor device, the uncommitted instruction comprising a write instruction to a destination logical register number (LRN) among a plurality of LRNs, wherein the processor device comprises a reorder buffer (ROB);
allocate, to the uncommitted instruction, a sliced reorder buffer (SROB) slice entry among a plurality of SROB slice entries of an SROB slice corresponding to the destination LRN among a plurality of SROB slices of an SROB of the processor device, wherein each SROB slice of the plurality of SROB slices is configured to track only uncommitted instructions that write to a respective LRN among the plurality of LRNs;
receive an indication of a pipeline flush from a target instruction within the execution pipeline; and
responsive to receiving the indication of the pipeline flush, restore a plurality of rename map table (RMT) entries of an RMT to a corresponding plurality of prior mapping states, based on sequential accesses, performed in parallel, of the plurality of SROB slices corresponding to LRNs of the plurality of RMT entries.

### Claim 20 (depends on 19)

The non-transitory computer-readable medium of claim 19, wherein:
the plurality of RMT entries comprises a respective plurality of program order identifiers; and
the computer-executable instructions cause the processor device to restore the plurality of RMT entries to the corresponding plurality of prior mapping states further based on the plurality of program order identifiers of the plurality of RMT entries.