Podręcznik

1. Rola i znaczenie syntezy logicznej

Synteza logiczna jest gałęzią wiedzy, która w ostatnich latach rozwijała się niezwykle intensywnie, a jej zastosowania szybko przekroczyły granice tradycyjnej dziedziny układów cyfrowych, dochodząc do obszarów wiedzy zaliczanej do szeroko rozumianych technik informacyjnych, a nawet informatyki. Przyczyną tej sytuacji jest z jednej strony rozwój technologii mikroelektronicznych, a z drugiej coraz większe zapotrzebowanie na analizę i eksplorację danych.

Rozwój technologii mikroelektronicznych zwiększa możliwości techniki cyfrowej, ale ich pełne wykorzystanie wymaga rozwoju nowych metod syntezy logicznej. Powszechnie stosowane tradycyjne metody syntezy logicznej np. minimalizacja funkcji boolowskich są niedostosowane do zasobów układów FPGA, wyposażonych w komórki LUT oraz pamięci ROM. Próby zaradzenia tej sytuacji podejmowane były od dawna, ale szczególnej intensywności nabrały stosunkowo niedawno. Mocnym głosem okazała się książka T. Sasao „Memory based logic synthesis” [1.17], w której po raz pierwszy tak wyraźnie stwierdzono, że jedynymi skutecznymi metodami syntezy są redukcja argumentów i dekompozycja funkcjonalna.

Wpływ zaawansowanych procedur syntezy logicznej na jakość implementacji sprzętowych układów cyfrowych jest najbardziej znaczący w algorytmach wykorzys­tujących nowoczesne struktury programowalne. Struktury takie są powszechnie stosowane w ukła­dach przetwa­rzania informacji i sygnałów np. w realizacjach algorytmów kryptogra­ficznych, w filtrach cyfrowych, układach transformacji falkowej oraz w syntezie funkcji generowania indeksów. 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 FPLD. Należy jednak podkreślić, że w przypadku generatorów adresu stosowanie procedur syntezy logicznej jest niezbędne [1.11], [1.15].

Skuteczność procedur syntezy logicznej można wyka­zać nawet na najpro­stszych przykła­dach. Na przykład prosta 10-argumen­towa funkcja boolo­wska TL27 (specy­fikację tej funkcji podano w podrozdz. 2.6 ) synte­zowana programem ISE 14.7 może być zrealizowana na 21 4-wejściowych komórkach logi­cz­nych układu Spartan-III. Nie jest to sytuacja odosobniona, gdyż synteza Synteza programem Vivado 2015.4.2 w układzie Virtex-7 wymaga zastosowania pięciu 6-wejściowych, trzech 5-wejściowych komorek oraz jednej 4-wejściowej komórki. Niewiele lepiej jest dla systemu Altera Quartus II i układu Cyclone III: siedmiu 4-wejściowych oraz trzech 3-wejściowych komórek logicznych.

Ta sama funkcja poddana zaa­wansowanym procedurom syntezy logicz­nej może być zrealizowana na 2 (dwóch!) 4 wejściowych komórkach logicznych . Do uzyskania tak prostej struktury trzeba zastosować dwie procedury syntezy logicznej: procedurę redukcji argumen­tów oraz procedurę dekompozycji funkcjonalnej.

            Sytuacja nie poprawia się nawet dla układów specjalnie przygotowywanych do realizacji na pamięciach. Charakterystycznym przykładem może być układ arytmetyki rozproszonej [1.13] filtru f5 [1.5]. Układ ten w reprezentacji za pomocą w pełni określonych funkcji boolowskich jest opisany tablicą o 11 zmiennych wejściowych i 11 wyjściach. Jego implementacja w strukturze Virtex-7 wykonana programem Vivado 2015.4.2 wymaga zastosowania 531 komórek (w tym 330 6-wejściowych, 86 5-wejściowych). Ponieważ układ ten, poddany procedurze redukcji argumentów jest funkcją zaledwie 7 argumentów, jego realizacja (wykonywana w tej samej strukturze programem Vivado) zajmuje 9 komórek 6-wejściowych oraz po jednej 5-, 4-, i 2-wejściowej.  Tak wielka różnica w jakości rozwiązania nie może być spowodowana tylko jakością wykonania oprogramowania – u jej podstaw musi leżeć odmienna metodyka syntezy. Potwierdzeniem tego przypuszczenia są najnowsze prace w tej dziedzinie [1.1], [1.15] wykazujące, że potencjalne możliwości redukcji argumentów i dekompozycji funkcjonalnej nie są jeszcze w pełni wykorzystane.

       Zaawansowane procedury syntezy logicznej mogą być również stosowane w zagad­nieniach związanych z klasyfikacją danych, obejmowanych nazwą eksploracji danych [1.7], [1.8]. Eksploracja danych (ang. data mining), nazywana często odkrywaniem wiedzy w bazach danych (ang. knowledge discovery in databases), jest dynamicznie rozwijającą się dziedziną informatyki o szerokich zastosowaniach, m.in. w telekomunikacji, inżynierii biomedycznej, bankowości, itp.

Jednym z ważniejszych zastosowań tych algorytmów są systemy wykrywania anomalii w sieciach telekomunikacyjnych. Są to systemy pracujące wg typowego schematu maszynowego uczenia, gdyż kombinacja reguł oraz algorytmów klasyfikacji służy do wykrywania anomalii na podstawie analizy danych treningowych.

      Innym typowym zastosowaniem jest wspomaganie decyzji podejmowanych przy diagnozie różnych chorób. Polega to na generowaniu reguł decyzyjnych obliczanych na podstawie baz danych zgromadzonych z badań wielu pacjentów. Obliczone w ten sposób reguły decyzyjne (tzw. klasyfikatory) pozwalają diagnozować nowych pacjentów.

       W eksploracji danych typowe zadanie polega na tworzeniu reguł (wyrażeń boolowskich) reprezentujących pierwotne obiekty zapisane w tablicach danych. w przypadku układów logicznych procesy takie są określane mianem minimalizacji funkcji boolowskich. Uzyskiwane w wyniku takiego procesu reguły są wykorzystywane do klasyfikacji danych albo do kolejnych etapów optymalizacji logicznej (w przypadku układów cyfrowych). Oczywiście dane wejściowe algorytmów uogólniania reguł są w obu przypadkach zasadniczo różne. Dla tablic danych mamy do czynienia z wielowartościowymi atrybutami warunkowymi i wielowartościowymi atrybutami decyzyjnymi. Dla tablic prawdy wartości argumentów i wartości funkcji są binarne. Jednocześnie całkowicie inaczej są interpretowane tzw. wartości nieokreślone. w tablicy danych wartość nieokreślona atrybutu warunkowego oznacza, że wartość tego atrybutu nie została ustalona [1.6], a w przypadku tablic funkcji logicznych nieokreśloność argumentu wektora wejściowego oznacza występowanie w specyfikacji wektorów o wszystkich możliwych wartościach danego argumentu [1.3].

       Na abstrakcyjnym poziomie algorytmów eksploracja danych polega m.in. na tzw. uogólnianiu/generacji reguł decyzyjnych, redukcji atrybutów, hierarchicznym podejmowaniu decyzji. Można wykazać, że algorytmy te są odpowiednikami algorytmów syntezy logicznej, a w szczególności tych które powstały w czasie ostatnich 30 lat. Na przykład generacja/uogólnianie reguł decyzyjnych – jest to typowa procedura stosowana w eksploracji danych i odpowiada minimalizacji funkcji boolowskiej, redukcja atrybutów odpowiada redukcji argumentów, natomiast hierarchiczne podejmowanie decyzji jest to dekompozycja funkcjonalna.