Parallel dynamic memory allocation using a lock-free pop-only FIFO

• US 9,417,881 B2
• Filed: 01/30/2012
• Issued: 08/16/2016
• Est. Priority Date: 01/30/2012
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Jones, Stephen, Huang, Xiaohuang
• Primary Examiner(s): PATEL, KAUSHIKKUMAR M
• Application Number:
  US13/361,802
• Publication Number:
  US 20130198479A1
• Time in Patent Office: 1,660 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

One embodiment of the present invention sets forth a technique for dynamically allocating memory using one or more lock-free pop-only FIFOs. One or more lock-free FIFOs are populated with FIFO nodes, where each FIFO node represents a memory allocation of a predetermined size. Each particular lock-free FIFO includes memory allocations of a single size. Different lock-free FIFOs may include memory allocations for different sizes to service allocation requests for different size memory allocations. A lock-free mechanism is used to pop FIFO nodes from the FIFO. The use of the lock-free FIFO allows multiple consumers to simultaneously attempt to pop the head FIFO node without first obtaining a lock to ensure exclusive access of the FIFO.

Claims

1. A method of allocating memory, the method comprising:

receiving a first memory allocation request specifying a first amount of memory;

receiving a second memory allocation request simultaneously with the first memory allocation request, wherein the second memory allocation request specifies the first amount of memory;

identifying a first-in first-out buffer (FIFO) node size included in a plurality of different FIFO node sizes based on the first amount of memory;

selecting a first FIFO and a second FIFO based on the FIFO node size, wherein the first FIFO and the second FIFO are each populated with FIFO nodes of the FIFO node size, and at least one of the first FIFO and the second FIFO comprises a lock-free pop-only FIFO;

determining that a first compare-and-swap (CAS) operation succeeded, wherein the first CAS operation swaps a first FIFO head value associated with the first FIFO with a next value of a FIFO node included in the first FIFO;

in response to determining that the first CAS operation succeeded, popping a first FIFO head node associated with the first FIFO head value from the first FIFO to satisfy the first memory allocation request;

determining that a second CAS operation succeeded, wherein the second CAS operation swaps a second FIFO head value associated with the second FIFO with a next value of a FIFO node included in the second FIFO; and

in response to determining that the second CAS operation succeeded, popping a second FIFO head node associated with the second FIFO head value from the second FIFO, simultaneously with the popping of the first FIFO head node, to satisfy the second memory allocation request.

2. The method of claim 1, further comprising receiving a first allocation free request to free a portion of memory represented by the first FIFO head node.

3. The method of claim 2, further comprising updating tracking information associated with the first FIFO to indicate that the first FIFO head node is freed.

4. The method of claim 3, wherein the tracking information is updated using an atomic operation.

5. The method of claim 2, further comprising:

receiving additional allocation free requests to free additional portions of memory represented by additional FIFO nodes popped from the first FIFO;

determining that all FIFO nodes popped from the first FIFO are freed;

retiring the first FIFO; and

releasing a quantity of memory corresponding to the FIFO nodes populating the first FIFO.

6. The method of claim 1, further comprising receiving a first allocation push request for a portion of memory represented by the second FIFO head node.

7. The method of claim 6, further comprising pushing the second FIFO head node onto the second FIFO as a new FIFO tail node.

8. The method of claim 7, further comprising:

changing a configuration of the second FIFO from a lock-free FIFO to a lock-free pop-only FIFO;

receiving an allocation free request to free a portion of memory represented by a FIFO node popped from the second FIFO; and

updating tracking information associated with the second FIFO to indicate that the FIFO node is freed.

9. The method of claim 1, further comprising:

creating the first FIFO;

populating the first FIFO with the FIFO nodes of the FIFO node size, wherein the FIFO nodes are configured in a linked list and each FIFO node includes a next value that indicates a next FIFO node in the linked list; and

initializing tracking information associated with the first FIFO indicating a quantity of FIFO nodes that populate the first FIFO.

10. The method of claim 1, wherein the first FIFO and the second FIFO are selected from a plurality of FIFOs, each FIFO included in the plurality of FIFOs is populated with FIFO nodes of a single FIFO node size, and the plurality of FIFOs includes FIFO nodes of at least two different FIFO node sizes.

11. The method of claim 1, further comprising changing a configuration of the second FIFO from a lock-free FIFO to a lock-free push-only FIFO.

12. A parallel processing unit, comprising:

a memory heap;

a first first-in first-out buffer (FIFO) that is populated with a first quantity of FIFO nodes that each represent a portion of memory from the memory heap;

a second FIFO that is populated with a second quantity of FIFO nodes that each represent the portion of memory from the memory heap; and

a memory allocation engine that is configured to;

receive a first memory allocation request specifying a first amount of memory;

receive a second memory allocation request simultaneously with the first memory allocation request, wherein the second memory allocation request specifies the first amount of memory;

identify a first-in first-out buffer (FIFO) node size included in a plurality of different FIFO node sizes based on the first amount of memory;

select the first FIFO and the second FIFO based on the FIFO node size, wherein the first FIFO and the second FIFO are each populated with FIFO nodes of the FIFO node size, and at least one of the first FIFO and the second FIFO comprises a lock-free pop-only FIFO;

determine that a first compare-and-swap (CAS) operation succeeded, wherein the first CAS operation swaps a first FIFO head value associated with the first FIFO with a next value of a FIFO node included in the first FIFO;

in response to determining that the first CAS operation succeeded, pop a first FIFO head node associated with the first FIFO head value from the first FIFO to satisfy the first memory allocation request;

determine that a second CAS operation succeeded, wherein the second CAS operation swaps a second FIFO head value associated with the second FIFO with a next value of a FIFO node included in the second FIFO; and

in response to determining that the second CAS operation succeeded, pop a second FIFO head node associated with the second FIFO head value from the second FIFO, simultaneously with the popping of the first FIFO head node, to satisfy the second memory allocation request.

13. The parallel processing unit of claim 12, wherein the memory allocation unit is further configured to receive a first allocation free request to free a portion of memory represented by the first FIFO head node.

14. The parallel processing unit of claim 13, wherein the memory allocation unit is further configured to update tracking information associated with the first FIFO to indicate that the first FIFO head node is freed.

15. The parallel processing unit of claim 13, wherein the memory allocation unit is further configured to:

receive additional allocation free requests to free additional portions of memory represented by additional FIFO nodes popped from the first FIFO;

determine that all FIFO nodes popped from the first FIFO are freed;

retire the first FIFO; and

release a quantity of memory corresponding to the FIFO nodes populating the first FIFO.

16. The parallel processing unit of claim 12, wherein the memory allocation unit is further configured to receive a first allocation push request for a portion of memory represented by the second FIFO head node.

17. The parallel processing unit of claim 16, wherein the memory allocation unit is further configured to push the second FIFO head node onto the second FIFO as a new FIFO tail node.

18. The parallel processing unit of claim 17, wherein the memory allocation unit is further configured to:

change a configuration of the second FIFO from a lock-free FIFO to a lock-free pop-only FIFO;

receive an allocation free request to free a portion of memory represented by a FIFO node popped from the second FIFO; and

update tracking information associated with the second FIFO to indicate that the FIFO node is freed.

19. A non-transitory computer-readable storage medium storing instructions that, when executed by a processor, cause the processor to allocate memory, by performing the steps of:

receiving a first memory allocation request specifying a first amount of memory;

receiving a second memory allocation request simultaneously with the first memory allocation request, wherein the second memory allocation request specifies the first amount of memory;

identifying a first-in first-out buffer (FIFO) node size included in a plurality of different FIFO node sizes based on the first amount of memory;

selecting a first FIFO and a second FIFO based on the FIFO node size, wherein the first FIFO and the second FIFO are each populated with FIFO nodes of the FIFO node size, and at least one of the first FIFO and the second FIFO comprises a lock-free pop-only FIFO;

determining that a first compare-and-swap (CAS) operation succeeded, wherein the first CAS operation swaps a first FIFO head value associated with the first FIFO with a next value of a FIFO node included in the first FIFO;

in response to determining that the first CAS operation succeeded, popping a first FIFO head node associated with the first FIFO head value from the first FIFO to satisfy the first memory allocation request;

determining that a second CAS operation succeeded, wherein the second CAS operation swaps a second FIFO head value associated with the second FIFO with a next value of a FIFO node included in the second FIFO; and

in response to determining that the second CAS operation succeeded, popping a second FIFO head node associated with the second FIFO head value from the second FIFO, simultaneously with the popping of the first FIFO head node, to satisfy the second memory allocation request.

20. The non-transitory computer-readable storage medium of claim 19, further comprising receiving a first allocation free request to free a portion of memory represented by the first FIFO head node.

21. The non-transitory computer-readable storage medium of claim 20, further comprising updating tracking information associated with the first FIFO to indicate that the first FIFO head node is freed.

22. The non-transitory computer-readable storage medium of claim 21, wherein the tracking information is updated using an atomic operation.

23. The non-transitory computer-readable storage medium of claim 20, further comprising:

receiving additional allocation free requests to free additional portions of memory represented by additional FIFO nodes popped from the first FIFO;

determining that all FIFO nodes popped from the first FIFO are freed;

retiring the first FIFO; and

releasing a quantity of memory corresponding to the FIFO nodes populating the first FIFO.

24. The non-transitory computer-readable storage medium of claim 19, wherein the first FIFO is configured as a lock-free pop-only FIFO and the second FIFO is configured as a lock-free FIFO.

25. The non-transitory computer-readable storage medium of claim 19, further comprising receiving a first allocation push request for a portion of memory represented by the second FIFO head node.

26. The non-transitory computer-readable storage medium of claim 25, further comprising pushing the second FIFO head node onto the second FIFO as a new FIFO tail node.

27. The non-transitory computer-readable storage medium of claim 26, further comprising:

changing a configuration of the second FIFO from a lock-free FIFO to a lock-free pop-only FIFO;

receiving an allocation free request to free a portion of memory represented by a FIFO node popped from the second FIFO; and

updating tracking information associated with the second FIFO to indicate that the FIFO node is freed.

28. A method of allocating memory, the method comprising:

receiving a first memory allocation request specifying a first amount of memory;

receiving a second memory allocation request simultaneously with the first memory allocation request, wherein the second memory allocation request specifies the first amount of memory;

identifying a first-in first-out buffer (FIFO) node size based on the first amount of memory;

selecting a first FIFO and a second FIFO that are each populated with FIFO nodes of the FIFO node size, wherein the first FIFO is configured as a lock-free pop-only FIFO, and wherein the second FIFO is configured as a lock-free FIFO;

popping a first FIFO head node from the first FIFO to satisfy the first memory allocation request; and

popping a second FIFO head node from the second FIFO, simultaneously with the popping of the first FIFO head node, to satisfy the second memory allocation request.