state machine implementation (similar states)

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

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

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

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