Microsoft PowerPoint - ELC_dek

ZPT

Struktury układów logicznych

FPGA

Field Programmable Gate Array

W dzisiejszych technologiach układy logiczne

to nie tylko bramki!

Coraz większego znaczenia
nabierają technologie, w których
podstawowym elementem
konstrukcyjnym są komórki logiczne
(Logic Cell)

Logic Cell

… a dla tych struktur klasyczne metody
syntezy - w szczególności minimalizacja -
są nieskuteczne

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
pojawiły się znacznie później i metody ich syntezy nie są jeszcze
wbudowane do systemów komercyjnych.

ZPT

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
technologii)

ZPT

Metoda klasyczna

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

••••

•••• •••• ••••

001

000

Elementami macierzy
M są wartości, jakie
przyjmuje funkcja f na
wektorach złożonych z
odpowiednich etykiet
i-tego wiersza i j-tej
kolumny.

... to metoda tablicowa, graficzna, której podstawowe
operacje wykonywane są na tzw. tablicy dekompozycji

ZPT

Krotność kolumn

Liczbę istotnie różnych kolumn tej macierzy ze względu na ich
zawartość nazywamy ich krotnością i oznaczamy symbolem
ν(A|B).

000

001

010

100

110

101

011

111

Krotność kolumn = 4

ZPT

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(g

(B),.., g

(B),A)

⇔ ν(A|B) ≤ 2

B (bound set), A (free set)

ZPT

Przykład

000

001

010

100

110

101

011

111

0 0

0 1

1 0

1 1

Istnieje dekompozycja !

f = h(x

, x

, g

, x

), g

, x

))

ZPT

Praktyczne znaczenie dekompozycji..

..dla struktur FPGA

ZPT

Przykład trochę trudniejszy

cde

a b

000

001

010

011

100

101

110

111

–

Istnieje dekompozycja !

f = h(a,b,g

(c,d,e), g

(c,d,e))

c d e

a b

ZPT

Relacja zgodno

ci kolumn

Jak obliczać dekompozycję

ZPT

Relacja zgodności kolumn

Kolumny {k

, k

} są zgodne, jeśli nie istnieje wiersz i,

dla którego elementy K

, K

są określone i różne,

tzn. odpowiednio: 0, 1 albo 1, 0.

ZPT

{K1,K4,K7}

Relacja zgodności kolumn

{K5,K6}

Kolumny zgodne można „sklejać”

ZPT

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.

ZPT

Przykład - obliczanie klas zgodności

cde

a b

000

001

010

011

100

101

110

111

–

K0, K1 sprzeczna

K0, K2 sprzeczna

K0, K3 zgodna

Pary sprzeczne:

K0, K4 zgodna

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

ZPT

Przykład – obliczanie klas zgodności

Stosując algorytm MKZ (był omawiany na PUL) obliczamy
rodzinę Maksymalnych Klas Zgodnych kolumn:

0,3,4,6

1,3,4,6

1,4,5

2,5,7

0,3,4,6

Wybieramy:

1,5

0,3,4,6

2,7

Rodzina rozłącznych
zbiorów kolumn
zgodnych:

1,4,5

2,5,7

Kolumny powtarzające się

usuwamy

Komentarz: formalnie

obliczamy pokrycie..

Kolumny ze zbiorów
zgodnych można sklejać!

ZPT

Sklejanie kolumn – funkcja h

cde

000

001

010

011

100

101

110

111

{K0,K3,K4,K6}

{K1,K5}

{K2,K7}

Kodowanie?

Może być dowolne

ZPT

Kodowanie kolumn – funkcja g

cde

000

001

010

011

100

101

110

111

ZPT

Co uzyskaliśmy

c d e

a b

Opis funkcji g i h tablicami prawdy wystarczy dla
realizacji w strukturach FPGA

Ale funkcje g i h można obliczyć jawnie…

czyli po procesie dekompozycji można je minimalizować

ZPT

uzyskując w rezultacie …

c d e

a b

…strukturę na bramkach

..ale to nas nie interesuje!!!

ZPT

Przykład (bardziej skomplikowany) - TL27

.type fr
.i 10
.o 1
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
1100010011 0
0100010110 0
1110100110 0
0100110000 0
0101000010 0
0111111011 1
0000010100 1
1101110011 1
0100100000 1
0100011111 1
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
1101100111 1
0010001111 1
1111100010 1
1010111101 1
0110000110 1
0100111000 1
.e

1 0

1 1 1

0 1

1 0 1

1 1

0 0 1

1 0

1 1 0

0 0

0 0 1

0 1

0 0 1

0 1

1 1 0

0 0

0 1 1

0 0

0 0 0

1 0

1 1 1

0 1

0 0 1

0 0

0 1 1

0 0

0 1 0

1 1

0 0 1

0 1

1 0 0

0 0

1 0 1

1 0

1 1 0

1 1

1 1 1

0 0

1 0 0

0 1

0 1 0

1 1

1 0 0

0 0

1 1 0

1 1

1 1 1

1 0

0 1 1

ZPT

Tablica dekompozycji dla funkcji TL27

0
0
0
0

0
0
1
0

0
0
1
1

0
1
0
0

0
1
0
1

0
1
1
0

0
1
1
1

1
0
0
0

1
0
0
1

1
0
1
0

1
0
1
1

1
1
0
0

1
1
0
1

1
1
1
0

1
1
1
1

000

–

001

–

010

–

011

–

100

–

101

–

110

–

111

–

ZPT

Tablica dekompozycji dla funkcji TL27

000

001

010

011

100

–

101

110

–

111

–

••••

ZPT

Praktyczny wynik dekompozycji funkcji TL27

Tylko 2 komórki

ZPT

Zagadka

QUARTUS

25 kom. (FLEX)

lub 27 kom. (Stratix)!!!

Na ilu komórkach zrealizuje tę funkcję
amerykański system QUARTUS?

Niesamowita skuteczność

procedur dekompozycji!!!

ZPT

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ą

ZPT

Metoda bezpośrednia

a, b

b, c
a, c

{a, b, c}

a, b, c

a, b, d

b, c, d
a, c, d

{a, b, c, d}

i.t.d.

Pary zgodne:

ZPT

Przykład – obliczanie klas zgodności

1,4,5

1,4,6

2,5,7

3,4,6

0,3,4,6

Maksymalne klasy
zgodności:

0,3
0,4
0,6

1,3
1,4
1,5
1,6

2,5
2,7

3,4
3,6

4,5
4,6

5,7

0,3,4

0,4,6

0,3,6

1,3,4

1,3,6

1,3,4,6

1,4,5

2,5,7

ZPT

Algorytm MKZ wg par zgodnych

E – relacja zgodności (e

)

∈ E

= { e

| i < j oraz (e

)

∈ E}

RKZ

k+1

∈ RKZ

a) R

k+1

φ, RKZ

k+1

jest powiększana o klasę KZ = {k+1}

b) KZ

∩ R

k+1

φ, KZ bez zmian

c) KZ

∩ R

k+1

≠ φ, KZ’ = KZ ∩ R

k+1

∪ {k+1}

ZPT

Przykład

0,1

0,1,3

1,2,4

= { e

| i < j oraz (e

)

∈ E}

0,3
0,4
0,6
1,3
1,4
1,5
1,6
2,5
2,7
3,4
3,6
4,5
4,6
5,7

φ
φ

= 0,1,3,4

= 2,5

ZPT

Przykład

{0,1}

{0,1,3}

{1,2,4}

φ
φ

= {0,1,3,4}

= {2,5}

{0}

{0} {1}

{0} {1} {2}

{0,3} {1,3} {2}

{0,3,4} {1,3,4} {2}
{4,5} {1,4,5} {2,5} {0,3,4} {1,3,4}

{1,4,6}

{2,5,7}

{0,3,4,6} {1,3,4,6}

{2,5}

{1,4,5}

{0,3,4,6} {1,3,4,6} {5,7} {1,4,5}

Rodzina MKZ

ZPT

Przykład…

0,3
0,4
0,6
1,3
1,4
1,5
1,6
2,5
2,7
3,4
3,6
4,5
4,6
5,7

Pary zgodne:

Pary sprzeczne:

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

ZPT

Graf niezgodno

(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)

i jego kolorowanie