Dlaczego podział sprzętu trwa znacznie dłużej niż mnożenie?

Dlaczego podział sprzętu zajmuje znacznie więcej czasu niż mnożenie na mikrokontrolerze? Na przykład na dsPIC podział zajmuje 19 cykli, a mnożenie zajmuje tylko jeden cykl zegara.

Przeszedłem kilka samouczków, w tym algorytm podziału i algorytm mnożenia na Wikipedii. Oto moje rozumowanie.

Algorytm podziału, podobnie jak metoda powolnego podziału z przywracaniem w Wikipedii, jest algorytmem rekurencyjnym. Oznacza to, że (pośrednie) wyniki z kroku ksą wykorzystywane jako dane wejściowe do kroku k+1, co oznacza, że ​​algorytmów tych nie można zrównoleglać. Dlatego nukończenie podziału wymaga co najmniej cykli, podczas gdy ndywidenda to pewna liczba bitów. W przypadku dywidend 16-bitowych jest to co najmniej 16 cykli.

Algorytm mnożenia nie musi być rekurencyjny, co oznacza, że ​​można go zrównoleglić. Istnieje jednak wiele różnych algorytmów mnożenia i nie mam pojęcia, który z nich może być wykorzystany przez mikrokontrolery. Jak działa mnożenie na sprzęcie / mikrokontrolerze?

Znalazłem algorytm mnożnika Daddy , który powinien zająć tylko jeden cykl zegara, aby zakończyć. Jednak nie rozumiem, że algorytm Daddy postępuje w trzech krokach, podczas gdy wyniki z kroku 1 są wykorzystywane w kroku 2 itd. Zgodnie z tym, ukończenie zajmie co najmniej trzy cykle zegara.

Dzielnik mapuje znacznie mniej elegancko na typowy sprzęt. Jako przykład weźmy układy FPGA Lattice ICE40.

Porównajmy dwa przypadki: ten mnożnik 8 x 8 bitów do 16 bitów:

module multiply (clk, a, b, result);
   input clk;
   input [7:0]a;
   input [7:0]b;
   output [15:0]result;
   always @(posedge clk)
     result = a * b;
endmodule // multiply

i ten dzielnik, który redukuje operandy 8 i 8 bitów do wyniku 8 bitów:

module divide(clk, a, b, result);
   input clk;
   input [7:0] a;
   input [7:0] b;
   output [7:0] result;
   always @(posedge clk)
     result = a / b;
endmodule // divide

(Tak, wiem, zegar nic nie robi )

Przegląd wygenerowanego schematu podczas mapowania mnożnika na układ FPGA ICE40 można znaleźć tutaj, a dzielnik tutaj .

Statystyki syntezy z Yosys są następujące:

zwielokrotniać

• Liczba drutów: 155
• Liczba bitów drutu: 214
• Liczba przewodów publicznych: 4
• Liczba publicznych bitów drutu: 33
• Liczba wspomnień: 0
• Liczba bitów pamięci: 0
• Liczba procesów: 0
• Liczba komórek: 191
  • SB_CARRY 10
  • SB_DFF 16
  • SB_LUT4 165

podzielić

• Liczba drutów: 145
• Liczba bitów drutu: 320
• Liczba przewodów publicznych: 4
• Liczba publicznych bitów drutu: 25
• Liczba wspomnień: 0
• Liczba bitów pamięci: 0
• Liczba procesów: 0
• Liczba komórek: 219
  • SB_CARRY 85
  • SB_DFF 8
  • SB_LUT4 126

Warto zauważyć, że wielkość generowanego verilog dla mnożnika o pełnej szerokości i dzielnika maksymalnie dzielącego nie są tak ekstremalne. Jeśli jednak spojrzysz na poniższe zdjęcia, zauważysz, że mnożnik ma być może głębokość 15, podczas gdy dzielnik wygląda bardziej na około 50; ścieżka krytyczna (tj. najdłuższa ścieżka, która może wystąpić podczas pracy) określa prędkość!

W każdym razie nie będziesz w stanie tego przeczytać, aby uzyskać wrażenie wizualne. Myślę, że różnice w złożoności są możliwe do zauważenia. Są to multiplikatory / dzielniki dla jednego cyklu!

Zwielokrotniać

Pomnóż na ICE40 (ostrzeżenie: ~ 100 Mpixel obraz)

Podzielić

( Podziel na ICE40 ) (ostrzeżenie: ~ 100 Mpixel obraz)

Powolny podział jest z natury iteracyjny, więc zwykle trwa dłużej. Istnieją nieco szybsze algorytmy powolnego podziału niż te proste, wykorzystujące tabele wyszukiwania. Algorytm SRT wytwarza dwa bity na cykl. Błąd w takiej tabeli był przyczyną niesławnego błędu Pentium FDIV (ok. 1994). Są też tak zwane algorytmy szybkiego podziału.

Oczywiście w zasadzie można po prostu użyć ogromnej tabeli odnośników do obliczenia iloczynu lub ilorazu dwóch liczb, a tym samym uzyskania wyników w jednym cyklu, ale tendencja ta szybko staje się niepraktyczna wraz ze wzrostem liczby bitów na liczbę.

Możemy mieć wiele warstw logiki na cykl zegara, ale istnieje limit, dokładnie to, ile warstw logiki możemy mieć, jak złożone mogą być te warstwy, będzie zależeć od naszej szybkości zegara i naszego procesu półprzewodnikowego.

Istnieje jednak wiele różnych algorytmów mnożenia i nie mam pojęcia, który z nich może być wykorzystany przez mikrokontrolery

Afaict większość mnożenia na komputerach używa wariantu binarnego długiego mnożenia. Binarne długie mnożenie obejmuje

• Przesuwanie jednego operandu o różne kwoty
• Maskowanie przesuniętych liczb na podstawie drugiego operandu
• Dodanie wyników maskowania razem.

Przyjrzyjmy się więc implementacji tego w sprzęcie.

• Zmiana biegów to tylko kwestia tego, jak załatwić sprawy, więc przychodzi za darmo.
• Maskowanie wymaga ORAZ bramek. Oznacza to jedną warstwę logiki, więc z punktu widzenia czasu jest tania.
• Dodawanie jest stosunkowo drogie ze względu na potrzebę łańcucha nośnego. Na szczęście istnieje sztuczka, której możemy użyć. W przypadku większości etapów dodawania zamiast dodawania dwóch liczb w celu uzyskania jednej, możemy dodać trzy liczby w celu uzyskania dwóch.

Pozwala więc na sprawdzenie, ile etapów logicznych potrzebujemy dla mnożnika 8x8 z 16-bitowymi wynikami. Dla uproszczenia załóżmy, że nie próbujemy optymalizować tego, że nie wszystkie wyniki pośrednie mają bity we wszystkich pozycjach.

Załóżmy, że pełny sumator jest implementowany w dwóch „etapach bramki”.

• 1 do maskowania w celu uzyskania 8 wyników pośrednich.
• 2, aby dodać grupy trzech liczb w celu zmniejszenia 8 wyników pośrednich do 6
• 2, aby dodać grupy trzech liczb w celu zmniejszenia 6 wyników pośrednich do 4
• 2, aby dodać grupę trzech liczb w celu zmniejszenia 4 wyników pośrednich do 3
• 2, aby dodać grupę trzech liczb w celu zmniejszenia 3 wyników pośrednich do 2
• 32, aby dodać ostatnie dwa wyniki.

Łącznie około 46 etapów logicznych. Większość z nich wydaje się na zsumowanie dwóch ostatnich wyników pośrednich.

Można to jeszcze bardziej ulepszyć, wykorzystując fakt, że nie wszystkie wyniki pośrednie mają wszystkie bity obecne (to jest w zasadzie to, co robi mnożnik dada), poprzez użycie sumatora przeniesienia wyprzedzającego dla ostatniego etapu. Dodając 7 liczb, otrzymujemy 3 zamiast trzech, aby wyprodukować dwa (zmniejszenie liczby etapów w cenie większej liczby bram i szerszych bram) itp.

To wszystko drobne szczegóły, ważne jest to, że liczba etapów potrzebnych do pomnożenia dwóch liczb n bitów i uzyskania wyniku 2n bitowego jest w przybliżeniu proporcjonalna do n.

Z drugiej strony, jeśli spojrzymy na algorytmy podziału, stwierdzimy, że wszystkie one mają iteracyjny proces gdzie.

1. To, co zostanie zrobione podczas jednej iteracji, zależy w dużej mierze od wyników poprzedniej iteracji.
2. liczba etapów logicznych wymaganych do wykonania iteracji jest w przybliżeniu proporcjonalna do n (odejmowanie i porównywanie są bardzo podobne pod względem złożoności do dodawania)
3. liczba iteracji jest również w przybliżeniu proporcjonalna do n.

Zatem liczba etapów logicznych wymaganych do wdrożenia podziału jest w przybliżeniu proporcjonalna do n do kwadratu.

Algorytm podziału (w rzeczywistości dowolny algorytm) można wykonać w jednym cyklu zegara. Jeśli chcesz zapłacić za dodatkowe tranzystory i niższą dozwoloną częstotliwość taktowania.

Załóżmy, że masz zestaw bramek, które implementują jeden cykl zegara istniejącego algorytmu podziału wielocyklowego. Aby algorytm był jednym cyklem, użyj wielu etapów sprzętu (podobnego do stosowanego w jednym etapie algorytmu wielocyklowego), z wyjściem jednego etapu zasilającym następny etap.

Oczywiście powodem tego nie jest, ponieważ używa wielu tranzystorów. Na przykład dla 16-bitowego podziału może użyć prawie 16 X więcej tranzystorów. Również posiadanie większej liczby bramek obniża maksymalną dozwoloną częstotliwość taktowania (ponieważ jest więcej etapów opóźnienia propagacji).

Praktyczne algorytmy podziału oparte są na zestawach numerycznych, które są zbieżne z ilorazem.

• Istnieją metody addytywne, takie jak brak przywracania lub SRT, który działa poprzez dodanie lub usunięcie 2 ^ N do ilorazu i odpowiednio dodanie lub usunięcie dzielnika 2 ^ N * do częściowej reszty, aż zbiegnie się do zera.

• Istnieją metody mnożenia, takie jak Newton-Raphson lub Goldshmidth, które są metodami znajdowania pierwiastków, w których dzielenie jest obliczane jako odwrotność mnożenia.

Metody addytywne dają jeden lub kilka bitów na cykl. Metody multiplikatywne podwajają liczbę bitów dla każdego cyklu, ale wymagają wstępnego przybliżenia, często uzyskiwanego przy stałej tabeli.

Mianowania „powolne” i „szybkie” wprowadzają w błąd, ponieważ rzeczywista prędkość zależy od liczby bitów, ilości sprzętu przeznaczonej na tę funkcję (a szybki mnożnik jest bardzo duży) ...

Podział jest wolniejszy niż mnożenie, ponieważ nie ma bezpośredniej, równoległej metody jego obliczania: albo istnieje iteracja, albo sprzęt jest kopiowany w celu zaimplementowania iteracji jako bloków kaskadowych (lub potokowych).

Dlaczego podział sprzętu zajmuje znacznie więcej czasu niż mnożenie na mikrokontrolerze?

To nie jest pytanie dotyczące elektroniki. W najlepszym razie jest to pytanie komputerowe, lepiej skierowane do przepełnienia stosu.

Zobacz na przykład tutaj: Czy mnożenie jest szybsze niż dzielenie zmiennoprzecinkowe?

W rzeczywistości jest to pytanie z życia: dlaczego podział trwa tak długo, jak rozmnażanie?

Co wolisz obliczać na papierze?

51 * 82

lub

4182 / 51

Dzielenie trwa dłużej niż mnożenie, ponieważ jest trudniejsze .