Podręcznik
5. Dekompozycja równoległa
Dekompozycja funkcjonalna jest – podobnie jak redukcja argumentów – metodą syntezy logicznej, dostosowaną do implementacji na komórkach FPGA i pamięciach ROM. W związku z tym jej stosowanie w projektowaniu układów cyfrowych staje się coraz bardziej znaczące. W [3-20] problem dekompozycji określa się jako jedno z najpilniejszych zadań syntezy logicznej.
W szczególności proponuje się dalsze rozwijanie metody dekompozycji, polegającej na stosowaniu tzw. tablic dekompozycji (Decomposition Chart). Wydaje się jednak, że metoda zaproponowana w niniejszym rozdziale (podrozdz. 3.1, 3.2 oraz 3.3) jest znacznie skuteczniejsza. Jej zaletą jest stosowanie rachunku podziałów, co umożliwia sformułowanie wygodnego praktyce twierdzenia (Twierdzenie 3.3), w którym warunek wystarczający dekompozycji polega na wyznaczaniu podziałów na zbiorze ponumerowanych wektorów tablicy funkcji. Twierdzenie to wyraźnie wskazuje, że istotnym ograniczeniem dekompozycji jest podział wyjściowy funkcji (PF) – im drobniejszy jest podział PF, tym trudniejsze jest spełnienie warunku dekompozycji PU × PG £ PF. Stąd pomysł uzupełnienia procesu dekompozycji funkcjonalnej – dekompozycją równoległą.
D e k o m p o z y c j a r ó w n o l e g ł a w układzie opisanym przez:
(y1,..., ym ) = F(x1,..., xn ) (3-5)
to podział zbioru {y1,..., ym} na takie rozłączne podzbiory Y1 ,..., Yi ,..., Yk , z których każdy można zrealizować w układzie kombinacyjnym o argumentach odpowiednio X1 ,..., Xi ,..., Xk , gdzie Xi Í {x1,..., xn}.
Sens powyższej dekompozycji wynika z ograniczeń konstrukcyjnych produkowanych modułów PLD i FPGA. Jeśli bowiem liczba wyjść, np. modułu PLD jest mniejsza od m, to do realizacji układu opisanego przez (3-5) można przeznaczyć (w zależności od m) kilka modułów, uzyskując w rezultacie układ pokazany na rys. 3.17. W układzie tym wyjścia yi trzeba odpowiednio rozdzielić na poszczególne moduły. Wskazane jest, aby zbiór {y1,..., ym} rozdzielić na takie podzbiory Yi , dla których odwzorowanie Yi = hi (Xi ) wymagałoby możliwie najmniejszej liczby argumentów Xi, przy czym Xi Í {x1,..., xn}, Yi Í {y1,..., ym}.
Rys. 3.17. Dekompozycja równoległa
Pełną informację o rozdziale zbioru Y = {y1,...,ym} na podzbiory Y1,...,Yk uzyskać można z minimalno-argumentowych realizacji poszczególnych wyjść yi.
Dla funkcji F z tablicy 3.35 redukty poszczególnych (pojedynczych) funkcji są odpowiednio:
y1: {x1, x2, x6}
y2: {x3, x4}
y3: {x1, x2, x4, x5, x8}, {x1, x2, x4, x6, x8}
y4: {x1, x2, x3, x4, x7}
y5: {x1, x2, x4}
y6: {x1, x2, x6, x8}
Tablica 3.35
|
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
y1 |
y2 |
y3 |
y4 |
y5 |
y6 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
– |
0 |
|
2 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
– |
1 |
0 |
1 |
|
3 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
|
4 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
|
5 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
– |
0 |
1 |
|
6 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
|
7 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
– |
0 |
1 |
0 |
|
8 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
– |
1 |
|
9 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
– |
1 |
0 |
1 |
– |
1 |
|
10 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
– |
1 |
|
11 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
– |
– |
1 |
0 |
0 |
0 |
Zatem rozsądnie jest funkcji G1 przyporządkować wyjścia y1, y3, y6, a funkcji G2 wyjścia y2, y4, y5 (rys. 3. 18), gdyż wtedy uzyska się minimalne zbiory argumentów dla komponentów G1 i G2 dekompozycji równoległej funkcji F, a mianowicie {x1, x2, x4, x6, x8} dla G1 oraz {x1, x2, x3, x4, x7} dla G2. Tablice funkcji G1 i G2 są podane w tablicach 3.36a i 3.36b.
Tablica 3.36
|
a) |
|
b) |
|
|
|
|
|
|
|
|
||||||||
|
|
x1 |
x2 |
x4 |
x6 |
x8 |
y1 |
y3 |
y6 |
|
|
x1 |
x2 |
x3 |
x4 |
x7 |
y2 |
y4 |
y5 |
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
2 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
2 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
3 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
|
3 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
|
4 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
|
4 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
|
5 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
|
5 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
|
6 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
|
6 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
|
7 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
|
7 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
– |
|
8 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
|
|
9 |
0 |
0 |
1 |
0 |
1 |
– |
1 |
0 |
|
|
|
|
|
|
|
|
|
|
Rys. 3.18. Dekompozycja równoległa funkcji z przykładu 3.15
Wpływ dekompozycji zrównoważonej na ostateczny wynik syntezy w układzie FPGA zostanie pokazany na przykładzie pewnej funkcji F z 10 wejściami i 2 wyjściami (tab. 3.37), którą realizujemy w komórkach o 4 wejściach i 1 wyjściu (w uproszczeniu oznaczanych (4,1).
Tablica 3.37
|
.type fr |
|
.i 10 |
|
.o 2 |
|
.p 25 |
|
0101000000 00 |
|
1110100100 00 |
|
0010110000 10 |
|
0101001000 10 |
|
1110101101 01 |
|
0100010101 01 |
|
1100010001 00 |
|
0011101110 01 |
|
0001001110 01 |
|
0110000110 01 |
|
1110110010 10 |
|
0111100000 00 |
|
0100011011 00 |
|
0010111010 01 |
|
0110001110 00 |
|
0110110111 11 |
|
0001001011 11 |
|
1110001110 10 |
|
0011001011 10 |
|
0010011010 01 |
|
e. |
 |
 |
|
|
Rys. 3.19. Dekompozycja funkcji F |
Rys. 3.20. Dekompozycja funkcji F |
Rys. 3.21. Dekompozycja funkcji F |
Skoro funkcja F ma 10 wejść i 2 wyjścia, pierwszym krokiem dekompozycji może być dekompozycja równoległa lub szeregowa. Jednak w tym przypadku zastosujemy dekompozycję szeregową. Algorytm wydziela funkcję G mającą wejścia x1, x3, x4 i x6,. Następny krok dotyczy więc funkcji 7-wejściowej H, dla której ponownie jest wykonywana dekompozycja szeregowa. Otrzymujemy blok G o 4 wejściach i 2 wyjściach (implementowany przez 2 komórki). Blok G ma na wejściu zmienne x0, x2, x5, and x7. Są to pierwotne zmienne wejściowe i na tym etapie nie jest zwiększona liczba poziomów, co widać na rys. 3.19.
W następnym kroku dokonujemy dekompozycji równoległej. Tworzy ona dwa komponenty, każdy o jednym wyjściu, natomiast odpowiednio o 4 i 5 wejściach. Pierwszy komponent realizuje pojedyncza komórka. Drugi komponent podlega dwupoziomowej dekompozycji szeregowej. Utworzona sieć może być zrealizowana za pomocą 7 komórek (4,1). Liczba poziomów ścieżki krytycznej wynosi 3.
Ta sama funkcja zdekomponowana tak, że najpierw wykonuje się dekompozycję równoległą, jest realizowana w zupełnie innej strukturze (rys. 3.20).
Rys. 3.22 Dekompozycja funkcji F – strategia równoległa
Dekompozycja równoległa zastosowana bezpośrednio dla funkcji F tworzy 2 komponenty o 6 wejściach i jednym wyjściu. Każdy z nich podlega dwupoziomowej dekompozycji szeregowej. Dla pierwszego z nich możliwa do zastosowania jest rozłączna dekompozycja szeregowa z blokiem G1 (4,1). Drugi komponent może być również zdekomponowany szeregowo, jednak liczba wyjść bloku G2 wynosi 2. Aby zmniejszyć łączną liczbę komórek, można zastosować dekompozycję nierozłączną, uzyskując tylko 4 komórki. Tablice prawdy tych komórek podane są w tabeli 3.38. Ta znacząca zmiana struktury wynika z tego, że dekompozycja równoległa zmniejsza liczbę wejść obu komponentów, prowadząc do uproszczenia końcowej implementacji.
Tablica 3.38
|
a) funkcja G1 |
b) funkcja H1 |
c) funkcja G2 |
d) funkcja H2 |
|
0110 1 1101 1 1000 1 0010 1 0000 0 0101 0 1100 0 0100 0 0011 0 1011 0 1111 0
|
-01 0 011 1 111 0 100 1 0-0 0 110 0
|
0110 1 0011 1 0100 1 1000 1 0101 1 1100 0 0010 0 1010 0 1110 0 0001 0 0111 0 1111 0 |
10-1 0 -101 1 -111 1 0011 0 0001 1 1-00 0 0000 0 1110 1 1010 0 0100 1 0010 1 |
Z powyższego przykładu wynika, że skuteczność dekompozycji w transformacji funkcji boolowskich na sieci komórek FPGA silnie zależy od scenariusza całego procesu dekompozycji, a w szczególności od kolejności wykonywania poszczególnych procedur, a także od parametrów składowej G oraz od rozdziału wyjść na komponenty dekompozycji równoległej.