.. _w04-sync-design: ====================================================== Wykład 4: Układy synchroniczne, przetwarzanie potokowe ====================================================== Data: 10.11.2020 .. toctree:: .. contents:: Przetwarzanie sekwencyjne a przetwarzanie potokowe ================================================== Załóżmy, że chcemy zbudować układ liczący aproksymację funkcji ``sin`` przez przybliżenie wielomianami drugiego stopnia:: # Liczby tutaj są stałoprzecinkowe — dla uproszczenia przykładu, # pomijam takie szczegóły jak przesunięcie "przecinka" w odpowiednie # miejsce czy sprecyzowanie ich szerokości. x = input() # [1] mapujemy x do przedziału [0, tau), mapujemy na [0, 1) x1 = fract(x * (1 / TAU)) # Dzielimy przedział [0, tau) na 256 równych przedziałów, dla każdego # wybieramy wielomian drugiego stopnia najlepiej przybliżający sin(x) # na danym przedziale. A = [...256 liczb...] # współczynniki przy x**2 B = [...256 liczb...] # współczynniki przy x C = [...256 liczb...] # współczynniki stałe # Górne 8 bitów x1 wybiera przedział i współczynniki z powyższej tabeli, # reszta bitów to parametr wielomianu r = x1[-8:] x2 = x1[:-8] # [2] liczymy A * x + B t = A[r] * x2 + B[r] # [3] liczymy A * x**2 + B * x + C y = t * x2 + C[r] output(y) Jak widzimy, nasz układ będzie musiał dla każdego obliczenia wykonać: 1. Trzy dostępy do pamięci (``A``, ``B``, ``C``) 2. Trzy mnożenia (``[1]``, ``[2]``, ``[3]``) 3. Dwa dodawania (``[2]``, ``[3]``) Projektując taki układ mamy dostępnych wiele sposobów realizacji, które różnią się: 1. Powierzchnią powstałego układu 2. Maksymalną częstotliwością układu 3. Opóźnieniem układu w cyklach (czas od otrzymania ``x`` do obliczenia ``y``) 4. Przepustowością układu w obliczeniach na cykl Prosty układ kombinacyjny ------------------------- Możemy po prostu zapisać powyższy pseudokod jako układ kombinacyjny, który będzie wykonywał całe obliczenie w jednym cyklu zegara. Tak skonstruowany układ będzie miał następujące cechy: 1. Powierzchnia: 3 mnożniki, 2 układy dodające, 3 porty odczytu 2. Maksymalna częstotliwość układu: 1 / (3 * opóźnienie mnożnika + 2 * opóźnienie układu dodającego + opóźnienie portu odczytu) 3. Opóźnienie układu: ≤1 cykl 4. Przepustowość układu w obliczeniach na cykl: 1 Realizacja układu w ten sposób jest zazwyczaj złym pomysłem: 1. Poważnie ogranicza to maksymalną częstotliwość zegara w naszym układzie (co wpływa na wydajność całej domeny zegarowej) 2. Wymagane są asynchroniczne porty odczytu Maszyna stanów -------------- Tworzymy maszynę stanów, na przykład z następującymi stanami: 1. ``INPUT``: wczytujemy wejście, liczymy ``x1, r, x2`` 2. ``READ_A``: wczytujemy ``A[r]`` 3. ``MUL_1``: liczymy ``A[r] * x2``, wczytujemy ``B[r]`` 4. ``ADD_1``: liczymy ``t`` 5. ``MUL_2``: liczymy ``t * x2``, wczytujemy ``C[r]`` 6. ``ADD_2``: liczymy ``y``, dajemy wynik Aby zredukować powierzchnię, współdzielimy układ mnożący i dodający oraz port odczytu między stanami. W nMigen mogłoby to wyglądać np. następująco:: mul_in_a = Signal(...) mul_in_b = Signal(...) mul_out = Signal(...) add_in_a = Signal(...) add_in_b = Signal(...) add_out = Signal(...) m.d.sync += [ mul_out.eq(mul_in_a * mul_in_b), add_out.eq(add_in_a * add_in_b), ] with m.FSM(): # ... with m.State('INPUT'): m.d.comb += [ mul_in_a.eq(x), mul_in_b.eq(CONST_1_BY_TAU), ] # ... with m.State('MUL_1'): m.d.comb += [ mul_in_a.eq(rd_port.data), mul_in_b.eq(x2), ] # ... with m.State('MUL_2'): m.d.comb += [ mul_in_a.eq(add_out), mul_in_b.eq(x2), ] # ... 1. Powierzchnia: 1 mnożnik, 1 układ dodający, 1 port odczytu, trochę multiplekserów, trochę przerzutników, logika maszyny stanów 2. Maksymalna częstotliwość układu: 1 / max(opóźnienie mnożnika, opóźnienie układu dodającego, opóźnienie portu odczytu) 3. Opóźnienie układu: 6 cykli 4. Przepustowość układu w obliczeniach na cykl: ⅙ Możemy sobie wyobrazić wiele możliwych wariantów tego rozwiązania: 1. Zmniejszamy liczbę stanów, na przykład przez wykonywanie mnożenia i dodawania w jednym cyklu (i dodanie dodatkowego portu odczytu) 2. Wykonujemy odczyt z pamięci asynchronicznie 3. Zwiększamy liczbę stanów, dodając dodatkowe rejestry przed albo po mnożeniu — synteza może być w stanie "przesunąć" te rejestry gdzieś w środek układu mnożącego, zwiększając jego maksymalną częstotliwość Spowodują one odpowiednią zmianę kompromisu między powierzchnią, częstotliwością zegara, a przepustowością. Potok ----- Realizujemy podobny układ do naszego pierwszego pomysłu (układ kombinacyjny), ale tym razem dodajemy rejestry między jego etapami:: # Etap 1 — wejście m.d.sync += x.eq(... input ...), # Etap 2 — obliczenie [1] m.d.sync += x1.eq(x * CONST_1_BY_TAU) # Etap 3 — wczytanie współczynników z pamięci # To jest tylko wycięcie bitów — brak opóźnienia. m.d.comb += r.eq(x1[:-8]) m.d.comb += x2.eq(x1[:-8]) # Podłączamy odpowiednie adresy do (synchronicznych) portów odczytu. m.d.comb += A_read_port.addr.eq(r) m.d.comb += B_read_port.addr.eq(r) m.d.comb += C_read_port.addr.eq(r) m.d.sync += x2_3.eq(x2) # Etap 4 — obliczenie [2], mnożenie m.d.sync += t_m.eq(x2_3 * A_read_port.data) m.d.sync += x2_4.eq(x2_3) m.d.sync += B_4.eq(B_read_port.data) m.d.sync += C_4.eq(C_read_port.data) # Etap 5 — obliczenie [2], dodawanie m.d.sync += t.eq(t_m + B_4) m.d.sync += x2_5.eq(x2_4) m.d.sync += C_5.eq(C_4) # Etap 6 — obliczenie [3], mnożenie m.d.sync += y_m.eq(x2_5 * t) m.d.sync += C_6.eq(C_5) # Etap 7 — obliczenie [3], dodawanie m.d.sync += y.eq(y_m + C_6) W powyższym kodzie należy zauważyć jawne "przekazywanie" wartości między kolejnymi etapami potoku — nie możemy np. w etapie 6 użyć po prostu sygnału ``x2``, gdyż ten jest już 3 cykle do przodu i zawiera wartość dotyczącą innego obliczenia. Musimy mieć więc odpowiednią liczbę rejestrów między każdą produkcją i konsumpcją wartości, która "wyrówna" etapy naszego potoku. Odpowiada to sygnałom ``x2_*`` w powyższym przykładzie. 1. Powierzchnia: 3 mnożniki, 2 układy dodające, 3 porty odczytu, dużo przerzutników (choć należy zauważyć, że FPGA Xilinxa mają na takie okazje specjalne rejestry przesuwne, dość efektywne w swojej funkcji) 2. Maksymalna częstotliwość układu: 1 / max(opóźnienie mnożnika, opóźnienie układu dodającego, opóźnienie portu odczytu) 3. Opóźnienie układu: 6 cykli 4. Przepustowość układu w obliczeniach na cykl: 1 Podobnie jak przy maszynie stanów, możemy stworzyć wiele wariantów tego potoku (scalając ze sobą bądź dzieląc etapy). Sterowanie przetwarzaniem ========================= Należy zauważyć, że powyższe implementacje algorytmu nie uwzględniają interfejsu i integracji z resztą układu. O ile użycie układu kombinacyjnego jest dosyć proste (dajemy mu wejście, dostajemy wynik), użycie maszyny stanów czy potoku jest nieco bardziej skomplikowane. Jest dość oczywiste, że moduły naszych układów często będą miały różne tempo pracy (nawet przy wspólnym zegarze) — w danym cyklu nasz moduł może nie mieć dostępnych danych wejściowych (gdyż poprzedni moduł jescze ich nie obliczył, jeszcze nie przyszedł pakiet sieciowy z nimi, itp), bądź też nie mieć możliwości wysłania swoich danych wyjściowych (gdyż docelowy moduł jest "zajęty"). Analogicznie, nasz własny moduł może nie mieć możliwości w danym momencie przyjąć danych. W przypadku maszyny stanów, która produkuje jedno wyjście z jednego wejścia (jak ta powyżej), rozwiązanie tego problemu jest dosyć proste: 1. Dajemy naszej maszynie sygnał wejściowy ``start`` bądź podobny (patrz zadanie 1), mówiący kiedy dane wejściowe są dostępne i powinna ona zacząć pracę. 2. Dajemy naszej maszynie sygnał wyjściowy ``busy`` mówiący, kiedy jest ona zajęta (i nie powinniśmy zlecać jej więcej zadań ani używać jej wyjść). W przypadku bardziej skomplikowanych maszyn stanów (wczytujących wiele wejść bądź produkujących wiele wyjść) potrzebujemy bardziej skomplikowanych sygnałów sterujących. Interfejs valid/ready --------------------- Dość popularnym i wygodnym mechanizmem kontroli przepływu w układach cyfrowych jest interfejs valid/ready. Składa się on z następujących sygnałów: - ``ready`` (od konsumenta do producenta) - ``valid`` (od producenta do konsumenta) - ``payload``: dowolny zbiór sygnałów z danymi (od producenta do konsumenta) Semantyka tego interfejsu jest następująca: 1. Producent: - jeśli nie ma gotowego pakietu danych, ustawia ``valid`` na 0 - jeśli ma gotowy pakiet, wystawia go na sygnałach ``payload`` i ustawia ``valid`` na 1 2. Konsument: - jeśli jest w stanie zaakceptować pakiet danych, ustawia ``ready`` na 1 - jeśli nie jest, ustawia ``ready`` na 0 3. W momencie nastąpienia zbocza zegara, jeśli zarówno producent jak i konsument byli gotowi (zachodzi ``valid & ready``), pakiet danych uważa się za przesłany. W przeciwnym wypadku, nic się nie dzieje. Implementacja takiego interfejsu w maszynie stanów jest prosta — dla interfejsów konsumujących dane, ustawiamy (kombinacyjnie) ``ready`` na 1, gdy jesteśmy w stanie w którym oczekujemy danych, po czym uzależniamy przejście do następnego stanu (i całą naszą logikę, w tym pobranie danych ``payload``) od prawdziwości ``valid``. Dla interfejsów produkujących dane, robimy na odwrót. Przykład maszyny stanów z takim interfejsem możemy zobaczyć tutaj: :ref:`ex-fsm`. Obsługa potoków, bąbelki ------------------------ W przypadku potoków, sterowanie robi się bardziej skomplikowane — aby poprawnie obsługiwać potok, musimy wiedzieć ile on ma etapów, i na których etapach potoku znajduje się która paczka naszych danych. Jest jasne, że nie zawsze wszystkie etapy potoku będą zawierały sensowne dane — w szczególności nawet, jeśli mamy nieskończony i nieprzerwany strumień danych wejściowych, przy starcie układu będziemy mieć "puste" etapy. Takie puste etapy (zawierające śmieciowe dane) nazywa się "bąbelkami" potoku. W praktyce jako część potoku zazwyczaj przekazuje się między etapami 1-bitową flagę, czy dany etap zawiera bąbelek. Można też analogicznie przekazywać bardziej skomplikowane metadane (choć na to bywają lepsze sposoby). Potoki a interfejsy valid/ready ------------------------------- Gdybyśmy mieli dostosować nasz pokazany wyżej potok do interfejsów valid/ready na obu końcach, musielibyśmy oczywiście dodać do niego informację o bąbelkach. Okazuje się jednak, że wciąż jest to nietrywialne. Stwierdzenie, czy ostatni etap naszego potoku zawiera sensowne dane i ustawienie flagi ``out_valid`` jest dość trywialne — ustawiamy ją, jeśli na końcu nie mamy bąbelka. Zauważmy jednak, że jeśli ``out_ready`` nie jest ustawione, a ``out_valid`` jest, musimy zablokować cały potok (nie wykonywać żadnych obliczeń, efektywnie zawierając wszystkie nasze synchroniczne obliczenia w wielkim ``m.If``). Jednak oznacza to też, że możliwość zaakceptowania danych na wejściu (czyli ``in_ready``) zależy (kombinacyjnie!) od możliwośći wysłania danych na wyjściu:: # UWAGA: niezalecane m.d.comb += out_data.eq(data_7) m.d.comb += out_valid.eq(valid_7) m.d.comb += in_ready.eq(0) with m.If(~valid_7 | out_ready): # Wejście m.d.comb += in_ready.eq(1) m.d.sync += [ data_1.eq(in_data), valid_1.eq(in_valid), ] # Etapy potoku # .. cała logika synchroniczna .. m.d.sync += [ valid_2.eq(valid_1), valid_3.eq(valid_2), # ... valid_7.eq(valid_6), ] Tworzenie układów, w których wyjściowe sygnały sterujące zależą kombinacyjnie od wejściowych sygnałów sterujących nie jest jednak dobrym pomysłem — przy łączeniu kilku takich układów opóźnienia kombinacyjne dodają się, a w niektórych przypadkach łatwo też o pętlę kombinacyjną. Należy raczej zapewnić, żeby wszystkie sygnały sterujące były synchroniczne bez żadnych ścieżek kombinacyjnych od wejścia (wiele standardów interfejsu jak np. AXI ma to jako twarde wymaganie). Przydatną konstrukcją, która pozwala dostosować nasz potok do takiego wymagania jest dodatnie dodatkowego bufora, który będzie "łapał" dane gdy potok zostanie zablokowany, pozwalając uniezależnić decyzje o pracy układu od gotowości konsumenta w danym cyklu (potok zostanie zablokowany dopiero w następnym cyklu, po zapełnieniu dodatkowego bufora):: buf_valid = Signal() buf_data = Signal(out_data.shape()) # Jeśli nasz dodatkowy bufor został zapełniony, # próbujemy wysłać dane z bufora; w przeciwnym wypadku # z końca potoku. m.d.comb += out_data.eq(Mux(buf_valid, buf_data, data_7)) m.d.comb += out_valid.eq(buf_valid | valid_7) m.d.comb += in_ready.eq(0) # Potok działa (i akceptuje wejście) gdy dodatkowy bufor # jest pusty bądź na końcu jest bąbelek. with m.If(~valid_7 | ~buf_valid): # Wejście m.d.comb += in_ready.eq(1) m.d.sync += [ data_1.eq(in_data), valid_1.eq(in_valid), ] # Etapy potoku # .. cała logika synchroniczna .. m.d.sync += [ valid_2.eq(valid_1), valid_3.eq(valid_2), # ... valid_7.eq(valid_6), ] # Jeśli konsument blokuje, a mamy dane, zapełnij bufor. with m.If(~out_ready & valid_7): m.d.sync += buf_valid.eq(1) m.d.sync += buf_data.eq(data_7) with m.If(out_ready & buf_valid): # Jeśli dane z bufora zostały zaakceptowane, zwolnij bufor. m.d.sync += buf_valid.eq(0)