Есть ли какие-либо инструкции asm, которые могут ускорить вычисление min/max вектора double/integers на архитектуре Core i7?x86 max/min asm инструкции?
Update:
Я не ожидал, что такие богатые ответы, спасибо. Итак, я вижу, что max/min можно обойтись без разветвления. У меня есть вопрос:
Есть ли эффективный способ получить индекс самого большого двойника в массиве?
SSE4 имеет PMAXSD или PMAXUD для 32-битных подписных/беззнаковых целых чисел, что может быть полезно.
SSE2 имеет MAXPD и MAXSD которые сравнивают между и между парами двойников, так что вы будете следовать п/2-1 MAXPDs с одним MAXSD, чтобы получить максимум вектора п, с обычным переплетением нагрузок и операций.
Имеются эквиваленты MIN, указанные выше.
Для двойной случае, вы, вероятно, не будет делать лучше на ассемблере, чем наполовину приличная компилятор C++ в режиме SSE:
peregrino:$ g++ -O3 src/min_max.cpp -o bin/min_max
peregrino:$ g++ -O3 -msse4 -mfpmath=sse src/min_max.cpp -o bin/min_max_sse
peregrino:$ time bin/min_max
0,40
real 0m0.874s
user 0m0.796s
sys 0m0.004s
peregrino:$ time bin/min_max_sse
0,40
real 0m0.457s
user 0m0.404s
sys 0m0.000s
где min_max вычисляет минимальное и максимальное из массива 500 дублей 100000 раз, используя наивный цикл:
bool min_max (double array[], size_t len, double& min, double& max)
{
double min_value = array [ 0 ];
double max_value = array [ 0 ];
for (size_t index = 1; index < len; ++index) {
if (array [ index ] < min_value) min_value = array [ index ];
if (array [ index ] > max_value) max_value = array [ index ];
}
min = min_value;
max = max_value;
}
в ответ на вторую часть традиционной оптимизации для удаления разветвлений от максимальной операции сравнить значения, получить флаг как грех gle bit (давая 0 или 1), вычтите один (давая 0 или 0xffff_ffff) и 'и' его с xor двух возможных результатов, так что вы получите эквивалент (a > best ? (current_index^best_index) : 0)^best_index). Я сомневаюсь, что есть простой способ SSE сделать это просто потому, что SSE имеет тенденцию работать с упакованными значениями, а не с мечеными значениями; есть некоторые операции с горизонтальным индексом, поэтому вы можете попробовать найти max, а затем вычесть это из всех элементов исходного вектора, затем собрать знаковый бит, а нулевой знак соответствия будет соответствовать индексу max, но это, вероятно, будет не будет улучшения, если вы не используете шорты или байты.
Вам нужно всего лишь log2 (vector_length) shuffle + MAXPS/MAXPD, а не VL/2, чтобы получить горизонтальный максимум одного SIMD-вектора. Это в основном та же идея, что и [горизонтальная сумма] (https://stackoverflow.com/questions/6996764/fastest-way-to-do-horizontal-float-vector-sum-on-x86): узкий пополам каждый раз , (Или, чтобы оставить результат трансляции каждому элементу, поменяйте верхний/низкий). –
Развертывание с несколькими аккумуляторами должно дать лучшее, чем 2x ускорение, если вы не узки в памяти. («MAXPD» имеет задержку 3 или 4 цикла, но пропускную способность 1 за цикл, поэтому вам нужен компилятор для извлечения asm, который использует несколько векторов и объединяет их в конце массива.) Clang имеет тенденцию делать это, векторизация, но gcc все равно обычно этого не делает. –
MAXPS и MINPS от SSE работают на упакованных числах с плавающей точкой с одной точностью. PMAXSW, PMINSW, PMAXUB и PMINUB работают на упакованных 8-битных словах, как подписанных, так и неподписанных. Обратите внимание, что они сравнивают два входных регистра SSE или адресные адреса по элементам и сохраняют результат в регистре SSE или в памяти.
Версия MAXPS и MINPS для SSE2 должна работать на поплавках с двойной точностью.
Какие флаги для компилятора и оптимизации используются? gcc 4.0 и выше должны автоматически векторизовать операции, если ваша цель поддерживает их, более ранним версиям может понадобиться определенный флаг.
если ваш используете IPP библиотеки Intel, вы можете использовать вектор statistical functions для расчета вектора мин/макс (среди прочего)
В ответ на ваш второй вопрос: на большинстве платформ, есть библиотеки, которые уже содержатся оптимизированные реализации этой самой операции (и большинство других простых векторных операций). Используйте их.
vDSP_maxviD() и cblas_idamax() в Accelerate.frameworkcblas_idamax() системcblas_idamax() в библиотеке BLAS, которая может быть или не быть настроена в зависимости от ее происхождения; пользователи, которые заботятся о производительности, обычно имеют хорошую реализацию (или могут быть убеждены в ее установке)В ответ на ваш второй вопрос, возможно, стоит подумать о том, как вы собираете и храните эти данные.
Вы можете хранить данные в B-дереве, которое хранит данные, отсортированные в любое время, требуя только логарифмических операций сравнения.
Тогда вы всегда знаете, где максимум.
Поскольку вы имеете дело только с 300 двойными, самобалансированное бинарное дерево, вероятно, лучше всего. http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree – Drew
Почему бы не двоичную кучу? Постоянное время лучше логарифмического ... –
Обновление: Я просто понял, что вы сказали «массив», а не «вектор» в части 2. Я оставлю это здесь в любом случае, в случае, если это полезно.
Re: часть вторая: найти индекс макс/мин элемента в векторе SSE:
сделать горизонтальный максимум. Для 128b-вектора из 2 double элементов это всего лишь один shufpd + maxpd, чтобы оставить результат трансляцией обоих элементов.
Для других случаев, конечно, потребуется больше шагов. См. Fastest way to do horizontal float vector sum on x86 для идей, заменяя addps на maxps или minps. (Но обратите внимание, что 16-битовое целое является особенным, потому что вы можете использовать SSE. Для макс, вычесть из 255)
Сделайте упакованное сравнение между векторным исходным вектором и вектором, где каждый элемент является максимальным.
(pcmpeqq целые битовые узоры или обычные cmpeqpd оба будут работать для корпуса double).
int _mm_movemask_pd (__m128d a) (movmskpd) Чтобы получить результат сравнения как целочисленное растровое изображение.bsf) для (первого) совпадения: index = _bit_scan_forward(cmpmask). cmpmask = 0 невозможно, если вы использовали целое число (потому что хотя бы один элемент будет соответствовать, даже если они являются NaN).Это должно составить только 6 инструкций (включая movapd). Да, просто проверил на the Godbolt compiler explorer, и это происходит, с SSE.
#include <immintrin.h>
#include <x86intrin.h>
int maxpos(__m128d v) {
__m128d swapped = _mm_shuffle_pd(v,v, 1);
__m128d maxbcast = _mm_max_pd(swapped, v);
__m128d cmp = _mm_cmpeq_pd(maxbcast, v);
int cmpmask = _mm_movemask_pd(cmp);
return _bit_scan_forward(cmpmask);
}
Отметьте, что _mm_max_pd is not commutative with NaN inputs.Если NaN возможно, и вы не заботитесь о производительности на Intel Nehalem, вы можете использовать _mm_cmpeq_epi64 для сравнения битовых шаблонов. Тем не менее, байпас-задержка от float до vec-int является проблемой для Nehalem.
NaN! = NaN в плавающей точке IEEE, поэтому маска результата _mm_cmpeq_pd может быть равна нулю в случае всего NaN.
Еще одна вещь, которую вы можете сделать в случае с 2 элементами, чтобы всегда получать 0 или 1, - это заменить бит-сканирование на cmpmask >> 1. (bsf странно с вводом = all-zero).
Что такое основной язык? Если это c/C++, я бы не стал слишком беспокоиться об этом. –
Максимум около 300 удваивается в самой внутренней петле большой программы. 5% времени проводится примерно в 10 из 8'000 строк кода. Язык хоста не имеет значения только из-за этого. Но да, это C++ –