Method and system for efficiently allocating resources for solving computationally hard problems

• US 6,085,216 A
• Filed: 12/31/1997
• Issued: 07/04/2000
• Est. Priority Date: 12/31/1997
• Status: Expired due to Term

• Current Assignee: Hanger Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Lukose, Rajan, Huberman, Bernardo A.
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US09/002,021
• Time in Patent Office: 916 Days
• Field of Search: 709/100, 709/102, 709/103, 709/104, 709/105, 709/108
• US Class Current: 718/104
• CPC Class Codes: G06F 9/50 Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A resource allocation method and system allocates a computational resource between elements of a portfolio of computational entities. The computational resource can be processing time, memory or display screen space. The computational resource can also be associated with a distributed network such as the Internet. In this case, the computational resource is the number of pending messages sent across the distributed network, pendancy time of a message sent across the distributed network, priority of the messages sent across the distributed network, and/or cost of the messages set across the distributed network. When the computational resource is processing time, the resource is allocated between different processes executing on the processor. These different processes include different solution procedures for solving a computationally hard problem, different instances of a single solution procedure for solving the computationally hard problem, and the like. The resource is allocated to optimize the solution time or variance in the solution time. When the computational resource is memory, the resource is allocated between files that are to be stored in the memory, where the total size of the files exceeds the available space in the memory. The available space in the memory is allocated to maximize the likelihood that a file will be stored in the memory when it is needed. When the computational resource is screen real estate, the resource is allocated between display icons that are to be displayed on the display screen, where the total area consumed by the icons exceeds the available screen real estate.

Claims

1. A method for allocating at least one resource between a plurality of entities of an information system, comprising:

selecting at least one performance factor for the plurality of entities;

determining a probability distribution of the at least one performance factor for the plurality of entities;

determining a risk associated with each of the plurality of probability distributions; and

allocating the at least one resource between the plurality of entities based on the plurality of risks.

2. The method of claim 1, wherein:

the information system is a computer comprising a processor and a memory;

the plurality of entities is a plurality of solution procedures for solving a computationally hard problem; and

the at least one resource is processing time of the processor.

3. The method of claim 2, wherein the performance factor is minimum time to obtain a solution to the computationally hard problem.

4. The method of claim 2, wherein the performance factor is minimum total risk associated with the plurality of solution procedures.

5. The method of claim 2, wherein the plurality of solution procedures comprises a plurality of different solution procedures.

6. The method of claim 2, wherein the plurality of solution procedures comprises a plurality of different instances of a single solution procedure.

7. The method of claim 1, wherein:

the information system is a distributed network connecting a plurality of computers;

the plurality of entities is a plurality of messages sent from a first one of the plurality of computers to a second one of the plurality of computers; and

the at least one performance factor is time to receive a response to the plurality of messages from the second computer at the first computer.

8. The method of claim 7, wherein the plurality of messages is a plurality of copies of a single message.

9. The method of claim 7, wherein:

the plurality of messages sent from the first one of the plurality of computers to the second one of the plurality of computers can be pending at the same time; and

the resource to be allocated is number of messages to be sent.

10. The method of claim 7, wherein:

only one of the plurality of messages sent from the first one of the plurality of computers to the second one of the plurality of computers can be pending at any one time; and

the resource to be allocated is delay between cancelling a pending one of the plurality of messages and sending another of the plurality of messages.

11. The method of claim 7, wherein:

the plurality of messages can be sent from the first one of the plurality of computers to the second one of the plurality of computers can be pending at the same time; and

the resource to be allocated is a priority of each of the plurality of messages.

12. The method of claim 1, wherein each different priority has a different price, and the priorities of the plurality of messages are further allocated to obtain a desired total cost.

13. The method of claim 11, wherein each different priority has a different price, and the priorities of the plurality of messages are further allocated to obtain a cost equal to sending a single message at a highest priority.

14. The method of claim 1, wherein:

the information system is a computer comprising a processor and a memory;

the plurality of entities is a plurality of files to be stored in the memory, a total size of the plurality of files exceeding a size of the memory; and

the at least one performance factor is likelihood that a desired file is stored in the memory.

15. The method of claim 14, wherein:

the resource to be allocated is space in the memory for storing the files.

16. The method of claim 1, wherein:

the information system is a computer comprising a processor and a display device, the display device having a display screen having an area;

the plurality of entities is a plurality of display entities to be displayed on the screen of the display device, a total amount of area consumed by the entities being greater than an area of the screen provided for the plurality of display entities; and

the at least one performance factor is likelihood that a desired display entity is displayed on the screen of the display device.

17. The method of claim 16, wherein:

the resource to be allocated the area of the screen provided for displaying the plurality of display entities.

18. A method for efficiently solving a computationally hard problem on a computer comprising a processor and a memory, the method comprising:

selecting a plurality of different computer-implemented solution procedures for solving the computationally hard problem;

selecting at least one performance factor of the computationally hard problem to be optimized;

determining a probability distribution for each at least one performance factor for each of the plurality of solution procedures;

determining a risk associated with each of the plurality of probability distributions; and

allocating at least one computational resource between the plurality of solution procedures based on the plurality of risks.

19. The method of claim 18, wherein the at least one computational resource is processing time of the processor.

20. The method of claim 18, wherein the performance factor is minimum time to obtain a solution to the computationally hard problem.

21. The method of claim 18, wherein the performance factor is minimum total risk associated with the plurality of solution procedures.

22. The method of claim 18, wherein the plurality of solution procedures comprises a plurality of different solution procedures.

23. The method of claim 18, wherein the plurality of solution procedures comprises a plurality of different instances of a single solution procedure.

24. A method for efficiently allocating at least one computational resource between a plurality of processes executing on a computer comprising a processor and a memory, comprising:

selecting at least one performance factor for the plurality of processes;

determining a probability distribution of the at least one performance factor for the plurality of processes;

determining a risk associated with each of the plurality of probability distributions; and

allocating the at least one computational resource between the plurality of processes based on the plurality of risks.