fifo reading

Discussion in 'VHDL' started by revkarol, Oct 3, 2013.

  1. revkarol

    revkarol Guest

    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.
    revkarol, Oct 3, 2013
    #1
    1. Advertising

  2. revkarol

    GaborSzakacs Guest

    revkarol wrote:
    > 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.

    --
    Gabor
    GaborSzakacs, Oct 3, 2013
    #2
    1. Advertising

  3. revkarol

    alb Guest

    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
    alb, Oct 3, 2013
    #3
  4. revkarol

    revkarol Guest

    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.

    On Thursday, 3 October 2013 11:17:23 UTC+2, revkarol wrote:
    > 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.
    revkarol, Oct 7, 2013
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.

Share This Page