Any good resource - understanding pipeline

[nesta]

Hi friends,

Typical problem
------------------
For an output y = a + cy(n-1)
Design a system y to compute using a 3-stage pipeline adders.


I am not exactly looking for any answer for this question, However
I want to know which is the best book to understand on pipeline problems (synthesis diagrams)
like the one mentioned above. I am not able to find one.

Please help me with some resources which will deal more with such
kind of problems and explanations mainly on pipeline stages using adders/multipliers.

Thanks in advance.
Nesta

 

[atulaxc]

There is a page on pipeline thats helps in general. Pipeline processing. In pipeline we basically divide the data processing into stages and push the inputs in a sequence through each stage.

 

[permute]

pipelining generally works well for systems with limited to no feedback, or when the feedback has certain qualities.

addition and multiplication are common operations that are somewhat complex. Multiplexing also can be a difficult operation due to routing issues. If we assume that multiplications and additions take 2ns each, then the operation:
y = a*c + b*d would take 4ns -- a*c and b*d are computed, then the sum is computed.

However, if 500MHz is required, then pipelining can be done. in that case, registers are placed after a*c and b*d. this gives:
yac <= a*c
ybd <= b*d
y <= yac + ybd
if a,b,c,d = 1,1,1,1 on cycle 1, 1,2,3,4 on cycle 3, and 1,3,5,7 on cycle 3:
1,1,1,1 -- yac <= 1, ybd <= 1, y <= 0 (yac and ybd are assumed to be equal to zero at the start of the cycle)
1,2,3,4 -- yac <= 2, ybd <= 12, y <= 1 (using the yac = ybd = 1 from the start of the cycle)
1,3,5,7 -- yac <= 3, ybd = 15, y <= 14 (using yac =2, ybd = 12)
0,0,0,0 -- yac <= 0, ybd = 0, y <= 18 (using yac = 3, ybd = 15)

Thus the design computes 1 new output per cycle, but has a latency of 1 additional cycle before the output is computed. this is similar to an assembly line that can produce 1000 items per hour, but requires an hour before any items have completed all stages of production.

The problem: y[n] = a*y[n-1] + b*x[n] is much more difficult. for example, the response for x[n] = 1, 2, 3 is b, a*b+2b, a^2*b+2a*b+3b
if ya = a*y, yb = b*x[n], y = ya+yb:
cycle 1, ya = 0, yb = b. y = 0 (waiting for ya, yb)
cycle 2, ya = 0, yb = 2b. y = b
cycle 3, ya = a*b, yb = 3b, y = 2b
cycle 4, ya = 2*a*b, yb = 0, y = a*b + 3b
notice that the values after pipelining no longer line up! this is because the value "y" is delayed by an additional cycle, but is needed on the next cycle. This type of problem can sometimes be solved, for example if a = 1 the problem can be solved (think about the logic for each bit of the addition).

Likewise, individual operations can be pipelined. A 32b addition could be broken into two 16b additions with carry in.

 

[yadog]

In hardware the function of pipeline is implemented by inserting registers in the combinational logic. Long combinational path tends to cause low maximum frequency. If there is critical path in your design, you can use the pipeline to insert registers in the long combinational path to shorten it. Then the timing performance will be improved.

so the basic function of pipeline is to optimize timing performance ,and the weapon is registers.

Just a clue for you!

 

[mrflibble]

On that subject, any good books on designing + HDL best practices for pipelines? The "what is a pipeline" I get. But there are still plenty challenges I encounter during pipeline design, that I'd really like to read a good book/paper/website about.

For an example of the things I mean ... Even the basic stuff like, how do you partition your pipeline into seperate modules etc. Say I have a pipeline that can be split into 5 stages. Then I make 5 modules, 1 for each stage. Then I make a 6th module that contains those 5. Seems reasonable to me, but maybe there's some clever reason to do thing another way.

Right now I maintain hierarchy for those modules, so I can find my signals in a testbench. But again, maybe that actually thought about this a bit longer came up with a better and more general solution. In which case it would be nice to learn of this solution.

Or stuff like processing time series in parallel, although that gets into the realm of DSP real quick...

Anyways, more info on pipeline design would be very much welcome!

 

[atulaxc]

There is not much to pipeline processing, quick reference Pipeline processing

 

[mrflibble]

There is not much to pipeline processing, quick reference Pipeline processing

Yeah, I noticed that one in the earlier post. There is also not much to boolean logic, yet books abound on the applications.