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

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

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

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

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

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

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

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

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

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

Esempio

x1

y1

x2

y2

f3

f1

s1 s2 s3 s4 s5 s6 s7

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

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

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

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

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

Segnali (righe) compatibili

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

Segnali (righe) compatibili

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

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

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

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

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

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