[P4-discuss] Question regarding semantics of actions in P4-14 (v1.0.3)

Ali Kheradmand a.i.kheradmand at gmail.com
Thu Jan 19 18:45:54 EST 2017


Thanks a lot to all of you for your responses. For those who didn't know I
am trying to formalize the semantics of P4 in K framework (kframework.org).

Based on your answers I think I will give sequential semantics to the
actions because there is a high probability I will switch to P4-16 anyway.

The way I would model this in an operational semantics is to (i) copy the
> old state before evaluating the primitives in the action body and (ii)
> define a merge operation that takes the updated states produced by
> evaluating the primitives and (non-deterministically) merges them to get a
> new state.


Defining merge for the simple cases like in the example I gave (modifying a
field twice) would be trivial. But generally I think it is not that trivial
(or maybe it is, but it is not clear to me). Actually the initial reason I
asked the question on this mailing list was to understand how to formalize
"change in state" or "effect of a single (primitive) action". My idea was
almost similar to yours. It was to execute the actions in a non
deterministic order, but instead of applying the effects immediately,
record the changes and commit the effects at the end. But then I got to
questions like what should be the result of something like this:
action a(){
     add_header(ethernet[1]);
     add_header(ethernet[2]);
}
Anyway I think it is not worth spending time on since the semantics has
changed to sequential.

But why bother about P4-14 any longer?
>

I started working on the semantics before the new spec draft (P4-16) was
published on the p4.org website and P4-14 seems to be quite different from
version 1.0.3. I was not sure if it is a good idea to change to P4-16 right
now (because I already had changed from v1.1 to v1.0.3 once and wasn't sure
if P4-16 spec is stable). We had a bit of discussion regarding this with
Nate. For now I decided to continue to have some (not complete) semantics
for P4-14 so that it can run very very simple P4 programs (I expect this to
be finished very soon) and meanwhile look into P4-16 more carefully and
then decide what to do.I am almost finished with this process except for
semantics of de-parsing which I will probably ask about in a separate topic
soon.






On Thu, Jan 19, 2017 at 3:08 PM, Gordon Brebner <Gordon.Brebner at xilinx.com>
wrote:

> The sequential semantics for execution of compound actions was actually
> introduced in the (now hidden) P4 v1.1 spec a year ago.  However, P4 v1.0.3
> has become the official “P4_14” representative, and so P4_14 doesn’t embody
> that change in semantics.  P4_16 has inherited the sequential semantics
> from P4 v1.1.
>
>
>
> This topic was much discussed in the P4 language design WG before the
> change was made.  The expectation is that, where suitable parallelism is
> available, compilers can parallelize the sequential actions as long as
> dependencies are respected.
>
>
>
> Gordon.
>
>
>
>
>
>
>
> *From:* P4-discuss [mailto:p4-discuss-bounces at lists.p4.org] *On Behalf Of
> *Andy Fingerhut
> *Sent:* Thursday, January 19, 2017 12:50 PM
> *To:* Nate Foster <jnfoster at cs.cornell.edu>
> *Cc:* Grigore Rosu <grigore.rosu at gmail.com>; p4-discuss at lists.p4.org;
> Nikolaj Bjorner <nbjorner at microsoft.com>
> *Subject:* Re: [P4-discuss] Question regarding semantics of actions in
> P4-14 (v1.0.3)
>
>
>
> Caveat: I am not a P4 language spec writer, just an avid reader who has
> thought about this issue a while.
>
>
>
> My reading of P4_14 spec is that the behavior of this code:
>
>
>
> action a  ( ) {
>
>   modify_field(h.a, 1);
>
>   modify_field(h.a, 2);
>
> }
>
>
>
> is undefined, because of the parallel semantics of primitive actions
> within an action.  A good quality P4_14 compiler could give an error
> stating this, and fail to compile the program.
>
>
>
> Consider an action like the one below, included in the SIGCOMM 2016 P4
> tutorial as an example:
>
>
>
> (excerpted from the file solution/heavy_hitter.p4 inside this file:
> https://github.com/p4lang/tutorials/blob/master/SIGCOMM_2016/heavy_hitter/
> solution.tar.gz )
>
>
>
> action set_heavy_hitter_count() {
>
>     modify_field_with_hash_based_offset(custom_metadata.hash_val1, 0,
>
>                                         heavy_hitter_hash1, 16);
>
>     register_read(custom_metadata.count_val1, heavy_hitter_counter1,
> custom_metadata.hash_val1);
>
>     add_to_field(custom_metadata.count_val1, 1);
>
>     register_write(heavy_hitter_counter1, custom_metadata.hash_val1,
> custom_metadata.count_val1);
>
>
>
> /* rest of action code deleted for brevity */
>
> }
>
>
>
> It seems like this was written with sequential execution of primitive
> actions in mind (i.e. it is intended to read a value from a register,
> calculate a modified value based upon the value read, and write that
> modified value back).  It definitely _doesn't_ do the same thing with
> parallel semantics (e.g. the value written by register_write would be the
> value of the metadata field custom_metadata.count_val1 _before the action
> started executing_).
>
>
>
> Example like this lead me to believe that there are at least some P4_14
> compilers that actually implement sequential semantics within an action,
> despite what the P4_14 spec says.
>
>
>
> Note that if a P4_14 compiler strictly followed the parallel semantics, it
> seems impossible in one action to implement the behavior of the C
> assignment X = (Y << 5) + 7.  You can do the shift, and you can add 2
> values together, but you can't add 2 values together where one of them is
> the result of another operation in the same action.
>
>
>
> The P4_16 draft doesn't mention the word "parallel" anywhere in it that I
> can find, so it seems that the intended semantics is sequential execution,
> and assignments like the one above are possible to specify in a single
> action, as well as the read-modify-write behavior.  It is up to the P4_16
> compiler to reject programs that have actions that are too complex for the
> target's capabilities, as always.  That seems like a clear win in terms of
> P4_16 program developers understanding the behavior of their programs,
> since most programmers are accustomed to sequential semantics.
>
>
>
> I have heard that the parallel semantics were included in P4_14 in an
> effort to make it easier to compile programs to a target similar to the RMT
> (Reconfigurable Match-action Table ?) architecture, by making it impossible
> to specify dependent arithmetic operations (dependent operations, if there
> is too long a chain, can't be calculated within a single clock cycle at
> high clock rates).  However, I don't think it is straightforward for a
> P4_16 compiler to determine the longest dependent chain in an action with
> sequential semantics.
>
>
>
> Andy
>
>
>
>
>
> On Thu, Jan 19, 2017 at 2:15 AM, Nate Foster <jnfoster at cs.cornell.edu>
> wrote:
>
> Hi Ali,
>
>
>
> It's almost like one needs to formalize the semantics to make sense of
> this! ;-)
>
>
>
> I wasn't involved with drafting the P4-14 spec so I could be wrong, but
> based on the informal text, I believe the intention is that the order of
> the statements is ignored, but the primitive instructions are executed with
> something akin to "true concurrency" and what Lamport calls "regular" in
> his classic work on semantics of registers. That is, after executing a the
> field h.a would either have the value 1 or 2, but not some other value
> (which weaker notions like "safe registers" allow, due to hazards that may
> occur when shared memory is written by two different threads
> simultaneously).
>
>
>
> The way I would model this in an operational semantics is to (i) copy the
> old state before evaluating the primitives in the action body and (ii)
> define a merge operation that takes the updated states produced by
> evaluating the primitives and (non-deterministically) merges them to get a
> new state.
>
>
>
> Maybe Nikolaj can weigh in on how P4-NoD handled this issue?
>
> https://www.microsoft.com/en-us/research/wp-content/
> uploads/2016/09/p4nod.pdf
>
>
>
> Cheers,
>
> -N
>
>
>
> On Wed, Jan 18, 2017 at 11:59 AM, Ali Kheradmand <a.i.kheradmand at gmail.com>
> wrote:
>
> Hi,
>
>
>
> In the language specification version 1.0.3, section 9.2.1 it is stated
> that “P4 assumes parallel semantics for the application of all the
> primitive actions executing as a result of a match in a given table.” It
> also mentions that “With parallel semantics, […] actions are started at the
> same time”.
>
>
>
> I was wondering whether it means that the order of actions are not
> important at all or not. If the order is ignored, I what happens if two
> primitive actions that are executed as a result of a match have overlapping
> effects, for example:
>
> action a  ( ) {
>
>   modify_field(h.a, 1);
>
>   modify_field(h.a, 2);
>
> }
>
>
>
> If the order is important, how exactly it relates to the parallel
> semantics?
>
>
>
> Regards,
>
> Ali
>
>
>
>
> _______________________________________________
> P4-discuss mailing list
> P4-discuss at lists.p4.org
> http://lists.p4.org/mailman/listinfo/p4-discuss_lists.p4.org
>
>
>
>
> This email and any attachments are intended for the sole use of the named
> recipient(s) and contain(s) confidential information that may be
> proprietary, privileged or copyrighted under applicable law. If you are not
> the intended recipient, do not read, copy, or forward this email message or
> any attachments. Delete this email message and any attachments immediately.
>
>
> _______________________________________________
> P4-discuss mailing list
> P4-discuss at lists.p4.org
> http://lists.p4.org/mailman/listinfo/p4-discuss_lists.p4.org
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.p4.org/pipermail/p4-discuss_lists.p4.org/attachments/20170119/b2e5b530/attachment-0002.html>


More information about the P4-discuss mailing list