load stalling and branch stalling in a pipeline datapath

I think you can just insert some very long-running operations in the pipeline - there will be clock cycles where the cpu is doing nothing but waiting for the results.  However, it is not as neutral as NOP - flags may be set as a result.

If it's too hard then I'll just use the nop operation

A question about stalling because of load.. if I have the code below then I just need to insert one nop after the last lw right in order to make it work in a pipelined datapath?

lw  $t2, 0($t2)			# load the corresponding element value at the frame
	lw  $t8, 0($t8)			# load the corresponding element value at the window
	sub $t2, $t2, $t8		# subtract the frame and window size element difference

Select allOpen in new window

Could you explain why you think you need to insert a nop?  Whether you have it there or not, the operation after still has to wait.  In a perfect world of pipelines, there would only be short instructions that filled the queues and no waiting, but the real world is rarely that way.

for example in a branch... we do need an nop... otherwise the already executed instructions needed to be flushed

Ah, I see what you're getting at - yes, for pipelined datapaths, you need to insert a nop after a branch because it is always executed.  It's called a branch delay slot: http://en.wikipedia.org/wiki/Delay_slot  The article also says a sophisticated design would insert instructions that don't depend on the result of the branch instruction, instead of a nop.

yes, I've read that article on wikipedia several times however I still don't grasp the idea of it... what does it mean to flush a pipeline? I think it means to have the next instructions as a nop and hold the program counter??

When we take a branch, we will have to clear/flush the instruction pipeline .. because those instruction wont execute ... since we took a branch.... the processor will have to pick up instruction from the new location.

The idea why to insert instructions that don't depend on the result of the branch instruction is because normally most the processors are superscalar... meaning that it can execute instructions in parallel...
So putting such instructions in the delay slot means that processor can execute those instruction while calculating/executing the branch instruction... and if branch fails.. then its a bonus... because the next instruction is already executed(or a part of it is done).... this can improve the performance.
If we put instruction that depend on the branch.. then the pipeline will stall because it cant execute those instructions since it depends on the branch results.

okay...so therefore in the controller I will need to do the following...
1. if the branch is not taken then everything is good, nothing needs to be flushed
2. if the branch is taken then we need to flush the pipeline

Now my understanding of flushing the pipeline is basically setting the instruction to be executed next to a nop. In a 5 state pipelined in MIPS we know whether to branch or not in the ID stage ( I moved the branch decision into the ID stage instead of the EX). So therefore all I need to do if the branch is taken is to flush the IF/ID register; i.e setting the 32 bit to 0? Is that all?

so a pipeline stall = a single nop
a pipeline flush = a number of nops

true?

Yes

if I had my branch decisions at the ID stage then I would only need to flush the ID pipeline

Is there such a thing as an ID pipeline?  I thought the stages in a data pipeline are fixed for a given processor and a flush clears all stages.

IF/ID pipeline I mean

There are still only two variations of inserting nops that I am aware of, as noted in http:#a31498972 - a stall or a full flush.

so let me re-word it then, if we have the branch decision in the ID stage then all we need to do is stall the IF/ID pipeline

The decision to stall or flush depends on how well you think your design will perform.  A flush will guarantee that there are no hazards, while a stall will put off the possibility.  Flushing a pipeline obviously makes the processor perform worse than a stall, but it might be better than repeating a stall n times.  This is a design decision only you can make, so there's no clear-cut answer.

stall looks better to me... ofcourse you will have to take care of data hazards.... you can use register renaming concept..that should prevent all sorts of data hazards.

well...renaming and re-arranging the register name would only help in the case of forwarding... but not in branches

yes.. you are correct.. renaming wont help ....
my bad.