Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1999-07-08
2003-04-01
Donoghue, Larry D (Department: 2154)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C712S228000
Reexamination Certificate
active
06542921
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to the field of multithreaded processing. More specifically, the present invention relates to a method and apparatus for controlling the processing priority between multiple threads in a multithreaded processor.
BACKGROUND OF THE INVENTION
Various multithreaded processor designs have been considered in recent times to further improve the performance of processors, especially to provide for a more effective utilization of various processor resources. By executing multiple threads in parallel, the various processor resources are more fully utilized which in turn enhance the overall performance of the processor. For example, if some of the processor resources are being idle due to a stall condition or other delay associated with the execution of a particular thread, these resources can be utilized to process another thread. A stall condition or other delay in the processing of a particular thread may happen due to a number of events that can occur in the processor pipeline. For instance, a cache miss or a branch misprediction may occur in the execution of an instruction included within a thread that can cause a stall condition or other delay with respect to the execution of that particular thread. Consequently, without multithreading capabilities, various available resources within the processor would have been idle due to a long-latency operation, for example, a memory access operation to retrieve the necessary data from main memory, that is needed to resolve the cache miss condition.
Furthermore, multithreaded programs and applications have become more common due to the support provided for multithreading programming by a number of popular operating systems such as the Windows NT® and UNIX operating systems. Multithreaded applications are particularly attractive in the area of multimedia processing.
Multithreaded processors may generally be classified into two broad categories, fine or coarse designs, based upon the particular thread interleaving or switching scheme employed within the respective processor. In general, fine multithreaded designs support multiple active threads within a processor and typically interleave two different threads on a cycle-by-cycle basis. Coarse multithreaded designs, on the other hand, typically interleave the instructions of different threads on the occurrence of some long-latency event, such as a cache miss. A coarse multithreaded design is discussed in Eickmayer, R., Johnson, R. et al. “Evaluation of Multithreaded Uniprocessors for Commercial Application Environments”,
The
23
rd
Annual International Symposium on Computer Architecture
pp. 203-212, May 1996. The distinctions between fine and coarse designs are further discussed in Laudon, J., Gupta, A. “Architectural and Implementation Tradeoffs in the Design of Multiple-Context Processors”,
Multithreaded Computer Architectures: A Summary of the State of the Art
, edited by R. A. lannuci et al., pp. 167-200, Kluwer Academic Publishers, Norwell, Mass., 1994.
There are some particular issues that arise with respect to the concept of multithreading and multithreaded processor design, especially with respect to the parallel or concurrent execution of instructions. The first issue is generally referred to as a deadlock condition. This condition can occur when each thread needs a resource that is held by another thread in order to proceed and neither thread will release the resource that it has. For example, suppose that thread
1
and thread
2
both need two resources A and B in order to complete their respective execution and make progress. However, suppose that thread
1
has control of resource A and thread
2
has control of resource B and neither thread will release the resource that it has until it gets the other resource to complete its respective execution. In this instance, both threads
1
and
2
will come to a halt because they will not get the resource they need unless there are some interventions to break the deadlock condition. Generally, there are four conditions that co-exist to cause a deadlock situation as described above. These four conditions are mutual exclusion, resource holding, no preemption, and circular wait. In the above example, each of the two threads
1
and
2
mutually excludes the other thread from gaining access to the resource that it is holding. In addition, there is no preemption rule to direct either one of the two threads to give up the resource that it is holding to the other thread. In other words, both of the threads
1
and
2
have equal rights to keep the resource allocated to it. Lastly, both threads
1
and
2
wait for the other resource to be released in a circular manner.
Another similar problem to the deadlock problem is the livelock problem. In general, this problem can arise when two or more threads continuously change their state in response to the changes in the other threads without doing any useful work. This problem generally involves the interleaving of threads in which the threads are not deadlocked but cannot proceed toward completion. This situation can arise when, in the above example, both threads
1
and
2
attempt to release the resource that they are holding but the timing is such that neither of them can gain access to both the resources A and B. This situation is similar to the deadlock situation in that no progress is made by thread
1
or
2
but is different in that neither thread is being blocked by the other thread. Referring to the above example, suppose that both threads
1
and
2
, after some interval of time, release the resource that they are holding and are able to gain access to the other resource that they need. In the above example, suppose that thread
1
has released the resource A and now has access to resource B and that thread
2
has released the resource B and now has access to resource A. Unfortunately, both threads
1
and
2
are back to the same problem that they faced earlier because neither thread has access to both resources A and B. Despite the fact that both threads have done something, i.e., releasing the resource that they held earlier and gaining control to the resource that the other thread was holding, both threads
1
and
2
still cannot make any progress because they still need both resources A and B to proceed any further.
As a result, there exists a need to address the problems of deadlock and livelock in multithreaded processors that are designed to execute multiple threads concurrently.
SUMMARY OF THE INVENTION
The present invention provides a method and apparatus for controlling a processing priority assigned alternately to a first thread and a second thread in a multithreaded processor to prevent deadlock and livelock problems between the first thread and the second thread. In one embodiment, the processing priority is initially assigned to the first thread for a first duration. It is then determined whether the first duration has expired in a given processing cycle. If the first duration has expired, the processing priority is assigned to the second thread for a second duration.
REFERENCES:
patent: 3771138 (1973-11-01), Celtruda et al.
patent: 5357617 (1994-10-01), Davis et al.
patent: 5386561 (1995-01-01), Huynh et al.
patent: 5404469 (1995-04-01), Chung et al.
patent: 5430850 (1995-07-01), Papadopoulos et al.
patent: 5499349 (1996-03-01), Nikhil et al.
patent: 5524263 (1996-06-01), Griffith et al.
patent: 5791522 (1998-08-01), Lee et al.
patent: 5809271 (1998-09-01), Colwell et al.
patent: 5809522 (1998-09-01), Novak et al.
patent: 5892959 (1999-04-01), Fung
patent: 5968160 (1999-10-01), Saito et al.
patent: 5996085 (1999-11-01), Cheong et al.
patent: 5999932 (1999-12-01), Paul
patent: 6052708 (2000-04-01), Flynn et al.
patent: 6052709 (2000-04-01), Paul
patent: 6088788 (2000-07-01), Borkenhagen et al.
patent: 6092175 (2000-07-01), Levy et al.
patent: 6105127 (2000-08-01), Kimura et al.
patent: 6115709 (2000-09-01), Gilmour et al.
patent: 6212544 (2001-04-01), Borkenhagen et al.
patent: 6233599 (2001-05-01), Natio
Blakely , Sokoloff, Taylor & Zafman LLP
Donoghue Larry D
Intel Corporation
LandOfFree
Method and apparatus for controlling the processing priority... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for controlling the processing priority..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for controlling the processing priority... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3101613