state machine implementation (similar states)

Discussion in 'VHDL' started by Enno Luebbers, Sep 7, 2005.

  1. Hi there,

    I'm currently implementing a processor cache in VHDL. There are the
    obvious states IDLE, READ_HIT, READ_MISS, READ_MISS_DIRTY, WRITE_HIT,
    WRITE_MISS, WRITE_MISS_DIRTY.

    The *_DIRTY states are responsible for writing back the cacheline
    contents to RAM before reading the new cacheline. So they essentially
    do the same (i.e. generate the same output signals), except that
    WRITE_MISS_DIRTY transitions to WRITE_MISS after writing back, and
    READ_MISS_DIRTY transitions to READ_MISS.

    So my question is: Is it more efficient to merge the two *_DIRTY states
    into one and reserve an additional state_next register to hold the
    state to transition to, or just duplicate the states?

    The benefits of merging the states would seem to be:
    - reduced number of states
    - simpler logic for generating the "write back" signals
    - only one place to change the write back code

    On the other hand, there's the drawbacks:
    - another state register

    Did I miss something here? What's the "right" way to do this?

    Thanks in advance,
    Enno
     
    Enno Luebbers, Sep 7, 2005
    #1
    1. Advertising

  2. Enno Luebbers

    Ben Jones Guest

    Hi Enno,

    > So my question is: Is it more efficient to merge the two *_DIRTY states
    > into one and reserve an additional state_next register to hold the
    > state to transition to, or just duplicate the states?
    > Did I miss something here? What's the "right" way to do this?


    Of course, there is no "right" way. :)

    Depending on how the synthesis tool chooses to encode the state machine,
    there's probably not very much to choose between the two in terms of
    efficiency. Indeed, a good synthesis tool should notice the opportunity to
    simplify the "write-back" signal logic, and do whatever it has to.

    Really, it is more a question of style. Keeping the "dirty" bit separate
    from the state machine is basically keeping state implicitly, which can
    often lead to confusion. In particular: is the contents of the "dirty" bit
    meaningful when you're not in the READ_MISS or WRITE_MISS state? If not,
    then the existing state machine is probably a better expression of the
    logical behaviour of your circuit than the merged version.

    If you are dead keen on efficiency, you could probably attach some attribute
    to your state vector to specify the encoding yourself, and stipulate
    explicitly that there will be a bit which is '1' when in a DIRTY state and
    '0' otherwise. I wouldn't recommend that, though, unless you're desperate -
    it can lead to maintenance nightmares.

    Sounds like at least you're thinking about the right things, which is always
    encouraging on this group. :)

    Cheers,

    -Ben-
     
    Ben Jones, Sep 7, 2005
    #2
    1. Advertising

  3. Hi Ben,

    > > So my question is: Is it more efficient to merge the two *_DIRTY states
    > > into one and reserve an additional state_next register to hold the
    > > state to transition to, or just duplicate the states?
    > > Did I miss something here? What's the "right" way to do this?


    > Really, it is more a question of style. Keeping the "dirty" bit separate
    > from the state machine is basically keeping state implicitly, which can
    > often lead to confusion. In particular: is the contents of the "dirty" bit
    > meaningful when you're not in the READ_MISS or WRITE_MISS state? If not,
    > then the existing state machine is probably a better expression of the
    > logical behaviour of your circuit than the merged version.


    I'm not sure if I got that right. The dirty-bit is stored together with
    the cache line in block ram. It's actually state information for the
    cacheline, not for the state machine that's controlling the reading and
    writing from/to the cache. So it has a meaning even when I'm in some
    other state; it marks the corresponding cache line as dirty.

    I'll try giving some simplified VHDL'ish example to clarify what I
    meant:

    -- First with separate states
    process(clk)
    [...]
    case state is
    when IDLE =>
    [...]
    when READ_FROM_RAM =>
    [...]
    when WRITE_TO_RAM =>
    [...]
    when READ_MISS =>
    if dirty = '1' then -- if cacheline is dirty
    state <= READ_MISS_DIRTY; -- write it back
    else
    state <= READ_FROM_RAM; -- otherwise read the new one
    end if;
    [...]
    when WRITE_MISS =>
    if dirty = '1' then
    state <= WRITE_MISS_DIRTY; -- see above
    else
    state <= WRITE_TO_RAM;
    end if;
    [...]
    when READ_MISS_DIRTY; -- almost equals WRITE_MISS_DIRTY
    write_back <= '1';
    -- do something else
    state <= READ_FROM_RAM; -- except for this
    end if;
    [...]
    when WRITE_MISS_DIRTY; -- almost equals READ_MISS_DIRTY
    write_back <= '1';
    -- do something else
    state <= WRITE_TO_RAM; -- except for this
    end if;
    [...]


    -- Or with a merged _DIRTY state
    process(clk)
    [...]
    case state is
    when IDLE =>
    [...]
    when READ_FROM_RAM =>
    [...]
    when WRITE_TO_RAM =>
    [...]
    when READ_MISS =>
    if dirty = '1' then
    state <= MISS_DIRTY;
    state_next <= READ_FROM_RAM; -- set next state
    else
    state <= READ_FROM_RAM;
    end if;
    [...]
    when WRITE_MISS =>
    if dirty = '1' then
    state <= MISS_DIRTY;
    state_next <= WRITE_TO_RAM; -- set next state
    else
    state <= WRITE_TO_RAM;
    end if;
    [...]
    when MISS_DIRTY; -- merged
    write_back <= '1';
    -- do something else
    state <= state_next; -- "jump"
    end if;
    [...]

    This is somehow like pushing the return address of a function onto the
    stack in C programs; and for some reason I don't feel comfortable with
    that. On the other hand, it allows me to change the write_back
    behaviour on one place (MISS_DIRTY) instead of two (READ_MISS_DIRTY and
    WRITE_MISS_DIRTY).

    The more I think about it, the more it appears to be a purely academic
    questions - both versions do work. ;)

    By the way, thanks for the quick response.

    Best regards,
    Enno
     
    Enno Luebbers, Sep 7, 2005
    #3
  4. Enno Luebbers

    Ben Jones Guest

    Hi Enno,

    > > Really, it is more a question of style. Keeping the "dirty" bit separate
    > > from the state machine is basically keeping state implicitly, which can
    > > often lead to confusion.

    > I'm not sure if I got that right. The dirty-bit is stored together with
    > the cache line in block ram.


    Oops, my bad. I should have chosen my words more carefully. The "dirty bit"
    I was refering to is really the equivalent of your "state_next" variable.
    You'll notice that state_next only ever has two values - so it is really
    representable by a single bit (you don't need to store the whole state
    vector). After I posted that, I realised it would probably be confusing
    since there will be "dirty" bits associated with the cache lines.

    > The more I think about it, the more it appears to be a purely academic
    > questions - both versions do work. ;)


    I think you're right. :) But I think your feeling of discomfort at the idea
    of "hiding" this state information in a secondary variable is probably
    justified - it means you now have to look in two places for the current
    state of the system, rather than just one.

    You might want to ask yourself if the extra cycle on misses (when you go
    through your "dirty" state or states) is really necessary. For example,
    could you do:

    when READ_MISS =>
    if dirty = '1' then
    write_back <= '1';
    end if;
    state <= READ_FROM_RAM;
    [...]
    when WRITE_MISS =>
    if dirty = '1' then
    write_back <= '1';
    end if;
    state <= WRITE_TO_RAM;

    That makes the problem go away completely (although the write_back behaviour
    is still specified in two places). However, it might not be possible.

    In any case, good luck with your project!

    Cheers,

    -Ben-
     
    Ben Jones, Sep 7, 2005
    #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.
Similar Threads
  1. David Lamb
    Replies:
    1
    Views:
    715
  2. nilavya

    State Machine Implementation

    nilavya, Dec 7, 2005, in forum: C++
    Replies:
    6
    Views:
    667
    Neil Cerutti
    Dec 7, 2005
  3. Amit
    Replies:
    6
    Views:
    689
    Symon
    Nov 6, 2007
  4. Mark

    state machine implementation

    Mark, Dec 9, 2010, in forum: C Programming
    Replies:
    4
    Views:
    470
    Jorgen Grahn
    Dec 11, 2010
  5. fenster
    Replies:
    3
    Views:
    1,198
    jeppe
    Dec 23, 2011
Loading...

Share This Page