Task distribution

• US 6,647,408 B1
• Filed: 07/16/1999
• Issued: 11/11/2003
• Est. Priority Date: 07/16/1999
• Status: Expired due to Term

• Current Assignee: Micro Focus Software, Inc. (Open Text Corporation)
• Original Assignee: Novell Incorporated (Open Text Corporation)
• Inventors: Carter, Stephen R., Ricart, Glenn, Jensen, Del
• Primary Examiner(s): Maung, Zarni
• Assistant Examiner(s): Nguyen, Dustin
• Application Number:
  US09/354,429
• Time in Patent Office: 1,579 Days
• Field of Search: 700/1, 709/105, 711/203, 711/220, 711/147, 712/13, 712/21, 712/22, 717/151
• US Class Current: 718/105
• CPC Class Codes: G06F 2209/502 Proximity
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]

Abstract

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.

Claims

1. 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 multidimensional region to the processing unit, the multidimensional region being within a multidimensional task space;

a point assignor which assigns a multidimensional point to a task; and

a task associator which associates the task with the processing unit if the multidimensional region allocated to the processing unit is close to the multidimensional point assigned to the task, wherein the task associator uses Euclidean distance to determine whether the multidimensional region allocated to the processing unit is close to the multidimensional point assigned to the task.

2. The system of claim 1, wherein the computing system has at least two processing units, each multidimensional region includes an interval in a given dimension, and the region allocator allocates equally sized intervals in the given dimension to each processing unit.

3. The system of claim 1, wherein the computing system has at least two processing units, the processing units are unequally powerful according to a selected metric, each multidimensional region includes an interval in a given dimension corresponding to the selected metric, and the region allocator allocates intervals in the given dimension for each processing unit proportional to the power of each processing unit according to the selected metric.

4. The system of claim 1, wherein the computing system has at least two differentiated processing units which are tailored to process specific types of tasks, and the region allocator allocates adjacent regions to those differentiated processing units.

5. The system of claim 1, further comprising a preexisting processor allocator and wherein the region allocator allocates an Interval to the preexisting processor allocator.

6. The system of claim 1, wherein tasks further comprise cooperative tasks and the point assignor assigns nearby points to cooperative tasks.

7. 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 multidimensional region to the processing unit, the multidimensional region being within a multidimensional task space;

a point assignor which assigns a multidimensional point to a task; and

a task associator which associates the task with the processing unit if the multidimensional region allocated to the processing unit is close to the multidimensional point assigned to the task, wherein the task associator uses taxicab distance to determine whether the multidimensional region allocated to the processing unit is close to the multidimensional point assigned to the task.

8. 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 region to the processing unit, the region being within a multi-faceted task space that is a derived space based on a foundation space, such that the region is a subset containing multiple points of the foundation space and the derived space uses a Hausdorff metric;

a point assignor which assigns a point to a task, such that the point is derived space point as a subset containing at least one point of the foundation space; 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.