TC Moduł 14

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.

---

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.

---

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.

---

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.

---

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},\ldots ,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},\ldots ,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}\geq P_{V}\cdot P_{W}\,$ taki, że: $P_{U}\cdot \Pi _{G}\leq P_{F}\,$

---

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

---

Powiemy, że podział $P_{a}\,$ jest nie większy od $P_{b}\,$ (co oznaczamy: $P_{a}\leq 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 $\leq \,$) 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}})$

---

Niech $P_{a}\,$ i $P_{b}\,$ są podziałami na $S\,$ oraz $P_{a}\geq 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}\,$.

---

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. connect ECONNREFUSED 127.0.0.1:10042”): {\displaystyle X=\{x_{3},x_{5},x_{6},x_{7},x_{8},x_{9},x_{1}_{0}\}\,} .

---

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

---

Korzystając z informacji o minimalnym zbiorze argumentów załóżmy poszukiwanie dekompozycji dla zbiorów $U=\{x_{7},x_{8},x_{9}\}\,$ oraz Parser nie mógł rozpoznać (Błąd konwersji. Serwer („https://wazniak.mimuw.edu.pl/api/rest_”) zgłosił: „Cannot get mml. connect ECONNREFUSED 127.0.0.1:10042”): {\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 $G\,$.

---

Kolejne obliczenia uzyskane bezpośrednio z podziałów $P_{i}\,$ są następujące: Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\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}} ${\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}}$

---

Obecnie stajemy przed najważniejszym zadaniem wynikającym z twierdzenia o dekompozycji, a mianowicie przed obliczeniem podziału $\Pi _{G}\,$.

---

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

---

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}\,$.

---

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}\leq P_{F}$. Zatem dekompozycja istnieje.

---

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\,$.

---

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\,$.

---

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 Parser nie mógł rozpoznać (Błąd konwersji. Serwer („https://wazniak.mimuw.edu.pl/api/rest_”) zgłosił: „Cannot get mml. connect ECONNREFUSED 127.0.0.1:10042”): {\displaystyle P_{1}_{0}\,} oraz w pierwszym bloku podziału $\Pi _{g}\,$. Dlatego odpowiadający mu wektor jest $1110\,$, a wartość funkcji $g=0$.

---

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}\,$.

---

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.

---

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.

---

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,\ldots ,|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,\ldots ,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}}\}$

---

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},\ldots ,B_{8}\,$.

---

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}\geq 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}})$

---

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\,$.

---

Fragment tej tablicy podany jest na planszy.

---

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\,$.

---

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.

---

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.

---