From: Michael McNamara (mac@verisity.com)
Date: Fri Aug 16 2002 - 09:50:07 PDT
Precedence: bulk
The following reply was made to PR errata/84; it has been noted by GNATS.
From: Michael McNamara <mac@verisity.com>
To: Steven Sharp <sharp@cadence.com>
Cc: etf-bugs@boyd.com
Subject: Re: errata/84: Should @* include delay controls?
Date: Fri, 16 Aug 2002 09:47:32 -0700
Steven Sharp writes:
> Precedence: bulk
>
> The following reply was made to PR errata/84; it has been noted by GNATS.
>
> From: Steven Sharp <sharp@cadence.com>
> To: etf-bugs@boyd.com
> Cc:
> Subject: Re: errata/84: Should @* include delay controls?
> Date: Thu, 15 Aug 2002 20:24:21 -0400 (EDT)
>
> > > > In the general case, I believe that the question of
> > > > whether a variable is guaranteed to be assigned before being
> > > > used can be reduced to the halting problem, and is therefore
> > > > uncomputable.
> >
> > Come now, this is absolutely not true.
>
> I am afraid that you are incorrect about this. It is impossible to
> write an algorithm that can determine this about an arbitrary piece
> of code.
We are not talking about arbitray code, or some abstract general case.
We are talking about Verilog statements. We are ignoring force and
release. We are ignoring someone using the command line interface at
run time. We are ignoring runtime pli access to set variables. We are
ignoring somebody using the a debugger to change the value of memory
at arbitrary points. We are ignoring hierarchical references from
other code.
The conservative algorithmn in IEEE 1364-2001 has us adding every
variable the appears in in a rhs context of any statement contained in
the statement (which could be a statement group) of a
procedural_timing_control_statement. This will result in more
execution than is necessary, execution which will exhibit side
effects.
That said, the alogrithmn in 1364-2001 is certainly O(n), and is fully
computable.
We have an opportunity to tune this text now; or we can continue to
pursue academic arguments, with the result that this feature will
either be implemented extremely conservatively by some (translated
into slow speed of execution), and be implemented by others in the
manner originally intended, (translating into faster execution) by
others.
I would like to see an O(nlogn) algorithmn, like that in use by the
compiler that compiled the code I am using to send you email, and that
you are using to read this email.
One could say let the market decide; and pick the faster simulator;
however, procedural blocks very naturally include many side effects
which will cause users to trivially get different answers, leading to
a requirement upon us as the standards body to set a useful,
unambiguous standard.
> With a little more thought, I was able to produce a proof
> of the fact, similar to the proof that the halting problem is
> uncomputable.
Show us the proof.
This archive was generated by hypermail 2.1.4
: Thu Oct 10 2002 - 09:24:28 PDT
and
sponsored by Boyd Technology, Inc.