US5995997A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and methods for optimally allocating currently available computer resources to future task instances versus continued execution of current task instances
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-05-02
•
Granted: 1999-11-30
•
Expires: 2017-05-02
Abstract
Abstract Apparatus and accompanying methods for optimally using available computer resources, illustratively processing time, and which can be advantageously used for selecting task(s) instances to be precomputed during idle time as well as during other periods of processing activity. Specifically, at an onset of each idle-time interval, processing time is allocated to precompute during the remainder of that interval a future task instance, from among a group of such instances then available for precomputation, that will provide the highest fixed or incremental utility. For those task instances which exhibit constant or varying value with time, task selection is based on maximum probability of future occurrence, or net expected value (NEV), respectively, of each such instance. NEV is evaluated as a product of the task instance probability multiplied by a rate of change in the value (EVC flux) to be provided by that task with continued computation time, respectively. This product is assessed, for task instances that exhibit linearly changing value with time, at the onset of each idle-time interval, or, for task instances that exhibit non-linearly changing value, at the onset of each time slice occurring during such an interval. Processing time can be also allocated, at non-idle times, to precomputing a future task instance in lieu of continuing a presently executing task instance, if the future task instance then exhibits a time-discounted NEV that is larger than the EVC flux presently being provided by the currently executing task instance.
Inventors
- 👤 Eric Horvitz
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 23:02
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4812; G06F9/4818
Claims Analysis
Total Claims: 41
Claim 1
Independent Claim
153 words
A method for use in a computer system, having a processor, for allocating and using currently available processing time comprising the steps of: (a) defining a list having a plurality of future task instances, each of said instances having an incremental utility measure associated therewith resulting from allocation of computational resources to execution of said each future task instance; (b) ascertaining, for each of said future task instances on said list, a corresponding time-discounted incremental utility measure therefor, said time-discounted utility measure being the incremental utility measure for said each future task discounted for time; and (c) if the time-discounted incremental utility measure for one of said future task instances exceeds an incremental utility measure of a currently executing task: suspending the currently executing task prior to its completion so as to define a suspended task; storing partial results of the suspended task for subsequent use; and executing the one future task instance.
Claim 2
Independent Claim
153 words
A method for use in a computer system, having a processor, for allocating and using currently available processing time comprising the steps of: (a) defining a list having a plurality of future task instances, each of said instances having an incremental utility measure associated therewith resulting from allocation of computational resources to execution of said each future task instance; (b) ascertaining, for each of said future task instances on said list, a corresponding time-discounted incremental utility measure therefor, said time-discounted utility measure being the incremental utility measure for said each future task discounted for time; and (c) if the time-discounted incremental utility measure for one of said future task instances exceeds an incremental utility measure of a currently executing task: suspending the currently executing task prior to its completion so as to define a suspended task; storing partial results of the suspended task for subsequent use; and executing the one future task instance.
Claim 3
Dependent Claim
28 words
The method in claim 1 further comprising the step of repeating steps (a)-(c) at the onset of each one of a series of predefined regularly occurring time intervals.
Claim 4
Dependent Claim
36 words
The method in claim 2 wherein the executing step comprises the step of executing said one future task instance during said each time interval to the extent of all remaining time in said each time interval.
Claim 5
Dependent Claim
84 words
The method in claim 3 wherein the executing step comprises the steps of: if the one future task instance completes during the remaining time in said each time interval, storing results of the one future task instance for subsequent use; and if the one future task instance does not complete during the remaining time in said each time interval, storing partial results of the one future task instance obtained at a conclusion of said each time interval and suspending the one future task instance.
Claim 6
Dependent Claim
204 words
The method in claim 4 wherein the currently executing task has a first utility measure associated therewith and each of the future task instances has a second utility measure and a second probability measure associated therewith, the second probability measure specifying for a given future task instance a probability that the given future task instance will be executed at a future time, the first and second utility measures specifying a utility of partial results provided by the first and second task instances, respectively; and wherein the defining step further comprises the step of: determining, for the currently executing task, a first associated rate of change in an expected value of computation therefor; and wherein the ascertaining step further comprises the step of: determining for each of said future task instances a second associated rate of change in an expected value of computation and a time-discounted product of the second utility measure and the second associated rate of change; and the method further comprises the step of: choosing, amongst all of said future task instances, a particular one of the future task instances, as said one future task instance, then having a largest time-discounted product associated therewith which exceeds the first associated rate of change.
Claim 7
Dependent Claim
42 words
The method in claim 5 wherein the first associated rate of change is a pre-defined function of the first utility measure; and the second associated rate of change is a pre-defined function of the second probability measure and the second utility measure.
Claim 8
Dependent Claim
84 words
The method in claim 6 wherein the time-discount product ascertaining step comprises the steps of, for each of said future task instances in the list: determining a corresponding second associated rate of change in the expected value of computation, as a function of the corresponding ones of both of the second probability measures and the second utility measures; and forming the time-discounted product as a product of a pre-defined numeric factor, the corresponding second associated rate of change and the second corresponding probability measure.
Claim 9
Dependent Claim
42 words
The method in claim 7 wherein the first associated rate of change is a pre-defined function of the first utility measure; and the second associated rate of change is a pre-defined function of the second probability measure and the second utility measure.
Claim 10
Dependent Claim
18 words
The method in claim 7 wherein the predefined factor, d is a predetermined number in a range 0<d≦1.
Claim 11
Dependent Claim
36 words
The method in claim 7 wherein the executing step comprises the step of executing said one future task instance during said each time interval to the extent of all remaining time in said each time interval.
Claim 12
Dependent Claim
85 words
The method in claim 10 wherein the executing step further comprises the steps of: if the one future task instance completes during the remaining time in said each time interval, storing results of the one future task instance for subsequent use; and if the one future task instance does not complete during the remaining time in said each time interval, storing partial results of the one future task instance obtained at a conclusion of said each time interval and terminating the one future task instance.
Claim 13
Dependent Claim
123 words
The method in claim 7 wherein the associated first utility measure and the second utility measure, for any one of said plurality of future task instances, are each a corresponding stored value, a corresponding stored function or a corresponding stored look-up table, and the first associated rate of change ascertaining step comprises the step of reading the corresponding stored value, evaluating the corresponding stored function or accessing the corresponding look-up table, respectively, to yield a numeric value of the first utility measure; and the corresponding second associated rate of change determining step comprises the step of reading the corresponding stored value, evaluating the corresponding stored function or accessing the corresponding look-up table, respectively, to yield a numeric value of the second utility measure.
Claim 14
Dependent Claim
31 words
The method of claim 7 further comprising the step of updating the list by adding each new future task instance to the list once said new future task instance is spawned.
Claim 15
Dependent Claim
26 words
The method of claim 12 wherein the new future task instance is spawned by an application program or an operating system then executing on said processor.
Claim 16
Dependent Claim
69 words
The method of claim 14 wherein the selecting step further comprises the steps of: evaluating a probability tree to determine a corresponding numeric value for the probability measure for each of said future task instances in said list; and selecting a future task instance, from among the future task instances in the list, having largest corresponding numeric value for the associated probability measure as said one future task instance.
Claim 17
Dependent Claim
42 words
The method in claim 15 wherein the first associated rate of change is a pre-defined function of the first utility measure; and the second associated rate of change is a pre-defined function of the second probability measure and the second utility measure.
Claim 18
Dependent Claim
23 words
The method of claim 16 further comprising the step of determining probabilities in the tree through a Bayesian network or a Hidden-Markov model.
Claim 19
Dependent Claim
31 words
The method of claim 16 further comprising the step of updating the list by adding each new future task instance to the list once said new future task instance is spawned.
Claim 20
Dependent Claim
26 words
The method of claim 17 wherein the new future task instance is spawned by an application program or an operating system then executing on said processor.
Claim 21
Dependent Claim
17 words
A computer readable medium having computer executable instructions stored therein for performing the steps of claim 1.
Claim 22
Dependent Claim
170 words
Apparatus for use in a computer system, having a processor, for allocating and using currently available processing time comprising: the processor; and a memory having executable instructions stored therein; and wherein the processor, in response to the instructions stored therein: (a) defines a list having a plurality of future task instances, each of said instances having an incremental utility measure associated therewith resulting from allocation of computational resources to execution of said each future task instance; (b) ascertains, for each of said future task instances on said list, a corresponding time-discounted incremental utility measure therefor, said time-discounted utility measure being the incremental utility measure for said each future task discounted for time; and (c) if the time-discounted incremental utility measure for one of said future task instances exceeds an incremental utility measure of a currently executing task: suspends the currently executing task prior to its completion so as to define a suspended task; stores partial results of the suspended task for subsequent use; and executes the one future task instance.
Claim 23
Dependent Claim
170 words
Apparatus for use in a computer system, having a processor, for allocating and using currently available processing time comprising: the processor; and a memory having executable instructions stored therein; and wherein the processor, in response to the instructions stored therein: (a) defines a list having a plurality of future task instances, each of said instances having an incremental utility measure associated therewith resulting from allocation of computational resources to execution of said each future task instance; (b) ascertains, for each of said future task instances on said list, a corresponding time-discounted incremental utility measure therefor, said time-discounted utility measure being the incremental utility measure for said each future task discounted for time; and (c) if the time-discounted incremental utility measure for one of said future task instances exceeds an incremental utility measure of a currently executing task: suspends the currently executing task prior to its completion so as to define a suspended task; stores partial results of the suspended task for subsequent use; and executes the one future task instance.
Claim 24
Dependent Claim
32 words
The apparatus in claim 21 wherein the processor, in response to the stored instructions, repeats operations (a)-(c) at the onset of each one of a series of predefined regularly occurring time intervals.
Claim 25
Dependent Claim
37 words
The apparatus in claim 22 wherein the processor, in response to the stored instructions, executes said one future task instance during said each time interval to the extent of all remaining time in said each time interval.
Claim 26
Dependent Claim
85 words
The apparatus in claim 23 wherein the processor, in response to the stored instructions: if the one future task instance completes during the remaining time in said each time interval, stores results of the one future task instance for subsequent use; and if the one future task instance does not complete during the remaining time in said each time interval, stores partial results of the one future task instance obtained at a conclusion of said each time interval and suspends the one future task instance.
Claim 27
Dependent Claim
187 words
The apparatus in claim 24 wherein the currently executing task has a first utility measure associated therewith and each of the future task instances has a second utility measure and a second probability measure associated therewith, the second probability measure specifying for a given future task instance a probability that the given future task instance will be executed at a future time, the first and second utility measures specifying a utility of partial results provided by the first and second task instances, respectively; and wherein the processor, in response to the stored instructions: determines, for the currently executing task, a first associated rate of change in an expected value of computation therefor; determines for each of said future task instances a second associated rate of change in an expected value of computation and a time-discounted product of the second utility measure and the second associated rate of change; and chooses, amongst all of said future task instances, a particular one of the future task instances, as said one future task instance, then having a largest time-discounted product associated therewith which exceeds the first associated rate of change.
Claim 28
Dependent Claim
42 words
The apparatus in claim 25 wherein the first associated rate of change is a pre-defined function of the first utility measure; and the second associated rate of change is a pre-defined function of the second probability measure and the second utility measure.
Claim 29
Dependent Claim
84 words
The apparatus in claim 26 wherein the processor, in response to the stored instructions and for each of said future task instances in the list: determines a corresponding second associated rate of change in the expected value of computation, as a function of the corresponding ones of both of the second probability measures and the second utility measures; and forms the time-discounted product as a product of a pre-defined numeric factor, the corresponding second associated rate of change and the second corresponding probability measure.
Claim 30
Dependent Claim
42 words
The apparatus in claim 27 wherein the first associated rate of change is a pre-defined function of the first utility measure; and the second associated rate of change is a pre-defined function of the second probability measure and the second utility measure.
Claim 31
Dependent Claim
18 words
The apparatus in claim 27 wherein the predefined factor, d, is a predetermined number in a range 0<d≦1.
Claim 32
Dependent Claim
36 words
The apparatus in claim 27 wherein processor, in response to the stored instructions, executes said one future task instance during said each time interval to the extent of all remaining time in said each time interval.
Claim 33
Dependent Claim
85 words
The apparatus in claim 30 wherein the processor, in response to the stored instructions: if the one future task instance completes during the remaining time in said each time interval, stores results of the one future task instance for subsequent use; and if the one future task instance does not complete during the remaining time in said each time interval, stores partial results of the one future task instance obtained at a conclusion of said each time interval and suspends the one future task instance.
Claim 34
Dependent Claim
106 words
The apparatus in claim 27 wherein the associated first utility measure and the second utility measure, for any one of said plurality of future task instances, are each a corresponding stored value, a corresponding stored function or a corresponding stored look-up table, and the processor, in response to the stored instructions: reads the corresponding stored value, evaluates the corresponding stored function or accesses the corresponding look-up table, respectively, to yield a numeric value of the first utility measure; and reads the corresponding stored value, evaluates the corresponding stored function or accesses the corresponding look-up table, respectively, to yield a numeric value of the second utility measure.
Claim 35
Dependent Claim
35 words
The apparatus of claim 27 wherein the processor, in response to the stored instructions, updates the list by adding each new future task instance to the list once said new future task instance is spawned.
Claim 36
Dependent Claim
26 words
The apparatus of claim 32 wherein the new future task instance is spawned by an application program or an operating system then executing on said processor.
Claim 37
Dependent Claim
69 words
The apparatus of claim 34 wherein the processor, in response to the stored instructions: evaluates a probability tree to determine a corresponding numeric value for the probability measure for each of said future task instances in said list; and selects a future task instance, from among the future task instances in the list, having largest corresponding numeric value for the associated probability measure as said one future task instance.
Claim 38
Dependent Claim
42 words
The apparatus in claim 35 wherein the first associated rate of change is a pre-defined function of the first utility measure; and the second associated rate of change is a pre-defined function of the second probability measure and the second utility measure.
Claim 39
Dependent Claim
27 words
The apparatus of claim 36 wherein the processor, in response to the stored instructions, determines probabilities in the tree through a Bayesian network or a Hidden-Markov model.
Claim 40
Dependent Claim
34 words
The apparatus of claim 36 wherein the processor, in response to stored instructions, updates the list by adding each new future task instance to the list once said new future task instance is spawned.
Claim 41
Dependent Claim
26 words
The apparatus of claim 37 wherein the new future task instance is spawned by an application program or an operating system then executing on said processor.
References Cited (Backward Citations)
US4387427A
Cited
US5381546A
Cited
US5506987A
Cited
US5247677A
Cited
US5727210A
Cited
US5526521A
Cited
EP0672990A2
Cited
US5784616A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-29 | 2003-05-31 | 2003-11-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-29 | 2007-05-31 | 2007-11-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-29 | 2011-05-31 | 2011-11-30 | $7700.00 | Window Closed / Lapsed |