fifo reading

[revkarol]

Hi,

I'm trying to solve this issue with reading a fifo.

I've an FSM which decides whether to read the next item in the fifo. Let's make the assumption that the fifo is never empty.

I want to decide what to do with each element based on its contents. For now let's assume the elements are just 1 bit long. I have two input fifos (A and B ) and two output ports (X and Y).


Here's the proposed functionality:
If the element is '0', put it in X, if it's '1', put it in Y. With this logic, if both elements are the same I can only read one of them but if they're different I can read both.

I can explain the problem with just one fifo.
Let's say the A fifo is like this (and we read off the end):

A : 0 1 1 0


Here's the problem:

t | A | action
=========================
0 | 0 | set X <= A, set A_read
1 | 0 | X gets value of A, A_read goes high, unset A_read
2 | 1 | set Y <= A, A_read goes low, set A_read
3 | 1 | Y gets value of A, A_read goes high, unset A_read

At t=1 A_read is still low and the fifo doesn't move along. Only at t=2 does is it high. So I'm reading at half the speed I want to.

This smells like a classic problem, but I'm a bit of a noob.

Any help would be appreciated.

Regards,
Karol.

 

[GaborSzakacs]

Hi,

I'm trying to solve this issue with reading a fifo.

I've an FSM which decides whether to read the next item in the fifo. Let's make the assumption that the fifo is never empty.

I want to decide what to do with each element based on its contents. For now let's assume the elements are just 1 bit long. I have two input fifos (A and B ) and two output ports (X and Y).


Here's the proposed functionality:
If the element is '0', put it in X, if it's '1', put it in Y. With this logic, if both elements are the same I can only read one of them but if they're different I can read both.

I can explain the problem with just one fifo.
Let's say the A fifo is like this (and we read off the end):

A : 0 1 1 0


Here's the problem:

t | A | action
=========================
0 | 0 | set X <= A, set A_read
1 | 0 | X gets value of A, A_read goes high, unset A_read
2 | 1 | set Y <= A, A_read goes low, set A_read
3 | 1 | Y gets value of A, A_read goes high, unset A_read

At t=1 A_read is still low and the fifo doesn't move along. Only at t=2 does is it high. So I'm reading at half the speed I want to.

This smells like a classic problem, but I'm a bit of a noob.

Any help would be appreciated.

Regards,
Karol.

Normally I would sort the data into two separate streams at the input,
and then write the appropriate FIFO. If you have data from two sources,
either of which can go to either output on a word by word basis, then
it may make sense to have a first set of FIFO's (one per source) that
takes each data word with its destination tag and then a second set of
FIFO's (one per destination) that feed the outputs. At the interface
between the upstream (source) and downstream (destination) FIFO's you
read and sort as quickly as possible, preferably running this
intermediate data path at a higher clock rate to allow for cases where
data comes in "clumps" for the same destination. The downstream
FIFO's should be longer than the expected clumps to prevent starving
the other destination.

 

[alb]

Hi Karol,

On 03/10/2013 11:17, revkarol wrote:
[]

I've an FSM which decides whether to read the next item in the fifo.
Let's make the assumption that the fifo is never empty.

IMO that's a very strong assumption which can prevent an easy
modification of your further reasoning if it fails to be true.

[]

Here's the proposed functionality: If the element is '0', put it in
X, if it's '1', put it in Y.

Meaning you are willing to either lose half of the data or go at half of
the speed according to data content. The first scenario does not violate
your 'never empty' assumption, while it is not the case for the second
one, unless your inputs are running at half the frequency your outputs
can run at.

With this logic, if both elements are
the same I can only read one of them but if they're different I can
read both.

I'm curious to know in your mind what will be the value of X when all
data should go to Y. If you have all '1', X will be '0'?

I can explain the problem with just one fifo. Let's say the A fifo is
like this (and we read off the end):
A : 0 1 1 0
Here's the problem:

t | A | action
=========================
0 | 0 | set X <= A, set A_read
1 | 0 | X gets value of A, A_read goes high, unset A_read
2 | 1 | set Y <= A, A_read goes low, set A_read
3 | 1 | Y gets value of A, A_read goes high, unset A_read

At t=1 A_read is still low and the fifo doesn't move along. Only at
t=2 does is it high. So I'm reading at half the speed I want to.

If you spend one clock cycle to read the fifo and one clock cycle to
evaluate whether your value should go in X or Y then yes, you are going
half of the speed.

You could instead read the fifo every cycle and combinatorially decide
whether your output is of one kind or another:

<code>
X <= A(p) and B(p); -- at least one '0' produces a '0'
Y <= A(p) or B(p); -- at least one '1' produces a '1'
</code>

Where p is the pointer to your data in the fifo.

That is assuming that X (and respectively Y) will have a '1' when none
of the bits is zero. You can add a registered output if you wish so.

This smells like a classic problem, but I'm a bit of a noob.

HTH,

Al

 

[revkarol]

Hi Gabor, Al,

Thanks for the quick responses. Certainly food for thought.


Al: I know the fifo will be empty sometimes. I just thought it would be easier for explanation to make the assumption that it's not. In the long run I think congestion will be my main issue, rather than what to do when idle.

Gabor: I think you're right that I need a faster write on the output. So probably a dual-clock fifo is the solution.

Karol.