TC Moduł 14

From Studia Informatyczne

Enlarge
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.



Enlarge
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.



Enlarge
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.

Enlarge
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.

Enlarge
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 P_1, P_2,..., P_n, P_f\, określonymi na zbiorze K\, ponumerowanych wektorów odwzorowania F:\, B^n\to \{0,1, -\}^m.

Na początek zajmiemy się poszukiwaniem dekompozycji F = H(U,G(V,W))\,, gdzie: U, V\, są podzbiorami zbioru X = \{x_1,..., x_n\} argumentów funkcji boolowskiej, a ponadto W\subseteq U\,, U\cup V\subseteq X, U\cap V  =\Phi. Dla podanych założeń obowiązuje twierdzenie:

F = H(U,G(V,W)),

wtedy i tylko wtedy, gdy istnieje podział \Pi_G\ge P_V\cdot P_W\, taki, że:

P_U\cdot \Pi_G\le P_F\,



Enlarge
Przypomnijmy istotne dla dekompozycji elementy rachunku podziałów.

Podziałem na zbiorze S\, jest system zbiorów \pi =\{B_i\}, którego bloki są rozłączne, czyli

B_i\cap B_j =\phi , jeśli tylko i\neq j\,

Na przykład dla S = \{1,2,3,4,5,6\}, P = \{\{1,2\}, \{3,5\}, \{4,6\} \} jest podziałem na S\,, co zapisujemy:

\pi=(\overline{1,2};\overline{3,5};\overline{4,6})

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


Enlarge
Powiemy, że podział P_a\, jest nie większy od P_b\, (co oznaczamy: P_a\le  P_b\, ), jeśli każdy blok z P_a\, jest zawarty w pewnym bloku z P_b\,.

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


\Pi_a=(\overline{1,2,4};\overline{3,5,6})

\Pi_b=(\overline{1,4};\overline{2,6};\overline{3,5})

\Pi_a\bullet \Pi_b =(\overline{1,4};\overline{2};\overline{6};\overline{3,5})


Enlarge
Niech P_a\, i P_b\, są podziałami na S\, oraz P_a\ge P_b\.

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


Enlarge
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 X = \{x_3, x_5, x_6, x_7, x_8, x_9, x_1_0\}\,.

Enlarge
Przystępując do obliczenia dekompozycji najpierw należy funkcję opisać podziałami.

Enlarge
Korzystając z informacji o minimalnym zbiorze argumentów załóżmy poszukiwanie dekompozycji dla zbiorów U = \{x_7, x_8, x_9\}\, oraz 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 G\,.

Enlarge
Kolejne obliczenia uzyskane bezpośrednio z podziałów P_i\, są następujące:


\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}


\begin{matrix} P_V=P_3\cdot P_5\cdot P_6\cdot P_{10} & = & (\overline{1};\overline{2};\overline{3,6,11};\overline{4,17};\overline{5,14};\overline{7,22};\overline{8,25};\overline{9}; \\ \ &  & \overline{10,18,23};\overline{12};\overline{13};\overline{15,19,24};\overline{16};\overline{20};\overline{21};) \end{matrix}


Enlarge
Obecnie stajemy przed najważniejszym zadaniem wynikającym z twierdzenia o dekompozycji, a mianowicie przed obliczeniem podziału \Pi_G\,.

Enlarge
Dla wygody dalszych obliczeń podział P_U\, zapiszemy w postaci podziału ilorazowego:

\begin{matrix} P_U|P_U\cdot P_f & = & \overline{(1,4)(10)};\overline{(2)(11)};\overline{(3)(14,18,21)};\overline{(5,9)(12,22)}; \\ \ &  & \overline{(6,7)(15,20,24)};\overline{(8)(13,16,19)};\overline{(17)(25)};\overline{(23)} \end{matrix}


Enlarge
Interpretując twierdzenie o dekompozycji łatwo zauważyć, że podział \Pi_G\, tworzymy z bloków podziału P_V\, zgodnie z podziałem ilorazowym P_U | P_F\,.

Enlarge
Aby to zrealizować wystarczy zauważyć, że:

a) podział \Pi_G\, 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ł \Pi_G\, musi być zbudowany z bloków podziału P_V\,.

Zatem, jeśli zaliczymy bloki \overline{1}\, oraz \overline{4,17}\, do pierwszego bloku \Pi_G\,, to blok \overline{10,18,23}\, musimy zaliczyć do drugiego bloku \Pi_G\, (ponieważ zawiera element 10) itp. Reszta obliczeń jest pokazana na planszy. Na tej podstawie stwierdzamy, że:


\Pi_g=(\overline{1,3,4,6,7,8,11,12,17,22,25};\overline{2,5,9,10,13,14,15,16,18,19,20,21,23,24})


Łatwo sprawdzić, że P_U\bullet \Pi_G\le  P_F. Zatem dekompozycja istnieje.


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

Enlarge
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 G\, i H\,.

Enlarge
Tablicę funkcji G\, obliczamy korzystając z podziałów P_V\, i \Pi_G\,.

Obliczenia interpretujemy następująco. Dla przykładu: blok \overline{1}\, jest zawarty w drugim bloku podziałów P_3, P_5, P_6\,, natomiast w pierwszym bloku podziału P_1_0\, oraz w pierwszym bloku podziału \Pi_g\,. Dlatego odpowiadający mu wektor jest 1110\,, a wartość funkcji g = 0.


Enlarge
Podobnie postępujemy dla funkcji H\,, ale tu korzystamy z bloków iloczynu podziałów P_U\bullet \Pi_g\, oraz ich przynależności do podziałów P_7, P_8, P_9, \Pi_g\, oraz P_F\,.



Enlarge
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.

Enlarge
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 H,G\,, 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.

Enlarge
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 B^n\, liczbami naturalnymi K = \{1,...,|B^n|\}, a przez P_F\, podział wyjściowy funkcji F\, skonstruowany w następujący sposób:


(s,t)\in B_{P_F}\iff F(s)=F(t)\,


Inaczej mówiąc, wektory s\, i t\, należą do jednego bloku B\, podziału P_F\, tylko wtedy, gdy odwzorowanie F\, przyporządkowuje tym wektorom taki sam wektor z \{0,1\}^m\,. Na przykład, dla odwzorowania F\, określonego jak w tablicy na planszy podział P_F\, (zapisany w postaci podziału na zbiorze K = \{1,2,...,15\}\, będzie miał postać:


P_F=\{\overline{1,9,14};\overline{5,7,8,13};\overline{2,6,12};\overline{4,11};\overline{3,10,15} \}


Enlarge
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 U\,, o której niestety ze względu na ograniczony zakres wykładu nie będziemy mówili.

Zatem przyjmujemy arbitralnie U = \{x_3,x_4\} oraz V= \{x_1,x_2,x_5\}, czyli podział P_U = P_3\bullet P_4, P_V = P_1\bullet P_2\bullet P_5, a więc:


P_U=(\overline{1,7,8,13};\overline{2,3,9,14,15};\overline{4,5,10};\overline{6,11,12})

P_F=(\overline{1,9,14};\overline{5,7,8,13};\overline{2,6,12};\overline{4,11};\overline{3,10,15})

P_U|P_F=(\overline{(1)(7,8,13)};\overline{(2)(9,14)(3,15)};\overline{(4)(5)(10)};\overline{(11)(6,12)})

P_V=(\overline{1,3};\overline{2};\overline{4,6,7};\overline{5};\overline{8,9,10,12};\overline{11};\overline{13,14};\overline{15})


gdzie bloki P_V\, są oznaczone kolejno B_1, B_2,..., B_8\,.


Enlarge
Z podziału ilorazowego P_U | P_F\, 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 \Pi_G\, (to samo dotyczy (4), (5) i (10)). Ponadto pamiętamy, że \Pi_G\ge P_V\,. Zatem wprowadzenie bloków z P_V\, do tworzonego \Pi_G\, powinno przebiegać według schematu pokazanego w kolorowej tablicy na planszy. Stąd:


\Pi_G=(\overline{2,4,6,7};\overline{8,9,10,12,13,14};\overline{1,3,5,11,15})


Enlarge
Przyjmując, że kodowanie bloków \Pi_G\, jest: pierwszy blok – 01, drugi blok – 10, trzeci blok – 00 i uwzględniając, iż kolejnym blokom z podziału P_V\, odpowiadają wektory (zmienne x_1, x_2, x_5\,) odpowiednio: B_1 = 000, B_2 = 001, B_3 = 010, B_4 = 011, B_5 = 110, B_6 = 111, B_7 = 101 oraz B_8 = 100, wyznaczamy tablicę prawdy funkcji G\,.

Enlarge
Fragment tej tablicy podany jest na planszy.

Enlarge
Podobnie, po obliczeniu iloczynu:

P_U\cdot \Pi_G=(\overline{1};\overline{7};\overline{8,13};\overline{3,15};\overline{2};\overline{9,14};\overline{4};\overline{5};\overline{10};\overline{6};\overline{11};\overline{12})

wyznaczamy tablicę prawdy funkcji H\,.


Enlarge
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.

Enlarge
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.