# US 2017/0255397 A1 · Efficient implementation of queues and other data structures using processing near memory > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2017/0255397 A1 - Document ID: US20170255397A1 - Status: Published application - Kind: A1 - Application number: 15/063,186 - Filed: 2016-03-07 - Published: 2017-09-07 - Earliest claimed: 2016-03-07 - Assignees: Advanced Micro Devices, Inc. - Applicants: Advanced Micro Devices, Inc. - Inventors: Nuwan S. Jayasena; Dong Ping Zhang; Paula Aguilera Diez - Web page: https://patentgrep.com/patent/US20170255397A1 ## CPC - G06F 12/10: Address translation - G06F 12/084: with a shared cache - G06F 12/0888: using selective caching, e.g. bypass - G06F 2212/1024: Latency reduction - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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 ### Claim 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. ### Claim 2 (depends on 1) 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. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) 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. ### Claim 5 (depends on 4) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 4) 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. ### Claim 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. ### Claim 9 (depends on 8) 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. ### Claim 10 (depends on 8) 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. ### Claim 11 (depends on 8) 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. ### Claim 12 (depends on 8) 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. ### Claim 13 (depends on 8) 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. ### Claim 14 (depends on 8) 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. ### Claim 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. ### Claim 16 (depends on 15) 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. ### Claim 17 (depends on 15) 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. ### Claim 18 (depends on 15) 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. ### Claim 19 (depends on 18) 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. ### Claim 20 (depends on 18) 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.