Time-multiplexed speculative multi-threading to support single-threaded applications

Abstract

One embodiment of the present invention provides a system that facilitates interleaved execution of a head thread and a speculative thread within a single processor pipeline. The system operates by executing program instructions using the head thread, and by speculatively executing program instructions in advance of the head thread using the speculative thread, wherein the head thread and the speculative thread execute concurrently through time-multiplexed interleaving in the single processor pipeline.

What is claimed is:  
     
         1 . A method for interleaving execution of a head thread and a speculative thread within a single processor pipeline, the method comprising: 
 executing program instructions using the head thread; and    speculatively executing program instructions in advance of the head thread using the speculative thread;    wherein the head thread and the speculative thread execute concurrently through time-multiplexed interleaving in the single processor pipeline.    
     
     
         2 . The method of  claim 1 , wherein the speculative thread includes one or more speculative threads.  
     
     
         3 . The method of  claim 1 , further comprising 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.  
     
     
         4 . The method of  claim 3 , 
 wherein the head thread operates on primary versions of memory elements;    wherein the speculative thread operates on space-time dimensioned versions of the memory elements; and    wherein performing the join operation involves 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.    
     
     
         5 . The method of  claim 4 , wherein if the speculative thread performs a read operation to a memory element, the method further comprises: 
 determining if the space-time dimensioned version of the memory element exists;    if the space-time dimensioned version of the memory element exists, reading the space-time dimensioned version of the memory element;    if the space-time dimensioned version of the memory element does not exist, reading the primary version of the memory element; and    updating status information associated with the memory element to indicate the memory element has been read by the speculative thread.    
     
     
         6 . The method of  claim 4 , wherein if the speculative thread performs a write operation to a memory element, the method further comprises: 
 determining if the space-time dimensioned version of the memory element exists;    if the space-time dimensioned version of the memory element does not exist, creating the space-time dimensioned version of the memory element; and    performing the write operation to the space-time dimensioned version of the memory element.    
     
     
         7 . The method of  claim 4 , wherein if the head thread performs a read operation to a memory element, the method further comprises performing the read operation to the primary version of the memory element.  
     
     
         8 . The method of  claim 4 , wherein if the head thread performs a write operation to a memory element, the method further comprises: 
 performing the write operation to the primary version of the memory element;    checking status information associated with the memory element to determine if the memory element has been read by the speculative thread;    if the memory element has been read by the speculative thread, causing the speculative thread to roll back so that the speculative thread can read a result of the write operation; and    if the memory element has not been read by the speculative thread, performing the write operation to the space-time dimensioned version of the memory element if the space-time dimensioned version exists.    
     
     
         9 . The method of  claim 4 , wherein the memory elements include objects defined within an object-oriented programming system.  
     
     
         10 . The method of  claim 1 , wherein the head thread and the speculative thread access separate hardware register files.  
     
     
         11 . A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for interleaving execution of a head thread and a speculative thread within a single processor pipeline, the method comprising: 
 executing program instructions using the head thread; and    speculatively executing program instructions in advance of the head thread using the speculative thread;    wherein the head thread and the speculative thread execute concurrently through time-multiplexed interleaving in the single processor pipeline.    
     
     
         12 . The computer-readable storage medium of  claim 11 , wherein the speculative thread includes one or more speculative threads.  
     
     
         13 . The computer-readable storage medium of  claim 11 , wherein the method further comprises 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.  
     
     
         14 . The computer-readable storage medium of  claim 13 , 
 wherein the head thread operates on primary versions of memory elements;    wherein the speculative thread operates on space-time dimensioned versions of the memory elements; and    wherein performing the join operation involves 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.    
     
     
         15 . The computer-readable storage medium of  claim 14 , wherein if the speculative thread performs a read operation to a memory element, the method further comprises: 
 determining if the space-time dimensioned version of the memory element exists;    if the space-time dimensioned version of the memory element exists, reading the space-time dimensioned version of the memory element;    if the space-time dimensioned version of the memory element does not exist, reading the primary version of the memory element; and    updating status information associated with the memory element to indicate the memory element has been read by the speculative thread.    
     
     
         16 . The computer-readable storage medium of  claim 14 , wherein if the speculative thread performs a write operation to a memory element, the method further comprises: 
 determining if the space-time dimensioned version of the memory element exists;    if the space-time dimensioned version of the memory element does not exist, creating the space-time dimensioned version of the memory element; and    performing the write operation to the space-time dimensioned version of the memory element.    
     
     
         17 . The computer-readable storage medium of  claim 14 , wherein if the head thread performs a read operation to a memory element, the method further comprises performing the read operation to the primary version of the memory element.  
     
     
         18 . The computer-readable storage medium of  claim 14 , wherein if the head thread performs a write operation to a memory element, the method further comprises: 
 performing the write operation to the primary version of the memory element;    checking status information associated with the memory element to determine if the memory element has been read by the speculative thread;    if the memory element has been read by the speculative thread, causing the speculative thread to roll back so that the speculative thread can read a result of the write operation; and    if the memory element has not been read by the speculative thread, performing the write operation to the space-time dimensioned version of the memory element if the space-time dimensioned version exists.    
     
     
         19 . The computer-readable storage medium of  claim 14 , wherein the memory elements include objects defined within an object-oriented programming system.  
     
     
         20 . The computer-readable storage medium of  claim 11 , wherein the head thread and the speculative thread access separate hardware register files.  
     
     
         21 . An apparatus that supports interleaving execution of a head thread and a speculative thread within a single processor pipeline, the apparatus comprising: 
 a processor;    a processor pipeline within the processor;    an execution mechanism within the processor that is configured to, execute program instructions using the head thread, and to speculatively execute program instructions in advance of the head thread using the speculative thread;    wherein the execution mechanism is configured to concurrently execute the head thread and the speculative thread through time-multiplexed interleaving in the processor pipeline.    
     
     
         22 . The apparatus of  claim 21 , wherein the speculative thread includes one or more speculative threads.  
     
     
         23 . The apparatus of  claim 21 , further comprising a join mechanism configured to perform 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.  
     
     
         24 . The apparatus of  claim 23 , 
 wherein the head thread operates on primary versions of memory elements;    wherein the speculative thread operates on space-time dimensioned versions of the memory elements; and    wherein the join mechanism is configured to merge 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.    
     
     
         25 . The apparatus of  claim 24 , wherein if the speculative thread performs a read operation to a memory element, the execution mechanism is configured to: 
 determine if the space-time dimensioned version of the memory element exists;    if the space-time dimensioned version of the memory element exists, to read the space-time dimensioned version of the memory element;    if the space-time dimensioned version of the memory element does not exist, to read the primary version of the memory element; and to    update status information associated with the memory element to indicate the memory element has been read by the speculative thread.    
     
     
         26 . The apparatus of  claim 24 , wherein if the speculative thread performs a write operation to a memory element, the execution mechanism is configured to: 
 determine if the space-time dimensioned version of the memory element exists;    if the space-time dimensioned version of the memory element does not exist, to create the space-time dimensioned version of the memory element; and to    perform the write operation to the space-time dimensioned version of the memory element.    
     
     
         27 . The apparatus of  claim 24 , wherein if the head thread performs a read operation to a memory element, the execution mechanism is configured to perform the read operation to the primary version of the memory element.  
     
     
         28 . The apparatus of  claim 24 , wherein if the head thread performs a write operation to a memory element, the execution mechanism is configured to: 
 perform the write operation to the primary version of the memory element;    check status information associated with the memory element to determine if the memory element has been read by the speculative thread;    if the memory element has been read by the speculative thread, to cause the speculative thread to roll back so that the speculative thread can read a result of the write operation; and    if the memory element has not been read by the speculative thread, to perform the write operation to the space-time dimensioned version of the memory element if the space-time dimensioned version exists.    
     
     
         29 . The apparatus of  claim 24 , wherein the memory elements include objects defined within an object-oriented programming system.  
     
     
         30 . The apparatus of  claim 21 , wherein the head thread and the speculative thread access separate hardware register files.