Task processing optimization in a multiprocessor system

• US 5,991,808 A
• Filed: 06/02/1997
• Issued: 11/23/1999
• Est. Priority Date: 06/02/1997
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Mitzenmacher, Michael, Broder, Andrei
• Primary Examiner(s): Asta, Frank J.
• Assistant Examiner(s): YUAN, ALMARI ROMERO
• Application Number:
  US08/867,095
• Time in Patent Office: 904 Days
• Field of Search: 709/203, 709/226, 709/229, 709/243, 709/227, 709/104, 709/105, 707/010
• US Class Current: 709/226
• CPC Class Codes: G06F 9/505 considering the load

Abstract

A method of operating a multiprocessor system having a predefined number of processing units for processing data, includes obtaining load information representing a loading of each of a number of randomly selected ones of the processing units. The number of randomly selected processing units is greater than 1 and substantially less than the predefined number of processing units. A least loaded of the randomly selected processing units is identified from the obtained load information. The data is directed to the identified least loaded randomly selected processing unit for processing.

Claims

1. A method of selecting one of a number of resources for servicing an item, comprising the steps of:

randomly selecting a subset of the resources, the subset having an associated number of resources that is greater than 1 and substantially less than the number of resources;

querying each of the randomly selected resources in the subset for load information after said step of selecting;

obtaining, in response to said step of querying, load information representing a loading of each resource in the subset from each resource in the subset;

identifying a least loaded of the randomly selected resources in the subset from the obtained load information; and

directing the item to the identified least loaded randomly selected resource of the subset for servicing on the item.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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