Granted Patent B2

US 7,366,884 · App. 10/082,776 · Granted Apr 29, 2008

Abstract

Claims (42)

1. A context switching system for a multi-thread execution pipeline ioop having a pipeline latency, comprising:

i. A single miss fulfillment first-in-first-out buffer (FIFO);

ii. A context switch requesting subsystem configured to:

(1) Detect a device request from a first thread executing within said multi-thread execution pipeline loop for access to a device having a fulfillment latency exceeding said pipeline latency, and

(2) Generate a context switch request for said first thread; and

iii. A context controller subsystem configured to receive said context switch request and, based thereon, store said first thread in said single miss fulfillment FIFO to prevent said first thread from executing until said device request is fulfilled, said first thread sequencing entirely through said single miss fulfillment FIFO at a rate equivalent to said pipeline latency before exiting therefrom.

2. The context switching system as recited in claim 1 wherein said context controller subsystem is further configured to allow a new thread to enter said multi-thread execution pipeline loop after storing said first thread in said miss fulfillment FIFO.

3. The context switching system as recited in claim 1 wherein said context controller subsystem is further configured to allow other threads within said multi-thread execution pipeline loop to continue to execute while said first thread is waiting for said device request to be fulfilled.

4. The context switching system as recited in claim 1 wherein said context controller subsystem is further configured to:

i. Store said first thread in said miss fulfillment FIFO upon reaching an end position of said multi-thread execution pipeline loop, and

ii. Reinsert said first thread into said multi-thread execution pipeline loop at a beginning position after said first thread exits said miss fulfillment FIFO.

5. The context switching system as recited in claim 1 wherein said first thread is looped back to a beginning stage of said multi-thread execution pipeline loop when said first thread reaches an end stage of said multi-thread execution pipeline loop and said first thread has not finished processing.

6. The context switching system as recited in claim 1 wherein said device request is a request to access external memory due to a cache miss status.

7. For use with a multi-thread execution pipeline loop having a pipeline latency, a method of operating a context switching system, comprising:

i. Detecting a device request from a first thread executing within said multi-thread execution pipeline loop for access to a device having a fulfillment latency exceeding said pipeline latency;

ii. Generating a context switch request for said first thread when said first thread issues said device request; and

iii. Receiving said context switch request and storing said first thread based thereon in a single miss fulfillment first-in-first-out buffer (FIFO) until said device request is fulfilled, said first thread sequencing entirely through said single miss fulfillment FIFO at a rate equivalent to said pipeline latency before exiting therefrom.

8. The method as recited in claim 7 further comprising allowing a new thread to enter said multi-thread execution pipeline loop after storing said first thread in said miss fulfillment FIFO.

9. The method as recited in claim 7 further comprising allowing other threads within said multi-thread execution pipeline loop to continue to execute while said first thread is waiting for said device request to be fulfilled.

10. The method as recited in claim 7 further comprising:

i. Storing said first thread in said miss fulfillment FIFO upon reaching an end position of said multithread execution pipeline loop, and

ii. Reinserting said first thread into said multi-thread execution pipeline loop at a beginning position after said first thread exits said miss fulfillment FIFO.

11. The method as recited in claim 7 further comprising looping said first thread back to a beginning stage of said multi-thread execution pipeline loop when said first thread reaches an end stage of said multi-thread execution pipeline loop and said first thread has not finished processing.

12. The method as recited in claim 7 wherein said device request is a request to access external memory due to a cache miss status.

13. A fast pattern processor that receives and processes protocol data units (PDUs), comprising:

i. A dynamic random access memory (DRAM) that contains instructions;

ii. A memory cache that caches certain of said instructions from said DRAM; and

iii. A tree engine that parses data within said PDUs and employs said DRAM and said memory cache to obtain ones of said instructions, including:

(1) A multi-thread execution pipeline loop having a pipeline latency, and

(2) A context switching system for said multi-thread execution pipeline loop, having:

(a) A single miss fulfillment first-in-first-out buffer (FIFO);

(b) A context switch requesting subsystem that:

(i) Detects a device request from a first thread executing within said multithread execution pipeline loop for access to a device having a fulfillment latency exceeding said pipeline latency, and

(ii) Generates a context switch request for said first thread, and

(3) A context controller subsystem that receives said context switch request and, based thereon, stores said first thread in said single miss fulfillment FIFO until said device request is fulfilled, said first thread sequencing entirely through said single miss fulfillment FIFO at a rate equivalent to having a said pipeline latency before exiting therefrom.

14. The fast pattern processor as recited in claim 13 wherein said context controller subsystem further allows a new thread to enter said multi-thread execution pipeline loop after said first thread is stored in said FIFO.

15. The fast pattern processor as recited in claim 13 wherein said context controller subsystem further allows other threads within said multi-thread execution pipeline loop to continue to execute while said first thread is waiting for said device request to be fulfilled.

16. The fast pattern processor as recited in claim 13 wherein said context switching system is further configured to:

i. Store said first thread in said miss fulfillment FIFO upon reaching an end position of said multithread execution pipeline loop, and

ii. Reinsert said first thread into said multi-thread execution pipeline loop at a beginning position after said first thread exits said miss fulfillment FIFO.

17. The fast pattern processor as recited in claim 13 wherein said first thread is looped back to a beginning stage of said multi-thread execution pipeline loop when said first thread reaches an end stage of said multi-thread execution pipeline loop and said first thread has not finished processing.

18. The fast pattern processor as recited in claim 13 wherein said device is said DRAM and said device request is a request to access said DRAM due to a cache miss status from said memory cache.

Assignments (7)