Relazione laboratorio pasd

Progetto Automatico dei Sistemi Digitali

Anno Accademico 2009/2010

TECHNOLOGY MAPPING IN SIS:

Effetto degli script rugged, boolean e algebraic sulla rete technology dependent

Studenti: Sferrazza Giovanni

Docente: Prof. Favalli Michele

Corso: Progetto Automatico dei Sistemi Digitali



INTRODUZIONE:

Il progetto di un sistema digitale può essere affrontato a diversi livelli di astrazione: idealmente, si può considerare un completo flusso di progettazione di tipo top-down che parte cioè dal livello di astrazione più elevato per giungere a quello fisico. Ad ogni passaggio, da un livello al successivo, corrisponde un’ operazione di sintesi che non è solo una trasformazione da un livello ad un altro, ma comporta anche un’ eventuale modifica o aggiunta delle informazioni, cosa che è possibile vedere come la trasformazione da una specifica (iniziale o intermedia) a un’ implementazione (completa o intermedia). Nel corso del passaggio si compiono delle scelte (ad es, il tipo di “forma” logica scelta, la famiglia di porte logiche, le fasi di ottimizzazione e le relative scelte di merito) che corrispondono ad altrettanti incrementi di informazione. Durante la nostra esperienza di laboratorio ci siamo focalizzati sul passaggio dal livello logico technology independent a quello technology dependent, cercando una correlazione tra i due livelli e come questa incida su un eventuale fattore di merito. Visto lo scopo puramente didattico di tale esperienza, abbiamo assunto l’area come unico fattore di merito della rete technology dependent, trascurando altri possibili fattori quali ad esempio il ritardo, il consumo di potenza e la collaudabilità, ci siamo quindi concentrati sulle variazioni dell’area in funzione dei diversi modelli utilizzati per descrivere la rete technlogy independent. Per eseguire la sintesi dal livello logico technology independent ci siamo avvalsi del programma SIS dell’Università di Berkeley, applicato ad un campione di 15 benchmark, della libreria LGSynth89, con dimensioni ( intese come costo in termini di letterali) che spaziano da 256 a 7412, in modo tale da poter generalizzare il più possibile i risultati ottenuti, evitando quindi di cadere in una sottoclasse di circuiti. Su tutti i benchmark sono stati applicati gli script: boolean, algebraic e rugged, ottenedo 3 ottimizzazioni diverse per ogni circuito, e successivamente è stata eseguita l’operazione di mapping con la libreria tecnologica mcnc.genlib. Da notare che gli script sono stati eseguiti una sola volta sul singolo circuito, in quanto non siamo interessati a valutare l’efficacia del singolo script ma bensì all’effetto che hanno le ottimizzazioni eseguite al livello logico technology independent sul livello di astrazione sottostante. Di seguito sono riportati i dati raccolti durante le fasi precedentemente illustrate.



NAME Function In Out Gates

no script

no mapno script

maprugged no map

rugged map

boolean no map

boolean map

algebraic no map

algebraic map

9symml Count Ones 9 1 43“ nodi 43 117 18 102 19 128 58 122“ letterali sop 277 393 234 307 285 380 267 380“letterali fact 277 351 286 270 234 344 267 331“ area 351 270 344 332“ fan in medio 4,98 4,33 6,63 4,28

f51m Arithmetic 8 8 43“ nodi 8 78 16 58 14 73 44 76“ letterali sop 319 253 125 162 178 222 159 220“letterali fact 169 213 98 140 131 190 159 191“ area 213 141 190 192“ fan in medio 4,5 3,53 5,44 3,36

C432Priority

Decoder 36 7 160“ nodi 160 151 52 133 53 130 62 133“ letterali sop 372 395 331 303 347 370 252 372“letterali fact 372 363 205 286 240 317 252 323“ area 363 289 326 332“ fan in medio 2,1 3,44 3,49 3,39

C880 Control 60 26 383“ nodi 357 230 79 227 70 214 116 233“ letterali sop 703 733 467 684 488 678 473 749“letterali fact 703 576 415 563 427 570 473 590“ area 599 581 586 606“ fan in medio 1,9 3,32 3,64 3,28

C1355 Error Correcting41 32 546“ nodi 514 544 162 244 162 222 174 294“ letterali sop 1032 1069 560 770 560 685 670 791“letterali fact 1032 1069 552 634 554 612 670 790“ area 1096 689 705 823“ fan in medio 1,95 4,28 2,1 2,55

C2670 ALU and Control233 140 1193“ nodi 1161 541 162 370 159 372 206 407“ letterali sop 2043 1573 866 1269 999 1220 840 1393“letterali fact 2043 1412 732 942 761 942 840 1041“ area 1412 974 974 1064“ fan in medio 1,71 2,41 2,42 2,04


C5315 Selector 178 123 2307“ nodi 2290 1257 380 876 367 915 512 977“ letterali sop 4369 3609 1857 2815 1964 2915 2008 3051“letterali fact 4369 3329 1734 2228 1786 2317 2008 2473“ area 3363 2287 2361 2509“ fan in medio 1,9 2,43 3,43 3,01

Multi-Level Examples



C6288 16-bit Multiplier 32 32 2406“ nodi 2416 2341 934 1862 932 1684 1416 1723“ letterali sop 4800 4722 3348 4674 3555 4501 3787 2536“letterali fact 4800 4693 3295 4419 3494 4246 3787 4094“ area 4723 4631 4457 4304“ fan in medio 1,99 2,6 2,81 2,65


des Data Encription 256 245 4000“ nodi 681 2612 590 1887 533 1938 745 1974“ letterali sop 7412 9393 3638 5055 4093 5381 3816 5353“letterali fact 6101 8003 3472 4781 3590 4989 3816 5045“ area 8003 4881 5040 5138“ fan in medio 5,51 3,62 3,74 3,74

rot Logic 135 107 691“ nodi 138 452 167 448 156 452 242 451“ letterali sop 1424 1151 854 1036 938 1110 803 1106“letterali fact 764 1079 671 955 716 1016 803 1013“ area 1090 965 1026 1024“ fan in medio 3,03 3,27 3,69 2,96

b9 Logic 41 21 125“ nodi 117 86 32 86 26 86 46 79“ letterali sop 256 220 169 194 197 196 140 181“letterali fact 236 207 125 184 124 186 140 174“ area 208 190 190 176“ fan in medio 2,02 3,5 4,04 2,9

apex6 Logic 135 99 452“ nodi 238 485 147 444 147 436 210 476“ letterali sop 904 1234 819 1093 896 1197 854 1190“letterali fact 904 1151 741 1036 771 1060 854 1121“ area 1163 1043 1077 1127“ fan in medio 3,59 4,33 4,52 3,79

apex7 Logic 49 37 176“ nodi 58 171 65 150 58 147 86 165“ letterali sop 351 436 266 347 289 359 286 401“letterali fact 289 404 245 330 248 337 286 365“ area 407 332 338 369“ fan in medio 4,32 3,38 3,83 3,08



ANALISI DEI DATI:

In primo luogo, abbiamo focalizzato la nostra attenzione al parametro di merito più significativo per questo livello d’astrazione, ovvero il numero di letterali, essendo quest’ultimo direttamente imputabile sul costo della rete finale, valutata in termini di area. Il successivo grafico mostra come i singoli script, per ogni circuito, abbiano ottimizzato il numero di letterali in funzione della dimensione iniziale della rete.

Per rappresentare tutti i punti è stata utilizzata una scala logaritmica per entrambi gli assi.

Osservando il grafico, si nota come, eccetto qualche circuito, lo script algebraic sia quello che ha ridotto maggiormente il numero di letterali mentre lo script che ha dato risultati peggiori sia stato il boolean, resta poi lo script rugged che ha fornito risultati intermedi. Utilizzare un diverso script, in realtà comporta l’assunzione di un diverso modello matematico per descrivere, e quindi anche per manipolare, la rete. Il modello matematico che meglio si presta a rappresentare una generica rete combinatoria è l’algebra booleana, tuttavia negli strumenti CAD questo modello tende ad essere sostituito a favore di quello algebrico a causa dell’eccessivo carico computazionale che ne impedisce una efficace manipolazione. Di fatto sfruttare una rappresentazione di funzioni booleane mediante espressioni algebriche comporta la perdita di alcune proprietà tipiche dell’algebra booleana, tra cui le condizioni d’indifferenza, a favore di una più facile verificabilità delle proprietà, cosa che si ripercuote positivamente sull’efficienza dell’ottimizzazione, giustificando oltretutto il grafico precedentemente esposto. Notoriamente efficace, è l’utilizzo di un livello d’ astrazione intermedio ai due precedentemente esposti, implementato in SIS tramite lo script rugged.



Bisogna comunque tenere in considerazione altri fattori che direttamente o indirettamente incidono sull’area del circuito technology dependent, quali fan-in e numero di nodi della rete technology independent. Il successivo grafico mostra l’andamento del numero di nodi ottenuti con ogni script, al variare della dimensione dei circuiti.

Si vuole ricordare che lo scopo degli script è quello di minimizzare il numero di letterali, ovviamente alterando anche il numero di nodi; vediamo infatti come quest’ultimo sia drasticamente diminuito dopo l’applicazione di uno qualsiasi degli script, questo perché il generico script per ridurre il costo della rete sfrutta il fan-out. Non verrà preso in considerazione il fan-out per via della difficoltà a stimarlo, ciò nonostante non significa che sia un fattore marginale nel determinare l’efficienza del mapping. Un ulteriore parametro significativo è il fan-in medio poiché è indice della dimensione dei singoli nodi; nel seguente grafico si osserva per ogni script l’andamento del fan-in in funzione del numero di letterali del circuito di partenza.



Nonostante il grafico a prima vista risulti confusionario, si può osservare un aumento del fan-in per qualunque script; accentuato nel caso del boolean mentre è di entità minore nel caso dell’algebraic. Da questa breve analisi, si evince che lo script algebraic minimizza il numero di letterali più degli altri, ottenendo anche un numero di nodi maggiore con un fan-in medio minore, cosa che intuitivamente ci farebbe attendere anche un circuito migliore, in termini di area, dopo il mapping, sempre se le nostre considerazioni non siano state troppo semplicistiche. Tenendo presente i dati ottenuti per le reti technology independent, ci accingiamo ad eseguire l’analisi delle reti technology dependent, ottenute a partire dalle precedenti mediante l’operazione di mapping. In questo nuovo livello d’astrazione il parametro di merito più importante è indiscutibilmente l’area, ed è proprio quest’ultima che è graficata di seguito in funzione di alcuni parametri tipici del livello technology independent, al fine di comprendere al meglio la correlazione tra i due livelli.

Il grafico cui sopra mostra l’andamento dell’area in funzione del numero di letterali iniziali del circuito, e diversamente da quello che ci saremmo aspettati, mostra come un circuito al quale è stato prima applicato lo script rugged e successivamente è stato eseguito il mapping, risulta avere un minor costo in termini di area, anche se questo nella fase intermedia non presentava enormi vantaggi in termini di numero di letterali. Nel grafico successivo in cui è presente l’andamento dell’area in funzione del numero di letterali ottenuto per ogni script, si evidenzia come non sempre aver raggiunto un numero minore di letterali con un certo script comporta un effettivo vantaggio per l’area.



I 3 punti all’interno dello stesso cerchietto, sono lo stesso circuito sintetizzato con script diversi

Al fine di scoprire il fenomeno al quale imputare il comportamento inaspettato appena illustrato, ci siamo cimentati a tracciare i due seguenti grafici, in cui si relaziona l’aera sia al numero di nodi che al fan-in medio dei circuiti sintetizzati con i diversi script.

Sebbene il fan-in sia un indice della dimensione dei singoli nodi, e quindi anche di quanto risulti efficace l’operazione di mapping, relazionandolo con l’aerea non ci fornisce informazioni significative.



I 3 punti all’interno dello stesso cerchietto, sono lo stesso circuito sintetizzato con script diversi

Anche da questo grafico non ci sono informazioni rilevanti, a parità di letterali, avere un numero maggiore di nodi con un fan-in medio più basso, dovrebbe rappresentare la situazione migliore per il mapping, ma valutando il costo in termini di area non risulta così. Visto che la dipendenza area-letterali risulta la più forte, ci siamo focalizzati a comprendere in che misura l’operazione di mapping modifica la scomposizione del circuito trovata dopo la minimizzazione, al fine di eseguire il matching con gli elementi della libreria.



Il precedente grafico mostra l’andamento del numero di letterali sia della rete technology independent sia di quella dependent. Essendo di fatto più interessati all’incremento del numero di letterali a causa del mapping, il seguente grafico risulta più significativo.

Si vede che lo script che comporta un maggiore incremento del numero dei letterali durante l’operazione di mapping è l’algebraic CONCLUSIONI:

Dal punto di vista della rete technology independent la rete con minor costo sembra essere quella ottenuta attraverso lo script algebraic, tuttavia restituisce una rete che molto meno, rispetto le altre due, si presta ad essere mappata, rendendola quella peggiore in termini di area. Durante l’operazione di mapping tecnologico, come più volte è stato ribadito, la rete iniziale viene modificata per permettere il matching con gli elementi di libreria, in quanto questi introducono anche nuovi limiti progettuali ( basti pensare ad esempio ai limiti imposti sul massimo fan-in e fan-out ), modifica che comporta un costo in termini di letterali e che si traduce direttamente in un costo inteso come area. Ecco che sfruttare in maniera intensiva il fan-out al fine di ridurre il numero di letterali, genera circuiti in cui i coni della rete sono poco disgiunti, andando a gravare sul mapping oltre che su un’eventuale collaudo; logicamente si deduce che il fan-out deve essere sfruttato fin tanto che gli oneri del mapping rimangono contenuti, ed è proprio in virtù di questo nuovo ragionamento che il rugged risulta il migliore. Sebbene questa sia solo un’esperienza di laboratorio può essere tratta come spunto per ulteriori indagini, ad esempio rimane da verificare, la dipendenza dell’area con il fan-out, oppure l’utilizzo di diverse librerie e cosa non meno importante sarebbe tener conto anche dei vincoli sui ritardi.

This work is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

Relazione laboratorio pasd

Education

Transcript of Relazione laboratorio pasd