Folding for a multi-threaded network processor

• US 20050038964A1
• 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, Wilkinson, Hugh, Hooper, Donald F., Jain, Sanjeev, Wilde, Myles J., Fallon, Michael F.
• Granted Patent: US 7,240,164 B2
• Time in Patent Office: Days
• US Class Current: 711/143
• CPC Class Codes: G06F 12/0804 with main memory updating G06F12/0806 takes precedence
• CPC Class Codes: G06F 12/0842 for multiprocessing or multitasking

Abstract

A mechanism to process units of data associated with a dependent data stream using different threads of execution and a common data structure in memory. Accessing the common data structure in memory for the processing uses a single read operation and a single write operation. The folding of multiple read-modify-write memory operations in such a manner for multiple multi-threaded stages of processing includes controlling a first stage, which operates on the same data unit as a second stage to pass context state information to the second stage for coherency.

Claims

1. A method comprising:

processing units of data associated with a dependent data stream using different threads of execution; and

accessing a common data structure in a memory for the processing, using a single read operation to read the common data structure from the memory for caching and a single write operation to write back a cached version of the common data structure to the memory.

2. The method of claim 1 wherein the different execution threads comprise threads controlled to execute in sequential order, and a first one of the threads to execute performs the single read operation.

3. The method of claim 2 wherein a last one of the threads to execute performs the single write operation.

4. The method of claim 3 wherein the threads execute on a processor coupled to the memory, and accessing the common data structure comprises:

caching the common data structure in a local memory of the processor after the single read operation is complete.

5. The method of claim 4 wherein the processor includes a Content Addressable Memory (CAM) of entries and caching comprises enabling the first one of the threads to write one of the entries with information indicating that the common data structure is cached in the local memory.

6. The method of claim 5 wherein accessing the common data structure comprises enabling any one of the threads to determine from the CAM entries if the common data structure is already cached in the local memory.

7. The method of claim 1 wherein the processor is configured to operate as a data processing pipeline of stages, each comprising a set of the threads, and corresponding threads in the sets of threads processing the same one of the data units in stages.

8. The method of claim 7 wherein the stages comprise a first stage and a second stage, and wherein accessing comprises:

controlling the first stage to provide context state information to the second stage.

9. The method of claim 8 wherein each of the first and second stages comprises a local memory for caching the common data structure and a CAM to manage the caching of the common data structure, and wherein accessing further comprises:

using the context information passed by the first stage to maintain coherency of contents of the CAM in the second stage.

10. The method of claim 9 wherein the context state information comprises a portion of the common data structure.

11. The method of claim 10 wherein the context state information comprises results of the processing of the first stage.

12. The method of claim 7 wherein the single read operation is performed by a first thread to execute in the threads set of a first one of the stages.

13. The method of 7 wherein the single write operation is performed by a last thread to execute in the threads set of a last one of the stages.

14. A method comprising:

processing units of data associated with a dependent data stream using different threads of execution; and

accessing a common data structure in a memory for the processing, using a single read operation to read the common data structure from the memory for caching, and one or more write operations to write back cached-versions of the common data structure to the memory.

15. The method of claim 14 wherein the different execution threads comprise threads controlled to execute in sequential order, and a first one of the threads to execute performs the single read operation.

16. An article comprising:

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

processing units of data associated with a dependent data stream using different threads of execution; and

accessing a common data structure in a memory for the processing, using a single read operation to read the common data structure from the memory for caching and a single write operation to write back a cached version of the common data structure to the memory.

17. The article of claim 16 wherein the different execution threads comprise threads controlled to execute in sequential order, and a first one of the threads to execute performs the single read operation.

18. The article of claim 17 wherein a last one of the threads to execute performs the single write operation.

19. The article of claim 18 wherein the threads execute on a processor coupled to the memory, and accessing the common data structure comprises:

caching the common data structure in a local memory of the processor after the single read operation is complete.

20. The article of claim 19 wherein the processor includes a Content Addressable Memory (CAM) of entries and caching comprises enabling the first one of the threads to write one of the entries with information indicating that the common data structure is cached in the local memory.

21. The article of claim 20 wherein accessing the common data structure comprises enabling any one of the threads to determine from the CAM entries if the common data structure is already cached in the local memory.

22. The article of claim 16 wherein the processor is configured to operate as a data processing pipeline of stages, each comprising a set of the threads, and corresponding threads in the sets of threads processing the same one of the data units in stages.

23. The article of claim 22 wherein the stages comprise a first stage and a second stage, and wherein accessing comprises:

controlling the first stage to provide context state information associated with the same data unit to the second stage.

24. The article of claim 23 wherein each of the first and second stages comprises a local memory for caching the common data structure and a CAM to manage the caching of the common data structure, and wherein accessing further comprises:

using the context information passed by the first stage to maintain coherency of contents of the CAM in the second stage.

25. The article of claim 24 wherein the context state information comprises a portion of the common data structure.

26. The article of claim 24 wherein the context state information comprises results of the processing of the first stage.

27. The article of claim 16 wherein the single read operation is performed by a first thread to execute in the threads set of a first one of the stages.

28. The article of 16 wherein the single write operation is performed by a last thread to execute in the threads set of a last one of the stages.

29. A network processor comprising:

processors to process data associated with a data stream using different execution threads; and

wherein the processors are operable to access at least one common data structure in a memory, for the processing, with read-modify-write operations performed by fewer than all of the different execution threads involved in the processing.

30. The network processor of claim 29, further comprising:

a local memory, in each of the processors, to cache the at least one common data structure, and a CAM, in each of the processors, usable by any of the execution threads to determine caching in the local memory;

wherein the processors are operable to process each data unit in stages, each stage corresponding to a different one of the processors; and

wherein each thread associated with each stage is configurable to pass context state information to a corresponding thread in a next stage for coherency of the CAM in such stage.

31. A system comprising:

a memory system;

a network processor coupled to the memory system, the network processor including processors to process data associated with a data stream using different execution threads; and

wherein the processors are operable to access at least one common data structure in the memory system, for the processing, with read-modify-write operations performed by fewer than all of the different execution threads involved in the processing.

32. The system of claim 31 further comprising:

a local memory, in each of the processors, to cache the at least one common data structure, and a CAM, in each of the processors, usable by any of the execution threads to determine caching in the local memory;

wherein the processors are operable to process each data unit in stages, each stage corresponding to a different one of the processors; and

wherein each thread associated with each stage is configurable to pass context state information to a corresponding thread in a next stage for coherency of the CAM in such stage.