Task distribution
View Patent ↗Methods, signals, devices and systems are provided for matching tasks with processing units. A region within a multi-faceted task space is allocated to a processing unit. A point in the multi-faceted task space is assigned to a task. The task is then associated with the processing unit if the region allocated to the processing unit is close to the point assigned to the task. The region allocated to a processing unit may be changed. If no assigned point for a task is sufficiently close to any allocated processing unit region, the task is suspended. Overlapping regions may be assigned to different processing units. In some implementations, the union of the allocated regions covers the task space, while in others it does not. Regions may also be allocated to wait conditions and one or more dimensions of a region may be allocated to conventional processor allocators.
1. A method for distributing tasks among a plurality of processing units using a multi-faceted task space, wherein the multi-faceted task space is divided into a plurality of regions with at least one region associated with each processing unit, the method comprising:
associating a value with a task, wherein the value is based on one or more task attributes;
identifying a location in the multi-faceted task space corresponding to the value;
determining which of the plurality of regions are associated with the identified location; and
assigning the task associated with the value to the processing unit associated with the determined region for processing.
2. The method of claim 1 wherein determining which of the plurality of regions are associated with the identified location includes identifying which of the plurality of regions is closest to the location.
3. The method of claim 1 wherein determining which of the plurality of regions are associated with the identified location includes identifying which of the plurality of regions contains the location.
4. The method of claim 1 wherein determining which of the plurality of regions are associated with the identified location includes identifying which of the plurality of regions is less than a predefined distance from the location.
5. The method of claim 1 further comprising processing the task using the processing unit associated with the determined region.
6. A method for associating tasks with processing units, the method comprising:
allocating a region to a processing unit, the region being within a metric space that is a multifaceted task space;
assigning a point of the multi-faceted task space to a task; and
associating the task with the processing unit if the region allocated to the processing unit is close to the point assigned to the task.
7. The method of claim 6 , wherein allocating a region allocates a region within a multidimensional task space, and wherein assigning a point assigns a point of the multidimensional task space.
8. The method of claim 6 , wherein allocating a region allocates a region within a derived task space, and wherein assigning a point assigns a point of the derived task space.
9. The method of claim 6 further comprising determining if the region allocated to the processing unit is closer to the point assigned to the task than any other allocated region within the task space prior to associating the task with the processing unit, wherein the associating occurs if the region allocated to the processing unit is closer to the point assigned to the task than any other allocated region within the task space.
10. The method of claim 6 further comprising determining if the region allocated to the processing unit contains the point assigned to the task prior to associating the task with the processing unit, wherein the associating occurs if the region allocated to the processing unit contains the point assigned to the task.
11. The method of claim 6 further comprising determining if the distance between the region allocated to the processing unit and the point assigned to the task does not exceed a predetermined threshold prior to associating the task with the processing unit, wherein the associating occurs if the distance between the region allocated to the processing unit and the point assigned to the task does not exceed the predetermined threshold.
12. The method of claim 6 further comprising changing the region allocated to the processing unit within the multi-faceted task space.
13. The method of claim 6 further comprising suspending the task if the task is assigned a point that is not contained within any allocated processing unit region.
14. The method of claim 6 further comprising allocating another region of the multi-faceted task space to at least one additional processing unit.
15. The method of claim 14 , wherein the allocating allocates overlapping regions which define a non-empty intersection, a point assigned to the task is within the intersection, and wherein the associating associates the task with one of the processing units whose region contains the point.
16. The method of claim 14 wherein the union of the allocated regions covers the task space.
17. The method of claim 6 further comprising allocating a region to a wait condition, and associating the task with the wait condition if the region allocated to the wait condition is close to a point assigned to the task.
18. The method of claim 6 wherein the region is not a connected region.
19. A processing unit task association system for associating tasks with processors, the system comprising:
a computing system having at least one processing unit;
a region allocator which allocates a mathematical region to the processing unit, the region being within a multi-faceted task space;
a point assignor which assigns a point to a task; and
a task associator which associates the task with the processing unit if the region allocated to the processing unit is close to the point assigned to the task.
20. The system of claim 19 , wherein the multi-faceted task space is multidimensional, the region allocator allocates a multidimensional region, and the point assignor assigns a multidimensional point.
21. The system of claim 19 , wherein the point assignor assigns to a task point including in a dimension a binary fraction, by randomly assigning a number within a binary fraction space to the dimension in the point.
22. The system of claim 21 , wherein the binary fraction space is represented in the computing system using a number representation which reduces the risk of duplicate binary fractions to an acceptable risk level.
23. The system of claim 19 , wherein the point assignor assigns a point to a task by randomly assigning a point to the task within the region allocated to the processing unit.
24. The system of claim 19 , wherein the computing system has at least two differentiated processing units which are tailored to process specific types of tasks, the region allocator allocates adjacent regions to those differentiated processing units, and the point assignor assigns a point to a task by assigning a point to the task within the union of the regions allocated to those differentiated processing units.