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