Могу ли я сделать проверенную арифметику с Vector<T>

Question

Я экспериментировал с Vector, чтобы использовать HW для распараллеливания целочисленной арифметики. Есть ли способ включить проверку переполнения с помощью векторных операций?

Одним из примеров является сложение двух столбцов (массивов одинаковой длины) целых. Вот c=a+b средства c[0] = a[0] + b[0], c[1] = a[1] + b[1], так далее.

Я полагаю, я мог бы сделать что-то вроде этого:

overflow[i] = b[i] >= 0 ? c[i] < a[i] : c[i] >= a[i];

Но это (ветвление) может быть медленнее, чем автоматическая проверка переполнения.Net, и может свести на нет преимущество в производительности при использовании Vector<T>,

Мы также хотим оптимизировать наши наиболее часто используемые операции: умножение, вычитание, в меньшей степени целочисленное деление.

Edit: я думал об этом немного больше, и придумал это, который в 2,5 раза медленнее, чем неконтролируемое добавление вектора. Похоже, много дополнительных накладных расходов.

    public Vector<int> Calc(Vector<int> a, Vector<int> b)
    {
        var result = a + b;
        var overflowFlag = Vector.GreaterThan(b, Vector<int>.Zero) * Vector.LessThan(result,a)
            + Vector.LessThan(b,Vector<int>.Zero) * Vector.GreaterThan(result, a);

        // It makes no sense to add the flags to the result, but haven't decided what to do with them yet, 
        // and don't want the compiler to optimise the overflow calculation away
        return result + overflowFlag;
    }

Время: (4 000 итераций, добавив пару массивов по 100 КБ)

• Нормальное добавление: 618мс
• Нормальный Проверено Добавить: 1092мс
• Vector Add: 208ms
• Вектор проверен Добавить: 536мс

Answer 1

Используя некоторую хитрость, заимствованную из восхищения Хакера (глава 2, раздел "Обнаружение переполнения"), вот некоторые предикаты переполнения (не проверено):

Подписанное дополнение:

var sum = a + b;
var ovf = (sum ^ a) & (sum ^ b);

Результат в знаках, а не в полных масках. Может быть, этого достаточно, а может и нет, и в этом случае я обычно рекомендую правильный сдвиг, но правого сдвига нет Vector<T> (слишком много вещей не хватает). Вы можете сравнить с нулем, хотя.

Добавление без знака: для полноты?

var sum = a + b;
var ovf = Vector.LessThan(sum, a);

Умножение:

Насколько я могу судить, разумного способа сделать это просто нет. Это немного раздражает даже в родном SSE, но с pmuldq и некоторые перетасовки это не так уж плохо.
В C# SIMD это кажется безнадежным. Не существует high-mul (также отсутствует в собственном SSE, за исключением 16-битных целочисленных значений, что также раздражает), нет расширяющегося умножения (и в любом случае нет способа сузить результат), также нет разумного способа расширения заранее. Даже если бы вы могли расширить (если бы они серьезно добавили это в API), умножение 64-битных целых чисел на SSE раздражает, поэтому раздражает, что делать это с помощью скалярной арифметики - не плохой вариант, который побеждает суть.

Поэтому я рекомендую не делать этого в SIMD, по крайней мере, в C#.

Это не значит, что вы используете встроенное обнаружение переполнения. Хотя это уместно, если переполнение является фатальной ошибкой, оно катастрофически медленно, если оно является распространенным и ожидаемым, и вы просто хотите получить статус переполнения в логическом флаге. В этом случае вы можете использовать:

Умножение со знаком:

long ext_prod = (long)a * b;
int prod = (int)ext_prod;
bool ovf = (prod >> 31) != (int)(ext_prod >> 32);

Умножение без знака:

ulong ext_prod = (ulong)a * b;
uint prod = (uint)ext_prod;
bool ovf = (ext_prod >> 32) != 0;

В SIMD это работало бы в основном таким же образом, т.е. проверяя, заполнена ли верхняя половина копиями знака (по определению ноль в случае без знака), но расширение делает его раздражающим в родной SIMD и безнадежным в C# SIMD.