Off-chip out of order memory allocation for a unified shader

• US 8,407,443 B1
• Filed: 05/01/2009
• Issued: 03/26/2013
• Est. Priority Date: 05/11/2006
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Nordquist, Bryon S.
• Primary Examiner(s): Thai, Tuan V.
• Application Number:
  US12/434,422
• Time in Patent Office: 1,425 Days
• Field of Search: 711/100, 711/154, 711/170
• US Class Current: 711/170
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 2209/5011 Pool
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

Systems and methods for dynamically allocating memory for thread processing may reduce memory requirements while maintaining thread processing parallelism. A memory pool is allocated to store data for processing multiple threads that does not need to be large enough to dedicate a fixed size portion of the memory pool to each thread that may be processed in parallel. Fixed size portions of the memory pool are dynamically allocated and deallocated to each processing thread. Different fixed size portions may be used for different types of threads to allow greater thread parallelism compared with a system that requires allocating a single fixed portion of the memory pool to each thread. The memory pool may be shared between all of the thread types or divided to provide separate memory pools dedicated to each particular thread type.

Claims

1. A method of allocating memory for processing threads in a multithreaded processor to execute a shader program, comprising:

receiving a thread launch request for a first thread;

determining that the first thread requires a memory allocation to execute the shader program in the multithreaded processor;

obtaining an available memory offset specifying an allocation unit within a memory pool allocated for processing the threads, wherein a size of the allocation unit is based on a largest amount of memory needed by any thread to execute the shader program in the multithreaded processor; and

writing the available memory offset in an entry of a thread table to allocate the allocation unit within the memory pool to the first thread.

2. The method of claim 1, wherein the memory pool is dedicated to processing a first type of shader program and the size of the allocation unit is based on the largest amount of memory needed by any thread to execute the first type of shader program.

3. The method of claim 2, wherein a second memory pool is dedicated to processing a second type of shader program and the second memory pool includes a second allocation unit corresponding to the second type of shader program that is sized based on the largest amount of memory needed by any thread to execute the second type of shader program.

4. The method of claim 1, wherein the shader program is one type of shader program including a pixel shader program type, a vertex shader program type, and a geometry shader program type.

5. The method of claim 1, further comprising waiting for an allocation unit to be deallocated when a thread counter equals a maximum number of threads sharing the memory pool.

6. The method of claim 1, further comprising determining that a deallocated allocation unit is not available for allocation to the first thread.

7. The method of claim 1, further comprising:

determining that a deallocated allocation unit is available for allocation to the first thread; and

reading a memory offset of the deallocated allocation unit from a deallocation buffer to use as the available memory offset.

8. The method of claim 1, further comprising:

processing the first thread to execute the shader program;

obtaining the memory offset for the first thread; and

storing the memory offset for the first thread in a deallocation buffer for allocation to another thread.

9. The method of claim 1, wherein the size of the allocation unit is based on the largest amount of memory needed by the shader program for storing stack data.

10. The method of claim 1, further comprising disabling a number of the processing threads by specifying a maximum number of the processing threads that can be execute in parallel to reduce an amount of memory needed for the memory pool.

11. A system for allocating memory for multiple execution threads, comprising:

a thread table configured to store a memory offset for each one of the multiple execution threads;

a multithreaded processing unit configured to process the multiple execution threads using the memory allocated to the multiple execution threads; and

a memory allocation unit configured to allocate allocation units from a memory pool to the multiple execution threads and deallocate the allocation units as each one of the multiple execution threads completes execution of a shader program, wherein the memory allocation unit is further configured to deallocate allocation units in either the same or a different order than the allocation units are allocated.

12. The system of claim 11, wherein the memory allocation unit includes a thread counter configured to update a count of the multiple execution units that have been allocated memory by incrementing a current thread count by the one to produce a new thread count when one of the allocation units is allocated to one of the multiple execution threads.

13. The system of claim 12, wherein the memory allocation unit is further configured to wait for an allocation unit to be deallocated when the thread counter equals a maximum number of threads that share the memory pool.

14. The system of claim 11, wherein the memory allocation unit includes a memory offset counter configured to produce a memory offset for each one of the allocation units in the memory pool by increasing a current memory offset by a size of the allocation units to produce a new memory offset when one of the allocation units is allocated to one of the multiple execution threads.

15. The system of claim 11, further comprising an additional thread table and an additional multithreaded processing unit, wherein the memory allocation unit is configured to allocate a portion of the allocation units from the memory pool for processing a portion of the multiple execution threads by the additional multithreaded processing unit and store memory offsets for the portion of the allocation units.

16. The system of claim 15, wherein a number of the allocation units equals a number of entries in the thread table combined with a number of entries in the additional thread table.

17. The system of claim 11, wherein the memory allocation unit includes a memory offset first in first out (FIFO) memory configured to store memory offsets that have been deallocated and are available for allocation to one of the multiple execution threads.

18. The system of claim 11, wherein the memory pool is shared between the multiple execution threads for execution of a variety of shader program types including a pixel shader program type, a geometry shader program type, and a vertex shader program type.

19. The system of claim 11, wherein a size of the allocation unit within the memory pool is based on a largest amount of memory needed by any of the multiple execution threads to execute one type of shader including a pixel shader program type, a geometry shader program type, and a vertex shader program type.

20. The system of claim 11, wherein a portion of the multiple execution threads are disabled by specifying a maximum number of the multiple execution threads that can be processed in parallel to reduce an amount of memory needed for the memory pool.