1 Struktury układów logicznychf Gate Array Standard Cell Programmable Logic Devices 1

2 Struktury układów logicznychAle w dzisiejszych technologiach układy logiczne to nie tylko bramki! FPGA Coraz większego znaczenia nabierają technologie, w których podstawowym elementem konstrukcyjnym są komórki logiczne (Logic Cell) Logic Cell … a dla tych struktur omówione do tej pory metody syntezy - w szczególności minimalizacja - są nieskuteczne Field Programmable Gate Array 2

3 Dekompozycja funkcji boolowskichDekompozycja funkcjonalna jest metodą znaną od dawna, ale jej intensywny rozwój dokonuje się od niedawna. Sytuacja jest podobna do rozwoju nowoczesnych metod minimalizacji, który to rozwój zapoczątkowany został pojawieniem się układów scalonych z milionami bramek logicznych. Jedyną różnicą jest fakt, że technologie struktur komórkowych pojawiły się znacznie później i metody ich syntezy nie są jeszcze wbudowane do systemów komercyjnych. 3

4 Dekompozycja funkcjonalnaSkuteczność dekompozycji jest tak ogromna, że mimo jej braku w narzędziach komercyjnych należy się z tymi metodami zapoznać i stosować w praktyce projektowania układów cyfrowych za pośrednictwem narzędzi uniwersyteckich. Dekompozycję funkcji boolowskich od razu omówimy w ujęciu nowoczesnym - dostosowanym do złożoności dzisiejszych technologii. Metodę klasyczną omówimy szkicowo, koncentrując się na jej mankamentach… 4

5 Dekompozycja metodą rachunku podziałówX U, V są rozłącznymi podzbiorami X, U W V ale U  V niekoniecznie = X G czyli U  V  X H W jest podzbiorem właściwym U W  U Y = F(X) Ponadto dopuszczamy powiększenie zbioru argumentów bloku G

6 Twierdzenie o dekompozycji… w ujęciu rachunku podziałów Funkcję F: Bn  {0,1}m można zrealizować w strukturze: F = H(U,G(V,W)) U G H P F wtedy i tylko wtedy, gdy istnieje podział G ³ PVW taki, że: PU · G £ PF

7 Twierdzenie o dekompozycji - interpretacjaF Y = F(X) X Y = H(U,G(V,W)) U G H P X G ³ PVW taki, że: PU · G £ PF PU PVW (PV) to podziały indukowane przez argumenty zbiorów U, V  W, (V) PF Podział wyjściowy funkcji F G  Trzeba obliczyć!!!

8 Przykład ilustrujący metodę dekompozycjiFunkcja f: Obliczyć dekompozycję dla U = {x1,x2}, V = {x3,x4,x5} x1 x2 x3 x4 x5 f 1 2 3 4 5 6 7 8 9 10 11 Nie wiemy ile jest wyjść z bloku G G H x1 x2 x3 f x5 x4 Pf =

9 Przykład…obliczanie podziałów PU, PVU = {x1,x2} V = {x3,x4, x5} x1 x2 x3 x4 x5 f 1 2 3 4 5 6 7 8 9 10 11 PU = PV = PU = Pf = Bardzo ważny w dalszych obliczeniach jest… PU |PU·Pf = Pf = 9

10 Przykład…obliczanie ПGPodział G składamy z bloków podziału PV, ale tak aby zapewnić warunki „rozdziału” zapisane w podziale PU |PU·Pf G ³ PV PU · G £ PF PU |PU·Pf = PV = G: Sklejanie, małe bloki podziału PV sklejamy w większe bloki G 3,9 ПG =

11 Komentarz G H ПG = Obliczony ΠG jest dwublokowy… fx1 x2 x3 x4 x5 Zatem dopiero teraz wiemy ile jest wyjść z bloku G. Tylko jedno wyjście! G H f 11

12 Przykład…tworzenie tablicy funkcji gH x1 x2 x3 x5 x4 ПG = x1 x2 x3 x4 x5 f 1 2 3 4 5 6 7 8 9 10 11 g 1 x3 x4 x5 g 1 2 3 4 5 6 7 8 9 10 11 x3 x4 x5 g 1

13 Przykład…tworzenie tablicy funkcji hh=f G H x1 x2 x3 x5 x4 g ПG = x1 x2 x3 x4 x5 f 1 2 3 4 5 6 7 8 9 10 11 g 1 x1 x2 g h 1 2 3 4 5 6 7 8 9 10 11 x1 x2 g h 1

14 Przykład (TL27) ilustrujący skuteczność dekompozycjiSynteza układów logicznych str. 65 .type fr .i 10 .o 1 .p 25 .e Można wykazać, że funkcja ta jest zależna od 7 argumentów X = {x3, x5, x6, x7, x8, x9, x10} Celem przykładu jest pokazanie, że cały proces dekompozycji (łącznie z obliczeniem tablic prawdy) można wykonać wyłącznie na podziałach Dalej wszystkie obliczenia będą wykonywane na podziałach P3, P5, P6, P7, P8, P9, P10 Są to podziały na zbiorze ponumerowanych wektorów 1,…,25

15 Specyfikacja funkcji – podziałamiPf =

16 Ustalenie zbiorów U i V G H X = {x3, x5, x6, x7, x8, x9, x10}Przyjmujemy arbitralnie… U = {x7, x8, x9} V = {x3, x5, x6, x10} f G H x 7 8 9 3 5 6 10 Nie wiemy ile jest wyjść z bloku G

17 Obliczenie podziałów PU, PVMożna je wyznaczyć bezpośrednio z tablicy funkcji, ale tym razem przy zastosowaniu rachunku podziałów: U = {x7, x8, x9} V = {x3, x5, x6, x10} PU=P7•P8•P9 …obliczenia są żmudne, ale proste PV=P3•P5•P6•P10 PU = PV=

18 Podział ilorazowy Pu|Pu•PFPrzy liczeniu podziału ilorazowego po prostu rozdzielamy elementy bloków PU między różne bloki podziału Pf Pu|Pu•Pf = ((1,4)(10) ; (2)(11) ; (3)(14,18,21) ; (5,9)(12,22) (6,7)(15,20,24) ; (8)(13,16,19) ; (17,25) ; (23)) W każdym bloku Pu|Pu• Pf są co najwyżej dwa elementy (nawiasy), zatem liczba bloków podziału ΠG musi być co najmniej dwa.

19 Obliczenie ΠG Pu|Pu · Pf = ((1,4)(10) ; (2)(11) ; (3)(14,18,21) ; (5,9)(12,22) ; (6,7)(15,20,24) ; (8)(13,16,19) ; (17,25) ; (23)) PV= 1 4,17 10,18,23 3,6,11 2 5,14 21 12 7,22 9 15,19,24 20 8,25 13 16

20 Liczba wyjść bloku G G H Skoro ΠG jest dwublokowy x f 7 8 9 3 5 6 10Liczba wyjść z bloku G = 1

21 Co dalej … f G H x 7 8 9 3 5 6 10 Zawartość bloków G i H, czyli tablice prawdy funkcji G i H

22 Funkcja G PV= x3 x5 x6 x10 g 1 1 1 0 1 0 1 0 1 0 0 1 0 P3 = P5 = P6 =Wektory (wiersze) tablicy funkcji g są wyznaczane przez bloki PV, a wartości tej funkcji przez bloki ΠG 1 P3 = P5 = P6 = P10 =

23 … Funkcja H < PF ...) 14,18,21 ; 3 11 2 10 1,4 ( PU  G =x7 x8 x9 g h Wektory (wiersze) tablicy funkcji h są wyznaczane przez bloki PU  G , a wartości tej funkcji przez bloki PF 1 … P7 = P8 = P9 =

24 Tylko 2 komórki typowej struktury FPGACo uzyskaliśmy… Tylko 2 komórki typowej struktury FPGA QUARTUS 23 kom. Uzyskaliśmy wynik dziesięciokrotnie razy lepszy od wyniku systemu Quartus amerykańskiej firmy Altera 24

25 Dekompozycja zespołu funkcjiTwierdzenie w ujęciu rachunku podziałów jest ogólne, obliczenia są niezależne od liczby wyjść funkcji F. X X G H Y U V F Dekompozycja Y = y1, y2,…, ym

26 Przykład dekompozycji zespołu funkcji (SUL Przykład 8.4)x1 x2 x3 x4 x5 y1 y2 y3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 v v v v v Niezależnie od liczby funkcji wszystkie wyjścia opisujemy jednym! podziałem v

27 Przykład…wyznaczanie podziałów PU, PVx3 x4 x1 x2 x5 g h • • • Szukamy dekompozycji  U = {x3,x4} V = {x1,x2,x5}   PU  = P3•P4 PV=P1•P2•P5

28 Przykład…obliczanie GJak wyznaczyć G ??? Trochę inny zapis (2) (9,14) (3,15)

29 Przykład…kodowanie ΠGW przypadku zespołu funkcji liczba bloków podziału ΠG jest większa. Należy zakodować bloki ΠG Kodowanie jest dowolne 01 10 00 Aktualna teoria nie podaje rozwiązania problemu kodowania Kodowanie jest potrzebne do wyznaczenia tablic prawdy funkcji G i H

30 Tablica prawdy G x1 x2 x5 g1 g2 0 0 0 1 0 1 0 0 01 10 00

31 … PU  G < PF PU  G = Tablica prawdy H x3 x4 g1 g2 y1 y2 y3 01 10 00 PU  G < PF … ( PU  G =

32 Co uzyskaliśmy… g h Proces minimalizacji jest niepotrzebny!!!Funkcje g i h można obliczyć jawnie…z tablic prawdy można uzyskać realizacje na bramkach. x3 x4 x1 x2 x5 g h Ale dla struktur FPGA wystarczy schemat dekompozycji i tablice prawdy. Proces minimalizacji jest niepotrzebny!!!

33 Systematyczny algorytm dekompozycjiObliczanie podziału ΠG metodą przenoszenia bloków PV na podstawie podziału ilorazowego PU│PU•ΠG jest trudne do zalgorytmizowania. Szczęśliwie jednak algorytm obliczania ΠG można sprowadzić do algorytmu obliczania MKZ.

34 Systematyczny algorytm dekompozycjiPV =( B1,…,Bi,…,Bj,…,BN) ij =( B1,…,BiBj,…,BN) Dwa bloki Bi i Bj podziału PV są zgodne, jeśli podział ij uzyskany z PV przez sklejenie Bi oraz Bj w jeden blok i pozostawienie pozostałych bloków bez zmiany spełnia warunek Twierdzenia o dekompozycji: PU  ij  PF. W przeciwnym przypadku Bi oraz Bj są niezgodne.

35 Przykład (ten sam co poprzednio)U = {x3,x4} oraz V = {x1,x2,x5}   Numerujemy bloki PV B1 B2 B B4 B5 B6 B7 B8 12 = 57 = 35

36 Przykład … Można sprawdzić, że (B1, B2) jest sprzecznaPU  12 PF, (B1, B2) jest sprzeczna PU  57  PF (B5, B7) jest zgodna Ale do wyznaczenia zgodnych (lub sprzecznych) par (Bi, Bj) niekoniecznie musimy się posługiwać skomplikowaną nierównością PU  ij  PF Wystarczy w tym celu obliczyć iloczyn zbioru Bi  Bj z blokami podziału PU i sprawdzić, czy każdy „niepusty iloczyn” jest zawarty w jakimś bloku PF

37 Przykład … B1  B2 = (B1,B2) jest sprzeczna PF (B5, B7) jest zgodna PU PF B5  B7 = (B5, B7) jest zgodna  PU  PF 37

38 Doskonale wiemy jak obliczać Maksymalne Klasy Zgodne MKZPrzykład c.d. Pary zgodne: (B1,B4), (B1,B6), (B1,B8), (B2,B3), (B2,B4), (B2,B6), (B3,B7), (B3,B8), (B4,B6), (B4,B7), (B4,B8), (B5,B7), (B6,B7), (B6,B8). Doskonale wiemy jak obliczać Maksymalne Klasy Zgodne MKZ Klasy maksymalne: {B1,B4, B6, B8} {B4, B6, B7} B1 B2 B B4 B5 B6 B7 B8 {B2, B4, B6} {B3, B8} {B3, B7} = P G ; {B2, B3} {B5, B7} ; {B1,B4, B6, B8} {B2, B3} {B5, B7}

39 Ten sam rezultat co poprzednioPrzykład c.d. B1 B2 B B4 B5 B6 B7 B8 = P G ; {B2, B3} {B5, B7} ; {B1,B4, B6, B8} Ten sam rezultat co poprzednio 39

40 Komentarz: algorytmy dekompozycjiDekompozycję funkcjonalną nazywać będziemy szeregową, dla odróżnienia od równoległej Szeregowa Równoległa 40