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

Andy Fingerhut andy.fingerhut at gmail.com
Thu Jan 19 15:49:30 EST 2017


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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.p4.org/pipermail/p4-discuss_lists.p4.org/attachments/20170119/ca009524/attachment-0002.html>


More information about the P4-discuss mailing list