Estimating a dominant resource used by a computer program

• US 7,797,692 B1
• Filed: 05/12/2006
• Issued: 09/14/2010
• Est. Priority Date: 05/12/2006
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Czajkowski, Grzegorz J.
• Primary Examiner(s): DAS, CHAMELI
• Application Number:
  US11/433,657
• Time in Patent Office: 1,586 Days
• Field of Search: 717/150, 717/151, 717/153, 717/155, 717/156, 717/160, 717/161, 717/154, 717/146, 717/124, 717/149, 718/102, 718/104, 709/201, 712/241, 712/244, 713/502
• US Class Current: 717/161
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals

Abstract

A system that estimates a dominant computational resource which is used by a computer program. During operation, for each basic block in the computer program, the system determines a nesting level for the basic block. Next, the system selects basic blocks with nesting levels greater than a specified threshold. For each selected basic block, the system analyzes the basic block to estimate the dominant computational resource used by the basic block. The system then uses the estimated dominant computational resources for the selected basic blocks to estimate the dominant computational resource for the computer program.

Claims

1. A method for estimating a dominant computational resource which is used by a computer program, comprising:

calculating, at a computer, a nesting level for a basic block in the computer program;

determining whether the nesting level is greater than a specified threshold;

in response to the nesting level being greater than the specified threshold, analyzing the basic block to determine a dominant computational resource used by the basic block;

estimating the dominant computational resource used by the computer program, which involves aggregating the determined dominant computational resources used by a plurality of basic blocks having nesting levels greater than the specified threshold; and

scheduling the computer program to run on a corresponding node in a multi-computer system based on the estimated dominant computational resource used by the computer program.

2. The method of claim 1, wherein aggregating the dominant computational resources used by the basic blocks involves weighting basic blocks with a maximum nesting level more heavily than basic blocks with a less than maximum nesting level.

3. The method of claim 1, wherein the computational resources can include:

CPU resources;

main memory resources (RAM);

network resources; and

disk resources.

4. The method of claim 1, wherein the nesting level is zero for each basic block of the main function that is not within a loop.

5. The method of claim 1, wherein if a basic block contains a method call, for each basic block within the method call, the method further comprises:

determining an initial nesting level for the basic block within the method call; and

calculating a final nesting level of the basic block within the method call by adding the nesting level of the basic block containing the method call to the initial nesting level.

6. The method of claim 1, wherein if a method is recursively called, the nesting level of basic blocks within the method are incremented by a specified value.

7. A non-transitory computer-readable storage medium storing instructions executed by a computer cause the computer to perform a method for estimating a dominant computational resource which is used by a computer program, wherein the method comprises:

calculating a nesting level for a basic block in the computer program;

determining whether the nesting level is greater than a specified threshold;

in response to the nesting level being greater than the specified threshold, analyzing the basic block to determine a dominant computational resource used by the basic block;

estimating the dominant computational resource used by the computer program, which involves aggregating the determined dominant computational resources used by a plurality of basic blocks having nesting levels greater than the specified threshold; and

scheduling the computer program to run on a corresponding node in a multi-computer system based on the estimated dominant computational resource used by the computer program.

8. The non-transitory computer-readable storage medium of claim 7, wherein aggregating dominant computational resources used by the basic blocks involves weighting basic blocks with a maximum nesting level more heavily than basic blocks with a less than maximum nesting level.

9. The non-transitory computer-readable storage medium of claim 7, wherein the computational resources can include:

CPU resources;

main memory resources (RAM);

network resources; and

disk resources.

10. The non-transitory computer-readable storage medium of claim 7, wherein the nesting level is zero for each basic block of the main function that is not within a loop.

11. The non-transitory computer-readable storage medium of claim 7, wherein if a basic block contains a method call, for each basic block within the method call, the method further comprises:

determining an initial nesting level for the basic block within the method call; and

calculating a final nesting level of the basic block within the method call by adding the nesting level of the basic block containing the method call to the initial nesting level.

12. The non-transitory computer-readable storage medium of claim 7, wherein if a method is recursively called, the nesting level of basic blocks within the method are incremented by a specified value.

13. A multi-computer system that estimates a dominant computational resource which is used by a computer program, comprising:

a set of computational nodes;

a computational resource estimation mechanism configured to;

calculate a nesting level for a basic block in the computer program;

determine whether the nesting level is greater than a specified threshold;

in response to the nesting level being greater than the specified threshold, analyze the basic block to determine a dominant computational resource used by the selected basic blocks; and

estimate the dominant computational resource used by the computer program, which involves aggregating the determined dominant computational resources used by a plurality of basic blocks having nesting levels greater than the specified threshold; and

a scheduling mechanism configured to schedule the computer program to run on a corresponding computational node based on the estimated dominant computational resource used by the computer program.

14. The multi-computer system of claim 13, wherein while aggregating the dominant computational resources used by the basic blocks, the computational resource estimation mechanism is configured to weight basic blocks with a maximum nesting level more heavily than basic blocks with a less than maximum nesting level.