System and method for dynamic ordering in a network processor

• US 20040187112A1
• Filed: 03/07/2003
• Published: 09/23/2004
• Est. Priority Date: 03/07/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Potter, Kenneth H. Jr.
• Granted Patent: US 7,039,914 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system

Abstract

A system and method maintains order among a plurality of threads in a multi-threaded processing system. The processing system, which may be disposed at an intermediate network device, has a plurality of processors each supporting a plurality of threads. The ordering system includes a dispatcher that assigns work, such as the processing of received packets to free threads, an order manager that keeps track of the relative order of the threads, and a thread client associated with each thread for enforcing the determined order. Packets to be processed by the processing system are assigned to an initial order group by the order manager based on a selected attribute, and those packets sharing the same attribute value are assigned to the same order group. During processing, a thread may request reassignment to other order groups in response to other attributes of the packets. The order manager preferably manages the switching of threads among order groups and ensures that the threads within each order group process their packets in order.

Claims

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 the steps of:

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

suspending 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 the step of 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 the step of 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 the step of 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 the step of 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 “

Wait_HOL”

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 an Exchange 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 Release 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 Free_Thread primitive that causes the thread client to make the thread available for work.

14. In an intermediate network node having a plurality of interfaces for sending and receiving network messages within a computer network, a forwarding engine configured to process network messages received at the intermediate network node, the forwarding engine comprising:

a plurality of threads for processing the received network messages;

a dispatcher for assigning at least a portion of the network messages to selected ones of the plurality of threads, wherein the dispatcher associates each network message with an order group;

an order manager in communicating relationship with the plurality of threads for tracking the relative order among threads associated with the same order group; and

a thread client associated with each thread, the thread clients configured to ensure that the threads process their respective network messages according to the threads'"'"' relative order within the order group.

15. The forwarding engine of claim 14 wherein the dispatcher associates all network messages that share an inter-dependency with the same order group.

16. The forwarding engine of claim 15 wherein

the intermediate network node has a plurality of physical interfaces and a plurality of logical interfaces, and

the inter-dependency is one of the physical interface and logical interface on which the network messages are received.

17. The forwarding engine of claim 14 wherein the network messages are one of packets, frames, and cells.

18. The forwarding engine of claim 14 wherein the threads are configured to issue requests to the order manager to change the order group with which the threads are associated as the threads process their respective network messages.

19. The forwarding engine of claim 18 wherein

the order manager tracks which thread is at a head of the relative order;

a given thread is blocked from changing its order group until the given thread reaches the head of its current order group.

20. The forwarding engine of claim 14 wherein

the order manager tracks which thread is at a head of the relative order;

the thread clients suspend the threads from performing at least some processing of the network messages until a thread is at the head of the relative order.

21. The forwarding engine of claim 19 wherein the threads perform at least some processing of the network messages before the threads reach the head of the relative order.

22. The forwarding engine of claim 20 wherein the order manager comprises:

an order group table that is manipulated to indicate which thread is at the head of line for each order group; and

a thread table that specifies where in the relative order each thread is located for its order group.

23. The forwarding engine of claim 22 wherein the order manager manipulates the order group table, as each thread reaches the head of line of its order group and completes its processing of the respective packet, so as to indicate that a next thread in the relative order has reached the head of line of the order group.

24. The forwarding engine of claim 22 wherein

each order group is assigned a group identifier (ID) value;

and

the order manager further comprises a group ID table that maps group ID values to corresponding entries in the order group table for the respective order groups.