Вы не указали какую-либо конкретную архитектуру, поэтому я сохраню эту архитектуру в основном нейтральной с помощью алгоритма, описанного на английском языке.Но для этого требуется SIMD ISA, который может эффективно переходить на SIMD, сравнивать результаты для проверки обычно истинного условия, такого как x86, но не совсем ARM NEON.
Это не будет работать хорошо для NEON, потому что у него нетэквивалент движущей маски, и SIMD -> целое число вызывает остановку во многих микроархитектурах 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 применяется к другим.И возможно, что в этом векторе есть несколько новых обновлений min-min, а в любой из этих точек - кандидаты new-diff.
Так что обрабатывайте этот вектор скалярным кодом (обновление скаляра diff, которое не нужночтобы быть синхронизированным с вектором diffmax, потому что нам не нужно положение).
Передайте окончательные min на vmin, когда вы закончите.Или выполните SIMD по горизонтали min, чтобы можно было начать выполнение более поздних итераций SIMD без ожидания скалярного vmin.Должно работать хорошо, если скалярный код не имеет разветвлений, поэтому в скалярном коде нет ошибочных прогнозов, которые приводят к выбрасыванию более поздней векторной работы.
В качестве альтернативы, SIMD-префикс-тип вещей(на самом деле prefix-min) может дать vmin, где каждый элемент - это минимальное значение до этой точки. ( параллельный префикс (накопительная) сумма с SSE ).Вы можете всегда делать это, чтобы избежать ветвления, но если новые кандидаты редки, то это дорого.Тем не менее, это может быть жизнеспособным на ARM NEON, где ветвление затруднено.
Если нет нового минимума, SIMD упакован максимум diffmax[0..7] = max(diffmax[0..7], v[0..7]-vmin).(Используйте насыщающее вычитание, чтобы избежать больших различий без знака, если вы используете беззнаковый максимум для обработки всего диапазона.)
В концецикл, сделайте SIMD горизонтальный максимум вектора diffmax.Обратите внимание, что поскольку нам не не нужна позиция максимальной разницы, нам не нужно обновлять все элементы внутри цикла, когда кто-то находит нового кандидата.Нам даже не нужно синхронизировать скалярный специальный случай diffmax и SIMD vdiffmax друг с другом, просто проверьте в конце, чтобы получить максимальное значение скаляра и максимальное различие SIMD.
SIMD мин / макс в основном совпадает с горизонтальной суммой, за исключением того, что вы используете упакованный-максимум вместо упакованного-добавления.Для x86 см. Самый быстрый способ сделать горизонтальную векторную сумму с плавающей запятой на x86 .
или на x86 с SSE4.1 для 16-разрядных целочисленных элементов, phminposuw / _mm_minpos_epu16 может бытьиспользуется для min или max, со знаком или без знака, с соответствующими настройками для ввода.max = -min(-diffmax).Вы можете рассматривать diffmax как неподписанный, потому что он известен как неотрицательный, но Горизонтальный минимум и максимум с использованием SSE показывает, как перевернуть знаковый бит для сдвига диапазона со знаком со знаком без знака и обратно.
Мы, вероятно, получаем ошибочный прогноз ветви каждый раз, когда находим нового min кандидата, или же мы слишком часто находим новых min кандидатов, чтобы это было эффективным.
Если часто ожидают новых min кандидатов, лучше использовать более короткие векторы.Или, обнаружив, что в текущем векторе есть новое значение - min, затем используйте более узкие векторы, чтобы скалярно использовать только меньшее количество элементов.На x86 вы можете использовать bsf (bit-scan forward), чтобы найти, какой элемент имеет первый новый мин.Это дает вашему скалярному коду зависимость данных от векторной маски сравнения, но если ответвление было неверно предсказано, тогда маска сравнения будет готова.В противном случае, если предсказание ветвления может каким-то образом найти шаблон, в котором векторам необходим скалярный запасной вариант, предсказание + умозрительное выполнение нарушит эту зависимость данных.
Незавершенный / сломанный (мной) пример, адаптированный из удаленного @ harold'sответ о версии без ответвлений, которая на лету создает вектор min-up-to-that-element для x86 SSE2.
(@ harold написал его с суффиксом-max вместо min, то есть IПодумайте, почему он удалил его. Я частично преобразовал его из 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.