.. _w02-logic:


===============================================
Wykład 2: Konstrukcja układów cyfrowych, nMigen
===============================================

Data: 27.10.2020

.. toctree::

.. contents::


Moduły
======

Układy cyfrowe składają się z modułów.  Moduły to wydzielone obszary układu
układające się w hierarchię — tworzymy większe moduły przez instancjonowanie
podmodułów i opisanie logiki je łączącej.  Układ cyfrowy ma ustalony
"główny" moduł (top module), który reprezentuje cały układ.

Moduły mogą zawierać:

- wejścia (sygnały wchodzące do modułu)
- wyjścia (sygnały wychodzące z modułu)
- sygnały wewnętrzne
- instancje podmodułów
- instancje prymitywĂłw
- logikę opisaną w języku HDL

Moduły w większości języków mogą być również parametryzowane.

Prymitywy są czymś podobnym do modułów — mają wejścia, wyjścia i parametry
oraz są instancjonowane podobnie do modułów.  Są jednak z punktu widzenia
syntezy "czarną skrzynką" reprezentującą gotowy blok sprzętowy dostępny
w danej technologii (rodzinie FPGA bądź bibliotece komórek ASIC).
Większość prymitywów jest automatycznie wybierana przez proces syntezy, lecz
niektóre trzeba zinstancjonować ręcznie (np. generatory zegarów).

Proces syntezy składa się z dwóch głównych etapów:

- elaboracja: zaczynając od modułu głównego, syntezator rekurencyjnie znajduje
  wszystkie moduły składające się na układ i instancjonuje je z odpowiednimi
  parametrami, tworząc pełną sieć połączeń
- właściwa synteza: cała logika opisana w języku wysokiego poziomu jest
  przetwarzana na prymitywy odpowiednie dla danej technologii

Prymitywy dostępne na Zynq można przejrzeć tutaj: https://www.xilinx.com/support/documentation/sw_manuals/xilinx2019_1/ug953-vivado-7series-libraries.pdf


Moduły w nMigen
---------------

Aby napisać moduł w nMigen, tworzymy klasę dziedziczącą z ``Elaboratable``.
Jeśli chcemy by nasz moduł był parametryzowany, dodajemy odpowiednie
parametry do konstruktora.  W konstruktorze tworzymy również sygnały które
będą interfejsem modułu.  W nMigen nie oznacza się specjalnie sygnałów
wejścia/wyjścia — aby połączyć sygnały między modułami, wystarczy sięgnąć
do odpowiedniego atrybutu podmodułu.  Ta klasa powinna też mieć metodę
``elaborate``, która stworzy właściwy moduł (instancję klasy ``Module``)
i wypełni go logiką (sygnałami wewnętrznymi, podmodułami, przypisaniami, itp).

Przykładowy moduł::

        # A counter that counts down to 0.
        class Counter(Elaboratable):
            # Width is the counter's width in bits.
            def __init__(self, width):
                self.width = width

                # Inputs.
                # Start trigger for the counter.
                self.start = Signal()
                # Start value of the counter.
                self.startval = Signal(width)
                # Counter enable — if 0, the counter will be paused.
                self.en = Signal(reset=True)

                # Outputs.
                # Set if the counter is done counting (the count is 0).
                self.done = Signal()

            def elaborate(self, platform):
                m = Module()

                val = Signal(self.width)

                with m.If(self.start):
                    m.d.sync += val.eq(self.startval)
                with m.Elif(self.en & (val != 0)):
                    m.d.sync += val.eq(val - 1)

                m.d.comb += self.done.eq(val == 0)

                return m

Aby dodać do modułu podmoduł również napisany w nMigenie, dodajemy go do
``m.submodules`` w ``elaborate``, po czym możemy po prostu używać jego
sygnałów w naszej logice::

        my_ctr = m.submodules.my_ctr = Counter(width=4)
        m.d.comb += my_ctr.start.eq(self.my_start_signal)

Jeśli chcemy dodać do modułu prymityw bądź podmoduł napisany w innym
języku, używamy klasy ``Instance``::

        my_inst = m.submodules.my_inst = Instance("nazwa_modułu",
            p_nazwa_parametru=wartość_parametru,
            i_nazwa_wejścia=self.sygnał_wejściowy,
            o_nazwa_wyjścia=self.sygnał_wyjściowy,
        )

W przypadku takich modułów trzeba ręcznie zdefiniować ich wejścia/wyjścia
w konstruktorze, by nMigen znał ich interfejs.


Sygnały i przypisania
=====================

Sygnały stanowią odpowiednik zmiennych w językach programowania — są
nazwanymi wartościami logicznymi (zmiennymi w czasie), których można użyć
w wyrażeniach logicznych do wyliczenia wartości innych sygnałów.

Sygnały w nMigen tworzy się następująco::

    # Jednobitowy sygnał.
    a = Signal()

    # 4-bitowy sygnał (reprezentujący wartość bez znaku w przypadku wyrażeń
    # arytmetycznych), zakres 0..15
    b = Signal(4)

    # 4-bitowy sygnał, reprezentujący wartość ze znakiem, zakres -8..7
    c = Signal(signed(4))

    # Sygnał mający tyle bitów (3), ile potrzeba, by reprezentować liczby
    # z zakresu 0..5
    d = Signal(range(6))

    class Color(enum.Enum):
        RED = 0
        GREEN = 1
        BLUE = 2

    # Sygnał mający tyle bitów (2), ile potrzeba, by reprezentować wartości
    # enumeracji Color.
    e = Signal(Color)

    # Sygnał o takim samym rozmiarze i znaku jak sygnał b.
    f = Signal(b.shape())

    # Sygnał mający 3 bity, o domyślnej wartości 2.
    g = Signal(3, reset=2)


Przypisania
-----------

Wartość sygnałów ustala się przypisaniami::

    # a jest rĂłwne 1 wtedy i tylko wtedy, gdy b jest rĂłwne 3
    m.d.comb += a.eq(b == 3)

    # b w każdym cyklu jest zwiększane o 1
    m.d.sync += b.eq(b + 1)

Przypisania i sygnały należą do "domen" określających, kiedy są one
przeliczane.  Domyślnie istnieją dwie domeny:

- ``comb``: sygnał jest przeliczany ciągle (zawsze gdy zmieni się
  wartość prawej strony lub warunku przypisania).  W przypadku bezwarunkowego
  przypisania oznacza to, że sygnał staje się efektywnie aliasem prawej strony
  przypisania.  Jeśli żadne przypisanie sygnału nie jest aktywne, sygnał
  automatycznie przyjmuje swoją wartość ``reset`` (domyślnie 0).

- ``sync``: sygnał jest przeliczany za każdym razem, gdy wystąpi rosnące zbocze
  zegara.  Wszystkie przypisania synchroniczne w domenie następują atomowo —
  wszystkie prawe strony przypisań są obliczane na podstawie wartości przed
  zboczem zegara.  Na przykład poniższy kod spowoduje zamienienie miejscami
  wartości sygnałów ``x`` i ``y``::

    m.d.sync += x.eq(y)
    m.d.sync += y.eq(x)

  Przed wystąpieniem pierwszego rosnącego zbocza zegara, sygnał ma swoją
  wartość ``reset`` (domyślnie 0).  Jeśli w danym cyklu zegara żadne
  przypisanie dla danego sygnału nie było aktywne, sygnał zachowuje swoją
  wartość z poprzedniego cyklu.

MoĹźliwe jest zdefiniowanie dodatkowych domen przez uĹźytkownika (ktĂłre
zachowują się jak domena ``sync``, ale z osobnym sygnałem zegarowym).
Jest to jednak dość zaawansowany temat.

Warunki
-------

Przypisania mogą być warunkowe (być aktywne tylko, jeśli dane wyrażenie
jest niezerowe itp).  W tym celu należy je umieścić w bloku ``m.If`` lub
podobnym::

    with m.If(a):
        m.d.sync += b.eq(0)
    with m.Elif(b == 3):
        # 3+1 is a bad value, we don't like it.  Skip over it.
        m.d.sync += b.eq(5)
    with m.Else():
        m.d.sync += b.eq(b + 1)

Dla danego sygnału, w kodzie mogą istnieć przypisania tylko z jednej
domeny (nie wolno przypisywać tego samego sygnału z kilku domen).

W przypadku, gdy kilka przypisań do tego samego sygnału jest aktywne
w danym momencie, ostatnie przypisanie wygrywa.  W przypadku, gdy Ĺźadne
przypisanie nie jest aktywne:

- dla sygnałów przypisywanych z domeny ``comb`` (lub nigdzie nie
  przypisywanych), sygnał jest ustawiany na wartość domyślną (``reset``)
- w przeciwnym przypadku (sygnał przypisywany z domeny synchronicznej),
  sygnał nie zmienia wartości.

Sygnały przypisywane z domeny ``comb`` syntezują się do układu obliczającego
odpowiednie prawe strony i warunki oraz drzewa multiplekserów wybierającego
aktywne przypisanie.  Sygnały przypisywane z domen synchronicznych syntezują
się do podobnego układu oraz zespołu przerzutników przechowujących obecny
stan sygnału.

Switch
------

Analogicznie do konstrukcji ``m.If`` istnieje rĂłwnieĹź konstrukcja ``Switch``::

    with m.Switch(operation):
        with m.Case(0):
            m.d.sync += o.eq(x + y)
        with m.Case(1):
            m.d.sync += o.eq(x - y)
        with m.Case(2):
            m.d.sync += o.eq(x | y)
        with m.Case(3):
            m.d.sync += o.eq(x & y)

Co więcej, oprócz w pełni zdefiniowanych stałych można używać wzorców bitowych
z "wildcardami"::

    with m.Switch(opcode):
        # Pasuje do 0, 1, 2, 3.
        with m.Case('0--'):
            m.d.sync += o.eq(x + opcode[0:2])
        with m.Case('100'):
            m.d.sync += o.eq(x + y)
        with m.Case('101'):
            m.d.sync += o.eq(x - y)
        with m.Case('110'):
            m.d.sync += o.eq(x | y)
        with m.Case('111'):
            m.d.sync += o.eq(x & y)


WyraĹźenia i operatory
=====================

nMigen ma dość bogaty zbiór wyrażeń, które można skonstruować i używać
w logice.  Podobnie jak sygnały, wyrażenia mają rozmiar w bitach
(który można sprawdzić przez ``len(wyrażenie)``) i mogą być ze znakiem
lub bez (``wyraĹźenie.shape().signed``).

Najprostszymi wyrażeniami są same sygnały oraz stałe.  Stałe w nMigen
można tworzyć jawnie (używając konstruktora ``Const``) lub niejawnie
(po prostu używając liczby bądź wartości enumeracji w wyrażeniu).
Użycie ``Const`` pozwala nam wybrać szerokość stałej (w przeciwnym
wypadku jest wybierana automatycznie)::

    # Stała o wartości 5, szerokości 3 bitów, bez znaku.
    Const(5)

    # Stała o wartości 5, szerokości 8 bitów, bez znaku.
    Const(5, 8)

    # Stała o wartości 5, szerokości 8 bitów, ze znakiem.
    Const(5, signed(8))

    # Stała o wartości -3, szerokości 3 bitów, ze znakiem
    Const(-3)

    # Stała o wartości 1, szerokości 2 bitów, bez znaku.
    Const(5, 2)

    # Stała o wartości 0, szerokości 2 bitów, bez znaku.
    Const(Color.RED)

Wyrażenia można też tworzyć z innych wyrażeń używając operatorów.  Operatory
arytmetyczne w nMigen automatycznie dobierają szerokość wyniku tak, by mógł
on reprezentować poprawny matematyczny wynik odpowiedniego obliczenia.

Dostępne operatory to:

- ``a.as_signed()``, ``a.as_unsigned()``: rzutowanie surowych bitów wartości na
  wartość ze znakiem / bez znaku (zmienia właściwości wartości, nie zmienia
  bitĂłw).
- ``a[2:4]``: wycina sygnał 2-bitowy bez znaku z bitów 2..3 wartości ``a``.
- ``Cat(a, b)``: skleja ze sobą bity dwóch wartości w większą wartość (``a``
  jest w niĹźszych pozycjach, ``b`` w wyĹźszych)
- ``Repl(a, 3)``: rĂłwnowaĹźne ``Cat(a, a, a)``
- ``~a``, ``a & b``, ``a | b``, ``a ^ b``: operacje bitowe NOT, AND, OR, XOR,
  operujące na parach bitów z ``a`` i ``b`` niezależnie i dające wynik takiego
  rozmiaru jak wejścia.  Jeśli wartości ``a`` i ``b`` są różnych rozmiarów,
  krótsza jest rozszerzana do rozmiaru dłuższej.
- ``a.all()``, ``a.any()``, ``a.xor()``: operacje bitowe AND, OR, XOR
  operujące na wszystkich bitach wartości ``a``, dające 1-bitowy wynik.
- ``a.bool()``: rzutowanie ``a`` na 1-bitową wartość logiczną.  1 jeśli
  ``a`` jest róşne od 0.  W zasadzie równowaşne ``a.any()``.
- ``Mux(a, b, c)``: operator wyboru.  Jeśli ``a`` jest prawdą, zwraca ``b``.
  W przeciwnym wypadku zwraca ``c``.  Rownoważne operatorowi ``?:`` z języka
  C.  Jeśli ``b`` i ``c`` mają różną długość, krótsza jest rozszerzana do dłuższej.
- ``a + b``, ``a - b``, ``-a``, ``a * b``: operatory arytmetyczne.  Wynik ma długość
  taką, by zawsze zmieścić wynik operacji.
- ``a == b``, ``a != b``, ``a < b``, ``a > b``, ``a <= b``, ``a >= b``: operatory
  porównania.  Zwracają 1-bitowy wynik.
- ``a.bit_select(b, 3)``: jak ``a[b : b+3]``, ale działa również, gdy ``b`` nie jest
  stałą.
- ``a.word_select(b, 3)``: jak ``a[b*3 : (b+1)*3]``, ale działa również gdy ``b``
  nie jest stałą.
- ``a << b``, ``a >> b``: operatory przesunięcia bitowego.  Uwaga: podobnie
  jak przy operatorach arytmetycznych, wyrażenie ma taką długość, by wynik
  się zawsze zmieścił.  W przypadku przesunięcia w lewo jest to wykładnicze
  od długości ``b``.  Należy zapewnić, że ``b`` tylko tyle bitów, ile jest konieczne.



.. _ex-fsm:

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

Ponieważ w układach cyfrowych nie można tak po prostu wyrazić pętli lub innych
skomplikowanych pojęć programowania imperatywnego, bardzo często spotyka się
maszyny stanów, które w zasadzie służą do ręcznej realizacji tych konceptów.
nMigen ma natywne wsparcie dla maszyn stanĂłw.

Rozważmy następujący kod w języku imperatywnym::

    while (1) {
        int num = get_input();
        int sum = 0;
        while (num--)
            sum += get_input();
        output(sum);

W logice cyfrowej podobny schemat zrealizowalibyśmy za pomocą maszyny stanów
w następujący sposób::

    with m.FSM() as fsm:
        with m.State('START'):
            m.d.comb += input_rdy.eq(1)
            with m.If(input_vld):
                m.d.sync += sum.eq(0)
                m.d.sync += num.eq(input)
                with m.If(input != 0):
                    m.next = 'ACCUMULATE'
                with m.Else():
                    m.next = 'DONE'
        with m.State('ACCUMULATE'):
            m.d.comb += input_rdy.eq(1)
            with m.If(input_vld):
                m.d.sync += sum.eq(sum + input)
                m.d.sync += num.eq(num - 1)
                with m.If(num == 1):
                    m.next = 'DONE'
        with m.State('DONE'):
            m.d.comb += output_vld.eq(1)
            m.d.comb += output.eq(sum)
            with m.If(m.output_rdy):
                m.next = 'START'