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

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?

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.

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.