Има ли 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 неща, които да сумират байтове в 128b регистри или може би да сумират байтове независимо между два регистъра, без да носят преноса, или и двете.

Има ли такова нещо там?

Забележка: Това Е действително преждевременна оптимизация, но е забавно, така че какво, по дяволите?

Редактиране: Все още имам нужда от начин да обобщя всички байтове в 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];

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 intrinsics. И е забавно! :)   -  person    schedule 23.02.2012


Отговори (2)


Да, има такива инструкции в набора от инструкции 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

Вижте _mm_add_ps. Едновременно добавяне на 128-битов непрекъснат блок. Ще трябва да нулирате своя масив или да обработите последните няколко стила, които не са SIMD.

person totowtwo    schedule 12.07.2011