Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
2000-06-30
2003-10-07
Treat, William M. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C712S241000, C717S159000, C717S160000
Reexamination Certificate
active
06631465
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to digital processing. More particularly, the present invention relates to code generating and code sequencing. Specifically, the present invention relates to a method and apparatus for instruction re-alignment using a branch on a falsehood of a qualifying predicate.
BACKGROUND OF THE INVENTION
A common operation for a digital processing system is running a program. The program code for the program is first compiled into code sequences (“instructions”), which are aligned or stored sequentially in “blocks” of memory. A processor processes the instructions to execute the program. For an instruction block having a conditional branch, the program control flow can either “fall-through” to the next sequential instruction block or “jump” to an instruction block at some offset from the instruction block having the conditional branch.
Typically, whether a conditional branch “falls-through” or “jumps” is dependent on the value of a guarding predicate for the conditional branch. That is, if the guarding predicate is “true” the conditional branch “jumps” to a target instruction (“target instruction”) and if the guarding predicate is “false” the conditional branch “falls-through” to the next sequential instruction (“fall-through instruction”). Consequently, in many instances, it is necessary to re-align the target instruction with the fall through instruction in a memory without changing the original semantics of the program code (i.e., to make the original fall-through instruction the target instruction and to make the original target instruction the fall-through instruction).
FIG. 1
depicts a prior art illustration
100
of re-aligning instruction blocks. The prior art illustration
100
shows how the target instruction can be re-aligned with the fall through instruction by using a complementary predicate (i.e., pF) of a qualifying predicate (i.e., pT) to guard the conditional branch. Complementary predicates are generated by compare instructions (e.g., pT, pF=compare (a>b)) in which the complementary predicates have opposite logic values. For example, using the compare instruction above, if “a” is greater than “b” the guarding predicate (pT) is true and its complementary predicate (pF) is false. Furthermore, if “a” is not greater than “b” the guarding predicate (pT) is false and its complementary predicate (pF) is true. In the prior art, the target instruction can be re-aligned with the fall through instruction by guarding the conditional branch with the complementary predicate (pF) instead of the qualifying predicate.
Referring to
FIG. 1
, logical representation of code sequencing
102
represents five instructions (A through E) to be executed by a processor. Instruction A has a conditional branch for either instruction block B or C. Physical layout in memory
103
show how instructions A through E are laid out in a memory for one implementation. In the implementation of physical layout in memory
103
, the conditional branch of instruction A “jumps” to instruction C (“target instruction”) if the qualifying predicate (pT) is true and “falls-through” to instruction B (“fall through instruction”) if pT is not true.
To re-align the target instruction (instruction C) with the fall-through instruction (instruction B) in the implementation of physical layout in memory
103
, the conditional branch of instruction A must be guarded by the complementary predicate (pF) of the qualifying predicate (pT). The re-aligned layout in memory
106
shows instruction A being guarded by the complementary predicate (pF) to jump to instruction B (“target instruction”) and to fall-through to instruction C (“fall-through instruction”) if pF is true.
A disadvantage of the prior art of re-aligning instructions is that it requires a complementary predicate for the qualifying predicate. That is, if a complementary predicate is not available for the qualifying predicate, the complementary predicate must be generated in order to re-align the instructions. Consequently, generating the complimentary predicate for a qualifying predicate can be problematic if compare instructions are complicated and cascaded. Thus, more instructions may be need to produce the complimentary predicate, which translates into additional resource usage and additional processing time.
REFERENCES:
patent: 5937195 (1999-08-01), Ju et al.
patent: 5999738 (1999-12-01), Schlansker et al.
Pnevmatikatos et al., Guarded Execution and Branch Prediction in Dynamic ILP Processors, Proceedings of the 21st Annual Symposium on Computer Architecture, IEEE, pp. 120-129, 1994.*
Mahlke et al., Effective Compiler Support for Predicated Execution Using the Hyperblock, Proceedings of the 25thannual International Symposium on Microarchitecture, IEEE, pp.45-54, 1992.*
Tirumalai et al., Parallelization of Loops with Exits on Pipelined Architectures, Proceedings of the 1990 Conference on Supercomputing, IEEE, pp. 200-212, 1990.*
Mahlke et al. A Comparison of Full and Partial Predicated Execution Support for ILP Processors, Proceedings of the 22nd Annual International Conference on Computer Architecture, IEEE, pp. 138-150, 1995.*
Vasanth Bala, Evelyn Duesterwald, Sanjeev Banerjia, “Transparent Dynamic Optimization: The Design and Implementation of Dynamo”, HP Laboratories Cambridge, HPL-1999-78, Jun., 1999.
Chen Dong-Yuan
Chen William Y.
Blakely , Sokoloff, Taylor & Zafman LLP
Intel Corporation
Treat William M.
LandOfFree
Method and apparatus for instruction re-alignment using a... 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 instruction re-alignment using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for instruction re-alignment using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3169351