Politecnico di Milano
STUDIO DI METODOLOGIE DI SINTESI
DI ALTO LIVELLO PER LA
REALIZZAZIONE DI UN
SINTETIZZATORE AUTOMATICO DA
INTEGRARE NEL PROGETTO PANDA
Relatore: Prof. Fabrizio FERRANDI
Correlatore: Ing. Marco Domenico SANTAMBROGIO
Francesco Redaelli MATRICOLA 656188
Davide Sacchi MATRICOLA 656975
Francesco Redaelli - Davide Sacchi
Sommario
Obiettivi
PANDA
Introduzione alla sintesi di alto livello
Tecnologie di sintesi:
Diagrammi ASM
Sintetizzatore SPARK
Grafi SDG
Caso di studio:
Algoritmo Kernighan-Lin
Risultati e Confronto
Conclusioni e sviluppi futuri
2
Francesco Redaelli - Davide Sacchi
Obiettivi
 Analisi di due metodi di sintesi di alto livello
esistenti: tramite ASM e tramite SPARK
 Introduzione di un nuovo metodo basato sugli
SDG come rappresentazione formale
 Confronto dei metodi di sintesi di alto livello
3
Francesco Redaelli - Davide Sacchi
PANDA
HLS
4
HW/SW Codesign
DRESD
Francesco Redaelli - Davide Sacchi
CERBERO
Sintesi di alto livello
“High-level synthesis is the process of mapping a
behavioral description at the algorithmic level to a
structural description in terms of functional units,
memory elements and interconnections”
Sabih H. Gerez,
“Algorithms for VLSI Design Automation”
while (TRUE) {
switch (state) {
case S0:
x = a + b;
state = S1;
next;
case S1:
...
}
}
5
Allocazione
risorse
Assegnamento
risorse
Schedulazione
sync: process begin
wait until CLOCK’event and CLOCK=‘1’;
state <= state_next;
end process sync;
ciclo: process begin
case state is
when S0 =>
out1 <= a + c;
state_next <= S1;
...
end process ciclo;
Francesco Redaelli - Davide Sacchi
Diagrammi ASM (1)
DESCRIZIONE IN
LINGUAGGIO C
Posizioni
possibili
per il nome
REALIZZAZIONE
DEL DIAGRAMMA
ASM
State Box
S1
S1
Zx
Condition
Box
FALSE
CONDIZIONE
Output
Box
TRUE
Condizione
di test
Zx
6
Uscite
asserite
Uscite
asserite
Francesco Redaelli - Davide Sacchi
Diagrammi ASM (2)
TRADUZIONE
DEL DIAGRAMMA A
BLOCCHI IN VHDL
INDIVIDUAZIONE
DEGLI STATI
CASE stato_presente IS
WHEN "10" =>
if( j<ndiv2 ) then
Operazioni stato 10
if (B[j*2 + 1] = 0) then
stato_presente <= "11";
else
stato_presente <= "13";
end if;
else
stato_presente <= "14";
end if;
WHEN "11" =>
Operazioni stato 11
if( max < maxp ) then
stato_presente <= "12";
else
stato_presente <= "13";
end if;
WHEN "12" =>
Operazioni stato 12
stato_presente <= "13";
WHEN "13" =>
j <= j+1;
stato_presente <= "14“;
end case;
7
Francesco Redaelli - Davide Sacchi
Sintetizzatore Spark
8
Francesco Redaelli - Davide Sacchi
Grafi SDG (1)
Scheduling
CASE stato IS
…
WHEN A =>
Operazioni stato A
WHEN B =>
Operazioni stato B
WHEN C =>
Operazioni stato C
…
end case;
9
Francesco Redaelli - Davide Sacchi
Grafi SDG (2)
Entry
W1
S1
S1 W1
10
S6
S5
S6
S5
S2
W2
S2
W2
T
T
S3
S3
S4
S4
if (clk'event AND clk = '1') then
CASE stato_presente IS
WHEN x"00" =>
i <= 0;
k <= 0;
stato_presente <= x"01";
WHEN x"01" =>
ind18 <= Dv(i) + Dv(k + ndiv2);
iA <= i;
iB <= k;
Mk <= M(A(i * 2)*n + B(k * 2)) * 2;
if(A((i * 2) + 1) > 0) then
i <= i+1;
S7
S7
end if;
if (B((k * 2) + 1) > 0) then
k <= k+1;
end if;
if ((A((i * 2) + 1) > 0) and (B((k * 2) + 1)>0)) then
stato_presente <= x"01";
else
stato_presente <= x“02";
end if;
WHEN x“02" =>
max <= ind18 - Mk;
stato_presente <= x"11";
end CASE;
end if;
Francesco Redaelli - Davide Sacchi
Algoritmo Kernighan-Lin
A
B
2
2
a
b
3
c
I a  vA Cav
d
5
e
f
Ea  vB Cav
Da  Ea  I a
g xy  Dx  D y  2C xy
D x  Dx  2C xa  2C xd
'
11
Francesco Redaelli - Davide Sacchi
Risultati e Confronto (1)
Metodo
f(MHz)
Cp(ns)
LUT
SLC
Stati
Transizioni
ASM O
ASM
SDG O
SDG
SPARK
62.160
61.949
210.013
99.856
200.423
16.087
16.142
4.762
10.014
4.989
429
734
445
757
525
237
407
240
419
341
10
10
16
11
14
15
15
21
16
18
Risultati ottenuti attraverso ISE
12
Francesco Redaelli - Davide Sacchi
I
O
5 9
5 9
5 15
5 20
4 14
Occupazione
Spazio (%)
5
8
5
8
5
Risultati e Confronto (2)
Metodo
f(MHz)
Cp(ns)
LUT
ASM O
101.430
9.859
395
ASM
101.276
9.874
474
SDG O
266.667
3.750
250
SDG
235.516
4.246
554
SPARK
280.741
3.562
514
Risultati ottenuti attraverso
Synplify Pro
13
Francesco Redaelli - Davide Sacchi
Risultati e Confronto (3)
Metodo
Cicli
Tempo ISE(ms)
Tempo Synplify(ms)
ASM O
445
7.16
4.39
ASM
445
7.18
4.39
SDG O
865
4.12
3.24
SDG
545
5.46
2.31
SPARK
876
4.37
3.12
Confronto tempistiche di
simulazione
14
Francesco Redaelli - Davide Sacchi
Conclusioni e sviluppi futuri
HLS
15
Modulo di sintesi di alto livello
HW/SW Codesign
DRESD
CERBERO
basato su SDG
Francesco Redaelli - Davide Sacchi
Fine Presentazione
• Domande
16
Francesco Redaelli - Davide Sacchi