System and method for dynamic ordering in a network processor

Abstract

In one embodiment a set of threads are assigned in a particular order to an order group. The first assigned thread is treated as being, at least initially, at a head-of-line (HOL) for the order group. Each thread of the set is assigned a separate sequence number, each sequence number indicating the order in which the respective thread was assigned to the order group. A given thread is prevented from performing at least some of the given thread's instruction sequence until the given thread reaches the HOL of the order group as indicated by a modifiable HOL sequence value.

1. A method for maintaining order among a plurality of threads disposed at one or more processors, each thread executing an instruction sequence, the method comprising:
 assigning, in a particular order, a set of threads to an order group; 
 treating the first assigned thread as being, at least initially, at a head-of-line (HOL) for the order group; 
 assigning a separate sequence number to each thread of the set, each sequence number indicating the order in which the respective thread was assigned to the order group; 
 providing a modifiable current HOL sequence value that specifies which sequence number is currently at the HOL of the order group; and 
 preventing a given thread of the set from performing at least some of the given thread's instruction sequence until the given thread reaches the HOL of the order group as indicated by the modifiable HOL sequence value. 
 
   
   
     2. The method of  claim 1  further comprising modifying the HOL sequence value, when the thread currently at the HOL of the order group completes its instruction sequence, so as to indicate the next thread in the particular order. 
   
   
     3. The method of  claim 1  wherein the one or more processors are disposed at an intermediate network node of a computer network and the threads are configured to process network messages traversing the computer network. 
   
   
     4. The method of  claim 3  wherein the set of threads assigned to the order group are each processing network messages that all share a common attribute. 
   
   
     5. The method of  claim 4  wherein
 the intermediate network node has a plurality of interfaces for sending and receiving network messages, and 
 a first common attribute corresponds to the interface on which a set of network messages are received. 
 
   
   
     6. The method of  claim 1  further comprising permitting one or more threads of the set to perform at least some of their respective instruction sequences before the one or more threads reach the HOL. 
   
   
     7. The method of  claim 1  further comprising the step of switching a selected thread from a first order group to a second order group. 
   
   
     8. The method of  claim 7  wherein the selected thread must be at the HOL for the first order group in order to be switched to the second order group. 
   
   
     9. The method of  claim 8  further comprising assigning the selected thread a new sequence number based on the order in which the selected thread was switched to the second order group. 
   
   
     10. The method of  claim 1  further comprising providing a thread client for each thread, wherein
 each thread communicates with its thread client through one or more primitives issued by the thread to the respective thread client, and 
 the primitives include a first primitive that causes the thread client to suspend the thread pending the thread reaching the HOL for its order group. 
 
   
   
     11. The method of  claim 10  wherein the primitives further include a second primitive that causes the thread client either to suspend the thread if the thread is not at the HOL for its order group or to switch the thread from a first order group to a second order group if the thread is at the HOL for its order group. 
   
   
     12. The method of  claim 10  wherein the primitives further include a third primitive that causes the thread client either (1) to suspend the thread if the thread is not at one of the HOL or near the HOL for its order group or (2) to have the thread removed from its order group if the thread is at the HOL or near HOL for its order group. 
   
   
     13. The method of  claim 10  wherein the primitives further include a fourth primitive that causes the thread client to make the thread available for work. 
   
   
     14. A forwarding engine, comprising:
 one or more processors; 
 a plurality of threads disposed at the one or more processors, each thread configured to execute an instruction sequence; 
 a dispatcher configured to assign, in a particular order, a set of threads to an order group; 
 an order manager in communicating relationship with the plurality of threads, the order manager configured to
 i) treat the first assigned thread as being, at least initially, at a head-of-line (HOL) for the order group, 
 ii) assign a separate sequence number to each thread of the set, each sequence number indicating the order in which the respective thread was assigned to the order group, and 
 iii) provide a modifiable current HOL sequence value that specifies which sequence number is currently at the HOL of the order group; and 
 
 a thread client associated with each thread, the thread clients configured to prevent a given thread of the set from performing at least some of the given thread's instruction sequence until the given thread reaches the HOL of the order group as indicated by the modifiable HOL sequence value. 
 
   
   
     15. The forwarding engine of  claim 14  wherein the order manager is further configured to modify the HOL sequence value when the thread currently at the HOL of the order group completes its instruction sequence, so as to indicate the next thread in the particular order. 
   
   
     16. The forwarding engine of  claim 14  wherein the forwarding engine is disposed at an intermediate network node of a computer network and the threads are configured to process network messages traversing the computer network. 
   
   
     17. The forwarding engine of  claim 16  wherein the set of threads assigned to the order group are each configured to process network messages that all share a common attribute. 
   
   
     18. The forwarding engine of  claim 17  further comprising a plurality of interfaces for sending and receiving network messages, wherein a first common attribute corresponds to the interface on which a set of network messages are received. 
   
   
     19. The forwarding engine of  claim 14  wherein the thread clients are further configured to permit one or more threads of the set to perform at least some of their respective instruction sequences before the one or more threads reach the HOL. 
   
   
     20. The forwarding engine of  claim 14  wherein the dispatcher is further configured to switch a selected thread from a first order group to a second order group. 
   
   
     21. The forwarding engine of  claim 20  wherein the selected thread must be at the HOL for the first order group in order to be switched to the second order group. 
   
   
     22. The forwarding engine of  claim 21  wherein the order manager is further configured to assign the selected thread a new sequence number based on the order in which the selected thread was switched to the second order group. 
   
   
     23. The forwarding engine of  claim 14  wherein each thread is configured to communicate with its thread client through one or more primitives issued by the thread to the respective thread client, and the primitives include a first primitive configure to cause the thread client to suspend the thread pending the thread reaching the HOL for its order group. 
   
   
     24. The forwarding engine of  claim 23  wherein the primitives further include a second primitive configured to cause the thread client either to suspend the thread if the thread is not at the HOL for its order group, or to switch the thread from a first order group to a second order group if the thread is at the HOL for its order group. 
   
   
     25. The forwarding engine of  claim 23  wherein the primitives further include a third primitive configured to cause the thread client either (1) to suspend the thread if the thread is not at one of the HOL or near the HOL for its order group or (2) to have the thread removed from its order group if the thread is at the HOL or near HOL for its order group. 
   
   
     26. The forwarding engine of  claim 23  wherein the primitives further include a fourth primitive configured to cause the thread client to make the thread available for work. 
   
   
     27. An apparatus, comprising:
 one or more processors; 
 a plurality of threads disposed at the one or more processors, each thread configured to execute an instruction sequence; 
 means for assigning, in a particular order, a set of threads to an order group; 
 means for treating the first assigned thread as being, at least initially, at a head-of-line (HOL) for the order group; 
 means for assigning a separate sequence number to each thread of the set, each sequence number indicating the order in which the respective thread was assigned to the order group; 
 means for providing a modifiable current HOL sequence value that specifies which sequence number is currently at the HOL of the order group; and 
 means for preventing a given thread of the set from performing at least some of the given thread's instruction sequence until the given thread reaches the HOL of the order group as indicated by the modifiable HOL sequence value. 
 
   
   
     28. The apparatus of  claim 27  further comprising means for modifying the HOL sequence value, when the thread currently at the HOL of the order group completes its instruction sequence, so as to indicate the next thread in the particular order. 
   
   
     29. The apparatus of  claim 27  wherein the apparatus is an intermediate network node of a computer network and the threads are configured to process network messages traversing the computer network. 
   
   
     30. The apparatus of  claim 29  wherein the set of threads assigned to the order group are each configured to process network messages that all share a common attribute. 
   
   
     31. The apparatus of  claim 30  further comprising a plurality of interfaces for sending and receiving network messages, wherein a first common attribute corresponds to the interface on which a set of network messages are received. 
   
   
     32. The apparatus of  claim 27  further comprising means for permitting one or more threads of the set to perform at least some of their respective instruction sequences before the one or more threads reach the HOL. 
   
   
     33. The apparatus of  claim 27  further comprising means for switching a selected thread from a first order group to a second order group. 
   
   
     34. The apparatus of  claim 33  wherein the selected thread must be at the HOL for the first order group in order to be switched to the second order group. 
   
   
     35. The apparatus of  claim 34  further comprising means for assigning the selected thread a new sequence number based on the order in which the selected thread was switched to the second order group. 
   
   
     36. The apparatus of  claim 27  wherein each thread is configured to communicate with its thread client through one or more primitives issued by the thread to the respective thread client, and the primitives include a first primitive configured to cause the thread client to suspend the thread pending the thread reaching the HOL for its order group. 
   
   
     37. The apparatus of  claim 36  wherein the primitives further include a second primitive configured to cause the thread client either to suspend the thread if the thread is not at the HOL for its order group, or to switch the thread from a first order group to a second order group if the thread is at the HOL for its order group. 
   
   
     38. The apparatus of  claim 36  wherein the primitives further include a third primitive configured to cause the thread client either (1) to suspend the thread if the thread is not at one of the HOL or near the HOL for its order group or (2) to have the thread removed from its order group if the thread is at the HOL or near HOL for its order group. 
   
   
     39. The apparatus of  claim 36  wherein the primitives further include a fourth primitive configured to cause the thread client to make the thread available for work. 
   
   
     40. A method for maintaining order among a plurality of threads disposed at one or more processors, each thread executing an instruction sequence, the method comprising:
 assigning, in a particular order, a set of threads to an order group; 
 treating the first assigned thread as being, at least initially, at a head-of-line (HOL) for the order group; 
 assigning a separate sequence number to each thread of the set, each sequence number indicating the order in which the respective thread was assigned to the order group; 
 preventing a given thread of the set from performing at least some of the given thread's instruction sequence until the given thread reaches the HOL of the order group as indicated by a modifiable HOL sequence value; and 
 permitting the given thread of the set of threads to perform the at least some of the instruction sequence when the given thread reaches the HOL of the order group. 
 
   
   
     41. The method of  claim 40  further comprising:
 permitting the given thread of the set of threads to perform a portion of the instruction sequence that does not include the at least some of the instruction sequence before the given thread reaches the HOL of the order group. 
 
   
   
     42. An apparatus comprising:
 a dispatcher configured to assign, in a particular order, a set of threads to an order group; 
 an order manager configured to treat the first assigned thread as being, at least initially, at a head-of-line (HOL) for the order group and to assign a separate sequence number to each thread of the set, each sequence number indicating the order in which the respective thread was assigned to the order group; and 
 a thread client configured to prevent a given thread of the set of threads from performing at least some of an instruction sequence, until the given thread reaches the HOL of the order group, the thread client further configured to permit the given thread of the set of threads to perform the at least some of the instruction sequence when the given thread reaches the HOL of the order group. 
 
   
   
     43. The apparatus of  claim 42  wherein the order manager is further configured to compare the sequence number of at least one of the threads of the set of threads to a HOL sequence value to determine if the thread is at the HOL of the order group. 
   
   
     44. The apparatus of  claim 43  wherein the order manager is further configured to modify the HOL sequence value when the thread currently at the HOL completes its instruction sequence, to indicate another thread is at the HOL. 
   
   
     45. The apparatus of  claim 42  wherein the order manager is further configured to permit the given thread of the set of threads to perform a portion of the instruction sequence that does not include the at least some of the instruction sequence before the given thread reaches the HOL of the order group.