Szybszy abs-max z macierzą zmiennoprzecinkową

Question

Potrzebuję narysować mierniki szczytowe dla dźwięku w czasie rzeczywistym. Minimum 44100 próbek na sekundę razy co najmniej 40 strumieni. Każdy bufor zawiera od 64 do 1024 próbek. Muszę pobrać abs max z każdego bufora. (Są one następnie podawane przez pewien rodzaj filtra dolnoprzepustowego i pobierane w odstępach około 20 ms.)

for(int i = 0; i < numSamples; i++) 
{ 
     absMaxOfBuffer = MAX(fabs(buffer[i]), absMaxOfBuffer); 
} 

Tak to teraz robię. Chciałbym to zrobić znacznie szybciej. Bufory mają pływaki w zakresie od -1 do 1, a więc z fabs.

Pytanie, czy jest jakiś skomplikowany sposób na szybkie i szybkie korzystanie z programu quicksort?

Jeśli te funkcje ABS i MAX są bez gałęzi, czy istnieją?

edycja: Podstawową platformą jest Linux/gcc, ale planowany jest port Windows (prawdopodobnie z mingw).

edycja, druga:
Dałem zgodę jednemu ze względu na fragment dotyczący faktycznej struktury alfa, która była kluczowa dla pytania.
Spróbuję rozwinąć pętlę do czterech w tym czasie, zerując znaki, a następnie otrzymując maksimum za pomocą SSE (instrukcja maxps) i zobaczę, czy to nie złuszczy banana. Dzięki za sugestie, oddałem głos niektórym z was, jako zdobywcom drugiego miejsca. :)

Answer 1

Fab i porównanie są bardzo szybkie dla IEEE float (na przykład, single-integer-op fast).

Jeśli kompilator nie obsługuje obu operacji, to albo przesuwaj go do tego czasu, albo znajdź implementację dla architektury i wstaw ją samodzielnie.

Możesz być może uzyskać coś z faktu, że pozytywne IEEE pływa w tej samej kolejności, co liczby całkowite z tymi samymi wzorami bitowymi. Oznacza to, że

f > g iff *(int*)&f > *(int*)&g 

Więc kiedy już fabs'ed, myślę, że oddział wolne max dla int będzie również pracować dla pływaka (przy założeniu, że są tej samej wielkości, oczywiście). Istnieje wyjaśnienie, dlaczego to działa tutaj: http://www.cygnus-software.com/papers/comparingfloats/comparingfloats.htm. Ale twój kompilator już to wszystko zna, podobnie jak twój procesor, więc nie ma to znaczenia.

Nie ma złożoności - szybszy sposób robienia tego. Twój algorytm jest już O (n), i nie możesz tego pokonać i wciąż patrzeć na każdą próbkę.

Domyślam się, że prawdopodobnie jest coś w SIMD twojego procesora (czyli SSE2 na Intel), które pomogłoby, przetwarzając więcej danych na cykl zegara niż twój kod. Ale nie wiem co. Jeśli tak, to prawdopodobnie będzie kilka razy szybciej.

Prawdopodobnie mógłbyś zrównoleglić na wielordzeniowym procesorze, zwłaszcza, że ​​masz do czynienia z 40 niezależnymi strumieniami. To w najlepszym przypadku kilka czynników szybciej. "Wystarczy" wystartować odpowiednią liczbę dodatkowych wątków, podzielić pracę między nimi i użyć najjaśniejszego prymitywu, aby wskazać, kiedy są one kompletne (być może bariera wątku). Nie jestem całkiem pewien, czy wykreślasz maks. 40 strumieni, czy maksimum każdego osobno, więc może nie musisz synchronizować wątków roboczych, poza tym, że wyniki są dostarczane do następnego etapu bez uszkodzenia danych.

Prawdopodobnie warto rzucić okiem na demontaż, aby zobaczyć, ile kompilator rozwinął pętlę. Spróbuj rozwinąć nieco więcej, zobacz, czy to ma znaczenie.

Kolejną kwestią, którą należy przemyśleć, jest liczba braków w pamięci podręcznej, którą można uzyskać, oraz możliwość zmniejszenia liczby pamięci podręcznych dzięki kilku wskazówkom, dzięki czemu można wczytać odpowiednie strony z wyprzedzeniem. Ale nie mam z tym żadnego doświadczenia i nie pokładałabym nadziei. __builtin_prefetch jest magicznym zaklęciem na gcc i myślę, że pierwszym eksperymentem będzie coś w rodzaju "wstępnego pobrania następnego bloku przed wejściem do pętli dla tego bloku".

Jaki procent wymaganej prędkości aktualnie masz? Czy jest to przypadek "tak szybko jak to możliwe"?

Answer 2

odpowiadając na pytanie z innym pytaniem nie odpowiada dokładnie, ale hej ... Nie jestem też programistą C++.

Skoro rozwijasz to w C++ i robisz DSP, czy nie możesz połączyć się z matlab lub oktawą (która jest opensource) z matematyką i uzyskać wynik?

są już funkcje (takie jak conv, fft, ifft, fir i kreślenia funkcji util takich jak freqz, stem, graph, plot, mesh itp.) Zaimplementowanych w tych programach. Spojrzałem w Photoshopie i jest tam duży folder o nazwie MATLAB ... z niektórymi plikami .m, które pobierają wywołania z aplikacji, wysyłają je do dynamicznej rzeczy matlab, a następnie zwracają wynik do aplikacji.

Mam nadzieję, że to pomaga.

Answer 3

warte spróbować:

• Fab() może nie być funkcja inline.
• Pomocna może być specjalna instrukcja montażu. Na Intel, SSE ma instrukcję obliczania maksymalnie czterech floats na raz.
• braku, specyfikacja IEEE 754 jest taka, że ​​w przypadku a i b są nieujemne pływaki, a następnie < B odpowiada int * (*) & w < * (int *) & b. Co więcej, dla każdego a możesz obliczyć -a z a przez przerzucenie MSB. Razem te właściwości mogą umożliwić niektóre bitowe twiddlingowe hacki.
• Czy naprawdę potrzebujesz maksimum każdej próbki? Być może maksimum może wystąpić więcej niż raz, otwierając możliwość nie sprawdzania każdego wejścia.
• Czy możesz obliczyć maksimum w trybie strumieniowym?

Answer 4

Jest tam fabs branchless udokumentowane na http://www.scribd.com/doc/2348628/The-Aggregate-Magic-Algorithms

Należy również pamiętać, że najnowsze wersje GCC będzie wbudować się branchless fabs dla Ciebie, korzystając z instrukcji MMX. Istnieje również fmin i fmax, ale GCC nie wstawia tych (otrzymasz call fmin).

Answer 5

Łatwe optymalizacje widzę:

• tłumaczyć pętlę do wersji wskaźnik arytmetyczna (przy założeniu, że kompilator nie widać tego)
• standard IEEE 754 definiuje jego reprezentację jako znak-wielkości. Zatem ustawienie najbardziej znaczącego bitu na 0 będzie takie samo jak wywołanie fabs().Może ta funkcja już używa tej sztuczki.

Answer 6

Możesz chcieć spojrzeć na Eigen.

Jest to biblioteka C++, który używa szablonu SSE (2 lub nowszy) i instrukcja AltiVec zestawy z wdzięku awaryjnej do kodu non-vectorized.

Szybko. (Zobacz benchmark).
Szablony wyrażeń umożliwiają inteligentne usuwanie tymczasowych plików i włączają leniwą ocenę, o ile jest to odpowiednie - Eigen zajmuje się tym automatycznie i obsługuje w większości przypadków aliasing.
Wyraźna wektoryzacja jest wykonywana dla zestawów instrukcji SSE (2 i późniejsze) i AltiVec, z pełnym wdziękiem powrotem do niezeralizowanego kodu. Szablony wyrażeń umożliwiają wykonywanie tych optymalizacji globalnie dla całych wyrażeń.
W przypadku obiektów o stałym rozmiarze unika się dynamicznego przydzielania pamięci, a pętle są rozwijane, gdy ma to sens.
W przypadku dużych macierzy szczególną uwagę zwraca się na łatwość obsługi pamięci podręcznej.

Answer 7

Dla swojego celu możesz go wyrównać, zamiast przyjmować wartość bezwzględną; jak matematycznie | < | b | jeśli jest to^2 < b^2 i vice versa. Mnożenie może być szybsze niż fabs() na niektórych maszynach (?), Nie wiem.