System and method for efficient scheduling of periodic phenomena
View Patent ↗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.
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=(p 1 , p 2 , . . . p k ), the defining cosets for tasks further comprises selecting coset representatives x and y for any two tasks with subgroup generators p i and p j , respectively, such that (x-y) is not evenly divisible by g=gcd(p i , p j ), where gcd( ) is the greatest common divisor function and where g is the greatest common divisor of p i and p j , 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.
2. The method of claim 1 wherein said system includes at least a first task represented by a coset and associated subgroup and at least a second task represented by a second coset and associated subgroup in which the generator of the second subgroup is different from the generator of said first subgroup.
3. The method of claim 1 wherein said scheduling system includes a plurality of resources.
4. The method of claim 3 wherein said plurality of resources are distributed throughout a physical domain.
5. The method of claim 4 wherein said plurality of resources are represented by groups with at least two different orders.
6. The method of claim 4 in which the unit of measure is chosen such that the corresponding set of orders of the groups representing said plurality of resources has a greatest common divisor that is relatively large.
7. The method of claim 1 wherein a task can be represented by a coset of a subgroup of the group representing a resource, 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.
8. The method of claim 7 wherein a task is represented by contiguous cosets of a group.
9. The method of claim 1 wherein said system includes a packet switching communications system having periodic scheduled task appointments for servicing a task.
10. The method of claim 1 wherein said act of defining and measuring tasks as cosets and resources as groups includes the act of deriving a set of possible subgroups associated with said cosets from the value of N, the order o the group representing a resource, from the power set of the prime factors of N, where N is the order of said group representing said resource, wherein this set is equivalent to the set of subgroups of the (additive) group Z N wherein if the prime factorization of N=p 1 p 2 p 3 . . . p j , then the set of all possible subgroup generators is composed of the 2 j values 1, p 1 , p 2 , p 3 , . . . , p j , p 1 p 2 , p 1 p 3 , . . . , p 1 p j , p 2 p 3 , p 2 p 4 , . . . p 2 p 4 , . . . p 2 p j , . . . , p 1 p 2 p 3 . . . p j .
11. The method of claim 1 wherein said system supports tasks represented by subgroups with generator values selected from P=(p 1 , p 2 , . . . p k ), wherein P is a schedule period, and further including the act of uniquely assigning coset representatives to the tasks, where said coset representatives are selected from the set of values (0, 1, . . . g−1), where g=gcd(P), the greatest common divisor of all of the element values in P.
12. The method of claim 1 wherein said system includes a plurality of resources, said plurality of resources represented by groups with at least two different orders.
13. The method of claim 1 wherein said mathematical group is selected from a set of groups consisting of abelian mathematical groups and non-abelian mathematical groups.
14. The method of claim 1 wherein the set of subgroup generators is restricted to a subset that is smaller than said set of subgroup generators.
15. The method of claim 1 wherein the set of subgroup generators is restricted to a subset that is smaller than said set of subgroup generators.
16. The method of claim 1 in which the groups representing resources are chosen such that the intersection of costs representing tasks will be null.
17. The method of claim 1 in which the unit of measure for a resource is chosen from the group consisting of wherein the set of generator values of all of the subgroups of the group representing said resource are not pairwise relatively prime, and wherein the said set of generator values has a greatest common divisor that is relatively large.
18. The method of claim 1 further comprising encoding system state information using at least one of the group consisting of group, subgroup, and coset notations.
19. The method of claim 1 wherein said scheduler identifies at least one of possible collision events before the possible collision events occur, and elements of a non-null intersection of cosets that represent tasks before such possible events occur.
20. The method of claim 1 wherein given a set of coset representatives, the defining cosets for tasks further includes selecting subgroups with generator values selected from a set P=(p 1 , p 2 , . . . p k ), such that for any two tasks with coset representatives x and y, the two subgroups have generators p 1 and p j selected such that (x-y) is not evenly divisible by g=gcd(p i ,p j ), where gcd( ) is the greatest common divisor function and therefore where g is the greatest common divisor of p i and p j .
21. The method of claim 1 wherein said system supports tasks with coset representatives uniquely selected from a set of values (0, 1, . . . g−1), and further including assigning subgroups to the tasks, wherein subgroup generator values are chosen from the set P={p 1 , p 2 , . . . p k } wherein P is a schedule period, and further including selecting the elements in P such that gcd(P), the greatest common divisor of the elements in P, is greater than or equal to g, where g is the joint greatest common divisor of p i and p j .
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 Z N wherein if the prime factorization of N=p 1 p 2 p 3 . . . p j , then said set of all subgroups has as task generators the values selected from the set of 2 j values, 1, p 1 , p 2 , p 3 , . . . , p j , p 1 p 2 , p 1 p 3 , . . . , p 1 p j , p 2 p 3 , p 3 p 4 , . . . p 2 p j , . . . , p 1 p 2 p 3 . . . p j , 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.
23. The system of claim 22 wherein given a set of one or more subgroups with generator values selected from the set P={p 1 , p 2 , . . . p k }, the act of defining cosets for tasks further includes the act of selecting coset representatives x and y for any two tasks with subgroup generators p i , and p j , respectively, such that (x-y) is not evenly divisible by g=gcd(p i , p j ), where gcd( ) is the greatest common divisor function and therefore where g is the greatest common divisor of p i and p j .
24. The system of claim 22 wherein said system supports tasks represented by subgroups with generator values selected from P={p 1 , p 2 , . . . p k }, wherein P is a schedule period, and further including the act of uniquely assigning coset representatives to the tasks, where said coset representatives are selected from the set of values {0, 1, . . . g−1}, where g=gcd(P), the greatest common divisor of all of the element values in P.
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 Z n , 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 Z N wherein if the prime factorization of N=p 1 p 2 p 3 . . . p j , then said set of task period values has as elements the 2 j values, 1, p 1 , p 2 , p 3 , . . . , p j , p 1 p 2 , p 1 p 3 , . . . , p 1 p j , p 2 p 4 , . . . p 2 p j , . . . , p 1 p 2 p 3 . . . p j ; 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.
26. The method of claim 25 wherein said system includes at least a first periodic task having a first period and at least a second periodic task having a second period different from said first period.
27. The method of claim 25 wherein given a set of one or more periodic tasks with rate values selected from R={r 1 , r 2 , . . . r k }, where r j measures the number of service events for a task during a resource schedule period, and a corresponding set of flow periods P={p 1 , p 2 , . . . p k }, where p j =N/r j and where N is the measure of the resource schedule period, further including selecting and assigning to any two tasks any two rates p i and p j and coset representatives x and y such that the intersection of the cosets <p i > x and <p j > y is null by selecting (x-y) that is not evenly divisible by g=gcd(p i , p j ), where g is the joint greatest common divisor of p i and p j .
28. The method of claim 25 wherein said system supports at least one of the group consisting of tasks with rates selected from a set R={r 1 , r 2 , . . . r k } and task period values selected from a corresponding set P={p 1 , p 2 , . . . p k }, where p j =N/r j , wherein P is a schedule period, and where N is the measure of the resource schedule period, further including uniquely assigning coset representatives to the tasks, where said coset representatives are selected from the set of values (0, 1, . . . g−1), where g=gcd(P), the greatest common divisor of all of the element values in P.
29. The method of claim 25 wherein said system includes a plurality of resources, said plurality of resources represented by groups Z N with at least one of the group consisting of at least two different values of N, and at least two different orders for said groups.
30. The method of claim 25 wherein the set of task periods is restricted to a subset that is smaller than said set of task periods.
31. The method of claim 25 in which said resource schedule periods are chosen such that the intersection of cosets representing tasks are null.
32. The method of claim 25 in which the unit of measure for said resource schedule period is chosen from the group consisting of such that the said set of task period values are not pairwise relatively prime and such that said set of task period values has a greatest common divisor that is relatively large.
33. The method of claim 25 in which the unit of measure for said resource schedule period is chosen from the group consisting of such that the said set of task period values are not pairwise relatively prime and such that said set of task period values has a greatest common divisor that is relatively large.
34. The method of claim 25 in which the unit of measure is chosen such that the corresponding set of orders of the groups representing said plurality of resources has a greatest common divisor that is relatively large.