Sprzętowa implementacja pierwiastka kwadratowego?

Próbuję znaleźć trochę więcej informacji na temat wydajnych algorytmów pierwiastkowych, które są najprawdopodobniej zaimplementowane na FPGA. Wiele algorytmów zostało już znalezionych, ale które są na przykład z Intel lub AMD? Przez sprawność mam na myśli, że albo są naprawdę szybkie, albo nie potrzebują dużo pamięci.Sprzętowa implementacja pierwiastka kwadratowego?

EDYCJA: Powinienem chyba wspomnieć, że pytanie jest na ogół liczbą zmiennoprzecinkową i ponieważ większość sprzętu implementuje standard IEEE 754, w którym liczba jest reprezentowana jako: 1 bit znaku, 8 bitów tendencyjnego wykładnika i 23 bitów mantysa.

Dzięki!

Źródło

2012-01-15 Dimitar Petrov

http://stackoverflow.com/questions/1528727/why-is-sse-scalar-sqrtx-slower-than-rsqrtx-x zawiera szczegółowe informacje. –

Dlaczego nie zaimplementować [this] (http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29)? Robisz tylko zmiany i dodajesz i nie potrzeba dodatkowej pamięci dla rzeczy takich jak tabele przeglądowe. Wygląda jak dobry kandydat na FPGA. –

Dzięki za komentarz @Alex. Spróbuję znaleźć więcej zasobów, ponieważ nadal nie mogę tego zrobić w VHDL. Jeszcze jedno pytanie, czy to nie jest tylko całkowita część sqrt? –

Nie jest to pełne rozwiązanie, ale kilka wskazówek.

Zakładam, że pracujesz w zmiennoprzecinkowy, więc punkt 1 jest pamiętany, że zmiennoprzecinkowe są przechowywane jako mantysa i wykładnik. Wykładnik pierwiastka kwadratowego będzie wynosił około połowy wykładnika oryginalnej liczby dzięki logarytmom.

Następnie mantykę można przybliżyć za pomocą tabeli przeglądowej, a następnie można użyć kilku rund Newton-Raphson, aby uzyskać dokładność wyniku LUT.

Nie zaimplementowałem czegoś takiego przez około 8 lat, ale myślę, że tak właśnie zrobiłem i udało mi się uzyskać wynik w 3 lub 4 cyklach.

Źródło

2012-01-16 02:09:17

Dzięki Paul! Czy możesz wskazać mi konkretny algorytm? Tak, pracuję w trybie zmiennoprzecinkowym i właśnie zredagowałem moje pytanie ... czy mógłbyś nieco rozszerzyć swoje wyjaśnienia, ponieważ nie bardzo rozumiałem wszystko :) –

Niestety to było tak długie, że nie pamiętam dokładnego szczegóły, i to było dla poprzedniego pracodawcy, więc nie mogę go też sprawdzić. Jeśli masz konkretne pytania, zrobię co w mojej mocy, aby na nie odpowiedzieć. –

Dzięki @Paul. Zaznaczam twoje pytanie jako najlepszą odpowiedź, ponieważ to dało mi pewne pomysły i wskazało (mam nadzieję) właściwy kierunek. Dzięki –

To jest świetny do szybkiego korzenia odwrotnego quare.
Spójrz na to here. Zauważ, że chodzi o początkowe przypuszczenia, raczej niesamowity dokument :)

Źródło

2012-01-15 17:07:50 ScarletAmaranth

Wielkie dzięki! Już to widziałem i wygląda to dość imponująco, jednak "magiczna liczba" trochę mnie przeraziła na samym początku. Przyjrzę się ponownie :) –

Nie sądzę, że ta odpowiedź jest naprawdę istotna dla pytania. Algorytm ten oblicza tylko przybliżone przybliżenie odwrotności pierwiastka kwadratowego, a na pewno nie jest zaimplementowany na FPGA –

Dzięki Sven. Czy większość implementacji FPGA używa tylko niektórych wariantów metody Newtona-Raphsona? Jak inwersja, aby pozbyć się dywizji, która sama w sobie jest kosztowną operacją? –

Sprzętowa implementacja pierwiastka kwadratowego?

Odpowiedz

Powiązane problemy