TC Moduł 14

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
TC M14 Slajd1.png
Zaawansowane procedury syntezy logicznej

Zapotrzebowanie na komputerowe narzędzia projektowania oraz coraz trudniejsze wyzwania stawiane przez technologie układów scalonych stały się najważniejszym czynnikiem rozwoju nowoczesnej syntezy logicznej. Dla wielu nowoczesnych technologii znaczący wpływ na ostateczną realizację ma etap syntezy logicznej. Okazało się to bardzo istotne w technologii układów programowalnych przez użytkownika, jakkolwiek szereg zadań techniki Full Custom i Semi Custom również charakteryzuje się dużą podatnością na „transformacje logiczne”. O randze problemu świadczy fakt finansowania prac nad algorytmami optymalizacji układów logicznych przez takie koncerny i instytucje, jak np. IBM, a także organizowanie corocznych, międzynarodowych konferencji poświęconych syntezie logicznej.



TC M14 Slajd2.png
o najważniejszych zagadnień syntezy logicznej jakie rozwijały się szczególnie intensywnie w ostatnich latach należą między innymi problemy, takie jak: synteza dwupoziomowa (two-level synthesis), synteza wielopoziomowa (multi-level synthesis), minimalizacja symboliczna, dekompozycja matryc PLA oraz dekompozycja funkcjonalna.

Szczególnie intensywne prace badawcze prowadzone były (i ciągle są) nad metodami i algorytmami syntezy logicznej dla układów FPGA o architekturze LUT (Look-Up Table). Intensywność tych prac jest wynikiem z jednej strony dużej popularności struktur FPGA, a z drugiej, ich odmiennej budowy, którą w pierwszym przybliżeniu można scharakteryzować jako strukturę komórkową, w odróżnieniu od struktury bramkowej charakterystycznej dla układów Gate Array i Standard Cell. Dla układów FPGA początkowo próbowano zaadaptować klasyczne algorytmy dekompozycji funkcjonalnej Curtisa, o których mówiliśmy w module 6.



TC M14 Slajd3.png
Jednak droga od prostego i ograniczonego modelu Curtisa do metod, które mogłyby być odpowiednie do wysokich wymagań współczesnych technologii układów FPGA, była bardzo długa i jak można sądzić z najnowszych publikacji badania nad dekompozycją funkcjonalną są ciągle w kręgu zainteresowań zarówno ośrodków uniwersyteckich, jak i firm opracowujących komputerowe systemy projektowania układów cyfrowych. Można stąd wnosić, że zagadnienia dekompozycji funkcjonalnej – do tej pory rzadko prezentowane w wydawnictwach książkowych – osiągnęły poziom i potrzebę ich rozpowszechnienia. Jest to istotne tym bardziej, że istniejące uniwersyteckie narzędzia komputerowe syntezy logicznej bezpośrednio wykorzystujące algorytmy dekompozycji dają bardzo dobre rezultaty w porównaniu do systemów komercyjnych.

TC M14 Slajd4.png
W module niniejszym omówiona będzie metoda. dekompozycji opracowana w Instytucie Telekomunikacji Politechniki Warszawskiej i zaimplementowana w systemie DEMAIN. Metoda ta polega na iteracyjnym stosowaniu różnych strategii dekompozycji – stosowana jest dekompozycja szeregowa rozłączna i nierozłączna oraz równole¬gła. Dekompozycja szeregowa to klasyczna dekompozycja Curtisa. Dekompozycja równoległa polega na podziale zbioru funkcji wyjściowych na dwa rozłączne podzbiory i realizacji każdego z nich oddzielnie. W przypadku, gdy dekompozycja równoległa jest obliczana na poziomie pierwotnych zależności funkcjonalnych, jej wpływ na jakość struktury wielopoziomowej może być bardzo istotny. Zastosowanie dekompozycji równoległej powoduje rozkład danej funkcji na dwie funkcje o mniejszej złożoności, co ułatwia znalezienie dobrych dekompozycji szeregowych dla każdej z nich.

TC M14 Slajd5.png
Obecnie zajmiemy się analitycznym opisem dekompozycji funkcji boolowskich. Do tego celu posłużymy się wprowadzonym w module 5 rachunkiem podziałów. W szczególności wyprowadzimy warunki dekompozycji dla funkcji boolowskich opisanych podziałami określonymi na zbiorze ponumerowanych wektorów odwzorowania .

Na początek zajmiemy się poszukiwaniem dekompozycji , gdzie: są podzbiorami zbioru argumentów funkcji boolowskiej, a ponadto , , . Dla podanych założeń obowiązuje twierdzenie:

,

wtedy i tylko wtedy, gdy istnieje podział taki, że:



TC M14 Slajd6.png
Przypomnijmy istotne dla dekompozycji elementy rachunku podziałów.

Podziałem na zbiorze jest system zbiorów , którego bloki są rozłączne, czyli

, jeśli tylko

Na przykład dla , jest podziałem na , co zapisujemy:

Dla podziałów – podobnie jak dla zbiorów –definiuje się relację porządku oraz typowe działania iloczynu, ilorazu itp.,


TC M14 Slajd7.png
Powiemy, że podział jest nie większy od (co oznaczamy: ), jeśli każdy blok z jest zawarty w pewnym bloku z .

Iloczynem podziałów nazywamy największy (względem relacji ) podział, który jest nie większy od oraz . Na przykład



TC M14 Slajd8.png
Niech i są podziałami na oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle P_a\ge P_b\} .

Podział jest podziałem ilorazowym i , jeżeli jego elementy są blokami , a bloki są blokami .


TC M14 Slajd9.png
Skuteczność wprowadzonego aparatu pokażemy na przykładzie funkcji TL27 z modułu 5 (plansza 19). Dla tej funkcji tej można wykazać (najlepiej policzyć programem PANDOR), że jednym z minimalnych zbiorów argumentów jest Parser nie mógł rozpoznać (Błąd konwersji. Serwer („https://wazniak.mimuw.edu.pl/api/rest_”) zgłosił: „Cannot get mml. TeX parse error: Double subscripts: use braces to clarify”): {\displaystyle X=\{x_{3},x_{5},x_{6},x_{7},x_{8},x_{9},x_{1}_{0}\}\,} .

TC M14 Slajd10.png
Przystępując do obliczenia dekompozycji najpierw należy funkcję opisać podziałami.

TC M14 Slajd11.png
Korzystając z informacji o minimalnym zbiorze argumentów załóżmy poszukiwanie dekompozycji dla zbiorów oraz Parser nie mógł rozpoznać (Błąd konwersji. Serwer („https://wazniak.mimuw.edu.pl/api/rest_”) zgłosił: „Cannot get mml. TeX parse error: Double subscripts: use braces to clarify”): {\displaystyle V=\{x_{3},x_{5},x_{6},x_{1}_{0}\}\,} . Inaczej mówiąc zakładamy jednocześnie schemat blokowy dekompozycji taki jak na rysunku na planszy. Zauważmy, że w założonym schemacie blokowym nie wiemy jeszcze ile jest wyjść z bloku .

TC M14 Slajd12.png
Kolejne obliczenia uzyskane bezpośrednio z podziałów są następujące:


Parser nie mógł rozpoznać (nieznana funkcja „\overlin”): {\displaystyle \begin{matrix} P_U=P_7\cdot P_8\cdot P_9 & = & (\overline{1,4,10};\overline{2,11};\overline{3,14,18,21};\overline{5,9,12,22}; \\ \ & & \overline{6,7,15,20,24};\overlin{8,13,16,19};\overline{17,25};\overline{23}) \end{matrix}}



TC M14 Slajd13.png
Obecnie stajemy przed najważniejszym zadaniem wynikającym z twierdzenia o dekompozycji, a mianowicie przed obliczeniem podziału .

TC M14 Slajd14.png
Dla wygody dalszych obliczeń podział zapiszemy w postaci podziału ilorazowego:


TC M14 Slajd15.png
Interpretując twierdzenie o dekompozycji łatwo zauważyć, że podział tworzymy z bloków podziału zgodnie z podziałem ilorazowym .

TC M14 Slajd16.png
Aby to zrealizować wystarczy zauważyć, że:

a) podział musi rozdzielać elementy 1 i 4 od elementu 10; 2 od 11; 3 od 14 i 18 i 21 itp.; wynika to z podziału ilorazowego;

b) podział musi być zbudowany z bloków podziału .

Zatem, jeśli zaliczymy bloki oraz do pierwszego bloku , to blok musimy zaliczyć do drugiego bloku (ponieważ zawiera element 10) itp. Reszta obliczeń jest pokazana na planszy. Na tej podstawie stwierdzamy, że:



Łatwo sprawdzić, że . Zatem dekompozycja istnieje.


TC M14 Slajd17.png
Obliczony podział jest dwublokowy, zatem możemy już ustalić liczbę wyjść z bloku . Czyli odpowiedni schemat blokowy dekompozycji można uszczegółowić względem dotychczas założonego przez poprowadzenie jednej linii połączeniowej między blokiem i blokiem .

TC M14 Slajd18.png
Dysponując uzyskanym w ten sposób schematem blokowym dekompozycji nie trudno zauważyć, że do całkowitego określenia układu logicznego realizującego naszą funkcję przede wszystkim należy obliczyć tablice prawdy funkcji i .

TC M14 Slajd19.png
Tablicę funkcji obliczamy korzystając z podziałów i .

Obliczenia interpretujemy następująco. Dla przykładu: blok jest zawarty w drugim bloku podziałów , natomiast w pierwszym bloku podziału Parser nie mógł rozpoznać (Błąd konwersji. Serwer („https://wazniak.mimuw.edu.pl/api/rest_”) zgłosił: „Cannot get mml. TeX parse error: Double subscripts: use braces to clarify”): {\displaystyle P_{1}_{0}\,} oraz w pierwszym bloku podziału . Dlatego odpowiadający mu wektor jest , a wartość funkcji .


TC M14 Slajd20.png
Podobnie postępujemy dla funkcji , ale tu korzystamy z bloków iloczynu podziałów oraz ich przynależności do podziałów oraz .



TC M14 Slajd21.png
Rysując raz jeszcze schemat blokowy uzyskanej dekompozycji łatwo zauważamy, że funkcję TL27 można zrealizować na 2 komórkach struktury FPGA typu LUT.

TC M14 Slajd22.png
Zauważmy, że twierdzenie o dekompozycji jest na tyle ogólne, że łączna (jednoczesna) dekompozy¬cja wszystkich funkcji wchodzących w skład układu realizowanego z zastosowaniem modułu wielowyjściowego pozwala na wyodrębnienie wielowyjściowych podukładów , których tablice prawdy stanowią bądź bezpośrednią informację, określającą na przykład zawartość pamięci ROM lub komórki typu LUT, bądź też są punktem wyjścia do dalszych etapów syntezy (np. minimalizacja układów wielowyjściowych) w przypadku matryc PLA.

TC M14 Slajd23.png
W celu pełnego przekonania o skuteczności twierdzenia o dekompozycji zajmiemy się dekompozycją zespołu 3 funkcji boolowskich o 5 argumentach, dla których tablica prawdy jest podana na planszy.

Oznaczmy jak poprzednio wektory z liczbami naturalnymi , a przez podział wyjściowy funkcji skonstruowany w następujący sposób:



Inaczej mówiąc, wektory i należą do jednego bloku podziału tylko wtedy, gdy odwzorowanie przyporządkowuje tym wektorom taki sam wektor z . Na przykład, dla odwzorowania określonego jak w tablicy na planszy podział (zapisany w postaci podziału na zbiorze będzie miał postać:



TC M14 Slajd24.png
Jak widać zastosowanie rachunku podziałów okazało się wyjątkowo wygodne, gdyż odpowiednie twierdzenie o dekompozycji układów wielowyjściowych traktuje zespół funkcji jako pojedynczy obiekt, podlegający zasadom dekompozycji identycznie jak pojedyncza funkcja

boolowska. Dodatkowo uzyskuje się tu prostą metodę selekcji zbioru argumentów należących do zbioru , o której niestety ze względu na ograniczony zakres wykładu nie będziemy mówili.

Zatem przyjmujemy arbitralnie oraz , czyli podział , , a więc:



gdzie bloki są oznaczone kolejno .


TC M14 Slajd25.png
Z podziału ilorazowego wnioskujemy, że odpowiedni PG powinien mieć co najmniej 3 bloki. Wynika to z faktu, że elementy (2), (9,14) i (3,15) muszą należeć do trzech różnych bloków (to samo dotyczy (4), (5) i (10)). Ponadto pamiętamy, że . Zatem wprowadzenie bloków z do tworzonego powinno przebiegać według schematu pokazanego w kolorowej tablicy na planszy. Stąd:



TC M14 Slajd26.png
Przyjmując, że kodowanie bloków jest: pierwszy blok – 01, drugi blok – 10, trzeci blok – 00 i uwzględniając, iż kolejnym blokom z podziału odpowiadają wektory (zmienne ) odpowiednio: , , , , , , oraz , wyznaczamy tablicę prawdy funkcji .

TC M14 Slajd27.png
Fragment tej tablicy podany jest na planszy.

TC M14 Slajd28.png
Podobnie, po obliczeniu iloczynu:

wyznaczamy tablicę prawdy funkcji .


TC M14 Slajd29.png
Warto podkreślić, że dla realizacji w strukturach FPGA wystarczy schemat dekompozycji i tablice prawdy składowych dekompozycji (G i H). Wynika to z faktu, że komórki struktur FPGA (o czym będziemy mówili na następnym wykładzie) realizują dowolną funkcję boolowska ograniczonej liczby zmiennych (typowo 4). Nie należy przy tym zapominać, że jeśli zależy nam na realizacji w strukturach bramkowych, to jest to oczywiście możliwe po przeprowadzeniu procesu minimalizacji funkcji dla każdej składowej dekompozycji. zatem metoda dekompozycji jest ogólniejsza od metody minimalizacji i powinna być przeprowadzana przed procesem minimalizacji. Niestety w systemach komercyjnych tak nie jest. I można się domyślać, że w takim razie wyniki odwzorowania technologicznego dla wielu funkcji mogą być w systemach komercyjnych o wiele gorsze niż w systemach uniwersyteckich stosujących metody dekompozycji.

TC M14 Slajd30.png
W pełni potwierdza to przypuszczenie wynik realizacji funkcji TL27, który metodą dekompozycji zrealizowaliśmy na 2 komórkach (patrz plansza 21 niniejszego modułu). Ten sam wynik uzyskamy za pośrednictwem specjalnego modułu oprogramowania DEMAIN wykonującego omówione w ramach niniejszego wykładu algorytmy dekompozycji. Niestety realizacja tej samej funkcji wykonana w systemie QUARTUS amerykańskiej firmy ALTERA zajmuje znacznie większe zasoby sprzętowe, a mianowicie 25 komórek. O sposobie przeciwdziałania wadom systemów syntezy układów cyfrowych w komercyjnych narzędziach projektowania mówić będziemy na następnym wykładzie.