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,...,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=\mathrm{\Phi }$. Dla podanych założeń obowiązuje twierdzenie: $F=H(U,G(V,W))$, wtedy i tylko wtedy, gdy istnieje podział ${\mathrm{\Pi }}_G\ge P_V\cdot P_W$ taki, że: $P_U\cdot {\mathrm{\Pi }}_G\le 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=\varphi$ , jeśli tylko $i\ne 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\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 ${\mathrm{\Pi }}_a=(\overline{1,2,4};\overline{3,5,6})$ ${\mathrm{\Pi }}_b=(\overline{1,4};\overline{2,6};\overline{3,5})$ ${\mathrm{\Pi }}_a\bullet {\mathrm{\Pi }}_b=(\overline{1,4};\bar{2};\bar{6};\overline{3,5})$

---

Niech $P_a$ i $P_b$ są podziałami na $S$ oraz Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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$.

---

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

---

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 składni): {\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$.

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---