Re: [sv-bc] Mantis 1345: 10.4: "illegal" unique if/case issues

Thanks for your support, Shalom.

   "Speculative" side-effects has a pretty trivial
implementation for synthesis, but I fear that there is no
feasible simulation semantics for it.
I am not a simulator guy, but those that have responded were
doubtful.

   "Unique if/case" is a synthesis idea still in search of
appropriate simulator support.  I wrote up this exercise to
see if I could get to the heart of the matter and I'm either
not yet there, or the issue itself is ill-conceived.

   If the parallel case could instantaneously fork the simulator
into N independent copies, each one running a serial simulation
of one alternative until just one is left whose guard evaluates
to TRUE, the others could be discarded and the survivor would
finish running the remainder of the simulation.  Easier said
than done.

   I think we'll have to concentrate on how to specify what is
prohibited in unique alternative expressions, so that they do
not require explicit simulator concurrency to be unambiguously
modeled.  It looks like we need to squelch all side-effects on
design variables altogether.

Greg


Bresticker, Shalom wrote:
> Sorry for the late response.
> 
> _____________________________________________
> ***From:* owner-sv-bc@eda.org [mailto:owner-sv-bc@eda.org]*** On Behalf 
> Of* Greg Jaxon
> ***Sent:* Thursday, February 23, 2006 3:33 AM
> ***To:* Steven Sharp
> ***Cc:* sv-bc@eda.org
> ***Subject:* Re: [sv-bc] Mantis 1345: 10.4: "illegal" unique if/case issues
> 
> Steven Sharp wrote:
> 
>> >From: "Bresticker, Shalom" <shalom.bresticker@intel.com>
> 
>>
> 
>>
> 
>> >[Shalom] And in unique 'if'. I admit I don't understand all the
> 
>> >discussion about interleaving orderings in that I don't think it makes
> 
>> >a difference in any normal case. Is there any such case which is not
> 
>> >pathological?
> 
>>
> 
>>
> 
>>  Except for the issue in Mantis item 1304, which is just plain wrong, I
> 
>>  would call all the cases where interleaving order matters pathological.
> 
>>  They could all be considered illegal, without losing anything useful.
> 
> I'd generally agree, and I'd guess the cost of detecting this at 
> simulation time is no worse than o(n log n) time and space proportional 
> to the storage addressed by the conditional tests.  Brad has often 
> suggested that SV prohibit side-effects here altogether, which would 
> probably not be practical for testbench uses; but prohibiting 
> side-effects on each others' logic cones is both sensible and doable.  
> Or there's another alternative (below)
> 
> [Shalom] If such a prohibition would only apply to ‘unique’ if/case and 
> not to regular case, maybe it would be practical.
> 
>> >I would be happy with deleting all the discussion about various
> 
>> >orderings from the LRM and even be willing to have the LRM specify
> 
>> >evaluation in top-down order.
> 
>>
> 
>>  I wouldn't have any problem with that.  Has anyone else implemented it
> 
>>  with a different evaluation order?
> 
> There are several ways to define "top-down", given that control is also 
> branching into one of the conditional statement lists.  Here's a 
> proposal in which the case label side-effects are permitted, but don't 
> compromise concurrent evaluation.
> 
> Consider code where A,B,C,... stand for expressions or statements whose 
> evaluation order we wish to settle.
> 
>      unique case (A)
> 
>       B, C :  D;
> 
>       E:      F;
> 
>       G, H:   I; J;
> 
>      endcase;
> 
>      K;
> 
> [Shalom] Quibble: “I;J;” needs to be enclosed in begin/end.
> 
> Clearly A evaluates once and must be compared with {B,C,E,G,H} in order 
> to test that
> 
>     - only one of the branch directions is taken, or
> 
>     - only one of those case labels matches A.
> 
> In the first instance, at most one of C or H might be skipped due to 
> shortcut evaluation.
> 
> If A has a side-effect, my gut says that all of {B-K} should see the 
> resulting state.
> 
> [Shalom] Agree.
> 
> Now consider who should see side-effects in E.  I think that this 
> side-effect must become visible to the execution of F when A==E. 
> 
> [Shalom] Agree.
> 
> Steven's instinct tells him that E's side-effect should probably /not/ 
> be visible to B, C, or D. 
> 
> [Shalom] Agree.
> 
> I agree and further argue that (by the symmetry of concurrency) it 
> should also /not/ be visible to G, H, I, or J.
> 
> [Shalom] Agree.
> 
> If that branch to F is taken, control will afterward move to K, and 
> clearly it sees E's side-effect.  But at this juncture, F has already 
> ignored any side-effects that were in {B,C,G,H}, and so K should 
> continue to ignore them.
> 
> [Shalom] Agree.
> 
> In this model, side-effects in case labels are "speculative" and only 
> committed if they appear on the "winning" branch.  This is really no 
> problem at all for synthesis :-)  For simulation, it looks more 
> complicated.  It's complexity is no worse than *detecting* side-effect 
> collision.  But if these side effects can trigger events, the whole 
> proposal looks silly.  I think embedded assignments cannot be 
> non-blocking, so perhaps their relationship to event scheduling is 
> already special in other ways that would support this "speculation".
> 
> If this is not supportable, then prohibiting side-effects (in the design
> 
> space) would be the best policy.
> 
> [Shalom] Just in uniques.
> 
> The final point in this definition is to say whether C and H see 
> side-effects of B or G (respectively).  If they do *not* see prior 
> label-list side effects, then they are acting like entirely separate 
> branch guardians, and as such they should be considered as separate case 
> labels subject to the uniqueness assertion - meaning that it would be 
> illegal for A==B && A==C.
> 
> [Shalom] Disagree. They should not see side-effects in a unique case, 
> though I would not make a big fuss about it. But definitely, the 
> case_expression should be allowed to match more than one expression 
> within a single case_item. One reason, but not the only one, is that the 
> problem with uniqueness (parallel_case) violation is really only when 
> the two matches can cause different case actions. That is difficult to 
> identify when they are in different case_items. However, when there is 
> more than one expression in a single case_item, then even if more than 
> one expression matches, they will cause the same case action.
> 
> The discussion of unique case so far hasn't required one-hot across all 
> the separate labels, but rather one-hot across the several label-lists.  
> Given that precedent, we'd expect serial, and possibly shortcut 
> evaluation of B then C, with C having access to B's side-effects, even 
> if B does not match A.
> 
> [Shalom] I don’t see why.
> 
> So that's a serializable parallel semantics that ought to model the 
> synthesized hardware reasonably well.  Side effects like $display which 
> have trouble being done "speculatively" are the cart which should not be 
> put before this horse.  I believe those effects lie outside the design 
> space anyway.
> 
>>  I can see the possibility of someone optimizing case statements for
> 
>>  efficient table lookup in a way that effectively alters the evaluation
> 
>>  order.  I can't actually think of any way of doing it in the presence
> 
>>  of the kinds of expressions that could have side effects, but maybe
> 
>>  somebody else could.
> 
> In my proposal, the side-effects only propagate downstream along the 
> taken branch - never sideways into the concurrent alternatives.
> 
> This leaves them unordered yet still well-defined.
> 
> It also avoids the pathology where G's side-effect can reach D.
> 
> By "top-down" I understand Steven to mean:
> 
> [Shalom] Actually, “top-down” was my term. Steven would have been more 
> precise.
> 
>    1) execute all the case labels in lexical order,
> 
>       possibly shortcutting,
> 
>       possibly triggering events due to embedded side-effects...
> 
>    2) compare and assert one-hotness
> 
>    3) execute the winning branch
> 
> That offers a lot of support for pathological cases - it puts too much 
> execution between the winning label and the winning branch.
> 
> I prefer to avert my eyes from pathological effects, so I propose 
> confining them to the taken control paths and ignoring those done only 
> to verify the one-hot assertion.
> 
> [Shalom] Is that easy to implement? Or make them illegal in unique if/cases.
> 
> This counter-proposal corresponds better to a "parallel"
> 
> reading for unique case.
> 
> [Shalom] Overall, I like the idea.
> 
> Greg Jaxon
> 
> Discalimer:  this is another crazy idea, with no specific relationship 
> to extant or planned Synopsys products.
> 
> [Shalom] A shame.
> 
> Thanks,
> 
> Shalom
>