Wykład 4: Układy synchroniczne, przetwarzanie potokowe

Data: 10.11.2020

Treść

• Wykład 4: Układy synchroniczne, przetwarzanie potokowe

  • Przetwarzanie sekwencyjne a przetwarzanie potokowe

    • Prosty układ kombinacyjny

    • Maszyna stanów

    • Potok

  • Sterowanie przetwarzaniem

    • Interfejs valid/ready

    • Obsługa potoków, bąbelki

    • Potoki a interfejsy valid/ready

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: Maszyny stanów.

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)