Task distribution

Details Task distribution Task distribution

1999-07-16

2003-11-11

Maung, Zarni (Department: 2154)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C711S147000, C711S203000, C711S220000, C712S013000, C712S021000, C712S022000, C717S151000

Reexamination Certificate

active

06647408

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to processor allocation generally, that is, to the problem of associating tasks with processing units in a computing system. The invention relates more particularly to associations made using derived task spaces and multidimensional task spaces.
TECHNICAL BACKGROUND OF THE INVENTION
Networks and other collections of connected processing units can be much more reliable than a single processing unit for a variety of reasons. When a processing unit fails, its tasks can be reassigned to working units, and new tasks can be diverted away from the failed unit. Tasks can often be performed faster by adding processing units and dividing tasks between processing units, which can then execute the tasks at least partially in parallel. Processing units include individual computer CPUs and supporting circuitry and software necessary for executing a task, as well as larger groups of processors such as multiprocessors and clusters.
One traditional method of associating tasks with processing units includes assigning a name or an ordinal number (sometimes referred to as a whole number or integer) to each task. A similar name or ordinal number is assigned to each processing unit. Names may be strings, enumeration values, or other familiar identifiers. Each task is then placed on a list associated with the assigned processing unit by placing its name, number, or other identifier on the list. Each processing unit thus has a list of the tasks it needs to perform. When a processing unit is added to the computing system, tasks must be explicitly sent to the new server. If existing tasks are among those sent, their identifiers must be located in the existing server list, deleted, and then reassigned to a new server. When a processing unit fails, tasks in the failed server's list must be located, deleted and then reassigned to a new server.
One variation assigns a fractional number (sometimes referred to as a real number) to each task and a range of fractional values to each processing unit. For instance, each task could be assigned a fraction in the interval [0, 1] on the real number line using the familiar Euclidean metric, with each processing unit being assigned a subinterval within that range. A given task is then associated with a given processing unit if the interval allocated to the processing unit contains the fraction assigned to the task.
With either approach, load balancing may be used to spread tasks evenly among servers or other processing units. Load balancing algorithms determine where to assign each task so that the collection of tasks and processing units satisfies some criterion such as finishing as quickly as possible. To achieve high reliability of the network as a whole, tasks assigned to failed servers are rebalanced across operating servers. This may require redistributing the list associated with a failed processing unit among the currently working processing units. Making, maintaining, and redistributing the lists is a relatively expensive operation. Distributed networks must often execute complicated distributed algorithms using imperfect knowledge to approximate optimal bandwidth, and task lists must often be kept in multiple places to facilitate recovery from failures.
A drawback of the approach that assigns fractions in [0 . . . 1] to tasks is that assigning the fractions may require difficult or arbitrary choices, because only a single fraction value is assigned to a given task. All servers that might be eligible to receive the task must likewise be characterized in the same way, namely, according to the single criterion that was used when characterizing the task by assigning it a fraction value.
Thus, it would be an advancement in the art to provide improved ways to associate tasks with server computers and other processing units so that creating and maintaining conventional task lists is unnecessary.
It would also be an advancement to provide improved ways to associate tasks with processing units such that the tasks and the processors may be characterized according to several criteria.
It would be an additional advancement to provide such improvements which extend the capabilities of existing processor allocation mechanisms, and hence can be used in conjunction with existing mechanisms.
Such improvements are disclosed and claimed herein.
BRIEF SUMMARY OF THE INVENTION
The present invention provides improved tools and techniques for associating tasks with server computers and other processing units. In one embodiment, a computer-implemented method begins by allocating a region within a derived metric space such as a Hausdorff task space with a Hausdorff or other metric, and then assigning a non-empty subset of the task space to each task. Each task is then assigned to the processing unit whose region is closest—in the given metric—to the task's assigned subset. In another embodiment, a computer-implemented method begins by allocating a region within a multidimensional task space which is a complete space having an associated metric, and then assigning each task a point in the space. If the region allocated to the processing unit includes the point which has been assigned to the task, then the task is associated with the processing unit.
Thus, some embodiments avoid giving tasks an identity by assigning a name or a single ordinal number or a single real value. Instead, each task is assigned multiple values for identification, at least for purposes of matching tasks with processing units. Likewise, some embodiments avoid giving processing units an identity by assigning a name or a single ordinal number or a single real value. Instead, each processing unit is assigned a multi-valued and/or multidimensional region. A task or a processing unit may, of course, have other identifiers used for other purposes; the focus here is on identifiers used for processor allocation.
Multidimensional and/or derived task spaces are termed “multi-faceted”. A “point” in a multi-faceted task space may thus be multidimensional in some embodiments and one-dimensional in others. A “subset” assigned to a task may be limited to a single point in some embodiments and be allowed to contain multiple points in other embodiments. The “component” value(s) within a point represent the position of the point within the dimension(s) of the task space. Point components may be real or fractional values, and points may include a mixture of such real values with enumerated or ordinal values.
Stated differently, some embodiments each use a derived space as the multi-faceted task space, such as the Hausdorff space (with a Hausdorff or other metric) derived from a foundation space. These derived spaces may be one-dimensional or multidimensional. They include the Hausdorff space derived from the real interval [0 . . . 1], the Hausdorff space derived from the two-dimensional foundation space [0. . . 1]×[0 . . . 1], and Hausdorff spaces derived from crossing the real line R and/or real intervals from R to obtain a space of N-dimensional points, and spaces derived from other foundation spaces. The terms “derived space” and “Hausdorff space” are used as synonyms herein (note, however, that a derived space need not use a Hausdorff metric). In these spaces, each task may be assigned one or more points of the foundation space, since a point in the derived space is a non-empty subset of the foundation space points. Each processing unit is allocated a region which is a not-necessarily-connected subset of the foundation space points.
Other embodiments do not necessarily use derived (Hausdorff) spaces, but use a multidimensional space as the multi-faceted task space. For instance, such embodiments include the two-dimensional space derived from [0 . . . 1]×0 . . . 1] with the familiar Euclidean metric, and higher dimensional Hausdorff spaces derived from crossing the real line R and/or real intervals from R to obtain a space of N-dimensional points. In these spaces, each task may be one (mu

Affiliated with

Also associated with

Rating

Task distribution does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Task distribution, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Task distribution will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3159292