Checked Data Parallel Arithmetic in C#

Adding two integers in C# can produce surprising results. For instance,

int sum = 2147483647;    // Int32.MaxValue == 0x7FFFFFFF
sum = sum + 1;

The resulting sum is expected to be 2147483648, but is -2147483648 instead.

uint sum = 4294967295;    // UInt32.MaxValue == 0xFFFFFFFF
sum = sum + 1;

The resulting sum is expected to be 4294967296, but is 0 instead.

This condition is called arithmetic overflow, and happens due to uint and int being limited to 32 bits, whereas the result of addition needs 33 bits to hold the entire result. Instead, only the lower 32 bits of the result are returned and the upper 1 bit is lost.

Checked Key Word

C# provides a checked keyword to detect arithmetic overflow, for operations such as addition. For example,

int sum = 2147483647;    // Int32.MaxValue == 0x7FFFFFFF
sum = checked(sum + 1);

In the above case, the checked block surrounds a potentially dangerous operation – addition. Instead of producing an unexpected result, an overflow exception is thrown when the result exceeds 32 bits. Otherwise, when the result fits within 32 bits, no overflow exception is thrown, as in:

int sum = 3;
sum = checked(sum + 1);

The checked key word can also be used as a block, to check multiple C# code statements for arithmetic overflow.

Intel and AMD processors provide an overflow flag to make it simple to detect arithmetic overflow. C# uses this facility to detect when an overflow occurs, within the checked block, and then throws an overflow exception whenever an overflow processor flag gets set.

SIMD/SSE Instructions

Intel and AMD processors provide 100’s of data parallel instructions. These can operate on several items in parallel. These instruction are called SIMD – single instruction multiple data – indicating that a single processor instruction operates on multiple data items. For example, for 256-bit wide instructions, eight 32-bit additions can be done in parallel.  In this case, a single instruction operates on eight data items in parallel. On newer Intel and AMD processors, up to 512-bit wide instructions are available, which is the width of a 64-byte cache line.

C# checked block can contain SIMD/SSE instructions. However, C# does not check for overflow that occurs in SIMD operations, probably because the processors do not provide overflow flags for SIMD instructions. To add support for overflow checking we would need to implement it in code.

Unsigned Integer Overflow Detection

When adding two unsigned integers, we expect the sum to be bigger than either of the numbers being added. If however, the result ends up smaller than either of the values being added, then an overflow has occurred. This condition is simple to detect:

ulong newSum = sum + value;
if (newSum < sum)
    throw new OveflowException;    //    arithmetic overflow occurred
else
    sum = newSum;                  // no arithmetic overflow occurred

Signed Integer Overflow Detection

When adding two signed integers, four cases are possible: both positive, both negative, first positive and second negative, first negative and second positive. For the two cases where the two values are of opposite sign, arithmetic overflow is not possible. For the case where both values are positive, the check is needed to see if the resulting sum is smaller – same as for the unsigned sum above. For the last case where both values are negative, the check is needed to see if the resulting sum is larger than either of the values being summed.

Other Integer Data Types

Just like for integer, unsigned and signed, data types, overflow can be detected for other integer data types, such as long and ulong, or short and ushort. Implementing overflow detection is especially useful for long and ulong integer data types, because there is no bigger integer CPU-native data types available in most programming languages. For summing of long and ulong arrays Decimal and BigInteger C# software data types are available, both of which provide more bits of precision to not cause overflow. HCPsharp supports fast single-core, multi-core and SIMD/SSE summation of long and ulong arrays.

Overflow Detection for SIMD/SSE

Implementing arithmetic overflow detection using SIMD/SSE data-parallel instructions is possible and has been added to the HPCsharp library for ulong and long integer data types. This capability provides a significant performance boost when performing summation of array of ulong or long integers to produce a BigInteger or a Decimal sum result.

Performance of SIMD/SSE implementation can be characterized by the two extremes: arithmetic overflow happens on every sum, and overflow never happens. Most real-world scenarios will fall in between these two extremes, depending on the percentage of the cases within an array that cause arithmetic overflow.

Performance Benchmarks

Present ulong array sum performance with overflow on every sum, and with no overflow (sum of 32-bit uint randoms): to Decimal and to BigInteger, single-core and multi-core SSE implementation.

Present long array sum performance with overflow on every sum (positive only and negative only), and with no overflow (32-bit int randoms, maybe also positive only 32-bit randoms and negative only 32-bit randoms): to Decimal and to BigInteger, single-core and multi-core SSE implementation

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s