Cache affinity scheduler
First Claim
1. A computing system, comprising:
- multiple computing engines that run processes, the multiple computing engines being associated with respective cache memories and respective affinity run queues;
cache context estimating means for estimating an amount of cache context of a particular one of the cache memories with respect to a particular one of the processes;
enqueuing means for enqueuing certain ones of the processes to the affinity run queues; and
decision means responsive to the estimated amount of cache context for deciding whether to enqueue the particular process to a particular one of the affinity run queues.
2 Assignments
0 Petitions
Accused Products
Abstract
A computing system (50) includes N number of symmetrical computing engines having N number of cache memories joined by a system bus (12). The computing system includes a global run queue (54), an FPA global run queue, and N number of affinity run queues (58). Each engine is associated with one affinity run queue, which includes multiple slots. When a process first becomes runnable, it is typically attached one of the global run queues. A scheduler allocates engines to processes and schedules the processes to run on the basis of priority and engine availability. An engine typically stops running a process before it is complete. When the process becomes runnable again the scheduler estimates the remaining cache context for the process in the cache of the engine. The scheduler uses the estimated amount of cache context in deciding in which run queue a process is to be enqueued. The process is enqueued to the affinity run queue of the engine when the estimated cache context of the process is sufficiently high, and is enqueued onto the global run queue when the cache context is sufficiently low. The procedure increases computing system performance and reduces bus traffic because processes will run on engines having sufficient cache affinity, but will also run on the best available engine when there is insufficient cache context.
-
Citations
25 Claims
-
1. A computing system, comprising:
-
multiple computing engines that run processes, the multiple computing engines being associated with respective cache memories and respective affinity run queues; cache context estimating means for estimating an amount of cache context of a particular one of the cache memories with respect to a particular one of the processes; enqueuing means for enqueuing certain ones of the processes to the affinity run queues; and decision means responsive to the estimated amount of cache context for deciding whether to enqueue the particular process to a particular one of the affinity run queues. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
-
17. A computing system, comprising:
-
multiple computing engines that run processes, the multiple computing engines each being associated with a cache memory and an affinity run queue; cache context estimating means for estimating with respect to a particular one of the processes an amount of cache context of the cache memory associated with a particular one of the multiple computing engines, which ran the particular process; enqueuing means for enqueuing certain ones of the processes to the affinity run queues; and decision means responsive to the amount of cache context for deciding whether to enqueue the particular process to the affinity run queue associated with the particular computing engine.
-
-
18. A computing system, comprising:
-
multiple computing engines that run processes, the multiple computing engines each being associated with a respective cache memory, a respective affinity run queue, and at least one global run queue; cache context estimating means for estimating an amount of cache context of a particular one of the cache memories with respect to a particular one of the processes; enqueuing means for enqueuing certain ones of the processes to the affinity run queues; and decision means responsive to the amount of cache context for deciding whether to enqueue the particular process to the affinity run queue associated with the particular computing engine or to one of the global run queues.
-
-
19. A computing system, comprising:
-
multiple computing engines that run processes including unaffinitied processes and affinitied processes, the multiple computing engines being associated with respective cache memories, respective affinity run queues, and at least one global run queue; cache context estimating means for estimating an amount of cache context of a particular one of the cache memories with respect to a particular one of the processes; enqueuing means for enqueuing certain ones of the processes to the affinity run queues; and decision means responsive to the estimated amount of cache context for deciding whether a particular unaffinitied process should become affinitied to a particular one of the computing engines and enqueued to the affinity run queue of the particular computing engine, and for deciding whether a particular affinitied process should become unaffinitied and enqueued to one of the global run queues.
-
-
20. A computing system, comprising:
-
multiple computing engines that run processes and are associated with respective affinity run queues, respective particular numbers of the processes being associated with each computing engine, the respective particular numbers being at least zero; storage means for storing multiple variables each having a value and each respectively associated with the multiple computing engines, each respective particular number corresponding to one of the variables; sampling means for repeatedly sampling the respective particular numbers of the processes associated with each computing engine; determining means for determining which of the respective particular numbers of processes are greater than the corresponding variable values; increasing means for increasing each one of the variable values for which a corresponding respective particular number is determined to be greater; and moving means for transferring certain ones of the processes from one of the affinity run queues associated with one of the computing engines associated with a highest variable value to one of the affinity run queues associated with one of the computing engines associated with a lowest variable value. - View Dependent Claims (21, 23)
-
-
22. A method for assigning processes to run queues in a multi-engine computing system, the method comprising the steps of:
-
queuing a process to a global run queue; running the process on a first computing engine which is associated with a first cache memory; storing the process in a memory; storing a first count of a counter associated with the first computing engine at a time that the process is stored; storing a second count of the counter at a time that the process becomes runnable; comparing the first and second counts to estimate the amount of cache context remaining in the first cache memory with respect to the process; and deciding whether to enqueue the process to an affinity run queue associated with the first computing engine or to another run queue based on the estimated amount of cache context.
-
-
24. A computing system, comprising:
-
multiple computing engines that run processes and are associated with respective affinity run queues, respective particular numbers of the processes being associated with each computing engine, the respective particular numbers being at least zero; storage means for storing multiple variables each having a value and each respectively associated with one of the multiple computing engines, each respective particular number corresponding to one of the variables; determining means for determining which of the respective particular numbers of processes are greater than the corresponding variable values; increasing means for increasing each one of the variable values for which a corresponding respective particular number is determined to be greater; and moving means for transferring certain ones of the processes from one of the affinity run queues associated with one of the computing engines having a particular variable value to another one of the affinity run queues associated with one of the computing engines associated with a lower variable value. - View Dependent Claims (25)
-
Specification