Context pipelines

• US 7,181,594 B2
• Filed: 01/25/2002
• Issued: 02/20/2007
• Est. Priority Date: 01/25/2002
• Status: Expired due to Fees

• Current Assignee: Tahoe Research Limited (f/k/a Learndale Limited) (Vector Capital Corporation)
• Original Assignee: Intel Corporation
• Inventors: Bernstein, Debra, Rosenbluth, Mark B., Wolrich, Gilbert, Adiletta, Matthew J., Wilkinson, Hugh M. III
• Primary Examiner(s): Coleman; Eric
• Application Number:
  US10/057,723
• Publication Number:
  US 20030145173A1
• Time in Patent Office: 1,852 Days
• Field of Search: 712/11, 712/228
• US Class Current: 712/11
• CPC Class Codes: G06F 9/30123 according to context, e.g. thread buffers
• CPC Class Codes: G06F 9/462 with multiple register sets

Abstract

A method of parallel hardware-based multithreaded processing is described. The method includes assigning tasks for packet processing to programming engines and establishing pipelines between programming stages, which correspond to the programming engines. The method also includes establishing contexts for the assigned tasks on the programming engines and using a software controlled cache such as a CAM to transfer data between next neighbor registers residing in the programming engines.

Claims

1. A method comprising:

establishing programming stages, each programming stage comprising at least one programming engine; and

at each programming stage,

assigning one or more tasks for processing in the at least one programming engine,

managing parallel processing of multiple tasks, including establishing a context for each of the multiple tasks, in which at least one of the multiple tasks requires execution of multiple instructions,

switching from processing one of the multiple tasks to another of the multiple tasks based on execution of the instructions, and

passing data associated with the multiple tasks to a subsequent programming stage upon completion of the multiple tasks.

2. The method of claim 1 wherein establishing contexts for the assigned tasks comprises providing a software controlled cache.

3. The method of claim 2 wherein the software controlled cache is a content addressable memory (CAM).

4. The method of claim 1, further comprising forming at least one next neighbor register residing in each of the programming engines.

5. The method of claim 4, further comprising establishing a plurality of pipelines, including transferring data from the at least one next neighbor register residing in one of the programming engines to a subsequent next neighbor register residing in an adjacent programming engine.

6. The method of claim 5 wherein the one of the programming engines maintains the currently operating programming stage of the pipeline and the adjacent programming engine maintains a subsequent programming stage of the plurality of pipelines.

7. The method of claim 1, further comprising modifying variables in the assigned tasks utilized in the programming stages by the programming engines.

8. The method of claim 7 wherein the variables are shared variables utilized by the programming engines of the programming stages and include a critical section defining the read-modify-write time of the shared variables.

9. The method of claim 8 further comprising defining a minimum resolution of the programming stage defined by the difference between the critical section of the shared variables and the arrival time of a subsequent packet wherein the critical section is less than the arrival time of the subsequent packet.

10. The method of claim 3 wherein each of the programming engines executes a plurality of contexts simultaneously.

11. The method of claim 10 wherein the plurality of contexts are executed in an order.

12. The method of claim 11 wherein the order includes a read phase and a write-modify phase.

13. The method of claim 12 wherein the CAM includes a plurality of entries for monitoring least recently used variables.

14. The method of claim 13 wherein the read phase includes determining the cache status of a shared variable in the CAM and updating a value for the shared variable if the shared variable is cached in the CAM.

15. The method of claim 13 wherein the read phase executes a read of the shared variable from a local memory in at least one of the plurality of contexts.

16. The method of claim 15 wherein the remaining plurality of contexts hide a latency time of the read by executing other assigned tasks for processing packets.

17. The method of claim 15 wherein the shared variable is cached in the CAM and is available for processing at the modify-write phase in the at least one of the plurality of contexts.

18. The method of claim 1 in which the at least one programming engine executes multiple instructions associated with a first one of the multiple tasks, and switches to a second one of the multiple tasks when an instruction associated with the first one of the multiple tasks comprises a long latency operation.

19. The method of claim 1 in which the at least one programming engine executes multiple instructions associated with a first one of the multiple tasks, and switches to a second one of the multiple tasks when an instruction associated with the first one of the multiple tasks requires access to memory.

20. A processor comprising:

programming engines arranged in programming stages, and at each programming stage, at least one programming engine to perform;

receiving tasks for processing,

managing parallel processing of multiple tasks, including establishing a context for each of the multiple tasks, in which at least one of the multiple tasks requires execution of multiple instructions,

switching from processing one of the multiple tasks to another of the multiple tasks based on execution of the instructions, and

passing data associated with the tasks to a subsequent programming stage upon completion of the tasks.

21. The processor of claim 20 wherein each of the programming engines includes next neighbor registers for transferring data from a next neighbor register residing in a programming engine to a subsequent next neighbor register residing in a subsequent programming engine.

22. The processor of claim 21 wherein each of the programming engines includes a content addressable memory (CAM).

23. The processor of claim 22 wherein the CAM includes a plurality of entries for monitoring least recently used variables.

24. The processor of claim 22, further comprising shared variables utilized by the programming stages of the plurality of programming engines, the shared variables including a critical section defining the read-modify-write time of the shared variables.

25. The processor of claim 24, further comprising a minimum resolution of the programming stage defined by the difference between the critical section of the shared variables and the arrival time of a subsequent packet wherein the critical section is less than the arrival time of the subsequent packet.

26. The processor of claim 22 wherein the plurality of contexts are executed in order, the order including a read phase and a write-modify phase, wherein the read phase includes determining the cache status of a shared variable in the CAM and updating a value for the shared variable if the shared variable is cached in the CAM, and wherein the read phase executes a read of the shared variable from a local memory in at least one of the plurality of contexts.

27. A computer program product stored on a computer readable medium, the program comprising instructions for causing a parallel processor to:

establish programming stages, each programming stage comprising at least one programming engine; and

at each programming stage,

assign tasks for processing in the at least one programming engine;

manage parallel processing of multiple tasks, including establishing a context for each of the multiple tasks, in which at least one of the multiple tasks requires execution of multiple instructions,

switch from processing one of the multiple tasks to another of the multiple tasks based on execution of the instructions, and

pass data associated with the tasks to a subsequent programming stage upon completion of the tasks.

28. The computer program product of claim 27 wherein the instructions for establishing contexts for the assigned tasks comprises providing a software controlled cache.

29. The computer program product of claim 27, further comprising instructions to establish a plurality of pipelines and form at least one next neighbor register residing in each of the programming engines, wherein the instructions to establish the plurality of pipelines include one or more instructions to transfer data from the at least one next neighbor register residing in one of the programming engines to a subsequent next neighbor register residing in an adjacent programming engine.

30. The computer program product of claim 27, further comprising instructions to transfer data from a next neighbor register residing in a programming engine to a subsequent next neighbor register residing in an adjacent programming engine.

31. The computer program product of claim 27, further comprising instructions to utilize shared variables of the programming stages that include a critical section defining the read-modify-write time of the variables.

32. A computer program product stored on a computer readable medium, the program comprising instructions for causing programming engines to:

perform specific tasks for packet processing;

arrange in programming stages, each comprising at least one programming engine; and

for at least one programming engine,

manage parallel processing of multiple tasks, including establish a context for each of the multiple tasks, in which at least one of the multiple tasks requires execution of multiple instructions,

switch from processing one of the multiple tasks to another of the multiple tasks based on execution of the instructions, and

pass data associated with the multiple tasks to a subsequent programming stage.

33. A multiprocessing system comprising:

a plurality of programming engines configured to process data packets, the plurality of programming engines arranged in a plurality of programming stages

wherein at least one programming engine

manages parallel processing of multiple tasks, including establishing a context for each of the multiple tasks, in which at least one of the tasks requires execution of multiple instructions,

switches from processing one task to another task based on execution of the instructions, and

passes data associated with the tasks to a subsequent programming stage upon completion of the tasks.

34. The multiprocessing system of claim 33 wherein each of the plurality of programming engines includes next neighbor registers for transferring data to a subsequent next neighbor register residing in an adjacent programming engine.

35. The multiprocessing system of claim 33, further comprising shared variables utilized by the programming stages of the plurality of programming engines, the shared variables including a critical section defining the read-modify-write time of the shared variables.

36. The multiprocessing system of claim 33 wherein each of the plurality of programming engines includes a content addressable memory (CAM).

37. The multiprocessing system of claim 36 wherein the CAM includes a plurality of entries for monitoring least recently used variables.

38. The multiprocessing system of claim 35 further comprising a minimum resolution of the programming stage defined by the difference between the critical section of the shared variables and the arrival time of a subsequent packet wherein the critical section is less than the arrival time of the subsequent packet.