System and method for efficient scheduling of periodic phenomena
First Claim
Patent Images
1. A method for modeling and structuring a scheduling system, said system including a plurality of tasks, a resource for servicing the tasks, and a scheduler that assigns the tasks to the resource, said method comprising:
- defining tasks as cosets of subgroups of a mathematical group, wherein a coset comprises a subgroup of a group representing a resource;
defining a resource as said group;
defining a unit of measure for the resource in such a way as to assign an order, or size, to the group; and
modeling and structuring the scheduling system using the defined tasks, the resource and the unit of measure;
wherein given a set of one or more subgroups with task generator values selected from the set P=(p1, p2, . . . pk), the defining cosets for tasks further comprises selecting coset representatives x and y for any two tasks with subgroup generators pi and pj, respectively, such that (x-y) is not evenly divisible by g=gcd(pi, pj), where gcd( ) is the greatest common divisor function and where g is the greatest common divisor of pi and pj, wherein the cosets represent tasks, the groups represent resources, and units of measure are defined over any physical domain, including at least one of the group consisting of time, space, frequency, energy, speed, and mass.
22 Assignments
0 Petitions
Accused Products
Abstract
The invention described is a system and method for efficient scheduling of periodic phenomena including a collection of methods for modeling and selecting periodic task rates, resource schedule periods, and units of measure for the task and resource periods in scheduling systems such that the systems'"'"' schedulers may be improved with respect to performance metrics such as collision avoidance, computational efficiency, and resource utilization.
12 Citations
34 Claims
-
1. A method for modeling and structuring a scheduling system, said system including a plurality of tasks, a resource for servicing the tasks, and a scheduler that assigns the tasks to the resource, said method comprising:
-
defining tasks as cosets of subgroups of a mathematical group, wherein a coset comprises a subgroup of a group representing a resource; defining a resource as said group; defining a unit of measure for the resource in such a way as to assign an order, or size, to the group; and modeling and structuring the scheduling system using the defined tasks, the resource and the unit of measure; wherein given a set of one or more subgroups with task generator values selected from the set P=(p1, p2, . . . pk), the defining cosets for tasks further comprises selecting coset representatives x and y for any two tasks with subgroup generators pi and pj, respectively, such that (x-y) is not evenly divisible by g=gcd(pi, pj), where gcd( ) is the greatest common divisor function and where g is the greatest common divisor of pi and pj, wherein the cosets represent tasks, the groups represent resources, and units of measure are defined over any physical domain, including at least one of the group consisting of time, space, frequency, energy, speed, and mass. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A computer scheduling system comprising:
-
a memory; a processor; a communications interface; an interconnection mechanism coupling the memory, the processor and the communications interface; and wherein the memory is encoded with an application that when performed on the processor, provides a process for processing information, the process causing the computer system to perform the operations of; providing a plurality of tasks, providing a resource for servicing the tasks, and providing a scheduler that identifies the plurality of tasks with cosets of subgroups of a group representing said resource, where said group is chosen by defining one or more units of measure for the resource in such a way as to index the resource by the elements of said group and wherein said scheduler derives a set of subgroups of said group representing said resource from the power set of the prime factors of N, where N is the order of said group representing said resource, wherein said set is equivalent to the set of subgroups of the group ZN wherein if the prime factorization of N=p1p2p3 . . . pj, then said set of all subgroups has as task generators the values selected from the set of 2j values, 1, p1, p2, p3, . . . , pj, p1p2, p1p3, . . . , p1pj, p2p3, p3p4, . . . p2pj, . . . , p1p2p3. . . pj, and wherein a task is represented by a coset of a subgroup, and the coset is represented by first and second values in which the first value includes a generator of the subgroup and the second value includes a coset representative. - View Dependent Claims (23, 24)
-
-
25. A method for modeling and structuring a scheduling system operating in the time domain, said system including a plurality of periodic tasks, a resource for servicing the tasks, and a schedule period associated with the resource, and a scheduler that assigns the set of tasks to the resource, said method comprising:
-
defining and measuring task periods and said resource schedule period by one or more units of measure in such a way that measurement values for the task periods and the resource schedule period are indexed by elements of a mathematical group and wherein said act of defining and measuring task periods and resource schedule periods identifies the resource with Zn, the group of integers modulo N, where N is the order of the group associated with said resource schedule period, and further includes deriving a set of possible task period values from the power set of the prime factors of N, wherein said set of task period values is equivalent to the set of subgroups of the group ZN wherein if the prime factorization of N=p1p2p3 . . . pj, then said set of task period values has as elements the 2j values, 1, p1, p2, p3, . . . , pj, p1p2, p1p3, . . . , p1pj, p2p4, . . . p2pj, . . . , p1p2p3 . . . pj; and modeling and structuring the scheduling system operating in the time domain using said defining and measuring of task periods and said resource schedule period by one or more units of measure. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32, 33, 34)
-
Specification