System and method for efficient scheduling of periodic phenomena

• US 20050034126A1
• Filed: 03/31/2004
• Published: 02/10/2005
• Est. Priority Date: 03/31/2003
• Status: Active Grant

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Incorporated
• Inventors: Moore, Sean S. B.
• Granted Patent: US 7,512,947 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/56 implementing delay-aware scheduling
• CPC Class Codes: H04Q 2213/13335 Simulation, emulation

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.

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 set of tasks to the resource, said method comprising the act of defining tasks as cosets of subgroups of a mathematical group, defining a resource as said mathematical group, and defining a unit of measure for the resource in such a way as to assign an order, or size, to the group.

2. The method of claim 1 in which the cosets representing tasks, the groups representing resources, and units of measure are defined over any physical domain, including but not limited to time, space, frequency, energy, speed, and mass.

3. 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.

4. The method of claim 1 wherein said scheduling system includes a plurality of resources.

5. The method of claim 4 wherein said plurality of resources are distributed throughout a physical domain.

6. 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 can be fully 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.

7. The method of claim 6 wherein a task can be represented by contiguous cosets of a group.

8. The method of claim 5 wherein said plurality of resources are represented by groups with at least two different orders.

9. The method of claim 1 wherein said system includes a packet switching communications system having periodic scheduled task appointments.

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 of the group representing a resource, from the power set of the prime factors of N, wherein this set is equivalent to the set of subgroups of the (additive) group Z_N wherein if the prime factorization of N=p₁p₂p₃ . . . p_j, then the set of all possible subgroup generators is composed of the 2^j values 1, p₁, p₂, p₃, . . . , p_j, p₁p₂, p₁p₃, . . . , p₁p_j, p₂p₃, p₂p₄, . . . , p₂p_j, . . . , p₁p₂p₃ . . . p_j.

11. The method of claim 1 wherein given a set of one or more subgroups with generator values selected from the set P={p₁, p₂, . . . 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.

12. The method of claim 1 wherein said system supports tasks represented by subgroups with generator values selected from P={p₁, p₂, . . . p_k} 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.

13. 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.

14. 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.

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 11 wherein the set of subgroup generators is restricted to a subset that is smaller than said set of subgroup generators.

17. The method of claim 1 in which the groups representing resources are chosen such that the intersection of cosets representing tasks will be null.

18. The method of claim 1 in which the unit of measure for a resource is chosen such that the set of generator values of all of the subgroups of the group representing said resource are not pairwise relatively prime or is chosen such that the said set of generator values has a greatest common divisor that is relatively large.

19. The method of claim 5 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.

20. The method of claim 1 further including the act of encoding system state information using group, subgroup, or coset notations.

21. The method of claim 1 wherein said scheduler identifies possible collision events, or equivalently the elements of a non-null intersection of cosets that represent tasks, before such possible events occur.

27. A scheduler operating in according with the method of claim 1.

28. A scheduling system operating in accordance with the method of claim 1.

29. The method of claim 1 wherein given a set of coset representatives, the act of defining cosets for tasks further includes the act of selecting subgroups with generator values selected from a set P={p₁, p₂, . . . p_k}, such that for any two tasks with coset representatives x and y, the two subgroups have generators p_i 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.

30. 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 the act of assigning subgroups to the tasks, wherein subgroup generator values are chosen from the set P={p₁, p₂, . . . p_k}, and further including the act of 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.

22. A scheduling system having a plurality of tasks, a resource for servicing the tasks, and 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 mathematical group.

23. The system of claim 22 wherein a task can be represented by a coset of a subgroup, and the coset can be fully 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.

24. The system of claim 22 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 (additive) group Z_N wherein if the prime factorization of N=p₁p₂p₃ . . . p_j, then said set of all subgroups has as generators the values selected from the set of 2^j values 1, p₁, p₂, p₃, . . . , p_j, p₁p₂, p₁p₃, . . . , p₁p_j, p₂p₃, p₂p₄, . . . p₂p_j, . . . p₁p₂p₃ . . . p_j.

25. The system of claim 24 wherein given a set of one or more subgroups with generator values selected from the set P={p₁, p₂, . . . 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.

26. The system of claim 24 wherein said system supports tasks represented by subgroups with generator values selected from P={p₁, p₂, . . . p_k} 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.

31. A method for synthesizing a task, represented by a coset and associated subgroup, from a plurality of tasks represented by cosets with subgroups different from the subgroup representing said task.

32. A method for decomposing a task, represented by a coset and associated subgroup, into a plurality of tasks represented by cosets with subgroups different from the subgroup representing said task.

33. 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 the act of 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.

34. The method of claim 33 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.

35. The method of claim 33 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 the act of 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 (additive) group Z_N wherein if the prime factorization of N=p₁p₂p₃ . . . p_j, then said set of task period values has as elements the 2^j values 1, p₁, p₂, p₃, . . . , p_j, p₁p₂, p₁p₃, . . . , p₁p_j, p₂p₃, p₂p₄, . . . p₂p_j, . . . , p₁p₂p₃ . . . p_j.

36. The method of claim 35 wherein given a set of one or more periodic tasks with rate values selected from R={r₁, r₂, 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₁, p₂, . . . p_k}, where p_j=N/r_j and where N is the measure of the resource schedule period, further including the act of 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.

37. The method of claim 35 wherein said system supports tasks with rates selected from a set R={r₁, r₂, . . . r_k} or equivalently with task period values selected from a corresponding set P={p₁, p₂, . . . p_k}, where p_j=N/r_j, and where N is the measure of the resource schedule period, 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.

38. The method of claim 33 wherein said system includes a plurality of resources, said plurality of resources represented by groups Z_N with at least two different values of N, or equivalently with at least two different orders for said groups.

39. The method of claim 35 wherein the set of task periods is restricted to a subset that is smaller than said set of task periods.

40. The method of claim 33 in which said resource schedule periods are chosen such that the intersection of cosets representing tasks will be null.

41. The method of claim 33 in which the unit of measure for said resource schedule period is chosen such that the said set of task period values are not pairwise relatively prime or chosen such that said set of task period values has a greatest common divisor that is relatively large.

42. The method of claim 35 in which the unit of measure for said resource schedule period is chosen such that the said set of task period values are not pairwise relatively prime or chosen such that said set of task period values has a greatest common divisor that is relatively large.

43. The method of claim 33 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.

44. 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 set of tasks to the resource, said method comprising the act of defining a unit of measure for the resource schedule period such that that the resource schedule period is indexed by elements of a mathematical group and tasks are represented either by cosets of subgroups of said mathematical group or by arbitrary collections of elements of said group representing said resource schedule period.

45. A scheduling system having a plurality of periodic tasks, a resource for servicing the tasks, and a scheduler that identifies the plurality of tasks with cosets of subgroups of a mathematical group representing said resource, where said group is chosen by defining one or more units of measure for the resource schedule period in such a way as to index the resource schedule period by the elements of said mathematical group.

46. A method for modeling and structuring a scheduling system, said system including a plurality of tasks, a plurality of resources for servicing the tasks, and a scheduler that assigns said tasks to said resources, said method comprising the act of defining a unit of measure for the resource in such a way that the resources are indexed by elements of mathematical groups and tasks are represented either by cosets of subgroups of said mathematical groups or by arbitrary collections of elements of said groups representing resources.