Optymalizacja algorytmów w układach FPGA

   Projektowanie wydajnych i bezbłędnych modeli na potrzeby układów FPGA wymaga dużego doświadczenia w projektowaniu modeli cyfrowych układów scalonych. Niestety nie da się na kilku stronach wyczerpać tego zagadnienia. Można jedynie wskazać najważniejsze sposoby, którymi należy się kierować przy projektowaniu modeli.

   Projektant rozpoczynający pracę z układami FPGA z pewnością przyjmie założenie, że projektując model układu cyfrowego należy stosować się do zasady używania jak najmniejszej ilości rejestrów oraz minimalizowania ilości przesyłów między-rejestrowych. Niestety dla wydajnych modeli projektowanych z naciskiem na maksymalną częstotliwość pracy nie jest to zawsze prawdą. Jedną z metod przyspieszenia pracy układu jest zastosowaniu większej ilości rejestrów podczas wykonywania złożonych operacji. Wydawać się może, że ta droga nie jest właściwa, jednak dodanie pośrednich rejestrów przyśpiesza działanie układu. Wadą takiego rozwiązania są:

Dobrym przykładem jest moduł przedstawiony na listingu:

//Rozwiązanie pracujace z fmax 123MHz
always@(posedge clk)
begin
   tmp0 <= din;
   if (rst == 1'b1) begin
      dout <= "00000000";
         tmp0 <= "00000000";
   end else begin
      dout <= (tmp0 + "01010101")*3;
   end
end

//Rozwiązanie pracujace z fmax 163MHz
always@(posedge clk)
begin
   tmp0 <= din;
   if (rst == 1'b1) begin
      dout <= "00000000";
      tmp0 <= "00000000";
      tmp1 <= "00000000";
   end else begin
      tmp1 <= tmp0 + "01010101";
      dout <= tmp1 * 3;
   end
end


W pierwszym przypadku operacja:

dout <= (tmp0 + "01010101")*3;

została rozłożona na dwie operacje:

tmp1 <= tmp0 + "01010101";
dout <= tmp1 * 3;

   Jak widać wyliczenie nowej wartości dla wyjścia dout zajmuje teraz dwa takty zegarowe, jednak dzięki pośredniemu rejestrowi maksymalna częstotliwość pracy układu zwiększyła się z 123MHz do 163MHz.

Szerokość Licznika

   Poza ogólnymi zaleceniami projektowymi jakie najczęściej opisywane są w literaturze na temat języka Verilog bardzo interesującym sposobem na przyspieszenie pracy układu jest takie zaprojektowanie licznika aby mieścił się w jednym bloku CLB. Dla układów Spartan2 maksymalna szerokość licznika to 24 bity. Powyżej tej wielkości, górna graniczna częstotliwość pracy układu spada skokowo ze względu na rozdzielenie logiki liczącej na przynajmniej dwa oddzielne bloki. Poza opisaną przypadkiem istnieje również oczywista zależność, że zwiększając szerokość licznika zmniejsza się dopuszczalna maksymalna częstotliwość pracy przy której układ działa stabilnie. Na rysunku poniżej przedstawiono wykres zależności maksymalnej częstotliwości pracy licznika w funkcji szerokości magistrali danych licznika.

fpga001.png

Wykres maksymalnej częstotliwości pracy licznika w funkcji szerokości magistrali danych

   Jak widać na wykresie, po przekroczeniu 24 bitów maksymalna częstotliwość pracy licznika spadła o 50MHz. Dlatego też projektując układ warto poszukać alternatywnych rozwiązań, które nie wymagają magistral, które nie mieszczą się w jednym bloku CLB.

Kodowanie maszyny stanów

   Przy projektowaniu modeli takich jak częstościomierze, analizatory stanów logicznych itp można wybrać spośród wielu szkieletów konstrukcji, które można zaimplementować na wiele różnych sposobów. Spośród dostępnych wybrano te, które demonstrują jak ogólne zalecenia projektowe nie zawsze się sprawdzają. Należą do nich:

  • Kodowanie maszyny stanów
  • Użycie różnych wersji przykładowego licznika pomiarowego

   W przypadku kodowania maszyny stanów, problem zaprojektowania szybkiego rozwiązania sprowadza się m.in. do właściwego wybrania implementowanej maszyny stanów. Projektant może zdecydować się na jedną z wielu kombinacji możliwych do zaimplementowania w układach FPGA. W pierwszej kolejności należy zdecydować się automat Mealy’ego lub Moore’a, który to na ogół lepiej sprawdza się w układach FPGA [6]. Dokładniejszy opis automatów stanów, innych konstrukcji symulacyjnych jak i syntezowanych oraz ogólne zalecenia projektowe znaleźć można w pomocy programu WebPack oraz w „Language Templates” dostępnych w programie WebPack w miejscu:

Menu->Edit-> Language_Templates

Maszyny stanów przedstawiono w miejscu:

Menu->Edit-> Language_Templates-> Verilog-> Synthesis_Constructs-> Coding_Examples-> State_Machines

Jako przykładowy projekt wybrano częstościomierz którego automat stanów został przedstawiony na rysunku:


Algorytm pomiarowy częstościomierza

   W przykładowym projekcie zdecydowano się na automat Moore’a, co nie jest najistotniejszym przedmiotem analizy w tym artykule. Dla analizy optymalizacji czasowej dużo bardziej interesującym zagadnieniem jest sposób zakodowania danej maszyny stanów który można zrealizować w następujący sposób:

  • One-Hot lub Binary. W przypadku One-Hot tyle ile jest stanów w maszynie taka jest szerokość rejestru, który decyduje o aktualnie wykonywanym stanie. W trybie binarnym stosowane jest zwykłe kodowanie dwójkowe. Na ogół kodowanie One-Hot jest szybsze
  • Fast lub Save. W przypadku Fast nie zakłada się, ze automat stanów może przyjąć stan, który nie odpowiada któremuś ze zdefiniowanych stanów. W trybie Save określony zostaje stan, który zostaje wywołany, gdy automat straci synchronizacje. Jak wskazuje nazwa szybszym rozwiązaniem jest tryb Fast

W przypadku projektowanego modelu przykładowego częstościomierza wykazały, że najszybciej działającą maszyną stanów Moore’a jest konfiguracja nr 3 w tabeli:

fpga003.png
Maksymalna częstotliwość pracy maszyny stanów

Ze względu na niewielkie rozmiary maszyny stanów różnice są niewielkie. Można jednak stwierdzić, że wprawdzie kodowanie One-Hot jest szybsze od Binary, to jednak układ działa szybciej przy teoretycznie wolniejszym trybie Save.

Użycie w projekcie maszyny stanów znacznie ułatwia proces projektowania. Ważne jednak jest aby poprawnie wybrać maszynę stanów i jej konfigurację. Wybór właściwego rozwiązania z pewnością ułatwi przeprowadzenie kilu testów wybranych kombinacji.

Kodowanie licznika

   W przypadku licznika pomiarowego użytego w projekcie częstościomierza, również miała miejsce sytuacja pogorszenia się otrzymanych parametrów modelu po zastosowaniu ogólnych zaleceń projektowych. Ta uwaga jest o tyle ważna ponieważ udowadnia znaną powszechnie tezę, że doświadczenie stanowi jeden z najistotniejszych czynników decydujących o powodzeniu projektów.
   Do tej pory zwrócono uwagę na rozbieżności w implementacjach maszyny stanów w odniesieniu do zalecanych reguł kodowania a osiągniętymi wynikami. Obecnie zajmiemy się dokładniejszą analizą licznika pomiarowego użytego w przykładowym częstościomierzu.

W układzie FPGA dostępnych jest kilka wersji przerzutnika D. Podstawowe dwa to FD i FDCP pokazane na rysunku:

fpga004.png
Przerzutniki D stosowane w układach FPGA [1]

   Podczas tworzenia przykładowego częstościomierza zdecydowano się na wybór licznika bez wejść zerująco-ustawiających. Elementarnym zaleceniem przy projektowania modeli jest zalecenie o unikaniu konstrukcji asynchronicznych. Używając asynchronicznego zerowania bardzo często pogarszają się wskaźniki:

  • Rozmiar modelu
  • Maksymalna częstotliwość pracy modelu

Kierując się tymi zaleceniami, użyto przerzutnik FD. Wyniki z syntezy poszczególnych przedstawiono w tabeli:

fpga005.png
Maksymalna częstotliwość pracy liczników synchronicznych

   Jak widać, nie ma praktycznie żadnej różnicy pomiędzy zastosowanymi rozwiązaniami. Mimo, że licznik z synchronicznym resetem posiada więcej logiki to jego prędkość działania jest identyczna z prędkością pozostałych konstrukcji. Dlatego tez podczas projektowania np. liczników warto dostosować się do zaleceń o stosowaniu synchronicznego zerownia. Pomimo, że nie jest to zgodne z wynikami przeprowadzonego testu, to konieczność zastosowania dodatkowej logiki może znacząco zmienić uzyskiwane parametry modelu. Podobnie jak to miało miejsce przy wyborze maszyny stanów, to i w tym przypadku należy do każdego problemu podejść indywidualnie.

Podsumowanie i literatura

Pozycje wykorzystane bezpośrednio do opracowania treści artykułu:

  • [1] Xilinx Libraries Guide. Wydanie 8.2i

Autorem artykułu jest mgr inż. Krzysztof Fijak