x86 max/min instrukcje asm?

Question

Czy są jakieś instrukcje asm, które mogą przyspieszyć obliczanie min/maks. Wektora podwójnych/całkowitych w architekturze Core i7?

Aktualizacja:

Nie spodziewałem się tak bogate odpowiedź, dziękuję. Widzę więc, że max/min można obejść bez rozgałęziania. Mam pod-pytanie:

Czy istnieje skuteczny sposób na uzyskanie indeksu największego podwójnego w tablicy?

Answer 1

SSE4 ma PMAXSD lub PMAXUD dla 32-bitowych liczb całkowitych podpisanych/bez znaku, co może być przydatne.

SSE2 ma MAXPD i MAXSD który porównywać i drugiej pary deblu, więc śledzić N/2-1 MAXPDs z jednej MAXSD aby uzyskać max wektora n, ze zwykłymi przeplotu ładunków i operacji.

Istnieje MIN odpowiedników powyższych.

Dla podwójnej przypadku, jesteś prawdopodobnie nie będziemy robić lepiej w asemblerze niż pół-przyzwoity kompilator C++ w trybie 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 

gdzie min_max oblicza min i max tablicy 500 deblu 100000 razy stosując naiwny pętlę:

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; 
} 

---

w odpowiedzi na dwie części, tradycyjny optymalizacja usunięcie rozgałęzień z max pracy jest porównanie wartości dostać flagę jako śpiewać le bit (dając 0 lub 1), odejmij jedną (dając 0 lub 0xffff_ffff) i "i" ją z xor z dwóch możliwych wyników, więc otrzymasz równowartość (a > best ? (current_index^best_index) : 0)^best_index). Wątpię, by był prosty sposób na SSE, po prostu dlatego, że SSE ma tendencję do działania na spakowanych wartościach zamiast oznaczonych wartościach; istnieją pewne poziome operacje indeksu, więc możesz spróbować znaleźć maksimum, a następnie odjąć je od wszystkich elementów w oryginalnym wektorze, a następnie zebrać bit znaku, a zero z podpisem odpowiada indeksowi maksimum, ale prawdopodobnie nie być poprawą, chyba że używasz szortów lub bajtów.

Answer 2

MAXPS i MINPS z SSE działają na liczbach zmiennoprzecinkowych o pojedynczej precyzji z zapakowanymi liczbami. PMAXSW, PMINSW, PMAXUB i PMINUB działają na spakowanych 8-bitowych słowach, podpisanych lub niepodpisanych. Należy zwrócić uwagę, że porównują one dwa wejściowe rejestry SSE lub lokalizacje adresów w sposób elementarny i zapisują wynik w rejestrze SSE lub w pamięci.

Wersje MAXPS i MINPS w wersji SSE2 powinny pracować z pacy o podwójnej precyzji.

Jakich flag kompilatora i optymalizacji używasz? gcc 4.0 i lepsze powinny automatycznie wektoryzować operacje, jeśli twój cel je obsługuje, wcześniejsze wersje mogą wymagać określonej flagi.

Answer 3

jeśli używasz IPP bibliotekę Intela można użyć wektor statistical functions obliczyć wektor min/max (między innymi)

Answer 4

W odpowiedzi na drugie pytanie: na większości platform, istnieją biblioteki, które już zawarte zoptymalizowane implementacje tej samej operacji (i większości innych prostych operacji wektorowych). Używaj ich.

• Na OS X, istnieje vDSP_maxviD() i cblas_idamax() w Accelerate.framework
• Kompilatory Intel obejmują biblioteki IPP i MKL, które mają wysokie implementacje wydajności, w tym cblas_idamax() systemów
• Większość Linux będą musiały cblas_idamax() w bibliotece BLAS, która może lub nie może być dobrze dostrojona w zależności od jej pochodzenia; użytkownicy dbający o wydajność będą na ogół mieli dobrą implementację (lub mogą zostać przekonani do zainstalowania).
• Jeśli wszystko inne zawiedzie, możesz użyć ATLAS (Automatycznie dostrojone oprogramowanie liniowego algebry), aby uzyskać przyzwoitą implementację wydajności na docelowej platformie

Answer 5

W odpowiedzi na twoje drugie pytanie warto zastanowić się nad sposobem gromadzenia i przechowywania tych danych.

Możesz przechowywać dane w drzewie B, które utrzymuje sortowane dane przez cały czas, wymagając tylko logarytmicznych operacji porównania.

Wtedy zawsze wiesz, gdzie jest maksymalna.

http://en.wikipedia.org/wiki/B_tree

Answer 6

Update: Właśnie sobie sprawę, że „tablica”, a nie „wektor” w części 2. Zostawię to tutaj w każdym razie w przypadku jest to użyteczne.

---

Przedmiot część druga: znajdowany elementu max/min w wektorze SSE:

• zrobić poziomy maksimum. W przypadku wektora 128b elementów 2 double to tylko jeden shufpd + maxpd, aby pozostawić wynik dla obu elementów.

  W innych przypadkach będzie to oczywiście wymagało więcej kroków. Aby uzyskać pomysły, zobacz Fastest way to do horizontal float vector sum on x86, zastępując addps przez maxps lub minps. (Należy jednak pamiętać, że 16-bitowa liczba całkowita jest szczególna, ponieważ można użyć SSE4 phminposuw. W przypadku maks. Odjąć od 255)

• Wykonać porównanie w wektorze wektorowym i wektorem, w którym każdy element ma wartość maksymalną.

  (pcmpeqq Wzorce bitowe całkowitoliczbowe lub zwykle cmpeqpd będą działać dla przypadku double).

• int _mm_movemask_pd (__m128d a) (movmskpd), aby uzyskać wynik porównania w postaci bitmapy całkowitej.
• bit-scan (bsf) dla pierwszego dopasowania: index = _bit_scan_forward(cmpmask). cmpmask = 0 jest niemożliwe, jeśli użyłeś porównania liczby całkowitej (ponieważ przynajmniej jeden element będzie pasował, nawet jeśli są NaN).

To powinno się skompilować do tylko 6 instrukcji (w tym movapd). Tak, właśnie sprawdziłem the Godbolt compiler explorer i tak jest z 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); 
} 

Zauważ, że _mm_max_pd is not commutative with NaN inputs.Jeśli NaN jest możliwe i nie zależy Ci na wydajności w Intel Nehalem, możesz rozważyć użycie _mm_cmpeq_epi64 do porównania wzorców bitowych. Opóźnienie bypassu z floata do vec-int jest jednak problemem na Nehalem.

NaN! = NaN w IEEE zmiennoprzecinkowy, więc maska ​​wynikowa _mm_cmpeq_pd może być zerowa w przypadku wszystkich NaN.

Inną rzeczą, którą można zrobić w przypadku 2 elementów, aby zawsze uzyskać 0 lub 1, jest zamiana bit-scan na cmpmask >> 1. (bsf jest dziwny z input = all-zero).