TECHNIQUE FOR EFFICIENT PARALLELIZATION OF SOFTWARE ANALYSIS IN A DISTRIBUTED COMPUTING ENVIRONMENT THROUGH INTELLIGENT DYNAMIC LOAD BALANCING

• US 20120110589A1
• Filed: 11/30/2010
• Published: 05/03/2012
• Est. Priority Date: 10/29/2010
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Ghosh, Indradeep, Prasad, Mukul Ranjan
• Granted Patent: US 8,763,001 B2
• Time in Patent Office: Days
• US Class Current: 718/104
• CPC Class Codes: G06F 11/3604 Software analysis for verifying properties of programs byte-code verification G06F9/44589
• CPC Class Codes: G06F 11/3688 for test execution, e.g. scheduling of test suites
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

A method for verifying software includes monitoring a resource queue and a job queue, determining whether the resource queue and the job queue contain entries, and if both the resource queue and the job queue contain entries, then applying a scheduling policy to select a job, selecting a worker node as a best match for the characteristics of the job among the resource queue entries, assigning the job to the worker node, assigning parameters to the worker node for a job creation policy for creating new jobs in the job queue while executing the job, and assigning parameters to the worker node for a termination policy for halting execution of the job. The resource queue indicates worker nodes available to verify a portion of code. The job queue indicates one or more jobs to be executed by a worker node. A job includes a portion of code to be verified.

Claims

1. A distributed computing system, comprising:

two or more worker nodes, the worker nodes configured to execute a job comprising a portion of code to be verified; and

a scheduler node comprising a processor coupled to a memory, wherein;

the memory comprises;

a resource queue indicating a plurality of worker nodes available to verify a portion of code; and

a job queue indicating one or more jobs to be executed by a worker node, each job indicating a portion of a code to be verified;

the scheduler node is configured to determine whether the resource queue and the job queue contain entries;

if both the resource queue and the job queue contain entries, the scheduler node is configured to;

apply a scheduling policy to select a first job;

select a first worker node as a best match for the characteristics of the first job among the resource queue entries;

assign the first job to the first worker node;

assign parameters to the first worker node for a job creation policy for creating new jobs in the job queue while executing the first job; and

assign parameters to the first worker node for a termination policy for halting execution of the first job.

2. The system of claim 1 wherein verifying code comprises symbolically executing code.

3. The system of claim 1 wherein the scheduler node is further configured to:

determine an initial number of worker nodes available to execute jobs;

create an initial number of jobs, the initial number of jobs greater than or equal to the initial number of worker nodes available to execute jobs; and

assign each of the initial number of worker nodes a job to execute.

4. The system of claim 1 wherein the scheduler node is further configured to:

determine whether the job queue is empty and all worker nodes are idle; and

if so, return the results returned from the execution of all jobs.

5. The system of claim 1 wherein the scheduler node is further configured to:

determine whether the job queue is less than a minimum and the resource queue is greater than a maximum; and

if so, adjust one or more policy parameters to increase the production of jobs.

6. The system of claim 1 wherein the scheduler node is further configured to:

determine whether the job queue is less than a first threshold and the resource queue is greater than a second threshold; and

if so, adjust one or more policy parameters to increase the execution of a given resource.

7. The system of claim 1 wherein the scheduler node is further configured to:

determine whether the job queue is greater than a first threshold and the resource queue is less than a second threshold; and

if so, adjust one or more policy parameters to decrease the production of jobs.

8. The system of claim 1 wherein the scheduler node is further configured to:

determine whether the job queue is greater than a first threshold and the resource queue is less than a second threshold; and

if so, adjust one or more policy parameters to decrease the execution of a given resource.

9. The system of claim 1 wherein the scheduler node is further configured to:

evaluate the status of the job queue; and

depending upon the status of the job queue, adjust one or more policy parameters of the system.

10. The system of claim 1 wherein the scheduler node is further configured to:

evaluate the status of the resource queue;

depending upon the status of the resource queue, adjust one or more policy parameters of the system.

11. A method for verifying software, comprising:

monitoring a resource queue and a job queue;

wherein

the resource queue indicates a plurality of worker nodes available to verify a portion of code;

the job queue indicates one or more jobs to be executed by a worker node; and

a job comprises a portion of code to be verified;

determining whether the resource queue and the job queue contain entries;

if both the resource queue and the job queue contain entries;

applying a scheduling policy to select a first job;

selecting a first worker node as a best match for the characteristics of the first job among the resource queue entries;

assigning the first job to the first worker node;

assigning parameters to the first worker node for a job creation policy for creating new jobs in the job queue while executing the first job; and

assigning parameters to the first worker node for a termination policy for halting execution of the first job.

12. The method of claim 11 wherein verifying code comprises symbolically executing code.

13. The method of claim 11 further comprising:

determining an initial number of worker nodes available to execute jobs;

creating an initial number of jobs, the initial number of jobs greater than or equal to the initial number of worker nodes available to execute jobs; and

assigning each of the initial number of worker nodes a job to execute.

14. The method of claim 11 further comprising:

determining whether the job queue is empty and all worker nodes are idle; and

if so, returning the results returned from the execution of all jobs.

15. The method of claim 11 further comprising:

determining whether the job queue is less than a first threshold and the resource queue is greater than a second threshold; and

if so, adjusting one or more policy parameters to increase the production of jobs.

16. The method of claim 11 further comprising:

determining whether the job queue is less than a first threshold and the resource queue is greater than a second threshold; and

if so, adjusting one or more policy parameters to increase the execution time of a given resource.

17. The method of claim 11 further comprising:

determining whether the job queue is greater than a first threshold and the resource queue is less than a second threshold; and

if so, adjusting one or more policy parameters to decrease the production of jobs.

18. The method of claim 11 further comprising:

determining whether the job queue is greater than a first threshold and the resource queue is less than a second threshold; and

if so, adjusting one or more policy parameters to decrease the execution time of a given resource.

19. The method of claim 11 further comprising:

evaluating the status of the job queue;

depending upon the status of the job queue, adjusting one or more policy parameters of the method.

20. The method of claim 11 further comprising:

evaluating the status of the resource queue;

depending upon the status of the resource queue, adjusting one or more policy parameters of the method.

21. An article of manufacture comprising:

a computer readable medium; and

computer-executable instructions carried on the computer readable medium, the instructions readable by a processor, the instructions, when read and executed, for causing the processor to;

monitor a resource queue and a job queue, wherein;

the resource queue indicates a plurality of worker nodes available to verify a portion of code;

the job queue indicates one or more jobs to be executed by a worker node; and

a job comprises a portion of code to be verified;

determine whether the resource queue and the job queue contain entries;

if both the resource queue and the job queue contain entries;

apply a scheduling policy to select a first job;

select a first worker node as a best match for the characteristics of the first job among the resource queue entries; and

assign the first job to the first worker node;

assign parameters to the first worker node for a job creation policy for creating new jobs in the job queue while executing the first job; and

assign parameters to the first worker node for a termination policy for halting execution of the first job.

22. The article of claim 21 wherein verifying code comprises symbolically executing code.

23. The article of claim 21 wherein the processor is further caused to:

determine an initial number of worker nodes available to execute jobs;

create an initial number of jobs, the initial number of jobs greater than or equal to the initial number of worker nodes available to execute jobs;

assign each of the initial number of worker nodes a job to execute.

24. The article of claim 21 wherein the processor is further caused to:

determine whether the job queue is empty and all worker nodes are idle; and

if so, return the results returned from the execution of all jobs.

25. The article of claim 21 wherein the processor is further caused to:

determine whether the job queue is less than a first threshold and the resource queue is greater than a second threshold; and

if so, adjust one or more policy parameters to increase the production of jobs.

26. The article of claim 21 wherein the processor is further caused to:

determine whether the job queue is less than a first threshold and the resource queue is greater than a second threshold; and

if so, adjust one or more policy parameters to increase the execution time of a given resource.

27. The article of claim 21 wherein the processor is further caused to:

determine whether the job queue is greater than a first threshold and the resource queue is less than a second threshold; and

if so, adjust one or more policy parameters to decrease the production of jobs.

28. The article of claim 21 wherein the processor is further caused to:

determine whether the job queue is greater than a first threshold and the resource queue is less than a second threshold; and

if so, adjust one or more policy parameters to decrease the execution time of a given resource.

29. The article of claim 21 wherein the processor is further caused to:

evaluate the status of the job queue;

depending upon the status of the job queue, adjust one or more policy parameters of the resource.

30. The article of claim 21 wherein the processor is further caused to:

evaluate the status of the resource queue;

depending upon the status of the resource queue, adjust one or more policy parameters of the resource.