34 replies to this topic

[Apprentice123]

The instructions on a given architecture are divided into six steps, which have operating times of 2ns, 2ns, 2.5ns, 1.5ns, 2.2ns and 1.8ns respectively. What is the maximum possible performance gain of this architecture using pipeline technique, where each step corresponds to a stage?

It's correct:

No Pipeline:

2+2+2.5+1.5+2.2+1.8 = 12ns

Gain with pipeline:

12/6 = 2ns

?

[RhetoricalRuvim]

It's actually probably somewhere in between those two numbers, because the processor can't at all times run at that speed, because of dependencies, etc. I mean, like if the next instruction relies on the current instruction, in which case the initialization of execution of the next instruction cannot be started before the completion of execution of the current instruction.

Some more complex processor architectures do try stepping across that limitation, however, by doing dependency checks, and by scanning ahead of time, what instructions can be executed without interfering with the dependencies of the instructions on results of other not-executed instructions.

[Apprentice123]

RhetoricalRuvim said:

It's actually probably somewhere in between those two numbers, because the processor can't at all times run at that speed, because of dependencies, etc. I mean, like if the next instruction relies on the current instruction, in which case the initialization of execution of the next instruction cannot be started before the completion of execution of the current instruction.

Some more complex processor architectures do try stepping across that limitation, however, by doing dependency checks, and by scanning ahead of time, what instructions can be executed without interfering with the dependencies of the instructions on results of other not-executed instructions.

The "maximum" gain is not it?
time not pipeline / number stages = 12 / 6 = 2ns ??

[RhetoricalRuvim]

It might be, on average; I don't know for sure. I was thinking 2.5 ns, maybe, because it's the longest out of all the items on that list you provided. I mean, wouldn't the 2 ns stage have to wait for the 2.5 ns stage? Or is there some intermediate buffer?

You can try asking one of the users from this thread; they seem to know some stuff up this alley.

[Apprentice123]

RhetoricalRuvim said:

It might be, on average; I don't know for sure. I was thinking 2.5 ns, maybe, because it's the longest out of all the items on that list you provided. I mean, wouldn't the 2 ns stage have to wait for the 2.5 ns stage? Or is there some intermediate buffer?

You can try asking one of the users from this thread; they seem to know some stuff up this alley.

I do not know. How to calculate the maximum gain in pipeline?

[dargueta]

I think we're supposed to assume there are no dependencies here, as the problem asks for the maximum performance gain. For the sake of simplicity let's count this in terms of clock cycles and assume that one cycle takes 0.2ns, so stage 1 is 20 clock cycles, stage 3 is 25, etc. Now we have whole numbers to work with.

If you look at the execution times, at stage 4 instruction B will have to wait 7 cycles before instruction A finishes stage 5. Make a note of this.
When pipelining, the first instruction executed always takes the same amount of time as if it weren't pipelined, so instruction A takes 120 cycles.

STAGE   1       2       3       4       5       6       DONE
LENGTH  20      20      25      15      22      18
TIME    0-20
        A       20-40
                A       40-65
                        A       65-80
                                A       80-102
                                        A       102-120
                                                A

We can extend this to the next five instructions. For now we'll just add one more:

STAGE   1       2       3       4       5       6       DONE
LENGTH  20      20      25      15      22      18
TIME    0-20
        A
           
        20-40   20-40
        B       A
        
                40-[COLOR=RED]60[/COLOR]   40-[COLOR=RED]65[/COLOR]
                B       A
                
                        60-85   65-80
                        B       A
                        
                                85-100  80-102
                                B       A
                                
                                        100-122 102-120
                                        B       A

Uh-oh: Notice that instruction B finishes before A. It can't go anywhere until A finishes. This is called a stall, where B--and everything behind it--is stuck waiting in the pipeline until the traffic ahead of it clears. Let's readjust B's start time in stage 3 so that it doesn't start before A is done with stage 4.

Note that this delay affects the timing of instruction B and everything behind it.

STAGE   1       2       3       4       5       6       DONE
LENGTH  20      20      25      15      22      18
TIME    0-20
        A
           
        20-40   20-40
        B       A
        
                40-[COLOR=RED]60[/COLOR]   40-[COLOR=RED]65[/COLOR]
                B       A
                
                        [U][B][COLOR=BLUE]65[/COLOR][/B][/U]-90   65-80
                        B       A
                        
                                90-105  80-102
                                B       A
                                
                                        105-127 102-120
                                        B       A
                                                
                                                127-145
                                                B

Here we see that for two instructions it actually takes 5 cycles longer for a pipelined execution path than a non-pipelined one. However, if we keep inserting instructions...

STAGE   1       2       3       4       5       6       DONE
LENGTH  20      20      25      15      22      18
TIME    0-20
        A
        
        20-40   20-40
        B       A
        
                40-60   40-65
        C       B       A
        
                        65-90   65-80
        D       C       B       A
        
                                90-105  80-102
        E       D       C       B       A
        
                                        105-127 102-120
        F       E       D       C       B       A
        
                                                127-145
        -       F       E       D       C       B
                                                
        -       -       F       E       D       C
        


        -       -       -       F       E       D


        -       -       -       -       F       E


        -       -       -       -       -       F

Once you fill up the pipeline and are using every stage at the same time, the speed gain is apparent.

Since this is homework I'll let you figure out the execution times for yourself, but alas the average is not 2.5 ns per instruction.

[Apprentice123]

Sothe gain will be approximately equal to the number of stages

Gain = 6

I'm Correct?

Edited by Apprentice123, 27 November 2011 - 07:29 AM.

[dargueta]

No. Did you calculate the timings? The speed gain factor isn't a whole number.

[Apprentice123]

dargueta said:

No. Did you calculate the timings? The speed gain factor isn't a whole number.

How will I calculate the timings if Ido not have the number of instructions?

[dargueta]

For calculations like this you only need to use enough instructions to fill the pipeline. Since there are six stages in this pipeline, use six instructions. For a twelve-stage pipeline, use twelve instructions, etc. Just fill in the blanks in the diagram I posted earlier.

[Apprentice123]

dargueta said:

For calculations like this you only need to use enough instructions to fill the pipeline. Since there are six stages in this pipeline, use six instructions. For a twelve-stage pipeline, use twelve instructions, etc. Just fill in the blanks in the diagram I posted earlier.

OK. I did not know that use instructions to fill the pipeline.
My solution:

Without Pipeline:
6 instructions * 12ns (time per instruction) = 72ns

With Pipeline:
12 + (5 * 2.5) = 24.5ns

Gain = 72 / 24 = 2.93

It is?

[dargueta]

2.94 (rounding error). Yes, that's correct. So what's the new average execution time for an instruction?