EFFICIENT IMPLEMENTATION OF QUEUES AND OTHER DATA STRUCTURES USING PROCESSING NEAR MEMORY

• US 20170255397A1
• Filed: 03/07/2016
• Published: 09/07/2017
• Est. Priority Date: 03/07/2016
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Jayasena, Nuwan S., Zhang, Dong Ping, Diez, Paula Aguilera
• Granted Patent: US 9,977,609 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/084 with a shared cache
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 2212/1024 Latency reduction

Abstract

Systems, apparatuses, and methods for implementing efficient queues and other data structures. A queue may be shared among multiple processors and/or threads without using explicit software atomic instructions to coordinate access to the queue. System software may allocate an atomic queue and corresponding queue metadata in system memory and return, to the requesting thread, a handle referencing the queue metadata. Any number of threads may utilize the handle for accessing the atomic queue. The logic for ensuring the atomicity of accesses to the atomic queue may reside in a management unit in the memory controller coupled to the memory where the atomic queue is allocated.

Claims

1. A system comprising:

one or more memory devices;

one or more processors; and

one or more memory controllers comprising;

a first interface configured to be coupled to the one or more processors;

a second interface configured to be coupled to the one or more memory devices; and

control logic;

wherein responsive to receiving a first operation from a first processor via the first interface, the control logic is configured to;

perform a first access to metadata via the second interface, wherein the metadata corresponds to a data structure referenced by the first operation; and

perform a second access to the data structure via the second interface, wherein the second access is specified by the first operation.

2. The system as recited in claim 1, wherein the first operation is configured to write data to the data structure or read data from the data structure.

3. The system as recited in claim 1, wherein the metadata comprises at least one of:

a head pointer, tail pointer, a count of a number of items in the data structure, a payload start pointer, and a payload end pointer.

4. The system as recited in claim 1, the one or more processors are configured to:

allocate first memory locations for the data structure in system memory responsive to detecting a request to allocate the data structure;

allocate second memory locations for metadata in the system memory;

initialize the metadata; and

return, to a requesting thread, a handle to the second memory locations.

5. The system as recited in claim 4, wherein the one or more processors are configured to allocate the first memory locations and second memory locations in a non-cacheable region of system memory address space.

6. The system as recited in claim 1, wherein each of the one or more memory controllers are included within the one or more memory devices.

7. The system as recited in claim 4, wherein the data structure is a queue, and wherein the first operation identifies a first handle to the metadata of the data structure.

8. A memory controller comprising:

a first interface configured to be coupled to one or more processors;

a second interface configured to be coupled to one or more memory devices; and

control logic;

wherein responsive to receiving a first operation from a first processor via the first interface, the control logic is configured to;

perform a first access to metadata via the second interface, wherein the metadata corresponds to a data structure referenced by the first operation; and

perform a second access to the data structure via the second interface, wherein the second access is specified by the first operation.

9. The memory controller as recited in claim 8, wherein the first operation is configured to write data to the data structure or read data from the data structure.

10. The memory controller as recited in claim 8, wherein the metadata comprises at least one of a head pointer, tail pointer, a count of a number of items in the data structure, a payload start pointer, and a payload end pointer.

11. The memory controller as recited in claim 8, wherein the control logic is configured to determine a location of the data structure from the metadata.

12. The memory controller as recited in claim 8, wherein prior to completing the first and second access, the memory controller is configured to:

receive a second operation from a second processor;

determine that the second operation references the data structure; and

prevent accesses, corresponding to the second operation, from being performed to the data structure until after the first and second access have been completed.

13. The memory controller as recited in claim 8, wherein the memory controller comprises a plurality of memory channels, wherein the data structure and the metadata are allocated to span only a single memory channel, and wherein the data structure and the metadata are allocated in a non-cacheable region of system memory address space.

14. The memory controller as recited in claim 8, wherein the data structure is a queue, and wherein the first operation identifies a first handle to metadata of the data structure.

15. A method comprising:

performing a first access to metadata via a second interface responsive to receiving a first operation from a first processor via a first interface, wherein the metadata corresponds to a data structure referenced by the first operation; and

performing a second access to the data structure via the second interface, wherein the second access is specified by the first operation.

16. The method as recited in claim 15, wherein the first operation is configured to write data to the data structure or read data from the data structure.

17. The method as recited in claim 15, wherein the metadata comprises at least one of a head pointer, tail pointer, a count of a number of items in the data structure, a payload start pointer, and a payload end pointer.

18. The method as recited in claim 15, wherein the method further comprising:

allocating first memory locations for the data structure in system memory responsive to detecting a request to allocate the data structure;

allocating second memory locations for the metadata in system memory;

initializing the metadata; and

returning, to a requesting thread, a handle to the second memory locations.

19. The method as recited in claim 18, further comprising allocating the first memory locations and second memory locations in a non-cacheable region of system memory address space.

20. The method as recited in claim 18, further comprising allocating the first memory locations and second memory locations to span only a single memory channel.