Wykład 6: Projektowanie układów synchronicznych¶
Data: 14.11.2018
Treść
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