Не сте посочили конкретна архитектура, така че ще запазя тази предимно архитектура неутрална с алгоритъм, описан на английски. Но изисква SIMD ISA, който може ефективно да се разклонява на резултатите от сравняване на SIMD, за да провери обикновено вярно състояние, като x86, но не наистина ARM NEON.
Това няма да работи добре за NEON, защото няма еквивалент на movemask, а SIMD -> integer причинява спирания на много ARM микроархитектури.
Нормалният случай при преминаване през масива е, че даден елемент или цял SIMD вектор от елементи не е нов min, а не diff кандидат. Можем бързо да прелитаме през тези елементи, като само забавяме, за да разберем подробностите, когато има нов min. Това е като SIMD strlen или SIMD memcmp, с изключение на това, че вместо да спрем при първото търсене, ние просто преминаваме скаларно за един блок и след това възобновяваме.
За всеки вектор v[0..7] от входния масив (приемайки 8 int16_t елемента на вектор (16 байта), но това е произволно):
SIMD сравнява vmin > v[0..7] и проверява за верни елементи. (напр. x86 _mm_cmpgt_epi16 / if(_mm_movemask_epi8(cmp) != 0)) Ако някъде има нов min, имаме специален случай: старият min се прилага за някои елементи, но новият min се прилага за други. И е възможно да има множество актуализации на нови минути във вектора и кандидати за нови разлики във всяка от тези точки.
Така че боравете с този вектор със скаларен код (актуализирайки скалар diff, който не е необходимо да бъде синхронизиран с вектора diffmax, защото нямаме нужда от позиция).
Излъчете последните min до vmin, когато сте готови. Или направете SIMD хоризонтално min, така че изпълнението извън реда на по-късни SIMD итерации да може да започне, без да чакате vmin от скалар. Трябва да работи добре, ако скаларният код е без разклонения, така че няма грешни прогнози в скаларния код, които причиняват изхвърляне на по-късна векторна работа.
Като алтернатива, SIMD тип префикс-сума (всъщност prefix-min) може да произведе vmin, където всеки елемент е min до този момент. (паралелна префиксна (кумулативна) сума със SSE). Бихте могли винаги да направите това, за да избегнете всякакво разклоняване, но ако новите мин кандидати са редки, тогава е скъпо. Все пак може да е жизнеспособен на ARM NEON, където разклоняването е трудно.
Ако няма нова мин., SIMD опакована макс. diffmax[0..7] = max(diffmax[0..7], v[0..7]-vmin). (Използвайте насищащо изваждане, за да не получите обгръщане до голяма разлика без знак, ако използвате max без знак за обработка на пълния диапазон.)
В края на цикъла направете SIMD хоризонтален макс на diffmax вектора. Забележете, че тъй като не се нуждаем от позицията на максималната разлика, не е необходимо да актуализираме всички елементи в цикъла, когато някой намери нов кандидат. Дори не е нужно да поддържаме скаларния специален случай diffmax и SIMD vdiffmax в синхрон помежду си, просто проверете в края, за да вземете максимума на скаларния и SIMD макс.
SIMD min/max е основно същото като хоризонталната сума, с изключение на това, че използвате packed-max вместо packed-add. За x86 вижте Най-бързият начин да направите хоризонтална плаваща векторна сума на x86.
Или на x86 със SSE4.1 за 16-битови цели числа, phminposuw / _mm_minpos_epu16 може да се използва за min или max, със знак или без знак, с подходящи настройки на входа. max = -min(-diffmax). Можете да третирате diffmax като unsigned, защото е известно, че е неотрицателен, но Хоризонтален минимум и максимум с помощта на SSE показва как да обърнете знаковия бит към обхват-преместване на знак към беззнаков и обратно.
Вероятно получаваме погрешно предвиждане на клон всеки път, когато намерим нов min кандидат, или пък намираме нови min кандидати твърде често, за да е ефективно.
Ако често се очакват нови min кандидати, използването на по-къси вектори може да е добро. Или при откриване на нов-min в текущия вектор, тогава използвайте по-тесни вектори, за да преминете скаларно върху по-малко елементи. На x86 можете да използвате bsf (bit-scan forward), за да намерите кой елемент е имал първия new-min. Това дава на скаларния ви код зависимост на данните от векторната маска за сравнение, но ако клонът към него е бил неправилно предвиден, тогава маската за сравнение ще бъде готова. В противен случай, ако прогнозирането на разклонения може по някакъв начин да намери модел, в който векторите се нуждаят от скаларния резервен вариант, прогнозирането+спекулативното изпълнение ще наруши тази зависимост от данни.
Незавършен/счупен (от мен) пример, адаптиран от изтрития отговор на @harold за напълно безклонова версия, която конструира вектор от min-up-to-that-element в движение, за x86 SSE2.
(@harold го написа със суфикс-max вместо min, което според мен е причината да го изтрие. Преобразувах го частично от max в min.)
Безразклонена вътрешна версия за x86 може да изглежда нещо така. Но разклоненото вероятно е по-добро, освен ако не очаквате някакъв вид наклон или тенденция, която прави новите min стойности чести.
// BROKEN, see FIXME comments.
// converted from @harold's suffix-max version
int broken_unfinished_maxDiffSSE(const std::vector<uint16_t> &input) {
const uint16_t *ptr = input.data();
// construct suffix-min
// find max-diff at the same time
__m128i min = _mm_set_epi32(-1);
__m128i maxdiff = _mm_setzero_si128();
size_t i = input.size();
for (; i >= 8; i -= 8) {
__m128i data = _mm_loadu_si128((const __m128i*)(ptr + i - 8));
// FIXME: need to shift in 0xFFFF, not 0, for min.
// or keep the old data, maybe with _mm_alignr_epi8
__m128i d = data;
// link with suffix
d = _mm_min_epu16(d, _mm_slli_si128(max, 14));
// do suffix-min within block.
d = _mm_min_epu16(d, _mm_srli_si128(d, 2));
d = _mm_min_epu16(d, _mm_shuffle_epi32(d, 0xFA));
d = _mm_min_epu16(d, _mm_shuffle_epi32(d, 0xEE));
max = d;
// update max-diff
__m128i diff = _mm_subs_epu16(data, min); // with saturation to 0
maxdiff = _mm_max_epu16(maxdiff, diff);
}
// horizontal max
maxdiff = _mm_max_epu16(maxdiff, _mm_srli_si128(maxdiff, 2));
maxdiff = _mm_max_epu16(maxdiff, _mm_shuffle_epi32(maxdiff, 0xFA));
maxdiff = _mm_max_epu16(maxdiff, _mm_shuffle_epi32(maxdiff, 0xEE));
int res = _mm_cvtsi128_si32(maxdiff) & 0xFFFF;
unsigned scalarmin = _mm_extract_epi16(min, 7); // last element of last vector
for (; i != 0; i--) {
scalarmin = std::min(scalarmin, ptr[i - 1]);
res = std::max(res, ptr[i - 1] - scalarmin);
}
return res != 0 ? res : -1;
}
Можем да заменим скаларното почистване с окончателен неподравнен вектор, ако се справим с припокриването между последния пълен вектор min.
person
Peter Cordes
schedule
25.09.2018
