Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Lifting e generazione di disuguaglianze per il politopo delle matrici “Consecutive Ones”

Tesi di Laurea Magistrale

Facoltà: Scienze Matematiche, Fisiche e Naturali

Autore: Francesco Zaccaria Contatta »

Composta da 139 pagine.

 

Questa tesi ha raggiunto 130 click dal 09/09/2016.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.

 

 

Estratto della Tesi di Francesco Zaccaria

Mostra/Nascondi contenuto.
1.1. PROBLEMI DI SEQUENZIAMENTO 7 A B C D E 1 2 3 4 5 6 7 (a) A B C D E 1 2 3 4 5 6 7 (b) A B C D E 1 2 3 4 5 6 7 (c) Figura 1.1: Esempio di gate matrix con 7 porte e 5 reti: posizione dei transistor sulle porte (a), connessione dei transistor tramite fili metallici (b) e tracce necessarie (c). 1.1.2 Gate Matrix Layout Problem (GMLP) Nella progettazione di alcune tipologie di circuiti elettronici con la tecno- logia VLSI [27] i pattern sono costituiti da sequenze di porte, o gates, da connettere per formare circuiti, con un’elevata integrazione di transistor ed elemeti circuitali in ogni singolo chip. Il problema Gate Matrix Lay- out Problem (GMLP) consiste nel cercare una permutazione della dispo- sizione delle porte che minimizzi i costi di connessione, sotto restrizioni sull’area del circuito. Più specificatamente, il problema consiste nel realizzare un circuito elettronico VLSI conn porte (gates) da connettere avendo a disposizione m reti (nets): si possono descrivere le porte come fili verticali e le reti come fili orizzontali. Per realizzare il circuito sono richieste delle connes- sioni, ottenute collegando tra loro dei transistor (situati all’intersezione fra fili verticali e orizzontali) che siano allineati orizzontalmente, tramite dei fili metallici. Un esempio di questa situazione, tratto da [7], è illu- strato in Figura 1.1: in questa istanza si hanno sette porte da mettere in comunicazione attaraverso cinque reti, le quali collegano i transistor evidenziati agli incroci. Per eseguire il collegamento può risultare neces- sario intersecare altre porte prive di transistor nella rete: tale esigenza dipende dalla sequenza scelta per le porte stesse. In questo contesto un primo obiettivo che si vuole ottenere è quello di minimizzare la lunghezza totale del filo metallico utilizzato per collegare i transistor, in modo da ridurre il costo di connessione: tale funzione obiettivo è equivalente al TOS precedentemente introdotto per il proble- ma MOSP. Un altro aspetto applicativo da tenere in considerazione è il fatto che, dopo aver collegato i transistor, si hanno delle sovrapposizioni dei fili su ciasuna porta: il massimo numero di tali sovrapposizioni è det- to il numero di tracce necessarie a connettere tutto il circuito. Al fine di limitare l’area del circuito, per motivi di miniaturizzazione, si considera allora come vincolo un upper bound al numero di tracce necessarie, la quale è equivalente al MOS introdotto nel Problema 1. Anche in questo problema, come nel MOSP, il valore della funzione
Estratto dalla tesi: Lifting e generazione di disuguaglianze per il politopo delle matrici “Consecutive Ones”