Allocation systems and method for partitioning lockless list structures

• US 10,223,253 B2
• Filed: 05/15/2017
• Issued: 03/05/2019
• Est. Priority Date: 04/27/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Dixit, Amol Dilip, Waters, Bradley Michael
• Primary Examiner(s): Woolwine, Shane D
• Application Number:
  US15/595,088
• Publication Number:
  US 20170249243A1
• Time in Patent Office: 659 Days
• Field of Search: 711123, 711129, 711173, 711153
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 12/0806 Multiuser, multiprocessor or multiprocessing cache systems
• CPC Class Codes: G06F 13/385 for adaptation of a particular data processing system to different peripheral devices
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

A memory allocation system is provided and includes nodes, one or more memories, and an allocation interface. Each of the nodes includes a respective set of processors. The one or more memories include memory elements for storing threads. The memory elements refer to respective portions of the one or more memories and are accessible to at least one of the nodes. The allocation interface is configured to allocate the memory elements to lockless list structures. Each of the lockless list structures is allocated to a respective set of the memory elements. The lockless list structures are partitioned for the processors. The allocation interface is configured to receive requests from the processors for the memory elements and adjust allocation of the memory elements between the lockless list structures according to a balancing metric.

Claims

1. A memory allocation system comprising:

a plurality of nodes each of which comprising a respective set of a plurality of processors;

one or more memories comprising a plurality of memory elements for storing threads, wherein the plurality of memory elements refer to respective portions of the one or more memories and are accessible to at least one of the plurality of nodes; and

an allocation interface configured to allocate the plurality of memory elements to a plurality of lockless list structures, wherein each of the lockless list structures is allocated to a respective set of the plurality of memory elements, wherein the plurality of lockless list structures are partitioned for the plurality of processors, and

wherein the allocation interface is configured to receive requests from the plurality of processors for the plurality of memory elements and adjust allocation of the plurality of memory elements between the plurality of lockless list structures according to a balancing metric.

2. The memory allocation system of claim 1, wherein the allocation interface is configured to:

in response to receiving one of the requests from one of the plurality of processors, search the plurality of lockless list structures for an available one of the plurality of memory elements that is eligible for allocation to the one of the plurality of processors; and

allocating the available one of the plurality of memory elements to the one of the plurality of processors.

3. The memory allocation system of claim 2, wherein:

the allocation interface is configured to search the plurality of lockless list structures based on a key; and

the key is a processor identifier or a non-uniform memory access number.

4. The memory allocation system of claim 1, wherein:

the plurality of lockless list structures are partitioned by application of an adaptive hash function to each of a plurality of key values; and

each of the plurality of key values corresponds to one of the plurality of nodes or one of the plurality of processors.

5. The memory allocation system of claim 1, wherein:

the plurality of processors comprise logical processors;

the plurality of lockless list structures are partitioned for the logical processors; and

the allocation interface is configured to receive requests from the logical processors for the plurality of memory elements.

6. The memory allocation system of claim 1, wherein:

the plurality of nodes comprise non-uniform memory access nodes;

each of the non-uniform memory access nodes comprises a respective set of the plurality of processors; and

each of the non-uniform memory access nodes is configured to communicate with the other ones of the plurality of nodes.

7. The memory allocation system of claim 1, wherein first one of the plurality of nodes is configured to communicate directly with a second one of the plurality of nodes or indirectly with the second one of the plurality of nodes via a third one of the plurality of nodes.

8. The memory allocation system of claim 1, wherein:

the one or more memories comprise a plurality of memories; and

each of the plurality of nodes comprises a respective one of the plurality of memories.

9. The memory allocation system of claim 1, wherein the allocation interface is implemented as one of the plurality of processors in one of the plurality of nodes.

10. The memory allocation system of claim 1, wherein the plurality of lockless list structures are slists.

11. The memory allocation system of claim 1, wherein each of the memory elements have a corresponding variable buffer size.

12. The memory allocation system of claim 1, wherein balancing metric is configured for maintaining numerical equality of the plurality of memory elements among the lockless list structures.

13. The memory allocation system of claim 1, wherein balancing metric is configured to prevent over-allocation of ones of the plurality of memory elements to one or more of the lockless list structures.

14. A method of operating a memory allocation system, wherein the memory allocation system comprises a plurality of nodes and one or more memories, the method comprising:

allocating a plurality of memory elements of the one or more memories to a plurality of lockless list structures, wherein

the plurality of memory elements store threads and refer to respective portions of the one or more memories and are accessible to at least one of the plurality of nodes,

each of the plurality of nodes comprises a respective set of a plurality of processors,

each of the lockless list structures is allocated to a respective set of the plurality of memory elements, and

the plurality of lockless list structures are partitioned for the plurality of processors;

receiving requests from the plurality of processors for the plurality of memory elements; and

adjusting allocation of the plurality of memory elements between the plurality of lockless list structures according to a balancing metric.

15. The method of claim 14, further comprising:

in response to receiving one of the requests from one of the plurality of processors, searching the plurality of lockless list structures for an available one of the plurality of memory elements that is eligible for allocation to the one of the plurality of processors; and

allocating the available one of the plurality of memory elements to the one of the plurality of processors.

16. The method of claim 15, wherein:

the searching of the plurality of lockless list structures is based on a key; and

the key is a processor identifier or a non-uniform memory access number.

17. The method of claim 14, wherein:

the plurality of lockless list structures are partitioned by application of an adaptive hash function to each of a plurality of key values; and

each of the plurality of key values corresponds to one of the plurality of nodes or one of the plurality of processors.

18. The method of claim 14, further comprising:

calculating a hash index value based on an identifier of one of the plurality of nodes or an identifier of one of the plurality of processors;

identifying one of the plurality of lockless list structures based on the hash index value;

determining if the one of the plurality of lockless list structures does not have an available memory element;

if the one of the plurality of lockless list structures does not have an available memory element, searching through the other ones of the plurality of lockless list structures to locate an available memory element;

transferring allocation of the available memory element from a donor one of the plurality of lockless list structures to a receiving one of the plurality of lockless list structures; and

returning allocation of the available memory element from the receiving one of the plurality of lockless list structures to the donor one of the plurality of lockless list structures after use of the available memory element by one of the plurality of processors.

19. A memory allocation system comprising:

a plurality of processor sockets each of which comprising a respective set of a plurality of processors;

one or more memories comprising a plurality of memory elements for storing threads, wherein the plurality of memory elements refer to respective portions of the one or more memories and are accessible to at least one of the plurality of processor sockets; and

an allocation interface configured to allocate the plurality of memory elements to a plurality of lockless list structures, wherein each of the lockless list structures is allocated a respective set of the plurality of memory elements, wherein the plurality of lockless list structures are partitioned for the plurality of processors, and

wherein the allocation interface is configured to receive requests from the plurality of processors for the plurality of memory elements and adjust allocation of the plurality of memory elements between the plurality of lockless list structures according to a balancing metric.

20. The memory allocation system of claim 19, wherein:

the one or more memories comprise a plurality of memories;

each of the plurality of processor sockets comprise a respective one of the plurality of memories;

a first portion of the plurality of lockless list structures are partitioned by application of an adaptive hash function to each of a first plurality of key values; and

each of the first plurality of key values corresponds to one of the plurality of processor sockets;

a second portion of the plurality of lockless list structures are partitioned by application of the adaptive hash function to each of a second plurality of key values; and

each of the second plurality of key values corresponds to one of the plurality of processors.