Cache utilization and eviction based on allocated priority tokens

Patent metadata

Field	Value
Publication number	US-9477526-B2
Application number	US-201414147395-A
Country	US
Kind code	B2
Filing date	Jan 3, 2014
Priority date	Sep 4, 2013
Publication date	Oct 25, 2016
Grant date	Oct 25, 2016

Abstract

A system, method, and computer program product are provided for providing prioritized access for multithreaded processing. The method includes the steps of allocating threads to process a workload and assigning a set of priority tokens to at least a portion of the threads. Access to a resource, by each one of the threads, is based on the priority token assigned to the thread and the threads are executed by a multithreaded processor to process the workload.

First claim

What is claimed is:

1. A method comprising:
allocating threads to process a workload;
assigning a set of reallocatable priority tokens with different priorities to at least a portion of the threads, wherein access to a resource, by each one of the threads, is based on the priority token assigned to the thread; and
executing, by a multithreaded processor, the threads to process the workload, the executing comprising:
determining that no cache entries are available to store data to complete a memory operation associated with a thread;
determining that a priority token assigned to the thread is lower priority compared with priority tokens associated with the cache entries; and
transmitting the memory operation to a memory system to complete the memory operation for the thread.

2. The method of claim 1 , wherein the resource is at least one of a storage resource or a communication resource.

3. The method of claim 1 , wherein the resource is a cache memory.

4. The method of claim 3 , wherein an eviction policy for the cache memory is applied based on the priority token.

5. The method of claim 3 , wherein an allocation policy for the cache memory is applied based on the priority token.

6. The method of claim 1 , further comprising determining a maximum number of priority tokens in the set.

7. The method of claim 6 , further comprising increasing or decreasing the maximum number of priority tokens in the set.

8. The method of claim 1 , further comprising acquiring, by a first thread, a priority token when a first instruction is reached during execution of a sequence of instructions.

9. The method of claim 1 , further comprising releasing, by a first thread, a priority token when a particular instruction is reached during execution of a sequence of instructions.

10. The method of claim 1 , further comprising releasing, by a first thread, a priority token when the first thread completes execution of a sequence of instructions for the workload and exits.

11. The method of claim 1 , further comprising storing the priority token assigned to a second thread when a first cache entry is allocated for storing data associated with the second thread.

12. The method of claim 1 , further comprising assigning a second set of second priority tokens to at least a second portion of the threads, wherein access to a second resource, by each one of the threads, is based on the second priority token assigned to the thread.

13. The method of claim 12 , wherein the resource is a first cache memory and the second resource is a second cache memory.

14. The method of claim 1 , further comprising giving scheduling priority for execution to the portion of the threads to which the priority tokens are assigned.

15. A method comprising:
allocating threads to process a workload;
assigning a set of priority tokens with different priorities to at least a portion of the threads, wherein access to a resource, by each one of the threads, is based on the priority token assigned to the thread; and
executing, by a multithreaded processor, the threads to process the workload, the executing comprising:
determining that no cache entries are available to store data to complete a memory operation associated with a thread;
determining that a first cache entry is allocated to store data associated with a second thread that has not been assigned a priority token;
evicting data from the first cache entry when the thread has been assigned a priority token; and
transmitting the memory operation to a memory system to complete the memory operation when the thread has been assigned the priority token.

16. A system comprising:
a multithreaded processor that is configured to:
allocate threads to process a workload;
assign a set of reallocatable priority tokens with different priorities to at least a portion of the threads, wherein access to a resource, by each one of the threads, is based on the priority token assigned to the thread; and
execute, by the multithreaded processor, the threads to process the workload, comprising:
determining that no cache entries are available to store data to complete a memory operation associated with a thread;
determining that a priority token assigned to the thread is lower priority compared with priority tokens associated with the cache entries; and
transmitting the memory operation to a memory system to complete the memory operation for the thread.

17. The system of claim 16 , wherein the resource is a cache memory.

18. A non-transitory computer-readable storage medium storing instructions that, when executed by a multithreaded processor, causes the multithreaded processor to perform steps comprising:
allocating threads to process a workload;
assigning a set of reallocatable priority tokens with different priorities to at least a portion of the threads, wherein access to a resource, by each one of the threads, is based on the priority token assigned to the thread; and
executing the threads to process the workload, the executing comprising:
determining that no cache entries are available to store data to complete a memory operation associated with a thread;
determining that a priority token assigned to the thread is lower priority compared with priority tokens associated with the cache entries; and
transmitting the memory operation to a memory system to complete the memory operation for the thread.

Assignees

• Nvidia Corp

Inventors

• Johnson Daniel Robert
• Rhu Minsoo
• O'Connor James M
• Keckler Stephen William

Classifications

• G06F2209/5021

  Priority · CPC title

• G06F9/5027 Primary

  the resource being a machine, e.g. CPUs, Servers, Terminals · CPC title

• G06F9/5016

  the resource being the memory · CPC title

• G06F9/48

  Program initiating; Program switching, e.g. by interrupt · CPC title

• Y02B60/142

  Cross-Sectional Technologies · mapped topic