FIFO queue, memory resource, and task management for graphics processing

• US 10,713,746 B2
• Filed: 06/06/2018
• Issued: 07/14/2020
• Est. Priority Date: 01/29/2018
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Gould, Jason M., Nevraev, Ivan
• Primary Examiner(s): Gray, Ryan M
• Application Number:
  US16/001,608
• Publication Number:
  US 20190236749A1
• Time in Patent Office: 769 Days
• Field of Search: None
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5016 the resource being the memory
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining

Abstract

Methods and devices for managing first-in first-out (FIFO) queues in graphics processing are described. A write operation can be executed by multiple write threads on a graphics processing unit (GPU) to write data to memory locations in the multiple pages of memory. The write operation can also include allocating additional pages of memory for the FIFO queue where a write allocation pointer is determined to achieve a threshold, such to grow the FIFO queue before the memory is actually needed for writing. Similarly, comprises a read operation can be executed by multiple read threads to read data from the memory locations. The read operation can also include deallocating pages of memory back to a memory pool where a read done pointer is determined to achieve a threshold, such as an end of a page.

Claims

1. A method for managing first-in first-out (FIFO) queues in graphics processing, comprising:

executing, via parallel execution of multiple write threads of a graphics processing unit (GPU), a write operation to write data to one or more write memory locations in multiple pages of memory from a memory pool allocated to a FIFO queue of the multiple FIFO queues, wherein, for a given write thread of the multiple write threads, the write operation comprises;

based on writing the data to the one or more write memory locations by using a write allocation pointer that is common to the FIFO queue, advancing a write done pointer to a next write memory location following the one or more write memory locations to which the data is written;

monitoring write done pointers associated with each of the multiple FIFO queues, including the write done pointer associated with the FIFO queue; and

in response to determining, based on monitoring the write done pointers and based on read allocation pointers, that written data is present in the FIFO queue but has not been consumed by, or scheduled for consumption by, one or more read threads;

comparing the write done pointers and the read allocation pointers to determine an amount of written data available for consumption from each of the multiple FIFO queues, based at least on;

selecting, based on one or more of criteria related to the multiple FIFO queues, the FIFO queue or a set of FIFO queues including the FIFO queue from which to consume the written data;

determining one or more base addresses of the written data to be processed based at least on one or more of the read allocation pointers associated with the FIFO queue or the set of FIFO queues;

executing, via parallel execution of multiple read threads of the GPU, a read operation to read the written data from one or more read memory locations in the multiple pages of memory associated with the FIFO queue or the set of FIFO queues, wherein the one or more read memory locations are determined based at least in part on the one or more base addresses; and

updating the one or more of the read allocation pointers, based on a range specified to one or more of the multiple read threads.

2. The method of claim 1, wherein the write operation further comprises:

advancing the write allocation pointer to a next available write memory location following the one or more write memory locations to which the data is to be written;

detecting whether the write allocation pointer achieves a threshold write memory location; and

where the write allocation pointer achieves the threshold write memory location, allocating at least one additional page of memory from the memory pool to the FIFO queue.

3. The method of claim 1, wherein advancing the write done pointer is performed by the given write thread or a thread dispatcher.

4. The method of claim 1, wherein the read operation further comprises advancing, based on reading the written data from the one or more read memory locations, a read done pointer to a next read memory location following the one or more read memory locations from which the written data is read.

5. The method of claim 4, wherein advancing the read done pointer is performed by the given read thread or a thread dispatcher.

6. The method of claim 4, wherein the read operation further comprises:

detecting whether the read done pointer achieves a threshold read memory location; and

where the read done pointer achieves the threshold read memory location, marking at least one page of the multiple pages of memory for deallocation to the memory pool.

7. The method of claim 6, wherein the threshold read memory location corresponds to a last memory location on the at least one page of memory or a certain memory location in a next page of memory, wherein the next page of memory is after the at least one page of the multiple pages of memory.

8. The method of claim 1, wherein the read operation further comprises:

incrementing, based on reading the written data, a read done counter of a number of items read from the one or more read memory locations on at least one page of the multiple pages of memory; and

where the read done counter achieves a threshold count indicating that the at least one page has been both entirely filled with the written data and then entirely consumed, at least one of;

marking the page for deallocation to the memory pool;

or

parsing read done counters associated with the multiple pages allocated to the FIFO queue in an order from oldest to newest, and marking all pages for deallocation to the memory pool until a page of memory in the multiple pages is reached whose written data has not been fully consumed.

9. The method of claim 1, wherein the read operation comprises an ordered read operation to read the written data from the one or more read memory locations in the multiple pages of memory, wherein the ordered read operation comprises:

obtaining a read allocation pointer of the one or more read allocations pointers that is common to the FIFO queue;

determining a read thread identifier;

determining a read memory location of the one or more read memory locations based at least in part on the read allocation pointer and the read thread identifier; and

reading memory at the read memory location.

10. The method of claim 9, wherein a dispatcher thread invokes execution of multiple ordered read threads that perform the ordered read operation and provides each of the multiple ordered read threads with the read allocation pointer and respective read thread identifiers, and wherein the dispatcher thread advances the read allocation pointer to a next read memory location following a last read memory location to be read by the multiple ordered read threads.

11. The method of claim 9, wherein a dispatcher thread executes multiple ordered read threads that perform the ordered read operation and further executes, via parallel execution of multiple ordered write threads of the GPU, an ordered write operation to write the data to ordered memory locations in the multiple pages of memory, wherein, for a given ordered write thread of the multiple ordered write threads, the ordered write operation comprises:

obtaining the write allocation pointer that is common to the FIFO queue;

determining a write thread identifier;

determining a write memory location based at least in part on the write allocation pointer and the write thread identifier; and

writing the data to the write memory location.

12. The method of claim 11, wherein the dispatcher thread executes the multiple ordered write threads and provides each of the multiple ordered write threads with the write allocation pointer and respective write thread identifiers, and wherein the dispatcher thread advances the write allocation pointer to a next memory location following a last write memory location written to by the multiple ordered write threads.

13. The method of claim 1, wherein initializing the memory pool of memory resources for the multiple FIFO queues comprises initializing a virtual address space that is larger than a physical address space allocated for the memory pool, and wherein a dispatcher thread manages allocation of the physical address space based on an amount of memory initialized in the virtual address space.

14. The method of claim 1, wherein the write operation further comprises incrementing, based on writing the data, a write page tracker of a number of items written to the memory locations on the at least one page of the multiple pages of memory;

based on comparing the write page tracker with the write allocation pointer, initiating an ordered scan of the write trackers associated with a subset of the multiple pages of memory that are not marked as done, and

based on the ordered scan, updating a write done pointer to indicate data in preceding memory locations has been written.

15. The method of claim 14, wherein initiating the ordered scan is based on determining when the write page tracker and write allocation pointer indicate that all memory locations allocated for writing on the at least one page have been written.

16. The method of claim 1, wherein the one or more of criteria related to the multiple FIFO queues include priorities associated with each of the multiple FIFO queues, the amount of written data available, thresholds associated with each of the multiple FIFO queues, FIFO queue identifiers, or a balanced selection method of the FIFO queues.

17. The method of claim 2, wherein the threshold write memory location corresponds to a certain memory location in a page of memory, wherein the page of memory is not a last page of memory in the multiple pages of memory allocated to the FIFO queue.

18. The method of claim 2, wherein the threshold write memory location is set based at least in part on a priority associated with the FIFO queue.

19. The method of claim 1, further comprising initializing a memory pool of the memory resources for the multiple FIFO queues;

allocating the multiple pages of memory from the memory pool to the FIFO queue of the multiple FIFO queues.

20. A device for managing first-in first-out (FIFO) queues in graphics processing, comprising

a memory storing one or more parameters or instructions for managing FIFO queues in graphics processing;

and

at least one processor coupled to the memory, wherein the at least one processor is configured to;

initialize a memory pool of memory resources in the memory for multiple FIFO queues;

allocate multiple pages of the memory pool to a FIFO queue of the multiple FIFO queues; and

execute, via parallel execution of multiple write threads of a graphics processing unit (GPU), a write operation to write data to memory locations in the multiple pages of memory, wherein, for a given write thread of the multiple write threads, the write operation comprises;

advancing a write allocation pointer to a next available memory location following one or more memory locations to which the data is to be written, wherein the write allocation pointer is common to the FIFO queue;

detecting whether the write allocation pointer achieves a threshold write memory location; and

where the write allocation pointer achieves the threshold write memory location, allocating at least one additional page of memory from the memory pool to the FIFO queue.

21. The device of claim 20, wherein the threshold write memory location corresponds to a certain memory location in a page of memory, wherein the page of memory is not a last page of memory in the multiple pages of memory allocated to the FIFO queue.

22. A method for managing first-in first-out (FIFO) queues in graphics processing, comprising:

monitoring, via one or more processors of a graphics processing unit (GPU) or a central processing unit (CPU), write done pointers associated with each of one or more FIFO queues, and in response to determining, based on the write done pointers and read allocation pointers associated with the one or more FIFO queues, that data is present in a FIFO queue but has not been consumed by, or scheduled for consumption by, one or more read threads;

determining an amount of the data that is available for consumption from each of the one or more FIFO queues, based at least on comparing the write done pointers and read allocation pointers, and/or on specified batch sizes;

selecting, based on one or more of;

specified priorities of each of the one or more FIFO queues, counts of data available for consumption in each of the one or more FIFO queues, specified thresholds associated with each of the one or more FIFO queues, FIFO queue identifiers, and/or a balanced selection method, the FIFO queue or a set of FIFO queues from which to consume data;

determining one or more base addresses of data to be processed based at least on a read allocation pointer associated with the FIFO queue or the read allocation pointers associated with the set of FIFO queues;

invoking execution of one or more threads of a data consumption shader program to be executed in parallel on the GPU, wherein the data consumption shader program is configured to retrieve the data from the FIFO queue or the set of FIFO queues; and

updating the read allocation pointer or the read allocation pointers, based on the range specified to the one or more shader threads.

23. The method of claim 22, wherein the data consumption shader program is additionally configured to perform calculations or memory requests based on data retrieved from the FIFO queue.

24. The method of claim 22, wherein the data consumption shader program is additionally configured to:

perform write operations to append the data to one or more other FIFO queues;

update a second write done pointer of the one or more other FIFO queues to indicate that data has been appended to the one or more other FIFO queues; and

notify a dispatcher thread that the data has been written to the one or more other FIFO queues.

25. The method of claim 22, wherein invoking execution of the one or more threads of the data consumption shader program comprises providing, to each of the one or more threads, at least one of an identifier for the FIFO queue, a starting or base address of the data, an index from which the base address can be derived, an identifier unique to each thread or group of threads, and/or a number of elements of data to be consumed.

26. The method of claim 22, wherein the data consumption shader program is additionally configured to at least one of update a read done counter indicating portions of the FIFO queue that have been read, or free the portions of the FIFO queue that have been read for reuse or to the memory pool.