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

37

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.

Marko Gulin
źródło
2
Algorytm tak naprawdę nie określa liczby cykli zegara. Twój konkretny procesor może mieć sprzętowy multiplikator / dzielnik działający w jednym cyklu lub 20 cyklach niezależnie od wewnętrznej implementacji.
Eugene Sh.
1
OP, czy możesz podać link, który daje więcej informacji o cyklach 19 vs 1, o których mówisz? Coś konkretnego w twoim DSP.
Vladimir Cravero
1
Dziękuję za odpowiedzi. Oto arkusz danych mojego mikrokontrolera: ww1.microchip.com/downloads/en/DeviceDoc/70005127c.pdf . Patrz Przegląd zestawu instrukcji, zaczynając od strony 292. Mówi, że wszystkie instrukcje DIV zajmują 18 cykli, podczas gdy wszystkie instrukcje MUL zajmują tylko 1 cykl. Ale nie jest to powszechne tylko w tym MCU, widziałem to w wielu innych MCU.
Marko Gulin
2
@ Curd, cóż, są mniej więcej takie same, prawda? Są dla mnie Nie sądzę, że to ilustruje tak dobrze, jak można sobie wyobrazić.
TonyM
1
Drugim czynnikiem jest ekonomia i wzorce użytkowania. Większość zwyczajów wywołuje mnożenie znacznie częściej niż dzielenie. Poświęcenie dużej powierzchni krzemu szybszej funkcji podziału sprzętowego, która będzie używana stosunkowo rzadko, jest słabą ekonomią. Lepiej zrobić mniejszy i tańszy układ lub zastosować dodatkową logikę w bardziej produktywny sposób. BTW, kiedy zaczynałem od minikomputerów, podział nie zawsze był instrukcją. Na niektórych komputerach było to wywołanie biblioteki oprogramowania, na przykład pierwiastek kwadratowy.
nigel222

Odpowiedzi:

34

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)

Skalowany obraz mnożnika

Podzielić

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

Skalowany obraz dzielnika

Marcus Müller
źródło
4
nie, możesz je wdrożyć bez iteracji. Ale po prostu zajmie to trochę czasu, zanim prawidłowy wynik przejdzie przez logikę. Powyższe implementacje nie są iteracyjne.
Marcus Müller,
9
Chcę plakat na ścianie z przegrodą.
Ian Howson
5
Jest teraz w PDF wielowarstwowego GIST. Ma 3378 × 3177 mm, więc przed umieszczeniem tego na suficie w sypialni przedyskutuj z innymi osobami.
Marcus Müller
2
Twoje 100-megapikselowe obrazy są imponujące, ale są zbyt przesadne w stosunku do punktu, który próbujesz zrobić, i powodują ogromne problemy dla każdego, kto próbuje wyświetlić tę stronę na urządzeniu z ograniczoną pamięcią, np. Telefonie lub tablecie. Jeśli chcesz wyświetlać obrazy w linii, znajdź sposób na wyświetlenie podglądu w niższej rozdzielczości.
Dave Tweed
4
Hej, te wykresy graficzne nie są dostępne, joł!
Spencer Williams
8

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ę.

Spehro Pefhany
źródło
Ale sedno jest takie - algorytmy dzielenia nie mogą być zrównoleglone, inaczej niż algorytmy mnożenia, i dlatego są one o wiele wolniejsze?
Marko Gulin,
2
@MarkoGulin „nie może” jest bardzo mocnym stwierdzeniem. Z pewnością nie jest to proste.
Spehro Pefhany
2
Myślę, że można osłabić to od „algorytmów dzielenia nie można zrównoleglać” do „sposobów, w jakie odkryliśmy, że równoległe dzielenie jest bardziej obciążające dla sprzętu realizującego podział niż równoległe mnożenie”. Sphero podaje przykład dzielenia pojedynczego cyklu za pomocą bramek O (2 ^ n) w celu pomnożenia liczb n-bitowych ... ale to po prostu nie jest praktyczne.
Cort Ammon
1
Długi podział może wykorzystywać paralelizm w dowolnym pożądanym stopniu, obliczając przybliżoną odwrotność, która pomnożona przez dzielnik daje wynik w postaci 1000 ... xxxx, Podczas pracy z dzielnikiem w takiej postaci z N zerami wiodącymi jest to łatwe obliczyć N bitów wyniku na każdym kroku.
supercat
8

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.

Peter Green
źródło
Dziękuję za Twoją odpowiedź. Czytałem na Wiki, że algorytm Daddy jest bardzo wydajny, jeśli chodzi o wymaganą liczbę bramek do implementacji tego algorytmu na sprzęcie. Mimo to większość sprzętu używa „binarnego długiego mnożenia”?
Marko Gulin
1
Wydaje mi się, że algotihm dada jest zoptymalizowaną wersją binarnego długiego mnożenia.
Peter Green
Spalam 8 cykli, aby wykonać podział 1 / x. Następnie używam tego do pomnożenia 8 cykli dla stałego kosztu 16 cykli.
b degnan
To ładnie pokazuje, że mnożenie nie jest wcale gorsze niż dodawanie.
Hagen von Eitzen
1
Iteracja wymaga odjęcia, które można wykonać w etapach O (lgN) przy użyciu sprzętu O (NlgN) lub etapów O (sqrt (N)) przy użyciu sprzętu O (N). Istotne jest jednak to, że mnożenie wymaga etapów O (lgN), podczas gdy podział wymaga etapów O (NlgN). Nie O (N * N), ale większe niż pomnożenie przez współczynnik O (N), chyba że ktoś zacznie od przybliżonej wzajemności, aby umożliwić wykonanie większej ilości pracy na krok.
supercat
4

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).

użytkownik4574
źródło
4

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).

TEMLIB
źródło
0

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 .

Nick Gammon
źródło