MEMORY ORDERING IN ACCELERATION HARDWARE

• US 20180188997A1
• Filed: 12/30/2016
• Published: 07/05/2018
• Est. Priority Date: 12/30/2016
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Granted Patent: US 10,572,376 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 12/109 for multiple virtual address spaces, e.g. segmentation G06F12/1036 takes precedence
• CPC Class Codes: G06F 2212/1008 Correctness of operation, e.g. memory ordering
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 9/30043 LOAD or STORE instructions; Clear instruction
• CPC Class Codes: G06F 9/3838 Dependency mechanisms, e.g. register scoreboarding
• CPC Class Codes: G06F 9/5033 considering data affinity

Abstract

An integrated circuit includes a memory interface, coupled to a memory to store data corresponding to instructions, and an operations queue to buffer memory operations corresponding to the instructions. The integrated circuit may include acceleration hardware to execute a sub-program corresponding to the instructions. A set of input queues may include an address queue to receive, from the acceleration hardware, an address of the memory associated with a second memory operation of the memory operations, and a dependency queue to receive, from the acceleration hardware, a dependency token associated with the address. The dependency token indicates a dependency on data generated by a first memory operation of the memory operations. A scheduler circuit may schedule issuance of the second memory operation to the memory in response to the dependency queue receiving the dependency token and the address queue receiving the address.

Claims

1. An integrated circuit comprising:

a memory interface coupled to a memory, the memory to store data corresponding to instructions being executed for a program;

an operations queue coupled to the memory interface, the operations queue to buffer memory operations corresponding to the instructions;

acceleration hardware to execute a sub-program corresponding to the instructions;

a set of input queues coupled to the acceleration hardware and to the memory interface, wherein the set of input queues are to receive, from the acceleration hardware;

an address, of the memory, associated with a second memory operation of the memory operations; and

a dependency token, associated with the address, that indicates a dependency on data generated by a first memory operation, of the memory operations, which precedes the second memory operation; and

a scheduler circuit coupled to the memory interface, the operations queue, and the set of input queues, wherein the scheduler circuit is to schedule issuance of the second memory operation to the memory in response to receipt, by the set of input queues, of the dependency token and the address.

2. The integrated circuit of claim 1, wherein the scheduler circuit is part of an operations manager circuit, and the operations manager circuit is to issue the second memory operation to the memory in response to completion of the first memory operation, wherein the first memory operation is one of a load operation, a store operation, or a fence operation, and the second memory operation is one of a load operation, a store operation, or a fence operation.

3. The integrated circuit of claim 1, wherein the second memory operation is a load operation, and the set of input queues comprises a load address queue, a store address queue, a store data queue, and a dependency queue, further comprising a completion queue coupled to the acceleration hardware and the memory interface, wherein the completion queue is to buffer the data received from the memory upon completion of the load operation.

4. The integrated circuit of claim 3, wherein one of the first memory operation and the second memory operation, as buffered in the operations queue, comprises memory arguments containing at least one of:

an input queue identifier to indicate an input channel within the set of input queues;

an output queue identifier to indicate an output channel within the completion queue;

a dependency queue identifier to indicate a dependency channel within the dependency queue;

or

an operation type indicator to indicate type of memory operation.

5. The integrated circuit of claim 3, further comprising a set of counters, the set of counters including a first counter to generate the dependency token, and wherein the scheduler circuit is to schedule the load operation further in response to the first counter being unsaturated and having room in the completion queue to complete the second memory operation.

6. The integrated circuit of claim 3, wherein, in response to receipt of the data stored at the address in the memory, the completion queue is further to provide the data to the acceleration hardware with the dependency token.

7. The integrated circuit of claim 3, wherein the scheduler circuit is further to:

determine that a third memory operation, which succeeds the load operation, depends on the data read by the load operation;

duplicate the dependency token of the load operation; and

issue the load operation to the memory with the dependency token, to indicate, to the third memory operation, a dependency on the data read by the load operation.

8. The integrated circuit of claim 1, wherein the second memory operation belongs to a plurality of executable memory operations buffered in the operations queue, further comprising:

a priority encoder to determine the second memory operation has a priority of execution from among the plurality of executable memory operations, and generate a selection signal to identify the second memory operation; and

a multiplexer to select the second memory operation from among the plurality of executable memory operations according to the selection signal.

9. A memory ordering circuit comprising:

a memory interface coupled to a memory, the memory to store data corresponding to instructions being executed for a program;

an operations queue coupled to the memory interface, the operations queue to buffer memory operations corresponding to the instructions;

a set of input queues coupled to acceleration hardware, which is to execute a sub-program corresponding to the instructions, wherein the set of input queues is to receive, from the acceleration hardware;

an address, of the memory, from which to retrieve data for a load operation of the memory operations; and

a dependency token associated with the address, wherein the dependency token indicates a dependency on data stored by a store operation, of the memory operations, that precedes the load operation; and

a scheduler circuit coupled to the memory interface, the operations queue, and the set of input queues, wherein the scheduler circuit is to schedule issuance of the load operation to the memory in response to receipt, by the set of input queues, of the dependency token and the address.

10. The memory ordering circuit of claim 9, wherein the set of input queues comprises:

a load address queue to receive, from the acceleration hardware, the address of the memory;

a store address queue to receive, from the acceleration hardware, the address of the memory, the address associated with the store operation;

a store data queue to receive, from the acceleration hardware, the data associated with the address for the store operation; and

a dependency queue to receive, from the acceleration hardware, the dependency token associated with the address in the load address queue.

11. The memory ordering circuit of claim 9, further comprising a completion queue coupled to the acceleration hardware and the memory interface, wherein the completion queue is to buffer the data received from the address of the memory upon completion of the load operation, and wherein one of the load operation or the store operation, as queued in the operations queue, comprises memory arguments containing at least one of:

an input queue identifier to indicate an input channel within the set of input queues;

an output queue identifier to indicate an output channel within the completion queue;

a dependency queue identifier to indicate a dependency channel within a dependency queue of the set of input queues;

or

an operation type indicator to indicate type of memory operation.

12. The memory ordering circuit of claim 11, wherein the scheduler circuit is further to indicate the load operation is executable in view of the dependency token, availability of the address in the set of input queues, and availability of a slot in the completion queue at which to buffer the data.

13. The memory ordering circuit of claim 12, wherein the memory ordering circuit further comprises an execution circuit coupled to the scheduler circuit, the execution circuit comprising a priority encoder to generate a selector signal to identify the load operation in response to determining the load operation has the priority of execution from among a plurality of executable memory operations in the operations queue, and wherein the execution circuit further comprises a selection circuitry to:

select, in response to the selection signal, the load operation from the plurality of executable memory operations in the operations queue; and

transmit a control signal, indicative of selection of the load operation, to a set of multiplexers to pass the address and data to a memory command to be transmitted to the memory.

14. The memory ordering circuit of claim 12, wherein the scheduler circuit determines that the store operation is executable in response to a store data queue, of the set of input queues, containing the data associated with the address buffered in a store address queue of the set of input queues.

15. The memory ordering circuit of claim 9, further comprising a plurality of counters coupled to a dependency queue, of the set of input queues, and to the scheduler circuit, the plurality of counters including a first counter to generate a second dependency token for a subsequent memory operation that depends on a result of the load operation.

16. The memory ordering circuit of claim 15, wherein the scheduler circuit is further to:

determine that the subsequent memory operation depends on the data retrieved from the address in the memory by the load operation;

provide a dependency argument within the subsequent memory operation, the dependency argument to identify the dependency queue in association with a second address to be buffered in a store address queue of the set of input queues;

trigger generation of a second dependency token in response to arrival of the data from the address in the memory, in completion of the load operation; and

schedule the subsequent memory operation for issuance in response to the dependency queue receiving the second dependency token and the store address queue receiving the second address.

17. The memory ordering circuit of claim 9, further comprising a completion queue coupled to the acceleration hardware and to the scheduler circuit, the completion queue to buffer data received in response to completion of the load operation, and wherein the scheduler circuit is further to:

allocate an index into the completion queue comprising an in-order next slot for the load operation, to generate an index allocation;

communicate the index allocation to the memory to indicate where to send the data in response to completion of the load operation;

enqueue the data within the completion queue upon arrival of the data; and

set to valid a validity bit associated with the in-order next slot.

18. The memory ordering circuit of claim 17, wherein the scheduler circuit is further to dequeue the data and set the validity bit to invalid in response to providing the data to the acceleration hardware in completing the load operation.

19. A method comprising:

queuing memory operations in an operations queue of a memory ordering circuit, the memory operations to interact with a memory in association with acceleration hardware, wherein a processor requests the memory operations to the memory out of program order;

receiving, in a set of input queues from the acceleration hardware, an address of the memory associated with a second memory operation of the memory operations;

receiving, from the acceleration hardware, a dependency token associated with the address, wherein the dependency token indicates a dependency on data generated by a first memory operation, of the memory operations, which precedes the second memory operation; and

scheduling, by the memory ordering circuit, issuance of the second memory operation to the memory in response to receiving the dependency token and the address associated with the dependency token.

20. The method of claim 19, further comprising issuing the second memory operation to the memory in response to completion of the first memory operation, wherein the first memory operation is one of a load operation, a store operation, or a fence operation, and the second memory operation is one of a load operation, a store operation, or a fence operation.

21. The method of claim 19, wherein the first memory operation comprises a store operation and wherein the second memory operation comprises a load operation to read the data at the address in the memory, the method further comprising:

scheduling, by a scheduler circuit of the memory ordering circuit, the second memory operation in response to detecting the dependency token and receipt of the address in a load address queue;

determining that a subsequent memory operation depends on the data retrieved from the address in the memory upon completion of the load operation;

providing a dependency argument within the subsequent memory operation, the dependency argument identifying a dependency queue in association with a second address to be buffered in the set of input queues;

triggering generation of a second dependency token for the dependency queue in response to, with respect to the load operation, one of sending the address to the memory or arrival of the data from the address in the memory; and

scheduling, by the scheduler circuit, the subsequent memory operation for issuance in response to the dependency queue receiving the second dependency token and the set of input queues receiving the second address.

22. The method of claim 19, wherein the memory ordering circuit further comprises a set of counters, the set of counters including a first counter to generate the dependency token, and wherein scheduling the second memory operation for issuance is further in response to the first counter being unsaturated and having room in a completion queue to complete the second memory operation.

23. The method of claim 19, wherein, in response to receiving data stored at the address in the memory upon completion of the second memory operation, the method further comprising providing, by a completion queue, the data to the acceleration hardware with the dependency token.

24. The method of claim 19, wherein the second memory operation of the memory operations belongs to a group of executable memory operations queued in the operations queue, the method further comprising:

determining, by a priority encoder of the memory ordering circuit, the second memory operation has a priority of execution from among the group of executable memory operations;

generating, by the priority encoder, a selection signal identifying the second memory operation; and

selecting the second memory operation from among the group of executable memory operations according to the selection signal.