Wektoryzacja warunkowego użycia szortów

Question

Używam zwartej struktury 2 niepodpisanych szortów wskazujących pozycję początkową i końcową.
Potrzebuję być w stanie szybko określić, czy istnieją jakieś obiekty Range o długości (różnica od początku do końca) poza wartością progową.

Będę miał ogromną liczbę obiektów, każdy z własną tablicą Range, więc nie jest możliwe śledzenie, które obiekty Range znajdują się powyżej progu na liście lub coś takiego. Ten kod będzie również uruchamiany bardzo często (wiele razy na sekundę dla każdej tablicy), więc musi być wydajny.

struct Range 
{ 
unsigned short start; 
unsigned short end; 
} 

będą zawsze mieć tablicę Range wymiarach 2^n. Chociaż chciałbym przerwać, gdy tylko znajdę coś powyżej progu, jestem prawie pewny, że szybsze byłoby po prostu LUB wszystko razem i sprawdzić na końcu ... zakładając, że mogę wektoryzować pętlę. Chociaż gdybym mógł zrobić instrukcję if na kawałku wyników dla każdego wektora, byłoby to wspaniałe.

size_t rangecount = 1 << resolution; 
Range* ranges = new Range[rangecount]; 

... 

bool result = false; 
for (size_t i = 0; i < ranges; ++i) 
{ 
result |= (range[i].end - range[i].start) > 4; 
} 

Nic dziwnego, że auto-Vectorizer daje błąd 1202, ponieważ mój typ danych nie 32 lub 64 bitów szerokości. Naprawdę nie chcę podwoić mojego rozmiaru danych i sprawić, aby każde pole było niepodpisane. Zgaduję, że auto-vectorizer jest na to gotowy.

Czy istnieją instrukcje wektorowe, które obsługują zmienne 16-bitowe? Jeśli są, jak mogę ich użyć w C++ do wektoryzacji mojej pętli?

Answer 1

Zastanawiasz się, czy jakakolwiek wartość jest większa niż 4?

Tak, istnieją instrukcje SIMD dla tego. To niefortunne, że auto-wektoryzacja nie jest w stanie obsłużyć tego scenariusza. Oto wektorowy algorytm:

diff_v = end_v - start_v; // _mm_hsub_epi16 
floor_v = max(4_v, diff_v); // _mm_max_epi16 
if (floor_v != 4_v) return true; // wide scalar comparison 

Zastosowanie _mm_sub_epi16 o strukturze macierzy lub _mm_hsub_epi16 z tablicą struktur.

Właściwie od start są przechowywane w pamięci pierwszy, będziesz pracować na start_v - end_v, więc używaj _mm_min_epi16 i wektorem -4.

Każda instrukcja SSE3 będzie wykonywać 8 porównań naraz. Najszybciej będzie wrócić wcześniej, niż do pętli. Jednak rozwijanie pętli nieco więcej może przynieść ci dodatkową prędkość (przekaż pierwszy zestaw wyników do zapakowanej funkcji min/max, aby je połączyć).

więc skończyć z (w przybliżeniu):

most_negative = threshold = _mm_set_epi64(0xFCFCFCFCFCFCFCFC); // vectorized -4 

loop: 
    a = load from range; 
    b = load from range; 
    diff = _mm_hsub_epi16(a, b); 
    most_negative = _mm_min_epi16(most_negative, diff); 

    // unroll by repeating the above four instructions 4 times or so 
    if (most_negative != threshold) return true; 
repeat loop