Multi-threaded packet processing engine for stateful packet processing

Abstract

A processing engine to accomplish a multiplicity of tasks has a multiplicity of processing tribes, each tribe comprising a multiplicity of context register sets and a multiplicity of processing resources for concurrent processing of a multiplicity of threads to accomplish the tasks, a memory structure having a multiplicity of memory blocks, each block storing data for processing threads, and an interconnect structure and control system enabling tribe-to-tribe migration of contexts to move threads from tribe-to-tribe. The processing engine is characterized in that individual ones of the tribes have preferential access to individual ones of the multiplicity of memory blocks.

1 . A method implemented by a multi-threaded packet processing engine, comprising: 
 executing a particular thread to process a particular packet, wherein the particular packet is part of a flow, wherein the flow comprises one or more other packets, wherein the other packets are processed by one or more other threads, and wherein the particular packet has a particular seniority relative to the other packets in the flow;    reaching, by the particular thread, a particular stage of execution;    determining whether there are any threads that are processing more senior packets in the flow that have not yet progressed beyond the particular stage of execution; and    in response to a determination that there is at least one thread that is processing a more senior packet in the flow that has not yet progressed beyond the particular stage of execution, stalling execution of the particular thread.    
   
   
       2 . The method of  claim 1 , further comprising: 
 in response to a determination that there is no thread that is processing a more senior packet in the flow that has not yet progressed beyond the particular stage of execution, allowing the particular thread to proceed with entering the particular stage of execution.    
   
   
       3 . The method of  claim 1 , wherein a thread has progressed beyond the particular stage of execution if that thread has entered and exited the particular stage of execution.  
   
   
       4 . The method of  claim 1 , wherein determining whether there are any threads that are processing more senior packets in the flow that have not progressed beyond the particular stage of execution comprises: 
 checking a value of a particular portion of a gateability vector, wherein the particular portion is associated with the particular thread.    
   
   
       5 . The method of  claim 1 , wherein determining whether there are any threads that are processing more senior packets in the flow that have not yet progressed beyond the particular stage of execution comprises: 
 determining whether there are any threads that are processing one or more of the other packets in the flow.    
   
   
       6 . The method of  claim 5 , wherein determining whether there are any threads that are processing more senior packets in the flow that have not yet progressed beyond the particular stage of execution further comprises: 
 in response to a determination that there are one or more threads that are processing one or more of the other packets in the flow, determining whether any of those threads are processing packets in the flow that are more senior than the particular packet.    
   
   
       7 . The method of  claim 6 , wherein determining whether there are any threads that are processing more senior packets in the flow that have not yet progressed beyond the particular stage of execution further comprises: 
 in response to a determination that there are one or more threads that are processing packets in the flow that are more senior than the particular packet, determining whether any of those threads have not yet progressed beyond the particular stage of execution.    
   
   
       8 . The method of  claim 1 , wherein reaching the particular stage of execution comprises: 
 executing a gate instruction that causes the particular thread to determine whether there are any threads that are processing more senior packets in the flow that have not yet progressed beyond the particular stage of execution.    
   
   
       9 . A method implemented by a multi-threaded packet processing engine, comprising: 
 executing a first thread to process a first packet, wherein the first packet is part of a flow, and wherein the first packet has a seniority relative to other packets in the flow;    executing a second thread to process a second packet, wherein the second packet is part of the same flow, and wherein the second packet is less senior than the first packet;    reaching, by the second thread, a particular stage of execution;    determining whether the first thread has progressed beyond the particular stage of execution; and    in response to a determination that the first thread has not yet progressed beyond the particular stage of execution, stalling execution of the second thread.    
   
   
       10 . The method of  claim 9 , wherein determining whether the first thread has progressed beyond the particular stage of execution comprises: 
 determining whether the first thread has entered and exited the particular stage of execution.    
   
   
       11 . The method of  claim 9 , wherein the first packet has a first flow ID, wherein the second packet has a second flow ID which is the same as the first flow ID, and wherein determining whether the first thread has progressed beyond the particular stage of execution comprises: 
 comparing the second flow ID with the first flow ID to determine whether the first and second packets are from the same flow.    
   
   
       12 . The method of  claim 11 , wherein the first packet has a first seniority indicator and the second packet has a second seniority indicator, and wherein determining whether the first thread has progressed beyond the particular stage of execution further comprises: 
 comparing the second seniority indicator with the first seniority indicator to determine whether the first packet is more senior than the second packet.    
   
   
       13 . The method of  claim 12 , wherein the first thread has an associated first execution progress indicator and the second thread has an associated second execution progress indicator, and wherein determining whether the first thread has progressed beyond the particular stage of execution further comprises: 
 processing the first and second execution progress indicators to determine whether the first thread has progressed beyond the particular stage of execution.    
   
   
       14 . The method of  claim 13 , wherein the first thread has a first gate vector register associated therewith, wherein the second thread has a second gate vector associated therewith, wherein the first execution progress indicator is stored in the first gate vector register and the second execution progress indicator is stored in the second gate vector register, and wherein processing the first and second execution progress indicators comprises: 
 accessing the first and second gate vector registers to obtain the first and second execution progress indicators; and    comparing the first and second execution progress indicators.    
   
   
       15 . The method of  claim 9 , wherein determining whether the first thread has progressed beyond the particular stage of execution comprises: 
 checking a value of a particular portion of a gateability vector, wherein the particular portion is associated with the second thread.    
   
   
       16 . The method of  claim 9 , wherein reaching the particular section of instructions comprises: 
 executing a gate instruction that causes the second thread to determine whether the first thread has progressed beyond the particular stage of execution.    
   
   
       17 . The method of  claim 16 , wherein determining whether the first thread has progressed beyond the particular stage of execution comprises: 
 determining whether the first thread has entered and exited the particular stage of execution.    
   
   
       18 . A multi-threaded packet processing engine, comprising: 
 a first set of processing resources for executing a first thread to process a first packet, wherein the first packet is part of a flow, and wherein the first packet has a seniority relative to other packets in the flow; and    a second set of processing resources for executing a second thread to process a second packet, wherein the second packet is part of the same flow, and wherein the second packet is less senior than the first packet, the second set of processing resources comprising an instruction execution mechanism, the instruction execution mechanism executing the second thread until a particular stage of execution is reached, and upon reaching the particular stage of execution, the instruction execution mechanism determining whether the first thread has progressed beyond the particular stage of execution, and in response to a determination that the first thread has not yet progressed beyond the particular stage of execution, the instruction execution mechanism causing execution of the second thread to stall.    
   
   
       19 . The packet processing engine of  claim 18 , wherein the first and second sets of processing resources are separate and distinct.  
   
   
       20 . The packet processing engine of  claim 18 , wherein the instruction execution mechanism executes a gate instruction when it reaches the particular stage of execution, the gate instruction causing the instruction execution mechanism to determine whether the first thread has progressed beyond the particular stage of execution, and to stall execution of the second thread if the first thread has not yet progressed beyond the particular stage of execution.  
   
   
       21 . The packet processing engine of  claim 20 , wherein the gate instruction is a processor-level instruction.  
   
   
       22 . The packet processing engine of  claim 18 , wherein the instruction execution mechanism determines whether the first thread has progressed beyond the particular stage of execution by determining whether the first thread has entered and exited the particular stage of execution.  
   
   
       23 . The packet processing engine of  claim 18 , 
 wherein the first set of processing resources comprises a first ID register for storing a first flow ID associated with the first packet;    wherein the second set of processing resources comprises a second ID register for storing a second flow ID associated with the second packet; and    wherein the instruction execution mechanism determines whether the first thread has progressed beyond the particular stage of execution by, at least, comparing the first and second flow ID's to determine whether the first and second packets are from the same flow.    
   
   
       24 . The packet processing engine of  claim 18 , 
 wherein the first set of processing resources comprises a first ID register for storing a first flow ID associated with the first packet, and a first seniority register for storing a first seniority indicator associated with the first packet;    wherein the second set of processing resources comprises a second ID register for storing a second flow ID associated with the second packet, and a second seniority register for storing a second seniority indicator associated with the second packet; and    wherein the instruction execution mechanism determines whether the first thread has progressed beyond the particular stage of execution by, at least, comparing the first and second flow ID's to determine whether the first and second packets are from the same flow, and comparing the first and second seniority indicators to determine whether the first packet is more senior than the second packet.    
   
   
       25 . The packet processing engine of  claim 18 , 
 wherein the first set of processing resources comprises a first ID register for storing a first flow ID associated with the first packet, a first seniority register for storing a first seniority indicator associated with the first packet, and a first progress register for storing a first execution progress indicator associated with the first thread;    wherein the second set of processing resources comprises a second ID register for storing a second flow ID associated with the second packet, a second seniority register for storing a second seniority indicator associated with the second packet, and a second progress register for storing a second execution progress indicator associated with the second thread; and    wherein the instruction execution mechanism determines whether the first thread has progressed beyond the particular stage of execution by, at least, comparing the first and second flow ID's to determine whether the first and second packets are from the same flow, comparing the first and second seniority indicators to determine whether the first packet is more senior than the second packet, and processing the first and second execution progress indicators to determine whether the first thread has progressed beyond the particular stage of execution.    
   
   
       26 . The packet processing engine of  claim 25 , wherein the first progress register is a first gate vector register, and wherein the second progress register is a second gate vector register.  
   
   
       27 . The packet processing engine of  claim 25 , wherein the first and second ID registers, the first and second seniority registers, and the first and second execution progress registers are dedicated, processor-level registers.  
   
   
       28 . The packet processing engine of  claim 27 , wherein the first and second sets of processing resources are separate and distinct.  
   
   
       29 . The packet processing engine of  claim 18 , wherein the instruction execution mechanism determines whether the first thread has progressed beyond the particular stage of execution by checking a value of a particular portion of a gateability vector, wherein the particular portion is associated with the second thread.  
   
   
       30 . A method implemented by a multi-threaded packet processing engine, comprising: 
 executing a first thread to process a first packet, the first packet having a seniority relative to other packets;    executing a second thread to process a second packet, wherein the second packet is less senior than the first packet;    reaching, by the second thread, a particular stage of execution;    determining whether the first thread has progressed beyond the particular stage of execution; and    in response to a determination that the first thread has not yet progressed beyond the particular stage of execution, stalling execution of the second thread.    
   
   
       31 . The method of  claim 30 , wherein determining whether the first thread has progressed beyond the particular stage of execution comprises: 
 determining whether the first thread has entered and exited the particular stage of execution.    
   
   
       32 . The method of  claim 30 , wherein the first packet has a first seniority indicator and the second packet has a second seniority indicator, and wherein determining whether the first thread has progressed beyond the particular stage of execution comprises: 
 comparing the second seniority indicator with the first seniority indicator to determine whether the first packet is more senior than the second packet.    
   
   
       33 . The method of  claim 32 , wherein the first thread has an associated first execution progress indicator and the second thread has an associated second execution progress indicator, and wherein determining whether the first thread has progressed beyond the particular stage of execution further comprises: 
 processing the first and second execution progress indicators to determine whether the first thread has progressed beyond the particular stage of execution.    
   
   
       34 . The method of  claim 33 , wherein the first thread has a first gate vector register associated therewith, wherein the second thread has a second gate vector associated therewith, wherein the first execution progress indicator is stored in the first gate vector register and the second execution progress indicator is stored in the second gate vector register, and wherein processing the first and second execution progress indicators comprises: 
 accessing the first and second gate vector registers to obtain the first and second execution progress indicators; and    comparing the first and second execution progress indicators.    
   
   
       35 . The method of  claim 30 , wherein determining whether the first thread has progressed beyond the particular stage of execution comprises: 
 checking a value of a particular portion of a gateability vector, wherein the particular portion is associated with the second thread.    
   
   
       36 . The method of  claim 30 , wherein reaching the particular section of instructions comprises: 
 executing a gate instruction that causes the second thread to determine whether the first thread has progressed beyond the particular stage of execution.    
   
   
       37 . The method of  claim 36 , wherein determining whether the first thread has progressed beyond the particular stage of execution comprises: 
 determining whether the first thread has entered and exited the particular stage of execution.    
   
   
       38 . A multi-threaded packet processing engine, comprising: 
 a first set of processing resources for executing a first thread to process a first packet, the first packet having a seniority relative to other packets; and    a second set of processing resources for executing a second thread to process a second packet, wherein the second packet is less senior than the first packet, the second set of processing resources comprising an instruction execution mechanism, the instruction execution mechanism executing the second thread until a particular stage of execution is reached, and upon reaching the particular stage of execution, the instruction execution mechanism determining whether the first thread has progressed beyond the particular stage of execution, and in response to a determination that the first thread has not yet progressed beyond the particular stage of execution, the instruction execution mechanism causing execution of the second thread to stall.    
   
   
       39 . The packet processing engine of  claim 38 , wherein the first and second sets of processing resources are separate and distinct.  
   
   
       40 . The packet processing engine of  claim 38 , wherein the instruction execution mechanism executes a gate instruction when it reaches the particular stage of execution, the gate instruction causing the instruction execution mechanism to determine whether the first thread has progressed beyond the particular stage of execution, and to stall execution of the second thread if the first thread has not yet progressed beyond the particular stage of execution.  
   
   
       41 . The packet processing engine of  claim 40 , wherein the gate instruction is a processor-level instruction.  
   
   
       42 . The packet processing engine of  claim 38 , wherein the instruction execution mechanism determines whether the first thread has progressed beyond the particular stage of execution by determining whether the first thread has entered and exited the particular stage of execution.  
   
   
       43 . The packet processing engine of  claim 38 , 
 wherein the first set of processing resources comprises a first seniority register for storing a first seniority indicator associated with the first packet;    wherein the second set of processing resources comprises a second seniority register for storing a second seniority indicator associated with the second packet; and    wherein the instruction execution mechanism determines whether the first thread has progressed beyond the particular stage of execution by, at least, comparing the first and second seniority indicators to determine whether the first packet is more senior than the second packet.    
   
   
       44 . The packet processing engine of  claim 38 , 
 wherein the first set of processing resources comprises a first seniority register for storing a first seniority indicator associated with the first packet, and a first progress register for storing a first execution progress indicator associated with the first thread;    wherein the second set of processing resources comprises a second seniority register for storing a second seniority indicator associated with the second packet, and a second progress register for storing a second execution progress indicator associated with the second thread; and    wherein the instruction execution mechanism determines whether the first thread has progressed beyond the particular stage of execution by, at least, comparing the first and second seniority indicators to determine whether the first packet is more senior than the second packet, and processing the first and second execution progress indicators to determine whether the first thread has progressed beyond the particular stage of execution.    
   
   
       45 . The packet processing engine of  claim 44 , wherein the first progress register is a first gate vector register, and wherein the second progress register is a second gate vector register.  
   
   
       46 . The packet processing engine of  claim 44 , wherein the first and second ID registers, the first and second seniority registers, and the first and second execution progress registers are dedicated, processor-level registers.  
   
   
       47 . The packet processing engine of  claim 46 , wherein the first and second sets of processing resources are separate and distinct.  
   
   
       48 . The packet processing engine of  claim 38 , wherein the instruction execution mechanism determines whether the first thread has progressed beyond the particular stage of execution by checking a value of a particular portion of a gateability vector, wherein the particular portion is associated with the second thread.