C ++ Добавление 2-х массивов быстро

Question

С учетом массивов:

int canvas[10][10];
int addon[10][10];

Где все значения находятся в диапазоне от 0 до 100, Какой самый быстрый способ в C ++ добавить эти два массива, чтобы каждая ячейка на холсте равнялась себе плюс соответствующее значение ячейки в дополнении?

IE, я хочу добиться чего-то вроде:

canvas += another;

Так что если canvas [0] [0] = 3 и addon [0] [0] = 2, то canvas [0] [0] = 5

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

И в качестве небольшого дополнительного вопроса (спасибо, если вы можете помочь!) Какой самый быстрый способ проверки, если любое из значений в canvas превышает 100? Циклы медленные!

Answer 1

Вот реализация SSE4, которая должна хорошо работать на Nehalem (Core i7):

#include <limits.h>
#include <emmintrin.h>
#include <smmintrin.h>

static inline int canvas_add(int canvas[10][10], int addon[10][10])
{
    __m128i * cp = (__m128i *)&canvas[0][0];
    const __m128i * ap = (__m128i *)&addon[0][0];
    const __m128i vlimit = _mm_set1_epi32(100);
    __m128i vmax = _mm_set1_epi32(INT_MIN);
    __m128i vcmp;
    int cmp;
    int i;

    for (i = 0; i < 10 * 10; i += 4)
    {
        __m128i vc = _mm_loadu_si128(cp);
        __m128i va = _mm_loadu_si128(ap);

        vc = _mm_add_epi32(vc, va);
        vmax = _mm_max_epi32(vmax, vc);   // SSE4 *

        _mm_storeu_si128(cp, vc);

        cp++;
        ap++;
    }
    vcmp = _mm_cmpgt_epi32(vmax, vlimit); // SSE4 *
    cmp = _mm_testz_si128(vcmp, vcmp);    // SSE4 *
    return cmp == 0;
}

Скомпилируйте с gcc -msse4.1 ... или эквивалентным для вашей конкретной среды разработки.

Для более старых процессоров без SSE4 (и с гораздо более дорогими смещенными нагрузками / хранилищами) вам необходимо (a) использовать подходящую комбинацию встроенных функций SSE2 / SSE3 для замены операций SSE4 (отмеченных * выше) и в идеале (b) убедитесь, что ваши данные выровнены по 16 байтам, и используйте выровненные загрузки / хранилища (_mm_load_si128 / _mm_store_si128) вместо _mm_loadu_si128 / _mm_storeu_si128.

Answer 2

Лучшее, что вы собираетесь сделать в стандартном C или C ++, это преобразовать его в одномерный массив из 100 чисел и добавить их в цикл. (Одиночные подписки будут использовать немного меньшую обработку, чем двойные, если компилятор не сможет их оптимизировать. Единственный способ узнать, какой это эффект, если он есть, - это проверить.)

Вы, конечно, можете создать класс, в котором сложение будет представлять собой одну простую инструкцию C ++ (canvas += addon;), но это ничего не ускорит. Все, что могло бы произойти, - это то, что простая инструкция C ++ расширилась бы в цикл выше.

Чтобы ускорить процесс, вам нужно перейти на более низкую обработку. На многих современных процессорах есть дополнительные инструкции для такой обработки, которые вы можете использовать. Возможно, вы сможете запустить что-то подобное на GPU, используя что-то вроде Cuda . Вы можете попытаться сделать операцию параллельной и работать на нескольких ядрах, но в таком маленьком случае вам нужно будет знать, как работает кэширование на вашем процессоре.

Альтернативой является улучшение вашего алгоритма (при решении проблемы типа рюкзака вы можете использовать динамическое программирование каким-либо образом - без дополнительной информации мы не можем вам сказать) или принять представление. Десятки миллионов операций с массивом 10 на 10 превращаются в сотни миллиардов операций с числами, и это не так страшно, как раньше. Конечно, я не знаю ваш сценарий использования или требования к производительности.

Answer 3

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

MacSTL - это библиотека, на которую вы можете посмотреть. Изначально это была библиотека для Macintosh, но теперь она кроссплатформенная. Смотрите их домашнюю страницу для получения дополнительной информации.

Answer 4

Вот альтернатива.

Если вы на 100% уверены, что все ваши значения находятся в диапазоне от 0 до 100, вы можете изменить свой тип с int на uint8_t. Затем вы можете добавить 4 элемента одновременно, используя uint32_t, не беспокоясь о переполнении.

То есть ...

uint8_t  array1[10][10];
uint8_t  array2[10][10];
uint8_t  dest[10][10];
uint32_t *pArr1 = (uint32_t *) &array1[0][0];
uint32_t *pArr2 = (uint32_t *) &array2[0][0];
uint32_t *pDest = (uint32_t *) &dest[0][0];

int  i;

for (i = 0; i < sizeof (dest) / sizeof (uint32_t); i++) {
    pDest[i] = pArr1[i] + pArr2[i];
}

Возможно, он не самый элегантный, но может помочь вам не переходить к конкретному коду архитектуры. Кроме того, если вы сделаете это, я настоятельно рекомендую вам прокомментировать, что вы делаете и почему.

Answer 5

Две части: во-первых, рассмотрим ваш двумерный массив [10] [10] как один массив [100]. Правила компоновки C ++ должны позволять это. Во-вторых, проверьте свой компилятор на наличие встроенных функций, реализующих некоторую форму SIMD-инструкций , таких как Intel SSE. Например, Microsoft поставляет набор . Я полагаю, что у SSE есть некоторые инструкции для проверки максимального значения и даже ограничения до максимального значения, если хотите.

Answer 6

Вы должны проверить CUDA. Проблема такого рода - вправо вверх по улице CUDA. Рекомендую Программирование массово параллельных процессоров книга.

Однако для этого требуется аппаратное обеспечение с поддержкой CUDA, и CUDA требуется немного усилий для настройки в вашей среде разработки, поэтому будет зависеть, насколько это важно на самом деле!

Удачи!