I
T
P
W
ZPT
1
UKA
ADY FPGA Z WBUDOWANYMI PAMI
CIAMI
(FLEX 10K10)
I/O Element
IOE IOE IOE
(IOE) IOE IOE IOE
Fast Track
Interconnect
IOE
IOE
IOE
IOE
Embedded
Array
Logic Element
ROM
Block
(LE)
IOE
IOE
IOE
IOE
Embedded
Logic Array Block
Array
(LAB)
Block
I
Logic
T
Array
IOE IOE IOE
IOE IOE IOE
P
W
ZPT
2
IMPLEMENTACJA AUTOMATÓW
ZA POMOC
PAMI
CI ROM
X
x
q
Rejestr adresowy
x + q
Pamięć mikroprogramu
EABs
(ROM)
y
FQ
Niestety taka realizacja wiąże się z
ogromnymi wymaganiami na pojemność
pamięci
I
T
P (x+q)
M = 2 × (q + y)
W
ZPT
3
UKA
ADY MIKROPROGRAMOWANE
Takt
RA
UA
X
X
A
ROM
Multiplekser warunków
UO
I
T
P
W
ZPT
4
MODYFIKACJA ADRESU
X
x
q
b
Pojemność ROM:
LUTs
Modyfikator adresu
(a+c)
M = 2 × (q + y)
a
c < b
Rejestr
(a + c) < (x + q)
Pamięć mikroprogramu
EABs
(ROM)
I
y
T
P
FQ
W
ZPT
5
JAK TO ZREALIZOWAĆ ???
X
X
x
x
q
q
b
b
Modyfikator G
Funkcjaadresu
a
a
c < b
c < b
Rejestr
Rejestr
(a + c) < (x + q)
(a + c) < (x + q)
Pamięć mikroprogramu
Funkcja H
(ROM)
y
y
I
T
P
FQ
FQ
W
ZPT
6
JAK TO ZREALIZOWAĆ ???
Y Funkcja G reprezentuje
U
W V
modyfikator adresu
LUTs
G
Y Funkcja H opisuje
zawartość pamięci
Rejestr
EABs
H
I
T
P
F = H(U, G(V *" W))
W
ZPT
7
ALGORYTM SYNTEZY AUTOMATU
(algebra podziałów)
1. Wybór zbioru U (wstępne kodowanie)
2. Określenie podziałów:
P(U), Pg = P(V)
3. Szukanie podziału g e" Pg
 e"
 e"
 e"
P(U) " g d" PF
"  d"
"  d"
"  d"
(czasami istnieje potrzeba wprowadzenia zbioru W)
4. Obliczenie funkcji G oraz H
I
T
P
W
ZPT
8
PRZYKA
AD
Wejścia (x1 , x2)
x1 x2
I1 I2 I3 I4 Wyj-
Stany
ścia
S1 S1 S2 S4 -
W
Y
S2 - - S5 S4
MODYFIKATOR ADRESU
J
Åš
S3 S3 S2 S1 S3
C
I
S4 S2 - S4 S1
REJESTR
A
S5 S3 S1 S4 S2
Odpowiednie zakodowanie stanów i
ROM
wejść może pomóc w podziale
zmiennych wejściowych na zbiory U i V
I
T
P
W
WY
ZPT
9
PRZYKA
AD c.d.
Kluczem do rozwiÄ…zania tego problemu jest permutacja
wierszy i/lub kolumn tablicy przejść oraz odpowiedni
podział tablicy przejść na podtablice z minimalna liczbą
stanów następnych
x 1 x q
2 1
I1 I2 I3 I4
MA
S1 S1 S2 S4 -
Modyfikator Adresu
S2 - - S5 S4
Rejestr
S4 S2 - S4 S1
S3 S3 S2 S1 S3
ROM
S5 S3 S1 S4 S2
I
T
P
W
Przestawiliśmy wiersze
Out
S3 oraz S4
ZPT
10
PRZYKA
AD c.d.
Przyjęty podział tablicy wymusza odpowiednie kodowanie
tzw. kodowanie wstępne
00 01 11 10
S1 0 S1 S2 S4 -
U= {x1,x2,q1}
V= {q2,q3}
S2 0 - - S5 S4
S4 0 S2 - S4 S1
S3 1 S3 S2 S1 S3
S5 1 S3 S1 S4 S2
I
Kodowanie wstępne koduje tylko jedną zmienną q, czyli q1
T
P
oraz zmienne zewnętrzne x
W
ZPT
11
PRZYKA
AD c.d.
Uzyskane kodowanie trzeba zapisać w rachunku podziałów
U= {x1,x2,q1}
V= {q2,q3}
x1x2
q1 q2 q3
00 01 11 10
00 01 11 10
S1 0 ? ?
1 2 3 -
S1 0 S1 S2 S4 -
- - 4 5
S2 0 ? ?
S2 0 - - S5 S4
S4 0 ? ? 6 - 7 8
S4 0 S2 - S4 S1
9 10 11 12
S3 1 S3 S2 S1 S3
S3 1 ? ?
13 14 15 16
S5 1 S3 S1 S4 S2 S5 1 ? ?
I
P(U)|PF = ((1)(6) ; (2) ; (3,7)(4) ; (5)(8) ;
T
P
W
(9,13) ; (10)(14) ; (11)(15) ;(12)(16))
ZPT
12
PRZYKA
AD c.d.
Kodowanie wtórne
U= {x1,x2,q1}
x1x2
V= {q2,q3}
q1 q2 q3 00 01 11 10
1 2 3 -
S1 0 0 0
- - 4 5
S2 0 0 1
S4 0 1 0
6 - 7 8
S3 1 1 1
9 10 11 12
S5 1 0 1
13 14 15 16
P(V) = (1,2,3; 4,5,13,14,15,16; 6,7,8; 9,10,11,12)
I
T
P
W
ZPT
13
PRZYKA
AD c.d.
U= {x1, x2, q1}V = {q2, q3}
P(U)|PF = ((1)(6) ; (2) ; (3,7)(4) ; (5)(8) ; (9,13) ; (10)(14) ;
(11)(15) ; (12)(16))
P(V) = (1,2,3; 4,5,13,14,15,16; 6,7,8; 9,10,11,12)
x1x2
00 01 11 10
"G
"
"
"
1 2 3 -
1, 2, 3 6, 7, 8
- - 4 5
6 - 7 8
4, 5, 13, 14, 15, 16 9, 10, 11, 12
9 10 11 12
I
T
P 13 14 15 16
W
Przyjmujemy: W = {x1}
ZPT
14
PRZYKA
AD c.d.
V = {x1, q2, q3}
P(V' ) = (1,2 ; 3 ; 13,14 ; 4,5,15,16 ; 6 ; 7,8 ; 9,10 ; 11,12)
P(U)|PF = ((1)(6) ; (2) ; (3,7)(4) ; (5)(8) ; (9,13) ; (10)(14) ;
(11)(15) ; (12)(16))
g = (1,2,3,7,8,9,10,11,12 ; 4,5,6,13,14,15,16)
Uwaga: jest to inne rozwi ce
zanie ni w ksi


I
T
Synteza układów logicznych
P
W
ale oba rozwi
zania s dobre


ZPT
15
PRZYKA
AD c.d.  tablica funkcji G
0 1
g = (1,2,3,7,8,9,10,11,12 ; 4,5,6,13,14,15,16)
P(V') = (1,2 ; 3 ; 13,14 ; 4,5,15,16 ; 6 ; 7,8 ; 9,10 ; 11,12)
x1 q2 q3 g
0 0 0
0
x1x2
q1q2q3 00 01 11 10
0
1 0 0
0 0 1
1
S1 0 0 0 1 2 3 -
S2 0 0 1
- - 4 5
S4 0 1 0
6 - 7 8
I
T
S3 1 1 1
9 10 11 12
P
W
S5 1 0 1
13 14 15 16
ZPT
16
PRZYKA
AD c.d.
x1
g
x1 x2 q1
q2
G
q3
REJESTR
g = x1q2q3 + q2q3
H
q1 q2 q3
I
T
P
W
ZPT
17
PRZYKA
AD c.d.  tablica funkcji H
q1 q2 q3 x1x2 00 01 11 10
I1 I2 I3 I4
S1 S1 S2 S4 -
S1 0 0 0
1 2 3 -
S2 - - S5 S4
- - 4 5
S2 0 0 1
S4 S2 - S4 S1
6 - 7 8
S4 0 1 0
S3 S3 S2 S1 S3
9 10 11 12
S3 1 1 1
S5 S3 S1 S4 S2
13 14 15 16
S5 1 0 1
P(U) = (1,6 ; 2 ; 3,4,7 ; 5,8 ; 9,13 ; 10,14 ; 11,15; 12,16)
G = (1,2,3,7,8,9,10,11,12 ; 4,5,6,13,14,15,16)
I
T
P(U) " G = (1; 6; 2; 3,7; 4; 5; 8; 9; 13; 10; 14; 11; 15; 12; 16)
" 
" 
" 
P
W
ZPT
18
PRZYKA
AD c.d.  tablica funkcji H
q1 q2 q3 x1x2 00 01 11 10
I1 I2 I3 I4
S1 0 0 0
1 2 3 -
S1 S1 S2 S4 -
- - 4 5
S2 0 0 1
S2 - - S5 S4
6 - 7 8
S4 0 1 0
S4 S2 - S4 S1
9 10 11 12
S3 1 1 1
S3 S3 S2 S1 S3
13 14 15 16
S5 1 0 1
S5 S3 S1 S4 S2
P(U) " G = (1; 6; 2; 3,7; 4; 5; 8; 9; 13; 10; 14; 11; 15; 12; 16)
" 
" 
" 
x1 x2 q1 g
1
0 0 0 0 S1
g = (1,2,3,7,8,9,10,11,12 ; 4,5,6,13,14,15,16)
6
S2
0 0 0 1
I
T
2 S2
0 1 0 0
P
W
S4
3,7 1 1 0 0
ZPT
19
PRZYKA
AD c.d.
x1
g
x1 x2 q1
q2
G
q3
REJESTR
g = x1q2q3 + q2q3
ROM
Tablica H określa zawartość
q1 q2 q3
pamięci ROM
I
T
P
W
ZPT
20
PRZYKA
AD - ten sam automat&
& ale w innej strukturze
x 1 x
2
U= {q1,q2}
V= {q3, x1,x2 }
q
3
I1 I2 I3 I4
UMA
q
q
1
2
S1 S1 S2 S4 -
Rejestr
Teraz sÄ…
S2 - - S5 S4
dwa wyjścia z UMA
S3 S3 S2 S1 S3
ROM
S4 S2 - S4 S1
S5 S3 S1 S4 S2
I
T
P
Out
W
ZPT
21
PRZYKA
AD c.d. - wyznaczenie P(U)
Kodowanie wstępne
U= {q1,q2}
V= {q3, x1,x2 }
x1x2
q1 q2 q3
00 01 11 10
I1 I2 I3 I4
S1 0 0 ?
1 2 3 -
S1 S1 S2 S4 -
- - 4 5
S2 0 0 ?
S2 - - S5 S4
6 7 8 9
S3 S3 S2 S1 S3
S3 0 1 ?
10 - 11 12
S4 S2 - S4 S1
S4 1 0 ?
13 14 15 16
S5 S3 S1 S4 S2
S5 1 1 ?
(
=
P(U)
1,2,3,4,5; 6,7,8,9; 13,14,15,16)
10, 11,12;
I
P(U)|PF=
(1),(3,5),(2),(4);
(6,9),(7),(8); (10),(11),(12);
T
P
W
(13),(14),(15),(16)
ZPT
22
PRZYKA
AD c.d. - wyznaczenie P(V)
U= {q1,q2}
Kodowanie wtórne
V= {q3, x1,x2 }
x1x2
q1 q2 q3
00 01 11 10
00
S1 0 0 0
1 2 3 -
- - 4 5
S2 0 0 1
S3 0 1 0 6 7 8 9
10 - 11 12
S4 1 0 1
13 14 15 16
S5 1 1 1
I
T
P(V) = (1,6 ; 10,13 ; 2,7 ; 14 ; 3,8 ; 4,11,15 ; 9;5,12,16)
P
W
ZPT
23
PRZYKA
AD c.d.  obliczenie G



x1x2
00
01 11 10
q1q2q3
000
1 2 3 -
P(U)|PF=
(1),(3,5),(2),(4);
(6,9),(7),(8);
001
- - 4 5
010
6 7 8 9
(10),(11),(12); (13),(14),(15),(16)
101 10 - 11 12
13 14 15 16
111
P(V) = (1,6 ; 10,13 ; 2,7 ; 14 ; 3,8 ; 4,11,15 ; 9;5,12,16)
00 0110 11
"G
"
" = 1,6,9,14; 3,5,8,12, 16; 2,7,10,13;4,11,15
"
(1) (3,5) (2) (4)
3,8
1,6 2,7 4,11,15
I
T
P
9
5,12,16
10,13
W
14
ZPT
24
PRZYKA
AD c.d.  tablice dla UMA i ROM
x1
q1 q2
x2
G
g1
g2
q3
REJESTR
H
q1 q2 q3
I
T
P
W
ZPT
25
PRZYKA
AD c.d.  tablice dla UMA i ROM
x1x2
q3 x1 x2 g1 g2
00
01 11 10
q1q2q3
0 0 0 0 0
1,6
000
1 2 3 -
0
1 0 0 1
10,13
001
- - 4 5
0
2,7 0 0 1 1
010
6 7 8 9
101 10 - 11 12
13 14 15 16
111
P(V) = (1,6 ; 10,13 ; 2,7 ; 14 ; 3,8 ; 4,11,15 ; 9;5,12,16)
00 0110 11
"G
"
"
"
= 1,6,9,14; 3,5,8,12, 16; 2,7,10,13;4,11,15
I
T
P
W
ZPT
26
PRZYKA
AD c.d.  tablice dla UMA i ROM
x1x2
00 q1 q2 g1 g2 q1 q2 q3
01 11 10
q1q2q3 I1 I2 I3 I4
000
1 2 3 - 0 0 0 0 0 0 0
S1 S2 S4 -
1
001
- - 4 5 - - S5 S4
1 0 1
0 0 0 1
3,5
010
6 7 8 9 S3 S2 S1 S3
0 0 1
0 0 1 0
2
S2 - S4 S1
101 10 - 11 12
S3 S1 S4 S2
13 14 15 16
111
(
=
P(U)
1,2,3,4,5; 6,7,8,9; 13,14,15,16)
10, 11,12;
00 0110 11
"G
"
"
"
= 1,6,9,14; 3,5,8,12, 16; 2,7,10,13;4,11,15
I
T
P
&
P(U) " G =
" 
" 
" 
1; 3,5 ; 2
W
ZPT
27
Jeszcze inna struktura (najlepsza)
U= {q1,q2, x1 }
V= {q3, x2 }
x1x2
q1 q2 q3
00 01 11 10
I1 I2 I3 I4
S1 0 0 0
1 2 3 -
S1 S1 S2 S4 -
- - 4 5
S2 0 0 1
S2 - - S5 S4
6 7 8 9
S3 S3 S2 S1 S3
S3 0 1 1
10 - 11 12
S4 S2 - S4 S1
S4 1 0 1
13 14 15 16
S5 S3 S1 S4 S2
S5 1 1 0
P(U) = (1,2 ; 3,4,5 ; 6,7 ; 8,9 ; ...
I
T
P
P(V) = (1,13, 16 ; 2,3, 14,15 ....)
W
ZPT
28
PRZYKA
ADOWE BENCHMARKI
TEST Wejścia Wyjścia Stany
d14 3 5 7
cse 7 7 16
ex4 6 9 14
mark1 5 16 15
s1 8 6 20
tbk 6 3 32
sse 7 7 16
I
T
P
W
ZPT
29
IMPLEMENTACJA AUTOMATU
WUKA
ADZIE EPF 10K10
AM
ROM
FF implementation
implementation
Benchmark Implementation
#LCs
#bits
#LCs #bits
d14 512 60 21 256
1)
cse 22528 92 2 5632
1)
ex4 13312 28 2 3328
mark1 10240 1) 40 2 5120
1)
s1 24576 137 96 5632
2)
tbk 16384 1) 759 333 4093
1)
sse 22528 52 3 5632
1) Implementation not possible  not enough memory recourses
2) Implementation not possible  not enough CLB recourses
I
T
P
W
ZPT
30
ODWZOROWANIE UKA
ADU TBK
tbk: 16 384 bitów tbk: 4093 bitów
lub 759 komórek log. oraz 333 komórek log.
tbk
tbk
6144 bits 6144 bits
EPF10K EPF10K
576 LCs 576 LCs
I
Po dekompozycji
Przed dekompozycjÄ…
T
P
W
ZPT
31