Task processing optimization in a multiprocessor system

Claim 3

A method according to claim 1, wherein the resources are processing units, the item is data and the load information represents the data awaiting servicing by each of the randomly selected processing units in the subset.

Claim 4

A method according to claim 1, wherein the random selection is made uniformly at random.

Claim 5

A method according to claim 1, wherein the random selection is made non-uniformly.

Claim 6

A method according to claim 1, wherein the resources are computer programs, the item is data and the load information represents the data awaiting processing by each of the randomly selected computer programs in the subset.

Claim 7

A method according to claim 1, wherein the loading information represents items queued on a first-in-first-out basis for servicing by each of the randomly selected resources in the subset.

Claim 8

A method according to claim 1, wherein the number of randomly selected resources is 2.

Claim 9

A method according to claim 1, wherein the number of randomly selected resources is a fixed number equal to at least 3 and no more than 10.

Claim 10

A method according to claim 1, wherein the number of randomly selected resources is no more than twenty percent of the number of resources.

Claim 11

A method according to claim 1, wherein the load information represents the current loading of at least one of the randomly selected resources in the subset.

Claim 12

A method according to claim 1, wherein the load information represents stale load information relating to at least one of the randomly selected resources in the subset.

Claim 13

A method according to claim 1, wherein the obtaining of the load information includes: controlling each of the randomly selected resources in the subset to respond to the query with load information representing the loading of the responding randomly selected resource.

Claim 14

A method according to claim 12, wherein each of the randomly selected resources in the subset is queried simultaneously.

Claim 15

A method according to claim 1, wherein the identified least loaded selected resource is a first least loaded selected resource and further comprising the steps of: identifying a second least loaded selected resource from the obtained load information, the first and the second least loaded resources having substantially equal loadings; and arbitrarily selecting one of the first and the second least loaded resources for servicing the item.

Claim 16

A method according to claim 1, wherein the item is a first item, the loading information is first loading information, the number of randomly selected resources in the subset is a number of first randomly selected resources, the identified least loaded of the randomly selected resources is an identified least loaded of the first randomly selected resources, and further comprising the steps of: obtaining second load information representing a loading of each of a number of second randomly selected ones of the resources, the number of second randomly selected resources being greater than the number of first randomly selected resources; identifying a least loaded of the second randomly selected resources from the obtained second load information; and directing a second item to the identified least loaded of the second selected resources for servicing the second item.

Claim 17

A method according to claim 15, wherein the number of first randomly selected resources is 2 and the number of second randomly selected resources is 3.

Claim 18

A method according to claim 15, wherein the first item is a type of item and the second item is a different type of item.

Claim 19

A method according to claim 15, wherein the first item is associated with a customer and the second item is associated with a different customer.

Claim 20

A method according to claim 15, further comprising the steps of: selecting a priority for servicing the first item; selecting a priority for servicing the second item; wherein the selected priority for servicing the first item is different than the selected priority for servicing on the second item.

Claim 21

A multi-resource system for servicing an item, comprising: a plurality of resources having a total number of resources N; a task directing unit interconnectable to each of the plurality of resources and configured (i) to randomly select a subset of the resources, the subset having an associated number of resources that is greater than 1 and substantially less than the total number of resources N; (ii) to query each of the randomly selected resources in the subset for load information after said step of selecting; (iii) to obtain load information representing a loading of each resource in the subset; (iv) to identify a least loaded of the randomly selected resources in the subset from the obtained load information, and (v) to direct the item to the identified least loaded of the randomly selected resources of the subset for servicing the item.

Claim 22

A multi-resource system for servicing an item, comprising: a plurality of resources having a total number of resources N; a task directing unit interconnectable to each of the plurality of resources and configured (i) to randomly select a subset of the resources, the subset having an associated number of resources that is greater than 1 and substantially less than the total number of resources N; (ii) to query each of the randomly selected resources in the subset for load information after said step of selecting; (iii) to obtain load information representing a loading of each resource in the subset; (iv) to identify a least loaded of the randomly selected resources in the subset from the obtained load information, and (v) to direct the item to the identified least loaded of the randomly selected resources of the subset for servicing the item.

Claim 23

A system according to claim 20, wherein the resources are processing units, the item is data and the load information is data awaiting for processing by the identified least loaded processing unit.

Claim 24

A system according to claim 20, wherein the resources are computer programs, the item is data and the load information includes data awaiting processing by each of the randomly selected computer programs in the subset.

Claim 25

A system according to claim 20, wherein the task directing unit is configured to randomly select 2 resources.

Claim 26

A system according to claim 20, wherein the task directing unit is configured to randomly select no more than twenty percent of the total number of resources.

Claim 27

A system according to claim 20, wherein the load information represents the current loading of at least one of the randomly selected resources in the subset.

Claim 28

A system according to claim 20, wherein the load information represents a previous loading of at least one of the randomly selected resources in the subset.

Claim 29

A system according to claim 20, wherein: the task directing unit is configured to query each of he randomly selected resources in the subset for load information; and each of the randomly selected resources in the subset includes a FIFO queue and is configured to respond to the query with load information representing the loading of the queue of the responding randomly selected resource.

Claim 30

A system according to claim 27, wherein the task directing unit is configured to query each of the selected resources in the subset simultaneously.

Claim 31

A system according to claim 20, wherein: the identified least loaded selected resource is a first least loaded selected resource; and the task directing unit is configured to identify a second least loaded selected resource from the obtained load information, the first and the second least loaded resources having substantially equal loadings, and to arbitrarily select one of the first and the second least loaded resources.

Claim 32

A system according to claim 20, wherein; the item is a first item; the loading information is first loading information; the number of randomly selected resources in the subset is a number of first randomly selected resources; the identified least loaded of the selected resources is an identified least loaded of the first randomly selected resources; the task directing unit is configured (i) to obtain second load information representing a loading of each of a number of second randomly selected ones of the plurality of resources, the number of second randomly selected resources being different than the number of first randomly selected resources, and (ii) to identify a least loaded of the second randomly selected resources from the obtained second load information, and (iii) to direct a second item to the identified least loaded of the second randomly selected resources for servicing the second item.

Claim 33

A system according to claim 20, wherein the task directing unit is a first task directing unit, the item is a first item, the loading information is first loading information, the number of randomly selected resources is a number of first randomly selected resources, the identified least loaded of the selected resources in the subset is an identified least loaded first randomly selected resources, and further comprising: a second task directing unit configured (i) to obtain second loading information representing a loading of each of a number of second randomly selected ones of the plurality of resources, the number of second randomly selected resources being different than the number of first randomly selected resources, (ii) to identify a least loaded of the second randomly selected resources from the obtained second loading information, and (iii) to direct a second item to the identified least loaded of the second randomly selected resources for servicing the second item.

Claim 34

A system according to claim 31, wherein the first item and the second item are different types of item.

Claim 35

A system according to claim 20, wherein the task directing unit is configured to randomly select a fixed number of resources equal to at least 3 and no more than 10.

Claim 36

An article of manufacture for processing data in a multiprocessor environment, comprising: computer readable storage medium; and computer programming stored on said storage medium; wherein said stored computer programming is configured to be readable from said computer readable storage medium by a computer and thereby cause said computer to operate so as to: randomly select a subset of at least 2 processing units, the subset having an associated number of processing units that is substantially less than the number of processing units; query the processing units in the subset for load information; obtain, in response to the query, load information representing a loading of each resource in the subset from each resource in the subset; identify a least loaded of the randomly selected processing units in the subset from the obtained load information; and direct the data to the identified least loaded selected processing unit in the subset for processing.

Claim 37

An article of manufacture for processing data in a multiprocessor environment, comprising: computer readable storage medium; and computer programming stored on said storage medium; wherein said stored computer programming is configured to be readable from said computer readable storage medium by a computer and thereby cause said computer to operate so as to: randomly select a subset of at least 2 processing units, the subset having an associated number of processing units that is substantially less than the number of processing units; query the processing units in the subset for load information; obtain, in response to the query, load information representing a loading of each resource in the subset from each resource in the subset; identify a least loaded of the randomly selected processing units in the subset from the obtained load information; and direct the data to the identified least loaded selected processing unit in the subset for processing.

Claim 38

An article of manufacture according to claim 34, wherein the data includes first data and second data, the directed data is first data, the load information is the first load information, the number of randomly selected processing units is a number of first randomly selected processing units, the identified least loaded of the selected processing units is an identified least loaded of the first randomly selected processing units, and said stored computer programming is configured to be readable from said computer readable storage medium by the computer to thereby cause said computer to operate so as to: associate the first data with a first processing priority; associate the second data with a second processing priority higher than the first processing priority; query a number of second randomly selected ones of the processing units to obtain second load information representing data queued for processing by each of the second randomly selected processing units, the number of second randomly selected processing units being greater than the number of first randomly selected processing units; identify a least loaded of the second randomly selected processing units from the obtained second load information; and direct the second data to the identified least loaded of the second randomly selected processing units for processing.

Claim 39

An article of manufacture according to claim 35, wherein the first data and the second data are different types of data.