Abstract:
Systems, methods, and computer program products for controlling a plurality of pipelined stages are described. In some implementations, an apparatus is described that includes a pipelined data path including a plurality of adjacent stages, where a stage includes a data store, a valid indicator, and a transfer controller including a state machine having a plurality of states. In some implementations, the stage is configured to send a status indicator different from the valid indicator to the state machine to indicate whether new data is available for processing by the stage in a next cycle, and whether a new data transfer is desired in the next cycle between the stage and the adjacent stage.

Description:
BACKGROUND 
     Pipelining is one technique used to make processors operate faster. Pipelining entails separating instruction and/or data paths into a number of stages. Pipelining enables data in different pipe stages to be operated on simultaneously. 
     A data path may be pipelined by adding a set of registers between each pair of pipe stages. Computational logic in the stage may operate on data in an adjacent register. Pipelining the data path may increase the speed at which results exit of the data path. Costs associated with pipelining include increased area for the registers and added latency corresponding to the number of clock cycles needed to initially fill (or prime) the pipeline, e.g., n clock stages in a pipeline with n stages. However, once the pipeline is filled, results may be issued nearly every clock cycle. 
     In certain pipelined data paths the number of cycles needed to process data in the stage may vary between stages, i.e., asynchronously. To prevent data from a stage from being written over valid data still being processed in the next stage, many processors including asynchronous pipelined data paths implement a handshake protocol between stages. In order for data to be moved up the pipe from one stage to the next stage, the two stages must agree that both are ready for the transfer. However, such handshake protocols require at least a clock cycle to complete, which introduces additional latency to the system. 
     SUMMARY 
     An asynchronous pipelined data path, e.g., in a switch, may include a state machine in each stage to control transfers of data into and out of that stage. The state machine may change states, and consequently initiate data transfers into and out of the stage, without sending or receiving requests or acknowledgments for the data transfer or any indication of the states of the state machines in other stages. 
     Each stage may include a data store to store data, a valid indicator to indicate whether the data in the data store in invalid or valid, and a transfer controller to control the transfer of data into and out of the data store. The transfer controller may include the state machine, which may control the stage to load data from a previous stage into the data store in response to one state transition and control the stage to transfer data out of the data store in response to another state transition. The pipelined data path may include control logic which may provide control signals to the stage. The stage may use the control signals to generate status signals for input to the state machine. The status signals may include the valid indicator and an indication whether a new calculation should start in the next cycle. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1A  is a block diagram of a pipelined data path according to an embodiment. 
         FIG. 1B  is a block diagram of a switch including a pipelined data path. 
         FIG. 2  is a block diagram of a pipe stage in the pipelined data path. 
         FIG. 3  is a state transition diagram for a state machine in a pipe stage. 
         FIG. 4  is a flowchart describing a data transfer out of a pipe stage. 
         FIG. 5  is a flowchart describing a data transfer into a pipe stage. 
         FIG. 6  is a flowchart describing a valid bit value transition in a pipe stage. 
         FIG. 7  is a timing diagram illustrating data transfers in a pipe stage. 
         FIG. 8  is a flowchart describing how data moves in the pipeline. 
         FIGS. 9A and 9B  illustrate an exemplary data transfer in the pipelined data path. 
         FIGS. 10A and 10B  illustrate another exemplary data transfer in the pipelined data path. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1A  shows a pipelined data path  102  including n stages  103 . Each stage includes a data store  104 , e.g., a register. The data may be operated on by stage logic  106  before being transferred to the next stage. The pipelined data path may be used in, e.g., a switch  150 , as shown in  FIG. 1B . Packets received in ports  152  may be buffered in packet buffers  154  and then sent to the pipelined data path  102  by an arbitration unit  156 . The packets may be subjected to different processing steps, e.g., policing, bridging, etc., in the different stages  103  before or after being switched by the switch fabric  158 . 
     Data in a stage may be valid or invalid. Valid data is data that is properly in the stage, e.g., (1) the data is still being processed or (2) the data is finished being processed and has not yet been transferred to the next pipe stage. A stage may contain invalid data when valid data in that stage is transferred to the next stage and no new valid data is transferred into the stage. 
     The number of cycles needed to process data may vary between stages, i.e., asynchronously. To prevent data from a stage from being written over valid data still being processed in the next stage, many processors including asynchronous pipelined data paths implement a handshake protocol between stages. In order for data to be moved up the pipe from a stage to the next stage, the two stages must agree that both are ready for the transfer. Typically such handshake protocols require a stage ready to receive data to send a request to the previous stage and send an acknowledgment after receiving the data. However, such handshake protocols require at least a clock cycle to complete, which introduces additional latency to the system. 
     In an embodiment, each stage may include a state machine  108  that controls data transfers into and out of the stage. Each stage may also include a valid bit store  110 , e.g., a flip flop. The valid bit store may be used to store a valid bit that indicates whether the data in the stage is valid or invalid. For example, valid data may be represented by a bit with a HIGH (“1”) value, and invalid data may be represented by a bit with a LOW (“0”) value. 
     The state machine  108  can transition between states based on control signals from control logic  112  and signals from the stage itself, as shown in  FIG. 2 . Each stage can provide two types of information about itself: (1) whether the data in the stage is valid, indicated by the valid bit value; and (2) whether a new calculation should start in the next cycle, indicated by the “next_start” signal. The next_start signal is used so that the state machine does not have to communicate with other stages. Instead, the stage itself informs the state machine that in the next cycle there will be new data and a new process should begin. 
     The control logic  112  provides control signals to the state machine  108  in a stage based on control information provided by the stage logic  106  in the stage and other stages in the pipeline. The “stage_done” control signal indicates that the data in the stage has been completely processed or is in the last processing cycle. The “pipe_rdy” control signal indicates whether there is an invalid stage above this stage in the pipeline (also referred to as “downstream” in the pipeline) and whether all stages between the current stage and the invalid stage are valid and finished processing. The “prev_done” control signal indicates whether the previous stage is done processing. The “valid_in” control signal indicates whether the previous stage contains valid data. 
       FIG. 3  is a state transition diagram  300  for the state machine  108 . The state machine may have two states: an “EMPTY” state  302  and a “FULL” state  304 . In the EMPTY state  302 , the stage is empty or contains invalid data. In the FULL state  304 , the stage contains valid data. The state machine may transition between these states in response to two state transitions: an outgoing transfer (“out_trans”) state transition and an incoming transfer (“in_trans”) state transition. The state machine controls the stage to output the data to the next stage in response to an out_trans state transition. The state machine controls the stage to load data from the previous stage into the data store  104 , overwriting the current data in the data store, in response to an in_trans state transition. The state machine may have an in_trans and an out_trans in the same cycle, e.g., when the pipe is moving and data is loaded into and output from the stage in the same cycle. 
     In an embodiment, the state machines of different pipe stages do not communicate with each other. Rather than have a handshake protocol established between stages to determine if it is safe to transfer data into a next stage, it is assumed from the control signals whether it is time to transfer data. Accordingly, there are no requests for acknowledgments for data transfers transmitted between stages in the pipeline. For example, it is assumed that if the state machine in one stage has an out_trans, the state machine in the next will have an in_trans in the same cycle. There is no need to check if the next or previous stage is in the right state or state transition for a transfer of data into or out of the stage as this is indicated by the control signals. In this manner, the latency usually associated with such handshake protocols may be reduced or eliminated. 
       FIG. 4  is a flowchart describing the triggering of an out_trans state transition  400  and consequent transfer of data out of the stage and into the next stage. The state machine will have an out_trans state transition if the following three conditions are met: (1) there is valid data in the stage  402  (indicated by the valid bit value); (2) this stage is done processing the data  404  (indicated by the stage_done control signal); and (3) the pipe is ready for the move 406 (indicated by the pipe_rdy control signal). 
       FIG. 5  is a flowchart describing the triggering of an in_trans state transition  500  of the state machine and consequent loading of data from the previous stage into the current stage. The state machine will transition to an in_trans state if the previous stage has valid data  502  (indicated by the valid_in signal), the previous stage is finished processing the data  504  (indicated by the prev_done control signal), and one of the following two conditions are met: (1) there is an out_trans in this stage this cycle  506 ; or (2) the data in this stage is invalid  508  (indicated by the valid bit value). 
     The valid bit store  110  holds the valid bit, which may change in response to different events.  FIG. 6  is a flowchart describing transitions of the valid bit value. The valid bit is asserted  602  (indicating valid data) if there is an in_trans in the cycle, since it is assumed that only valid data is loaded into the stage. The valid bit is de-asserted  606  (indicating invalid data) when there is an out_trans and no in_trans  608 . This is because the stage is done with this data and it has been passed down the pipe, and therefore is no longer valid for this stage. The value of the valid bit is unchanged if there is no in_trans or out_trans in a cycle. 
       FIG. 7  is a timing diagram  700  illustrating the timing sequence for an incoming transfer and an outgoing transfer. An incoming transfer occurs at time t 1    702  because the valid_in, prev_done, and next_start control signals are asserted, indicating that the data coming in is valid, the previous stage is done processing the data, and the stage is ready to start a new calculation. An outgoing transfer occurs at time t 2    704  because the valid_out and pipe_rdy control signals are asserted, indicating that the data in the stage is valid, the data in the next stage is invalid, and all stages up to this stage are done. 
       FIG. 8  is a flowchart describing how data moves in the pipeline. When control logic identifies an invalid stage down stream in the pipeline from the current stage (i.e., the first invalid stage from the current stage) (block  800 ), the control logic determines if the data in the current stage is current (block  802 ). If not, the pipe is not ready to move (block  804 ). Control logic also determines if the current stage is finished processing (block  806 ). In addition, control logic determines whether the stage(s) between the current stage and the invalid stage are done processing (block  808 ). If these conditions are not met, the pipe is not ready to move (block  804 ). However, if all of these conditions are met, the pipe is ready to move (block  810 ). 
       FIGS. 9A and 9B  illustrate an example of how data moves down the pipe. For example, as shown in  FIG. 9A , stages 0, 1, and 2 in a five-stage pipe  900  contain valid data (“V”) and are done processing. The data in stage 4 is also valid, but the stage is still processing the data. The data in stage 3 is invalid (“I”). As shown by the arrows in  FIG. 9A , the valid data in stages 0, 1, and 2 can move forward for processing in stages 1, 2, and 3, respectively, and new data can be loaded into stage 0. The valid data in stage 4 does not have to be moved and may continue to be processed. As shown in  FIG. 9B , in the next cycle all five stages contain valid data. 
       FIGS. 10A and 10B  illustrate another example of how data moves down the pipe. For example, as shown in  FIG. 10A , stages 0, 2, and 4 in the five-stage pipe  800  contain valid data and are done processing. The data in stages 1 and 3 is invalid. As shown by the arrows in  FIG. 10A , the valid data in stages 0 and 2 can move forward for processing in stages 1 and 3, respectively, and new data can be loaded into stage 0. The valid data in stage 4 can exit the data path.  FIG. 10B  shows the status of the pipe stages in the next cycle. In this case, both stage 2 and stage 4 now contain invalid data because they experienced an outgoing transition without an incoming transition to replace the valid data that was transferred out of the respective stage. 
     A number of embodiments have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. For example, blocks in the flowcharts may be skipped or performed out of order and still produce desirable results. Accordingly, other embodiments are within the scope of the following claims.