Существуют ли SIMD-инструкции для ускорения вычисления контрольной суммы?

Мне нужно будет написать очень простую функцию контрольной суммы, например:

char sum(const char * data, const int len)
{
    char sum(0);
    for (const char * end=data+len ; data<end ; ++data)
        sum += *data;
    return sum;
}

Это тривиально. Теперь, как я должен оптимизировать это? Во-первых, мне, вероятно, следует использовать какой-нибудь std::for_each с лямбдой или что-то в этом роде:

char sum2(const char * data, const int len)
{
    char sum(0);
    std::for_each(data, data+len, [&sum](char b){sum+=b;});
    return sum;
}

Затем я мог бы использовать несколько потоков/ядер для суммирования фрагментов, а затем добавить результаты. Я не буду это записывать, и я боюсь, что стоимость создания потоков (или получения их из пула в любом случае), затем разрезания массива, затем диспетчеризации всего и т. д., будет не очень хорошей, учитывая, что я в основном вычислять контрольные суммы для небольших массивов, в основном 10-100 байт, редко до 1000.

Но то, что я действительно хочу, это что-то более низкого уровня, что-то вроде SIMD, которое суммировало бы байты в 128-битных регистрах или, может быть, независимо суммировало бы байты между двумя регистрами без переноса, или и то, и другое.

Есть ли там что-то подобное?

Примечание. Это действительно преждевременная оптимизация, но это весело, так что, черт возьми?

Редактировать: мне все еще нужен способ суммировать все байты в регистре SSE, что-то лучше, чем

char ptr[16];
_mm_storeu_si128((__m128i*)ptr, sum);
checksum += ptr[0] + ptr[1] + ptr[2]  + ptr[3]  + ptr[4]  + ptr[5]  + ptr[6]  + ptr[7]
          + ptr[8] + ptr[9] + ptr[10] + ptr[11] + ptr[12] + ptr[13] + ptr[14] + ptr[15];

c++ checksum simd
person Gabriel    schedule 12.07.2011    source источник
comment
У меня нет фактических доказательств этого, но я подозреваю, что версия std::for_each будет медленнее, чем ручной метод...   -  person Mike Caron    schedule 13.07.2011
comment
Я предполагаю, что вы хотите, чтобы Intel Opps здесь?   -  person Michael Dorgan    schedule 13.07.2011
comment
@Mike Зависит, на самом деле это медленнее для маленьких пакетов, но быстрее для больших. Я тестировал с 100b и 900b, я не знаю, где предел для моей настройки. Я предполагаю, что стоимость создания объекта связана с этим. Неудивительно, что SSE превзошли оба для обоих размеров.   -  person Gabriel    schedule 13.07.2011
comment
@Gabriel: это не преждевременная оптимизация. В моем проекте, например, это было самое медленное место. Сначала раскатал на 4, что дало много буста, но все равно было самым медленным. Поэтому мне пришлось переписать его, используя встроенные функции SSE. И это весело! :)   -  person    schedule 23.02.2012

Ответы (2)


arrow_upward
2
arrow_downward

Да, в наборе инструкций MMX есть такие инструкции, называемые «Packed ADD»:

  • _mm_add_pi8 в Visual C++
  • __builtin_ia32_paddb в gcc

И в наборе инструкций SSE2:

РЕДАКТИРОВАТЬ: более быстрый способ добавить частичные суммы:

__m128i sums;

sums = _mm_add_epi8(sums, _mm_srli_si128(sums, 1));
sums = _mm_add_epi8(sums, _mm_srli_si128(sums, 2));
sums = _mm_add_epi8(sums, _mm_srli_si128(sums, 4));
sums = _mm_add_epi8(sums, _mm_srli_si128(sums, 8));
checksum += _mm_cvtsi128_si32(sums);
person Ben Voigt    schedule 12.07.2011
comment
Теперь, достаточно ли какой-нибудь крутой компилятор, чтобы создать правильный код с учетом циклов, описанных выше? - person Gabriel; 13.07.2011
comment
Я не могу себе представить, чтобы большинство компиляторов потрудились выдавать SSE для первого цикла. Раздражает попытка загрузки с произвольного указателя — компилятор не знает, выровнена ли цель, может ли она загружаться фрагментами размером с SSE и т. д. - person John Calsbeek; 13.07.2011
comment
Здесь нет необходимости использовать имена компиляторов. GCC, а также Visual C++ поддерживают стандартные заголовки и функции расширений MMX/SSE. Я не пользователь MMX/SSE, но проверьте, например, <mmintrin.h> для прототипов. - person rubenvb; 13.07.2011

arrow_upward
-1
arrow_downward

Посмотрите на _mm_add_ps. Одновременное добавление 128-битного непрерывного блока. Вам нужно будет обнулить свой массив или обработать последние несколько стилей, отличных от SIMD.

person totowtwo    schedule 12.07.2011