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

Gordon Brebner Gordon.Brebner at xilinx.com
Thu Jan 19 16:08:06 EST 2017


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<mailto: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<mailto: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<mailto: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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.p4.org/pipermail/p4-discuss_lists.p4.org/attachments/20170119/655d5407/attachment-0002.html>


More information about the P4-discuss mailing list