Хабрахабр

Небольшой обзор SIMD в .NET/C#

NET Framework и . Вашему вниманию предлагается небольшой обзор возможностей векторизации алгоритмов в . Цель статьи познакомить с этими приёмами тех, кто их вообще не знал и показать, что . NETCORE. NET не сильно отстаёт от "настоящих, компилируемых" языков для нативной
разработки.

Я только начинаю изучать приёмы векторизации, так что если кто из сообщества укажет мне на явные косяк, или предложит улучшенные версии описанных ниже алгоритмов, то буду дико рад.

Немного истории

NET SIMD впервые появился в 2015 году с выходом . В . 6. NET Framework 4. Позже был добавлен тип Vector<T>, который предоставил больше возможностей для векторизации алгоритмов. Тогда были добавлены типы Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3 и Vector4, которые позволили прозводить векторизированные вычисления. вышеописанные типы ограничивали поток мыслей программиста и не давали возможности использовать полную мощь SIMD-инструкций современных процессоров. Но многие программисты всё равно были недовольны, т.к. NET Core 3. Уже в наше время, в . Runtime. 0 Preview появилось пространство имён System. Чтобы получить наилучшие результаты в скорости надо использовать RyuJit и нужно либо собирать под x64, либо отключить Prefer 32-bit и собирать под AnyCPU. Intrinsics, которое предоставляет гораздо большую свободу в выборе инструкций. 40GHz (Skylake). Все бенчмарки я запускал на компьютере с процессором Intel Core i7-6700 CPU 3.

Суммируем элементы массива

Это задача нахождения суммы элементов массива. Я решил начать с классической задачи, которую часто пишут первой, когда речь заходит про векторизацию. Напишем четыре реализации этой задачи, будем суммировать элементы массива Array:

Самая очевидная

public int Naive() return result;
}

С использованием LINQ

public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);

Numerics: С использованием векторов из System.

public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result;
}

Runtime. С использованием кода из пространства System. Intrinsics:

public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result;
}

Я запустил бенчмарк на эти 4 метода у себя на компьютере и получил такой результат:

Method

ItemsCount

Median

Naive

10

75.12 ns

LINQ

10

1 186.85 ns

Vectors

10

60.09 ns

Intrinsics

10

255.40 ns

Naive

100

360.56 ns

LINQ

100

2 719.24 ns

Vectors

100

60.09 ns

Intrinsics

100

345.54 ns

Naive

1000

1 847.88 ns

LINQ

1000

12 033.78 ns

Vectors

1000

240.38 ns

Intrinsics

1000

630.98 ns

Naive

10000

18 403.72 ns

LINQ

10000

102 489.96 ns

Vectors

10000

7 316.42 ns

Intrinsics

10000

3 365.25 ns

Naive

100000

176 630.67 ns

LINQ

100000

975 998.24 ns

Vectors

100000

78 828.03 ns

Intrinsics

100000

41 269.41 ns

Теперь надо разобраться что происходит в этих двух методах. Видно, что решения с Vectors и Intrinsics очень сильно выигрывают в скорости по сравнению с очевидным решением и с LINQ.

Рассмотрим подробнее метод Vectors:

Vectors

public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result;
}

  • int vectorSize = Vector<int>.Count; — это сколько 4х байтовых чисел мы можем поместить в вектор. Если используется аппаратное ускорение, то эта величина показывает сколько 4х-байтовых чисел можно поместить в один SIMD регистр. По сути она показывает над сколькими элементами данного типа можно проводить операции параллельно;
  • accVector — вектор, в котором будет накапливаться результат функции;
    var v = new Vector<int>(array, i); — загружаются данные в новый вектор v, из array, начиная с индекса i. Загрузится ровно vectorSize данных.
  • accVector = Vector.Add(accVector, v); — складываются два вектора.
    Например в Array хранится 8 чисел: {0, 1, 2, 3, 4, 5, 6, 7} и vectorSize == 4, тогда:
    В первой итерации цикла accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3}, после сложения в accVector будет: {0, 0, 0, 0} + {0, 1, 2, 3} = {0, 1, 2, 3}.
    Во второй итерации v = {4, 5, 6, 7} и после сложения accVector = {0, 1, 2, 3} + {4, 5, 6, 7} = {4, 6, 8, 10}.
  • Остаётся только как-то получить сумму всех элементов вектора, для этого можно применить скалярное умножение на вектор, заполненный единицами: int result = Vector.Dot(accVector, Vector<int>.One);
    Тогда получится: {4, 6, 8, 10} {1, 1, 1, 1} = 4 1 + 6 1 + 8 1 + 10 * 1 = 28.
  • В конце, если требуется, то досуммируются числа, которые не помещаются в последний вектор.

Если взглянуть в код метода Intrinsics:

Intrinsics

public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result;
}

То можно увидеть, что он очень похож на Vectors за некоторым исключением:

Сравниваем два массива

Собственно это та задача, из-за которой я начал изучать SIMD в . Надо сравнить два массива байт. Напишем опять несколько методов для бенчмарка, будем сравнивать два массива: ArrayA и ArrayB: NET.

Самое очевидное решение:

public bool Naive() { for (int i = 0; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true;
}

Решение через LINQ:

public bool LINQ() => ArrayA.SequenceEqual(ArrayB);

Решение через функцию MemCmp:

[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)]
static extern int memcmp(byte[] b1, byte[] b2, long count); public bool MemCmp() => memcmp(ArrayA, ArrayB, ArrayA.Length) == 0;

Numerics: С использованием векторов из System.

public bool Vectors() { int vectorSize = Vector<byte>.Count; int i = 0; for (; i < ArrayA.Length - vectorSize; i += vectorSize) { var va = new Vector<byte>(ArrayA, i); var vb = new Vector<byte>(ArrayB, i); if (!Vector.EqualsAll(va, vb)) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true;
}

С использованием Intrinsics:

public unsafe bool Intrinsics() { int vectorSize = 256 / 8; int i = 0; const int equalsMask = unchecked((int) (0b1111_1111_1111_1111_1111_1111_1111_1111)); fixed (byte* ptrA = ArrayA) fixed (byte* ptrB = ArrayB) { for (; i < ArrayA.Length - vectorSize; i += vectorSize) { var va = Avx2.LoadVector256(ptrA + i); var vb = Avx2.LoadVector256(ptrB + i); var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }
}

Результат бэнчмарка на моём компьютере:

Method

ItemsCount

Median

Naive

10000

66 719.1 ns

LINQ

10000

71 211.1 ns

Vectors

10000

3 695.8 ns

MemCmp

10000

600.9 ns

Intrinsics

10000

1 607.5 ns

Naive

100000

588 633.7 ns

LINQ

100000

651 191.3 ns

Vectors

100000

34 659.1 ns

MemCmp

100000

5 513.6 ns

Intrinsics

100000

12 078.9 ns

Naive

1000000

5 637 293.1 ns

LINQ

1000000

6 622 666.0 ns

Vectors

1000000

777 974.2 ns

MemCmp

1000000

361 704.5 ns

Intrinsics

1000000

434 252.7 ns

Весь код этих методов, думаю, понятен, за исключением двух строк в Intrinsics:

var areEqual = Avx2.CompareEqual(va, vb);
if (Avx2.MoveMask(areEqual) != equalsMask) { return false;
}

Получается, что если векторы из байт va и vb полностью равны, то в areEquals все элементы должны равняться 255 (11111111b). В первой два вектора сравниваются на равенство и результат сохраняется в вектор areEqual, у которого в элемент на конкретной позиции все биты выставляются в 1, если соответствующие элементы в va и vb равны. Avx2. Т.к. Значениями битов являются старшие биты каждого из 32 однобайтовых элементов вектора. CompareEqual является обёрткой над _mm256_cmpeq_epi8, то на сайте Intel можно посмотреть псевдокод этой операции:
Метод MoveMask из вектора делает 32-х битное число. Псевдокод можно посмотреть здесь.

MoveMask тоже будут равны 0 и сравнение с equalsMask не пройдёт. Таким образом, если какие-то байты в va и vb не совпадают, то в areEqual соответствующие байты будут равны 0, следовательно старшие биты этих байт тоже будут равны 0, а значит и соответствующие биты в ответе Avx2.

Разберём небольшой пример, приняв что длина вектора 8 байт (чтобы писать было меньше):

  • Пускай va = {100, 10, 20, 30, 100, 40, 50, 100}, а vb = {100, 20, 10, 30, 100, 40, 80, 90};
  • Тогда areEqual будет равен {255, 0, 0, 255, 255, 255, 0, 0};
  • Метод MoveMask вернёт 10011100b, который нужно будет сравнивать с маской 11111111b, т.к. эти маски неравны, то выходит, что и векторы va и vb неравны.

Подсчитываем сколько раз элемент встречается в коллекции

Напишем несколько методов для сравнения, будем искать в массиве Array элемент Item. Иногда требуется посчитать сколько раз конкретный элемент встречается в коллекции, например, интов, этот алгоритм тоже можно ускорить.

Самый очевидный:

public int Naive() { int result = 0; foreach (int i in Array) { if (i == Item) { result++; } } return result;
}

с использованием LINQ:

public int LINQ() => Array.Count(i => i == Item);

Numerics. с использованием векторов из System. Vectors:

public int Vectors() { var mask = new Vector<int>(Item); int vectorSize = Vector<int>.Count; var accResult = new Vector<int>(); int i; var array = Array; for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); var areEqual = Vector.Equals(v, mask); accResult = Vector.Subtract(accResult, areEqual); } int result = 0; for (; i < array.Length; i++) { if (array[i] == Item) { result++; } } result += Vector.Dot(accResult, Vector<int>.One); return result;
}

С использованием Intrinsics:

public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; //var mask = Avx2.SetAllVector256(Item); //var mask = Avx2.SetVector256(Item, Item, Item, Item, Item, Item, Item, Item); var temp = stackalloc int[vectorSize]; for (int j = 0; j < vectorSize; j++) { temp[j] = Item; } var mask = Avx2.LoadVector256(temp); var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); var areEqual = Avx2.CompareEqual(v, mask); accVector = Avx2.Subtract(accVector, areEqual); } } int result = 0; Avx2.Store(temp, accVector); for(int j = 0; j < vectorSize; j++) { result += temp[j]; } for(; i < array.Length; i++) { if (array[i] == Item) { result++; } } return result;
}

Результат бенчмарка на моём компьютере:

Method

ItemsCount

Median

Naive

1000

2 824.41 ns

LINQ

1000

12 138.95 ns

Vectors

1000

961.50 ns

Intrinsics

1000

691.08 ns

Naive

10000

27 072.25 ns

LINQ

10000

113 967.87 ns

Vectors

10000

7 571.82 ns

Intrinsics

10000

4 296.71 ns

Naive

100000

361 028.46 ns

LINQ

100000

1 091 994.28 ns

Vectors

100000

82 839.29 ns

Intrinsics

100000

40 307.91 ns

Naive

1000000

1 634 175.46 ns

LINQ

1000000

6 194 257.38 ns

Vectors

1000000

583 901.29 ns

Intrinsics

1000000

413 520.38 ns

Идея в целом такая: Методы Vectors и Intrinsics полностью совпадают в логике, отличия только в реализации конкретных операций.

  • создаётся вектор mask, в котором в каждом элементе храниться искомое число;
  • Загружается в вектор v часть массива и сравнивается с маской, тогда в равных элементах в areEqual будут выставлены все биты, т.к. areEqual — вектор из интов, то, если выставить все биты одного элемента, получим -1 в этом элементе ((int)(1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
  • вычитается из accVector вектор areEqual и тогда в accVector будет сумма того, сколько раз элемент item встретился во всех векторах v для каждой позиции (минус на минут дают плюс).

Весь код из статьи можно найти на GitHub

Заключение

NET для векторизации вычислений. Я рассмотрел лишь очень малую часть возможностей, которые предоставляет . NETCORE под x86 можно обратиться к исходному коду. За полным и актуальным список доступных интринсиков в . NET. Удобно, что там в C# файлах в summary каждого интринсика есть его же название из мира C, что упрощает и понимание назначения этого интринсика, и перевод уже существующих С++/С алгоритмов на . Numerics. Документация по System. Vector доступна на msdn.

NET есть большое преимущество перед C++, т.к. На мой вгляд, у . При этом программист для написания быстрого кода может оставаться в рамках одного языка и технологий. JIT компиляция происходит уже на клиентской машине, то компилятор может оптимизировать код под конкретный клиентский процессор, предоставляя максимальную производительность.

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть