Transcript PERCOLATION AND ROBUST COMPUTATION

Nanoscale Digital Computation
Through Percolation
Mustafa Altun
Electrical and Computer Engineering
University of Minnesota
DAC, “Wild and Crazy Ideas” Session ─ San Francisco, July 29, 2009
Non-Linearities
signal out
From vacuum tubes, to transistors, to carbon nanotubes,
the basis of digital computation is a robust non-linearity.
Holy Grail
signal in
2
Randomness at the Nanoscale
General Characteristics of
Nanoscale Circuits:




Self-assembled topologies.
High density of bits/
logic/interconnects.
High defect and failure rates.
Inherent randomness in both
interconnects and signal values.
Probabilistic FET-like connections
in a stochastically assembled
nanowire array.
3
Nanoscale Computation through Percolation

Given: Physical structures
exhibiting randomness.

Want: Robust digital
computation.

“WACI” idea:
Exploit the mathematics of
percolation.
Percolation Theory
Random
Graphs
Probability of global connectivity
Rich mathematical topic that forms the basis of explanations
of physical phenomena such as diffusion and phase changes
in materials.
1.0
0.8
Sharp non-linearity in
global connectivity as
a function of random
local connectivity.
0.6
0.4
0.2
0.0
0.0
0.2
0.4
0.6
0.8
1.0
Probability of local connectivity
Broadbent & Hammersley (1957); Kesten (1982); and Grimmett (1999).
Percolation Theory
Poisson distribution of points with density
λ
Points are connected if their distance is less than
2r
D
S
Study probability
of connected
components
6
Percolation Theory
There is a phase transition at a critical node density value.
signal in
Nanowire crossbar arrays
TOP
LEFT
RIGHT
BOTTOM
INSULATOR
METAL
signal out
V-Applied
Suppose that, in this technology, crosspoints are
FET-like junctions.
 When a high or low voltage is applied, these
develop low or high impedances, respectively. 8

Crosspoints as squares
We model each crosspoint as a square.
(Black corresponds to ON; white corresponds to OFF.)
9
Implementing Boolean functions
signals in: Xij’s
signals out: connectivity top-to-bottom / left-to-right.
g (X11,…,XRC)
C Columns
TOP
X12
X1(C-1) X1C
M Columns
X(R-1)1
XR1
N Rows
X2C
LEFT
R Rows
X21
RIGHT
f (X11,…,XRC)
X11
INSULATOR
V-applied (Xij)
X(R-1)C
XR2
XR(C-1) XRC
BOTTOM
10
An example with 16 Boolean inputs
TOP
0
0
0
1
1
1
1
0
1
0
1
0
1
0
BOTTOM
LEFT
1
RIGHT
0
RIGHT
LEFT
TOP
BOTTOM
A path exists between top and bottom,
f=1
11
An example on 2×2 array
LEFT
LEFT
LEFT
LEFT
RIGHT
RIGHT
p1=0.9
p1=0.1
p14
0.66
1e-4
RIGHT
RIGHT
BOTTOM
TOP
TOP
TOP
TOP
BOTTOM
BOTTOM
BOTTOM
4p13(1-p1)
0.29
3.6e-3
4p1(1-p1)3
3.6e-3
0.29
(1-p1)4
1e-4
0.66
Relation between p1 ─ probability of experiencing ON crosspoint ─ and switch’s behavior.
If p1 is 0.9 then the switch is ON with probability 95%.
(The probability of getting an error is 5%.)
 If p1 is 0.1, the switch is OFF with probability 95%.
(The probability of getting an error is 5%.)

12
Non-Linearity Through Percolation
1.0
TOP
0.8
2
p
0.6
0.4
0.2
pc
0.0
BOTTOM
0.0
0.2
0.4
p
0.6
p2 versus p1 for 1×1, 2×2, 6×6, 24×24, 120×120, and
1

0.8
1.0
infinite size lattices.
Each square in the lattice is colored black with
independent probability p1.
 p2 is the probability that a connected path exists
between the top and bottom plates.
13
Defects matter!
TOP
LEFT
ON
Real
case
RIGHT
RIGHT
Ideal
case
LEFT
TOP
BOTTOM
BOTTOM
DEFECT
VApplied
OF
F
LEFT
BOTTOM
Real
case
RIGHT
RIGHT
Ideal
case
TOP
LEFT
TOP
BOTTOM
Ideally, if the applied voltage is 0, then all the crosspoints are OFF
and so there is no connection between any of the plates.
 Ideally, If the applied voltage is VDD, then all the crosspoints are ON
and so the plates are connected.
 With defect in nanowires, not all crosspoints will respond this way.

14
p 2 - Probability of global connectivity
Margins
1.0
ONEMARGIN
0.8
One-margin: Tolerable p1
ranges for which we
interpret p2 as logical one.
 Zero-margin: Tolerable p1
ranges for which we
interpret p2 as logical zero.

0.6
0.4
0.2
ZEROMARGIN
0.0
0.0
0.2
0.4
0.6
0.8
1.0
p1 - Probability of local connectivity
Margins correlate with the degree of defect tolerance.
15
Margin performance with a 2×2 lattice
TOP
X11
X12
LEFT
RIGHT
X21
X22
BOTTOM
X11
X21
X12
X22
f
Margin
g
Margin
0
0
0
0
0
40%
0
40%
0
0
0
1
0
25%
0
25%
0
0
1
1
1
14%
0
23%
0
1
0
1
0
23%
1
14%
0
1
1
0
0
0%
0
0%
0
1
1
1
1
14%
1
14%
1
1
1
1
1
25%
1
25%
f =X11X21+X12X22
g =X11X12+X21X22
Different assignments of input
variables to the regions of the
network affect the margins.
16
One-margins (always good)
0
1
1
p 2 - Probability of global connectivity
0
RIGHT
LEFT
TOP
BOTTOM
1.0
ONEMARGIN
0.8
0.6
0.4
0.2
0.0
0.0
f =0
=1
0.2
0.4
0.6
0.8
1.0
p1 - Probability of local connectivity
Defect probabilities exceeding the one-margin would likely
cause an (1→0) error.
17
Good zero-margins
1
0
1
p 2 - Probability of global connectivity
0
RIGHT
LEFT
TOP
BOTTOM
1.0
0.8
0.6
0.4
0.2
ZEROMARGIN
0.0
0.0
f =1
=0
0.2
0.4
0.6
0.8
1.0
p1 - Probability of local connectivity
Defect probabilities exceeding zero-margin would likely
cause an (0→1) error.
18
Poor zero-margins
1
1
0
p 2 - Probability of global connectivity
0
RIGHT
LEFT
TOP
BOTTOM
1.0
0.8
0.6
0.4
POOR
ZERO-MARGIN
0.2
0.0
0.0
f =1
=0
0.2
0.4
0.6
0.8
1.0
p1 - Probability of local connectivity
Assignments that evaluate to 0 but have diagonally adjacent
assignments of blocks of 1's result in poor zero-margins
19
Lattice duality
g (X11,…,XRC)
C Columns
TOP
X12
X1(C-1) X1C
X21
X2C
X(R-1)1
X(R-1)C
LEFT
R Rows
X11
RIGHT

Note that each side-to-side
connected path corresponds to
the AND of the inputs; the
paths taken together
correspond to the OR of these
AND terms, so implement a
sum-of-products expression.
A necessary and sufficient
condition for good error
margins is that the Boolean
functions corresponding to the
top-to-bottom and left-to-right
plate connectivities f and g
are dual functions.
f (X11,…,XRC)

XR1
XR2
XR(C-1) XRC
BOTTOM
20
Lattice duality
f  g D  f ( X11,....., X rc )  g ( X11,....., X rc )
TOP
1
1
0
1
0
0
1
1
0
0
0
0
1
1
0
1
1
0
1
0
0
1
1
0
1
1
0
1
0
0
BOTTOM
LEFT
0
RIGHT
1
RIGHT
LEFT
TOP
BOTTOM
21
Further work
Solve the logic synthesis problem. (Bring
continuum mathematics into the field.)
 Explore physical implementation in
nanowire arrays.
 Explore percolation as a model for digital
computation with DNA and other
molecular substrates.

22
Funding
MARCO (SRC/DoD)
Contract #NT-1107
NSF CAREER
Award #0845650
23