Parallel join operation to support space and time dimensional program execution
First Claim
1. A method for performing a parallel join operation to merge state created during speculative execution into the non-speculative state of a program during space and time dimensional program execution, comprising:
- executing the program using a head thread, the head thread operating on primary versions of memory elements and accessing a primary version of a stack;
executing the program using a speculative thread that speculatively executes program instructions in advance of the head thread while the head thread is executing, the speculative thread operating on space-time dimensioned versions of the memory elements and accessing a speculative version of the stack; and
performing a join operation between the head thread and the speculative thread when the head thread reaches a point in the program where the speculative thread began executing, the join operation involving performing operations in parallel using both the head thread and the speculative thread, the operations including, merging the space-time dimensioned versions of the memory elements into the primary versions of the memory elements so that updates to the space-time dimensioned versions of the memory elements are incorporated into corresponding primary versions of memory elements, and merging the speculative version of the stack into the primary version of the stack.
2 Assignments
0 Petitions
Accused Products
Abstract
One embodiment of the present invention provides a system that supports space and time dimensional program execution by performing a parallel join operation to merge state created during speculative execution into the non-speculative state of a program. The system executes a program using a head thread that operates on primary versions of memory elements and accesses a primary version of a stack. The system also executes the program using a speculative thread that speculatively executes program instructions in advance of the head thread while the head thread is executing. This speculative thread operates on space-time dimensioned versions of the memory elements and accesses a speculative version of the stack. The system performs a join operation between the head thread and the speculative thread when the head thread reaches a point in the program where the speculative thread began executing. This join operation involves using both the head thread and the speculative thread to perform a number of operations in parallel. These operations include merging the space-time dimensioned versions of the memory elements into the primary versions of the memory elements so that updates to the space-time dimensioned versions of the memory elements are incorporated into corresponding primary versions of memory elements. These operations also include merging the speculative version of the stack into the primary version of the stack.
26 Citations
25 Claims
-
1. A method for performing a parallel join operation to merge state created during speculative execution into the non-speculative state of a program during space and time dimensional program execution, comprising:
-
executing the program using a head thread, the head thread operating on primary versions of memory elements and accessing a primary version of a stack;
executing the program using a speculative thread that speculatively executes program instructions in advance of the head thread while the head thread is executing, the speculative thread operating on space-time dimensioned versions of the memory elements and accessing a speculative version of the stack; and
performing a join operation between the head thread and the speculative thread when the head thread reaches a point in the program where the speculative thread began executing, the join operation involving performing operations in parallel using both the head thread and the speculative thread, the operations including, merging the space-time dimensioned versions of the memory elements into the primary versions of the memory elements so that updates to the space-time dimensioned versions of the memory elements are incorporated into corresponding primary versions of memory elements, and merging the speculative version of the stack into the primary version of the stack. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. An apparatus that performs a parallel join operation to merge state created during speculative execution into the non-speculative state of a program during space and time dimensional program execution, comprising:
-
a head thread that executes program instructions, the head thread operating on primary versions of memory elements and accessing a primary version of a stack;
a speculative thread that executes program instructions in advance of the head thread while the head thread is executing, the speculative thread operating on space-time dimensioned versions of the memory elements and accessing a speculative version of the stack;
a join mechanism that performs a join operation between the head thread and the speculative thread when the head thread reaches a point in the program where the speculative thread began executing, the join mechanism being configured to perform operations in parallel using both the head thread and the speculative thread, the operations including, merging the space-time dimensioned versions of the memory elements into the primary versions of the memory elements so that updates to the space-time dimensioned versions of the memory elements are incorporated into corresponding primary versions of memory elements, and merging the speculative version of the stack into the primary version of the stack. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for performing a parallel join operation to merge state created during speculative execution into the non-speculative state of a program during space and time dimensional program execution, the method comprising:
-
executing the program using a head thread, the head thread operating on primary versions of memory elements and accessing a primary version of a stack;
executing the program using a speculative thread that speculatively executes program instructions in advance of the head thread while the head thread is executing, the speculative thread operating on space-time dimensioned versions of the memory elements and accessing a speculative version of the stack; and
performing a join operation between the head thread and the speculative thread when the head thread reaches a point in the program where the speculative thread began executing, the join operation involving performing operations in parallel using both the head thread and the speculative thread, the operations including, merging the space-time dimensioned versions of the memory elements into the primary versions of the memory elements so that updates to the space-time dimensioned versions of the memory elements are incorporated into corresponding primary versions of memory elements, and merging the speculative version of the stack into the primary version of the stack. - View Dependent Claims (23, 24)
-
-
25. An computer system that facilitates a parallel join operation to merge state created during speculative execution into the non-speculative state of a program during space and time dimensional program execution, comprising:
-
a processor;
a memory;
an operating system;
a head thread within the operating system that executes program instructions, the head thread operating on primary versions of memory elements and accessing a primary version of a stack;
a speculative thread within the operating system that executes program instructions in advance of the head thread while the head thread is executing, the speculative thread operating on space-time dimensioned versions of the memory elements and accessing a speculative version of the stack;
a join mechanism within the operating system that performs a join operation between the head thread and the speculative thread when the head thread reaches a point in the program where the speculative thread began executing, the join mechanism being configured to perform operations in parallel using both the head thread and the speculative thread, the operations including, merging the space-time dimensioned versions of the memory elements into the primary versions of the memory elements so that updates to the space-time dimensioned versions of the memory elements are incorporated into corresponding primary versions of memory elements, and merging the speculative version of the stack into the primary version of the stack.
-
Specification