-
Notifications
You must be signed in to change notification settings - Fork 80
saturating
The goal of this proposal is to introduce a new integer data type to enable saturating arithmetic. For these data types, all operations such as addition and multiplication are limited to a fixed range between a minimum and maximum value. We proposed to introduce both signed and unsigned saturating integers. Some ASIC platforms natively support saturating arithmetic due to its practical advantages. According to Wikipedia (https://en.wikipedia.org/wiki/Saturation_arithmetic) the result of saturating arithmetic is as numerically close to the true answer as possible; for 8-bit binary signed arithmetic, when the correct answer is 130, it is considerably less surprising to get an answer of 127 from saturating arithmetic than to get an answer of −126 from modular arithmetic. Likewise, for 8-bit binary unsigned arithmetic, when the correct answer is 258, it is less surprising to get an answer of 255 from saturating arithmetic than to get an answer of 2 from modular arithmetic.
Note that P4_14 supports saturating arithmetic using the saturating modifier applied to fields,
counters, registers, Section 9.1.1 in the P4_14 specification v1.0.4 discusses the saturating
attribute.
The main use case is saturating counters: many operations in packet processing require counting events: packets, packet bytes, etc. It is much more intuitive to have a counter provide a max value, rather than overflow/underflow and wrap-around.
- Intel® 64 and IA-32 Architectures Software Developer’s Manual. See page 4-211 (for example).
- ARM® AArch32. See Section 3.10.
- DSPs: Qualcomm Hexagon
- Barefoot's Tofino
There is currently no support for saturating arithmetic in P4_16.
We propose to add two new data types for saturating arithmetic in P4_16, saturating_bit<W>
and saturating_int<W>, for unsigned and signed fixed-width saturating integers, respectively.
We still get away without the need to support arithmetic exceptions in P4, as there is no overflow or underflow for saturating arithmetic.
We propose that saturating arithmetic is supported for a limited set of operations: addition, subtraction, and multiplication, as well as equality, inequality, and comparison operations. We do not support saturating division. Bitwise operations are not supported.
Explicit casting is allowed between saturating and modular integers, with appropriate sign
extension, clamping, or truncation. We allow constant literals to be automatically converted by the compiler.
Alternatively, we may introduce notation, such as 1ss and 1sw, to denote saturating constant literals.
A saturating unsigned integer is declared using saturating_bit<W>. It has a bit-width of W, and
thus will have a minimum value of 0 and a maximum value of 2^W-1. W must be a compile-time known
value.
As opposed to the modular arithmetic supported with bit<W>, saturating arithmetic will clamp the
value of the result to either the minimum or maximum value supported by the data type.
All binary operations require both operands to have the same exact type, saturating, signedness, and width. Supplying operands of different types produces a compile-time error. No implicit casts (conversions) are inserted by the compiler to equalize the types. P4 does not support any binary operations that combine saturating and modular arithmetic, except cast.
The saturating_bit<W> datatype supports the following operations:
- Addition, denoted by
+. Example:
saturating_bit<W> a, b;
int tmp = a + b;
if (tmp < a.min) // a.min = 0
a.min
else if (tmp > a.max) // a.max = 2^W - 1
a.max
else
tmp
- Subtraction, denoted by
-. - Multiplication, denoted by
*. Result has the same width as the operands. P4 architectures may impose additional restrictions---e.g., they may only allow multiplication by a power of two. Multiplication semantics is equivalent to repeated addition. - Comparison for equality and inequality, denoted
==and!=respectively. These operations produce a Boolean result. - Numeric comparisons, denoted by
<,<=,>,and>=. These operations produce a Boolean result. - Casting between saturating and non-saturating unsigned integers:
- Widening between saturating or saturating and non-saturating: extend the width of the type. The result has the same value as before, with the new wider type (saturating or non-saturating).
- Narrowing
- from saturating -> non-saturating: truncate the result to the width of the desired type. If the value was larger that the width of the resulting type maximum, the result is truncated.
- from saturating/non-saturating -> saturating: truncate and clamp the result to the width of the desired type. If the value was larger, the result will be clamped to the maximum.
A saturating integer is declared using saturating_int<W>. It has a bit-width of W, and thus will
have a minimum value of -2^(W-1) and a maximum value of 2^(W-1)-1. The most significant bit
(bit W-1) is the sign bit. W must be a compile-time known value.
As opposed to the modular arithmetic supported with int<W>, saturating arithmetic will clamp the
value of the result to either the minimum or maximum value supported by the data type.
All binary operations require both operands to have the same exact type, saturating, signedness, and width. Supplying operands of different types produces a compile-time error. No implicit casts (conversions) are inserted by the compiler to equalize the types. P4 does not support any binary operations that combine saturating and modular arithmetic, except cast.
The saturating_int<W> datatype supports the following operations:
- Negation, denoted by unary
-. - Unary plus, denoted by
+. This operation behaves like a no-op. - Addition, denoted by
+. Example:
saturating_int<W> a, b;
int tmp = a + b;
if (tmp < a.min) // a.min = -2^(W-1)
a.min
else if (tmp > a.max) // a.max = 2^(W-1) - 1
a.max
else
tmp
- Subtraction, denoted by
-. - Multiplication, denoted by
*. Result has the same width as the operands. P4 architectures may impose additional restrictions---e.g., they may only allow multiplication by a power of two. Multiplication semantics is equivalent to repeated addition. - Comparison for equality and inequality, denoted
==and!=respectively. These operations produce a Boolean result. - Numeric comparisons, denoted by
<,<=,>,and>=. These operations produce a Boolean result. - Casting between saturating and non-saturating signed integers:
- Widening between saturating or saturating and non-saturating signed: sign extend and extend the width of the type. The result has the same value as before, with the new wider type (saturating or non-saturating).
- Narrowing
- from saturating -> non-saturating: truncate the result to the width of the desired type, while preserving the sign. If the value was larger/smaller, the result will be truncated to the maximum/minimum value on the narrower width with the appropriate sign. Essentially, the same operation as a W-1 unsigned with the preserved sign.
- from saturating/non-saturating -> saturating: truncate and clamp the result to the width of the desired type, while preserving the sign. If the value was larger/smaller, the result will be clamped to the maximum/minimum on the narrower width with the appropriate sign. Essentially, the same operation as a W-1 unsigned with the preserved sign.
header ipv4_t {
bit<4> version;
bit<4> ihl;
bit<8> diffserv;
bit<16> totalLen;
saturating_bit<16> identification;
bit<3> flags : 3;
bit<13> fragOffset;
saturating_bit<8> ttl;
bit<8> protocol;
bit<16> hdrChecksum;
bit<32> srcAddr;
bit<32> dstAddr;
}
}
control ingress(...) {
action a(in saturating_bit<16> value) {
// even if ttl == 0, following the decrement operation, ttl will continue to be 0
ttl = ttl - saturating_bit<8>(1);
// assuming identification == 0xFFE0, adding value = 0x0FFF, will result in
// identification == 0xFFFF
identification = identification + value;
}
...
}
Definitions of saturating arithmetic operations in terms of the non-saturating arithmetic operations already part of P4_16.
Note: These reference implementations are provided as a further example to further the understanding of the semantics of these operations. It is our expectation that programs that use saturating arithmetic are accepted by compiler backends for targets that support hardware implementations. Targets that do not have a hardware implementation, may simply reject the program.
Note: Casts between types bit<W> and saturating_bit<W> make no change to the sequence of W bits
used to represent the value. Similarly for casts between types int<W> and saturating_int<W>.
// bit_W_max is the maximum unsigned integer value that can be
// represented in W bits. It consists of W bits, all 1s.
constant bit<W> bit_W_min = ((bit<W>) 0);
constant bit<W> bit_W_max = ~((bit<W>) 0);
// Each W-bit unsigned operand represents an integer in the range [0,
// 2^W-1].
// The result of adding 2 such operands is thus in range [0,
// 2^(W+1)-2], if done using arithmetic with values of at least W+1
// bits.
control saturating_bit_add(
in saturating_bit<W> a,
in saturating_bit<W> b,
out saturating_bit<W> result)
{
bit<W+1> tmpa = (bit<W+1>) a;
bit<W+1> tmpb = (bit<W+1>) b;
bit<W+1> tmpresult = tmpa + tmpb; // modular arithmetic on type bit<W+1>
if (tmpresult > bit_W_max) {
result = (saturating_bit<W>) bit_W_max;
} else {
result = (saturating_bit<W>) tmpresult;
}
}
control saturating_bit_subtract(
in saturating_bit<W> a,
in saturating_bit<W> b,
out saturating_bit<W> result)
{
bit<W+1> tmpa = (bit<W+1>) a;
bit<W+1> tmpb = (bit<W+1>) b;
bit<W+1> tmpresult = tmpa - tmpb; // modular arithmetic on type bit<W>
if (tmpb > tmpa) {
result = (saturating_bit<W>) bit_W_min;
} else {
result = (saturating_bit<W>) tmpresult;
}
}
// int_W_min is the minimum signed integer value that can be
// represented in W bits using 2's complement arithmetic. It has a
// sign bit of 1, and all other bits 0.
constant int<W> int_W_min = ((int<W>) 1) << (W-1);
// int_W_max is the maximum signed integer value that can be
// represented in W bits using 2's complement arithmetic. It has a
// sign bit of 0, and all other bits 1.
constant int<W> int_W_max = int_W_min - 1;
control saturating_int_add(
in saturating_int<W> a,
in saturating_int<W> b,
out saturating_int<W> result)
{
int<W> tmpa = (int<W>) a;
int<W> tmpb = (int<W>) b;
int<W> tmpresult = tmpa + tmpb; // modular arithmetic on type int<W>
// This is the correct result in many cases. Cases where a
// different result is needed are checked below.
result = (saturing_int<W>) tmpresult;
// Note: all comparisons of the form "x < 0" or "x >= 0", where x
// is of type int<W>, can be implemented by examining only the
// sign bit of x.
if (tmpa < 0 && tmpb < 0) {
if (tmpresult >= 0) {
// modular arithmetic wrapped around below int_W_min
result = (saturing_int<W>) int_W_min;
}
} else if (tmpa >= 0 && tmpb >= 0) {
if (tmpresult < 0) {
// modular arithmetic wrapped around above int_W_max
result = (saturing_int<W>) int_W_max;
}
}
// Two cases remain:
// (3) tmpa >= 0 && tmpb < 0
// (4) tmpa < 0 && tmpb >= 0
// In case (3), the arbitrary precision result is in the range
// [0, int_W_max] + [int_W_min, -1] -> [int_W_min,
// int_W_max-1], so the result is in the range of an int<W>
// value. Case (4) is symmetrical with (3).
}
control saturating_int_subtract(
in saturating_int<W> a,
in saturating_int<W> b,
out saturating_int<W> result)
{
int<W> tmpa = (int<W>) a;
int<W> tmpb = (int<W>) b;
int<W> tmpresult = tmpa - tmpb; // modular arithmetic on type int<W>
// This is the correct result in many cases. Cases where a
// different result is needed are checked below.
result = (saturing_int<W>) tmpresult;
// Note: all comparisons of the form "x < 0" or "x >= 0", where x
// is of type int<W>, can be implemented by examining only the
// sign bit of x.
if (tmpa < 0 && tmpb >= 0) {
if (tmpresult >= 0) {
// modular arithmetic wrapped around below int_W_min
result = (saturing_int<W>) int_W_min;
}
} else if (tmpa >= 0 && tmpb < 0) {
if (tmpresult < 0) {
// modular arithmetic wrapped around above int_W_max
result = (saturing_int<W>) int_W_max;
}
}
// Two cases remain:
// (3) tmpa >= 0 && tmpb >= 0
// (4) tmpa < 0 && tmpb < 0
// In case (3), the arbitrary precision result is in the range [0,
// int_W_max] - [0, int_W_max] -> [-int_W_max, int_W_max], so the
// result is in the range of an int<W> value.
// In case (4), the arbitrary precision result is in the range
// [int_W_min, -1] - [int_W_min, -1] -> [int_W_min+1, (-int_W_min)
// - 1], so the result is in the range of an int<W> value.
}
// Multiplication semantics is equivalent to repeated addition.