Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf ·...

Claudio ArbibUniversità di L’Aquila

Ricerca Operativa

Layout ottimo di dispositivi elettronici ad altissima scala di integrazione

PDF created with pdfFactory Pro trial version www.pdffactory.com

http://www.pdffactory.com

Problema

Realizzare una funzione booleana

f: {0, 1}n → {0, 1}m

tramite una matrice logica programmabile (PLA)



Esempio

f = x + y

0000000100100011010001010110011110001001101010111100110111101111

0000000100100011010001010110011110001001101010111100110111101111

000001010011001010011100010011100101011100101110

000001010011001010011100010011100101011100101110

0000000100100011010001010110011110001001101010111100110111101111

0000000100100011010001010110011110001001101010111100110111101111

f3 = (x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (¬x1 ∧ x2 ∧ ¬y1 ∧ y2) ∨ (x1 ∧ x2 ∧ ¬y1 ∧ y2)∨ (x1 ∧ ¬x2 ∧ y1 ∧ y2) ∨ (¬x1 ∧ x2 ∧ y1 ∧ y2) ∨ (x1 ∧ x2 ∧ y1 ∧ y2)

000001010011001010011100010011100101011100101110

000001010011001010011100010011100101011100101110



Esempio

f3 = (x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (¬x1 ∧ x2 ∧ ¬y1 ∧ y2) ∨ (x1 ∧ x2 ∧ ¬y1 ∧ y2) ∨ (x1 ∧ ¬x2 ∧ y1 ∧ y2) ∨ (¬x1 ∧ x2 ∧ y1 ∧ y2) ∨ (x1 ∧ x2 ∧ y1 ∧ y2)

0000000100100011010001010110011110001001101010111100110111101111

0000000100100011010001010110011110001001101010111100110111101111

000001010011001010011100010011100101011100101110

000001010011001010011100010011100101011100101110



Esempio

f3 = (x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (x2 ∧ ¬y1 ∧ y2) ∨ (x1 ∧ ¬x2 ∧ y1 ∧ y2) ∨ (x2 ∧ y1 ∧ y2)

0000000100100011010001010110011110001001101010111100110111101111

0000000100100011010001010110011110001001101010111100110111101111

000001010011001010011100010011100101011100101110

000001010011001010011100010011100101011100101110



Esempio


0000000100100011010001010110011110001001101010111100110111101111

0000000100100011010001010110011110001001101010111100110111101111

000001010011001010011100010011100101011100101110

000001010011001010011100010011100101011100101110

0000000100100011010001010110011110001001101010111100110111101111

0000000100100011010001010110011110001001101010111100110111101111

000001010011001010011100010011100101011100101110

000001010011001010011100010011100101011100101110

f1 = (x1 ∧ ¬y1 ∧ ¬y2)∨ (¬x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (x1 ∧ ¬y1 ∧ y2) ∨ (¬x1 ∧ y1 ∧ y2)



Esempio0000000100100011010001010110011110001001101010111100110111101111

0000000100100011010001010110011110001001101010111100110111101111

000001010011001010011100010011100101011100101110

000001010011001010011100010011100101011100101110

f1 = (x1 ∧ ¬y1 ∧ ¬y2)∨ (¬x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (x1 ∧ ¬y1 ∧ y2) ∨ (¬x1 ∧ y1 ∧ y2)




Esempio0000000100100011010001010110011110001001101010111100110111101111

0000000100100011010001010110011110001001101010111100110111101111

000001010011001010011100010011100101011100101110

000001010011001010011100010011100101011100101110

f1 = (x1 ∧ ¬y1)∨ (¬x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (¬x1 ∧ y1 ∧ y2)




Esempio

Piano ORPiano OR

Piano ANDPiano ANDx

y

s

f

f1 = (x1 ∧ ¬y1)∨ (¬x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (¬x1 ∧ y1 ∧ y2)




Esempio

x1

y1

x2

y2

f3

f1

s1 s2 s3 s4 s5 s6 s7

f1 = (x1 ∧ ¬y1)∨ (¬x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (¬x1 ∧ y1 ∧ y2)




Esempio

x1

y1

x2

y2

f3

f1

s1 s2 s3 s4 s5 s6 s7



Esempio

x1

y1

x2

y2

f3 f1

s1 s2 s3 s4 s5 s6 s7

Riduzione dell’area del dispositivotramite Folding

x1

y1

x2

y2

f3

f1

s1 s2 s3 s4 s5 s6 s7



Segnali (righe) compatibili

Partizionare le colonne in due insiemi C1, C2 in modo damassimizzare il più piccolo tra gli insiemi di righe

A, con solo elementi in C1B, con solo elementi in C2

A






A

B






B

A



Grafo di compatibilità

1

2

3

4

5

6

7

8

3

5

6

7Problema (folding semplice): Dato un grafo G, trovare un sottografo isomorfo a Km,m con m massimo.

12345678



Riduzione dell’areaRiduzione dell’area

Una diversa tecnica di folding



La riga verde e quella bianca sono compatibili, ma la partizione di colonne scelta non consente di sfruttare questo fatto per ridurre ulteriormente l’area. Un risultato migliore di quello ottenuto mediante folding semplice si può ottenere permutando le colonne e interrompendo la traccia sulle righe a livelli differenti



Una diversa tecnica di folding1 2 3 4 5 6 7 8 9 10 11 12 13 1412 9 1 7 2 3 13 8 5 4 6 10 11 14



12 9 1 7 2 3 13 8 5 4 6 10 11 14




Riduzione dell’areaRiduzione dell’area

12 9 1 7 2 3 13 8 5 4 6 10 11 14


Siamo riusciti in questo modo a compattare ulteriormente il dispositivo. In termini di grafo di compatibilità il problema però non è più quello di individuare un sottografo bipartito completo e bilanciato.



Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf ·...

Documents

Transcript of Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf ·...