Abstract:
A state machine may have a sequence that is called by multiple threads within the state machine. Prior to calling the sequence, an address specific to the current state is stored in an address register. After the sequence has executed, the address register is queried and the thread may continue. Many different threads may call the sequence. In more complex hardware implemented state machines, the total number of gates may be reduced significantly.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    a. Field of the Invention  
           [0002]    The present invention pertains to computational devices and specifically to programming of state machines.  
           [0003]    b. Description of the Background  
           [0004]    State machines are computational devices that are used for many low-level functions in today&#39;s computers. Many routine, repetitive sequences such as communications handshaking can be quickly and efficiently implemented in a finite state machine. Further, since the state machine can be implemented in hardware, using a series of gates and other hardware devices, the speed and reliability of the state machine can be very high.  
           [0005]    State machines are frequently incorporated into integrated circuit devices. It is common for an integrated circuit to have a state machine plus other circuitry and other functionality. Space on an integrated circuit may be limited so that it may be desirable to make the state machine from the smallest number of gates and thus minimize the space it occupies on the integrated circuit.  
           [0006]    When several state machines are used in conjunction with each other, some handshaking may occur between the state machines as they communicate with each other. The handshaking may cause some latency in operations and may further complicate the overall implementation.  
           [0007]    It would therefore be advantageous to provide a system and method for reducing the number of gates required for large, complex state machines. It would be further advantageous if the functionality of several state machines could be combined so that faster, more efficient operations are achieved.  
         SUMMARY OF THE INVENTION  
         [0008]    The present invention overcomes the disadvantages and limitations of the prior art by providing a system and method for common state sequences in a state machine. A sequence may be invoked by various states in a state machine. An address is stored in an address register prior to calling the sequence. When the sequence is completed, the address register is queried to direct the operation back to the state prior to sequence being executed.  
           [0009]    The present invention may therefore comprise a method of controlling the operation of a finite state machine comprising: providing an address register; providing a common routine, the common routine comprising a plurality of states; executing a first thread of execution, the first thread of execution comprising: storing a first value in the address register; stopping the first thread of execution; executing the common routine; retrieving the first value from the address register; and causing the first thread of execution to continue based on the first value stored in the address register; and, executing a second thread of execution, the second thread of execution comprising: storing a second value in the address register; stopping the second thread of execution; executing the common routine; retrieving the second value from the address register; and causing the second thread of execution to continue based on the second value stored in the address register.  
           [0010]    The present invention may further comprise a method of creating logic for a finite state machine so as to minimize the number of states comprising: providing a first set of executable logic states; providing a second set of executable logic states; determining a subset of executable logic states that are common to the first set of executable logic states and the second set of executable logic states; creating a common set of executable logic states from the subset of executable logic states; creating an address register adapted to contain a pointer; adapting the first set of executable logic states to store a first pointer in the address register prior to executing the common set of executable logic states; adapting the second set of executable logic states to store a second pointer in the address register prior to executing the common set of executable logic states; adapting the common set of executable logic states to retrieve the pointer from the address register; and adapting the common set of executable logic states to continue executing one of the first set or the second set of executable logic states based upon the pointer within the address register.  
           [0011]    The present invention may further comprise an integrated circuit comprising: a first series of gates arranged to perform a first set of actions; an address register; a second series of gates arranged to perform a first thread of actions, the first thread of actions comprising: storing a first value in the address register; stopping the first thread of actions; causing the first series of gates to perform the first set of actions; retrieving the first value from the address register; and causing the first thread of actions to continue based on the first value stored in the address register; and, a third series of gates arranged to perform a second thread of actions, the second thread of actions comprising: storing a second value in the address register; stopping the second thread of actions; causing the first series of gates to perform the first set of actions; retrieving the second value from the address register; and causing the second thread of actions to continue based on the second value stored in the address register.  
           [0012]    The present invention may further comprise an integrated circuit comprising a state machine having a reduced number of gates comprising: a first set of executable logic states; a second set of executable logic states; a subset of executable logic states that are common to the first set of executable logic states and the second set of executable logic states; an address register adapted to contain a pointer; the first set of executable logic states adapted to store a first pointer in the address register prior to executing the subset of executable logic states; the second set of executable logic states adapted to store a second pointer in the address register prior to executing the subset of executable logic states; the subset of executable logic states adapted to retrieve the pointer from the address register; and the subset of executable logic states adapted to continue executing one of the first set or the second set of executable logic states based upon the pointer within the address register.  
           [0013]    The advantages of the present invention are that a complex state machine may have repetitive sequences called by different states in the state machine. This reduces the number of gates required for the state machine because the sequence is not repeated several times. Further, the present invention reduces latency and overhead associated with separate state machines by combining all of the logic into one state machine. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0014]    In the drawings,  
         [0015]    [0015]FIG. 1 is an illustration of an embodiment of the present invention of a shared routine in a state machine.  
         [0016]    [0016]FIG. 2 is a more detailed illustration of an embodiment of the present invention of a shared routine in a state machine.  
         [0017]    [0017]FIG. 3 is an illustration of an embodiment of a pseudo-code representation of the present invention of a shared routine in a state machine.  
         [0018]    [0018]FIG. 4 is an illustration of an embodiment of a method for the implementation of shared subsets of routines in a state machine. 
     
    
     DETAILED DESCRIPTION  
       [0019]    [0019]FIG. 1 illustrates an embodiment  100  of the present invention of a shared routine in a state machine. A common routine  102  may be executed by various threads  104 ,  106 ,  108 , and  110 . The routine  102  may be called by each of the threads and have control returned to the thread after the common routine  102  has completed execution.  
         [0020]    The routine  102  may contain a sequence of states that needs to be executed in different threads of the state machine. For example, a state machine that is designed to handle a particular communications protocol may require a handshaking sequence to be executed by different threads. A thread that receives data may require that a series of handshaking lines to toggle in the same manner as a thread that transmits data. Both threads may call a common routine that performs the toggling sequence.  
         [0021]    The control of the individual thread may be passed to the routine  102  and returned to that particular thread when the routine  102  has completed. A return address is stored prior to calling the routine  102 . When the routine  102  is complete, the return address is used to direct the thread to continue.  
         [0022]    [0022]FIG. 2 illustrates an embodiment  200  of the present invention of a shared routine in a state machine. Two different execution threads  202  and  203  each pause execution, transfer execution control to the common routine  214 , then pass the execution back to the respective thread. The thread  202  executed until state  204  at which the return address  206  is stored into register  212 . The execution thread is passed to the begin state  208  and the set of common steps is executed  214 . At the end of the common routine  214 , the return function  216  refers to the register  212  to obtain an address  218 . The result of the return function  216  is to transfer execution to state  220  based on the address  218 .  
         [0023]    The embodiment  200  allows a common routine  214  to be shared by a plurality of threads  202  and  203 . A unique identifier for each thread  202  and  203  is stored in the address register  212  prior to executing the common routine  214 . When the common routine  214  has completed execution, the value that is stored in the register  212  is used to direct the execution of the state machine back to the appropriate thread.  
         [0024]    In some embodiments where there are only two threads that share a common routine  214 , the register  212  may contain only one bit. In embodiments where more than two threads share a common routine  214 , the register  212  may contain as many bits as necessary to be able to store a unique identifier for each thread. In some cases, an alphanumeric designation may be used while in other cases a binary combination of bits may be used.  
         [0025]    The common routine  214  may be executed in series with states  204  and  220 . In other embodiments, the common routine  214  may be executed in parallel with other states within the thread  202 .  
         [0026]    [0026]FIG. 3 illustrates an embodiment  300  of pseudo-code representation of the present invention of a shared routine in a state machine. A first thread  302  and a second thread  304  each cause a shared routine  306  to be executed. Within the first thread  302 , the return address is stored with the continuation state X 2  in line  308  and control is passed to the shared routine sub 1  in line  310 . State X 2  is continued in line  312 . Similarly, in second thread  304 , the return address is stored with the continuation state Y 2  in line  314  and control is passed to the shared routine sub 1  in line  316 . State Y 2  is continued in line  318 . The shared routine sub 1  is begun in line  320 . When the shared routine sub 1  is completed, the next state is the value stored in the return address in line  322 .  
         [0027]    The embodiment  300  may be a series of instructions that is compiled into a series of gates that are created in an integrated circuit. By using a shared routine  306 , the overall number of gates in the integrated circuit may be reduced, since the functionality of the shared routine  306  would have to have been duplicated for each of the threads  302  and  304 .  
         [0028]    [0028]FIG. 4 illustrates an embodiment  400  of an implementation of shared subsets of routines in a state machine. Executable threads are created for a state machine in block  402 . If a common subset of executable thread is identified in block  404 , an address register for the subset be created in block  406 . A link from the thread to the common subset is created in block  408  and a state in the thread is created to store a unique identifier for that thread into the address register in block  410 . Within the common subset, a state is created to return to the thread based on the unique identifier in block  412 . If another thread is identified in block  414 , the process is repeated for that thread beginning in block  408 . If no more threads are identified in block  414 , another common subset of threads is evaluated in block  404 . If none are found, the process stops in block  416 .  
         [0029]    The embodiment  400  may be executed manually by a programmer or may be an automated process designed to optimize the state machine by minimizing the number of gates required to implement a specific state machine.  
         [0030]    The foregoing description of the invention has been presented for purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise form disclosed, and other modifications and variations may be possible in light of the above teachings. The embodiment was chosen and described in order to best explain the principles of the invention and its practical application to thereby enable others skilled in the art to best utilize the invention in various embodiments and various modifications as are suited to the particular use contemplated. It is intended that the appended claims be construed to include other alternative embodiments of the invention except insofar as limited by the prior art.