3
\$\begingroup\$

Let's consider an algorithm (for instance encryption) that has 8 strictly identical steps (the output is used as input of the next step).

Considering that I have enough resources to put 8 "step-modules" on my board I'm wondering what are the advantages of doing it as a pipeline (8 modules connected in line with some buffers in between) or as 8 separated modules (with a loop on itself via multiplexer and buffer).

If I have a one input port to give the data to encrypt the performance should not change, the overall latency and the throughput will be the same.

schematic

simulate this circuit – Schematic created using CircuitLab

On the top: the pipeline, below the parallel (considering only 2 times through the "step-module" and omitting the buffers)

Is there any significant difference?

Further exploration: what if I have not enough space for 8 modules (but maybe only 7) or for more than 8 (maybe 9)?

\$\endgroup\$
  • 1
    \$\begingroup\$ I think you ought to draw up your example as a block diagram. \$\endgroup\$ – Andy aka Nov 27 '15 at 14:45
  • \$\begingroup\$ I believe those two block diagrams you have drawn don't achieve the same result. Maybe the encryption block in the 2nd diagram is not the same as the first diagram? \$\endgroup\$ – Andy aka Nov 27 '15 at 14:58
  • \$\begingroup\$ It depends on what the "Encryption Module" actually does. If it is truly pipelined, you would only use one (assuming the modules are the same in both diagrams), and then simply feed each input through it in turn. This massively reduces logic consumption at the expense of bandwidth (you can only feed one word in at a time). In the parallel one you use far more logic, but you can feed multiple words in at a time. If you can clarify a bit, I'll write this up as an answer. \$\endgroup\$ – Tom Carpenter Nov 27 '15 at 14:58
  • \$\begingroup\$ I'm confused by your diagram - you seem to be saying that to process a stream of data (in chunks) you can run data thru a single module 8 times by "looping" OR by "cascading" modules. If that is the crux of your question then why show all the input and output logic in scenario B - you have shown a loop around the modules in scenario B and surely that is enough OR maybe I'm getting it all wrong? \$\endgroup\$ – Andy aka Nov 27 '15 at 15:07
  • \$\begingroup\$ No need to delete the question, just edit in the extra information as a second part at the end. \$\endgroup\$ – Tom Carpenter Nov 27 '15 at 15:58
6
\$\begingroup\$

You have a module which must process the data multiple times in a row to complete the conversion. In the 'pipelined' example, you simply feed through each in turn. This will have some latency as the data takes some time to go from the input to the output. However if the blocks are truly pipelined, this is just a latency - you can feed in a new data word on each cycle, and there will be multiple samples in the pipeline stage at any given point allowing for the same throughput in the end.

Your 'parallel' case isn't really a parallel case. It is basically the same pipelined case, but instead of sticking them one after another, you end up with extra logic to distribute the incoming data to each block, and then presumably each block has more logic to feed its output back through itself enough times to complete the conversion. At the end you then have to recombine them all. It is basically an ugly method of doing a pipelined calculation.

I am not sure where you get the idea that your pipeline must have 2,4,8,16 units? If you need to process the data through the module 7 times, you would simply stick 7 in a row in the pipeline - each one operates on the output of the last so it doesn't matter if it isn't a power of two length.


A truly parallel version, would be one where the calculation can be split into partial operations. Say for example you wanted to multiply two 16bit numbers, but only had an 8x8 multipler block which takes one clock cycle to complete. You could stick 4 in series and have some accumulation (this would be a pipelined operation), or you could add multiple instances of the multiplier and put them in parallel. In parallel the result would have 1 clock cycle latency, in pipelined (series) it would have 4 cycles latency. This comes at the cost of using 4 times as much logic.

Another example of true parallel behaviour is if you need to process multiple words at once, and faster than one block could handle. Say you had a block which took a data word and encrypted it. The block can only handle one word at its input in each clock cycle. Now what if your incoming data stream consists of four words which arrive all in the same clock cycle, but your encryption block can only handle one at a time. The throughput of the encryption module is 1/4 of what is required. Now if you put four blocks in parallel, you can now process each of the four words at the same time allowing for the required throughput - again at the expense of requiring four times as much logic.


There is one case where the second approach is actually justified. Say you need to process each word through the calculation stage 8 times, but because of the size of the calculation, you only have room in the FPGA for say, 3 passes, then you would need a way to reuse resource. You are trying to break the calculation to use fewer blocks.

In this situation, yes, having logic to feed back through the same block multiple times is quite advantageous. This allows you to reuse the same module and so much less logic resources to process the calculation. However this comes at the expense of throughput. If you need to feed the same data word through the same block 8 times, then your throughput is reduced to one eighth - because while you are doing that, no new words can enter the block.

Having room for additional blocks (say 3) would allow you to perform the calculation in parallel for three data words at a time. You instantiate three copies of your single block circuit and add some additional logic to determine when it is time for a new word to enter each of the blocks. This in turn gains back some performance - it is now 3/8ths of what it was.


I can update the answer with some diagrams if needed, but hopefully the explanation is fairly clear.

\$\endgroup\$
  • \$\begingroup\$ @oliverpool I think my point is the "ugly" method doesn't help at all, there is no benefit to doing it that way - in fact it consumes more logic and is a massive debugging headache. \$\endgroup\$ – Tom Carpenter Nov 27 '15 at 15:34
  • 2
    \$\begingroup\$ @oliverpool there is NO benefit. Both arrangements have exactly the same pipeline delay and exactly the same throughput. The only difference is one has a load of extra logic for multiplexing. \$\endgroup\$ – Tom Carpenter Nov 27 '15 at 15:40
  • \$\begingroup\$ Your last comment should actually replace your answer (as it exactly answer my question - which was previously not well asked) \$\endgroup\$ – oliverpool Nov 27 '15 at 15:52
  • \$\begingroup\$ @oliverpool see my edit. \$\endgroup\$ – Tom Carpenter Nov 27 '15 at 15:57
0
\$\begingroup\$

In simple words, a single pipeline will only do ONE thing at a time. If you have modules in series, each module will then have to wait for the previous module to complete.

Since all steps are identical, this will only be an issue until the pipeline is full.

If it's done in parallel, this initial penalty will be negated.

\$\endgroup\$
-1
\$\begingroup\$

Here are the differences that I can think of (after writing the question and editing it according to the comments):

The parallel version will need more logic (multiplexers) to dispatch the input and keep trace of how many times the data went through the module already.

But the parallel version also supports an arbitrary* number of "step-module" (e.g. 7 of 9) whereas the pipeline is not so flexible (strictly dependent on the algorithm requirements).

*considering that my algorithm requires 8 steps, but my FPGA has maybe only place for 7 (or 9) step-modules, I can do 7 (or 9) parallel versions and the throughtput will be increased accordingly.

\$\endgroup\$
  • 1
    \$\begingroup\$ The last paragraph is wrong. Completely wrong. I don't understand why you think you can't have an arbitrary number of modules in the first design. \$\endgroup\$ – Tom Carpenter Nov 27 '15 at 15:41
  • \$\begingroup\$ Why not? Just put three modules one after another. \$\endgroup\$ – Tom Carpenter Nov 27 '15 at 15:45
  • \$\begingroup\$ You're edit has just completely changed the question. If I were you I'd delete this answer and copy it all into the question. \$\endgroup\$ – Tom Carpenter Nov 27 '15 at 15:47
  • \$\begingroup\$ Why has this answer been downvoted? It has more or less the same content as @TomCarpenter (and was posted before...) \$\endgroup\$ – oliverpool Nov 27 '15 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.