TC Moduł 15

Zaawansowane metody syntezy logicznej w projektowaniu układów cyfrowych w strukturach programowalnych.

---

Jak już mówiliśmy ogromną rolę w technice cyfrowej spełniają układy programowalne, często określane nazwą programowalnych modułów logicznych lub krótko hasłem FPLD (Field Programmable Logic Devices). Obecnie produkowane układy FPLD w zależności od ich struktury klasyfikujemy na: proste układy PLD, złożone układy PLD (Complex PLD, w skrócie CPLD) oraz układy FPGA. W prostych układach PLD podstawowym elementem konstrukcyjnym jest matryca AND-OR i zespoły elementów wyjściowych, które w najprostszych układach ograniczają się do przerzutników i trójstanowych buforów wyjściowych, a w bardziej rozbudowanych obejmują dodatkowo multipleksery oraz bramki XOR i z tych powodów nazywane są makrokomórkami (Macrocell). Matryca AND-OR może być matrycą typu PAL (Programmable Array Logic), której cechą charakterystyczną jest programowalna matryca AND i stała matryca OR lub typu PLA (Programmable Logic Array), gdzie obie matryce, AND i OR są programowalne. Znaczy to, że PAL jest zespołem bramek iloczynowych dołączonych do oddzielnych bramek OR, a w PLA każda bramka AND może być dołączona do dowolnej bramki OR.

---

Symboliczny schemat matrycy PLA rozumieć należy następująco: linie poziome reprezentują zmienne wejściowe i wyjściowe. Linie wejściowe są podwójne, górna odpowiada zmiennej w postaci prostej, dolna – zmiennej w postaci zanegowanej. Linie pionowe reprezentują iloczyny (wejścia bramek AND). Zmienna (prosta lub zanegowana) jest czynnikiem iloczynu jeżeli na przecięciu odpowiedniej linii poziomej i pionowej jest kropka. Jeśli iloczyn ten jest składnikiem odpowiedniej sumy (bramki OR) – analogiczna kropka jest umieszczona na przecięciu linii pionowej i poziomej wyjściowej. Fizycznie kropka oznacza, że dany punkt połączeniowy między linią pionową i poziomą jest zaprogramowany. Proces programowania jest wykonywany automatycznie, najczęściej na podstawie schematu punktów programowania wytworzonego wg. procesu syntezy wykonanego w komputerowym systemie projektowania. W rezultacie tradycyjny układ logiczny zbudowany z bramek może być łatwo zrealizowany w strukturze PLA.

---

W podobny sposób interpretujemy schemat matrycy PAL. Jedyną różnicą jest to, że w tym przypadku wyjścia bramek AND są dołączone do wejść bramek OR na stałe – czyli nie są programowane. Z tych powodów liczba linii iloczynu w strukturach typu PAL jest przy realizacjach zespołów funkcji na ogół większa niż w matrycach PLA. Mimo to w produkowanych obecnie strukturach programowalnych częściej stosuje się matryce typu PAL. Decydują o tym inne zalety tych struktur, a właściwie technologiczne wady matryc PLA.

---

Bardziej rozbudowane struktury programowalne to przede wszystkim układy CPLD oraz FPGA.

---

W układach CPLD cechą charakterystyczną struktury jest programowalna matryca połączeń (PIA – Programmable Interconnect Array) otoczona makrokomórkami (Macrocell). Typowa makrokomórka układów CPLD typu MAX (ALTERA) jest zbudowana z matrycy AND-OR (najczęściej typu PAL), z programowalnych przerzutników, bramek OR i XOR, multiplekserów i buforów trójstanowych. Jest to jakby sekcja układu PAL dodatkowo wyposażona w przerzutniki i inne elementy logiczne spełniające rolę pomocniczą. Cechą charakterystyczną tej struktury są bloki logiczne LAB (Logic Array Block), zbudowane z matrycy tzw. ekspanderów i matrycy makrokomórek (na ogół kilkanaście makrokomórek) połączonych z matrycą PIA i blokiem wejściowo-wyjściowym (I/O Control Block).

---

W układach FPGA typową strukturą jest prostokątna macierz elementów logicznych zwanych komórkami, rozmieszczonych w środowisku komutacyjnym kanałów połączeniowych, jak to jest pokazane na rysunku na planszy. Komórka struktur FPGA jest zazwyczaj zbudowana z uniwersalnego układu kombinacyjnego (w sensie możliwości realizacji dowolnej funkcji logicznej) o kilku wejściach i jednym lub dwóch wyjściach, przerzutników i pomocniczych multiplekserów. Uniwersalny układ kombinacyjny nazywa się strukturą tablicową – LUT (Look Up Table), a jednocześnie klasę układów zbudowanych z takich komórek nazywa się układami FPGA typu LUT. Budowa komórek układów FPGA wywarła ogromny wpływ na rozwój specjalnych procedur syntezy logicznej zwanych dekompozycją funkcjonalną.

---

Wpływ zaawansowanych procedur syntezy logicznej na jakość implementacji sprzętowych układów cyfrowych jest najbardziej znaczący w algorytmach wykorzys¬tujących struktury FPGA typu LUT. Struktury takie są powszechnie stosowane w ukła¬dach przetwarzania informacji i sygnałów np. w realizacjach algorytmów kryptogra¬ficznych, w filtrach cyfrowych, układach transformacji falkowej oraz w realiza¬cjach układów wykorzystujących arytmetykę rozproszoną. Zatem stosowanie zaawansowanych procedur syntezy logicznej – dostępnych głównie w oprogramowaniu uniwersyteckim – niejednokrotnie może się przyczynić do sukcesu rynkowego wielu urządzeń cyfrowych, w szczególności tych realizowanych w technologii układów programowalnych przez użytkownika PLD/FPGA.

---

Zalety struktur FPGA to przede wszystkim elastyczność architektury (równoległość przetwarzania i dowolna szerokość ścieżki danych), wielokrotne użycie tych samych zasobów sprzętowych oraz rekonfigurowalność. Wady to niedoskonałość narzędzi projektowania oraz trudny proces uczenia się języka HDL.

---

Jak już mówiliśmy, tworzenie modelu układu cyfrowego w języku HDL bardziej przypomina pisanie programów komputerowych niż tradycyjne projektowanie polegające na syntezie strukturalnej. Tym samym synteza układów cyfrowych za pomocą komputerowych narzędzi projektowania jest złożonym procesem, którego procedury obejmują: a) specyfikację układu w języku HDL, b) syntezę funkcjonalną, c) syntezę i optymalizację logiczną, d) odwzorowanie technologiczne, e) syntezę fizyczną lub programowanie układu. Ważną rolę w całym procesie projektowania odgrywają procedury syntezy logicznej, niejednokrotnie decydujące o jakości transformacji sieci logicznej na wynikowe struktury odwzorowania technologicznego.

---

W celu przekonania się o skuteczności procedur syntezy logicznej w całym procesie projektowania układu logicznego omówimy syntezę układu kombinacyjnego realizującego zespół dwóch funkcji boolowskich 10 argumentów. Zespół ten dla ustalenia uwagi w dalszej części wykładu nazywać będziemy funkcją BUL.

---

W celu syntezy tej funkcji w systemie MAX+PLUSII jej pierwotną tablicę prawdy (zapisaną w tzw. standardzie berkely’owskim) należy zapisać w stosownej konstrukcji języka AHDL. W tym przypadku najwygodniej jest zastosować zapis typu TABLE. Tak zapisaną funkcję BUL system projektowania MAX+PLUSII realizuje na 35 komórkach typowych struktur FPGA firmy Altera. Istotny jest fakt, że komórki tych struktur mają 4 wejścia i 1 wyjście, zatem realizują dowolną funkcję boolowska co najwyżej 4 zmiennych.

---

Podany na planszy fragment raportu kompilatora systemu MAX+PLUSII pozwala sprawdzić, że funkcję BUL realizowaliśmy w układzie typu EPF10K oraz, że liczba zajętych do tego celu komórek LC (Logic Cell) wynosi 35. Jest to co prawda zaledwie 6% wszystkich zasobów sprzętowych zastosowanej struktury, ale przecież sam układ jest zaledwie prostym układem kombinacyjnym.

---

W celu zwiększenia wiarygodności przeprowadzanych eksperymentów funkcję BUL zrealizujemy jeszcze za pośrednictwem nowszego systemu firmy ALTERA jakim jest QUARTUS. Z tych samych powodów zastosujemy specyfikację tej funkcji w języku VHDL (powszechnie uznawanym za „lepszy” niż AHDL). Jak widać rezultat jest zastanawiający: 36 lub 37 komórek. Zatem sytuacja jest niepokojąca o tyle, że lepszy system, lepszy język oraz lepszy układ prowadzi do gorszego wyniku.

---

Niepokój jest większy o tyle, że stosując odpowiednie metody dekompozycji (tzw. zrównoważonej, o której będziemy jeszcze mówili) można funkcję BUL zrealizować w strukturze zbudowanej wyłącznie z 4 komórek.

---

Mając na uwadze fakt, że realizacja układu, który jest opisany prostą funkcją boolowską może budzić wątpliwości co do jego praktycznego znaczenia, zajmiemy się teraz omówieniem eksperymentu z bardziej praktycznym układem cyfrowym, jakim jest transkoder kodu binarnego na kod BCD. Przykład ten był omawiany dokładnie w module 11.

---

Typową realizację transkodera można uzyskać w specyfikacji behawioralnej podanej w dwóch fragmentach na planszach 17 i 18.

---

Jednocześnie na planszy 18 podano zajętość zasobów sprzętowych przy realizacji tego układu za pośrednictwem systemu QUARTUS. Zapamiętajmy: 48 komórek i 29 przerzutników.

---

Konwerter kodu binarnego na BCD dla liczb z zakresu 0 do 99 może być zrealizowany jako układ kombinacyjny, którego tablicę prawdy (opis w stylu Data Flow) łatwo utworzyć na podstawie definicji kodu BCD. Tablicę taką można – stosując odpowiedni konwerter – zapisać w standardzie języka AHDL (format TABLE). Tablica taka poddana procedurze kompilacji w systemie QUARTUS tworzy układ kombinacyjny odwzorowany na 29 komórek układu FLEX10K. Jest to więc rozwiązanie znacznie lepsze od uzyskanego poprzednio metodą syntezy behawioralnej. Zaletą takiego rozwiązania jest również szybkość działania. Uwzględniając ten fakt warto się pokusić o przeprowadzenie dodatkowych zbiegów optymalizacyjnych. Są one możliwe, gdyż układ opisany tablicą prawdy można poddać procedurom dekompozycji funkcjonalnej zaimplementowanym w programie DEMAIN. Rezultat jest wysoce satysfakcjonujący – cała struktura konwertera zajmuje zaledwie 13 komórek. Warto powtórzyć ten eksperyment samodzielnie.

---

Bezpośrednią przyczyną tej sytuacji jest niedoskonałość procedur odwzorowania technologicznego tradycyjnie przystosowanych do struktur typu bramkowego, dla których podstawową metodą optymalizacji jest minimalizacja i faktoryzacja funkcji boolowskich. Transformują one sumo-iloczynowe wyrażenia boolowskie na wielopoziomowe postacie wyrażeń silnie sfaktoryzowanych, a te dopiero odwzorowywane są na komórki typu LUT. Jest to postępowanie sprzeczne z naturą komórki o tyle, że z punktu widzenia syntezy logicznej jest ona przystosowana do realizacji dowolnej funkcji logicznej o argumentach wprowadzonych na jej wejścia. Z tych powodów dla struktur FPGA znacznie skuteczniejszą metodą syntezy okazuje się dekompozycja funkcji boolowskich, której istotą jest synteza funkcji boolowskich w strukturach wielopoziomowych złożonych z komponentów w postaci bloków logicznych typu LUT specyfikowanych pierwotnymi tablicami prawdy. Skuteczność dekompozycji funkcjonalnej została potwierdzona w wielu pracach o charakterze teoretycznym. Stosunkowo mało jest prac, w których procedury dekompozycji funkcjonalnej byłyby konfrontowane z analogicznymi narzędziami syntezy stosowanymi w komercyjnych systemach projektowania. Bezpośrednią przyczyną takiej sytuacji jest brak odpowiednich interfejsów przekształcających strukturę uzyskaną na zewnątrz systemu w strukturę specyfikowaną zgodnie z zasadami systemu komercyjnego. Drugą przyczyną jest złożoność obliczeniowa procedur dekompozycji funkcjonalnej, a w konsekwencji trudność realizacji procedur automatycznych. Trudności te – przynajmniej częściowo – zostały zlikwidowane w metodzie tzw. dekompozycji zrównoważonej.

---

Dekompozycja zrównoważona polega na iteracyjnym stosowaniu różnych strategii dekompozycji – stosowana jest dekompozycja szeregowa rozłączna i nierozłączna oraz równoległa. Warunek wystarczający dekompozycji szeregowej jest sformu¬łowany w modelu algebry podziałów, a jego istotą jest odpowiedni algorytm weryfikacji dekompozycji, w tym algorytm obliczania podziału ${\mathrm{\Pi }}_G$ spełniającego warunek wystarczający dekompozycji szeregowej. Cechą charakterystyczną metody jest wpływ odpowiedniej równowagi między dekompozycją szeregową a równoległą na liczbę komórek i liczbę poziomów układu zdekompowanego. Metoda dekompozycji zrównoważonej została zaimplementowana w sys¬temie DEMAIN opracowanym w Zakładzie Podstaw Telekomunikacji na Wydziale Elektroniki i Technik Informacyjnych Politechniki Warszawskiej.

---

Zastosowanie dekompozycji zrównoważonej w systemie komercyjnym polega na zastąpieniu oryginalnych procedur syntezy logicznej nakładką oprogramowania ze specjalnie skonstruowanym interfejsem. W rezultacie na zewnątrz systemu wykonywane są wyłącznie procedury syntezy logicznej, natomiast procedury odwzorowania technologicznego, symulacji i weryfikacji są realizowane całkowicie za pośrednictwem systemu komercyjnego.

---

Dekompozycja zrównoważona skutecznie wpływa na redukcję zasobów sprzętowych w realizacjach układów cyfrowych. Jakość dekompozycji będziemy – podobnie jak poprzednio – szacowali liczbą zajętych komórek. Ważnymi składnikami wielu układów cyfrowego przetwarzania sygnałów są filtry cyfrowe. Z tych powodów przyjmiemy je jako charakterystyczne i typowe przykłady praktycznych układów cyfrowych, a wyniki odpowiednich eksperymentów będziemy mogli uważać za potwierdzenie skuteczności metod dekompozycji.

---

Filtry cyfrowe wykorzystuje się do zmiany atrybutów sygnału zarówno w dziedzinie czasowej jak i częstotliwościowej poprzez proces zwany splotem liniowym. Proces ten w formalny sposób opisuje poniższa formuła: $y[n]=x[n]*f[n]=\sum _{k}x[k]\cdot f[n-k]=\sum _{k}x[k]\cdot c[k]$ gdzie wartości $c[i]\ne 0$ nazywane są współczynnikami filtru. W szczególności zajmiemy się filtrami o skończonej odpowiedzi impulsowej tzw. filtrami typu FIR (Finite Impulse Response). Zgodnie z nazwą filtry FIR do obliczenia pojedynczej próbki sygnału wyjściowego wymagają skończonej liczby próbek sygnału wejściowego, co redukuje równanie splotu liniowego do sumy skończonej liczby próbek wejściowych. Odpowiedź y[n] filtru FIR rzędu L na skończoną liczbę próbek wejściowych x[n], opisana jest przez skończoną wersję sumy splotu liniowego: Parser nie mógł rozpoznać (nieznana funkcja „\displastyle”): {\displaystyle \displastyle y[n]=\sum_{k=0}^{L} x[k]\cdot c[k]} Dzięki zastosowaniu odpowiedniego oprogramowania można bardzo łatwo obliczyć współczynniki projektowanego filtru. Jednakże najtrudniej jest dokonać efektywnego odwzorowania struktury filtru FIR w architekturę docelową. Zazwyczaj filtry realizuje się jako algorytm MAC (Multiply And Accumulate) z wykorzystaniem wyspecjalizowanych układów DSP.

---

W przypadku realizacji filtrów w strukturach programowalnych dla osiągnięcia dużych szybkości działania i niewielkiego wykorzystania zasobów sprzętowych preferuje się realizacje w formie bezpośredniej lub transponowanej. Zwiększenie efektywności tego typu realizacji filtrów w strukturach programowalnych możliwe jest przez optymalizację realizacji układów mnożących i sumatorów wykorzystanych do implementacji.

---

Nie jest to rozwiązanie najlepsze, gdyż realizacja bezpośrednia jest wygodna dla procesorów sygnałowych, ale nie jest odpowiednia dla struktur FPGA.

---

Całkowicie inną architekturę filtru można otrzymać wykorzystując koncepcję arytmetyki rozproszonej DA (distributed arithmetic). W odróżnieniu od tradycyjnej architektury opartej na sumowaniu wyników iloczynów (sum-of-product), wykorzystanie koncepcji DA umożliwia obliczenie w jednym kroku sumy iloczynów konkretnego bitu próbki wejściowej przez wszystkie współczynniki. W realizacji takiej uniwersalny układ mnożący zostaje zastąpiony uniwersalnym układem kombinacyjnym typu LUT.

---

Oto przykład wyjaśniający działanie układu arytmetyki rozproszonej dla filtru cyfrowego 4 rzędu.

---

Nie ulega wątpliwości, że działanie tak zbudowanego filtru można zapisać w języku AHDL, a następnie poddać kompilacji i w rezultacie można przeprowadzić eksperyment, w którym filtr będzie realizowany dwoma sposobami. W pierwszym cały filtr będzie projektowany wyłącznie za pośrednictwem systemu komercyjnego, a w drugim, wewnętrzny układ arytmetyki rozproszonej będzie syntezowany najpierw za pomocą dekompozycji zrównoważonej, a następnie tak zaprojektowany fragment będzie dołączony do pozostałych zasobów sprzętowych.

---

Jednocześnie, aby wpływ lepszej syntezy fragmentu układu odpowiadającego za funkcje arytmetyki rozproszonej na realizację całości był zgodny z rzeczywistymi realizacjami filtrów, eksperymentom poddamy filtry z wbudowanymi rejestrami potokowymi.

---

Na planszy przedstawiono wyniki zastosowania dekompozycji funkcjonalnej w realizacji układów DA typowych filtrów FIR wykorzystując koncepcję arytmetyki rozproszonej. Dla celów eksperymentów wykorzystano kilka przykładów filtrów różnego rzędu (ozn. F4 do F9) znanych z literatury. Dla porównania wszystkie filtry zostały zrealizowane w strukturze FLEX10K10 z wykorzystaniem systemu QuartusII v4.0 SP1. W pierwszym etapie eksperymentu odpowiednie układy DA były projektowane w całości systemem Quartus. W drugim etapie do optymalizacji logiki DA zastosowano oprogramowanie DEMAIN, zaś cała struktura filtru zrealizowana została z wykorzystaniem systemu Quartus. Wyniki zaprezentowane w tablicy wskazują na znaczący wpływ dekompozycji na jakość realizacji tablic DA. Zastosowanie zaawansowanej metody syntezy logicznej pozwoliło na ponad 40% redukcję wykorzystania zasobów.

---

Oczywiście można mieć wątpliwości czy zaprojektowany lepiej fragment układu wpłynie znacząco na realizację całego układu, zbudowanego w końcu z wielu innych skomplikowanych bloków – rejestry, sumatory itp.

---

Dlatego w kolejnych eksperymentach dokonano porównania jakości realizacji całej struktury filtru. Można zauważyć, że zastosowanie dekompozycji doprowadziło do zmniejszenia liczby komórek logicznych niezbędnych do realizacji filtrów bez zmniejszenia szybkości działania tych filtrów a nawet ją zwiększając. Dla przykładu do realizacji filtru F9, który jest filtrem 19 rzędu, wymaganych jest 2624 komórek logicznych, jeśli zastosowany zostanie jedynie system Quartus. Szybkość działania tak zrealizowanego filtru charakteryzowana przez maksymalną częstotliwości taktowania wynosi $f_{max}=31,25MHz$. Zastosowanie oprogramowania DEMAIN umożliwia realizację tego filtru z wykorzystaniem jedynie 1672 komórek logicznych. Jednocześnie maksymalna częstotliwości taktowania uległa zwiększeniu i wynosi $f_{max}=38,61MHz$

---

Ostateczny rezultat syntezy i odwzorowania technologicznego uzyskiwany za pomocą programu DEMAIN silnie zależy od strategii dekompozycji, przez którą należy rozumieć kolejność wykonywania poszczególnych procedur dekompozycji, tj. dekompo¬zycji szeregowej (rozłącznej i nierozłącznej) oraz równoległej. Oczywiście w wersji automatycznej (stosowanej do tej pory) użytkownik nie ma możliwości sterowania przebiegiem procesu dekompozycji. Program DEMAIN ma również możliwość takiego prowadzenia procesu dekompozycji, w którym decyzja o modelu dekompozycji stosowanym na danym etapie może być podejmowana przez użytkownika.

---

Wpływ różnych strategii dekompozycji na jakość realizacji sprzętowych układów cyfrowych wyjaśnimy na przykładzie funkcji BUL. Funkcję tę będziemy realizowali dwoma sposobami. W pierwszym najpierw wykonywana będzie dekompozycja szeregowa, a następnie równoległa. W drugim odwrotnie, tzn. najpierw cały układ zostanie zdekomponowany równolegle, a następnie uzyskane w ten sposób komponenty będą dekomponowane szeregowo.

---

W pierwszej strategii, program wykonuje najpierw kolejno dwa algorytmy dekompozycji szeregowej. W wyniku uzyskuje się strukturę o 5 wyjściach (z uwzględnieniem 2 wejść pierwotnych) zbudowaną z 3 komórek LC. Wykonując następnie dekompozycję równoległą i znowu szeregową dla poszczególnych kompo¬nentów dekompozycji równoległej, uzyskujemy schemat układu zbudowany z 4 komórek LC. Zatem realizacja całego układu wymaga zastosowania 7 komórek FLEX.

---

W drugiej strategii algorytm dekompozycji równoległej zostaje zastosowany już w pierwszym kroku syntezy, a jego wynikiem są dwa podukłady o odpowiednio 6 i 7 zmiennych wejściowych. Zastosowanie dla każdego z nich algorytmu dekompozycji szeregowej prowadzi do realizacji zbudowanej zaledwie z 4 komórek.

---

Jak pamiętamy ta sama funkcja w systemie QUARTUS była zrealizowana na 36 komórkach.

---

Wpływ dekompozycji interaktywnej na jakość realizacji układów DA filtrów cyfrowych podsumowany jest w tablicy podanej na planszy.

---

Warto podkreślić, że podobne zjawisko poprawiania jakości implementacji sprzętowych przy zastosowaniu dodatkowej procedury dekompozycji zaobserwowano dla wielu innych układów, np. dla układów kryptograficznych.

---