claudio arbib universitàdi l’aquilans.di.univaq.it/~oil/didattica/corsi/ro1/layoutvlsi.pdf ·...
TRANSCRIPT
![Page 1: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/1.jpg)
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
![Page 2: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/2.jpg)
Problema
Realizzare una funzione booleana
f: {0, 1}n → {0, 1}m
tramite una matrice logica programmabile (PLA)
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 3: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/3.jpg)
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
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 4: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/4.jpg)
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
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 5: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/5.jpg)
Esempio
f3 = (x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (x2 ∧ ¬y1 ∧ y2) ∨ (x1 ∧ ¬x2 ∧ y1 ∧ y2) ∨ (x2 ∧ y1 ∧ y2)
0000000100100011010001010110011110001001101010111100110111101111
0000000100100011010001010110011110001001101010111100110111101111
000001010011001010011100010011100101011100101110
000001010011001010011100010011100101011100101110
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 6: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/6.jpg)
Esempio
f3 = (x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (x2 ∧ ¬y1 ∧ y2) ∨ (x1 ∧ ¬x2 ∧ y1 ∧ y2) ∨ (x2 ∧ y1 ∧ y2)
0000000100100011010001010110011110001001101010111100110111101111
0000000100100011010001010110011110001001101010111100110111101111
000001010011001010011100010011100101011100101110
000001010011001010011100010011100101011100101110
0000000100100011010001010110011110001001101010111100110111101111
0000000100100011010001010110011110001001101010111100110111101111
000001010011001010011100010011100101011100101110
000001010011001010011100010011100101011100101110
f1 = (x1 ∧ ¬y1 ∧ ¬y2)∨ (¬x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (x1 ∧ ¬y1 ∧ y2) ∨ (¬x1 ∧ y1 ∧ y2)
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 7: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/7.jpg)
Esempio0000000100100011010001010110011110001001101010111100110111101111
0000000100100011010001010110011110001001101010111100110111101111
000001010011001010011100010011100101011100101110
000001010011001010011100010011100101011100101110
f1 = (x1 ∧ ¬y1 ∧ ¬y2)∨ (¬x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (x1 ∧ ¬y1 ∧ y2) ∨ (¬x1 ∧ y1 ∧ y2)
f3 = (x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (x2 ∧ ¬y1 ∧ y2) ∨ (x1 ∧ ¬x2 ∧ y1 ∧ y2) ∨ (x2 ∧ y1 ∧ y2)
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 8: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/8.jpg)
Esempio0000000100100011010001010110011110001001101010111100110111101111
0000000100100011010001010110011110001001101010111100110111101111
000001010011001010011100010011100101011100101110
000001010011001010011100010011100101011100101110
f1 = (x1 ∧ ¬y1)∨ (¬x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (¬x1 ∧ y1 ∧ y2)
f3 = (x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (x2 ∧ ¬y1 ∧ y2) ∨ (x1 ∧ ¬x2 ∧ y1 ∧ y2) ∨ (x2 ∧ y1 ∧ y2)
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 9: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/9.jpg)
Esempio
Piano ORPiano OR
Piano ANDPiano ANDx
y
s
f
f1 = (x1 ∧ ¬y1)∨ (¬x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (¬x1 ∧ y1 ∧ y2)
f3 = (x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (x2 ∧ ¬y1 ∧ y2) ∨ (x1 ∧ ¬x2 ∧ y1 ∧ y2) ∨ (x2 ∧ y1 ∧ y2)
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 10: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/10.jpg)
Esempio
x1
y1
x2
y2
f3
f1
s1 s2 s3 s4 s5 s6 s7
f1 = (x1 ∧ ¬y1)∨ (¬x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (¬x1 ∧ y1 ∧ y2)
f3 = (x1 ∧ x2 ∧ y1 ∧ ¬y2) ∨ (x2 ∧ ¬y1 ∧ y2) ∨ (x1 ∧ ¬x2 ∧ y1 ∧ y2) ∨ (x2 ∧ y1 ∧ y2)
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 11: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/11.jpg)
Esempio
x1
y1
x2
y2
f3
f1
s1 s2 s3 s4 s5 s6 s7
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 12: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/12.jpg)
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
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 13: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/13.jpg)
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
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 14: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/14.jpg)
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
B
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 15: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/15.jpg)
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
B
A
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 16: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/16.jpg)
Segnali (righe) compatibili
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 17: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/17.jpg)
Segnali (righe) compatibili
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 18: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/18.jpg)
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
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 19: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/19.jpg)
Riduzione dell’areaRiduzione dell’area
Una diversa tecnica di folding
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
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
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 20: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/20.jpg)
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
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 21: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/21.jpg)
12 9 1 7 2 3 13 8 5 4 6 10 11 14
Una diversa tecnica di folding
PDF created with pdfFactory Pro trial version www.pdffactory.com
![Page 22: Claudio Arbib Universitàdi L’Aquilans.di.univaq.it/~oil/didattica/corsi/ro1/LayoutVLSI.pdf · Claudio Arbib Universitàdi L’Aquila Ricerca Operativa Layout ottimo di dispositivi](https://reader031.vdocumenti.com/reader031/viewer/2022022016/5b7734c17f8b9ad2498c3a3d/html5/thumbnails/22.jpg)
Riduzione dell’areaRiduzione dell’area
12 9 1 7 2 3 13 8 5 4 6 10 11 14
Una diversa tecnica di folding
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.
PDF created with pdfFactory Pro trial version www.pdffactory.com