question about the verilog standard.

[Michael Katelman]

On Apr 8, 11:16 am, Stephen Williams <spamt...@icarus.com> wrote:

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

This shows up in the -2001 version of the standard as well. I do
not know of any simulator that interrupts a behavioral process at
any time other then at time control constructs. To do so would cause
utter chaos.

The problem is that the atomicity of execution is the only form
of synchronization that a Verilog programmer has. Without it,
cycle-based simulation would be nearly impossible. No compiler
intentionally violates that atomicity, and in the few cases where
Icarus Verilog did, I was handed a plate full of bug reports.

You'll have to ask some committee members why that paragraph is
there, but I think you will find that all the Verilog simulator
implementers are careful to not interrupt execution outside of
timing constructs. If you think you've found an instance, then
please do tell.



hairyotter wrote:
Thank you everybody for all the insights, I am finding this very
interesting as well.

However, I think I might use some clarification.

using the example above:

initial begin
a = 1;
b = 1;
end

always @(a or b) begin
 x = a + b;
 y = a + b;
end

As already reported, the verilog standard (11.4.2 in 1364-2005)
explicitly states that execution can be suspended, and that the order
of interleaved execution is nondeterministic.
However, I have a "problem" with this.
What if, for whatever reason:

- a = 1 is executed and the initial suspended
- the always process is triggered, the x = a+b executed and then the
process suspended
- the initial is resumed, executes b=1, but the always is no longer
listening to a.

End result, x wrong, y correct.

Please note: I do not see a reason in the world why a simulator would
want to do this, it's just that the verilog standard allows for it, so
I'm wondering how would you get out safely.

Thanks, Marco.

- --
Steve Williams                "The woods are lovely, dark and deep.
steve at icarus.com           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."
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.4-svn0 (GNU/Linux)
Comment: Using GnuPG with SUSE -http://enigmail.mozdev.org

iD8DBQFJ3L/ZrPt1Sc2b3ikRAvFsAKCd0rWL3bM1sKS7GWJaDSTXR/94wgCeMlrd
AlRrXvWrwn4bALzv6Gfw4oY> =bvPC
-----END PGP SIGNATURE-----

On Marco's 4-6-2009 7:29 post: This is EXACTLY why I posted
originally, although the standard suggests your x is correct y is
incorrect interpretation is valid, which is equivalent to one of the
cases in my original post, it JUST FEELS "wrong". That is, as if the
standard shouldn't allow it. This is a great thread , it's really
helping me with the work that I'm doing.

Along these lines, Marco and Muzaffer's back-and-forth on

always @(a or b) begin
x = a + b;
end

is really the key question, at least in my mind. If you think of each
always block as having a sort of "program counter", then the question
is where are the legal spots for it to point? If I understand
correctly, Marco's interpretation is that there are two spots, the @(a
or b) and the x = a + b, and Muzaffer is treating the @(a or b) begin
x = a + b end as a single spot. Again, one FEELS like the standard
should not allow x and y to end up with different values, Muzaffer's
interpretation, but Marco's interpretation seems sensible to me based
on 11.4.2 etc.

Honestly, I really don't know what the standard intends here. However,
I was wondering what Marco, Muzaffer, etc. think about the following
sentence from 11.4.2:

"Another source of nondeterminism is that statements without time-
control constructs in behavioral
blocks do not have to be executed as one event."

The subtle thing that I'm wondering about is this: does the above
sentence imply that statements WITH A TIME CONTROL construct must be
executed as a single event? If you look at the syntax definition, @()
begin end is a single statement (A.6.4), while a begin-end block is
defined as a list of statements in the formal syntax ({statement}).

If such a statement must be executed as one event then

@(a or b) begin x = a+b end AND EVEN
@(a or b) begin x = a+b; y = a+b; end

must commit 1 and 2 updates atomically and re-sensitize. Of course,
this also implies that

@(a or b) begin x = a+b; #5 y = a + b; end

must execute as a single event, which doesn't make any sense at all.

All things considered, I tend to agree with the original interleaved
semantics from my first post (and corroborated by others), and I also
agree with Marco's interpretation of

always @(a or b) begin
x = a + b
end

always @(a or b) begin
y = a + b
end

where x and y could differ.

-Mike

ps: I wasn't sure if Steve was commenting specifically on this last
issue?

 

[Michael Katelman]

On Apr 8, 11:31 am, Jason Zheng <Xin.Zh...@jpl.nasa.gov> wrote:

On Fri, 3 Apr 2009 16:08:09 -0700 (PDT)



Michael Katelman <katel...@gmail.com> wrote:
On Apr 3, 5:55 pm, Jason Zheng <Xin.Zh...@jpl.nasa.gov> wrote:
If you read the Verilog standard more carefully, you'll notice that
there is a guarantee that this won't happen. x and y will always be
2 in Verilog. Think of it this way: once a=1 starts, the always
block cannot be triggered until b=1 finishes.

--
And now for something completely different.

Thank your for your demeaning response! However, both the post I
linked and the standard (section 9.9) disagree with your assertion
that the initial block must finish before the always block is
triggered. Who to believe? You have your considerable aplomb, but the
synopsys engineer and standard writers have some authority as well I
SHOULD THINK!

Contrary to your baseless assertion about my knowledge of the
standard, I have spent a considerable amount of time reading it. It's
not the clearest document. The purpose of my post wasn't to get
exasperated answers, but rather some thoughtful justification based on
the language of the standard why it should do what you say, or why it
should do something else. I'm not interested in building hardware
(otherwise I would just write predicatable Verilog) but I am
interested in understanding the semantics at a deeper level.

Mike,

You are right. I was basing on what I thought was on the 1995 standard
which turns out to be false. I didn't mean to make my post demeaning,
however. My apologies.

~Jason

Jason,

No worries. I shouldn't have responded how I did, anyway. It's realize
that it's really hard to interpret someone's tone with email and my
response wasn't professional, sorry about that.

In any case, I am glad that it continues to be an engaging thread .

-Mike

 

[Michael Katelman]

On Apr 8, 1:59 pm, Michael Katelman <katel...@gmail.com> wrote:

On Apr 8, 11:16 am, Stephen Williams <spamt...@icarus.com> wrote:



-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

This shows up in the -2001 version of the standard as well. I do
not know of any simulator that interrupts a behavioral process at
any time other then at time control constructs. To do so would cause
utter chaos.

The problem is that the atomicity of execution is the only form
of synchronization that a Verilog programmer has. Without it,
cycle-based simulation would be nearly impossible. No compiler
intentionally violates that atomicity, and in the few cases where
Icarus Verilog did, I was handed a plate full of bug reports.

You'll have to ask some committee members why that paragraph is
there, but I think you will find that all the Verilog simulator
implementers are careful to not interrupt execution outside of
timing constructs. If you think you've found an instance, then
please do tell.

hairyotter wrote:
Thank you everybody for all the insights, I am finding this very
interesting as well.

However, I think I might use some clarification.

using the example above:

initial begin
a = 1;
b = 1;
end

always @(a or b) begin
 x = a + b;
 y = a + b;
end

As already reported, the verilog standard (11.4.2 in 1364-2005)
explicitly states that execution can be suspended, and that the order
of interleaved execution is nondeterministic.
However, I have a "problem" with this.
What if, for whatever reason:

- a = 1 is executed and the initial suspended
- the always process is triggered, the x = a+b executed and then the
process suspended
- the initial is resumed, executes b=1, but the always is no longer
listening to a.

End result, x wrong, y correct.

Please note: I do not see a reason in the world why a simulator would
want to do this, it's just that the verilog standard allows for it, so
I'm wondering how would you get out safely.

Thanks, Marco.

- --
Steve Williams                "The woods are lovely, dark and deep.
steve at icarus.com           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."
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.4-svn0 (GNU/Linux)
Comment: Using GnuPG with SUSE -http://enigmail.mozdev.org

iD8DBQFJ3L/ZrPt1Sc2b3ikRAvFsAKCd0rWL3bM1sKS7GWJaDSTXR/94wgCeMlrd
AlRrXvWrwn4bALzv6Gfw4oY> > =bvPC
-----END PGP SIGNATURE-----

On Marco's 4-6-2009 7:29 post: This is EXACTLY why I posted
originally, although the standard suggests your x is correct y is
incorrect interpretation is valid, which is equivalent to one of the
cases in my original post, it JUST FEELS "wrong". That is, as if the
standard shouldn't allow it. This is a great thread , it's really
helping me with the work that I'm doing.

oops: that should be x is INCORRECT, y is CORRECT.


-Mike

Along these lines, Marco and Muzaffer's back-and-forth on

always @(a or b) begin
 x = a + b;
end

is really the key question, at least in my mind. If you think of each
always block as having a sort of "program counter", then the question
is where are the legal spots for it to point? If I understand
correctly, Marco's interpretation is that there are two spots, the @(a
or b) and the x = a + b, and Muzaffer is treating the @(a or b) begin
x = a + b end as a single spot. Again, one FEELS like the standard
should not allow x and y to end up with different values, Muzaffer's
interpretation, but Marco's interpretation seems sensible to me based
on 11.4.2 etc.

Honestly, I really don't know what the standard intends here. However,
I was wondering what Marco, Muzaffer, etc. think about the following
sentence from 11.4.2:

"Another source of nondeterminism is that statements without time-
control constructs in behavioral
blocks do not have to be executed as one event."

The subtle thing that I'm wondering about is this: does the above
sentence imply that statements WITH A TIME CONTROL construct must be
executed as a single event? If you look at the syntax definition, @()
begin end is a single statement (A.6.4), while a begin-end block is
defined as a list of statements in the formal syntax ({statement}).

If such a statement must be executed as one event then

@(a or b) begin x = a+b end AND EVEN
@(a or b) begin x = a+b; y = a+b; end

must commit 1 and 2 updates atomically and re-sensitize. Of course,
this also implies that

@(a or b) begin x = a+b; #5 y = a + b; end

must execute as a single event, which doesn't make any sense at all.

All things considered, I tend to agree with the original interleaved
semantics from my first post (and corroborated by others), and I also
agree with Marco's interpretation of

always @(a or b) begin
 x = a + b
end

always @(a or b) begin
 y = a + b
end

where x and y could differ.

-Mike

ps: I wasn't sure if Steve was commenting specifically on this last
issue?

 

[Michael Katelman]

On Apr 6, 7:07 pm, hairyotter <marco.br...@gmail.com> wrote:

Hi Mike,

Just another viewpoint:

I have (and my customers as well) simulations that, at RTL level, take
from several hours to a couple of days EACH.

I agree that if you're just running regressions it might be more
important to run as many as possible in parallel, but when you're
still debugging a testcase, getting to the end as quickly as possible
becomes mandatory.

At the same time, at this point we have 16-core machines easily.
If I could allocate 4 regressions on each machine, ecah taking 4 cores
and speeding up ~4x, the turnaround time of a last-minute ECO would be
much faster, provided management can be convinced to buy enough CPUs

However, it will cost much less to invest in more processing than
waiting a week for the regressions to end.
And if you have no speedup you can have as many machines as you want,
but no speedup.

However, I do not know what percentage of companies do big chips,
let's say > 40Mgates + 100Mbit sram or edram

Ciao, Marco

I would actually be surprised to see at multi-threaded simulator, at
least if the justification is performance. I'd personally rather be
able to use my extra cores to spawn more constrained-random simulation
instances, or whatever, and don't really sit around waiting for single
simulations to finish running. Maybe I'm the exception?

-Mike

To all of the people who commented a few days ago about the single
simulation performance vs total number of simulations: thanks for your
feedback. Clearly it seems that people are more interested in single
simulation performance/interactive debugging than I had thought. I buy
all of your arguments.

-Mike

 

[Chris F Clark]

Muzaffer Kal <kal@dspia.com> writes:

"Another source of nondeterminism is that statements without time-
control constructs in behavioral
blocks do not have to be executed as one event."

The subtle thing that I'm wondering about is this: does the above
sentence imply that statements WITH A TIME CONTROL construct must be
executed as a single event?

I thought about this pretty hard too. I should say that Standardese is
probably my 4th language but I think what it is trying to say is that
"statements with a time control are not subject to this statement at
all" ie if a time control exists there can be no hope of atomicity ie
even the ones without a time control can not be expected to execute as
one event. If there is a time control the scheduler is bound to break
them up and execute them according to the strict requirements of the
time control. If there are none (time controls) one might be inclined
to assume atomicity but they "do not have to be executed as one
event".

As a professional compiler writer, meaning I read language standards
for different languages all the time, I would agree with Muzaffer's
interpretation. In particular, take consider the following variation.

// Please excuse some minor Verilog sytax issues,
// I don't write in this language on a regular basis.

reg [1:0] a,b,c;

initial begin
a = 0;
b = 0;
end

always begin
@a;
b = 3;
end

always begin
@(a,b); // this is a timing control
c = a | b; // this is an executable statement
$display(c); // what does this display for c?
end

Note, the rule about c = a | b; not being atomic applies here. Thus,
you can get displayed for c, any value of 0, 1, 2, 3, 'b0x, 'b1x,
'bx0, 'bx1, 'bxx and still conform to this part of the standard.

Why is this so?

1: The assignment to c moves more than 1 bit and is not required to be
atomic, nor to move the bits in any particular order. the same
applies to the assignments of a and b.

2: There is a race between the two always blocks. Thus, the block
which assigns b may happen at any point relative to the block which
assigns c, including in the middle of the assignment, so that some
bits get moved before and some after.

So, according to my recollection of the standard. At the very beginning, we have all the bits of a[1], a[0], b[1], b[0], c[1], and c[0] as x.

Now, we start moving 0 bits into a. We can do that in either order.
a[0] = 0;
a[1] = 0;
or vice versa.

However, once we've moved the first bit into a[0] or a[1], a has
changed and either of the other two always blocks can start executing
and we can move bits into b and c (in ay order we feel like.

b[0] = 1;
c[1] = a[1] | b[1];
c[0] = a[0] | b[0];
b[1] = 1;

Now, at some point we finish the initial assignment into a, and the first block starts assigning into b;
b[0] = 0;
b[1] = 0;

Simlarly, we finish the assignment into c and the $display of c occurs.

Now, also any order of the above actions can occur. The only
restrictions are that the two assignments in the initial block happend
in order (and are not interleaved) and that the assignment to c
happens before the $display. Otherwise, all bets are off. In fact, I
don't think the standard requires or prohibits the 2nd always block
from firing more than once. Thus, it isn't clear even how many
$display statements this code executes.

In general, most simulators will not be that careless in how they
follow the rules and values like 'b0x will not get output. It is
generally not advantageous for a simulator to do so. Registers 32
bits wide or less, will generally be assigned atomicly. Statements,
will generally execute atomicly. Races will not be resolved by
interleaving the two blocks. Etcetera. However, such interpretations
are legal and they are there to cover the cases that one would not
normally think of. If your bit vector is wide enough, there won't be
a hardware action that moves (or computes) it atomicly. If you want
to build a multi-threaded interpreter, you don't want to have to
synchronize things on a statement by statement basis. If you put
those two things together, you get something that works (in some
case), just as I have described. The standard wants to allow such
implementations, so it warns the user about what not to expcect,
i.e. don't expect atomicity of statements even without timing clause,
don't expecdt blocks to be atomic, and so forth. All of these things
are so that it is possible to build simulators that run fast even on
weird architectures or using novel techniques.

Compiler folks tend to become "language lawyers" because every rule
that they put down about how a language must behave generally means
that some piece of code has to be written to make certain that the
language does behave that way. The more code that has to be written
the more bugs and generally the slower the programs execute. Thus, as
a compiler writer, you want the standard to make as few gaurantees as
possible. It's not that one takes joy in fiding obscure legal
interpretations, but that one's code will naturally find such
interpretations on its own. You want the standard to leave that code
as still correct, so that you don't have to fix it.

Note, I don't normally add my .sig in this group as it isn't relevant,
but in this case it is marginally so.

Hope this helps,
-Chris

******************************************************************************
Chris Clark Internet: christopher.f.clark@compiler-resources.com
Compiler Resources, Inc. or: compres@world.std.com
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

 

[hairyotter]

Thank you everybody for this most interesting thread.
I apologize I could not come back sooner to the discussion.

Coming back to Muzaffer, Michael and Steven comments:

Steven: no, I do not know of any sims where the condition is violated.

I KNOW that the end result is correct; x, y will have the correct
result at the end of the time cycle.

However, I'm trying to reconcile this with the "freedoms" allowed in
the standard.

In VHDL it would be easier: every updated creates a delta-cycle, so it
is very easy to understand how this kind of "re-arming" is
accomplished.

Indeed if you do implement delta cycles it becomes trivial to maintain
coherence.
The first two statements (a=1, b=1) are both executed at "delta = 0"
the next delta goes over all the processes sensitive to a, b and
you're done (it's obviously more complicated than this)

However, verilog does not require this.

Stephen, do you care to comment how you do resolve this in icarus ?

Thanks, Marco.

 

I was not involved in the standards group when this text was added to
the LRM, but have picked up some impressions of what was going on
here.

The LRM started out as the Verilog-XL reference manual. As a user
manual, it didn't describe how the event scheduling worked
underneath. It only described some race conditions whose behavior was
not guaranteed, and that users might need to avoid.

Somebody felt that the LRM should describe how the event scheduling
should work, and what was and was not guaranteed. So this section got
added to the LRM. They couldn't specify exactly how it worked in
Verilog-XL, because they didn't know, it would have been too complex
even if they did, and they wouldn't want to constrain simulators that
much anyway. They were trying to write a theoretical model instead.
However, this model had to allow anything that Verilog-XL actually did
(as well as any other implementations who might have proponents in the
standards group).

In some situations, Verilog-XL does the kind of inlining of fanout
that was described for VCS in the Deepchip posting. So the scheduling
model had to allow for that. That kind of inlining looks like the
original process suspending, the fanout process executing, and then
the original process resuming. There might have been other
optimizations that looked like one process suspending in favor of
another process. Without knowing what is going on underneath and when
this might be allowed to happen, a very general rule is to allow any
process to suspend itself at any point.

There was also a desire to allow for the possibility of parallel
simulation, which would have the appearance of interleaved execution
of processes.

In practice, no simulator is going to suspend processes at arbitrary
points. It would slow down simulation, not make it faster.
Furthermore, there is a huge amount of legacy code out there that
simply wouldn't work if a simulator did this. Even if somebody did
manage to make a parallel simulator that sped up typical real-world
simulations significantly, they would have to restrict the visible
effects of interleaving so that existing code would continue to work
(which further reduces the chances of such a simulator speeding things
up).

So regardless of what the LRM says, you don't have to worry about
extreme cases. Implementations will be ruled by what actually gives
good performance, and a sort of "de facto" standard of what works.

 

[Michael Katelman]

On Apr 4, 10:31 am, Muzaffer Kal <k...@dspia.com> wrote:

On Fri, 3 Apr 2009 11:14:09 -0700 (PDT), "katel...@gmail.com"



katel...@gmail.com> wrote:
I was reading the following post on deepchip and it got me wondering
about something...

http://www.deepchip.com/items/0428-09.html

suppose I have the following:

initial begin
a = 1;
b = 1;
end

always @(a or b) begin
x = a + b;
y = a + b;
end

and that somehow a = b = 0 when simulation starts. By the reasoning of
the deepchip post, once the a = 1 update event happens, the always
block can execute its body and stop in the middle, so x = 1 + 0 = 1
and y is unassigned, then b = 1  can execute and since the always
block hasn't made it back to the @, it doesn't sense b to re-evaluate.
Therefore, when it resumes y = 1 + 1 = 2, but x does not get re-
evaluated and the end result is x = 1. Therefore, this
nondeterministically allows for x = 1 or x = 2 when simulation
finishes? correct? Thanks.

-Mike

Technically what you're suggesting is possible based on the standard
but I think it's unlikely because it wouldn't make much sense as an
optimization. The reason simulators suspend execution is to be able to
reduce queue operations ie always @(a,b) would suspend at x= ... so
that the consequences of it can be resolved quickly. To me it seems
that a LIFO stack would be much more efficient here so initial would
suspend because of a=... then always would suspend because of x=...
and when the third block (not shown) is done, the simulator would get
back to always finish it, then initial and then continue with more
events in the queue.
In this scenario what you're suggesting does not happen. If the
simulator makes different choices it may. Of course if someone comes
up with a multi-threaded verilog simulator all bets are off and we
need completely new algorithms to make things faster and be
"compliant" with verilog-xl; probably that's why we have very few
multi-threaded verilog simulators.

Muzaffer Kal

DSPIA INC.
ASIC/FPGA Design Serviceshttp://www.dspia.com

I see. Thank you both for your responses, they are very helpful. I'm
getting a better understanding both of how people expect the simulator
to push and pop events, but also what's "technically possible
according to the standard". Both are important for what I'm working
on, so that's great.

Thanks again.

-Mike