Distribution of operations to remote computers

• US 20040083475A1
• Filed: 10/25/2002
• Published: 04/29/2004
• Est. Priority Date: 10/25/2002
• Status: Abandoned Application

• Current Assignee: Mentor Graphics Corporation (Siemens AG)
• Original Assignee: Mentor Graphics Corporation (Siemens AG)
• Inventors: Todd, Robert A., Cobb, Nicolas B., Grodd, Laurence W.
• Application Number:
  US10/280,710
• Publication Number:
  US 20040083475A1
• Time in Patent Office: Days
• US Class Current: 718/102
• CPC Class Codes: G06F 2209/5018 Thread allocation
• CPC Class Codes: G06F 9/5005 to service a request

Abstract

A method and tool are disclosed for distributing operations in a software application from a master computer to one or more slave computers for execution. Operations within the software application are identified that employ input data independent of other input data. The identified operations, which can be organized into groups of one or more operations, may then be distributed to a slave computer for execution. A group of operations may also include one or more heuristics, for determining when the group of operations should be executed on a slave computer. If a group of operations is distributed to a slave computer for execution, the master computer subsequently determines if the slave computer successfully executed those operations. If the slave computer successfully executed the group of operations, it returns the results to the master computer, which then employs the returned results to continue running the software application. If, however, the slave computer was unable to successfully execute the group of operations, then the master computer may execute the group of operations itself or provide the group of operations to another slave computer, allowing the master computer to continue running the software application without interruption.

Claims

1. A method for distributing operations among a plurality of processing threads, comprising:

receiving a plurality of operations for execution on a first thread using input data obtained from a database;

identifying one or more independent operations from among the plurality of received operations, such that the one or more independent operations are for execution using input data independent of the database;

providing at least one of the one or more independent operations to a second thread for execution; and

receiving results of the execution of the at least one independent operation from the second thread.

2. The method for distributing operations recited in claim 1, further comprising:

providing at least another of the one or more independent operations to a third thread for execution; and

receiving results of the execution of the at least another independent operation from the third thread.

3. The method for distributing operations recited in claim 1, further comprising:

if the received results of the execution of the at least one independent operation indicate that the execution of the at least one independent operation was successful, saving the received results; and

if the received results of the execution of the at least one independent operation indicate that the execution of the at least one independent operation was unsuccessful,

reexecuting the at least one independent operation on the first thread or on a third thread, and

receiving results of the reexecution of the at least one independent operation from the first thread or the third thread.

4. The method for distributing operations recited in claim 1, wherein the first thread is running on a first computer, and the second thread is running on a second computer remote from the first computer.

5. The method for distributing operations recited in claim 1, wherein the first computer is a multi-processor computer and the second computer is a single processor computer or multi-processor computer.

6. The method for distributing operations recited in claim 1, wherein the input data from the database is organized into hierarchical cells, such that results obtained by execution of operations using input data of a cell of a first hierarchical level are provided to the database and employed as input data of a cell of a second hierarchical level above the first hierarchical level.

7. A method of distributing operations among a plurality of computers, comprising:

receiving a plurality of operations for execution on a first computer using input data obtained from a database;

identifying one or more independent operations from among the plurality of received operations, such that the one or more independent operations are for execution using input data independent of the database;

determining whether at least one of the one or more independent operations should be executed on a second computer remote from the first computer, and

if it is determined that the at least one independent operation should be executed on the second computer,

providing the at least one independent operation to the second computer for execution, and

receiving results of the execution of the at least one independent operation from the second computer; and

if it is determined that the at least one independent operation should not be executed on a second computer, executing the at least one independent operation on the first computer.

8. The method for distributing operations recited in claim 7, wherein determining whether at least one of the one or more independent operations should be executed on a second computer includes executing a heuristic associated with the at least one independent operation.

9. The method for distributing operations recited in claim 8, wherein the heuristic determines whether the at least one independent operation may be executed on the second computer based upon the amount of independent input data to be used in executing the at least one independent operation.

10. The method for distributing operations recited in claim 9, wherein the heuristic determines whether the at least one independent operation may be executed on the second computer based upon a status of a communication interface between the first computer and the second computer.

11. The method for distributing operations recited in claim 10, wherein the heuristic further determines the status of the communication interface between the first computer and the second computer.

12. The method for distributing operations recited in claim 8, wherein the heuristic determines whether the at least one independent operation may be executed on the second computer based upon a status of a communication interface between the first computer and the second computer.

13. The method for distributing operations recited in claim 12, wherein the heuristic further determines the status of the communication interface between the first computer and the second computer.

14. The method for distributing operations recited in claim 8, wherein:

the heuristic determines whether the at least one independent operation will be executed on the second computer using only a first portion of independent input data to be used in executing the at least one independent operation; and

if the heuristic determines that the at least one independent operation will be executed on the second computer using only a first portion of the independent input data to be used in executing the at least one independent operation, the heuristic

provides the at least one independent operation to the second computer with the first portion of the independent input data to be used in executing the at least one independent operation, and

provides the at least one independent operation to a third computer with a second portion of the independent input data to be used in executing the at least one independent operation.

15. The method for distributing operations recited in claim 7, wherein:

the first computer employs multiple processing threads and multiple processors, and

determining whether at least one of the one or more independent operations should be executed on a second computer includes

determining if a processing thread is available on the first computer for executing the at least one independent operation, and

if a processing thread is available on the first computer for executing the at least one independent operation, determining that the at least one independent operation should be executed by the available processing thread on the first computer.

16. The method for distributing operations recited in claim 7, wherein determining whether at least one of the one or more independent operations should be executed on a second computer includes:

determining if a processing thread is available on the second computer for executing the at least one independent operation, and

if a processing thread is available on the second computer for executing the at least one independent operation, determining that the at least one independent operation should be executed by the available processing thread on the second computer.

17. The method for distributing operations recited in claim 7, further comprising:

determining whether at least another of the one or more independent operations should be executed on a third computer; and

if it is determined that the at least another independent operation should be executed on a third computer,

providing the at least another independent operation to the third computer for execution, and

receiving results of the execution of the at least another independent operation from the third computer; and

if it is determined that the at least another independent operation should not be executed on the third computer, executing the at least another independent operation on the first computer.

18. The method for distributing operations recited in claim 7, further comprising:

if the received results of the execution of the at least one independent operation indicate that the execution of the at least one independent operation was successful, saving the received results; and

if the received results of the execution of the at least one independent operation indicate that the execution of the at least one independent operation was unsuccessful, reexecuting the at least one independent operation.

19. The method for distributing operations recited in claim 18, further comprising reexecuting the at least one independent operation on the first computer.

20. The method for distributing operations recited in claim 18, further comprising reexecuting the at least one independent operation on a third computer.

21. The method for distributing operations recited in claim 7, wherein the input data from the database is organized into hierarchical cells, such that results obtained by execution of operations using input data of a cell of a first hierarchical level are provided to the database and employed as input data of a cell of a second hierarchical level above the first hierarchical level.

22. A tool for distributing operations among a plurality of computers, comprising:

an identification module that;

parses through a plurality of operations for execution on a master computer using input data obtained from a database, and

identifies one or more independent operations that use input data independent of the database from among the plurality of received operations;

a remote execution determination module that determines whether each identified independent operation should be executed on a slave computer or executed on the master computer; and

a remote computer interface module that;

transmits independent operations from the master computer to one or more slave computers for execution, and

receives results of execution of the transmitted independent operations from the one or more slave computers.

23. The tool recited in claim 22, wherein the remote execution determination module is configured to employ a heuristic associated with each independent operation to determine whether the independent operation should be executed on a slave computer.

24. The tool recited in claim 23, wherein the remote execution determination module is configured to employ a heuristic that determines whether a independent operation may be executed on a slave computer based upon the amount of independent input data to be used in executing the independent operation.

25. The tool recited in claim 24, wherein the remote execution determination module is configured to employ a heuristic that further determines whether a independent operation may be executed on a slave computer based upon a status of a communication interface between the master computer and the slave computer.

26. The tool recited in claim 25, wherein the remote execution determination module is configured to further determine the status of the communication interface between the master computer and the slave computer.

27. The tool recited in claim 23, wherein remote execution module is configured to employ a heuristic that determines whether a independent operation may be executed on a slave computer based upon a status of a communication interface between the master computer and the slave computer.

28. The tool recited in claim 27, wherein the remote execution determination module is configured to further determine the status of the communication interface between the master computer and the slave computer.

29. The tool recited in claim 22, wherein:

the remote execution determination module is configured to employ a heuristic that determines whether a independent operation will be more efficiently executed on a slave computer using only a portion of independent input data to be used in executing the independent operation; and

if the remote execution determination module determines that the independent operation will be more efficiently executed on the slave computer using only a portion of the independent input data to be used in executing the independent operation, then the remote computer interface module

provides the independent operation to a first slave computer with a first portion of the independent input data to be used in executing the independent operation, and

provides the at independent operation to a second slave computer with a second portion of the independent input data to be used in executing the at least one independent operation.

30. The tool recited in claim 22, wherein:

the master computer employs multiple processing threads with multiple processors; and

the remote execution determination module is configured to;

determine if a processing thread is available on the master computer for executing the independent operation, and

if a thread is available on the master computer for executing the independent operation, determine that the independent operation should be executed by the available thread on the master computer.

31. The tool recited in claim 22, wherein the remote execution determination module is configured to:

determine if a processing thread is available on a slave computer for executing the at least one independent operation; and

if a thread is available on a slave computer for executing the independent operation, determine that the independent operation should be executed by the available thread on the slave computer.

32. The tool recited in claim 22, wherein the remote computer interface module is configured to:

save received results of the execution of a independent operation that indicate that the execution of the independent operation was successful, and

have the independent operation reexecuted when the received results of the execution of a independent operation indicate that the execution of the independent operation was unsuccessful.

33. The tool recited in claim 32, wherein the remote computer interface module is configured to have the independent operation reexecuted on the master computer.

34. The tool recited in claim 32, wherein the remote computer interface module is configured to have the independent operation reexecuted on a second slave computer.

35. A computer-readable medium having stored thereon a data structure, comprising:

a plurality of operations for execution on a host computer; and

an identifier identifying a group of the operations as operations that may alternately be executed on a slave computer.

36. The computer-readable medium recited in claim 35,wherein the data structure further comprises a heuristic for the group of operations that, when executed, determines whether the associated group of operations may be executed on a slave computer.

37. The computer-readable medium recited in claim 36, wherein the heuristic determines whether the group of operations may be executed on a slave computer based upon the amount of independent input data to be used in executing the group of operations.

38. The computer-readable medium recited in claim 37, wherein the heuristic further determines whether the group of operations may be executed on a slave computer based upon a status of a communication interface between the master computer and the slave computer.

39. The computer-readable medium recited in claim 38, wherein the heuristic further determines the status of the communication interface between the master computer and the slave computer.

40. The computer-readable medium recited in claim 36, wherein the heuristic determines whether the group of operations may be executed on a slave computer based upon a status of a communication interface between the master computer and the slave computer.

41. The computer-readable medium recited in claim 40, wherein the heuristic further determines the status of the communication interface between the master computer and the slave computer.

42. The computer-readable medium recited in claim 39, wherein the data structure further comprises a second identifier identifying a second group of the operations as operations that may alternately be executed on a slave computer, such that

the first identifier is employed when a status of communication between the master computer and one or more slave computers is in a first state, and

the second identifier is employed when a status of communication between the master computer and one or more slave computers is in a second state.