Patent US5261053A successfully refreshed from Google Patents.
US5261053A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Cache affinity scheduler
Assignee: International Business Machines Corp
•
Filing: 1992-11-30
•
Granted: 1993-11-09
•
Expires: 2012-11-30
Abstract
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.
Inventors
- 👤 Andrew J. Valencia
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 19:14
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5005; G06F9/5027; G06F9/5033; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0842
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
190 words
A load balancing system for use with a computing system having multiple computing engines each having a respective affinity run queue onto which a number of processes are enqueued, the load balancing system comprising: calculating means for calculating for each engine the number of processes associated with the engine; comparing means for comparing the number of processes associated with each engine with a variable associated with the engine; variable adjusting means for adjusting for each engine the variable associated with the engine by a particular amount if the number of processes associated with the engine is greater than the variable associated with the engine; determining means for determining whether the variable having a highest value is a predetermined amount greater than the variable having a lowest value; and process moving means for moving processes from the affinity run queue of the engine associated with the variable having the highest value to the affinity run queue of the engine associated with the variable having the lowest value if the determining means determines that the variable with the highest value is the predetermined amount greater than the variable with the lowest value.
Claim 2
Dependent Claim
190 words
A load balancing system for use with a computing system having multiple computing engines each having a respective affinity run queue onto which a number of processes are enqueued, the load balancing system comprising: calculating means for calculating for each engine the number of processes associated with the engine; comparing means for comparing the number of processes associated with each engine with a variable associated with the engine; variable adjusting means for adjusting for each engine the variable associated with the engine by a particular amount if the number of processes associated with the engine is greater than the variable associated with the engine; determining means for determining whether the variable having a highest value is a predetermined amount greater than the variable having a lowest value; and process moving means for moving processes from the affinity run queue of the engine associated with the variable having the highest value to the affinity run queue of the engine associated with the variable having the lowest value if the determining means determines that the variable with the highest value is the predetermined amount greater than the variable with the lowest value.
Claim 3
Dependent Claim
24 words
The system of claim 1 in which the number associated with each engine equals the number of process enqueued to the affinity run queue.
Claim 4
Dependent Claim
36 words
The system of claim 1 in which the number associated with each engine equals a number of processes enqueued to the affinity run queue plus one if a process is being currently run by the engine.
Claim 5
Dependent Claim
80 words
The system of claim 1 in which X processes are enqueued to the affinity run queue of the engine associated with the variable having the highest value and Y processes are enqueued to the affinity run queue of the engine associated with the variable having the lowest value, and the number of processes moved from the engine associated with the variable having the highest value to the engine associated with the variable having the lowest value is equal to (X-Y)/2.
Claim 6
Dependent Claim
12 words
The system of claim 1 in which the particular amount is 150.
Claim 7
Dependent Claim
12 words
The system of claim 1 in which the predetermined amount is two.
Claim 8
Dependent Claim
15 words
The system of claim 1 in which the comparing means compares ten times per second.
Claim 9
Dependent Claim
15 words
The system of claim 1 in which the determining means determines once every five seconds.
Claim 10
Dependent Claim
211 words
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; a global run queue; cache context estimating means for estimating respective amounts of cache context with respect to respective cache memories and particular ones of the processes; enqueuing means for enqueuing the processes to the affinity run queues and the global run queue; decision means responsive to the estimated amount of cache context for deciding whether a particular process is to be enqueued to a particular one of the affinity run queues or to the global run queue, the decision means including hysteresis so that for one range of amounts of cache context the decision means decides the process is to be enqueued to the global run queue regardless of which run queue the process was most recently enqueued, for another range of amounts of cache context the decision means decides the process is to be enqueued to the particular affinity run queue regardless of which run queue the process was most recently enqueued, and for a middle range of amounts of cache context the decision means decides the process is to be enqueued to the run queue to which the process was most recently enqueued.
Claim 11
Dependent Claim
211 words
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; a global run queue; cache context estimating means for estimating respective amounts of cache context with respect to respective cache memories and particular ones of the processes; enqueuing means for enqueuing the processes to the affinity run queues and the global run queue; decision means responsive to the estimated amount of cache context for deciding whether a particular process is to be enqueued to a particular one of the affinity run queues or to the global run queue, the decision means including hysteresis so that for one range of amounts of cache context the decision means decides the process is to be enqueued to the global run queue regardless of which run queue the process was most recently enqueued, for another range of amounts of cache context the decision means decides the process is to be enqueued to the particular affinity run queue regardless of which run queue the process was most recently enqueued, and for a middle range of amounts of cache context the decision means decides the process is to be enqueued to the run queue to which the process was most recently enqueued.
Claim 12
Dependent Claim
38 words
The computing system of claim 9 in which there is more than one global run queue and the decision means decides which global run queue a process is to be enqueued depending on the type of the process.
Claim 13
Dependent Claim
68 words
A multiple engine computing system that runs a process, comprising: a pointer to a home run queue where the process was first enqueued; a pointer to a current run queue associated with an engine that last ran the process; a parameter stored for estimating an amount of cache context associated with the process; and a memory location storing an identity of an engine that last ran the process.
Claim 14
Dependent Claim
68 words
A multiple engine computing system that runs a process, comprising: a pointer to a home run queue where the process was first enqueued; a pointer to a current run queue associated with an engine that last ran the process; a parameter stored for estimating an amount of cache context associated with the process; and a memory location storing an identity of an engine that last ran the process.
Claim 15
Dependent Claim
16 words
The system of claim 11 in which the parameter is indicative of an engine runtime parameter.
Claim 16
Dependent Claim
68 words
A multiple engine computing system that runs a process, comprising: a memory location storing a priority of a currently running process; a pointer to a list of run queues from which the engine receives processes; a pointer to an affinity run queue associated with the engine; and a memory location storing an engine related parameter used for estimating an amount of cache context associated with a runnable process.
Claim 17
Dependent Claim
68 words
A multiple engine computing system that runs a process, comprising: a memory location storing a priority of a currently running process; a pointer to a list of run queues from which the engine receives processes; a pointer to an affinity run queue associated with the engine; and a memory location storing an engine related parameter used for estimating an amount of cache context associated with a runnable process.
Claim 18
Dependent Claim
66 words
The engine data structure of claim 13 further comprising: a pointer to a run queue not associated with the engine where a process can be moved when the run queue associated with the engine data structure contains more than a predetermined number of processes; and a memory storing a datum indicative of how many processes to move to the run queue not associated with the engine.
References Cited (Backward Citations)
US4567562A
Cited
US4914570A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1996-11-08 | 1997-05-10 | 1997-11-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2000-11-08 | 2001-05-10 | 2001-11-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2004-11-08 | 2005-05-10 | 2005-11-09 | $7700.00 | Window Closed / Lapsed |