Thread interleaving in a multithreaded embedded processor

Details Thread interleaving in a multithreaded embedded processor Thread interleaving in a multithreaded embedded processor

2008-04-15

2008-04-15

Treat, William M. (Department: 2181)

Electrical computers and digital processing systems: processing

Dynamic instruction dependency checking, monitoring or...

Reducing an impact of a stall or pipeline bubble

C712S214000

Reexamination Certificate

active

10733153

ABSTRACT:
The present invention provides a network multithreaded processor, such as a network processor, including a thread interleaver that implements fine-grained thread decisions to avoid underutilization of instruction execution resources in spite of large communication latencies. In an upper pipeline, an instruction unit determines an instruction fetch sequence responsive to an instruction queue depth on a per thread basis. In a lower pipeline, a thread interleaver determines a thread interleave sequence responsive to thread conditions including thread latency conditions. The thread interleaver selects threads using a two-level round robin arbitration. Thread latency signals are active responsive to thread latencies such as thread stalls, cache misses, and interlocks. During the subsequent one or more clock cycles, the thread is ineligible for arbitration. In one embodiment, other thread conditions affect selection decisions such as local priority, global stalls, and late stalls.

REFERENCES:
patent: 5613114 (1997-03-01), Anderson et al.
patent: 5724586 (1998-03-01), Edler et al.
patent: 5742822 (1998-04-01), Motomura
patent: 5771382 (1998-06-01), Wang et al.
patent: 5799188 (1998-08-01), Manikundalam et al.
patent: 5881277 (1999-03-01), Bondi et al.
patent: 5907702 (1999-05-01), Flynn et al.
patent: 5913049 (1999-06-01), Schiell et al.
patent: 5991792 (1999-11-01), Nageswaran
patent: 6016542 (2000-01-01), Gottlieb et al.
patent: 6073159 (2000-06-01), Emer et al.
patent: 6076157 (2000-06-01), Borkenhagen et al.
patent: 6105051 (2000-08-01), Borkenhagen et al.
patent: 6212544 (2001-04-01), Borkenhagen et al.
patent: 6216220 (2001-04-01), Hwang
patent: 6223208 (2001-04-01), Kiefer et al.
patent: 6256775 (2001-07-01), Flynn
patent: 6272520 (2001-08-01), Sharangpani et al.
patent: 6292888 (2001-09-01), Nemirovsky et al.
patent: 6308261 (2001-10-01), Morris et al.
patent: 6341347 (2002-01-01), Joy et al.
patent: 6353881 (2002-03-01), Chaudhry et al.
patent: 6385715 (2002-05-01), Merchant et al.
patent: 6411982 (2002-06-01), Williams
patent: 6418458 (2002-07-01), Maresco
patent: 6477562 (2002-11-01), Nemirovsky et al.
patent: 6490612 (2002-12-01), Jones et al.
patent: 6507862 (2003-01-01), Joy et al.
patent: 6535905 (2003-03-01), Kalafatis et al.
patent: 6542920 (2003-04-01), Belkin et al.
patent: 6542921 (2003-04-01), Sager
patent: 6542987 (2003-04-01), Fischer et al.
patent: 6556045 (2003-04-01), Cohen
patent: 6567839 (2003-05-01), Borkenhagen et al.
patent: 6584488 (2003-06-01), Brenner et al.
patent: 6594755 (2003-07-01), Nuechterlein et al.
patent: 6785890 (2004-08-01), Kalafatis et al.
patent: 6792446 (2004-09-01), Merchant et al.
patent: 6889319 (2005-05-01), Rodgers et al.
patent: 6931639 (2005-08-01), Eickemeyer
patent: 7013400 (2006-03-01), Kalla et al.
patent: 7051329 (2006-05-01), Boggs et al.
patent: 2001/0032307 (2001-10-01), Rohlman et al.
patent: 2001/0056456 (2001-12-01), Cota-Robles
patent: 2002/0010733 (2002-01-01), Baba et al.
patent: 2002/0062435 (2002-05-01), Nemirovsky et al.
patent: 2002/0087840 (2002-07-01), Kottapalli et al.
patent: 2003/0037228 (2003-02-01), Kelsey et al.
patent: 2003/0154235 (2003-08-01), Sager
patent: 2003/0158885 (2003-08-01), Sager
patent: 2003/0163589 (2003-08-01), Bunce et al.
patent: 2003/0163678 (2003-08-01), Bennett et al.
Regnier et al., ETA: Experience with an Intel/spl reg/Xeon/spl trade/processor as a Packet Processing Engine, Proceedings of the 11th Symposium on High Performance Interconnects, IEEE, Aug. 20-22, 2003, pp. 76-82.
Boothe, B. and Ranade, A. G., “Improved Multithreading Techniques for Hiding Communication Latency in Multiprocessors,” ACM 1992, pp. 214-223.
Gulati, M. and Bagherzadeh, N., “Performance Study of a Multithreaded Superscalar Microprocessor,” 2ndInternational Symposium on High-Performance Computer Architecture, Feb. 1996, 11 pages.
Loikkanen, M. and Bagherzadeh, N., “A Fine-Grain Multithreading Superscalar Architecture,” Proc. 1996 Confer. Parallel Architectures and Compilation Techniques, Oct. 1996, 6 pages.
Tullsen, D. M. et al., “Exploiting Choice: Instruction Fetch and Issue on an Implementable Simultaneous Multithreading Processor,” Proc. Of the 23rdISCA, May 1996, 12 pages.
Tullsen, D. M. et al., “Simultaneous Multithreading: Maximizing On-Chip Parallelism,” Proc. Of the 22ndISCA, Jun. 1995, 12 pages.
Yamamoto, W., “An Analysis of Multistreamed, Superscalar Processor Architectures,” Ph.D. Thesis, U.C. Santa Barbara, Dec. 1995, pp. 1-155.

Affiliated with

Also associated with

Rating

Thread interleaving in a multithreaded embedded processor does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Thread interleaving in a multithreaded embedded processor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Thread interleaving in a multithreaded embedded processor will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3952335