iverilog-devel

[Iverilog-devel] Verilog execution of always block as multiple events

[Julian T. P. <jtp...@uw...>]

This isn't an issue with iverilog, but I have a question about the
execution semantics of Verilog. There isn't much information online
and a lot of it points to this mailing list
(e.g. https://sourceforge.net/p/iverilog/mailman/message/36358575/)
so I'm hoping it's alright if I ask here.

In 1364-2005, section 11.4.2 includes the following sentence (which
is also present in SystemVerilog): "Another source of nondeterminism
is that statements without time-control constructs in behavioral
blocks do not have to be executed as one event."

As an example, it presents the following:

  assign p = q;
  initial begin
      q = 1;
      #1 q = 0;
      $display(p);
  end

The simulator is allowed to process the "q = 0" assignment, then
suspend execution in favour of updating p, and then display p as 0.

Does this also apply to the typical style of always process used
to express combinatorial circuits ?

For example, if someone were to implement an and gate using a
temporary variable:

  always @(a or b) begin
      temp = a & b;
      c = temp;
  end

Say a and b both have pending update events. Could the simulator
update a, see that the always has been activated, execute
"temp = a | b;", then suspend execution to update b ? At which
point the always block is not sensitive to changes because it is
still being executed, so it ends up missing the second update even
though b is in the sensitivity list.

Is this valid behavior according to the standard ? Or does
"statements without time-control constructs" apply to the
"begin end" block as a whole and prevent it from being executed as
multiple events because it does have a time-control ? If this is
valid, do iverilog or other simulators ever behave in this manner ?


Thanks,

-Julian

Re: [Iverilog-devel] Verilog execution of always block as multiple events

[Stephen W. <st...@ic...>]

This is an interesting problem, and has come down to an unwritten rule
that sequential statements are executed without interruption until
they voluntarily yield by a time or event statement. Many people who
tried to implement multi-threaded Verilog simulators have discovered
this assumption the hard way. The problem is that Verilog has no
thread synchronization primitives other than the time and event
controls, and so every Verilog programmer has used these controls
exactly that way. So:

always @(a or b) begin
  temp = a & b;
  c = temp;
end

Once this thread is started, it will run, uninterrupted, until it gets
to the @(...) statement, which yields the CPU.

Now, it can also be pointed out that this is technically only a single
statement. The @(a or b)... is a single statement that has as a
sub-statement a begin..end block. People don't usually think about it
that way, but it is technically true.

On Sat, May 16, 2020 at 3:05 PM Julian Thomas Parkin
<jtp...@uw...> wrote:
>
> This isn't an issue with iverilog, but I have a question about the
> execution semantics of Verilog. There isn't much information online
> and a lot of it points to this mailing list
> (e.g. https://sourceforge.net/p/iverilog/mailman/message/36358575/)
> so I'm hoping it's alright if I ask here.
>
> In 1364-2005, section 11.4.2 includes the following sentence (which
> is also present in SystemVerilog): "Another source of nondeterminism
> is that statements without time-control constructs in behavioral
> blocks do not have to be executed as one event."
>
> As an example, it presents the following:
>
>   assign p = q;
>   initial begin
>       q = 1;
>       #1 q = 0;
>       $display(p);
>   end
>
> The simulator is allowed to process the "q = 0" assignment, then
> suspend execution in favour of updating p, and then display p as 0.
>
> Does this also apply to the typical style of always process used
> to express combinatorial circuits ?
>
> For example, if someone were to implement an and gate using a
> temporary variable:
>
>   always @(a or b) begin
>       temp = a & b;
>       c = temp;
>   end
>
> Say a and b both have pending update events. Could the simulator
> update a, see that the always has been activated, execute
> "temp = a | b;", then suspend execution to update b ? At which
> point the always block is not sensitive to changes because it is
> still being executed, so it ends up missing the second update even
> though b is in the sensitivity list.
>
> Is this valid behavior according to the standard ? Or does
> "statements without time-control constructs" apply to the
> "begin end" block as a whole and prevent it from being executed as
> multiple events because it does have a time-control ? If this is
> valid, do iverilog or other simulators ever behave in this manner ?
>
>
> Thanks,
>
> -Julian
>
>
> _______________________________________________
> Iverilog-devel mailing list
> Ive...@li...
> https://lists.sourceforge.net/lists/listinfo/iverilog-devel



-- 
Steve Williams                "The woods are lovely, dark and deep.
st...@ic...              But I have promises to keep,
http://www.icarus.com         and lines to code before I sleep,
http://www.picturel.com       And lines to code before I sleep."

Re: [Iverilog-devel] Verilog execution of always block as multiple events

[Cary R. <cy...@ya...>]

 
In a multi threaded simulator this is certainly possible unless it has created some kind of dependency graph. Most/maybe all single threaded simulators and icarus specifically will execute the currently running process until it reaches some kind of time statement (the @ in this code) before switching to the next process. The order of the processes running is not deterministic, though most simulators use a FIFO queue so there is some known determinism for a specific simulator.
It would require a well controlled seed for repeatability, but I always thought pulling a random element from the queue would over many regressions find most timing races that people code, but never get bitten by since their simulator has at least some determinism.
Cary
    On Saturday, May 16, 2020, 3:05:26 PM PDT, Julian Thomas Parkin <jtp...@uw...> wrote:  
 
 This isn't an issue with iverilog, but I have a question about the
execution semantics of Verilog. There isn't much information online
and a lot of it points to this mailing list
(e.g. https://sourceforge.net/p/iverilog/mailman/message/36358575/)
so I'm hoping it's alright if I ask here.

In 1364-2005, section 11.4.2 includes the following sentence (which
is also present in SystemVerilog): "Another source of nondeterminism
is that statements without time-control constructs in behavioral
blocks do not have to be executed as one event."

As an example, it presents the following:

  assign p = q;
  initial begin
      q = 1;
      #1 q = 0;
      $display(p);
  end

The simulator is allowed to process the "q = 0" assignment, then
suspend execution in favour of updating p, and then display p as 0.

Does this also apply to the typical style of always process used
to express combinatorial circuits ?

For example, if someone were to implement an and gate using a
temporary variable:

  always @(a or b) begin
      temp = a & b;
      c = temp;
  end

Say a and b both have pending update events. Could the simulator
update a, see that the always has been activated, execute
"temp = a | b;", then suspend execution to update b ? At which
point the always block is not sensitive to changes because it is
still being executed, so it ends up missing the second update even
though b is in the sensitivity list.

Is this valid behavior according to the standard ? Or does
"statements without time-control constructs" apply to the
"begin end" block as a whole and prevent it from being executed as
multiple events because it does have a time-control ? If this is
valid, do iverilog or other simulators ever behave in this manner ?


Thanks,

-Julian


_______________________________________________
Iverilog-devel mailing list
Ive...@li...
https://lists.sourceforge.net/lists/listinfo/iverilog-devel
  

Re: [Iverilog-devel] Verilog execution of always block as multiple events

[Douglas S. <dc...@tr...>]

Julian,

In the case you mention, the always block will finish the update due to 
a changing, and then activate again because b changed. If we say that a 
changes from a0 to a1, and b changes from b0 to b1, then c will change 
from a0 & b0 to a1 & b0, and then to a1 & b1.

And since it could have updated b before the assignment to temp, it 
could have gone from a0 & b0 directly to a1 & b1. Since you are not 
specifying any delays here, I assume that a and b are changing "at the 
same time" (but not the same simulator cycle), so of course b could be 
the one to trigger the always block, giving a different intermediate 
state for c.

I remember someone saying "Time is natures way of ensuring that 
everything doesn't happen all at once." In verilog, time is the only way 
to ensure sequencing of signals: you can't assume the order of signals 
changing at the same time, and verilog will remain at that time 
(re-triggering any always blocks, gates, assign statements ...) until no 
more events are scheduled for that time.

Doug Sojourner

On 05/16/20 13:55, Julian Thomas Parkin wrote:

This isn't an issue with iverilog, but I have a question about the
execution semantics of Verilog. There isn't much information online
and a lot of it points to this mailing list
(e.g. https://sourceforge.net/p/iverilog/mailman/message/36358575/)
so I'm hoping it's alright if I ask here.

In 1364-2005, section 11.4.2 includes the following sentence (which
is also present in SystemVerilog): "Another source of nondeterminism
is that statements without time-control constructs in behavioral
blocks do not have to be executed as one event."

As an example, it presents the following:

   assign p = q;
   initial begin
       q = 1;
       #1 q = 0;
       $display(p);
   end

The simulator is allowed to process the "q = 0" assignment, then
suspend execution in favour of updating p, and then display p as 0.

Does this also apply to the typical style of always process used
to express combinatorial circuits ?

For example, if someone were to implement an and gate using a
temporary variable:

   always @(a or b) begin
       temp = a & b;
       c = temp;
   end

Say a and b both have pending update events. Could the simulator
update a, see that the always has been activated, execute
"temp = a | b;", then suspend execution to update b ? At which
point the always block is not sensitive to changes because it is
still being executed, so it ends up missing the second update even
though b is in the sensitivity list.

Is this valid behavior according to the standard ? Or does
"statements without time-control constructs" apply to the
"begin end" block as a whole and prevent it from being executed as
multiple events because it does have a time-control ? If this is
valid, do iverilog or other simulators ever behave in this manner ?


Thanks,

-Julian


_______________________________________________
Iverilog-devel mailing list
Ive...@li...
https://lists.sourceforge.net/lists/listinfo/iverilog-devel

Re: [Iverilog-devel] Verilog execution of always block as multiple events

[Julian T. P. <jtp...@uw...>]

Thanks for the explanations everyone, very helpful.

Would I be correct in summarizing this as, the standard doesn't
strictly require an always block to run uninterrupted until it
suspends on its own, but there's a lot of inertia behind the
assumption that it does (an "unwritten rule" as Steve calls it) to
the point that it's a safe assumption to make when writing Verilog.


-Julian

________________________________
From: Julian Thomas Parkin <jtp...@uw...>
Sent: Saturday, May 16, 2020 4:55 PM
To: ive...@li... <ive...@li...>
Subject: [Iverilog-devel] Verilog execution of always block as multiple events

This isn't an issue with iverilog, but I have a question about the
execution semantics of Verilog. There isn't much information online
and a lot of it points to this mailing list
(e.g. https://sourceforge.net/p/iverilog/mailman/message/36358575/)
so I'm hoping it's alright if I ask here.

In 1364-2005, section 11.4.2 includes the following sentence (which
is also present in SystemVerilog): "Another source of nondeterminism
is that statements without time-control constructs in behavioral
blocks do not have to be executed as one event."

As an example, it presents the following:

  assign p = q;
  initial begin
      q = 1;
      #1 q = 0;
      $display(p);
  end

The simulator is allowed to process the "q = 0" assignment, then
suspend execution in favour of updating p, and then display p as 0.

Does this also apply to the typical style of always process used
to express combinatorial circuits ?

For example, if someone were to implement an and gate using a
temporary variable:

  always @(a or b) begin
      temp = a & b;
      c = temp;
  end

Say a and b both have pending update events. Could the simulator
update a, see that the always has been activated, execute
"temp = a | b;", then suspend execution to update b ? At which
point the always block is not sensitive to changes because it is
still being executed, so it ends up missing the second update even
though b is in the sensitivity list.

Is this valid behavior according to the standard ? Or does
"statements without time-control constructs" apply to the
"begin end" block as a whole and prevent it from being executed as
multiple events because it does have a time-control ? If this is
valid, do iverilog or other simulators ever behave in this manner ?


Thanks,

-Julian


_______________________________________________
Iverilog-devel mailing list
Ive...@li...
https://lists.sourceforge.net/lists/listinfo/iverilog-devel

Re: [Iverilog-devel] Verilog execution of always block as multiple events

[Martin W. <ic...@ma...>]

Steve's point that the time control requires the whole begin...end block 
to be executed as a single event does mean that I am wrong and the vvp 
behaviour is broken. See the second example I gave in

https://github.com/steveicarus/iverilog/issues/321#issuecomment-626305761

If update events are not allowed to be executed during the begin...end 
blocks, the wires should never reflect the glitches.

On 16/05/2020 23:52, Stephen Williams wrote:
> This is an interesting problem, and has come down to an unwritten rule
> that sequential statements are executed without interruption until
> they voluntarily yield by a time or event statement. Many people who
> tried to implement multi-threaded Verilog simulators have discovered
> this assumption the hard way. The problem is that Verilog has no
> thread synchronization primitives other than the time and event
> controls, and so every Verilog programmer has used these controls
> exactly that way. So:
> 
> always @(a or b) begin
>    temp = a & b;
>    c = temp;
> end
> 
> Once this thread is started, it will run, uninterrupted, until it gets
> to the @(...) statement, which yields the CPU.
> 
> Now, it can also be pointed out that this is technically only a single
> statement. The @(a or b)... is a single statement that has as a
> sub-statement a begin..end block. People don't usually think about it
> that way, but it is technically true.
> 
> On Sat, May 16, 2020 at 3:05 PM Julian Thomas Parkin
> <jtp...@uw...> wrote:
>>
>> This isn't an issue with iverilog, but I have a question about the
>> execution semantics of Verilog. There isn't much information online
>> and a lot of it points to this mailing list
>> (e.g. https://sourceforge.net/p/iverilog/mailman/message/36358575/)
>> so I'm hoping it's alright if I ask here.
>>
>> In 1364-2005, section 11.4.2 includes the following sentence (which
>> is also present in SystemVerilog): "Another source of nondeterminism
>> is that statements without time-control constructs in behavioral
>> blocks do not have to be executed as one event."
>>
>> As an example, it presents the following:
>>
>>    assign p = q;
>>    initial begin
>>        q = 1;
>>        #1 q = 0;
>>        $display(p);
>>    end
>>
>> The simulator is allowed to process the "q = 0" assignment, then
>> suspend execution in favour of updating p, and then display p as 0.
>>
>> Does this also apply to the typical style of always process used
>> to express combinatorial circuits ?
>>
>> For example, if someone were to implement an and gate using a
>> temporary variable:
>>
>>    always @(a or b) begin
>>        temp = a & b;
>>        c = temp;
>>    end
>>
>> Say a and b both have pending update events. Could the simulator
>> update a, see that the always has been activated, execute
>> "temp = a | b;", then suspend execution to update b ? At which
>> point the always block is not sensitive to changes because it is
>> still being executed, so it ends up missing the second update even
>> though b is in the sensitivity list.
>>
>> Is this valid behavior according to the standard ? Or does
>> "statements without time-control constructs" apply to the
>> "begin end" block as a whole and prevent it from being executed as
>> multiple events because it does have a time-control ? If this is
>> valid, do iverilog or other simulators ever behave in this manner ?
>>
>>
>> Thanks,
>>
>> -Julian
>>
>>
>> _______________________________________________
>> Iverilog-devel mailing list
>> Ive...@li...
>> https://lists.sourceforge.net/lists/listinfo/iverilog-devel
> 
> 
> 

Re: [Iverilog-devel] Verilog execution of always block as multiple events

[Julian T. P. <jtp...@uw...>]

That is an interesting bug report. Assuming that update events
should not be processed during the always block for sanity reasons,
then your second example with the continuous assignment (or the
original report using modules) shouldn't be an infinite loop.

I think your first example without any wires or module ports between
the mutual triggering always blocks should be an infinite loop. The
assignment to 0 should schedule an evaluation event for the other
block, which can't be unscheduled by the assignment to 1. That being
said, I tried it under ModelSim for comparison and it stops looping
after one iteration of unchanged values (i.e. once tmp0 = 1 and
tmp1 = 1, each always block runs one more time), a behavior which I
don't see an explanation for.


-Julian

________________________________
From: Martin Whitaker <ic...@ma...>
Sent: Sunday, May 17, 2020 5:33 AM
To: ive...@li... <ive...@li...>
Subject: Re: [Iverilog-devel] Verilog execution of always block as multiple events

Steve's point that the time control requires the whole begin...end block
to be executed as a single event does mean that I am wrong and the vvp
behaviour is broken. See the second example I gave in

https://github.com/steveicarus/iverilog/issues/321#issuecomment-626305761

If update events are not allowed to be executed during the begin...end
blocks, the wires should never reflect the glitches.

On 16/05/2020 23:52, Stephen Williams wrote:
> This is an interesting problem, and has come down to an unwritten rule
> that sequential statements are executed without interruption until
> they voluntarily yield by a time or event statement. Many people who
> tried to implement multi-threaded Verilog simulators have discovered
> this assumption the hard way. The problem is that Verilog has no
> thread synchronization primitives other than the time and event
> controls, and so every Verilog programmer has used these controls
> exactly that way. So:
>
> always @(a or b) begin
>    temp = a & b;
>    c = temp;
> end
>
> Once this thread is started, it will run, uninterrupted, until it gets
> to the @(...) statement, which yields the CPU.
>
> Now, it can also be pointed out that this is technically only a single
> statement. The @(a or b)... is a single statement that has as a
> sub-statement a begin..end block. People don't usually think about it
> that way, but it is technically true.
>
> On Sat, May 16, 2020 at 3:05 PM Julian Thomas Parkin
> <jtp...@uw...> wrote:
>>
>> This isn't an issue with iverilog, but I have a question about the
>> execution semantics of Verilog. There isn't much information online
>> and a lot of it points to this mailing list
>> (e.g. https://sourceforge.net/p/iverilog/mailman/message/36358575/)
>> so I'm hoping it's alright if I ask here.
>>
>> In 1364-2005, section 11.4.2 includes the following sentence (which
>> is also present in SystemVerilog): "Another source of nondeterminism
>> is that statements without time-control constructs in behavioral
>> blocks do not have to be executed as one event."
>>
>> As an example, it presents the following:
>>
>>    assign p = q;
>>    initial begin
>>        q = 1;
>>        #1 q = 0;
>>        $display(p);
>>    end
>>
>> The simulator is allowed to process the "q = 0" assignment, then
>> suspend execution in favour of updating p, and then display p as 0.
>>
>> Does this also apply to the typical style of always process used
>> to express combinatorial circuits ?
>>
>> For example, if someone were to implement an and gate using a
>> temporary variable:
>>
>>    always @(a or b) begin
>>        temp = a & b;
>>        c = temp;
>>    end
>>
>> Say a and b both have pending update events. Could the simulator
>> update a, see that the always has been activated, execute
>> "temp = a | b;", then suspend execution to update b ? At which
>> point the always block is not sensitive to changes because it is
>> still being executed, so it ends up missing the second update even
>> though b is in the sensitivity list.
>>
>> Is this valid behavior according to the standard ? Or does
>> "statements without time-control constructs" apply to the
>> "begin end" block as a whole and prevent it from being executed as
>> multiple events because it does have a time-control ? If this is
>> valid, do iverilog or other simulators ever behave in this manner ?
>>
>>
>> Thanks,
>>
>> -Julian
>>
>>
>> _______________________________________________
>> Iverilog-devel mailing list
>> Ive...@li...
>> https://lists.sourceforge.net/lists/listinfo/iverilog-devel
>
>
>



_______________________________________________
Iverilog-devel mailing list
Ive...@li...
https://lists.sourceforge.net/lists/listinfo/iverilog-devel

Re: [Iverilog-devel] Verilog execution of always block as multiple events

[Evan L. <sa2...@cy...>]

On 17/05/2020 07:11, Julian Thomas Parkin wrote:
> Thanks for the explanations everyone, very helpful.
> 
> Would I be correct in summarizing this as, the standard doesn't
> strictly require an always block to run uninterrupted until it
> suspends on its own, but there's a lot of inertia behind the
> assumption that it does (an "unwritten rule" as Steve calls it) to
> the point that it's a safe assumption to make when writing Verilog.

Basically, yes, but the unwritten rule is occasionally broken. The
scheduler is event-driven, not pre-emptive; it shouldn't arbitrarily
decide when to transfer control between different processes. But, OTOH,
the LRM does *not* specify atomic execution of code between scheduling
points, and explicitly says in 11.4.1(a) that "Execution of statements
in a particular begin-end block can be suspended in favor of other
processes in the model".

Steven Sharp covered this in comp.lang.verilog at

https://groups.google.com/forum/?hl=en#!topic/comp.lang.verilog/2X9f9ds9XnE

as follows (in other words, this is as Gospel as it gets for Verilog):

"There is the rigamarole about allowing a begin-end to suspend in favor
of executing another process, and then resume later.  If taken to
extremes, this would make the language very hard to use, since many
common practices would become nondeterministic.  This seems to have
been stated partly to allow for simulator optimizations involving
inlining of one process into another.  For example, when an always
block updates a variable, a simulator might immediately update a net
that is assigned from that variable.  This can be viewed as suspending
the always block, executing the continuous assignment, and then
resuming the always block.  But no simulator is going to arbitrarily
suspend one process to execute another, unless there is at least some
kind of event-driven connection between them".

I'm sure this is covered elsewhere in c.l.v, but it's next to useless
now, since Google removed the advanced search.

But not all simulators play ball. See:

https://groups.google.com/forum/#!searchin/comp.lang.verilog/%22STEVEN$20SHARP%22$20scheduler|sort:date/comp.lang.verilog/tK-MpHdfVCE/uGAgIp4BpBIJ

Look up my comment for:

x = add(x, 1);

I found one simulator where this wasn't atomic. This was a long time ago
(2008), and I don't have notes, so I don't know which sim it was.

Re: [Iverilog-devel] Verilog execution of always block as multiple events

[Julian T. P. <jtp...@uw...>]

Thanks for the links. I found this other Steven Sharp comment from
that discussion to be particularly illuminating (referring to trying
to understand the scheduling only by reading the standard, something
which I guess I was guilty of).

"This is a bit dangerous. The section on scheduling semantics was
grafted onto the standard rather late in the process.  It uses
terminology that is not used anywhere else in the standard.  It tries
not to disallow any behavior of Verilog-XL or other simulators of the
time, and in the process allowed so much nondeterminism that it would
be hard to write working Verilog if it were taken too literally."


-Julian

________________________________
From: Evan Lavelle <sa2...@cy...>
Sent: Sunday, May 17, 2020 12:37 PM
To: ive...@li... <ive...@li...>
Subject: Re: [Iverilog-devel] Verilog execution of always block as multiple events

On 17/05/2020 07:11, Julian Thomas Parkin wrote:
> Thanks for the explanations everyone, very helpful.
>
> Would I be correct in summarizing this as, the standard doesn't
> strictly require an always block to run uninterrupted until it
> suspends on its own, but there's a lot of inertia behind the
> assumption that it does (an "unwritten rule" as Steve calls it) to
> the point that it's a safe assumption to make when writing Verilog.

Basically, yes, but the unwritten rule is occasionally broken. The
scheduler is event-driven, not pre-emptive; it shouldn't arbitrarily
decide when to transfer control between different processes. But, OTOH,
the LRM does *not* specify atomic execution of code between scheduling
points, and explicitly says in 11.4.1(a) that "Execution of statements
in a particular begin-end block can be suspended in favor of other
processes in the model".

Steven Sharp covered this in comp.lang.verilog at

https://groups.google.com/forum/?hl=en#!topic/comp.lang.verilog/2X9f9ds9XnE

as follows (in other words, this is as Gospel as it gets for Verilog):

"There is the rigamarole about allowing a begin-end to suspend in favor
of executing another process, and then resume later.  If taken to
extremes, this would make the language very hard to use, since many
common practices would become nondeterministic.  This seems to have
been stated partly to allow for simulator optimizations involving
inlining of one process into another.  For example, when an always
block updates a variable, a simulator might immediately update a net
that is assigned from that variable.  This can be viewed as suspending
the always block, executing the continuous assignment, and then
resuming the always block.  But no simulator is going to arbitrarily
suspend one process to execute another, unless there is at least some
kind of event-driven connection between them".

I'm sure this is covered elsewhere in c.l.v, but it's next to useless
now, since Google removed the advanced search.

But not all simulators play ball. See:

https://groups.google.com/forum/#!searchin/comp.lang.verilog/%22STEVEN$20SHARP%22$20scheduler|sort:date/comp.lang.verilog/tK-MpHdfVCE/uGAgIp4BpBIJ

Look up my comment for:

x = add(x, 1);

I found one simulator where this wasn't atomic. This was a long time ago
(2008), and I don't have notes, so I don't know which sim it was.


_______________________________________________
Iverilog-devel mailing list
Ive...@li...
https://lists.sourceforge.net/lists/listinfo/iverilog-devel

Re: [Iverilog-devel] Verilog execution of always block as multiple events

[Evan L. <sa2...@cy...>]

Yes, interesting stuff - it surprises me that anyone ever managed to
write a Verilog simulator. The second edition of Thomas and Moorby's
book (1995) doesn't appear to have a single mention of the scheduler.