Ricerca Operativa

Claudio Arbib

Università di L’Aquila

Ricerca Operativa

Layout ottimo di dispositivi elettronici ad altissima scala di integrazione

Problema

Realizzare una funzione booleana f: {0, 1}ⁿ → {0, 1}^m

tramite una matrice logica programmabile (PLA)

Esempio

f = x + y

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110 000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110 0000

0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

f₃ = (x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (¬x₁ ∧ x₂ ∧ ¬y₁ ∧ y₂)

∨ (x₁ ∧ x₂ ∧ ¬y₁ ∧ y₂)

∨ (x₁ ∧ ¬x₂ ∧ y₁ ∧ y₂)

∨ (¬x₁ ∧ x₂ ∧ y₁ ∧ y₂)

∨ (x₁ ∧ x₂ ∧ y₁ ∧ y₂)

000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110 000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110

Esempio

f₃ = (x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (¬x₁ ∧ x₂ ∧ ¬y₁ ∧ y₂)

∨ (x₁ ∧ x₂ ∧ ¬y₁ ∧ y₂)

∨ (x₁ ∧ ¬x₂ ∧ y₁ ∧ y₂)

∨ (¬x₁ ∧ x₂ ∧ y₁ ∧ y₂)

∨ (x₁ ∧ x₂ ∧ y₁ ∧ y₂)

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110 000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110

Esempio

f₃ = (x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (x₂ ∧ ¬y₁ ∧ y₂)

∨ (x₁ ∧ ¬x₂ ∧ y₁ ∧ y₂)

∨ (x₂ ∧ y₁ ∧ y₂)

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110 000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110

Esempio

f₃ = (x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (x₂ ∧ ¬y₁ ∧ y₂)

∨ (x₁ ∧ ¬x₂ ∧ y₁ ∧ y₂)

∨ (x₂ ∧ y₁ ∧ y₂)

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110 000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110 0000

0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110 000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110

f₁ = (x₁ ∧ ¬y₁ ∧ ¬y₂)

∨ (¬x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (x₁ ∧ ¬y₁ ∧ y₂)

∨ (¬x₁ ∧ y₁ ∧ y₂)

Esempio

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110 000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110

f₁ = (x₁ ∧ ¬y₁ ∧ ¬y₂)

∨ (¬x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (x₁ ∧ ¬y₁ ∧ y₂)

∨ (¬x₁ ∧ y₁ ∧ y₂)

f₃ = (x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (x₂ ∧ ¬y₁ ∧ y₂)

∨ (x₁ ∧ ¬x₂ ∧ y₁ ∧ y₂)

∨ (x₂ ∧ y₁ ∧ y₂)

Esempio

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111

000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110 000 001 010 011 001 010 011 100 010 011 100 101 011 100 101 110

f₁ = (x₁ ∧ ¬y₁)

∨ (¬x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (¬x₁ ∧ y₁ ∧ y₂)

f₃ = (x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (x₂ ∧ ¬y₁ ∧ y₂)

∨ (x₁ ∧ ¬x₂ ∧ y₁ ∧ y₂)

∨ (x₂ ∧ y₁ ∧ y₂)

Esempio

Piano OR Piano OR Piano AND Piano AND x

y

s

f f₁ = (x₁ ∧ ¬y₁)

∨ (¬x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (¬x₁ ∧ y₁ ∧ y₂)

f₃ = (x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (x₂ ∧ ¬y₁ ∧ y₂)

∨ (x₁ ∧ ¬x₂ ∧ y₁ ∧ y₂)

∨ (x₂ ∧ y₁ ∧ y₂)

Esempio

x₁ y₁ x₂ y₂

f₃ f₁

s₁ s₂ s₃ s₄ s₅ s₆ s₇ f₁ = (x₁ ∧ ¬y₁)

∨ (¬x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (¬x₁ ∧ y₁ ∧ y₂)

f₃ = (x₁ ∧ x₂ ∧ y₁ ∧ ¬y₂)

∨ (x₂ ∧ ¬y₁ ∧ y₂)

∨ (x₁ ∧ ¬x₂ ∧ y₁ ∧ y₂)

∨ (x₂ ∧ y₁ ∧ y₂)

Esempio

x₁ y₁ x₂ y₂

f₃ f₁

s₁ s₂ s₃ s₄ s₅ s₆ s₇

Esempio

x₁ y₁ x₂ y₂

f₃ f₁

s₁ s₂ s₃ s₄ s₅ s₆ s₇

Riduzione dell’area del dispositivo x₁ y₁ x₂ y₂

f₃

f₁ s₁ s₂ s₃ s₄ s₅ s₆ s₇

Segnali (righe) compatibili

Partizionare le colonne in due insiemi C₁, C₂ in modo da massimizzare il più piccolo tra gli insiemi di righe

A, con solo elementi in C₁ A

Segnali (righe) compatibili

Partizionare le colonne in due insiemi C₁, C₂ in modo da massimizzare il più piccolo tra gli insiemi di righe

A, con solo elementi in C₁ A

B

Segnali (righe) compatibili

Partizionare le colonne in due insiemi C₁, C₂ in modo da massimizzare il più piccolo tra gli insiemi di righe

A, con solo elementi in C₁ B

A

Segnali (righe) compatibili

Segnali (righe) compatibili

Grafo di compatibilità

1

2

3

4

5

6

7

8

3 5

6

Problema (folding semplice): 7

Dato un grafo G, trovare un sottografo isomorfo a K_m,m con m massimo.

1 2 3 4 5 6 7 8

Riduzione dell’area Riduzione dell’area

Una diversa tecnica di folding

Partizionare le colonne in due insiemi C₁, C₂ in modo da massimizzare il più piccolo tra gli insiemi di righe

A, con solo elementi in C₁

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 folding

1 2 3 4 5 6 7 8 9 10 11 12 13 14 12 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

Una diversa tecnica di folding

Riduzione dell’area Riduzione 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.