THREAD LIVELOCK UNIT

• US 20100229172A1
• Filed: 05/19/2010
• Published: 09/09/2010
• Est. Priority Date: 09/23/2004
• Status: Active Grant

• Current Assignee: David W. Burns, K.S. Venkatraman
• Original Assignee: David W. Burns, K.S. Venkatraman
• Inventors: Venkatraman, K.S., Burns, David W.
• Granted Patent: US 8,276,149 B2
• Time in Patent Office: Days
• US Class Current: 718/100
• CPC Class Codes: G06F 9/38 Concurrent instruction execution, e.g. pipeline or look ahead
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3854 Instruction completion, e.g. retiring, committing or graduating

Abstract

Method, apparatus and system embodiments to assign priority to a thread when the thread is otherwise unable to proceed with instruction retirement. For at least one embodiment, the thread is one of a plurality of active threads in a multiprocessor system that includes memory livelock breaker logic and/or starvation avoidance logic. Other embodiments are also described and claimed.

Claims

1. In a first multi-threaded processor, a method of assigning thread priority among a plurality of threads and a memory livelock unit, comprising:

determining whether a plurality of livelock conditions are present among the memory livelock unit and at least two threads of the processor, the at least two threads including a first thread and a set of remaining threads;

determining, based on satisfaction of said plurality of livelock conditions, whether the first thread is live-locked; and

assigning priority to the first thread and not to any of the set of remaining threads in response to determining the first thread is live-locked.

2. The method of claim 1, further comprising:

determining the first thread has been live-locked for at least a predetermined length of time.

3. The method of claim 1, further comprising:

taking an action to stimulate forward progress of the first thread.

4. The method of claim 3, wherein taking an action further comprises:

issuing a stall to at least one of the remaining threads.

5. The method of claim 3, wherein taking an action further comprises:

invoking a livelock breaker in response to determination of instruction-side starvation.

6. The method of claim 5, further comprises:

evaluating whether a portion of a retirement queue is empty.

7. The method of claim 3, wherein taking an action further comprises:

issuing a priority request to an arbitrator in response to a cache miss.

8. The method of claim 3, wherein taking an action further comprises:

issuing a stall request to a second multi-threaded processor coupled in a system including the first multi-threaded processor.

9. A multicore multithreaded processor comprising:

a plurality of processor cores, each of said plurality of processor cores being a multithreading processor capable of executing a plurality of threads;

a livelock reducer coupled to communicate with each of the plurality of processor cores, said livelock reducer to receive thread progress information about a first thread from a first processor core and to adjust activity of a second thread of a second processor core of said plurality of processor cores in response to the thread progress information about said first thread from the first processor core, wherein the livelock reducer is further to receive subsequent thread progress information about the first thread from the first processor core after adjusting activity of the second thread and to request priority for the first thread in response to the subsequent thread progress information about said first thread.

10. The processor of claim 9, wherein:

said livelock reducer comprises a plurality of livelock circuits, at least one livelock circuit being associated with one of said plurality of processor cores.

11. The multicore multithreaded processor of claim 9 wherein said livelock reducer comprises:

arbitration control logic coupled to said plurality of processor cores, said arbitration control logic to receive thread progress information from said plurality of processor cores and to arbitrate priority to determine which threads should be assisted.

12. The multicore multithreaded processor of claim 9 wherein each processor core comprises:

a thread livelock unit coupled to said core to measure thread livelock indicators; and

a memory livelock unit coupled to said core to measure memory livelock indicators.

13. The multicore multithreaded processor of claim 12, further comprising:

an arbitrator to receive livelock information from the thread livelock unit and said memory livelock unit of each of said plurality of processor cores, said arbiter to prioritize one thread over another in response to said livelock information.