UPGRADE YOUR BROWSER

We have detected your current browser version is not the latest one. Xilinx.com uses the latest web technologies to bring you the best online experience possible. Please upgrade to a Xilinx.com supported browser:Chrome, Firefox, Internet Explorer 11, Safari. Thank you!

cancel
Showing results for 
Search instead for 
Did you mean: 
Highlighted
Scholar helmutforren
Scholar
3,839 Views
Registered: ‎06-23-2014

Verilog Moore vs Mealy machine Simulation misbehavior?

Jump to solution

I'm using Vivado 2017.1.  I'm using SystemVerilog.

 

I've known lots about Moore and Mealy machines for almost 40 years.  I'll synopsize right now by saying that if I code a Moore machine, then the outputs depend only on the state.  But if I code a Mealy machine, then the outputs depend on both the state and the inputs.

 

I haven't been coding them for Xilinx or in [System]Verilog nearly so long.  I've encountered a simulation behavior that doesn't make sense to me.

 

I'm using a two-always-blocks coding method that I'll generalize as follows:

typedef enum bit [1:0] { IDLE, WAIT, GET} t_STATE;
t_STATE current_state, next_state;

typedef struct packed { logic data } t_DATA;
t_DATA current_data, next_data;

always @(posedge clk) begin
    if (rst) begin
        current_state = IDLE;
        current_data = 0;
    end else begin
        current_state <= next_state
        current_data <= next_data
    end
end

always @* begin
    next_state = current_state; // Default to keep old state, unless overridden below
    next_data = current_data; // Default to keep old data, unless overridden below

    case (current_state)
    IDLE: next_state = WAIT;
    WAIT: next_state = GET;
    GET: begin
        if (!fifo.empty) begin
            next_data = 1;
next_state = IDLE; end end endcase end

This is a Mealy machine because of the "if (!fifo.empty)" statement.  NOTE THERE IS MORE CODE IN REAL SITUATION, BUT NO OTHER ACCESSES TO "next_data".  (Note I realize I am not only changing the output in response to an input, but also changing the state in that same if block.)

 

Here's what's happening in simulation that confuses me.  I set a breakpoint inside the GET state.  I run my simulation.  It stops at this breakpoint.  I single step forward and in my waveform window I see next_data become 1.  I am now expecting that at the next clock, current_data will become 1.  But it doesn't.  So I repeat my simulation.  After next_data becomes 1, I set a breakpoint at every access of next_data and current_data, including the two places inside the first always and the two places inside the second always.  I single step through to the end of the always block.  next_data remains 1. But now the simulation has exited these always blocks and I must click the run icon in order to get to one of my breakpoints.  When I do so, the simulation comes back to the first always block, with @(posedge clk), exactly as I expected.  However, next_data is no longer 1.  OUTSIDE of all of my code, next-data has gone from 1 to 0.  I don't know how this is happening.

 

So, I start to doubt myself with regard to the "@*" in the second always block.  I remove the "next_data = current_data;" setting as default.  Now, while I do have some X's in the waveform, indeed I discover that next_data persists as 1 when I get back into my first always block, and current_data is successfully set to 1.

 

This behavior is confusing.  On one hand, it seems like the "@*" is causing the block to execute at an unexpected time, possible due to the Mealy nature of my machine -- when one of those other inputs I didn't put in this post example changes.  Doing this, the default has reset next_data back to zero.  HOWEVER, this shouldn't be the case, because I had breakpoints all over the place in that always block, including the default set, and the simulation didn't stop on one.

 

So what's going on?  

 

Since I'm coding a Mealy machine, do I need to not use the defaults method, and explicitly set every output for every state value in my case statement?  Even if that's NOT the problem here, is that wise if I continue to do Mealy machines? 

 

Or is something else going on?  You know, I've seen all kinds of misbehavior related to typedefs and structs.  Is it a bug?

 

Thanks in advance for your advice.

 

EDIT(1): No, I shouldn't have to not use the defaults method.  Note I duplicated them into every state case, and that 1 still goes to 0.  Furthermore, I realized that the current_state shouldn't change until the first always is executed.  So if the second always runs again for some other funny input change reason, it should produce the same result, of next_data=1.  So it doesn't seem to be my coding method.  Again, is it a bug?

 

EDIT(2): I put in parallel with current_data and next_data a single bit reg variable that doesn't involve the typedef or struct.  It does the same thing, going back to 0 between simulation of the second always block and the first always block.  So this shouldn't bre a typedef or struct issue.  So what's up?  I don't understand.

 

-Helmut

 

 

0 Kudos
1 Solution

Accepted Solutions
Historian
Historian
6,172 Views
Registered: ‎01-23-2009

Re: Verilog Moore vs Mealy machine Simulation misbehavior?

Jump to solution

The problem is your real code (which you didn't copy into your simplified code).

 

In your always @* the line does not say

 

next_data = current_data;

 

it says

 

next_data <= current_data;

 

This non-blocking assignment gets deferred to the end of the time tick - after the blocking assignment that does next_data = 1.

 

This is why your signal goes back to a 0 - it does it due to the completion of the deferred assignment.

 

Avrum

Tags (2)
0 Kudos
6 Replies
Historian
Historian
3,806 Views
Registered: ‎01-23-2009

Re: Verilog Moore vs Mealy machine Simulation misbehavior?

Jump to solution

OK - first. If the only place that next_data goes is into the clocked process that says "current_data <= next_data" then this is a Moore machine.

 

In a Mealy machine, the inputs affect the outputs combinatorially. If the only "outputs" of this state machine are current_state and current_data, then this is a Moore machine. That being said, the definition of Mealy and Moore are somewhat unimportant here - that has nothing to do with your problem.

 

It is very hard to follow exactly what you are seeing, but it sounds like you have a race condition on the fifo.empty.

 

Let's say that while you are in the GET state, FIFO.empty is 0 - this will result in next_data going to 1. 

 

Now lets look at what happens during the time when clock rises. If either

  - fifo.empty doesn't change on the rising edge of the clock or

  - fifo.empty does change, but only using a non-blocking assignment (i.e. <=)

then when the always @(posedge clk) occurs, the current_data will be set to a 1. From what you are seeing, neither of these are happening.

 

However, if fifo.empty does change to a 1, different things can happen depending on how the change occurs:

  - if fifo.empty changes before the time tick of the rising edge of clock (by any amount), then the alwyas @* will execute again, and next_data will return to 0. At the rising edge of clock current_data will stay a 0

      - however, you would probably be able to see this in the waves if this was the case

  - if fifo.empty changes "at the same time" as the rising edge of clock, then it matters how the change of fifo.empty is done:

      - if the fifo.empty change is done with a non-blocking assignment (NBA), then the change in fifo.empty is guaranteed to be evaluated after all active processes, which includes the posedge clk, so current_data will go to 1

         - again, based on your description, this is not happening

      - if the fifo.empty change is done with a blocking assignment (in an active process), then we have a race - either of the two active processes may go first

          -  if the posedge clk goes first, then current_data will go to a 1

          - if the always @*  goes first, then next_data will return to a 0. Then when the posedge clk goes, current_data will remain a 0

 

So you need to look at what is happening to fifo.empty...

 

Finally (and this is just style) all the assignments, including the reset assignments, in your always @(posedge clk) should use NBAs - the blocking assignments in the resets are probably harmless, but are not the way this should be coded...

 

Avrum

 

Tags (4)
0 Kudos
Scholar helmutforren
Scholar
3,767 Views
Registered: ‎06-23-2014

Re: Verilog Moore vs Mealy machine Simulation misbehavior?

Jump to solution

@avrumw,

 

Thanks for picking up this thread.

 

 

Note, the blocking assignments in the first always rst were a TYPO.  They are indeed NBA's.

 

So I'm thinking through the FIFO.empty race condition question.  I agree with your paragraph of why current_data would be set to 1.

 

However, I put a breakpoint on ALL of the sections of code as well as the germane detail lines.  The block and the detail line 

next_data = current_data; // Default to keep old data, unless overridden below

is NOT being executed.  The whole race condition concept requires that this line get executed in order to set next_data back to zero.  The simulator stops there beforehand, but between then and the next stop, the simulator does NOT stop there.  Shouldn't the simulator stop as the code

 

Here is the code again, with NBA forum typo fixed "<=" in red.  I've added [1] [2] etc for where I put breakpoints:

typedef enum bit [1:0] { IDLE, WAIT, GET} t_STATE;
t_STATE current_state, next_state;

typedef struct packed { logic data } t_DATA;
t_DATA current_data, next_data;

always @(posedge clk) begin
[1] if (rst) begin
[2]     current_state <= IDLE;
[3]     current_data <= 0;
    end else begin
[4]     current_state <= next_state
[5]     current_data <= next_data
    end
end

always @* begin
[6] next_state = current_state; // Default to keep old state, unless overridden below
[7] next_data = current_data; // Default to keep old data, unless overridden below

    case (current_state)
    IDLE: next_state = WAIT;
    WAIT: next_state = GET;
    GET: begin
[8]     if (!fifo.empty) begin
[9]         next_data = 1;
next_state = IDLE; end end endcase end

So, In the beginning, I have only breakpoint [9].  The simulator stops there.  I single step and then see next_data becomes 1.  Then I go and set the other breakpoints [1] through [8]. (Breakpoints [1] [2] [4] [6] [8] represent the beginning of code blocks, and remember there's certainly unrelated code in there.  Breakpoints [3] [5] [7] [9] cover all places next_data or current_data are accessed.)  

 

I *continue* single stepping toward the endcase.  Register next_data remains 1.  When I step past the endcase (actually, the last stop was at an unrelated "if" that doesn't go inside, and the simulator doesn't stop at the "end" or "endcase"), the blue pointer goes to the beginning of that whole (the @*) always block.  But this isn't a stop for the simulator.  It just puts the blue arrow there while it's simulating other code in other modules.  To get back to a line in this module, I then tell the simulator to run.  Remember, I have all those breakpoints [1] through [9].  Before I click on run, the simulator still reports next_data as 1.  But when I click on run, the next simulator stop is at  breakpoint [1].  I immediately look at next_data in the waveform, and the "Value" column has a zero.  It's as if "next_data" got changed by the code that got executed (simulated) outside of this module.  Well, this can happen in regular sequential programming such as "C", but it should not be possible in this hardware programming.  Furthermore, if there was a race condition causing the always @* to run again and causing the line at breakpoint [7] to execute, the simulator would have stopped at breakpoints [6] and [7] first, which it did NOT.

 

I am trying to upload a video...  (EDIT: worked, see attachment) Company policy won't let me share the project.  But I think I can get away with showing you a video.  You can see EXACTLY what happens:

  • Time 0:00:05 -- next_note_REL_test has been set to 1.  (This corresponds to "next_data" in my original post.)  I then single step.
  • Time 0:00:11 -- single stepping has looped back to put the blue pointer at "always @* begin".  Then I set more breakpoints.  Note in the waveform at right that next_note_REL_test (highlighted) remains 1.
  • Time 0:00:29 -- I have finished setting breakpoints in the "always @* begin" block and begin setting more in the "always (@posedge clk) begin" block. 
  • Time 0:00:53 -- I am about to press run, but I do not yet.  I go point out that net_note_REL_test in the waveform is still showing a 1.  I realize this might not be updated while the simulation is outside this module.  But even if it's just leftover from the last time code in this module was simulated, it's showing that this was still a 1.
  • Time 0:01:06 -- Finally I go press run.
  • Time 0:01:09 -- Immediately you can see that next_note_REL_test has gone to 0.  It's as if it changed outside of my module.  The breakpoint hit was inside the "always (@posedge clk) begin" block, exactly as expected.  I didn't continue the video, but had I single stepped, it would have gone into the rst else clause and set note_REL_test to 0 from next_note_REL_test that was SEEMINGLY ERRONEOUSLY 0.

So the big point here is to look at the time span between 0:01:06 and 0:01:09.  next_note_REL_test goes from 1 to 0 *without* going through any code that touches next_note_REL_test.  How can this be?

 

EDIT: Here's the declaration:

reg note_REL_test, next_note_REL_test;

 

 

P.S. Regarding Moore vs Mealy, I apologize for leaving out the code to make it obvious.  Inside that "if (!fifo.empty)" is additional code that goes to output.  This makes the machine overall a Mealy machine.  HOWEVER, if one looks at the design in pieces, you're correct.  The piece dealing with current_data and next_data is indeed a Moore machine.  I didn't see that before because I knew of the full code.  But in this reduction of the example, the Moore aspect of this piece is exposed.  I wouldn't belabor this point except that the fact that this piece is a Moore machine means that I shouldn't get race conditions through to the output.  (Of course, the output isn't shown.  Whatever.  I'm done with this paragraph).

 

EDIT: ATTACHMENT REMOVED BY ORIGINAL POSTER.

 

0 Kudos
Historian
Historian
6,173 Views
Registered: ‎01-23-2009

Re: Verilog Moore vs Mealy machine Simulation misbehavior?

Jump to solution

The problem is your real code (which you didn't copy into your simplified code).

 

In your always @* the line does not say

 

next_data = current_data;

 

it says

 

next_data <= current_data;

 

This non-blocking assignment gets deferred to the end of the time tick - after the blocking assignment that does next_data = 1.

 

This is why your signal goes back to a 0 - it does it due to the completion of the deferred assignment.

 

Avrum

Tags (2)
0 Kudos
Scholar helmutforren
Scholar
3,739 Views
Registered: ‎06-23-2014

Re: Verilog Moore vs Mealy machine Simulation misbehavior?

Jump to solution

Zip-a-dee-doo-dah, zip-a-dee-ay
My, oh, my, what a wonderful day
Plenty of sunshine headin' my way
Zip-a-dee-doo-dah, zip-a-dee-ay!

 

Thanks, the unexpected behavior now makes perfect sense with the defered NBA that shouldn't have been NBA.  It was cloning error from the @posedge clk section.  I type them all there, copy them, move "next_" from RHS to LHS of operator, forgot to change operator.  I really need to add double checking my operators to my debug checklist.

Helmut

0 Kudos
Historian
Historian
3,722 Views
Registered: ‎01-23-2009

Re: Verilog Moore vs Mealy machine Simulation misbehavior?

Jump to solution

I know you have Mealy outputs, and the two process state machine can be a convenient way of coding Mealy state machines (the next state and outputs can be coded together), but this is a good example of why many people prefer the one process state machine. In the one process state machine, the "copy paste" that you do from one process to the other wouldn't exist - less code means less possibility for error...

 

Avrum

0 Kudos
Scholar helmutforren
Scholar
3,684 Views
Registered: ‎06-23-2014

Re: Verilog Moore vs Mealy machine Simulation misbehavior?

Jump to solution

Avrum,

 

I really wanted to ask you one additional question, and I will in a moment.  But first, I'd like to reply to your one-process comment.

 

I've been doing Xilinx FPGA's for two years now.  Up until recently, I used only one always block.  I believe that my method was consistent with the standard that of which you're thinking.  All assignments were non-blocking (<=); there were no blocking assignments (=).  While I'm excellent with logical thinking, it still took a lot of thinking to get complex systems to work (even after subdividing the systems to make them more simple).  Then, it took a long time to debug them, due to subtle nuances.

 

Then last month I did some independent studying, including coming across these two papers by Clifford E. Cummings:

 

http://www.sunburst-design.com/papers/CummingsICU2002_FSMFundamentals.pdf (2002, easier to read)

https://pdfs.semanticscholar.org/b4d2/38899ab8ac75a271d3dcc07b595867946b7a.pdf (2003, presumably more up-to-date)

 

Note that Cummings says to avoid the one-always block style with registered outputs.  That's what I had been doing.  [He] described the difficulties with it, which were exactly coincident with what I was experiencing.  I considered what Cummings said in this paper, and thought that the three-always block could be easily reduced to a two-always block.  I tried the two-always block, and made it Mealy rather than Moore.  Subsequently, I found that my design time on individual modules was cut as much as in half.  My debugging time was cut in half, too.  Of course, I ran into a couple snafu's, such as with this post.  But once I learn the common errors, I should be able to easily recognize and avoid those.  (Such as, when a simulation variable seems to change outside the always block, look for a deferred assignment due to an NBA.)  Even with that recent difficulty, the two-always block technique has already proven much faster and easier to debug.  It also looks like it's going to be less likely to have hidden errors revealed in the future.  The ease of design and debugging leave things much more understandable.  This means there is less likelihood of an unforeseen situation and error to be discovered in the future.

 

With the above said, please allow me to move to my follow-up questions:

 

FIRST, LOTS OF SETUP FOR MY QUESTION:

 

All of my projects to date have dealt heavily with FIFO use.  I've been using FWFT FIFOs and I like it.  (No, I'm not really a Katy Perry fan!)  Previously, it was actually rather complex within a module to read one input FIFO, process data, and write it to one output FIFO.  This was especially true if you wanted to keep up the highest bandwidth possible, as opposed to only reading/writing every other clock cycle.  Then, with my new two-always block Mealy machine method, I find that I can do this very simply:

  1. (All in the combinational block, with blocking assignments)...
  2. Default InputFIFO.rd_en = 1, and default OutputFIFO.wr_en=0.
  3. Check if (!InputFIFO.empty) as well as (!OutputFIFO.prog_full), where I make sure prog_full leaves enough margin for all of my processing after this point.
  4. Do my processing and set data output OutputFIFO.dout and override OutputFIFO.wr_en=1.
  5. Note that if it was InputFIFO.empty, then I override InputFIFO.rd_en=0 so as not to "consume" that input yet.

The above is definitely Mealy, with OutputFIFO.wr_en happening in response to !InputFIFO.empty.  It also allows IN A SINGLE CLOCK CYCLE for the decision and write to occur.  There's no looking at the last clock cycle and predicting the next clock cycle, as was required with the single always block method.  It's SOOOO much more simple.  I know the single always block may seem simple at first, but once you get complications of a real system, it gets more difficult.  This two-always block style with Mealy outputs remains extremely simple.  

 

And when the data processing can't be done in a single clock cycle, I've done the job with two state machines.  My input state machine transfers data to holding registers.  Then my output state machine does the multi-clock processing of the holding registers and then writes to the output FIFO.  The two state machines communicate with a data_ready and done done_flag.  As already mentioned, I make sure that prog_full is far enough below full, that once the input stage commits after looking at the output prog_full, there's enough free space in the output FIFO to hold all of the processing that the output stage is going to push out.  (That is, note that the module may input one FIFO word but output many.)

 

FINALLY, MY QUESTION:

 

I wonder about race conditions and slow timing flowing through multiple modules using this Mealy technique.  In theory, because the Mealy output changes with the input, one could have an indefinite number of modules linked together and an indefinite length of combinational logic without an intervening register.    This could definitely make it difficult to meet timing requirements, and I can image that it might lead to race conditions.

 

HOWEVER, between every module is a FIFO.   The Mealy input-to-output path is strictly associated with FIFO controls of empty, rd_en, prog_full, and wr_en.  I ****believe**** that all of these are "registered" signals.  Therefore, that indefinite number of modules liked together ****does**** have intervening registers between every module.  Therefore I should NOT be getting into a problem of slow timing or race conditions.

 

Do you agree?  Or am I misunderstanding something here.  Aside from possibly slow arrival to the module of InputFIFO.empty or OutputFIFO.prog_full, I believe that those signals, once arrived, will not change again until the next clock edge.  If not actually, they behave as if they're generated by NBAs.  In addition, my InputFIFO.rd_en and OutputFIFO.wr_en signals that I generate will ****not**** actually be used until the clock edge.  In fact, one way to look at this is that, if the InputFIFO and OutputFIFO are considered inside my "black box" along with my state machine, then the "black box" is actually a Moore machine, even though my state machine inside the "black box" appears to be a Mealy Machine.

 

Thanks very much,

Helmut

0 Kudos