What you should get out of this handout
----------

A.  	An understanding of why CPU pipelining is used to speedup execution time. 

B.	The ability to explain how data and branch hazards are created as a result of pipelining, and the means by which they may be resolved.

C.	How the MIPS pipeline is implemented.

D.	A basic understanding of superpipelining and superscalar processors as method to increase speedup, including methods for dealing with the more complex hazard conditions that can arise.

A.  Foundation

a.	An equation for program execution time

Execution Time	 = clock cycle time * the number of instructions * the average clock cycles per instruction

             		 = number of instructions * CPI (average)
              		    -----------------------------------------------
                  		        clock-rate

b.	Since there are three variables in this equation, there are three basic way to decrease execution time:

1.	Reduce the cycle time (increase the clock rate)  

a.	Can be achieved by use of improved hardware design/manufacturing techniques.  In particular, reducing the FEATURE SIZE (chip area needed for one component), results in lower capacitance and inductance, and can therefore run the chip at a higher frequency
b.	Do less computation on each cycle (which increases CPI, of course!)

2.	Reduce the instruction count.

a.	Better algorithms (see CMSC 451)
b.	Do more work per instruction  - This is the idea behind CISC machines
Trade off - May lead to a longer clock cycle time

3.	Reduce CPI

a.	Do less work per instruction - This is the idea behind RISC machines
Trade off - Leads to more instructions per program
b.	Do more work per clock cycle - May increase clock cycle time

4.	Note that, in the case of clock rate and instruction count, there are speedup techniques that are clear "wins" - utilizing them does not adversely affect the other two components of the equation. It appears, though; that it is only possible to reduce CPI is at the cost of more instructions or a slower clock.

5.	While there is no way to reduce the total number of clocks needed for an individual instruction without adversely impacting some other component of performance, it is possible to reduce the AVERAGE CPI by doing portions of two or more instructions in parallel. This is the idea behind pipelining.

c.	Now we are ready to start looking at different ways to decrease execution time, leading to a fully pipelined machine.  Some of these ideas apply to any architecture, but are entirely implemented in RISC machines.

1.	Let's first look at a generic CPU which required six steps to execute an instruction.

a.	The Fetch step (IF) reads the next instruction to be executed from memory (the address is in the program counter register PC) and increment the PC
b.	The Decode step (ID) decodes the instruction and reads any needed CPU registers
c.	Steps 3-6 (S3-S6) are generic and do whatever is needed to complete the instruction

Clock Cycle:        1  2   3   4   5   6   7   8   9  10  11 12 13 14 15 16 17 18
Instruction 1:	IF ID S3 S4 S5 S6
Instruction 2:			 IF ID S3 S4 S5 S6 
Instruction 3:					   IF ID S3 S4 S5 S6

		Note:  This table makes a couple of assumptions.
i.	Each step takes the same amount of time
ii.	All instructions have the same number of steps

2.	If we add a little hardware, we can decrease the execution time by completing portions of instructions in parallel.

A simple method to speed things up is the pre-fetching of instructions.  

Clock Cycle:        1  2   3   4   5    6   7   8   9  10  11 12 13 14 15 16 17 18
Instruction 1:	IF ID S3 S4 S5 S6
Instruction 2:	                          IF ID S3 S4 S5 S6 
Instruction 3:			                       IF ID S3 S4 S5 S6

Each instruction still takes 6 cycles, but once execution gets rolling an instruction is completed every 5 cycles.

		Speedup = Old Execution Time/ New Execution Time
			 = 6/5   =>  This modification gives us a speedup of 1.2

3.	Pre-fetching does cause a problem.  What happens with conditional instruction?  Until the conditional is executed the next instruction is not known.  This is called a BRANCH or CONTROL HAZARD.  

What can we do to overcome this problem?
	--  All of these solutions require adding additional hardware to the CPU.
--  We can stop pre-fetching until the branch hazard is resolved.  This is called stalling, bubbling or doing NoOps.
--  We can guess the branch is taken/not taken, and flush the pipe if we guess wrong.
	*The book list several ways to do this.
	** We have to make sure we can undo everything until the hazard is resolved!!!
--  We could pre-fetch both sides of the branch and discard what we don't need.
--  There are other methods talked about in your book like branch delay slots

4.	Pre-fetching on RISC machines is relatively simple because all instructions are required to be the same length, one word.  On CISC machines with variable length instruction, that you may not know how long it is until you start decoding it, is a bit more complicated.

5.	Now lets try pre-fetching and decoding the instructions in parallel!

Clock Cycle:        1  2   3   4    5   6    7   8   9  10  11 12 13 14 15 16 17 18
Instruction 1:	IF ID S3 S4 S5 S6
Instruction 2:	                     IF ID S3 S4 S5 S6 
Instruction 3:			             IF ID S3 S4 S5 S6

Assuming we don't have to stall for any control hazard, we are completing an instruction every 4 clock cycles.  Our speedup is 6/4 or 1.5.  Pretty impressive.

6.	As you probably guessed, decoding instructions in parallel has some problems too.

I'll use pseudo code, but Dr. Hugue will be using MIPS for this course.

Look at the following code fragment.

Instruction 1:		R1 = R2 + R3
Instruction 2:		R5 = R1 + R7

If we decode instruction 2 before instruction 1 has been completed, remember that in the Decode step we read any registers needed, then R1 will not have the new value written into it and R5 is going to have a bogus value assigned to it.  This is called a DATA HAZARD or instruction 2 has a DATA DEPENDENCY on instruction 1.

Data hazard - the result of one instruction is needed as input to another instruction

Data Hazard Classification
Consider 2 instructions i and j, i occurs before j, the possible data hazards are:
1)	RAW (read after write) - j tries to read a source before i writes it, so j gets the old value.
2)	WAW (write after write) - j tries to write an operand before it is written by i, therefore the value left is written by i instead of j - wrong order !. 
3)	WAR(write after read) - j tries to write a destination before it is read by i, so i incorrectly reads new value not the old one. 
4)	RAR(read after read) - this is not a hazard because reading does not change the value.

 What can we do to overcome this problem?
	--  Again more hardware needed!
	--  We can stall instruction 2 until instruction 1 is completed.
--  If we have a smart compiler, it could stuff some instructions without a data                                            
    dependency between instructions 1 and 2, OUT OF ORDER COMPLETION
--  Forwarding

7.	Forwarding

Lets look at what would happed if we just stall until the hazard clears.  In this case instruction 2 has a data dependency on instruction 1

Clock Cycle:        1  2   3   4    5   6    7   8   9  10  11 12 13 14 15 16 17 18
Instruction 1:	IF ID S3 S4 S5 S6
Instruction 2:	                     IF stl  ID S3 S4 S5 S6 
Instruction 3:			                   IF ID S3 S4 S5 S6

	In clock cycle 6, instruction 2 stalls for one cycle to allow instruction 1 to be completed.

Let's assume for this example that instruction 1 has completed the calculation of the needed value in Step 4, that would be clock cycle 4 in this example.  Do we really need to stall in clock cycle 6?  No.  We can add additional hardware that can detect this condition and forwards or bypasses the value to where it is need to minimize the number of stalls.  This is the general idea behind forwarding.

8.	The greatest degree of parallelism would be to overlap all steps in the completion of instructions.

Clock Cycle:        1  2   3   4    5   6    7   8   9  10  11 12 13 14 15 16 17 18
Instruction 1:	IF ID S3 S4 S5 S6
Instruction 2:	     IF ID S3 S4 S5 S6 
Instruction 3:	          IF ID S3 S4 S5 S6

We call this a FULLY PIPELINED CPU.  In the steady state, it completes one instruction on every cycle, so its average CPI is 1.

Of course, an average CPI of 1 is attainable only when the pipeline is full of valid instructions.  When the pipeline has been flushed (e.g. after a branch), it may take several cycles for the pipeline to fill up again.  As a result, a fully pipelined machine ends up in practice having a CPI somewhat bigger than 1.

B.	A Simple Implementation of the RISC Instruction Set

1.	As discussed in the book, RISC instructions are implemented in up to five steps.  In a pipelined implementation, EVERY instruction has all five steps (though some may not actually do any useful work), and the pipeline has 5 stages:

2.	Pipeline Stages

a.	IF - does both of the following in parallel
-	instruction fetch
-	increments the program counter
b.	ID - does all of the following in parallel
-	decodes the instruction
-	reads register file into ALU holding registers A + B
-	calculates the branch target address
-	not all of these are used
c.	EX - does one of the following
-	calculates the address for a memory reference instruction
-	ALU operation for a R type instruction
d.	MEM - does one of the following
-	reads or writes to memory for a memory operation
-	on non-memory instruction this step does nothing
e.	WB - does one of the following
-	writes the output of the ALU to the appropriate register in the register file
-	writes the value read from memory into the appropriate register in the register file
-	for all other instructions does nothing

3.	Note the presence of pipeline registers between each pair of stages. Since there are five instructions in the pipeline at any time, there is a need to keep copies of four instructions (or at least portions of them) in registers at any time.  (There are only four instructions in registers, because one is coming out of memory during stage 1). In addition, we need to keep certain data in these registers.

a.	IF/ID holds an instruction, plus the incremented PC value of where it came from.
b.	ID/EXEC holds the op-code (possibly in some decoded form) plus the destination register specifier, immediate value, and function fields of the instruction, plus the A and B source values read out of the register file, plus the PC passed on from the IF/ID register
c.	EXEC/MEM holds the op-code and destination register specifier fields of the instruction (copied from ID/EXEC), plus the ALUOut value, plus the data that is to be written to memory if the instruction is a store (contents of register specified by rt).
d.	MEM/WB holds the op-code and destination register specifier fields of the instruction and the ALUOut value (copied from ID/EXEC) plus the value just read from memory if the instruction is a load.

4.	The motivation for going to a five-stage pipeline appears to be the following
 
a.	Doing the register file read, ALU operation, and write back of the ALU result in one step (as is the case for the three-stage pipeline) would require a longer clock cycle for this stage, and thus for all stages in the pipeline.
b.	As. Likewise, doing a memory read and writing the item read back to a register in one step (as is also the case for the three-stage pipeline) would pose a similar problem.
c.	As Since the load instruction ends up requiring 5 steps (which is the longest instruction) a 5-stage pipeline is called for.

5.	Actually, the way the book describes the MIPS pipeline - and the way we have described it here - is a bit oversimplified.  The actual pipeline on most MIPS implementations has five stages, but uses only four clocks because two of the stages are just half a clock long.  (Recall that the clock is a square wave, and a complete cycle includes both rising and falling edges).  Here is the actual structure:

                                              ----------------------------------
WB (1/2 cycle)                                | S1 |/////| S2 |/////| S3 | ... 
                                   ---------------------------------------------
MEM                                |    S1    |    S2    |    S3    |    S4    |
                        --------------------------------------------------------
EXEC                    |    S1    |    S2    |    S3    |    S4    | ...
                   --------------------------------------------------
ID (1/2 cycle)     | S1 |/////| S2 |/////| S3 |/////| S4 | ...
        --------------------------------------------------
IF      |    S1    |    S2    |    S3    |    S4    | ...
        ---------------------------------------------

        ///// = this pipeline stage is idle on this half-cycle

 (We will stick with the simplified version used in the book for most of our discussion, since the basic issues are not affected.)
        
6.	The use of a five-stage pipeline allows for a shorter clock cycle, but the downside is that it complicates dealing with hazards.

a.	At first glance, it would appear that the branch hazard problem would be exacerbated, because instructions are normally executed in stage 3 (meaning that there would now be 2 instructions in the pipeline when a branch is executed.)  However, the hardware is arranged so that branch instructions are executed in stage 2 of the pipeline, and deals with the single instruction behind it in the pipeline by using delayed branching.

b.	On the other hand, the data hazard issue is made much worse. In the 5-stage pipeline, data hazards can also arise from dependent sequences of computational instructions.

-	Example: Consider the following program fragment:

Inst1:	add     r2, r4, r5
                	Inst2:	add     r3, r6, r7
                	Inst3:	add     r3, r2, r3
                	Inst4:	add     r2, r2, r8

(where it is the intention that Inst3 use the values in r2 and r3 computed by Inst1 and Inst2, and Inst4 uses the value in r2 computed by Inst1)

Consider what happens with a 5-stage pipeline

        WB                                      			Inst1	Inst2 	... 	...
                                                			r2 <-   	r3 <-
                                                			r4+r5   	r6+r7

        MEM                             		Inst1   	Inst2:     	...	...
                                        			(pass   	(pass
                                        			ALU  	ALU
					Out	Out
                                        			thru)   	thru)

        EXEC                    		Inst1     	Inst2     	Inst3     	Inst4
                                		ALU  	ALU	ALU	ALU
				Out	Out	Out	Out
                                		<- A+B  <- A+B  <- A+B  <- A+B
                                		(r4+r5) 	(r6+r7) 	(r2+r3) 	(r2+r8)

        ID			Inst1	Inst2	Inst3	Inst4:
                        		A<-r4 	A<-r6   	A<-r2   	A<-r2
                        		B<-r5   	B<-r7   	B<-r3   	B<-r8
                                        			(BOTH   (A
                         				VALUES  VALUE
                                         			WRONG!) WRONG!)
        
        IF		Inst1	Inst2	Inst3	Inst4

How many bubbles, NoOPs, or other instructions would need to be inserted between Inst2 and Inst3 to make Inst3 and Inst4 get the right values?

            - One would take care of getting the right r2 for Inst4, but would not help Inst3 at all.

            - Two would take care of getting the right r2 for Inst3 as well, but r3 would still be wrong

            - Three would make everything work correctly:

        WB                                      			Inst1	Inst2 	... 	...
                                                			r2 <-   	r3 <-
                                                			r4+r5   	r6+r7

        MEM                             		Inst1   	Inst2:     	...	...
                                        			(pass   	(pass
                                        			ALU  	ALU
					Out	Out
                                        			thru)   	thru)

        EXEC                    		Inst1     	Inst2     	NoOp	NoOp	NoOp	Inst3     	Inst4
                                		ALU  	ALU				ALU	ALU
				Out	Out				Out	Out
                                		<- A+B  <- A+B  			<- A+B  <- A+B
                                		(r4+r5) 	(r6+r7) 				(r2+r3) 	(r2+r8)

        ID			Inst1	Inst2	NoOp	NoOP	NoOP	Inst3	Inst4:
                        		A<-r4 	A<-r6   				A<-r2   	A<-r2
                        		B<-r5   	B<-r7   				B<-r3   	B<-r8

        IF		Inst1	Inst2	NoOp	NoOP	NoOp	Inst3	Inst4
 
-	Requiring three instructions between the time a value is computed and the time it is used would have a very severe negative impact on performance, so some other solution is desirable.  This pipeline uses two.
-	A one instruction reduction in the size of the problem is achieved automatically by the fact that ID and WB are half cycles. (Refer to more accurate timing diagram).
-	To squeeze the remaining two delays out, observe that the values needed by Inst3 EXIST at the time Inst3 needs them - they're just not in the right places.
i.	The value which will go into r2 is sitting in the ALUOut portion of the MEM/WB pipeline register when Inst3 needs to use it during its EXEC step.
ii.	The value which will go into r3 is sitting in the ALUOut portion of the EXEC/MEM pipeline register when Inst3 needs to use it during its EXEC step.
iii.	The two stage delay that would otherwise be needed between computing a result and using it could be avoided if the ALU input selection logic could be modified to either use a value from any of the following:
-	The register A or B portion of the ID/EXEC pipeline register (as the case may be)
-	or  - The ALUOut register portion of the EXEC/MEM pipeline register
-	or  - The ALUOut register portion of the MEM/WB pipeline register
-	This must be handled separately for each of the two ALU inputs.

        

        WB                                      			Inst1	Inst2 	... 	...
                                                			r2 <-   	r3 <-
                                                			r4+r5   	r6+r7

        MEM                             		Inst1   	Inst2:     	...	...
                                        			(pass   	(pass
                                        			ALU  	ALU
					Out	Out
                                        			thru)   	thru)

        EXEC                    		Inst1     	Inst2     	Inst3     	Inst4
                                		ALU  	ALU	ALU	ALU
 				Out	Out	Out	Out
						<-M/W	<- A+B
						+E/M
						ALU
						Outs
                                		<- A+B  <- A+B  <- A+B  

                                		(r4+r5) 	(r6+r7) 	(r2+r3) 	(r2+r8)

        ID			Inst1	Inst2	Inst3	Inst4:
                        		A<-r4 	A<-r6   	A<-r2   	A<-r2
                        		B<-r5   	B<-r7   	B<-r3   	B<-r8
                                        			(BOTH   
                         				VALUES  
                                         			WRONG!) 
        
        IF		Inst1	Inst2	Inst3	Inst4

This is an example of DATA FORWARDING.

7.	We have examined the impact of the five-stage pipeline on R-Type instructions, and have seen that data forwarding can prevent hazards.  What about load-type instructions.

a.	Both R-Type instructions and load instructions write their value to a register in the last stage of the pipeline, so the basic issue is the same.
b.	However, a key difference is that, with an R-Type instruction, the value is actually available at the end of the EXEC stage (stage 3) and can be forwarded from them, where as in the load instruction the value does not become available until the end of the MEM stage (stage 4).
c.	As a result, by use of data forwarding, we can reduce the delay.  We must have one instruction intervening between a load instruction and any other instruction that uses its result.  This is handled by using DELAYED LOAD.

IV. Moving Beyond Basic Pipelining
--  ------ ------ ----- ----------

   A. The potential speedup from pipelining is a function of the number of stages in the pipeline.

      1. For example, suppose that an instruction that would take 4 ns to execute is implemented using a 4 stage pipeline with each stage taking 1 ns.  Then the speedup gained by pipelining is

         w/o pipeline  - 1 instruction / 4 ns
         with pipeline - 1 instruction / 1 ns
 
         4ns/1ns = 4:1

         Now if, instead, we could implement the same instruction using a 5 stage pipeline with each stage taking 0.8 ns, we could get a 5:1 speedup instead.

      2. This leads to a desire to make the pipeline consist of as many stages as possible, each as short as possible.  This strategy is known as SUPERPIPLINING, and is used by a number of CPU's. However, superpiplining does run into some problems that prevent the theoretical maximum speedup from being achieved.

         a. If the individual steps an instruction is broken up into don't all take the same time (a likely situation), then the time for the longest step becomes the time for all steps.

            Example: if in going from 4 stages to 5 in our example above it turned out that one of the steps needed only 0.6 ns but another needed 1 (still 4 ns total), the cycle time would have to be 1ns, and the speedup would still be only 4:1

         b. The longer the pipeline, the greater the potential waste of time due to data and branch hazards.

      3. Note that superpipelining attempts to maintain CPI at 1 (or as close as possible) while using a longer pipeline to allow the use of a faster clock.

   B. It would appear, at first, that a CPI of 1 is as good as we can get - so there is nothing further that can be done beyond full pipelining to reduce CPI.  Actually, though, we can get CPI less than one if we      execute two or more instructions fully in parallel (i.e. fetch them at the same time, do each of their steps at the same time, etc) by duplicating major portions of the instruction execution hardware.
      
      1. If we can start 2 instructions at the same time and finish them at the same time, we complete 2 instructions per clock, so average CPI drops to 0.5.  If we can do 4 at a time, average CPI drops to 0.25.

      2. Because various hazards make it impossible to always achieve the maximum degree of parallelism, we speak of a machine as ISSUING some number of instructions on a given clock.  (An instruction is         issued when it is actually allowed to begin execution.) Potentially, for a given machine, this might be 2 or 4; however, the actual number issued on a given clock may be less.

      3. This is facilitated by taking advantage of the fact that many CPU's have separate execution units for executing different types of instructions - e.g. there may be:

         a. An integer execution unit used for executing integer instructions like add, bitwise or, shift etc..

         b. A floating point execution unit for executing floating point arithmetic instructions.  (Note that many architectures use separate integer and floating point register sets).
        
         c. A branch execution unit used for executing branch instructions.

         If two instructions need two different execution units (e.g. if one is an integer instruction and one is floating point) then they can be issued simuiltaneously and execute totally in parallel with each other, without needing to replicate execution hardware (though decode and issue hardware does need to be replicated.)

         Note that, for example, many scientific programs contain a mixture of floating point operations (that do the bulk of the actual computation), integer operations (used for subscripting arrays of floating point        values and for loop control), and branch instructions (for loops). For such programs, issuing multiple instructions at the same time becomes very feasible.

         Note: in effect, a group of instructions that do a computation - say - on an array element and then update a pointer to point to the next element become, in effect, like a single CISC instruction with autoincrement!

      4. The earliest scheme used for doing this was the VERY LONG INSTRUCTION WORD architecture.  In this architecture, a single instruction could specify more than one operation to be performed - in fact, it could specify one operation for each execution unit on the machine.

         a. The instruction contains one group of fields for each type of instruction - e.g. one to specify an integer operation, one to specify a floating point operation, etc.

         b. If it is not possible to find operations that can be done at the same time for all functional units, then the instruction may contain a NOP in the group of fields for unneeded units.

         c. The VLIW architecture requires the compiler to be very knowledgeable of implementation details of the target computer, and may require a program to be recompiled if moved to a different implementation of  the same architecture.  

         d. Because most instrucion words contain some NOP's, VLIW programs tend to be very long.

      5. Current practice - found on a number of RISCs including Dec Alpha and the Power PC - is to use SUPERSCALAR architecture.

         a. A superscalar CPU fetches groups of instructions at a time - typically two (64 bits) or four (128 bits) and decodes them in parallel.

         b. A superscalar CPU has just one instruction fetch unit (which fetches a whole group of instructions), but it has 2 or 4 decode units and a number of different execution units.

         c. If the instructions fetched together need different execution units, then they are issued at the same time.   If two instructions need the same execution unit, then only the first is issued; the second is issued on the next clock.  (This is called a STRUCTURAL HAZARD).

         d. To reduce the number of structural hazards that occur, some superscalar CPU's have two or more integer execution units, along with a branch unit and a floating point unit, since integer operations are more frequent.  Or, they might have a unit that handles integer multiply and divide and one that does add and            subtract.

      6. Once again, the issue of data and branch hazards becomes more complicated when multiple instructions are issued at once, since an instruction cannot depend on the results of any instruction         issued at the same time, nor on the results of any instruction issued on the next one or more clocks.  With multiple instructions issued per clock, this increases the potential for interaction between instructions, of course.

         a. Example: If a CPU issues 4 instructions per clock, then up to seven instructions following a branch might be in the pipeline by the time the branch instruction finishes computing its target address.  (If it is the first of a group of 4, plus a second group of 4.)

         b. Example: If a CPU issues 4 instructions per clock, then there may  need to be a delay of up to seven instructions before one can use the result of a load instruction, even with data forwarding as described above.

   C. Dealing with Hazards on a Superscalar Machine

      1. Data hazards

         a. We have previously seen how data forwarding can be used to eliminate data hazards between successive instructions where one instruction uses a result computed by an immediately-preceeding            one.  However, if "producer" and "consumer" instruction are executed simultaneously in different execution units, forwarding no longer helps.  Likewise, the unavoidable one cycle delay needed by a load could effect many successive instructions.

         b. Superscalar machines typically incorporate hardware interlocks to prevent data hazards from leading to wrong results.  When an instruction that will store a value into a particular register is          issued, a lock bit is set for that register that is not cleared until the value is actually stored - typically several cycles later.  An instruction that uses a locked register as a data input is not issued until the register(s) it needs is/are unlocked.

         c. Further refinements on this include a provision that allows the hardware to schedule instructions dynamically, so that a "later" instruction that does not depend on a currently executing instruction might be issued after an "earlier" instruction that does.  (This is called OUT OF ORDER EXECUTION.)

      2. Branch hazards

         a. To reduce the impact of branch hazards, some machines (CISCs as well as highly-pipelined RISCS) may make use of BRANCH PREDICTION.  When a conditional branch instruction is encountered, the fetch  unit makes a guess as to whether or not the branch is going to be taken.  If the prediction is that the branch will be taken (or the branch is unconditional), then the fetch unit begins to fetch          instructions from the  new location; otherwise, it keeps fetching as usual.  Only if the prediction is wrong does a pipeline flush occur.

            i. How can such a prediction be done?

              - One way to do the prediction is to use the following rule of thumb: assume that forward conditional branches will not be taken, and backward conditional branches will be taken.

                Why?  ASK

                - Forward branches typically arise from a construct like

                  if something then
                        common case
                  else
                        less common case

                - Backward branches typically result from loops - and only the last time the branch is encountered will it not be taken.

              - Some machines incorporate bits into the format for branch instructions whereby the compiler can furnish a hint as to whether the branch will be taken.

              - Some machines maintain a branch history table which stores the address from which a given branch instruction was fetched and an indication as to whether it was taken the last time it was executed.

           ii. In any case, prediction requires the ability to reach a definitive decision about whether the branch is going to be taken before any following instructions have stored any values into memory or registers.

          iii. Prediction cannot eliminate all problems, because if the branch is predicted to be taken, it is not possible to begin prefetching down the new path until the target address has been computed (in stage 2 of the pipelines we have been using for examples.)  CPU's that record branch history can avoid this       problem by also storing the target address of the branch. (Since the target address of a branch instruction is generally computed by PC + displacement in instruction, a given branch instruction will always point to the same target.)

         b. An alternative to branch prediction that is being used on the new Intel RISC architecture in development (IA 64) is called PREDICATION.  In this strategy, the CPU includes a number of one            bit predicate registers that can be set by conditional instructions. The instruction format includes a number of bits that allow execution of an instruction to be contingent on a particular predicate register being true (or false).  Further, a predicated instruction can begin executing before the value of its predicate is actually known, as long as the value becomes known before the instruction needs to store its result.  This can eliminate the need for a lot of branch instructions.

            Example:

                if r10 = r11 then
                    r9 = r9 + 1
                else
                    r9 = r9 - 1            Would be translated on MIPS as:

                bneq    $10, $11, else
                nop                     # Branch delay slot
                br      endif
                addi    $9, $9, 1       # In branch delay slot - always done
            else:
                addi    $9, $9, -1
            endif:

            Which is 5 instructions long and needs 4 clocks if $10 = $11 
            and 3 if not.

            But on a machine with predication as:

                set predicate register 1 true if $10 = $11
                (if predicate register 1 is true) addi $9, $9, 1
                (if predicate register 1 is false) addi $9, $9, -1

            Which is 3 instructions long (all of which can be done in parallel, provided the set predicate instruction sets the predicate register earlier in its execution than the other two store their results.)
                
   D. Advanced CPU's use both superpiplining and superscalar techniques. (E.g. Dec Alpha is both superpipelined and superscalar).  The benefits that can be achieved are, of course, dependent on the ability of the compiler to arrange instructions in the program so that when one instruction depends upon another it occurs enough later in the program to prevent hazards from stalling execution and wasting the speedup that      could otherwise be attained.