When to FIFO

A FIFO is a memory which acts like a buffer type queue on say an A/D before processing.
Under what circumstances do we need one versus the data just coming straight from the A/D and into processing? Or is it good practice to always use a FIFO.

On 13.02.2013 13:07, gyansorova@gmail.com wrote:
> A FIFO is a memory which acts like a buffer type queue on say an A/D before processing.
> Under what circumstances do we need one versus the data just coming straight from the A/D and into processing? Or is it good practice to always use a FIFO.
>
1. when the processing block can't take data at regular intervals of 
time. For example, if you look into a hardware reference manual on a 
digital signal processor you'll see that external sources are interfaces 
to internal buses through internal FIFOs even when the clocks are 
derived from the same master clock, cause one can't guarantee that data 
words/samples will be served as soon as they are ready due to multiple 
devices being connected to the buses.
2. when the master clocks on the a-to-d conversion and processing sides 
are derived from different sources (so-called cross-domain crossing, CDC)

These are just two examples that came to my mind. But there are cases 
when one can avoid using a FIFO, as well.

-- 

Alexander

On 2/13/13 5:23 AM, Alexander Sotnikov wrote:
> On 13.02.2013 13:07, gyansorova@gmail.com wrote:
>> A FIFO is a memory which acts like a buffer type queue on say an A/D
>> before processing.
>> Under what circumstances do we need one versus the data just coming
>> straight from the A/D and into processing? Or is it good practice to
>> always use a FIFO.
>>
> 1. when the processing block can't take data at regular intervals of
> time. For example, if you look into a hardware reference manual on a
> digital signal processor you'll see that external sources are interfaces
> to internal buses through internal FIFOs even when the clocks are
> derived from the same master clock, cause one can't guarantee that data
> words/samples will be served as soon as they are ready due to multiple
> devices being connected to the buses.

but that only needs to be one sample deep.  no?

> 2. when the master clocks on the a-to-d conversion and processing sides
> are derived from different sources (so-called cross-domain crossing, CDC)

is that asynchronous sample rate conversion?



for the OP:

if your process *requires* block processing (like if an FFT is in 
there), then a FIFO buffer is necessary.

sometimes block processing is *desirable* but not necessary.  if you 
want to structure your DSP code to process blocks of samples at a time, 
often with your intermediate signals also in blocks, then FIFO buffering 
on *both* the input (A/D) and the output (D/A) will be necessary.

buffering causes delay.  if you put a buffer on both input and output, 
but processes these blocks naturally, where processes that happen 
earlier in the signal chain are executed earlier chronologically, then 
the added delay from this block processing is two blocks.  that delay 
will impose limits to how big of a block you can get away with.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

On Wed, 13 Feb 2013 11:44:08 -0500
robert bristow-johnson <rbj@audioimagination.com> wrote:

> On 2/13/13 5:23 AM, Alexander Sotnikov wrote:
> > On 13.02.2013 13:07, gyansorova@gmail.com wrote:
> >> A FIFO is a memory which acts like a buffer type queue on say an A/D
> >> before processing.
> >> Under what circumstances do we need one versus the data just coming
> >> straight from the A/D and into processing? Or is it good practice to
> >> always use a FIFO.
> >>
> > 1. when the processing block can't take data at regular intervals of
> > time. For example, if you look into a hardware reference manual on a
> > digital signal processor you'll see that external sources are interfaces
> > to internal buses through internal FIFOs even when the clocks are
> > derived from the same master clock, cause one can't guarantee that data
> > words/samples will be served as soon as they are ready due to multiple
> > devices being connected to the buses.
> 
> but that only needs to be one sample deep.  no?
> 

It needs to be as deep as it needs to be.  A FIFO represents an
averaging filter on throughput, in both the input and output
directions.  If either of those is peaky rather than constant, then the
amount of FIFO that you need is a function of just how peaky.

We do a 16-channel x 500 ksps A/D board with 1K FIFO on each channel,
with the expectation that the end user has a periodic task that goes
through, channel by channel, grabbing as much data is available from
that FIFO at that time.  This allows for pretty extreme peakiness; the
FIFO counts wind up looking like sawtooth waves, but it allows the user
to pull data using efficient DMA transfers rather than pokey
single-word transfers. 

-- 
Rob Gaddi, Highland Technology -- www.highlandtechnology.com
Email address domain is currently out of order.  See above to fix.

On Wed, 13 Feb 2013 01:07:02 -0800, gyansorova wrote:

> A FIFO is a memory which acts like a buffer type queue on say an A/D
> before processing.
> Under what circumstances do we need one versus the data just coming
> straight from the A/D and into processing? Or is it good practice to
> always use a FIFO.

It's not really a digital signal processing question as such, more of a 
general real-time computing.

So the answer is: when it makes sense.  When the cost of being able to 
respond to the ADC at its speed is high, and the cost of the delay 
involved in waiting for the ADC output is low, then it makes sense to use 
a FIFO.  If you read "is impossible" as being "the cost is infinitely 
high" then you can pretty much apply the above statement to _any_ yes/no 
decision on using a FIFO.

The reasons already given are just special cases where the immediate 
response to the ADC is high cost (or impossible).

Another specific, that I end up using often: you can use a FIFO as a 
handy way of reducing the number of times you need to call an ISR.  
Interrupts take clock ticks for the context change, so ISRs don't come 
for free.  Storing up a set number of ADC conversions in a FIFO, then 
interrupting so you can suck them out in a bunch, can increase the 
overall throughput that you can attain with a given processor.

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

On 2/13/13 12:40 PM, Rob Gaddi wrote:
> On Wed, 13 Feb 2013 11:44:08 -0500
> robert bristow-johnson<rbj@audioimagination.com>  wrote:
>
>> On 2/13/13 5:23 AM, Alexander Sotnikov wrote:
>>> On 13.02.2013 13:07, gyansorova@gmail.com wrote:
>>>> A FIFO is a memory which acts like a buffer type queue on say an A/D
>>>> before processing.
>>>> Under what circumstances do we need one versus the data just coming
>>>> straight from the A/D and into processing? Or is it good practice to
>>>> always use a FIFO.
>>>>
>>> 1. when the processing block can't take data at regular intervals of
>>> time. For example, if you look into a hardware reference manual on a
>>> digital signal processor you'll see that external sources are interfaces
>>> to internal buses through internal FIFOs even when the clocks are
>>> derived from the same master clock, cause one can't guarantee that data
>>> words/samples will be served as soon as they are ready due to multiple
>>> devices being connected to the buses.
>>
>> but that only needs to be one sample deep.  no?
>>
>
> It needs to be as deep as it needs to be.

i think i understand.  it's just "block processing" as i had described, 
but it is forced upon us because "the processing [device] can't take 
data at regular intervals of time" because it is busy with some other tasks.

> A FIFO represents an averaging filter on throughput, in both the input
> and output directions.  If either of those is peaky rather than constant,
> then the amount of FIFO that you need is a function of just how peaky.

i had understood that, too.  for block processing.


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

One reason that many modern dsp's like to use lots of FIFO's is that the memory bandwidth is low compared to the core speed, and it can't keep up with stream-oriented processing. You can get around this by having lots of registers that are coupled to the multiplier, and pre-load these registers from memory, and then do a bunch of calculations for aparticular sub-algorithm at once, before moving on to the next sub-algorithm.


Bob

On 2/13/13 2:46 PM, radams2000@gmail.com wrote:
> One reason that many modern dsp's like to use lots of FIFO's is that the memory bandwidth is low compared to the core speed,

yup.

> and it can't keep up with stream-oriented processing.

what, exactly, do you mean here?  i think i understand what "keeping up" 
is, but i don't understand exactly what is behind "not keeping up" and 
"keeping up" regarding the buffering of samples.  (other than an often 
*small* amount of efficiency regarding overhead gained when processing 
samples in blocks, and *that* is processor specific.  i don't think we 
can get one of your Sigmas to process samples in blocks, even if we 
wanted to.)

> You can get around this by having lots of registers that are coupled to the multiplier, and pre-load these registers from memory, and then do a bunch of calculations for a particular sub-algorithm at once, before moving on to the next sub-algorithm.


Bob, is this not what we call "pipelining" of the instruction execution?

just trying to decode what we are all talking about.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

Robert

 Many modern processors have full register files connected directly to the multiplier inputs, and the assumption is that you load up these registers with coefficients or other values that will be used repeatedly, and then execute that algorithm repeatedly so that the setup/tear-down overhead of the register files is amortized over the largest number of input samples possible.  That's why the benchmark results for, say, a single biquad filter is much worse than the benchmark results for 10 biquad filters. It also depends on whether the memory can supply data and coefficient in a single cycle or whether you need multiple accesses. 

This style is also enforced by many modern C compilers, and you would need to code in assembl to get around this. 

These processors are often the variety that combine micro-controller features with some dsp capability, rather than dedicated dsp processors. I prefer dsp's that don't work this way, but it does seem to be a trend. 


Bob

On 2/13/13 9:09 PM, radams2000@gmail.com wrote:
> Robert
>
>   Many modern processors have full register files connected directly to the multiplier inputs, and the assumption is that you load up these registers with coefficients or other values that will be used repeatedly, and then execute that algorithm repeatedly so that the setup/tear-down overhead of the register files is amortized over the largest number of input samples possible.  That's why the benchmark results for, say, a single biquad filter is much worse than the benchmark results for 10 biquad filters. It also depends on whether the memory can supply data and coefficient in a single cycle or whether you need multiple accesses.
>
> This style is also enforced by many modern C compilers, and you would need to code in assembl to get around this.
>
> These processors are often the variety that combine micro-controller features with some dsp capability, rather than dedicated dsp processors. I prefer dsp's that don't work this way, but it does seem to be a trend.
>
>
> Bob


-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."