Parallel dynamic memory allocation using a lock-free FIFO
AssigneeNVIDIA Corporation
InventorsStephen Jones, Xiaohuang Huang
Life of this patent
Estimating the term…
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.
Claims28
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.
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.
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 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.
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 memory allocation request specifying an amount of memory;
- identify a FIFO node size based on the amount of memory;
- select the first FIFO that is populated with the FIFO nodes, wherein the FIFO nodes are of the FIFO node size;
- pop a FIFO head node from the first FIFO to satisfy the memory allocation request;
- receive a second memory allocation request;
- 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.
Dependencies are inferred from the claim text.