PRIORITIZATION OF MULTIPLE CONCURRENT THREADS FOR SCHEDULING REQUESTS TO SHARED MEMORY
First Claim
1. A memory controller for scheduling thread requests in a general-purpose computer system, comprising:
- a memory request buffer for receiving and buffering a plurality of thread requests from a plurality of concurrent threads on an ongoing basis;
a device for assigning a priority to each thread;
a device for determining a priority level of each request based on the priority of each corresponding thread;
a memory scheduler for determining a servicing order of the requests to access shared memory of the general-purpose computer;
wherein the shared memory comprises a plurality of separate memory banks; and
wherein the servicing order of the requests is determined as a function of the priority level of each request.
2 Assignments
0 Petitions
Accused Products
Abstract
A “request scheduler” provides techniques for batching and scheduling buffered thread requests for access to shared memory in a general-purpose computer system. Thread-fairness is provided while preventing short- and long-term thread starvation by using “request batching.” Batching periodically groups outstanding requests from a memory request buffer into larger units termed “batches” that have higher priority than all other buffered requests. Each “batch” may include some maximum number of requests for each bank of the shared memory and for some or all concurrent threads. Further, average thread stall times are reduced by using computed thread rankings in scheduling request servicing from the shared memory. In various embodiments, requests from higher ranked threads are prioritized over requests from lower ranked threads. In various embodiments, a parallelism-aware memory access scheduling policy improves intra-thread bank-level parallelism. Further, rank-based request scheduling may be performed with or without batching.
63 Citations
20 Claims
-
1. A memory controller for scheduling thread requests in a general-purpose computer system, comprising:
-
a memory request buffer for receiving and buffering a plurality of thread requests from a plurality of concurrent threads on an ongoing basis; a device for assigning a priority to each thread; a device for determining a priority level of each request based on the priority of each corresponding thread; a memory scheduler for determining a servicing order of the requests to access shared memory of the general-purpose computer; wherein the shared memory comprises a plurality of separate memory banks; and wherein the servicing order of the requests is determined as a function of the priority level of each request. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A system for controlling scheduling of memory requests of concurrent threads in a general-purpose computer having shared memory which includes a plurality of memory banks, comprising:
-
a device for receiving a plurality of requests from a plurality of corresponding concurrent threads on an ongoing basis; a device for buffering the requests in a memory request buffer on an ongoing basis; a device for assigning a priority to each of the threads; a device for determining a priority level of each request based on the priority of each corresponding thread; and a device for scheduling an order of servicing of the buffered requests from memory banks of the shared memory based on the priority level of each request. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
-
17. A method for scheduling requests of concurrent threads in a general-purpose computer system having shared memory including a plurality of memory banks, comprising steps for:
-
executing a plurality of concurrent threads on one or more processing cores of the general-purpose computer system on an ongoing basis, each thread generating one or more memory requests for access to a corresponding location of one of the plurality of memory banks; buffering the memory requests in a memory request buffer; assigning a priority to each thread; determining a priority level of each of the buffered memory requests based on the priority of each corresponding thread; scheduling the buffered memory requests based on the priority of the corresponding threads and on the priority level of each request. - View Dependent Claims (18, 19, 20)
-
Specification