System, apparatus and method for program order queue (POQ) to manage data dependencies in processor having multiple instruction queues

Patent metadata

Field	Value
Publication number	US-11243775-B2
Application number	US-201916364688-A
Country	US
Kind code	B2
Filing date	Mar 26, 2019
Priority date	Mar 26, 2019
Publication date	Feb 8, 2022
Grant date	Feb 8, 2022

Abstract

In one embodiment, an apparatus includes: a plurality of registers; a first instruction queue to store first instructions; a second instruction queue to store second instructions; a program order queue having a plurality of portions each associated with one of the plurality of registers, each of the portions having entries to store a state of an instruction, the state comprising an encoding of a use of the register by the instruction and a source instruction queue for the instruction; and a dispatcher to dispatch for execution the first and second instructions from the first and second instruction queues based at least in part on information stored in the program order queue, to manage instruction dependencies between the first instructions and the second instructions. Other embodiments are described and claimed.

First claim

What is claimed is:

1. An apparatus comprising:
a plurality of registers;
a memory instruction queue to exclusively store memory instructions to be dispatched to one or more execution circuits, each memory instruction comprising a memory source operand and a memory destination operand;
an arithmetic instruction queue to store arithmetic instructions to be dispatched to the one or more execution circuits, each arithmetic instruction comprising at least one arithmetic source operand and an arithmetic destination operand;
a plurality of program order queues each associated with a different one of the plurality of registers to be involved in execution of the memory instructions and the arithmetic instructions, wherein a first program order queue associated with a first register comprises a plurality of entries each to store a state of an instruction including the first register as one of the memory source operand, the memory destination operand, the at least one arithmetic source operand, and the arithmetic destination operand, the state comprising an encoding of a use of the first register by the instruction and a source instruction queue for the instruction, the source instruction queue being one of the memory instruction queue and the arithmetic instruction queue; and
a dispatcher to dispatch for execution the memory instructions from the memory instruction queue and the arithmetic instructions from the arithmetic instruction queue for the execution by the one or more execution circuits based at least in part on information stored in the program order queue, to manage instruction dependencies between the memory instructions and the arithmetic instructions;
wherein for a first instruction having a first source operand that identifies the first register, the first program order queue is to store in a first entry of the first program order queue a read event state;
wherein for a second instruction having a second destination operand that identifies the first register, the first program order queue is to store in a second entry of the first program order queue a first write event state.

2. The apparatus of claim 1 , wherein the instruction dependencies include write-after-read dependencies, read-after-write dependencies and write-after-write dependencies.

3. The apparatus of claim 1 , wherein for the first instruction having a first destination operand that identifies a second register, the first program order queue is to store in a first entry of a second program order queue associated with the second register a write event state, wherein the first source operand is one of the memory source operand and the at least one arithmetic source operand and the first destination operand is one of the memory destination operand and the arithmetic destination operand.

4. The apparatus of claim 3 , wherein the read event state is to identify that the first instruction is stored in the source instruction queue.

5. The apparatus of claim 3 , wherein the first program order queue and the second program order queue are to store the read event state and the write event state on allocation of the first instruction into the source instruction queue.

6. The apparatus of claim 3 , wherein the dispatcher is to dispatch the first instruction from the source instruction queue to the one or more execution circuits when a top entry of the first program order queue includes the read event state and a top entry of the second program order queue includes the write event state.

7. The apparatus of claim 6 , wherein the first program order queue is to dequeue the top entry of the first program order queue when the first instruction is completed.

8. The apparatus of claim 6 , wherein the dispatcher is to stall the first instruction in the source instruction queue when the top entry of the first program order queue does not include the read event state or the top entry of the second program order queue does not include the write event state.

9. The apparatus of claim 1 , wherein for the first instruction having a destination operand that identifies the first register, the first program order queue is to store a read write event state.

10. The apparatus of claim 1 , wherein the apparatus comprises a single program multiple data processor including a plurality of execution lanes each including the one or more execution circuits, wherein each of the plurality of execution lanes is to execute instructions dispatched by the dispatcher.

11. The apparatus of claim 1 , wherein the memory instruction queue and the arithmetic instruction queue comprise in-order queues.

12. A machine-readable medium having stored thereon instructions, which if performed by a machine cause the machine to perform a method comprising:
receiving a first instruction for allocation into a first instruction queue of a processor, the first instruction identifying a first register of a plurality of registers as a first source operand and identifying a second register of the plurality of registers as a destination operand, the first instruction queue being one of a memory instruction queue to exclusively store memory instructions and an arithmetic instruction queue to store arithmetic instructions, wherein each register of the plurality of registers is associated with a single program order queue of a plurality of program order queues;
enqueuing, into a first entry of a first program order queue associated with the first register, a read event state that indicates that the first instruction is to read the first register and is allocated into the first instruction queue;
enqueuing, into a second entry of the first program order queue associated with the first register, a second write event state that indicates that a second instruction is to write the first register;
enqueuing, into a second program order queue associated with the second register, a write event state that indicates that the first instruction is to write the second register and is allocated into the first instruction queue; and
controlling dispatch of the first instruction from the first instruction queue to at least one execution circuit based on contents of at least one entry of the first program order queue and at least one entry of the second program order queue.

13. The machine-readable medium of claim 12 , wherein the method further comprises:
selecting the first instruction for dispatch to the at least one execution circuit;
determining whether a top entry of the first program order queue has the read event state that indicates that the first instruction is to read the first register and is allocated into the first instruction queue; and
responsive, at least in part to determining that the top entry of the first program order queue has the read event state that indicates that the first instruction is to read the first register and is allocated into the first instruction queue, dispatching the first instruction to the at least one execution circuit.

14. The machine-readable medium of claim 13 , wherein the method further comprises:
responsive to dispatching the first instruction to the at least one execution circuit, dequeuing the top entry of the first program order queue; and
responsive to completion of the first instruction in the at least one execution circuit, dequeuing a top entry of the second program order queue.

15. The machine-readable medium of claim 13 , wherein the method further comprises responsive to determining that the top entry of the first program order queue does not have the read event state that indicates that the first instruction is to read the first register and is allocated into the fir

Assignees

• Intel Corp

Inventors

• Ayupov Andrey
• Srinivasan Srikanth T
• Pearce Jonathan D
• Sheffield David B

Classifications

• Y02D10/00

  Energy efficient computing, e.g. low power processors, power management or thermal management · CPC title

• G06F9/3887

  controlled by a single instruction for multiple data lanes [SIMD] · CPC title

• G06F9/3851

  from multiple instruction streams, e.g. multistreaming · CPC title

• G06F9/3838 Primary

  Dependency mechanisms, e.g. register scoreboarding · CPC title

• G06F9/3842

  Speculative instruction execution · CPC title