Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-08-06
2001-05-29
Follansbee, John A. (Department: 2783)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S206000
Reexamination Certificate
active
06240510
ABSTRACT:
BACKGROUND OF THE INVENTION
Technical Field
This invention relates to microprocessors, and in particular to systems for processing branch instructions.
Background Art
Modern processors have the capacity to process multiple instructions concurrently at very high rates. Currently available processors are clocked at frequencies approaching the gigahertz regime. Despite the impressive capabilities of these processors, their actual instruction throughput on a broad cross-section of applications is often limited by a lack of parallelism among the instructions to be processed. While there may be sufficient resources to process, for example, six instructions concurrently, dependencies between the instructions rarely allow all six execution units to be kept busy. Consequently, there has been an increasing focus on methods to identify and exploit the instruction level parallelism (“ILP”) needed to fully utilize the capabilities of modern processors.
Different approaches have been adopted for identifying ILP and exposing it to the processor resources. For example, speculation and predication operate through the compiler to address the bottlenecks that limit ILP. Speculative instruction execution hides latencies by issuing selected instructions early and overlapping them with other, non-dependent instructions. Predicated execution of instructions reduces the number of branch instructions and their attendant latency problems. Predicated instructions replace branch instructions and their subsequent code blocks with conditionally executed instructions which can often be executed in parallel. Predication may also operate in conjunction with speculation to facilitate movement of additional instructions to enhance parallelism and reduce the overall execution latency of the program.
One side effect of the above-described code movement is that branch instructions tend to become clustered together. Compiler techniques such as trace scheduling, superblock scheduling, and hyper block scheduling also cause branches to cluster at the end of a scheduled code block. Even in the absence these techniques, certain programming constructs, e.g. switch constructs and “if then else if” constructs, can cluster branch instructions in close proximity.
Serial processing of clustered branch instructions is highly inefficient. Fall through branches do not resteer the processor to a non-sequential code sequence, and thus have no impact on code flow. In serial execution, each fall through branch that is processed delays forward progress of the code segment by an additional clock cycle. Where branch instructions are clustered, multiple fall-through branches may be traversed before a branch that alters the control flow of the processor is executed.
SUMMARY OF THE INVENTION
The present invention is a system and method for processing clustered branch instructions concurrently.
In accordance with the present invention, a branch processing system includes multiple branch execution pipelines and linking logic. The linking logic is coupled to receive branch resolution information and identify a first executed branch instruction from one of the branch execution pipelines.
REFERENCES:
patent: 4833599 (1989-05-01), Colwell
patent: 5333280 (1994-07-01), Ishikawa et al.
patent: 5414822 (1995-05-01), Saito et al.
patent: 5655098 (1997-08-01), Witt
patent: 5699536 (1997-12-01), Hopkins et al.
patent: 5699537 (1997-12-01), Sharangpani
patent: 5729728 (1998-03-01), Colwell et al.
patent: 5826070 (1998-10-01), Olson et al.
patent: 5860017 (1999-01-01), Sharangpani et al.
patent: 5903750 (1999-05-01), Yeh
Sharangpani, Harsh, “Intel Itanium Processor Microarchitecture Overview”, Intel, http://www.intel.com on Oct. 19, 1999. all pgs.*
Shanley, Tom, “Pentium Pro Processor Sytsem Architecture”, Mindshare, Inc., pp. 63, 66, 67, 80, 89, and 109, 1997.*
Harshvardhan Sharangpani et al., U.S. Patent Application No. 08/949277 entitled Efficient Processing of Clustered Branch Instructions, Filed Oct. 13, 1997.
Corwin Michael Paul
Jamil Sujat
Sharangpani Harshvardhan
Yeh Tse-Yu
Follansbee John A.
Intel Corporation
Novakoski Leo V.
Whitmore Stacy
LandOfFree
System for processing a cluster of instructions where the... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for processing a cluster of instructions where the..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for processing a cluster of instructions where the... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2502585