Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1997-02-14
2001-10-16
Follansbee, John A. (Department: 2154)
Electrical computers and digital processing systems: processing
Processing control
Branching
Reexamination Certificate
active
06304961
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Related Application
The present application which is a continuation application of, commonly assigned application Ser. No. 07/938,371 entitled “A Computer System Having a Minimum Latency Cache Which Stores Partially Decoded Instructions, Branch Prediction and Next Fetch Address Prediction Information,” filed Aug. 31, 1992, now abandoned and incorporated in its entirety by reference herein.
2. Field Of Invention
The present invention relates to the field of computer systems. More specifically, the present invention relates to a computer system having a minimum latency cache which stores instructions decoded to determine class, branch prediction and next fetch address prediction information.
BACKGROUND
Historically, when a branch instruction was dispatched in a computer system, instruction fetching and dispatching were stalled until the branch direction and the target address were resolved. Since this approach results in lower system performance, it is rarely used in modern high performance computers. To obtain higher system performance, various techniques have been developed to allow instruction fetching and dispatching to continue in an efficient manner without waiting for the resolution of the branch direction. Central to the efficiency of continuing instruction prefetching and dispatching is the ability to predict the correct branch direction. There are several common approaches to predicting branch direction:
1. Static prediction: Under this approach, the higher probability direction for a particular branch instruction is ascertained. When the branch instruction is fetched, the ascertained direction is always taken. For example, a direction for a branch instruction maybe set to “Branch Taken”, or alternatively, set to “Branch Not Taken”.
2. Dynamic software prediction: Under this approach, a branch prediction algorithm predicts the branch direction.
3. Dynamic hardware prediction: Under this approach, a branch prediction algorithm predicts the branch direction based on the branch history information maintained in a branch prediction table.
The static prediction approach is simple to implement, however, its prediction hit rate is generally less than 75%. Such a prediction hit rate is generally too low for high performance computers. The dynamic software prediction approach generally works quite well when used in conjunction with a compilation technique known as trace scheduling. Without trace scheduling, the prediction hit rate is generally very low. Unfortunately, trace scheduling is difficult to apply to some programs and implementations. The dynamic hardware prediction generally provides an adequate prediction hit rate. However, it increases the complexity of the processor design and requires additional hardware to maintain the separate branch prediction table. Further, if the size of a cache is enlarged in a redesign, the size of the table would also have to be increased, complicating the redesign process.
SUMMARY OF THE INVENTION
The present invention relates to a novel computer system. The computer system includes a low latency cache that stores instructions decoded to determine class, branch prediction information, and next address fetch information.
The present invention includes a cache having a plurality of cache lines. Each cache line includes (n) instructions and (n) instruction class (ICLASS) fields for storing the decoded class information of the instructions respectively. Each cache line also includes one or more branch prediction (BRPD) fields and one or more next fetch address prediction (NFAPD) fields.
When an instruction is fetched, the corresponding ICLASS field, BRPD field information and the NFAPD information are all provided to the prefetch and dispatch unit of the computer system. The ICLASS information informs the prefetch unit if the fetched instruction is a branch. Since the instruction has already been partially decoded, the need to perform a partial decode in the prefetch and dispatch unit to determine if an instruction is a branch instruction is avoided. If the instruction is a branch instruction, the BRPD field provides a prediction of either “Branch Taken” or “Branch Not Taken”. For non-branch instructions, the BRPD field is ignored. For non-branch instructions, the NFAPD typically contains the next sequential address. For branch instructions, the NFAPD contains either the next sequential address or the target address of the branch instruction. If the BRPD field contains a “Branch Taken” prediction, the corresponding NFAPD field typically contains the target address for the branch instruction. Alternatively, if the BRPD field contains a “Branch Not Taken” status, the corresponding NFAPD field typically contains the next sequential address. In any event, the NFAPD information is used to define the next line from the cache to be fetched, thereby avoiding the need to calculate the next fetch address in the prefetch unit. The prefetch and dispatch unit needs to calculate the next fetch address only when a misprediction of a branch instruction occurs. An update policy is used to correct the BRPD and the NFAPD values in the event the predictions turn out to be wrong.
The number of BRPD fields and NFAPD fields per cache line varies depending on the specific embodiment of the present invention. In one embodiment, a specific BRPD field and an NFAPD field is provided for each instruction per cache line. If there is more than one branch instruction per cache line, each branch instruction enjoys the benefit of a dedicated branch prediction and next fetch address prediction. In a simplified embodiment, one BRPD field and one NFAPD field is shared among all the instructions per cache line. Under these circumstances, only a dominant instruction in the cache line makes use of the BRPD and the NFAPD information. A dominant instruction is defined as the first branch instruction with a “Branch Taken” status in the cache line. For example, with a dominant instruction, the BRPD field is set to “Branch Taken”, and the NFAPD typically contains the target address for the dominant branch instruction. When the instruction is fetched, control is typically transferred to the target address of the dominant instruction. Since the dominant instruction is the first instruction in a cache line to cause a control transfer, it is not necessary for the other instructions in the cache line to have their own BRPD fields and NFAPD fields respectively.
The present invention represents a significant improvement over the prior art. The need to perform a partial decode or a next fetch address calculation in the prefetch and dispatch unit is eliminated with a vast majority of the fetched instructions. As such, fetch latency is significantly reduced and processor throughput is greatly enhanced.
REFERENCES:
patent: 4228498 (1980-10-01), Moshier
patent: 4435756 (1984-03-01), Potash
patent: 4437149 (1984-03-01), Pomerene et al.
patent: 4894772 (1990-01-01), Langendorf
patent: 5129067 (1992-07-01), Johnson
patent: 5136697 (1992-08-01), Johnson
patent: 5226130 (1993-07-01), Favor et al.
patent: 5230068 (1993-07-01), Van Dyke et al.
patent: 5265213 (1993-11-01), Weiser et al.
patent: 5367694 (1994-11-01), Ueno
patent: 5381533 (1995-01-01), Peleg et al.
patent: 5481751 (1996-01-01), Alpert et al.
patent: 5832259 (1998-11-01), Stiles
patent: 0381 444 A2 (1990-01-01), None
patent: 0401 992 A2 (1990-05-01), None
“The Hardware Architecture of the CRISP Microprocessor” by Ditzel et al., 1987 ACM.
Manolis G. H. Katevenis, “Reduced Instruction Set Computer Architecture for VLSI”,1984, pp. 150-158, ACM Doctoral Dissertation.
Linley Gwennap, “Desktop Market Will Open--Slowly”, Jan. 24,1994, p. 3, The Editor's View, Microprocessor Report.
Linley Gwennap, “PA-7200 Enables Inexpensive MP Systems”, Mar. 7, 1994, pp. 12-15, Microprocessor Report.
Joy William N.
Tam Kit Sang
Yeung Alfred K. W.
Yung Robert
Finnegan Henderson Farabow Garrett & Dunner L.L.P.
Follansbee John A.
Sun Microsystems Inc.
LandOfFree
Computer system and method for fetching a next instruction does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer system and method for fetching a next instruction, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer system and method for fetching a next instruction will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2582918