Dlaczego podział jest o wiele bardziej złożony niż inne operacje arytmetyczne?

39

Ostatnio spotkałem się z przypadkiem, w którym potrzebowałem operacji dzielenia liczb całkowitych na chipie, który jej nie miał (ARM Cortex-A8). Próbując zbadać, dlaczego tak musi być, odkryłem, że ogólny podział zajmuje znacznie więcej cykli niż dodawanie, odejmowanie lub mnożenie na prawie dowolnej architekturze liczb całkowitych (lub punktach stałych). Dlaczego tak jest? Czy to nie jest reprezentowalne z dwuwarstwową logiką AND-OR, jak wszystko inne?

Phonon
źródło

Odpowiedzi:

34

Dzielenie jest iteracyjnym algorytmem, w którym wynik z ilorazu należy przesunąć do reszty za pomocą miary euklidesowej, patrz 2 ; podczas gdy mnożenie może być zredukowane do (ustalonej) serii sztuczek manipulacji bitami.

aterrel
źródło
2
Kiedyś zarówno mnożenie, jak i dzielenie były powolnymi operacjami. W dzisiejszych czasach mnożenie jest nieco szybsze (ale nieco wolniejsze niż dodawanie / odejmowanie), ale podział jest wolniejszy niż inne. Wierzę, że Newton-Raphson jest nadal wykorzystywany wewnętrznie przez większość do odwzajemniania liczby.
JM
12
(Poza tematem: „Operacje odwrotne są zwykle trudne. Spójrz tylko na integrację a różnicowanie.” - zależy od tego, czy to, co robisz, jest symboliczne czy numeryczne. Różnicowanie jest symbolicznie łatwe, ale trudne liczbowo; integracja jest symbolicznie trudna, ale liczbowo łatwe.)
JM
1
Okej, wykopię cię, mówiąc, że kubatura to inna puszka robaków; ale przynajmniej w przypadku jednowymiarowym kwadratura jest łatwiejsza niż różnicowanie.
JM
1
W każdym razie odwrotności zawsze występują w parach. Dlaczego nazwałbyś jeden „operacją”, a drugi „odwrotnością”?
David Ketcheson,
2
Ani iteracja, ani odwrotność nie utrudniają. Twardość podziału wynika z faktu, że musisz zmienić wynik z ilorazu na pozostały przy użyciu miary euklidesowej. Zobacz twierdzenie o algorytmie podziału .
20

Chociaż wszystkie obecne procesory wydają się stosować podejście iteracyjne, jak sugeruje aterrel , wykonano pewne prace nad podejściami nie iteracyjnymi. Zmienna zmiennoprzecinkowa podział zmiennoprzecinkowy i pierwiastek kwadratowy mówi o nie-iteracyjnej implementacji podziału zmiennoprzecinkowego i pierwiastka kwadratowego w układzie FPGA , przy użyciu tabel odnośników i rozszerzenia serii Taylor.

Podejrzewam, że te same techniki mogą umożliwić sprowadzenie tych operacji do jednego cyklu (przepustowość, jeśli nie opóźnienie), ale prawdopodobnie będziesz potrzebować ogromnych tabel odnośników, a tym samym niewiarygodnie dużych obszarów krzemu nieruchomości, aby to zrobić .

Dlaczego nie byłoby to wykonalne?

Przy projektowaniu procesorów jest wiele kompromisów. Funkcjonalność, złożoność (liczba tranzystorów), prędkość i zużycie energii są ze sobą powiązane, a decyzje podejmowane podczas projektowania mogą mieć ogromny wpływ na wydajność.

Nowoczesny procesor prawdopodobnie mogłyby mieć główną jednostkę zmiennoprzecinkową, która poświęca wystarczającej liczby tranzystorów na krzemie wykonać podział zmiennoprzecinkowych w jednym cyklu , ale byłoby to mało prawdopodobne, aby być efektywne wykorzystanie tych tranzystorów.

Mnożenie zmiennoprzecinkowe sprawiło, że dziesięć lat temu przejście z iteracyjnego na nie-iteracyjny. W dzisiejszych czasach mnożenie, a nawet mnożenie w jednym cyklu jest powszechne, nawet w procesorach mobilnych.

Zanim stało się efektywnym wykorzystaniem budżetu tranzystora, mnożenie, podobnie jak dzielenie, było często wykonywane metodą iteracyjną. Wtedy dedykowane procesory DSP mogły poświęcić większość swojego krzemu pojedynczej jednostce szybkiego wielokrotnego gromadzenia (MAC) . Procesor Core2duo ma zmiennoprzecinkowe opóźnienie mnożenia 3 (wartość wychodzi z cyklu potoku 3 po wejściu), ale może mieć 3 zwielokrotnienia w locie, co powoduje przepustowość jednego cyklu, tymczasem jego jednostka SSE2 może wypompuj wielokrotność FP w jednym cyklu.

Zamiast dedykować ogromne obszary krzemu jednostce podziału w jednym cyklu, nowoczesne procesory mają wiele jednostek, z których każda może wykonywać operacje równolegle, ale są zoptymalizowane pod kątem własnych specyficznych sytuacji. W rzeczywistości, gdy weźmie się pod uwagę SIMD instrukcji takich jak SSE lub CPU zintegrowana grafika w Sandy Bridge lub później CPU, może istnieć wiele takich zmiennoprzecinkowe jednostki Podzielić na CPU.

Jeśli ogólny podział zmiennoprzecinkowy byłby ważniejszy dla współczesnych procesorów, sensowne może być poświęcenie wystarczającej powierzchni krzemu, aby uczynić go jednym cyklem, jednak większość twórców chipów najwyraźniej zdecydowało, że mogą lepiej wykorzystać ten krzem, używając tych bramek do innych rzeczy . Dlatego jedna operacja jest wolniejsza, ale ogólnie (w typowych scenariuszach użytkowania) procesor jest szybszy i / lub zużywa mniej energii.

Mark Booth
źródło
O ile mi wiadomo, żadne układy nie mają opóźnień dzielących pojedynczego cyklu dla liczb zmiennoprzecinkowych. Na przykład tabele instrukcji Agner Fog dla procesorów Intel, AMD i VIA podają DIVPS (dzielenie zmiennoprzecinkowe SSE) jako 10-14 cykli. Nie mogę znaleźć żadnego sprzętu z instrukcjami podziału pojedynczego cyklu, ale chciałbym się wykazać, że się mylę. O ile mi wiadomo, nie jest to powszechne.
Bill Barth,
@Bill - Dzięki, masz rację. Jestem pewien, że widziałem wcześniej operacje podziału pojedynczego cyklu w układach DSP, więc zakładałem, że trafiłoby to na pulpit, podobnie jak mnożenie w jednym cyklu, ale nie mogę teraz znaleźć żadnych odniesień. Zaktualizowałem swoją odpowiedź i dodałem kilka istotnych informacji na temat nie iteracyjnych metod, które mogą na to pozwolić w przyszłości. To niesamowite, że podział nie jest teraz bardziej wydajny na cykl niż w przeszłości, kiedy korzystałem z transputerów.
Mark Booth,
1
Myślę, że DSP robią to, ograniczając zakres, w którym są dokładne. Jest to ta sama strategia, jak w przypadku wyszukiwania + interpolacji pierwiastka kwadratowego.
Matt Knepley,
1
Nie jestem jednak pewien, jakie byłyby opóźnienia takiego podziału. Przy częstotliwości 4 GHz wykonywanie podróży w obie strony do tabeli przeglądowej w ciągu N cykli poważnie ogranicza potencjalną wielkość wspomnianej tabeli (na przykład pamięci podręczne L1 stagnowały przy 32 KB każdego). Przejście do 3D pomogłoby to zwiększyć (ale stanowi poważne wyzwanie dla chłodzenia). Czy masz pojęcie, jakie opóźnienie można osiągnąć w przypadku współczesnych procesorów 4 GHz / 5 GHz?
Matthieu M.
1
Aby zapoznać się z liczbami opóźnień i przepustowości divps / divpd vs. mulps / mulpd, zobacz Dzielenie zmiennoprzecinkowe vs mnożenie zmiennoprzecinkowe . Wziąłem dane z tabel instrukcji Agner Fog i sformatowałem je w podsumowanie dotyczące przepływów i opóźnień div i mul dla pojedynczego kontra podwójnego i dla różnych szerokości wektorów SIMD. (Układy Intel zwykle mają dzielnik SIMD, który ma tylko połowę szerokości innych ALU wektorów).
Peter Cordes