.. _w06-sync-design:


===============================================
Wykład 6: Projektowanie układów synchronicznych
===============================================

Data: 14.11.2018

.. toctree::

.. contents::


Przetwarzanie potokowe
======================

Wróćmy do tematu układu dzielącego z pierwszego zadania.  Zrealizowany
kombinacyjnie układ dzialący wygląda mniej-więcej tak::

    input wire [BITS-1:0] A;
    input wire [BITS-1:0] B;
    output wire [BITS-1:0] Q; // A / B
    output wire [BITS-1:0] R; // A % B

    wire [BITS-1:0] tmp[BITS:0];
    assign tmp[BITS] = A;
    assign R = tmp[0];

    genvar i;
    generate for (i = BITS - 1; i >= 0; i = i - 1) begin
        // Wyznacza jedną cyfrę wyniku, odejmuje (bądź nie) odpowiednio przesunięte B, wynik
        // przekazuje dalej.
        div1 #(.IDX(i)) dzielacz(.A_IN(tmp[i + 1]), .A_OUT(tmp[i]), .Q(Q[i]), .B(B));
    end endgenerate

Załóżmy, że chcemy mieć układ synchroniczny, który będzie wykonywał operację
dzielenia.  Używając bezpośrednio powyższego układu (dodając przerzutniki na
wejściach i wyjściach), maksymalna częstotliwość działania będzie wynosić
około ``1/(BITS * t_div1 + t_ff)``, gdzie ``t_div`` to opóźnienia kombinacyjne na
układzie ``div``, a ``t_ff`` to opóźnienie na przerzutniku.  Jest to bardzo zły wynik.

Nie jesteśmy w stanie poprawić czasu wykonywania pojedynczego dzielenia bez
zmiany algorytmu.  Możemy jednak znacznie poprawić częstotliwość działania
naszego układu, wstawiając mu przerzutniki między układy dzielące::

    input wire [BITS-1:0] A;
    input wire [BITS-1:0] B;
    output wire [BITS-1:0] Q; // A / B
    output wire [BITS-1:0] R; // A % B
    input wire clk;

    wire [BITS-1:0] tmp_a[BITS:0];
    wire [BITS-1:0] tmp_q[BITS:0];
    wire [BITS-1:0] tmp_b[BITS:0];
    assign tmp_a[BITS] = A;
    assign tmp_q[BITS] = 0;
    assign tmp_b[BITS] = B;
    assign R = tmp_a[0];
    assign Q = tmp_q[0];

    genvar i;
    generate for (i = BITS - 1; i >= 0; i = i - 1) begin
        wire q1;
        wire [BITS-1:0] out;

        reg [BITS-1:0] out_a;
        reg [BITS-1:0] out_q;
        reg [BITS-1:0] out_b;

        div1 #(.IDX(i)) dzielacz(.A_IN(tmp_a[i+1]), .A_OUT(out), .Q(q1), .B(tmp_b[i+1]));
        always @(posedge clk) begin
            out_a[i] <= out;
            out_q[i] <= tmp_q[i+1] | {q1, {{i}1'b0}};
            out_b[i] <= tmp_b[i+1];
        end
        assign tmp_a[i] = out_a;
        assign tmp_q[i] = out_q;
        assign tmp_b[i] = out_b;
    end endgenerate

Teraz nasz układ potrzebuje aż ``BITS`` cykli zegara na wykonanie jednego dzielenia
zamiast jednego cyklu, ale za to jego maksymalną częstotliwością jest teraz
``1/(t_div1 + t_ff)`` -- czyli czas wykonywania jednego dzielenia nie zmienił się
aş tak bardzo (``t_ff`` jest prawdopdobnie znacznie mniejsze niş opóźnienia kombinacyjne).
Co więcej, znacznie wzrosła przepustowość naszego układu -- wykonujemy teraz ``BITS``
dzieleń równocześnie (każde na innym etapie przetwarzania)!

Taką optymalizację układu nazywa się przetwarzaniem potokowym (pipeline).  Jest to podstawa
efektywnego projektowania układów synchronicznych i pozwala uzyskać wyższe częstotliwości
zegara i przepustowość za cenę zwiększenia opóźnienia.

Projektując prawdziwy potok prawdopodobnie będziemy potrzebować jeszcze dwóch rzeczy:

- jakiegoś sposobu na oznaczenie, które etapy potoku przetwarzają dane w danym momencie,
  a które są nieaktywne (np. z powodu braku dostępnych danych w źródle -- tzw. pipeline bubble)
- jakiegoś sposobu na zatrzymanie potoku, gdy układ docelowy nie jest w stanie teraz
  akceptować danych (prawdopodonie flaga clock enable na cały potok, ale są możliwe
  bardziej skomplikowane pomysły, szczególnie w połączeniu z bąbelkami)

Najczęsszy problem przy użyciu potoków do realizacji procesorów polega na tym, że dane
wejściowe mogą zależeć od danych wyjściowych, które wysłaliśmy wcześniej, ale jeszcze
nie zostały przetworzone (rozważmy dwie instrukcje dzielenia pod rząd, przy czym druga
instrukcja zależy od wyniku pierwszej) -- wtedy konieczne jest pamiętanie, które dane są
już obliczone i wstawianie bąbelków do potoku aż do momentu policzenia wszystkich potrzebnych
wejść.

Zauważmy, że przetwarzanie potokowe skomplikowało nam układ -- musimy teraz pamiętać osobny
stan ``B`` na każdy krok dzielenia (żeby każdy krok działający na danej dzielnej widział
ten sam dzielnik).  Gdybyśmy spodziewali się, że dzielnik zmienia się rzadko, moglibyśmy
wyeliminować osobne stany i wymuszać przerwanie potoku w momencie zmian dzielnika (tak
robi się w procesorach z rzadko zmieniającym się stanem, np. poziomem uprzywilejowania).


Maszyny stanĂłw
==============

Ponownie rozważmy nasz układ dzialący.  Załóżmy, że nie jest nam potrzebna duża przepustowość
(wystarczy nam wykonywanie tylko jednego dzielenia na raz).  Możemy wtedy zredukować nasz
układ do pojedynczego bloku ``div`` i użyć rejestru do pamiętania, który etap dzielenia akurat
wykonujemy::

    input wire [BITS-1:0] A;
    input wire [BITS-1:0] B;
    output wire [BITS-1:0] Q; // A / B
    output wire [BITS-1:0] R; // A % B
    input wire input_vld; // 1 jeśli ktoś przesyła nam nowe liczby do dzielenia
    output wire output_vld; // 1 jeśli skończyliśmy dzielenie
    input wire clk;

    reg [$clog2(BITS)-1:0] bitidx = 0;
    reg active = 0;
    reg [BITS-1:0] tmp_a;
    reg [BITS-1:0] tmp_q;
    assign R = tmp_a;
    assign Q = tmp_q;
    assign output_vld = !active;

    wire q1;
    wire [BITS-1:0] out;

    div1 dzielacz(.A_IN(tmp_a[i]), .A_OUT(out), .Q(q1), .B(B), IDX(bitidx));
    always @(posedge clk) begin
        if (!active) begin
            if (input_vld) begin
                tmp_a <= A;
                tmp_q <= 0;
                active <= 1;
                bitidx <= BITS - 1;
            end
        end else begin
            tmp_a <= out;
            tmp_q[bitidx] <= q1;
            if (bitidx == 0)
                active <= 0;
            bitidx <= bitidx - 1;
        end
    end

Taka konstrukcja efektywnie jest maszyną stanów (``BITS`` różnych stanów na każdy etap dzielenia +
stan nieaktywny).  Maszyny stanów są, obok potoków, drugim podstawowym budulcem układów synchronicznych.


Kodowanie one-hot
-----------------

Rozważmy prostą maszynę stanów rozpoznającą podciąg ``"ABC"`` na strumieniu wejściowym::

    parameter NONE = 2'b00;
    parameter GOT_A = 2'b01;
    parameter GOT_AB = 2'b10;
    parameter GOT_ABC = 2'b11;

    parameter SYMBOL_A = 8'h41;
    parameter SYMBOL_B = 8'h42;
    parameter SYMBOL_C = 8'h43;

    input [7:0] wire data;
    input wire clk;
    output wire found;

    reg state [1:0] = NONE;

    assign found = (state == GOT_ABC);

    always @(podedge clk) begin
        case (state)
        NONE: state <= (data == SYMBOL_A) ? GOT_A : NONE;
        GOT_A: state <= (data == SYMBOL_B) ? GOT_AB : (data == SYMBOL_A) ? GOT_A : NONE;
        GOT_AB: state <= (data == SYMBOL_C) ? GOT_ABC : (data == SYMBOL_A) ? GOT_A : NONE;
        GOT_ABC: state <= (data == SYMBOL_A) ? GOT_A : NONE;
        default: state <= 2'bxx;
        endcase
    end

Może wydawać się, że użycie 2-bitowego rejestru do zakodowania 4 stanów jest efektywne -- w końcu
zużywa minimalną liczbę bitów.  Okazuje się jednak, że dekodowanie tych stanów (porównanie
``state == xxx`` zaszyte w ``case``) kosztuje nas znacznie więcej niż bity w rejestrze.  Znacznie
efektywniejsze kodowanie jest następujące (nazywane one-hot -- w każdym momencie dokładnie jeden
bit jest aktywny)::

    parameter NONE = 4'b0001;
    parameter GOT_A = 4'b0010;
    parameter GOT_AB = 4'b0100;
    parameter GOT_ABC = 4'b1000;

    reg state [3:0] = NONE;

Użycie takiego kodowania eliminuje koszt dekodowania stanu (aby sprawdzić, czy jesteśmy w stanie
``GOT_A``, wystarczy popatrzeć na bit 1) i upraszcza multiplexery kodujące nowy stan.


Pamięć RAM
==========

Przy tworzeniu bardziej skomplikowanych układów, przydaje się możliwość
zapisania większej ilości danych.  Do tego celu śluży pamięć RAM.

W układach FPGA najczęściej mamy do czynienia z dwoma rodzajami RAMu:

- distributed RAM -- wielkość pojedynczego RAMu rzędu kilkudziesięciu bitów,
  polega na użyciu tablicy LUT elementu logicznego jako zapisywalnej pamięci.
- block RAM -- wielkość pojedynczego RAMu rzędu kilkunastu kilobitów,
  dedykowany blok pamięci.

RAM charakteryzuje się następującymi parametrami:

- synchroniczny bądź asynchroniczny (w FPGA prawie zawsze znajdziemy tylko
  RAM synchroniczny, czyli wykonujący wszystkie operacje tylko na zboczach
  zegarowych)
- szerokość -- ile bitów czytamy bądź piszemy w jednym dostępie
- wielkość -- ile bitów ma cały RAM
- głębokość -- ile różnych adresów mamy do dyspozycji (równe wielkości podzielonej przez szerokość)
- liczba i typ portĂłw

Port RAMu to interfejs, którym możemy dostać się do zawartych danych.  Porty
mogą być do odczytu, do zapisu, bądź do jednego i drugiego.  Wewnątrz FPGA
spotkamy pamięć z jednym lub dwoma portami.  Zdarza się, że porty mają
różną szerokość (czyli możemy mieć np. pamięć, do której piszemy jednym portem
po 8 bitów, a czytamy drugim po 1 bicie).  Zdarza się też, że porty mają
niezależne sygnały zegarowe (pozwalając na dostęp do tej samej pamięci
z dwĂłch domen zegarowych).

W bloku pamięci powinniśmy się spodziewać następujących sygnałów (po szczegóły odsyłam do dokumentacji):

- zegar
- write enable (po jednym na port zapisujący) -- jeśli 1, będziemy wykonywać zapis w danym cyklu
- output enable (po jednym na port odczytujący, jeśli port odczytujący jest synchroniczny) -- jeśli 1,
  chcemy wykonywać odczyt w danym cyklu
- adres (po jednym na port)
- dane wejściowe (po jednym na port zapisujący)
- dane wyjściowe (po jednym na port odczytujący)

Pamięci możemy użyć na dwa sposoby:

- ręcznie wybrać bloki, których chcemy użyć (https://www.xilinx.com/support/documentation/sw_manuals/xilinx11/spartan3e_hdl.pdf) i podłączyć odpowiednie sygnały
- napisać tablicę rejestrów w Verilogu i procesy, które z niej czytają i do niej piszą

Używając tego drugiego sposobu, zdajemy się na nasze narzędzie do syntezy.
Aby użycie bloku pamięci się udało, należy zapewnić, że wyspecyfikowany przez
proces rzeczywiście dało się zrealizować sprzętowo:

- nie możemy mieć w kodzie więcej zapisów do pamięci, niż pamięć ma portów do zapisu
  (i analogicznie z odczytem).
- jeśli chcemy użyć portu zarówno do odczytu jak i zapisu, musimy zapewnić, że
  nie używamy zarówno odczytu jak i zapisu w jednej ścieżce w naszym kodzie.

Jeśli parametry pamięci dostępnej w FPGA nam nie odpowiadają, możemy złożyć większą
pamięć z kilku bloków:

- aby otrzymać szerszą pamięć, używamy kilku bloków pamięci z wspólnymi liniami adresowymi
- aby otrzymać głębszą pamięc, używamy kilku bloków pamięci, multipleksera na portach odczytu,
  dekodera adresów i maski sygnału włączającego na porcie zapisu
- aby otrzymać pamięć z większą liczbą portów odczytu, możemy zduplikować cały blok pamięci
  razem z wszystkimi portami zapisu (dość drastyczne, ale bywa przydatne do plików rejestrów
  w procesorach)


Distributed RAM
---------------

W układach Spartan 3E mamy do dyspozycji następujące rodzaje rozproszonego
RAMu:

- RAM16X1S -- 16-bitowy RAM o 1-bitowej szerokości, jeden port (pozwalający
  na odczyt i zapis).  Zajmuje 1 blok logiki.
- RAM16X2S -- 32-bitowy RAM o 2-bitowej szerokości, jeden port (pozwalający
  na odczyt i zapis).  Zajmuje 1 blok logiki.
- RAM32X1S -- 32-bitowy RAM o 1-bitowej szerokości, jeden port (pozwalający
  na odczyt i zapis).  Zajmuje 1 blok logiki.
- RAM64X1S -- 64-bitowy RAM o 1-bitowej szerokości, jeden port (pozwalający
  na odczyt i zapis).  Zajmuje 2 bloki logiki.
- RAM16X1D -- 16-bitowy RAM o 1-bitowej szerokości, dwa porty -- jeden
  do odczytu i zapisu, drugi tylko do odczytu.  Porty mają wspólny zegar.
  Zajmuje 1 blok logiki.

Zapis w pamięci rozproszonej działa synchronicznie (następuje na zboczu zegara),
natomiast odczyt działa natychmiast (czyli możemy przeczytać coś z pamięci i natychmiast
wykonać na tym obliczenia).

Rozproszony RAM jest używany do syntezy małych bloków pamięci (poniżej
kilobita) -- ponieważ elmenty są bardzo małe, używa się ich dużo i składa
się szersze i/lub głębsze pamięci.  Z rozproszonego RAMu możemy na przykład
poskładać plik rejestrów w procesorze.


Block RAM
---------

W układach Spartan 3E mamy do dyspozycji 18-kilobitowe bloki RAMu.  W naszym układzie mamy ich 4.

Bloki RAMu mają dwa kompletnie niezależne porty, każdy dostępny do odczytu i zapisu.  Porty
mogą pracować na niezależnych zagarach i mieć różną szerokość.  Szerokość każdego portu możemy
wybrać z nastepujących możliwości:

- 1 bit
- 2 bity
- 4 bity
- 8+1 bitĂłw
- 16+2 bitĂłw
- 32+4 bity

Zarówno zapis jak i odczyt są synchroniczny (przy odczycie, podajemy adres w jednym cyklu
i otrzymujemy wynik w kolejnym).


Komunikacja między domenami zegarowymi
======================================

Mając w układzie synchronicznym wiele domen zegarowych napotykamy na problem
przekazywania danych między nimi.  Dla pojedynczego sygnału (np. linii przerwania)
wystarczy synchronizator, ale przekazanie większej ilości danych wymaga bardziej
skomplikowanych układów.


Kod Graya
---------

Załóżmy, że chcemy przekazać między dwiema domenami jakąś liczbę, która może
zmienić się co najwyżej o 1 (w górę bądź w dół) w kolejnych cyklach zegara.
Przekazanie jej bezpośrednio przez tablicę synchronizatorów nie zadziała
-- przy zmianie, zmiany różnych bitów mogą dojśc w różnych cyklach do nowej
domeny zegarowej.  Istnieje jednak kodowanie liczb, które rozwiązuje ten
problem -- zapewnia, że każde kolejne liczby są kodowane do wektorów bitowych
różniących się w dokładnie jednej pozycji.  Jest to kod Graya.  Dla przykładu,
kod 4-bitowy:

- 0: 0000
- 1: 0001
- 2: 0011
- 3: 0010
- 4: 0110
- 5: 0111
- 6: 0101
- 7: 0100
- 8: 1100
- 9: 1101
- 10: 1111
- 11: 1110
- 12: 1010
- 13: 1011
- 14: 1001
- 15: 1000

Aby zakodować liczbę ``x`` do kodu graya, wystarczy policzyć ``x ^ (x >> 1)``.
Dekodowanie jest trochę bardziej skomplikowane, ale dośc efektywnie realizowalne
w sprzęcie.


FIFO
----

Do przekazania dużej ilości danych między domenami zegarowymi najczęściej używa
się kolejek FIFO zrealizowanych za pomocą bloków RAMu używanych jako buforów cyklicznych:

- jeden port działa tylko w trybie zapisu w domenie źródłowej
- drugi port działa tylko w trybie odczytu w domenie docelowej
- wskaźniki odczytu i zapisu są przekazywane między domenami zegarowymi w kodzie Graya