Browse Prior Art Database

Mechanism for Improving Conditional Branch Performance

IP.com Disclosure Number: IPCOM000100256D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 7 page(s) / 290K

Publishing Venue

IBM

Related People

Irish, JD: AUTHOR [+3]

Abstract

Described is a mechanism for improving the performance of conditional branch instructions in a pipelined processor. This mechanism provides the performance benefit gained by fetching both possible outcomes of a conditional branch without requiring the hardware necessary to save the instructions that will be thrown away.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 22% of the total text.

Mechanism for Improving Conditional Branch Performance

       Described is a mechanism for improving the performance of
conditional branch instructions in a pipelined processor. This
mechanism provides the performance benefit gained by fetching both
possible outcomes of a conditional branch without requiring the
hardware necessary to save the instructions that will be thrown away.

      In general, instruction pipelining involves dividing the
instruction execution into a sequence of steps.  These steps may
include:  1) decoding the instruction, 2) fetching the data to be
operated on by the instruction, 3) performing the instruction's
operation, and 4) storing the results. Each of these steps is then
implemented as a separate entity, known as a "stage".  The stages are
connected sequentially to form a pipeline.  In order for an
instruction to be executed, it must pass through all stages of the
pipeline. Each stage may take one or more processor cycles to
complete.  Only one instruction can occupy a stage at a given time;
however, each stage may be operating on a different instruction.  In
a pipeline with four stages as described above, there can be four
different instructions, one in each stage, being worked on in
parallel.  This parallelism results in a higher instruction execution
rate than would be obtained by executing the instruc- tions one at a
time.

      Normally, instructions are executed sequentially from main
storage. In a processor where the instruction execution is pipelined,
as soon as an instruction completes the first stage of the pipe and
moves to the second stage, the next sequential instruction from main
storage is fed into the pipe.  In this way, the pipeline is kept full
of instructions and is thus operating at its greatest efficiency.  A
problem occurs, however, when a conditional branch instruction is to
be executed.  The problem is:  It is not known what instruction to
feed into the pipe following the conditional branch until after the
condition specified in the branch instruction can be tested.

      When the branch condition is tested, a decision is made whether
to execute the instruction addressed by the conditional branch
instruction, known as the branch target, or to execute the
instruction sequentially following the conditional branch, known as
the branch successor.  Once the branch target or branch successor has
been picked, it and the instructions sequentially following it are
fed through the pipeline.  This may not occur until the conditional
branch instruction has reached one of the last stages of the
pipeline.  The result is that pipeline stages are idle until the
pipeline is restarted.  These idle stages lower the pipeline's
efficiency and, as a result, reduce the processor's instruction
execution rate.

      The following is a brief description of the assumed pipeline
stages and their function.

      The pipeline that is implemented is comprised of four stages:
...