# US 2013/0297912 A1 · Apparatus and method for dynamic allocation of execution queues

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

- Number: US 2013/0297912 A1
- Document ID: US20130297912A1
- Status: Published application
- Kind: A1
- Application number: 13/462,993
- Filed: 2012-05-03
- Published: 2013-11-07
- Earliest claimed: 2012-05-03
- Assignees: Freescale Semiconductor, Inc.
- Inventors: Thang M. Tran; Sourav Roy
- Web page: https://patentgrep.com/patent/US20130297912A1

## CPC

- G06F 9/3836: {Instruction issuing, e.g. dynamic instruction scheduling or out of order instruction execution}
- G06F 9/3814: {Implementation provisions of instruction buffers, e.g. prefetch buffer; banks}
- G06F 9/3822: {Parallel decoding, e.g. parallel decode units}
- G06F 9/3885: {using a plurality of independent parallel functional units}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A processor reduces the likelihood of stalls at an instruction pipeline by dynamically extending the size of a full execution queue. To extend the full execution queue, the processor temporarily repurposes another execution queue to store instructions on behalf of the full execution queue. The execution queue to be repurposed can be selected based on a number of factors, including the type of instructions it is generally designated to store, whether it is empty of other instruction types, and the rate of cache hits at the processor. By selecting the repurposed queue based on dynamic factors such as the cache hit rate, the likelihood of stalls at the dispatch stage is reduced for different types of program flows, improving overall efficiency of the processor.

## Claims

### Claim 1

A method, comprising:
decoding at a processor a first instruction to determine a first decoded instruction;
in response to determining the first decoded instruction is dependent on a second instruction, assigning the first decoded instruction to a first queue of a plurality of execution queues;
in response to determining the first queue is full, storing the first decoded instruction information at an entry of a second queue of the plurality of execution queues in response to determining the second queue is not full, the second queue able to store independent instructions when it does not store instructions dependent on instructions stored.

### Claim 2 (depends on 1)

The method of claim 1, further comprising arbitrating between entries of the first queue and entries of the second queue for provision to an execution unit of the processor.

### Claim 3 (depends on 1)

The method of claim 1, further comprising:
in response to determining the second queue is full, storing the first instruction information at an entry of a third queue.

### Claim 4 (depends on 3)

The method of claim 3, wherein storing the first instruction information at the entry of the third queue comprises storing the first instruction information at the entry of the third queue in response to determining the third queue does not store a third decoded instruction of a type associated with the third queue, and further comprising:
stalling the first decoded instruction in response to determining the third queue stores the third decoded instruction of the type associated with the third queue.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
determining if the first decoded instruction is dependent on the second instruction based on a scoreboard that keeps track of pending instructions in the first and second queues.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
in response to determining the first decoded instruction is dependent on multiple instructions stored at multiple queues, selecting a queue to store the first decoded instruction based on a specified set of priorities.

### Claim 7 (depends on 1)

The method of claim 1, further comprising selecting the second queue based on a cache miss rate at a cache of the processor.

### Claim 8

A method, comprising:
decoding at a processor a first instruction to determine a first decoded instruction;
selecting a queue to store the first decoded instruction based on a hit rate at a cache of the processor.

### Claim 9 (depends on 8)

The method of claim 8, wherein the first decoded instruction is dependent on a second instruction of a first type, and wherein selecting the queue comprises storing the first decoded instruction at a queue designated to store independent instructions of a first type of instruction in response to determining the hit rate is above threshold.

### Claim 10 (depends on 9)

The method of claim 9, wherein selecting the queue comprises storing the first decoded instruction at a queue designated to store independent instructions of a second type different than the first type in response to determining the hit rate is below the threshold.

### Claim 11 (depends on 9)

The method of claim 9, wherein the first type is a load/store type of instruction, and the second type is a complex type of instruction.

### Claim 12 (depends on 9)

The method of claim 9, further comprising:
determining if the first decoded instruction is dependent on the second instruction based on a scoreboard that keeps track of pending instructions in the first and second queues.

### Claim 13 (depends on 8)

The method of claim 8, wherein selecting the queue comprises linking a first queue to a second queue in response to determining the first queue is full, and storing the first decoded instruction at the second queue.

### Claim 14

A processor, comprising:
a decode stage to determine a first decoded instruction;
a plurality of execution queues to store decoded instructions awaiting execution, the plurality of execution queues comprising a first queue and a second queue; and
a queue selection module to assign the first decoded instruction to the first queue, and to store the first decoded instruction information at an entry of the second queue in response to determining that the first decoded instruction is dependent on a second instruction and that the first queue is full.

### Claim 15 (depends on 14)

The processor of claim 14, further comprising:
a scoreboard based to keep track of pending instructions in the plurality of queues, the scoreboard comprising a plurality of entries, each of the plurality of entries associated with a corresponding architectural register and comprising:
a renamed physical register field;
a queue number indicating the location of the most recently instruction with destination operand's architectural register
a valid bit to indicate a pending write to the corresponding architectural register;
the queue selection module to assign the first decoded instruction to the first queue based on one of the pluralities of entries of the scoreboard.

### Claim 16 (depends on 15)

The processor of claim 15, wherein the plurality of execution queues each includes a plurality of queue entries, each of the plurality of queue entries comprising:
a valid scoreboard bit to indicate if an instruction stored at the entry is the most recent instruction with the architectural register of the instruction's destination operand.

### Claim 17 (depends on 15)

The processor of claim 15, wherein the queue selection module is to, in response to determining that the first decoded instruction is dependent on multiple prior instructions, to select the first queue based on a defined priority.

### Claim 18 (depends on 15)

The processor of claim 15, further comprising an arbitrator coupled to the plurality of execution queues to arbitrate between entries of the first queue and entries of the second queue for provision to an execution unit of the processor.

### Claim 19 (depends on 18)

The processor of claim 18, wherein the queue selection module is to store the first instruction information at an entry of a third queue of the plurality of execution queues in response to determining the second queue is full.

### Claim 20 (depends on 15)

The processor of claim 15, wherein the queue selection module is to select the second queue based on a cache miss rate at a cache of the processor.
