Phasing for a multi-threaded network processor

• US 20050039182A1
• Filed: 08/14/2003
• Published: 02/17/2005
• Est. Priority Date: 08/14/2003
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wolrich, Gilbert M., Bernstein, Debra, Rosenbluth, Mark, Hooper, Donald F., Jain, Sanjeev, Fallon, Michael F.
• Granted Patent: US 7,441,245 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 2209/5018 Thread allocation
• CPC Class Codes: G06F 9/5038 considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration scheduling strategies G06F9/4881 and subgroups
• CPC Class Codes: H04L 69/12 Protocol engines

Abstract

A method of and apparatus for associating units of data with threads of a multi-threaded processor for processing, and enabling each thread to perform processing for at least two of the data units during a thread execution period. The thread execution period is divided among phases, and each of the data units processed by a thread is processed by a different one of the phases.

Claims

1. A method comprising:

associating units of data with threads of a multi-threaded processor for processing; and

enabling each thread to perform processing for at least two of the data units during a thread execution period.

2. The method of claim 1 wherein the thread execution period is divided among phases, and each of the at least two data units is processed by a different one of the phases.

3. The method of claim 2 wherein the threads execute one at a time in a sequential order.

4. The method of claim 3 wherein the threads are configured to perform a function comprising tasks, and a different one of the tasks is performed by each of phases.

5. The method of claim 4 wherein the tasks comprise at least one dependent memory reference.

6. The method of claim 4 wherein the tasks comprise multiple dependent memory references, each directed to a different memory data structure.

7. The method of claim 4 wherein the function comprises a hierarchical tree search.

8. The method of claim 7 wherein the hierarchical tree search comprises Longest Prefix Matching.

9. The method of claim 1 wherein the data units comprise a sequence of data units, and the at least two data units comprise consecutive data units in the sequence.

10. The method of claim 1 wherein the data units comprise a sequence of data units, and associating comprises associating each data unit with a different one of the threads in order of the sequence.

11. An article comprising:

a storage medium having stored thereon instructions that when executed by a machine result in the following;

associating units of data with threads of a multi-threaded processor for processing; and

enabling each thread to perform processing for at least two of the data units during a thread execution period.

12. The article of claim 11 wherein the thread execution period is divided among phases, and each of the at least two data units is processed by a different one of the phases.

13. The article of claim 12 wherein the threads execute one at a time in a sequential order.

14. The article of claim 13 wherein the threads are configured to perform a function comprising tasks, and a different one of the tasks is performed by each of phases.

15. The article of claim 14 wherein the tasks comprise at least one dependent memory reference.

16. The article of claim 14 wherein the tasks comprise multiple dependent memory references, each directed to a different memory data structure.

17. The article of claim 14 wherein the function comprises a hierarchical tree search.

18. The article of claim 17 wherein the hierarchical tree search comprises Longest Prefix Matching.

19. The article of claim 11 wherein the data units comprise a sequence of data units, and the at least two data units comprise consecutive data units in the sequence.

20. The article of claim 11 wherein the data units comprise a sequence of data units, and associating comprises associating each data unit with a different one of the threads in order of the sequence.

21. A network processing comprising:

an I/O interface to receive units of data from a network device;

one or more multi-threaded processors, coupled to the I/O device, each having multiple threads of execution to process data units received by the I/O device;

wherein each thread on at least one of the multi-threaded processors is enabled to perform processing for at least two of the data units during a thread execution period.

22. The network processor of claim 21 wherein the thread execution period is divided among phases, and each of the at least two data units is processed by a different one of the phases.

23. The network processor of 22 wherein the threads execute one at a time in a sequential order.

24. The network processor of claim 23 wherein the threads are configured to perform a function comprising tasks, and a different one of the tasks is performed by each of phases.

25. The network processor of claim 24 wherein the tasks comprise at least one dependent memory reference.

26. A system comprising:

a network device coupled to a network to receive incoming network traffic;

an I/O interface to receive units of data associated with the incoming network traffic from the network device;

one or more multi-threaded processors, coupled to the I/O device, each having multiple threads of execution to process data units received by the I/O device; and

wherein each thread on at least one of the multi-threaded processors is enabled to perform processing for at least two of the data units during a thread execution period.

27. The system of claim 26 wherein the thread execution period is divided among phases, and each of the at least two data units is processed by a different one of the phases.

28. The system of claim 27 wherein the threads execute one at a time in a sequential order.

29. The system of claim 28 wherein the threads are configured to perform a function comprising tasks including at least one dependent memory reference, and a different one of the tasks is performed by each of phases.