# US 2021/0279837 A1 · Cooperative parallel memory allocation > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2021/0279837 A1 - Document ID: US20210279837A1 - Status: Published application - Kind: A1 - Application number: 16/813,116 - Filed: 2020-03-09 - Published: 2021-09-09 - Earliest claimed: 2020-03-09 - Assignees: NVIDIA Corporation - Applicants: NVIDIA Corporation - Inventors: Harold Carter Edwards - Web page: https://patentgrep.com/patent/US20210279837A1 ## CPC - G06F 12/084: with a shared cache - G06T 1/60: Memory management - G06F 8/45: {Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions} - G06F 9/3004: {to perform operations on memory} - G06F 9/3822: {Parallel decoding, e.g. parallel decode units} - G06F 9/5016: {the resource being the memory} - G06F 12/0806: Multiuser, multiprocessor or multiprocessing cache systems - G06F 12/0811: with multilevel cache hierarchies - G06F 12/0897: with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811) - G06T 1/20: Processor architectures; Processor configuration, e.g. pipelining - G06F 2212/1024: Latency reduction - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract Apparatuses, systems, and techniques to perform multi-threaded memory allocation in parallel by one or more software programs being performed on a parallel processing unit (PPU), such as a graphics processing unit (GPU), or any other processing unit capable of supporting multi-threaded software execution. In at least one embodiment, one or more software programs expressed in part by code using an application programming interface for parallel computing, such as CUDA, perform allocation, search, and deallocation of memory efficiently and in parallel on a GPU. ## Claims ### Claim 1 A processor comprising: one or more circuits to exclusively allocate one or more memory portions to one or more instruction threads based, at least in part, on a size of the one or more memory portions while another thread is able to allocate one or more other memory portions. ### Claim 2 (depends on 1) The processor of claim 1, wherein: the one or more memory portions are contained in a memory block of a tree of related memory blocks; a first group of the one or more instruction threads concurrently examines the tree of related memory blocks and determines a first thread of the first group and a first memory block for an allocation; the first thread locates a first one or more memory portions for the allocation in the first memory block; the first thread updates a state for the first memory block to indicate the first one or memory portions are allocated; the first thread unlocks the first memory block; and a second thread is able to allocate or deallocate the one or more other memory portions in a second block of the tree of related memory blocks while the first thread locates the first one or more memory portions. ### Claim 3 (depends on 2) The processor of claim 2, wherein the memory block of the tree of related memory blocks to contain the one or more memory portions is determined based, at least in part, on the size. ### Claim 4 (depends on 2) The processor of claim 2, wherein the first group determines the first thread and the first memory block by voting by each thread of the first group. ### Claim 5 (depends on 2) The processor of claim 2, wherein the state comprises one or more values indicating information about the one or more memory portions contained in the memory block. ### Claim 6 (depends on 2) The processor of claim 2, wherein the first thread locates the first one or more memory portions to be allocated in a third memory block of the tree of related memory blocks if the first memory block does not contain the first one or more memory portions to be allocated, the third memory block being in a different branch of the tree of related memory blocks. ### Claim 7 (depends on 2) The processor of claim 2, wherein the first thread locks the first block by modifying the state for the first block. ### Claim 8 (depends on 2) The processor of claim 2, wherein the state comprises one or more values indicating additional memory blocks to be concurrently examined in the tree of related memory blocks. ### Claim 9 (depends on 2) The processor of claim 2, wherein a first memory portion and a second memory portion of the first block indicate a third block containing a third one or more memory portions. ### Claim 10 (depends on 2) The processor of claim 2, wherein if the second thread is unable to deallocate the one or more other memory portions as a result of the first memory block being locked, the first thread performs deallocation of the one or more other memory portions. ### Claim 11 (depends on 1) The processor of claim 1, wherein the one or more memory portions are exclusively allocated by performing a function call to an application programming interface for parallel computing by the one or more instruction threads. ### Claim 12 A system, comprising: one or more processors to exclusively allocate one or more memory portions to one or more instruction threads based, at least in part, on a size of the one or more memory portions while another thread is able to allocate one or more other memory portions. ### Claim 13 (depends on 12) The system of claim 12, wherein: the one or more memory portions are contained in a first block of a set of memory blocks; the first block is locked by a first thread of a first group of the one or more instruction threads; the one or more memory portions in the first block are claimed by the first thread; and a second thread of a second group of the one or more instruction threads is able to claim or unclaim the one or more other memory portions in a second block of the set of memory blocks while the first block is locked by the first thread. ### Claim 14 (depends on 13) The system of claim 13, wherein the first thread unlocks the first block after the one or more memory portions in the first block are claimed. ### Claim 15 (depends on 13) The system of claim 13, wherein the second block is not locked by the first thread. ### Claim 16 (depends on 13) The system of claim 13, wherein the first block and second block of the set of memory blocks are determined based, at least in part, on the size. ### Claim 17 (depends on 13) The system of claim 13, wherein each block of the set of memory blocks is associated with a state value indicating information about the block. ### Claim 18 (depends on 17) The system of claim 17, wherein the first block is locked by incrementing a reference count in the state associated with the first block. ### Claim 19 (depends on 17) The system of claim 17, wherein the one or more memory portions in the first block are claimed by updating the state associated with the first block. ### Claim 20 (depends on 12) The system of claim 12, wherein the one or more memory portions are exclusively allocated by performing a function call to an application programming interface for parallel computing by the one or more instruction threads. ### Claim 21 A machine-readable medium having stored thereon an application programming interface (API), which if performed by one or more processors, cause the one or more processors to at least: exclusively allocate, by the API, one or more memory portions to one or more instruction threads based, at least in part, on a size of the one or more memory portions while another thread is able to allocate one or more other memory portions. ### Claim 22 (depends on 21) The machine-readable medium of claim 21, wherein: the one or more memory portions and the one or more other memory portions are contained in a memory block of a set of memory blocks; a first thread of a first group of the one or more instruction threads determines a first memory block of the set of memory blocks; the first thread locks the first memory block; the first thread locates a first one or more memory portions to be allocated in the first memory block; the first thread allocates the first one or more memory portions in the first memory block; the first thread unlocks the first memory block; and a second thread of a second group of the one or more instruction threads is able to locate a second one or more memory portions in the one or more other memory portions in a second block of the set of memory blocks while the first thread locates the first one or more memory portions. ### Claim 23 (depends on 22) The machine-readable medium of claim 22, wherein the first thread locks the first memory block by modifying a first state value associated with the first memory block. ### Claim 24 (depends on 22) The machine-readable medium of claim 22, wherein the first memory block is determined based, at least in part, on the size. ### Claim 25 (depends on 22) The machine-readable medium of claim 22, wherein the first memory block indicates a third memory block of the set of memory blocks. ### Claim 26 (depends on 25) The machine-readable medium of claim 25, wherein the first thread locates the first one or more memory portions to be allocated in the third memory block if the first memory block does not contain the first one or more memory portions to be allocated. ### Claim 27 (depends on 22) The machine-readable medium of claim 22, wherein the first thread allocates the first one or more memory portions in the first memory block by modifying a first state value associated with the first memory block. ### Claim 28 (depends on 27) The machine-readable medium of claim 27, wherein the first state value is modified by setting bitwise values indicating a status for each of the one or more memory portions. ### Claim 29 (depends on 21) The machine-readable medium of claim 21, wherein the one or more memory portions are exclusively allocated by performing a function call to an application programming interface for parallel computing by the first group and the second group of the one or more instruction threads. ### Claim 30 A method, comprising: exclusively allocating one or more memory portions to one or more instruction threads based, at least in part, on a size of the one or more memory portions while another thread is able to allocate one or more other memory portions. ### Claim 31 (depends on 30) The method of claim 30, wherein: the one or more memory portions and the one or more other memory portions are contained in one or more memory blocks; a first group of the one or more instruction threads concurrently examines the one or more memory blocks and determines a first thread of the first group and a first memory block for an allocation; the first thread locks the first memory block; the first thread determines if a first one or more memory portions of the one or more memory portions are contained in the first memory block; if the first one or more memory portions are available in the first memory block, the first thread allocates the first one or more memory portions in the first memory block; the first thread unlocks the first memory block; and a second group of the one or more instruction threads is able to allocate and deallocate a second one or more memory portions of the one or more other memory portions in a second memory block of the one or more memory blocks while the first thread allocates the first one or more memory portions. ### Claim 32 (depends on 31) The method of claim 31, wherein the first group determines the first thread and the first memory block by voting by each thread of the first group. ### Claim 33 (depends on 31) The method of claim 31, wherein the first thread locks the first memory block by modifying a first state value associated with the first memory block. ### Claim 34 (depends on 31) The method of claim 31, wherein the first memory block is determined based, at least in part, on the size. ### Claim 35 (depends on 31) The method of claim 31, wherein the first thread determines a third memory block of the one or more memory blocks if the first one or more memory portions are not available in the first memory block. ### Claim 36 (depends on 35) The method of claim 35, wherein the first thread allocates the first one or more memory portions in the third memory block. ### Claim 37 (depends on 31) The method of claim 31, wherein the first thread allocates the first one or more memory portions in the first memory block by modifying a first state associated with the first memory block. ### Claim 38 (depends on 37) The method of claim 37, wherein the first state is modified by setting individual bit values indicating a status for each of the one or more memory portions. ### Claim 39 (depends on 31) The method of claim 31, wherein the first state comprises one or more values indicating additional memory blocks to be concurrently examined in the tree of related memory blocks. ### Claim 40 (depends on 31) The method of claim 31, wherein if the second thread is unable to deallocate the one or more other memory portions as a result of the first memory block being locked, the first thread performs deallocation of the one or more other memory portions. ### Claim 41 (depends on 30) The method of claim 30, wherein the one or more memory portions are exclusively allocated by performing a function call to an application programming interface for parallel computing by the first group and the second group of the one or more instruction threads.