Virtual machine branching and parallel execution

Abstract

A state branching system is described herein that allows parallel execution of complex state transitions while leveraging time invested to setup a starting state. By allowing branching at the virtual machine level, the state branching system allows setup of a particular condition or state in a virtual machine, then copying and branching to parallel instances of the virtual machine to explore different possible subsequent states. Upon detecting a large state change with unknown outcome, the state branching system instructs the hypervisor to copy the executing virtual machine into one or more separate virtual machines. The system then allows divergent branching between the two or more virtual machines to explore different states from a similar starting point. Once the executions have reached the next state, the system coordinates to determine which copies will continue execution. Thus, the state branching system allows faster exploration of complex state changes.

I/we claim: 
     
         1 . A method for controlling a computer system to exit one or more clone virtual machines and converge execution back to an original virtual machine, wherein the instructions, upon execution, cause a processor to perform actions comprising:
 selecting a first cloned virtual machine created by previously detecting branches of application code in an original virtual machine and spawning multiple cloned virtual machines to execute each branch path;   detecting that the selected cloned virtual machine has completed execution of the branch path to which it was assigned;   identifying a result state of executing the cloned virtual machine;   selecting a branch to take in the original virtual machine based on one or more conditions in the application code running on the original virtual machine;   copying the identified result state from the cloned virtual machine that executed the selected branch; and   continuing execution of the original virtual machine using the copied result from the cloned virtual machine.   
     
     
         2 . The method of  claim 1  further comprising:
 upon a second or subsequent iteration selecting a next cloned machine created by previously detecting branches of application code in the original virtual machine and spawning multiple cloned virtual machines to execute each branch path. 
 
     
     
         3 . The method of  claim 1  wherein the branch path may represent a small subsection of a larger body of code. 
     
     
         4 . The method of  claim 3  wherein the subsection produces results or changes state in a manner that isolates execution of the branch to determine a result outside the larger body of code. 
     
     
         5 . The method of  claim 1  further comprising:
 inserting an instruction or other indication at a point when the first cloned virtual machine will have completed execution of the branch. 
 
     
     
         6 . The method of  claim 1  further comprising:
 monitoring by a hypervisor for the completion of the execution of the branch path. 
 
     
     
         7 . The method of  claim 1  wherein the result state comprises one of numeric results, data produced by the first cloned virtual machine, or state changes to the first cloned virtual machine. 
     
     
         8 . The method of  claim 1  further comprising:
 comparing the first cloned virtual machine with the original virtual machine to identify changes produced by the branch path. 
 
     
     
         9 . The method of  claim 1  wherein the cloned virtual machines operate as speculative execution engines for speculatively executing branch path that the original virtual machine might take. 
     
     
         10 . The method of  claim 1  wherein selecting a branch to take in the original virtual machine further comprises:
 executing the original virtual machine to a point where the one or more conditions have been evaluated; 
 selecting the branch corresponding to one of the multiple cloned machines that matches the evaluated one or more conditions; and 
 discarding any remaining branches. 
 
     
     
         11 . The method of  claim 1  wherein each of the multiple cloned virtual machines represent cumulative results that are used by the original virtual machine. 
     
     
         12 . The method of  claim 11  wherein the results from each of the cloned virtual machines are executed in parallel. 
     
     
         13 . The method of  claim 12  further comprising:
 receiving at the original virtual machine results from each of the cloned virtual machines; and 
 performing additional processing on the received results. 
 
     
     
         14 . The method of  claim 1  wherein the cloned virtual machine provides the result state to the original virtual machine prior to a time the original virtual machine could have obtained the result state on its own. 
     
     
         15 . A computer readable storage device having computer executable instructions for controlling a computer system to exit one or more clone virtual machines and converge execution back to an original virtual machine, wherein the instructions that when executed cause at least one computer having at least on processor to:
 select a first cloned virtual machine created by previously detecting branches of application code in an original virtual machine and spawning multiple cloned virtual machines to execute each branch path;   detect that the selected cloned virtual machine has completed execution of the branch path to which it was assigned;   identify a result state of executing the cloned virtual machine;   select a branch to take in the original virtual machine based on one or more conditions in the application code running on the original virtual machine;   copy the identified result state from the cloned virtual machine that executed the selected branch; and   continue execution of the original virtual machine using the copied result from the cloned virtual machine.   
     
     
         16 . The computer readable storage device of  claim 15  wherein each of the multiple cloned virtual machines is executed in parallel with each other. 
     
     
         17 . The computer readable storage device of  claim 16  wherein at least a portion of the multiple cloned virtual machines provides a corresponding result state to the original virtual machine at a point in time prior to when the original virtual machine could have obtained the corresponding result state. 
     
     
         18 . The computer readable storage device of  claim 15  further comprising instructions to:
 discard branches associated with non-selected cloned virtual machines upon selection of a branch. 
 
     
     
         19 . The computer readable storage device of  claim 15  further comprising instructions to:
 determine if there are additional cloned virtual machines associated with a current branch. 
 
     
     
         20 . A method for controlling a computer system to exit one or more clone virtual machines and converge execution back to an original virtual machine, wherein the instructions, upon execution, cause a processor to perform actions comprising:
 selecting a first cloned virtual machine created by previously detecting branches of application code in an original virtual machine and spawning multiple cloned virtual machines to execute each branch path;   detecting that the selected cloned virtual machine has completed execution of the branch path to which it was assigned;   determining if there are additional cloned virtual machines associated with the branch path;   repeating the steps of selecting and detecting for each additional cloned virtual machine;   identifying a result state of executing each of the cloned virtual machines;   selecting a branch to take in the original virtual machine based on one or more conditions in the application code running on the original virtual machine;   copying the identified result state from the selected cloned virtual machine that executed the selected branch; and   continuing execution of the original virtual machine using the copied result from the cloned virtual machine.