Parallel dynamic memory allocation using a lock-free FIFO

Patent metadata

Field	Value
Publication number	US-9542227-B2
Application number	US-201213361816-A
Country	US
Kind code	B2
Filing date	Jan 30, 2012
Priority date	Jan 30, 2012
Publication date	Jan 10, 2017
Grant date	Jan 10, 2017

Abstract

One embodiment of the present invention sets forth a technique for dynamically allocating memory using one or more lock-free 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.

First claim

The invention claimed is:

1. A method of allocating memory, the method comprising:
receiving a plurality of memory allocation requests from a plurality of threads, wherein each memory allocation request specifies an amount of memory;
identifying a first-in first-out sub-system (FIFO) node size based on the amounts of memory associated with the plurality of memory allocation requests;
selecting a first FIFO included in a plurality of FIFOs and populated with FIFO nodes of the FIFO node size;
popping a first FIFO head node from the first FIFO to satisfy the memory allocation request associated with a first thread included in the plurality of threads;
determining that all of the FIFO nodes that populate the first FIFO have been freed; and
in response, retiring the first FIFO.

2. The method of claim 1 , further comprising:
creating the first FIFO including a head pointer value; and
populating the first FIFO with the FIFO nodes configured in a linked list, wherein each FIFO node includes a next value that indicates a next FIFO node in the linked list.

3. The method of claim 1 , further comprising:
receiving a second memory allocation request that is not included in the plurality of memory allocation requests;
determining that the second memory request is rejected by the first FIFO;
selecting a second FIFO included in the plurality of FIFOs; and
popping a FIFO head node from the second FIFO to satisfy the second memory allocation request.

4. The method of claim 3 , further comprising indicating that the first FIFO is unavailable for allocations.

5. The method of claim 4 , wherein the first FIFO is empty.

6. The method of claim 1 , further comprising:
receiving a second memory allocation request that is not included in the plurality of memory allocation requests;
determining that the second memory request is rejected by the first FIFO;
creating a second FIFO;
populating the second FIFO with 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
popping a FIFO head node from the second FIFO to satisfy the second memory allocation request.

7. The method of claim 1 , further comprising:
receiving a second memory allocation request specifying a second amount of memory, wherein the second memory allocation request is not included in the plurality of memory allocation requests;
determining that the FIFO node size is smaller than the second amount of memory;
creating a second FIFO;
populating the second FIFO with second FIFO nodes of a second FIFO node size that is greater than the FIFO node size; and
popping a FIFO head node from the second FIFO to satisfy the second memory allocation request.

8. The method of claim 1 , wherein the FIFO nodes represent portions of sequential memory and the FIFO nodes are configured in a linked list in an order of the portions of sequential memory.

9. The method of claim 1 , further comprising combining a first memory allocation request from a first thread with a second memory allocation request from a second thread to generate the memory allocation request.

10. The method of claim 1 , further comprising releasing a quantity of memory corresponding to the FIFO nodes.

11. A parallel processing unit, comprising:
a memory heap;
a first first-in first-out sub-system (FIFO) that is populated with FIFO nodes that each represent a portion of memory from the memory heap; and
a memory allocation engine that is configured to:
receive a plurality of memory allocation requests from a plurality of threads, wherein each memory allocation request specifies an amount of memory;
identify a first-in first-out sub-system (FIFO) node size based on the amounts of memory associated with the plurality of memory allocation requests;
select the first FIFO included in a plurality of FIFOs and populated with FIFO nodes of the FIFO node size;
pop a first FIFO head node from the first FIFO to satisfy the memory allocation request associated with a first thread included in the plurality of threads;
determine that all of the FIFO nodes that populate the first FIFO have been freed; and
in response, retire the first FIFO.

12. The parallel processing unit of claim 11 , wherein the memory allocation unit is further configured to:
create the first FIFO including a head pointer value; and
populate the first FIFO with the FIFO nodes configured in a linked list, wherein each FIFO node includes a next value that indicates a next FIFO node in the linked list.

13. The parallel processing unit of claim 11 , wherein the memory allocation unit is further configured to:
receive a second memory allocation request that is not included in the plurality of memory allocation requests;
determine that the second memory request is rejected by the first FIFO;
select a second FIFO included in the plurality of FIF 0 s; and
pop a FIFO head node from the second FIFO to satisfy the second memory allocation request.

14. The parallel processing unit of claim 13 , wherein the memory allocation unit is further configured to indicate that the first FIFO is unavailable for allocations.

15. The parallel processing unit of claim 11 , wherein the memory allocation unit is further configured to:
receive a second memory allocation request that is not included in the plurality of memory allocation requests;
determine that the second memory request is rejected by the first FIFO;
create a second FIFO;
populate the second FIFO with 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
pop a FIFO head node from the second FIFO to satisfy the second memory allocation request.

16. The parallel processing unit of claim 11 , wherein the memory allocation unit is further configured to:
receive a second memory allocation request specifying a second amount of memory wherein the second memory allocation request is not included in the plurality of memory allocation requests;
determine that the FIFO node size is smaller than the second amount of memory;
create a second FIFO;
populate the second FIFO with second FIFO nodes of a second FIFO node size that is greater than the FIFO node size; and
pop a FIFO head node from the second FIFO to satisfy the second memory allocation request.

17. The parallel processing unit of claim 11 , wherein the memory allocation unit is further configured to release a quantity of memory corresponding to the FIFO nodes.

18. The parallel processing unit of claim 11 , further comprising, prior to determining that all of the FIFO nodes that populate the first FIFO have been freed, converting the first FIFO to a pop-only FIFO.

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 plurality of memory allocation requests from a plurality of threads, wherein each memory allocation request specifies an amount of memory;
identifying a first-in first-out sub-system (FIFO) node size based on the amounts of memory associated with the plurality of memory allocation requests;
selecting a first FIFO included in a plurality of FIFOs and populated with FIFO nodes of the FIFO node size;
popping a first FIFO head node from the first FIFO to satisfy the memory allocation request associated with a first thread included in

Assignees

• Jones Stephen
• Huang Xiaohuang
• Nvidia Corp

Inventors

• Jones Stephen
• Huang Xiaohuang

Classifications

• G06F2205/064

  Linked list, i.e. structure using pointers, e.g. allowing non-contiguous address segments in one logical buffer or dynamic buffer space allocation · CPC title

• G06F12/023

  Free address space management · CPC title

• G06F2209/5011

  Pool · CPC title

• G06F12/0253

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title

• G06F9/5016 Primary

  the resource being the memory · CPC title