Microprocessor systems

• US 20090198969A1
• Filed: 01/31/2008
• Published: 08/06/2009
• Est. Priority Date: 01/31/2008
• Status: Active Grant

• Current Assignee: Arm Norway As (SoftBank Group Corp.)
• Original Assignee: Arm Norway As (SoftBank Group Corp.)
• Inventors: Nystad, Jorn, Heggelund, Frode
• Granted Patent: US 8,719,555 B2
• Time in Patent Office: Days
• US Class Current: 712/216
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862
• CPC Class Codes: G06F 9/3851 from multiple instruction streams, e.g. multistreaming
• CPC Class Codes: G06F 9/3861 Recovery, e.g. branch miss-prediction, exception handling error detection or correction G06F11/00

Abstract

A microprocessor pipeline arrangement 1 includes a plurality of functional units P₁, P₂, P₃, . . . , P_N. A number of the functional units P₁, P₃, P_N have access to a respective cache memory C₁, C₃, C_N from which it can retrieve data needed to process threads that pass through the pipeline. The pipeline arrangement 1 also includes a number of monitors to determine when the system enters a state of livelock (e.g. inter-cache livelocks, intra-cache livelocks and/or “near-livelock” situations): a top-level monitor MT to detect livelock situations in the pipeline as a whole; and second-level (“local”) monitors M₁ and M₃ associated with individual caches C₁ and C₃.

If the system is determined to have entered a livelock state, e.g. by the top-level monitor M_T, the number of threads able to change the contents of one or more of the caches C₁, C₃, C_N is reduced.

Claims

1. A method of operating a microprocessor system that includes a plurality of functional units arranged in a pipelined fashion and in which at least one stage in the pipeline can process a thread for execution at the same time as other stages in the pipeline are processing other threads for execution, one or more of the functional units each including or having associated with it a cache memory for data to be used by the functional unit when processing a thread, the method comprising:

detecting whether the system is in a livelock state; and

if a livelock state is detected, preventing one or more of the threads in the pipeline from being able to change the contents of one or more of the caches.

2. The method of claim 1, wherein said step of detecting whether the system is in a livelock state comprises identifying and/or determining whether a thread has been processed by at least one of the functional units in the pipeline in a predefined or predetermined period.

3. The method of claim 1, wherein said step of detecting whether the system is in a livelock state comprises:

monitoring the progress of threads through the pipeline as a whole so as to determine whether the system is in a livelock state; and

simultaneously, monitoring the progress of threads in one or more particular portions of the pipeline so as to determine whether one or more portions of the system are in a livelock state.

6. The method of claim 1, wherein one or more of the threads have associated with them information indicating whether the thread is able to change the contents of one or more of the caches.

8. The method of claim 1, wherein the one or more threads that are prevented from being able to change the contents of one or more of the caches are prevented from writing to said cache or caches, but are still permitted to read from said cache or caches.

26. A computer program product comprising computer software specifically adapted to carry out the method of claim 1 when installed on a data processor.

4. A method of operating a microprocessor system that includes a plurality of functional units arranged in a pipelined fashion and in which at least one stage in the pipeline can process a thread for execution at the same time as other stages in the pipeline are processing other threads for execution, the method comprising:

monitoring the progress of threads through the pipeline as a whole so as to determine whether the system is in a livelock state; and

simultaneously, monitoring the progress of threads in one or more particular portions of the pipeline so as to determine whether one or more portions of the system are in a livelock state.

5. The method of claim 4, further comprising:

if a livelock state is detected in a particular portion of the pipeline, preventing one of more of the threads from being able to change the contents of a cache or caches associated with the particular portion of the pipeline in which livelock was detected.

7. A method of operating a microprocessor system that includes a plurality of functional units arranged in a pipelined fashion and in which one or more of the functional units can process a thread for execution at the same time as other functional units in the pipeline are processing other threads for execution, one or more of the functional units including or having associated with it a cache for data to be used by the functional unit, the method comprising at least one of:

determining whether a thread is either permitted or prevented from changing the contents of one or more caches; and

changing information associated with one or more of the threads that are passed down the pipeline for execution indicating whether the thread is either permitted or prevented from changing the contents of one or more caches.

9. A method of operating a microprocessor system that includes a plurality of functional units arranged in a pipelined fashion and in which at least one stage in the pipeline can process a thread for execution at the same time as other stages in the pipeline are processing other threads for execution, one or more of the functional units each including or having associated with it a cache memory for data to be used by the functional unit when processing a thread, the method comprising:

detecting whether the system is in a livelock state; and

if a livelock state is detected, reducing the number of threads in the pipeline that are allowed to change the contents of one or more of the caches.

10. The method of claim 9, further comprising:

repeatedly detecting whether the system is in a livelock state.

11. The method of claim 9, further comprising:

progressively decreasing the number of threads able to change the contents of one of more of the caches until it is determined that the system is no longer in a livelock state.

12. The method of claim 9, further comprising:

increasing the number of threads able to change the contents of one or more of the caches once it is determined that the system is no longer in a livelock state.

13. A method of operating a microprocessor system that includes a plurality of functional units arranged in a pipelined fashion and in which at least one stage in the pipeline can process a thread for execution at the same time as other stages in the pipeline are processing other threads for execution, one or more of the functional units each including or having associated with it a cache for data to be used by the functional unit when processing a thread, the method comprising:

selectively decreasing or increasing the number of threads of the threads in the pipeline that are able to change the contents of one or more of the caches.

14. A microprocessor system for processing a plurality of threads, the system comprising:

a plurality of functional units arranged in a pipelined fashion, one or more of the functional units being operable to receive and process a thread received from the preceding functional unit in the pipeline and to pass a thread after processing to the next functional unit in the pipeline, and one or more of the functional units each including or having associated with it a cache memory for data to be used by the functional unit when processing a thread;

at least one livelock monitor for detecting whether the system is in a livelock state; and

progressing logic operable to prevent one or more of the threads in the pipeline from being able to change the contents of one or more of the caches if a livelock state is detected.

15. The microprocessor system of claim 14, wherein said at least one livelock monitor comprises means for identifying and/or determining whether a thread has been processed by at least one of the functional units in the pipeline in a predefined or predetermined period.

16. The microprocessor of claim 14, wherein said at least one livelock monitor comprises:

a first livelock monitor for monitoring the progress of threads through the pipeline as a whole so as to determine whether the system is in a livelock state; and

one or more second livelock monitors for monitoring the progress of threads in a particular portion of the pipeline so as to determine whether one or more portions of the system are in a livelock state.

19. The microprocessor system of claim 14, wherein one or more of the threads have associated with them information indicating whether the thread is able to change the contents of one or more of the caches.

21. The microprocessor system of claim 14, wherein the one or more threads that are prevented from being able to change the contents of one or more of the caches are prevented from writing to said cache or caches, but are still permitted to read from said cache or caches.

17. A microprocessor system comprising:

a plurality of functional units arranged in a pipelined fashion, one or more of the functional units being operable to receive and process a thread received from the preceding functional unit in the pipeline and to pass a thread after processing to the next functional unit in the pipeline;

a first livelock monitor for monitoring the progress of threads through the pipeline as a whole so as to determine whether the system is in a livelock state; and

one or more second livelock monitors for monitoring the progress of threads in a particular portion of the pipeline so as to determine whether one or more portions of the system are in a livelock state.

18. The microprocessor system of claim 17, wherein said one or more second livelock monitors are each included in or associated with one of the functional units.

20. A functional unit for use in a microprocessor system that includes a plurality of functional units arranged in a pipelined fashion and in which one or more of the functional units can process a thread for execution at the same time as other functional units in the pipeline are processing other threads for execution, one or more of the functional units including or having associated with it a cache for data to be used by the functional unit, the functional unit comprising at least one of:

processing logic operable to determine whether a thread is either permitted or prevented from changing the contents of one or more caches; and

processing logic operable to change information associated with one or more of the threads that are passed down the pipeline for execution indicating whether the thread is either permitted or prevented from changing data in one or more of the caches.

22. A microprocessor system for processing a plurality of threads, the system comprising:

a plurality of functional units arranged in a pipelined fashion, one or more of the functional units being operable to receive and process a thread received from the preceding functional unit in the pipeline and to pass a thread after processing to the next functional unit in the pipeline, and one or more of the functional units each including or having associated with it a cache memory for data to be used by the functional unit when processing a thread;

at least one livelock monitor for detecting whether the system is in a livelock state; and

processing logic operable to reduce the number of threads in the pipeline that are allowed to change the contents of one or more of the caches if a livelock state is detected.

23. The microprocessor system of claim 22, further comprising:

processing logic operable to progressively decrease the number of threads able to change the contents of one of more of the caches until it is determined that the system is no longer in a livelock state.

24. The microprocessor system of claim 22, further comprising:

processing logic operable to increase the number of threads able to change the contents of one or more of the caches once it is determined that the system is no longer in a livelock state.

25. A microprocessor system for processing a plurality of threads, the system comprising:

a plurality of functional units arranged in a pipelined fashion, one or more of the functional units being operable to receive and process a thread received from the preceding functional unit in the pipeline and to pass a thread after processing to the next functional unit in the pipeline, and one or more of the functional units each including or having associated with it a cache memory for data to be used by the functional unit when processing a thread;

processing logic operable to decrease the number of threads of the threads in the pipeline that are able to change the contents of one or more of the caches; and

processing logic operable to increase the number of threads of the threads in the pipeline that are able to change the contents of one or more of the caches.