Co uzyskaliśmy do tej pory...
Jaka jest
skuteczność..
.
I
T
P
W
ZPT
1
Przykład...
.type fr
.i 10
.o 1
Synteza układów cyfrowych str. 32
.p 25
0010111010 0
1010010100 0
0100011110 0
1011101011 0
1100010011 0 Redukcja argumentów pozwoli
0100010110 0
obliczyć
ć, że funkcja ta
ć
ć
1110100110 0
0100110000 0
jest zależna od
0101000010 0
0111111011 1
0000010100 1
1101110011 1
0100100000 1
7 argumentów!
0100011111 1
0010000110 1
1111010001 1
1111101001 1
X = {x3, x5, x6, x7, x8, x9, x10}
1111111111 1
0010000000 1
1101100111 1
I
0010001111 1
T
1111100010 1
P
1010111101 1
W
0110000110 1
0100111000 1
ZPT
.e
2
Ustalenie zbiorów A i B
X = {x3, x5, x6, x7, x8, x9, x10}
A = {x7, x8, x9} B = {x3, x5, x6, x10}
x3 x5 x6 x10
x3 x5 x6 x10
G
x7 x8 x9
G
x7 x8 x9
H
H
I
T
P
f
W
f
Więcej wyjść z bloku G???
ZPT
3
Realizacja w strukturze FPGA
x3 x5 x6 x10
x3 x5 x6 x10
G
G
x7 x8 x9
x7 x8 x9
H
H
f
f
3 najwyżej 4 komórki 4/1
2 komórki 4/1
I
T
P
W
ZPT
4
Ta sama funkcja w systemie Altery
.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
realizuje tę
0100100000 1 MAX+PLUSII
0100011111 1
funkcję na
0010000110 1
1111010001 1
1111101001 1
1111111111 1
0010000000 1
1101100111 1
I
23 komórkach !!!
0010001111 1
T
1111100010 1
P
1010111101 1
W
0110000110 1
0100111000 1
ZPT
.e
5
Niestety bezpośrednie zastosowanie
dekompozycji funkcjonalnej w
komputerowych systemach
projektowania jest  ze względu na
ogromną złożoność obliczeniową 
bardzo trudne
Oprogramowanie uniwersyteckie:
SIS (Berkeley) oferuje metodę balansu procedur minimalizacji i dekompozycji
Nasza propozycja polega na zastosowaniu wspomagającej procedury
dekompozycji równoległej
I
T
P
W
ZPT
6
Dekompozycja równoległa
YG
XG X
G
YG YH= Y
Y
X
F
YH
X X
H
H
U
YG YH = Ś
I
T
P
W
ZPT
7
Dekompozycja równoległa - przykład
y1: {x1, x4}, {x4, x5}
x1 x2 x3 x4 x5 x6 y1 y2 y3 y4
1 0 1 0 0 0 1 0 0 0 -
y2: {x2, x3, x5}
2 1 0 0 0 1 1 0 0 1 -
y3: {x1, x4}
3 1 1 0 1 1 1 1 1 1 0
4 1 1 0 1 0 0 - 0 1 1
y4: {x2, x5}, {x5, x6}, {x1, x6},
5 1 1 1 1 1 1 1 0 - 0
6 0 0 1 0 1 1 - 0 0 -
7 0 1 1 0 0 1 0 1 - 0
8 1 0 1 1 1 0 1 - 1 1
9 1 0 0 1 1 0 1 0 - 1
G= {y1, y3} H= {y2, y4}
10 0 1 1 1 0 1 0 1 1 1
I
Xg = {x1, x4} Xh ={x2, x3, x5}
T
P
W
ZPT
8
Dekompozycja równoległa - przykład
c.d.
x1 x2 x3 x4 x5 x6
H
G
y1 y3
y2 y4
I
T
P
W
ZPT
9
Algorytmy dekompozycji
Szeregowa
Równoległa
X
X
A B
G
H
G
H
Yg
Yh
Y
I
T
P
W
ZPT
10
Zrównoważona dekompozycja funkcjonalna
X
Metoda polegająca na wykonywaniu
Metoda polegająca na wykonywaniu
na przemian dekompozycji szeregowej
na przemian dekompozycji szeregowej
i równoległej, zgodnie z przyjętą strategią.
i równoległej, zgodnie z przyjętą strategią.
F
Zastosowana w procedurze DEMAIN
Zastosowana w procedurze DEMAIN
Y
X X
X2
X3 X4
G
X1
A B H
I
T
P
W
Y
Y1
Y2
ZPT
Dekompozycja równoległa Dekompozycja szeregowa
Dekompozycja równoległa Dekompozycja szeregowa
11
Jak dekomponuje Demain
START
DANE
g
:= cin
DECYZJA
in
DEKOMPOZYCJA
UŻYTKOWNIKA
gout
:= cout
RÓWNOLEGA
A
DEKOMP OZYCJA
SZEREGOWA
ta k
nie
n < c
ISTNIEJ E ?
in
nie
ta k
ZMIANA LICZBY
WEJ ŚĆ/WYJ ŚĆ
KONIEC
I
BLOKU G
T
P
W
ZPT
12
Decyzje użytkownika
The H table under consideration has 10 inputs and 2 outputs
Serial decomposition is suggested with G function parameters
assumed to be equal to the declared cell parameters
Do you prefer parallel decomposition ?: p
OR continue serial decomposition as suggested ?: s
OR continue serial decomposition with changed parameters ?: c c
n wejśc
no. of block inputs= n
G
no. of block outputs= m
m wyjść
H
I
T
P
W
Opcja c umożliwia również redukcję argumentów
ZPT
13
Jak obliczyć najlepszą dekompozycję
.type fr
.i 10
.o 1
.p 25
1) Zredukować argumenty
0010111010 0
1010010100 0
(zastosować opcję c)
0100011110 0
1011101011 0
1100010011 0
0100010110 0
2) Zastosować dekompozycję szeregową
1110100110 0
(opcja s)
0100110000 0
0101000010 0
x3 x5 x6 x10
0111111011 1
0000010100 1
1101110011 1
0100100000 1
G
x7 x8 x9
0100011111 1
0010000110 1
1111010001 1
1111101001 1
1111111111 1
H
0010000000 1
1101100111 1
I
0010001111 1
T
1111100010 1
f
P
1010111101 1
W
Opis w książce Synteza układów
0110000110 1
0100111000 1
ZPT
cyfrowych, przykład 3.8, str. 108
.e
14
Przykład z Synteza układów cyfrowych str 32
.type fr
.i 10
.o 1
.p 25
Demain 2 komórki LUT
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
MAX+PLUSII
1111111111 1
0010000000 1
1101100111 1
I
0010001111 1
T
23 komórki LUT
1111100010 1
P
1010111101 1
W
0110000110 1
0100111000 1
ZPT
.e
15
Inny przykład  benchmark BUL (SUC przykład 3.9)
.type fr
.i 10
.o 2
.p 25
0101000000 00
1110100100 00
0010110000 01
0101001000 01
Układ kombinacyjny
1110101101 10
0100010101 10
1100010001 00
0011101110 10
x0
0001001110 10
0110000110 10
x2
1110110010 01
y0 0111100000 00
x3
0100011011 00
0010111010 10
0110001110 00
UK
y1 0110110111 11
0001001011 11
1110001110 01
x9
0011001011 01
0010011010 10
I
1010110010 00
T
0100110101 11
P
0001111010 00
W
1101100100 01
1001110111 11
ZPT
.e
16
Specyfikacja AHDL
SUBDESIGN bul
SUBDESIGN bul
(
(
i[1..10] : INPUT;
i[1..10] : INPUT;
o[1..2] : OUTPUT;
o[1..2] : OUTPUT;
)
)
BEGIN
BEGIN
TABLE
TABLE
(i[1..10]) => (o[1..2]);
(i[1..10]) => (o[1..2]);
B"0101000000" => B"00";
B"0101000000" => B"00";
B"1110100100" => B"00";
B"1110100100" => B"00";
B"0010110000" => B"10";
B"0010110000" => B"10";
B"0101001000" => B"10";
B"0101001000" => B"10";
B"1110101101" => B"01";
B"1110101101" => B"01";
B"0100010101" => B"01";
B"0100010101" => B"01";
B"1100010001" => B"00";
B"1100010001" => B"00";
B"0011101110" => B"01";
B"0011101110" => B"01";
B"0001001110" => B"01";
B"0001001110" => B"01";
B"0110000110" => B"01";
B"0110000110" => B"01";
B"1110110010" => B"10";
B"1110110010" => B"10";
B"0111100000" => B"00";
B"0111100000" => B"00";
B"0100011011" => B"00";
B"0100011011" => B"00";
B"0010111010" => B"01";
B"0010111010" => B"01";
MAX+PLUSII
B"0110001110" => B"00";
B"0110001110" => B"00";
B"0110110111" => B"11";
B"0110110111" => B"11";
B"0001001011" => B"11";
B"0001001011" => B"11";
B"1110001110" => B"10";
B"1110001110" => B"10";
B"0011001011" => B"10";
B"0011001011" => B"10";
AHDL: 35 komórek
B"0010011010" => B"01";
B"0010011010" => B"01";
B"1010110010" => B"00";
B"1010110010" => B"00";
B"0100110101" => B"11";
B"0100110101" => B"11";
LUT
B"0001111010" => B"00";
B"0001111010" => B"00";
B"1101100100" => B"10";
B"1101100100" => B"10";
B"1001110111" => B"11";
B"1001110111" => B"11";
I
END TABLE;
END TABLE;
T
P
END;
END;
W
ZPT
17
Fragment raportu MAX+PLUSII
Project Information d:\maxplus2\work\bul.rpt
MAX+plus II Compiler Report File
Version 10.2 07/10/2002
Compiled: 04/18/2004 15:57:42
***** Project compilation was successful
Converted from PLA file: bul
** DEVICE SUMMARY **
Chip/ Input Output Bidir Memory Memory LCs
POF Device Pins Pins Pins Bits % Utilized LCs % Utilized
bul EPF10K10LC84-3 10 2 0 0 0 % 35 6 %
User Pins: 10 2 0
Device-Specific Information: d:\maxplus2\work\bul.rpt
bul
***** Logic for device 'bul' compiled without errors.
Device: EPF10K10LC84-3
I
T
P
W
ZPT
18
Specyfikacja VHDL
library IEEE;
library IEEE;
use IEEE.STD_LOGIC_1164.all;
use IEEE.STD_LOGIC_1164.all;
entity bul is
entity bul is
port(i : in std_logic_vector(1 to 10);
port(i : in std_logic_vector(1 to 10);
o : out std_logic_vector(1 to 2));
o : out std_logic_vector(1 to 2));
end bul;
end bul;
architecture arch1 of bul is
architecture arch1 of bul is
begin
begin
PLA: process(i)
PLA: process(i)
begin
begin
case i is
case i is
when "0101000000" => o <= "00";
when "0101000000" => o <= "00";
when "1110100100" => o <= "00";
when "1110100100" => o <= "00";
when "0010110000" => o <= "10";
when "0010110000" => o <= "10";
when "0101001000" => o <= "10";
when "0101001000" => o <= "10";
when "1110101101" => o <= "01";
when "1110101101" => o <= "01";
when "0100010101" => o <= "01";
when "0100010101" => o <= "01";
when "1100010001" => o <= "00";
when "1100010001" => o <= "00";
when "0011101110" => o <= "01";
when "0011101110" => o <= "01";
when "0001001110" => o <= "01";
when "0001001110" => o <= "01";
when "0110000110" => o <= "01";
when "0110000110" => o <= "01";
MAX+PLUSII
when "1110110010" => o <= "10";
when "1110110010" => o <= "10";
when "0111100000" => o <= "00";
when "0111100000" => o <= "00";
when "0100011011" => o <= "00";
when "0100011011" => o <= "00";
when "0010111010" => o <= "01";
when "0010111010" => o <= "01";
when "0110001110" => o <= "00";
when "0110001110" => o <= "00";
when "0110110111" => o <= "11";
when "0110110111" => o <= "11";
VHDL: 67 komórek
when "0001001011" => o <= "11";
when "0001001011" => o <= "11";
when "1110001110" => o <= "10";
when "1110001110" => o <= "10";
when "0011001011" => o <= "10";
when "0011001011" => o <= "10";
LUT
when "0010011010" => o <= "01";
when "0010011010" => o <= "01";
when "1010110010" => o <= "00";
when "1010110010" => o <= "00";
when "0100110101" => o <= "11";
when "0100110101" => o <= "11";
I
when "0001111010" => o <= "00";
when "0001111010" => o <= "00";
T
when "1101100100" => o <= "10";
when "1101100100" => o <= "10";
P when "1001110111" => o <= "11";
when "1001110111" => o <= "11";
when others => o <= "XX";
when others => o <= "XX";
W
end case;
end case;
end process;
end process;
end;
end;
ZPT
19
Przykład
(Leonardo Spectrum)
.type fr
.i 10
.o 2
.p 25
0101000000 00
1110100100 00
0010110000 01
0101001000 01
1110101101 10
0100010101 10
1100010001 00
0011101110 10
0001001110 10
0110000110 10
1110110010 01
0111100000 00
0100011011 00
Leonardo Spectrum
0010111010 10
0110001110 00
0110110111 11
0001001011 11
1110001110 01
96 komórek LUT
0011001011 01
0010011010 10
I
1010110010 00
T
0100110101 11
P
0001111010 00
W
1101100100 01
1001110111 11
ZPT
.e
20
Zagadka
.type fr
.i 10
.o 2
.p 25
0101000000 00
1110100100 00
0010110000 01
0101001000 01
1110101101 10
0100010101 10
Ile komórekLUT
4 komórki LUT ?
Demain
1100010001 00
0011101110 10
0001001110 10
0110000110 10 7 0 1 2 6
0 1 3
1110110010 01
0111100000 00
0100011011 00
G1 G2
4 6 1 7 9
0010111010 10
0110001110 00
0110110111 11
H1
H2
0001001011 11
1110001110 01
0011001011 01
y0 y1
0010011010 10
I
1010110010 00
T
0100110101 11
P
0001111010 00
W
1101100100 01
1001110111 11
ZPT
.e
21
Jak osi
gnąć najlepszy wynik


Wynik Demaina silnie zależy od strategii syntezy
tzn. kolejności wykonywania dekompozycji
szeregowej i równoległej
Duże znaczenie ma dekompozycja
nierozłączna
I
T
P
W
ZPT
22
Dekompozycja funkcji BUL
Najpierw równoległa póz
niej szeregowa
7 6
0 1 3 0 1 2
G1 G2
4 6 1 7 9
H1
H2
y0 y1
I
T
Liczba zajętych komórek: 4
P
W
ZPT
23
Dekompozycja funkcji BUL wg innej
strategii syntezy
Najpierw szeregowa póz
niej równoległa
a)
8 9 1 3 4 6 0 2 5 7
(4/1) (4/2)
2 4
0 3
1
0 1 2 4 0 1 2 3 4
c)
b)
(4/1) (4/2)
I
(3/1)
y0
T
P
W
y1
Liczba zajętych komórek: 7
ZPT
24
Przyczyna wad systemów komercyjnych
Library of gates
Komórka LUT struktur FPGA
x1
x2
LUT
x3
y
x4
y = f(x1, x2, x3, x4) !!!
I
T
P
W
ZPT
25