IL PROBLEMA DEL LAYOUT DELLE TOPOLOGIE DI...

IL PROBLEMA DEL LAYOUT DELLE TOPOLOGIE DI INTERCONNESSIONE

OVVERO IL DISEGNO ORTOGONALE SU GRIGLIA

Prof. Tiziana Calamoneri

Corso di Algoritmi per le reti

A.A. 2010/11

Il modello di Thompson

IL MODELLO DI THOMPSON (1)

Il problema del layout di topologie di interconnessione nasce dal problema di stampare circuiti VLSI (Very Large Scale Integration) su un supporto di silicio.

Esso ebbe origine negli anni ’40, ma ha ottenuto un significativo studio solo in tempi relativamente recenti, quando la tecnologia ha consentito di stampare circuiti in due e tre dimensioni a prezzi ragionevoli

3


Due esempi di circuiti stampati:

4

Intel 2004 Intel Pentium


Se modelliamo il circuito con un grafo, c’è una stretta relazione tra la stampa del circuito ed il disegno del grafo.

La tecnologia di produzione VLSI impone molti vincoli al layout; in particolare, bisogna tenere conto:

che la macchina che traccia i fili può solo approssimare segmenti obliqui con sequenze di segmenti orizzontali e verticali (⇒disegno ortogonale);

… 5


… che per evitare interferenze bisogna garantire che i fili siano ad una certa distanza l’uno dall’altro (problema della risoluzione ⇒disegno su griglia);

che i fili non si possono incrociare; per evitare gli incroci si possono far viaggiare i fili uno su una faccia e uno sull’altra, introducendo dei “buchi” per permettere il passaggio dei fili da una faccia all’altra; il numero di tali fori deve comunque essere contenuto poiché il costo di realizzazione è elevato (⇒minimizzazione degli incroci)

…

6


…che, di tutto il processo di produzione, il materiale è la cosa più costosa; per questo motivo è necessario che il layout abbia area minima (⇒minimizzazione dell’area).

… che i fili non devono essere troppo lunghi in quanto il ritardo di propagazione è proporzionale alla loro lunghezza e che, in caso di struttura a livelli, i fili dello stesso livello dovrebbero avere approssimati-vamente la stessa lunghezza, in modo da evitare problemi di sincronizzazione (⇒minimizzazione della lunghezza degli archi).

7


Thompson ha introdotto un modello consistente con tutti questi vincoli:

i l layout di una topologia G è una rappresentazione su un insieme di tracce orizzontali e verticali a distanza unitaria l’una dall’altra che mappa:

8


i nodi del grafo nei punti di intersezione delle tracce,

gli archi del grafo in percorsi disgiunti costituiti da segmenti di tracce orizzontali e verticali; tali percorsi non possono intersecare nodi a loro non adiacenti e possono avere intersezioni tra loro solo in corrispondenza degli incroci;

non sono permesse sovrapposizioni, non sono permessi incroci arco-nodo, non sono permessi “knock-knees”

9

DISEGNO ORTOGONALE DI GRAFI

DISEGNO ORTOGONALE DI GRAFI (1)

DEF. Un disegno ortogonale su griglia di un grafo G=(V,E) è una funzione biunivoca che mappa vertici v ∈ V in punti a coordinate intere Γ(v) ed archi (v,w) ∈ E in cammini che non si sovrappongono tali che le immagini dei loro estremi Γ(v) e Γ(w) siano connesse dai cammini corrispondenti. Tali cammini sono costituiti da segmenti orizzontali o verticali con le eventuali svolte a coordinate intere.

DEF. Un disegno ortogonale è su griglia se tutti i suoi oggetti (nodi, segmenti di arco, svolte) sono a coordinate intere.

N.B. Possibile visualizzare solo grafi con grado ≤ 4! 11

Dunque, il layout è un disegno ortogonale su griglia per cui si richiede la minimizzazione dell’area, del numero di incroci e della lunghezza degli archi.

Usiamo gli algoritmi noti nell’area del GRAPH DRAWING per disegnare in modo ortogonale su griglia un grafo?

12


Questa tecnica non funziona in modo soddisfacente: gli algoritmi per disegnare grafi garantiscono certe limitazioni delle funzioni di ottimizzazione per OGNI grafo dato in input che soddisfi i requisiti necessari; le topologie di interconnessione, però sono grafi con forte struttura (tipicamente regolari, molto simmetriche, con proprietà ricorsive, …) e, sfruttando queste proprietà, si possono ottenere risultati migliori.

13


Gli algoritmi per disegnare grafi prendono in input un grafo e lo disegnano

Gli algoritmi per il layout sono progettati per una peculiare topologia di interconnessione e, perciò, ne prendono in input la dimensione.

N.B. L’ottimizzazione al meglio delle funzioni di ottimizzazione (in special modo l’area), anche nelle costanti, è un obiettivo assai più importante che nel caso di disegni di grafi per quanto già osservato: se un layout viene fatto nella metà dell’area rispetto ad un altro, il suo costo sarà dimezzato!

14


LAYOUT DELLA BUTTERFLY

LA BUTTERFLY (MEMORANDUM)

Def. Sia N=2n (e quindi n=log N); una Butterfly n-dimensionale è un grafo livellato con N (n+1) nodi (n+1 livelli ognuno con 2n nodi) e 2Nn archi, i cui nodi sono etichettati con una coppia (w, i), dove i è il livello del nodo e w è un numero binario di n bit che indica la riga del nodo.

Due nodi (w, i) e (w’, i’) sono adiacenti se e solo se i’=i+1 e:

w=w’ (straight edge) o w e w’ differiscono esattamente

nell’i-esimo bit (cross edge). 16

LAYOUT DI WISE (1)

Layout proposto da D.S.Wise (‘81)

17

LAYOUT DI WISE (2)

Questo layout ha una proprietà che è molto richiesta per una topologia livellata:

ha tutti i fili di uno stesso livello della stessa lunghezza,

tuttavia la lunghezza cresce esponen-zialmente con il livello

18

LAYOUT DI WISE (3)

la lunghezza di ogni cammino da un input ad un output è lineare in N (esattamente 2(N-1)). Infatti: consideriamo per semplicità il percorso dal nodo

più in alto a sinistra a quello più in basso a destra la lunghezza di questo cammino può essere

calcolata come la diagonale di un quadrato di lato √2 (N-1)

la lunghezza di tale cammino è quindi uguale a 2(N-1).

19

LAYOUT DI WISE (4)

Il layout è formato da due strati, stampati sulle due facce della lastra di silicio; su uno si trovano le linee che vanno da in alto a sinistra a in basso a destra (linee rosse), sull’altro si trovano i fili che vanno da in alto a sinistra a in basso a destra (linee nere), si può pensare a questi due strati come alle due facce della lastra di supporto.

20

LAYOUT DI WISE (5)

Vantaggi: Area buona: √2 (N-1) × √2 (N-1)= 2N2+o(N2) lunghezza dei fili costante su ogni livello; questo

non è vero in ogni layout: nel disegno classico della butterfly, ad esempio, sull’ultimo livello, gli straight-edges hanno lunghezza unitaria, mentre i cross-edges hanno lunghezza lineare in N; questa è una proprietà estremamente negativa perché si perde il sincronismo del flusso delle informazioni;

i nodi di input ed output giacciono sul contorno, che può essere richiesto da alcune applicazioni.

21

LAYOUT DI WISE (6)

Svantaggi: linee “slanted”, quindi l’area misurata non è quella del

rettangolo con lati paralleli agli assi cartesiani, ma con i lati a 45°; seguendo la definizione standard di area essa risulta 2(N-1) × 2(N-1)= 4N2+o(N2), infatti il quadrato circoscritto al layout con lati paralleli alle linee della griglia ha lato di lunghezza pari al cammino dal nodo più in alto a sinistra a quello più in basso a destra e cioè 2(N-1);

… 22

LAYOUT DI WISE (7)

Svantaggi (segue): … non è un layout ‘pulito’, poiché i “knock-knees”

non vengono evitati ma sistemati con dei dispositivi che, oltre tutto, non hanno area nulla, quindi il loro inserimento causa un peggioramento delle dimensioni del layout;

per ottenere il layout proposto bisogna permutare l’ordine dei nodi

23

LAYOUT DI EVEN E EVEN (1)

Layout presentato da Even e Even (‘00), basato sulla nozione di Layered Cross Product

Def. Un grafo livellato con l+1 livelli G=(V0, V1, …, Vl, E) consiste di l+1 livelli di nodi; Vi è l’insieme (non vuoto) di nodi di livello i; E è l’insieme degli archi: ogni arco (u,v) connette due nodi di livelli adiacenti, cioè, se u è al livello i allora v è al livello i+1.

24


Def. (Even & Litman ‘92) Il Layered Cross Product (LCP) di due grafi livellati di l+1 livelli, G1=(V0

1, V11,

…, Vl1, E1) e G2=(V0

2, V12, …, Vl

2, E2), è un grafo livellato con l+1 livelli G=(V0, V1, …, Vl, E) tale che:

per ogni i=0, …, l, Vi = Vi1×Vi

2 (ogni livello è il prodotto cartesiano dei livelli dei grafi fattore);

esiste un arco (u,v) che connette i nodi (u1,u2) e (v1,v2) se e solo se (u1,v1) ed (u2,v2) sono archi dei grafi fattori.

25


Even e Litman hanno dimo-strato che molte topologie di interconnessione ben note sono il risultato del prodotto di semplici grafi livellati come gli alberi.

In particolare, la butterfly è il LCP di due alberi binari completi uno con la radice posta in alto, l’altro con la radice posta in basso.

26

Esempi di LCP


Metodo di proiezione: Siano G1 e G2 due grafi livellati di l+1 livelli e sia G

il loro LCP. Un disegno bidimensionale di G si ottiene nel modo seguente:

27


Metodo di proiezione (segue): Considera lo spazio cartesiano xyz; Disegna sul piano xy il grafo G1 e sul piano yz il grafo

G2 in modo tale che la coordinata y di ogni nodo di livello i sia uguale a i, le altre coordinate siano interi;

…

28

LAYOUT DI EVEN E EVEN (6) Metodo di proiezione (segue): … Costruisci un disegno 3D di G come segue: se u∈Vi

1 è disegnato alle coordinate (xu, i, 0) e v∈Vi

2 è disegnato alle coordinate (0, i, zv), allora le coordinate del nodo (u,v) sono (xu, i, zv), cioè i nodi di G sono i punti di intersezione delle rette perpendicolari al piano xy passanti per i nodi di G1 e delle rette perpendicolari al piano yz passanti per i nodi di G2.

Il disegno 2D di G si ottiene proiettando il disegno 3D sul piano xz

29


Oss. Si può evitare di passare per la rappresentazione 3D, infatti i nodi del LCP coincidono con le intersezioni dei prolungamenti sul piano xz delle proiezioni dei nodi di livello i di G1 sull’asse x e dei nodi di livello i di G2 sull’asse z per i=0,…,l

30


Il metodo di proiezione può produrre rappre-sentazioni che non rispettano i vincoli dettati dal layout di topologie, ad esempio il disegno costruito pur essendo su griglia non è ortogonale.

Analizziamo i diversi tipi di archi risultanti dall’LCP; ciò ci permetterà di imporre le condizioni necessarie e sufficienti affinché il metodo di proiezione produca archi che corrono lungo le linee della griglia, nodi mappati in punti distinti della griglia e archi che non si sovrappongono. 31

LAYOUT DI EVEN E EVEN (9) Ci sono quattro tipi di archi nel grafo prodotto G:

1. il prodotto di due archi obliqui dà come risultato un arco obliquo;

2. il prodotto di un arco verticale ed uno obliquo dà come risultato un arco verticale;

3. il prodotto di un arco obliquo ed uno verticale dà come risultato un arco orizzontale;

4. il prodotto di due archi verticali mappa due nodi distinti in uno stesso punto della griglia.

32


Per ottenere un layout ammissibile tramite il metodo di proiezione bisogna imporre che non ci siano archi generati dal prodotto di due archi obliqui o di due archi verticali . Più precisamente, possiamo formalizzare al modo seguente:

1. Il metodo di proiezione genera un layout di G i cui archi giacciono su linee della griglia se e solo se i disegni di G1 e G2 soddisfano la seguente condizione: per ciascun arco di G, esattamente uno dei suoi fattori è obliquo.

Questa affermazione previene anche le sovrapposizioni di nodi nell’ambito di ciascun livello.

33


E’ necessario imporre anche che nodi di diversi livelli non si sovrappongono. Per fare questo, è sufficiente che sia verificata la seguente affermazione:

2. Il metodo di proiezione genera un layout di G in cui al più un nodo è mappato su ogni punto della griglia se e solo se, per ogni i=0, 1, …, l, gli insiemi {(xu, zv): u ∈ Vi

1 e v ∈ Vi2} sono disgiunti.

34

LAYOUT DI EVEN E EVEN (12) Si considerino ora due archi obliqui (a,b) e (c,d) in G1;

i quattro nodi a, b, c, d, hanno coordinate: nodo a: (xa, i, 0); nodo b: (xb, i+1, 0); nodo c: (xc, j, 0); nodo d: (xd, j+1, 0).

I due archi si dicono consistenti se e solo se gli intervalli aperti (xa, xb) e (xc, xd) sono disgiunti.

35


3. Il metodo di proiezione genera un layout di G in cui nessun arco di griglia viene usato due volte se e solo se per ogni coppia di archi inconsistenti in G1 (G2):

i due archi non sono sullo stesso livello e sui due livelli su cui si trovano non esistono due archi

co-lineari in G2 (G1)

36


Affinché il metodo di proiezione produca un layout ammissibile del grafo G dobbiamo quindi disegnare i due grafi fattori in modo che siano rispettate le tre affermazioni enunciate.

Vediamole una per una: 1. Il metodo di proiezione genera un layout di G i cui

archi giacciono su linee della griglia se e solo se i disegni di G1 e G2 soddisfano la seguente condizione: per ciascun arco di G, esattamente uno dei suoi fattori è obliquo.

37


Introduciamo nel disegno dei due grafi fattori dei nodi e degli archi fittizi in modo tale che:

ogni arco sia spezzato in due archi uno obliquo e uno verticale;

nel disegno di G1 gli archi obliqui siano nei livelli dispari e quelli verticali nei livelli pari;

nel disegno di G2 gli archi obliqui siano nei

livelli pari e quelli verticali nei livelli dispari.

38


In questo modo viene simulata la creazione delle svolte.

39


2. Il metodo di proiezione genera un layout di G in cui al più un nodo è mappato su ogni punto della griglia se e solo se, per ogni i=0, 1, …, l, gli insiemi {(xu, zv): u ∈ Vi

1 e v ∈ Vi2} sono disgiunti.

Bisogna fare in modo che non ci siano due nodi, esclusi gli estremi di un arco verticale, nel disegno di ciascun fattore, che condividano la stessa coordinata; questo è sempre possibile allargando opportunamente il disegno.

40


3. Il metodo di proiezione genera un layout di G in cui nessun arco di griglia viene usato due volte se e solo se per ogni coppia di archi inconsistenti in G1 (G2):

i due archi non sono sullo stesso livello e sui due livelli su cui si trovano non esistono due

archi co-lineari in G2 (G1) Molto difficile in caso di grafi qualsiasi (collo di

bottiglia di questo metodo). Nel caso della butterfly comunque, questo può essere fatto.

41


42


Otteniamo il layout della n-butterfly come prodotto di due alberi binari completi di n+1 livelli, uno con la radice sul primo livello e l’altro con la radice sull’ultimo livello come segue: nel disegno dell’albero binario, aggiungere i nodi

fittizi ed assegnare ad ogni nodo una colonna per evitare collisioni di nodi;

disegnare un albero sul piano xy, l’altro sul piano yz;

(opzionale) costruire il LCP in 3D; proiettare il LCP sul piano xz. 43


Il layout così ottenuto ha le seguenti proprietà: è simmetrico; ha altezza H=2(N-1); ha ampiezza W=2(N-1); ha area 4N2+o(N2); i nodi di input e output non sono sui bordi

(proprietà negativa…) tutti gli archi di ciascun livello hanno la stessa

lunghezza 44

RAFFRONTO DELLE TECNICHE WISE - PRO:

area relativamente bassa “sembrare” una butterfly nodi di input/ output sul bordo

WISE - CONTRO: knok-knees griglia “slanted”

EVEN & EVEN - PRO: elimina i difetti

EVEN & EVEN - CONTRO: aumenta l’area pone i nodi di input/output all’interno del disegno

45

Nell’ottica di ottimizzare al meglio l’area, sono stati proposti altri latyouts della butterfly: Dinitz [’98] dimostra che il layout di Even ed Even

può essere migliorato, con degli aggiustamenti locali in modo da avere un’area pari a 11/6 N2+o(N2)

Successivamente, Avior et al. [’98] dimostrano che un layout con rettangolo circoscritto a lati paralleli agli assi cartesiani non può avere area minore di N2 + o(N2) e forniscono un algoritmo che produce un layout di area ottima

46

ALTRI RISULTATI (1)

Dinitz et al. [’99] dimostrano infine che, se si accetta che il layout possa avere rettangolo circoscritto con i lati non necessariamente paralleli agli assi (cioè ‘slanted’), allora area 1/2 N2+o(N2) è necessaria e sufficiente

Questi lavori chiudono la problematica del layout di area ottima della Butterfly.

47

ALTRI RISULTATI (2)

IL PROBLEMA DEL LAYOUT DELLE TOPOLOGIE DI...

Documents

Transcript of IL PROBLEMA DEL LAYOUT DELLE TOPOLOGIE DI...