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

Nate Foster jnfoster at cs.cornell.edu
Sat Jan 21 05:55:11 EST 2017


A couple of quick reactions to the nice points raised on this thread.

First, why should we bother formalizing this? P4-16 uses sequential
semantics, so is this issue still relevant? I believe it is worth writing
this down carefully for a few reasons:

* It's not actually hard. Although the English prose in the specification
is vague, as several have people noted, we can do a fairly simple
formalization it in the style of fork-join parallelism -- provide a copy
the state to each primitive action, then merge the updated states they
produce. The merge operation could be something quite simple -- e.g.,
resolve conflicts by taking both values, non-deterministically, or by
mapping them to havoc.

* Some people using P4-14 may not transition to P4-16 for a while. One of
the principles that guided the design of P4-16 was that there should be a
path for migrating programs into the language, possibly automatically. The
new p4c compiler provides a P4-14 to P4-16 conversion tool, but it does not
implement parallel semantics (see https://github.com/p4lang/p4c/issues/246).

* I think it's worth having an independent description of what we meant by
parallel actions written down. I have spoken to some people in the P4
community who think that it was a mistake to change from parallel to
sequential semantics for actions. I'm not proposing revisiting that
decision or spending significant energy haggling over the details, but
having it written down seems useful.

* Comment: As Andy noted, Bmv2 and some of the tutorial materials assume
sequential semantics. Relying on a reference implementation to define the
semantics of a language is almost never a good idea... this is why we need
clear (and I would argue) formal specification of the semantics.

-N

On Thu, Jan 19, 2017 at 3:48 PM, Mihai Budiu <mbudiu at vmware.com> wrote:

> Your interpretation is correct. P4-14 did not specify precisely what
> “parallel” means. Different P4 experts had different opinions on the
> meaning of the word “parallel”. That is why P4-16 adopts a strictly
> sequential semantics for statements. This was done in P4 v1.1.
>
>
>
> As far as I can tell, the real intent of P4-14 was to implement all
> statements in an action in the following way:
>
> -          Read all right-hand values concurrently
>
> -          Execute all arithmetic operations concurrently
>
> -          Execute all assignments to the left-hand side values
> concurrently
>
>
>
> This can be implemented efficiently by a parallel circuit that can
> read/write to “storage” concurrently. This is how a hardware implementation
> would work too.
>
>
>
> Obviously, this is undefined if a left-value appears multiple times on the
> left-hand side.
>
>
>
> Another issue was the definition of “arithmetic operations”: what are the
> operations that a given target can implement? This is why P4-14 has a large
> number of “primitive operations”: https://github.com/p4lang/p4c/
> blob/master/ir/v1.cpp, such as bit_andca (and this set of operations is
> still insufficient for describing the capabilities of a reasonable target!).
>
>
>
> Indeed, for a language without pointers it should be easier for a compiler
> to extract the parallelism than for the programmer to specify it. Moreover,
> the code generator can now accept chains of arithmetic operations if they
> can be mapped to the target capabilities (a & ~b).
>
>
>
> Mihai
>
>
>
> *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
> <https://urldefense.proofpoint.com/v2/url?u=https-3A__github.com_p4lang_tutorials_blob_master_SIGCOMM-5F2016_heavy-5Fhitter_solution.tar.gz&d=DwMFaQ&c=uilaK90D4TOVoH58JNXRgQ&r=tGW6TKXajnoXSyy1S1P4DHGPe8sj54GGvw-b21n7aWg&m=H4WSu8jYAonsjCtp2NimjPzDKncKkYQIULbTE7tCTKc&s=HKrHaaNCZqpSULOy0LZYrs6T31vZtJ3anqiaM2LUN5w&e=>
>  )
>
>
>
> 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
> <https://urldefense.proofpoint.com/v2/url?u=https-3A__www.microsoft.com_en-2Dus_research_wp-2Dcontent_uploads_2016_09_p4nod.pdf&d=DwMFaQ&c=uilaK90D4TOVoH58JNXRgQ&r=tGW6TKXajnoXSyy1S1P4DHGPe8sj54GGvw-b21n7aWg&m=H4WSu8jYAonsjCtp2NimjPzDKncKkYQIULbTE7tCTKc&s=I3xAidTX8gp_EfZWvsiS_lJeCLMT_CxNr4zfeXKtgl4&e=>
>
>
>
> 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
> <https://urldefense.proofpoint.com/v2/url?u=http-3A__lists.p4.org_mailman_listinfo_p4-2Ddiscuss-5Flists.p4.org&d=DwMFaQ&c=uilaK90D4TOVoH58JNXRgQ&r=tGW6TKXajnoXSyy1S1P4DHGPe8sj54GGvw-b21n7aWg&m=H4WSu8jYAonsjCtp2NimjPzDKncKkYQIULbTE7tCTKc&s=WhROEasSCFKPfGs6tsTrIlyUWm-fdz1ydQJD-lcxF9I&e=>
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.p4.org/pipermail/p4-discuss_lists.p4.org/attachments/20170121/ee192abd/attachment-0002.html>


More information about the P4-discuss mailing list