US5628013A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for allocating processing time in a frame-based computer system
Assignee: Apple Inc
•
Filing: 1992-09-30
•
Granted: 1997-05-06
•
Expires: 2012-09-30
Abstract
Abstract In a computer system having a digital signal processor for processing tasks in real-time within a series of frames, a method is described for determining whether there is enough processing time available within each frame to process the task such that the frame's total processing time is not exceeded. First, the task's processing time requirement is determined. The time for executing the current task list is then calculated. Next, the remaining amount of processing time available in the frame is determined. This is accomplished by subtracting the current task list execution time from the frame's total processing time. The new task is installed in the task list if the frame's available processing time is at least as great as the task's required processing time. Otherwise, the task is not installed in the task list and an error indication is generated.
Inventors
- 👤 Eric C. Anderson
- 👤 A. Phillip Sohn
- 👤 Hugh B. Svendsen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 06:33
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/48; G06F9/4806; G06F9/4843; G06F9/4881; G06F9/4887
Claims Analysis
Total Claims: 39
Claim 1
Independent Claim
231 words
In a computer system having a processor for processing data in real-time by executing at least one task during each of a series of predetermined duration processing frames, a computer implemented method for determining whether a first task is executable within a particular predetermined duration processing frame such that a total processing duration corresponding to said particular predetermined duration processing frame is not exceeded if said task is processed within said particular predetermined duration processing frame, comprising the steps of: determining a required processing duration for said first task; calculating a required processing duration for a set of tasks in a task list, said set of tasks including at least one second task designated for execution during said particular predetermined duration processing frame, said at least one second task included in said task list for said particular predetermined duration processing frame, said task list specifying at least said second task to be executed in said particular predetermined duration processing frame; calculating an amount of processing time available in said particular predetermined duration processing frame by subtracting said required processing duration for said set of tasks from said total processing duration; and installing said first task in said task list if said amount of processing time available is at least as great as said required processing duration for said first task, otherwise generating a signal indicating said first task cannot be installed.
Claim 2
Dependent Claim
231 words
In a computer system having a processor for processing data in real-time by executing at least one task during each of a series of predetermined duration processing frames, a computer implemented method for determining whether a first task is executable within a particular predetermined duration processing frame such that a total processing duration corresponding to said particular predetermined duration processing frame is not exceeded if said task is processed within said particular predetermined duration processing frame, comprising the steps of: determining a required processing duration for said first task; calculating a required processing duration for a set of tasks in a task list, said set of tasks including at least one second task designated for execution during said particular predetermined duration processing frame, said at least one second task included in said task list for said particular predetermined duration processing frame, said task list specifying at least said second task to be executed in said particular predetermined duration processing frame; calculating an amount of processing time available in said particular predetermined duration processing frame by subtracting said required processing duration for said set of tasks from said total processing duration; and installing said first task in said task list if said amount of processing time available is at least as great as said required processing duration for said first task, otherwise generating a signal indicating said first task cannot be installed.
Claim 3
Dependent Claim
30 words
The method of claim 1 wherein said required processing duration for said set of tasks is determined by adding together processing durations for each installed task in said task list.
Claim 4
Dependent Claim
20 words
The method of claim 2 wherein each task is comprised of at least one module having a module's processing duration.
Claim 5
Dependent Claim
38 words
The method of claim 3 wherein said processing duration for an installed task is calculated by determining a worst-case utilization of said modules corresponding to said task and adding together each module's processing duration for said worst-case utilization.
Claim 6
Dependent Claim
53 words
The method as in claim 3 further comprising the step of implementing one or more scaling vectors corresponding to said module for calculating said module's processing duration, said scaling vectors including a frame rate, a scaling factor, and at least one memory access count(s) corresponding to at least one type of memory reference.
Claim 7
Dependent Claim
95 words
The method of claim 3 further comprising the step of implementing one or more scaling vectors corresponding to said module for calculating said processing duration for said module, wherein said module's processing duration for said module is determined according to the formula mx+b, wherein m correspondence to an incremental amount of time for processing an input sample, b corresponds to an overhead time for said computer system, and x corresponds to a number of samples to process, wherein said scaling vectors include a frame rate, a scaling factor, and said values of m and b.
Claim 8
Dependent Claim
133 words
The method of claim 3 wherein said module's processing duration is calculated in reference to said module's type of algorithm, wherein: if said module comprises a smooth algorithm, said module's processing duration is an estimated processing duration if an actual processing duration has not been measured for said module, otherwise said module's processing duration is comprised of the actual processing duration; if said module comprises a smart-lumpy algorithm, said module's processing duration is comprised of the larger of said estimated processing duration and actual processing duration if said task's worst-case processing duration situation has not yet occurred, otherwise said module's processing duration is said actual processing duration; if said module comprises a dumb-lumpy algorithm, said module's processing duration is the larger of said estimated processing duration or actual processing duration for said module.
Claim 9
Dependent Claim
30 words
The method as in claim 7 wherein a processing allocation of said module is varied dynamically, depending on said availability of processing time within said particular predetermined duration processing frame.
Claim 10
Dependent Claim
34 words
The method of claim 8 further comprising the step of updating said actual processing duration when said task is removed from said task list and storing said updated processing duration in a storage means.
Claim 11
Dependent Claim
25 words
The method of claim 9, wherein said updated processing duration is retrieved and utilized in calculating said required processing duration for said set of tasks.
Claim 12
Dependent Claim
18 words
The method of claim 7 wherein said actual processing duration for said module is measured by a timer.
Claim 13
Dependent Claim
19 words
The method of claim 11 wherein said module's actual processing duration measured by said timer includes related system activities.
Claim 14
Dependent Claim
24 words
The method of claim 12 wherein said module's processing duration measured by said timer is measured in reference to instruction cycles of said processor.
Claim 15
Dependent Claim
75 words
The method of claim 13 wherein if said module is processed in a subsequent predetermined duration processing frame which follows a prior predetermined duration processing frame, a comparison is made between a prior actual processing duration for said prior predetermined duration processing frame and a subsequent actual processing duration for said module during said subsequent predetermined duration processing frame, said actual processing duration for said module is updated with the larger of these two values.
Claim 16
Dependent Claim
26 words
The method as in claim 12 wherein a plurality of scaling vectors corresponding to said module are implemented, enabling said module to function in different instantiations.
Claim 17
Dependent Claim
20 words
The method of claim 15 wherein said scaling vectors include a frame rate, scale factor, and a processing bandwidth value.
Claim 18
Dependent Claim
188 words
In a computer system wherein data is processed in real-time by executing at least one task during each of a series of predetermined duration processing frames, an apparatus for ensuring that a first task can be completely executed within a particular predetermined duration processing frame such that a total processing duration for said particular predetermined duration processing frame is not exceeded, comprising; a task list for specifying a set of tasks to be processed during said particular predetermined duration processing frame, said task list being stored in said computer system; a digital signal processor coupled to said computer system for executing said task list; and an operating system coupled to said computer system which determines an available processing duration for said particular predetermined duration processing frame by subtracting an execution duration for executing said set of tasks from said total processing duration for said particular predetermined duration processing frame, wherein if said available processing duration is at least as large as an execution duration for said first task, said first task is included in said task list, otherwise said first task is not included in said task list.
Claim 19
Dependent Claim
188 words
In a computer system wherein data is processed in real-time by executing at least one task during each of a series of predetermined duration processing frames, an apparatus for ensuring that a first task can be completely executed within a particular predetermined duration processing frame such that a total processing duration for said particular predetermined duration processing frame is not exceeded, comprising; a task list for specifying a set of tasks to be processed during said particular predetermined duration processing frame, said task list being stored in said computer system; a digital signal processor coupled to said computer system for executing said task list; and an operating system coupled to said computer system which determines an available processing duration for said particular predetermined duration processing frame by subtracting an execution duration for executing said set of tasks from said total processing duration for said particular predetermined duration processing frame, wherein if said available processing duration is at least as large as an execution duration for said first task, said first task is included in said task list, otherwise said first task is not included in said task list.
Claim 20
Dependent Claim
56 words
The apparatus of claim 17 further comprising a scaling vector for calculating said execution duration for said first task, said scaling vector including a frame rate, a scale factor, and at least one memory access count corresponding to at least one type of memory reference and wherein said scaling vector being stored in said computer system.
Claim 21
Dependent Claim
94 words
The apparatus of claim 17 further comprising a scaling vector for calculating said execution duration for said first task, said scaling vector including a frame rate, a scale factor, and values m and b, wherein said execution duration for said first task is determined according to the formula mx+b, wherein m correspondence to an incremental amount of time for processing an input sample, b corresponds to an overhead time for said computer system, and x corresponds to a number of samples to process and wherein said scaling vector being stored in said computer system.
Claim 22
Dependent Claim
55 words
The apparatus as in claim 17 further comprising a first flag corresponding to each task in said task list, wherein the state of said first flag determines whether said corresponding task is active, wherein active tasks in said task list are processed during said particular predetermined duration processing frame when said task list is executed.
Claim 23
Dependent Claim
34 words
The apparatus as in claim 20 wherein said execution duration for executing said set of tasks is determined by adding together all processing durations for each task which is installed in said task list.
Claim 24
Dependent Claim
16 words
The apparatus of claim 21 wherein each task is further comprised of at least one module.
Claim 25
Dependent Claim
67 words
The apparatus of claim 22 further comprises a second flag associated with said module which has a module's processing duration, the state of said second flag determining whether said module's processing duration is to be included in calculating said task's processing duration, wherein said task's processing duration is the sum of the total processing times for each module of said task as determined by said second flag.
Claim 26
Dependent Claim
72 words
The apparatus of claim 23 further comprising: a first register associated with said module for storing said module's actually measured processing duration; a second register associated with said module for storing an estimated processing duration for said module; a third flag which determines whether said first register value represents the worst case of said module's processing duration, wherein the state of said first, second and third flags depends upon said module's algorithm.
Claim 27
Dependent Claim
18 words
The apparatus of claim 24 wherein said module's algorithm includes one of three types: smooth, smart-lumpy, and dumpy-lumpy.
Claim 28
Dependent Claim
21 words
The apparatus of claim 25 further comprising a timer for determining said module's actual processing duration including any related system activities.
Claim 29
Dependent Claim
20 words
The apparatus of claim 26 wherein said timer determines said module's actual processing duration in reference of an instruction cycle.
Claim 30
Dependent Claim
52 words
The apparatus of claim 27 wherein each time said module is processed, said timer measures an actual processing duration for said module, said first register is updated with said actual processing duration if said actual processing duration is larger than said first register's current value, otherwise said first register is not updated.
Claim 31
Dependent Claim
28 words
The apparatus of claim 28 further comprising a plurality of scaling vectors associated with said module, enabling said module to perform its function in a plurality of instantiations.
Claim 32
Dependent Claim
20 words
The apparatus of claim 29 wherein said scaling vectors include a frame rate, a scale factor, and a processing value.
Claim 33
Dependent Claim
19 words
The apparatus of claim 30, wherein said estimated processing duration of said module is derived from said scaling vector.
Claim 34
Dependent Claim
23 words
The apparatus of claim 30 wherein said module's processing allocation is varied dynamically, depending on said availability of processing time within said frame.
Claim 35
Dependent Claim
15 words
The apparatus of claim 32 further comprising a storage means for storing updated processing durations.
Claim 36
Dependent Claim
30 words
The apparatus of claim 33 further comprises a means for calculating said execution duration for executing said set of tasks based on said updated processing durations in said storage means.
Claim 37
Dependent Claim
162 words
In a computer system having a processor for processing data by executing at least one task during each of a series of predetermined duration processing frames, a computer implemented method for determining whether a first task can properly be serviced on a timeshare basis during said series of predetermined duration processing frames, comprising the steps of: determining a required processing duration for said task, said first task comprising at least one module having a module's processing duration, said required processing duration for said first task being calculated by determining a worst-case utilization of said at least one module and adding together each module's processing duration corresponding to said worst-case utilization; determining an amount of processing duration which is available for timeshare processing per predetermined duration processing frame; computing a frequency of execution for timeshare processing of said first task during said series of predetermined duration processing frames; and comparing said frequency of execution with a required timeshare execution frequency for said task.
Claim 38
Dependent Claim
162 words
In a computer system having a processor for processing data by executing at least one task during each of a series of predetermined duration processing frames, a computer implemented method for determining whether a first task can properly be serviced on a timeshare basis during said series of predetermined duration processing frames, comprising the steps of: determining a required processing duration for said task, said first task comprising at least one module having a module's processing duration, said required processing duration for said first task being calculated by determining a worst-case utilization of said at least one module and adding together each module's processing duration corresponding to said worst-case utilization; determining an amount of processing duration which is available for timeshare processing per predetermined duration processing frame; computing a frequency of execution for timeshare processing of said first task during said series of predetermined duration processing frames; and comparing said frequency of execution with a required timeshare execution frequency for said task.
Claim 39
Dependent Claim
38 words
A method as in claim 35 further comprising: installing said first task in a list of timeshare tasks if said frequency of execution is at least as large as said required timeshare execution frequency for said first task.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-05 | 2000-11-04 | 2001-05-06 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-05 | 2004-11-04 | 2005-05-06 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-05 | 2008-11-04 | 2009-05-06 | $7700.00 | Window Closed / Lapsed |