Struktury ukÅ‚adów logicznych f Gate Array Standard Cell I T P W Programmable Logic Devices ZPT 1 Struktury ukÅ‚adów logicznych Ale w dzisiejszych technologiach ukÅ‚ady logiczne to nie tylko bramki! Coraz wiÄ™kszego znaczenia FPGA 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 I minimalizacja - sÄ… nieskuteczne T P W Field Programmable Gate Array ZPT 2 Dekompozycja 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 I T pojawiÅ‚y siÄ™ znacznie pózniej i metody ich syntezy nie nie sÄ… P W jeszcze wbudowane do systemów komercyjnych. ZPT 3 Dekompozycja funkcjonalna Skuteczność 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 omówimy w dwóch ujÄ™ciach: a) metoda klasyczna (znana od dawna...) b) metoda nowoczesna (dostosowana do zÅ‚ożonoÅ›ci dzisiejszych I technologii) T P W ZPT 4 Metoda klasyczna ... to metoda tablicowa, graficzna, której podstawowe operacje wykonywane sÄ… na tzw. tablicy dekompozycji TablicÄ… dekompozycji funkcji f nazywamy macierz dwuwymiarowÄ… o kolumnach etykietowanych wartoÅ›ciami zmiennych funkcji f ze zbioru B oraz o wierszach etykietowanych wartoÅ›ciami zmiennych funkcji f ze zbioru A B x1x2x3 " " " " " " " " " " " " x4x5 000 001 Elementami macierzy 0 1 00 M sÄ… wartoÅ›ci, jakie przyjmuje funkcja f na 1 0 I 01 A T wektorach zÅ‚ożonych z P odpowiednich etykiet " " " " W " i-tego wiersza i j-tej " " " " " " " ZPT kolumny. 5 Krotność kolumn LiczbÄ™ istotnie różnych kolumn tej macierzy ze wzglÄ™du na ich zawartość nazywamy ich krotnoÅ›ciÄ… i oznaczamy symbolem ½(A|B). B x1x2x3 000 001 010 100 110 101 011 111 x4x5 00 1 1 1 1 0 0 0 0 01 0 1 1 1 0 0 0 0 10 0 0 0 0 0 0 0 0 A 11 0 0 0 0 1 1 1 0 I T P Krotność kolumn = 4 W ZPT 6 Klasyczne twierdzenie o dekompozycji Niech bÄ™dzie dana funkcja boolowska f oraz podziaÅ‚ zbioru zmiennych wejÅ›ciowych funkcji f na dwa rozÅ‚Ä…czne zbiory A i B, to wówczas: f(A,B) = h(g1(B),.., gj(B),A) Ô! ½(A|B) d" 2j. A f h g B I T P W B (bound set), A (free set) ZPT 7 PrzykÅ‚ad B x1x2x3 000 001 010 100 110 101 011 111 x4x5 00 1 1 1 1 0 0 0 0 01 0 1 1 1 0 0 0 0 10 0 0 0 0 0 0 0 0 A 11 0 0 0 0 1 1 1 0 g1g2 00 01 10 11 x1 x2 x3 g1 g2 x4x5 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 1 1 1 0 0 1 0 1 1 0 1 0 I 1 0 1 1 0 T Istnieje dekompozycja ! P 0 1 1 1 0 W 1 1 1 1 1 f = h(x4, x5, g1(x1, x2, x3), g2(x1, x2, x3)) ZPT 8 Praktyczne znaczenie dekompozycji.. ..dla struktur FPGA x4 x5 x1 x2 x3 x1 x2 x3 x4 x5 g f h g1 g2 h I T P W ZPT 9 PrzykÅ‚ad trochÄ™ trudniejszy cde 000 001 010 011 100 101 110 111 a b 00 1 0 1 0 1 0 01 1 1 10 0 1 0 0 0 1 11 0 1 K0 K1 K2 K3 K4 K5 K6 K7 a b c d e Istnieje dekompozycja ! g I f = h(a,b,g1(c,d,e), g2(c,d,e)) T h P W ZPT 10 Relacja zgodnoÅ› Å›ci kolumn Å› Å› Jak obliczać dekompozycjÄ™ I T P W ZPT 11 Relacja zgodnoÅ›ci kolumn Kolumny {kr, ks} sÄ… zgodne, jeÅ›li nie istnieje wiersz i, dla którego elementy Kir, Kis sÄ… okreÅ›lone i różne, tzn. odpowiednio: 0, 1 albo 1, 0. K1 K2 K3 K4 K5 K6 K7 1 -0 1 -0 1 - --- 11 - - 0 1 0 0 - 0 I T 0 1 - -- - 0 P W ZPT 12 Relacja zgodnoÅ›ci kolumn K1 K2 K3 K4 K5 K6 K7 1 -0 1 -0 1 - --- 11 - - 0 1 0 0 - 0 0 1 - -- - 0 Kolumny zgodne można sklejać {K1,K4,K7} 1 0 {K5,K6} - 1 I T 0 0 P W 0 - ZPT 13 Obliczanie dekompozycji... Wyznaczyć relacjÄ™ zgodnoÅ›ci kolumn, czyli wypisać wszystkie pary sprzeczne. Wyznaczyć rodzinÄ™ maksymalnych zbiorów kolumn zgodnych (maksymalnych klas zgodnych MKZ). Z rodziny tej wyselekcjonować minimalnÄ… podrodzinÄ™ (w sensie licznoÅ›ci) rozÅ‚Ä…cznych zbiorów zgodnych pokrywajÄ…cÄ… zbiór K wszystkich kolumn tablicy dekompozycji. I T P W ZPT 14 PrzykÅ‚ad - obliczanie klas zgodnoÅ›ci Pary sprzeczne: 0,1 cde 0,2 000 001 010 011 100 101 110 111 a b 0,5 00 1 0 1 0 1 0 0,7 01 1 1 10 0 1 0 0 0 1 1,2 11 0 1 1,7 K0 K1 K2 K3 K4 K5 K6 K7 2,3 2,4 2,6 K0, K1 sprzeczna 3,5 3,7 K0, K2 sprzeczna 4,7 I 5,6 T K0, K3 zgodna P 6,7 W K0, K4 zgodna ZPT 15 PrzykÅ‚ad obliczanie klas zgodnoÅ›ci StosujÄ…c algorytm MKZ obliczamy rodzinÄ™ Maksymalnych Klas Zgodnych kolumn: Ostatecznie: Wybieramy: 0,3,4,6 0,3,4,6 0,3,4,6 1,3,4,6 1,4,5 1,4,5 1,5 2,5,7 2,5,7 2,7 Kolumny powtarzajÄ…ce siÄ™ usuwamy Komentarz: formalnie I KZ = K T
obliczamy pokrycie.. P KZ"RKZS W ZPT 16 Sklejanie kolumn funkcja h cde 000 001 010 011 100 101 110 111 ab 00 1 -0 1 -0 1 0 01 ----11 -- 10 -0 1 0 0 - 0 1 11 0 1 --- - - - K0 K1 K2 K3 K4 K5 K6 K7 {K0,K3,K4,K6} {K1,K5} {K2,K7} g1g2 00 01 11 10 ab Kodowanie? 00 1 0 0 - Może być dowolne I 01 1 1 - - T P 10 0 0 1 - W 11 0 1 - - ZPT 17 Kodowanie kolumn funkcja g cde 000 001 010 011 100 101 110 111 ab 00 1 -0 1 -0 1 0 01 ----11 -- 10 -0 1 0 0 - 0 1 11 0 1 --- - - - K0 K1 K2 K3 K4 K5 K6 K7 c d e g1 g2 g1g2 00 01 11 10 0 0 0 0 0 ab 0 1 1 0 0 00 1 0 0 - 1 0 0 0 0 1 1 0 0 0 01 1 1 - - 0 0 1 0 1 I T 10 0 0 1 - 1 0 1 0 1 P W 0 1 0 1 1 11 0 1 - - 1 1 1 1 1 ZPT 18 Co uzyskaliśmy c d e g1 g2 a b c d e 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 g 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 g1g2 h 00 01 11 10 ab 00 1 0 0 - 01 1 1 - - 10 0 0 1 - 11 0 1 - - Opis funkcji g i h tablicami prawdy wystarczy dla realizacji w strukturach FPGA I T Ale funkcje g i h można obliczyć jawnie& P W ZPT czyli po procesie dekompozycji można je minimalizować 19 uzyskując w rezultacie & a b c d e g h & strukturę na bramkach I T P W ZPT 20 Przykład funkcje g1 i g2 c d e g1 g2 e e 0 1 0 1 0 0 0 0 0 cd cd 0 1 1 0 0 00 00 00 0 1 1 0 0 0 0 1 1 0 0 0 01 1 0 01 1 0 0 0 1 0 1 11 0 1 11 0 1 1 0 1 0 1 10 00 10 0 1 0 1 0 1 1 1 1 1 1 1 +cde +ce + de g =cde g =cde 1 2 I T P W ZPT 21 Przykład funkcja h Uwaga: g1g2 00 01 11 10 Przestawiliśmy wiersze ab 00 1 0 0 - 01 1 1 - - 11 0 1 - - 10 0 0 1 - h = ag2 + bg2 + ag1 I T P W ZPT 22 Przykład realizacja a b c d e c e c d e c d e c d e d e G g1 g2 a g2 b g2 a g1 H I T P W h = f ZPT 23 Przykład (bardziej skomplikowany) - TL27 .type fr x3 x5 x6 x7 x8 x9 x10 f .i 10 x7 x8 x9 x3 x5 x6 x10 f .o 1 1 0 1 1 1 1 0 0 1 1 1 1 0 1 0 0 .p 25 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 0 0010111010 0 1 1 1 0 0 1 0 0 0 0 1 1 1 1 0 0 1010010100 0 1 0 1 1 1 0 1 0 1 1 0 1 0 1 1 0 0100011110 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 0 1011101011 0 0 1 1 0 0 1 0 0 1100010011 0 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0100010110 0 1 1 0 0 1 1 0 0 1110100110 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0100110000 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0101000010 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0111111011 1 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0000010100 1 0 0 1 0 1 1 1 1 0 1 1 0 0 1 1 1 1101110011 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0100100000 1 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1 0100011111 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 1 0010000110 1 0 0 0 1 0 1 1 1 1111010001 1 1 0 1 0 0 0 1 1 1111101001 1 1 0 0 1 1 0 1 1 1 1 0 1 0 0 1 1 1111111111 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0010000000 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 1101100111 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0010001111 1 I 1 1 1 1 0 0 1 1 1 0 0 1 1 1 1 1 1111100010 1 T 0 0 1 1 1 0 0 1 1 1 0 0 0 1 0 1 P 1010111101 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 W 0110000110 1 1 0 0 0 1 1 0 1 0 1 1 1 0 0 0 1 0100111000 1 .e ZPT B A 24 Tablica dekompozycji dla funkcji TL27 x3 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 x5 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 x6 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 x10 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 x7x8x9 1 0 1 1 000 0 0 1 1 001 1 0 010 0 1 1 0 011 1 1 100 0 0 1 101 1 110 I T 1 1 1 111 P W ZPT 25 Tablica dekompozycji dla funkcji TL27 H G x3 x5 x6 x10 G g 0 1 0 0 0 0 0 x7x8x9 0 0 1 0 1 1 0 000 0 0 1 1 0 0 1 001 0 1 0 0 0 0 1 010 0 1 0 1 0 0 1 1 0 1 1 0 011 0 1 1 1 1 1 100 1 0 0 0 0 1 0 101 " " " " " " " " " " " " " " " " 1 110 " " " " " " " " 1 1 1 1 0 1 111 I T P W ZPT 26 Praktyczny wynik dekompozycji funkcji TL27 .type fr .i 10 .o 1 .p 25 x3 x5 x6 x10 0010111010 0 1010010100 0 0100011110 0 1011101011 0 1100010011 0 0100010110 0 G 1110100110 0 x7 x8 x9 0100110000 0 0101000010 0 0111111011 1 0000010100 1 1101110011 1 0100100000 1 0100011111 1 H 0010000110 1 1111010001 1 1111101001 1 1111111111 1 0010000000 1 Tylko 2 komórki f 1101100111 1 0010001111 1 1111100010 1 1010111101 1 I 0110000110 1 T 0100111000 1 P .e W ZPT 27 Zagadka Na ilu komórkach zrealizuje tę funkcję amerykański system QUARTUS? 25 kom. (FLEX) QUARTUS lub 27 kom. (Stratix)!!! I T P W ZPT 28 Jak usprawnić obliczanie MKZ? W metodzie dekompozycji jednym z najważniejszych algorytmów jest algorytm obliczania maksymalnych klas zgodności W celu sprawniejszego obliczania MKZ wprowadzimy metodę wg par zgodnych: a) metodę bezpośrednią b) metodę iteracyjną I T P W ZPT 29 Metoda bezpośrednia Pary zgodne: a, b b, c {a, b, c} a, c a, b, c a, b, d {a, b, c, d} b, c, d a, c, d i.t.d. I T P W ZPT 30 Przykład obliczanie klas zgodności 0,3 0,4 Maksymalne klasy 0,6 0,3,4 zgodności: 0,3,6 1,3 0,4,6 1,4 1,5 0,3,4,6 1,3,4 1,6 1,3,6 1,3,4,6 2,5 1,4,5 2,7 1,4,5 1,4,6 3,4 2,5,7 3,6 2,5,7 4,5 3,4,6 4,6 I T P W 5,7 ZPT 31 Algorytm MKZ wg par zgodnych E relacja zgodności (ei,ej) " E Rj = { ei | i < j oraz (ei,ej) " E} RKZk RKZk+1 KZ " RKZk a) Rk+1 = Ć, RKZk+1 jest powiększana o klasę KZ = {k+1} b) KZ )" Rk+1 = Ć, KZ bez zmian c) KZ )" Rk+1 `"Ć, KZ = KZ )" Rk+1*" {k+1} I T P W ZPT 32 Przykład Rj = { ei | i < j oraz (ei,ej) " E} 0,3 Ć R0 = E: 0,4 R1 = 0,6 Ć 1,3 R2 = Ć 1,4 1,5 R3 = 0,1 1,6 2,5 R4 = 0,1,3 2,7 3,4 R5 = 1,2,4 3,6 I 4,5 R6 = 0,1,3,4 T P 4,6 W 5,7 R7 = 0,2,5 ZPT 33 Przykład Ć R0 = {0} R1 = Ć {0} {1} R2 = Ć {0} {1} {2} R3 = {0,1} {0,3} {1,3} {2} R4 = {0,1,3} {2} {0,3,4} {1,3,4} R5 = {1,2,4} {4,5} {1,4,5} {2,5} {0,3,4} {1,3,4} R6 = {0,1,3,4} {1,4,6} {0,3,4,6} {1,3,4,6} {1,4,5} {2,5} {1,4,5} R7 = {0,2,5} {2,5,7} {0,3,4,6} {1,3,4,6} {5,7} I T P W Rodzina MKZ ZPT 34 Warto umieję ć ę... ętnie dobierać metodę ę ć ę ę ć ę Pary zgodne: (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (2,3), (2,5), (2,6), (2,7), (3,4), (3,5), (3,6), (3,8), (4,6), (4,7), (4,8), (5,6), (5,7), (5,8), (6,7), (6,8), (7,8), Pary sprzeczne: (1,8) (2,4) (2,8) (3,7) (4,5) Wybór metody jest oczywisty! I T P W ZPT 35 W poszukiwaniu innych metod& W obliczaniu kolumn, które można skleić znajdują zastosowanie algorytmy kolorowania grafu. Wierzchołki grafu reprezentują kolumny tablicy dekompozycji. Niezgodne pary kolumn łączy się krawędziami. Graf niezgodności: Pary niezgodne: k1 ks (ki, kj) k2 (ki, ks) kr (kl, kr) ki I T P kj W kp kl ZPT 36 Przykład& Pary sprzeczne: Pary zgodne: 0,3 0,1 0,4 0,2 0,6 0,5 1,3 0,7 1,4 1,2 1,5 1,7 1,6 2,3 2,5 2,4 2,7 2,6 3,4 3,5 3,6 3,7 I 4,5 4,7 T P 4,6 5,6 W 5,7 6,7 ZPT 37 Graf niezgodnoś ści ś ś (0,1), (0,2), (0,5), (0,7), (1,2), (1,7), (2,3), (2,4), (2,6), (3,5), (3,7), (4,7), (5,6), (6,7) 0 7 1 i jego kolorowanie 6 2 I T 3 5 P W 4 ZPT 38