Transcript No Slide Title - Microsoft Research

Computing
Alternatives
Joel Birnbaum
Hewlett-Packard Senior VP R&D,
Director, HP Labs
ACM 97
ACM 97
THE NEXT 50 YEARS OF COMPUTING
ACM 97
ACM 97
THE NEXT 50 YEARS OF COMPUTING
Copyright  1997 ACM, Association for Computing
The files on this disk or server have been provided by ACM. Copyright and all rights therein are maintained by
ACM. It is understood that all persons copying this information will adhere to the terms and constraints
invoked by ACM’s copyright. These works may not be reposted without the explicit permission of ACM.
Reuse and/or reposting for noncommercial classroom use is permitted. Questions regarding usage rights and
permissions may be addressed to: [email protected]
ACM 97
JOEL BIRNBAUM
ACM 97
Computing
Alternatives
Joel Birnbaum
Hewlett-Packard Senior VP R&D,
Director, HP Labs
ACM 97
Three Alternatives

Quantum Computing
 DNA-based Computing
 Optical Computing
ACM 97
ENIAC Circa 1947
Source: U.S. Army photo
ACM 97
ENIAC Vital Statistics

Physical Characteristics





19,000 vacuum tubes, 1,500 relays
60,000 pounds, 16,200 cubic feet
174 kilowatts
5 kflops (~ same as Intel 4004)
Future Prediction (1949 Popular Mechanics)



1,500 vacuum tubes
3,000 pounds
10 kilowatts
ACM 97
ENIAC Vital Statistics

Physical Characteristics





19,000 vacuum tubes, 1,500 relays
60,000 pounds, 16,200 cubic feet
174 kilowatts
5 kflops (~ same as Intel 4004)
Future Prediction (1949 Popular Mechanics)



1,500 vacuum tubes
3,000 pounds
10 kilowatts
ACM 97
Moore’s Law
109
?
Transistors per Chip
108
107
Pentium
80486
Pentium Pro
106
80286
80786
80386
105
8086
104
8080
103
4004
1972
1976 1980
1984
1988
1992
Date
1996
2000
2004
2008
ACM 97
Moore’s Law
109
?
Transistors per Chip
108
107
Pentium
80486
Pentium Pro
106
80286
80786
80386
105
8086
104
8080
103
4004
1972
1976 1980
1984
1988
1992
Date
1996
2000
2004
2008
ACM 97
Vanishing Electrons
Electrons per Device
104
Transistors per Chip
103
16M
64M
256M
1G
102
4G
16G
101
?
100
10-1
1988 1992
1996
2000
2004
2008
2012
2016
2020
Date
Source: Motorola
ACM 97
Quantum Dots: (Ge Islands on Si)
Height (nm)
Average Height: 15nm
Standard Dev.: <1nm
Density: 6.4 x 109 /cm2
20
0
-20
Source: HP Labs Quantum Structures Research Initiative
ACM 97
Quantum Dots: (Ge Islands on Si)
Height (nm)
Average Height: 15nm
Standard Dev.: <1nm
Density: 6.4 x 109 /cm2
20
0
-20
Source: HP Labs Quantum Structures Research Initiative
ACM 97
Quantum Dots: (Ge Islands on Si)
Height (nm)
Average Height: 15nm
Standard Dev.: <1nm
Density: 6.4 x 109 /cm2
20
0
-20
Source: HP Labs Quantum Structures Research Initiative
ACM 97
Computational Complexity
Efficiency of an algorithm depends on how its execution
time grows as the size of the problem (input) increases...
Exp
Exp(L)
Execution Time
Ln
NP
L
P
Input Size L
Source: Artur Ekert, Clarendon Laboratories, Oxford University
ACM 97
Difficulty in Factoring
Number N of L decimal digits: N is of the order 10L
The trial division method: dividing N by 2,3,5... N1/2
Number of divisions required: N1/2 = 10L/2
Grows Exponentially with L
If a computer can perform 1010 divisions per second,
factoring a 100 decimal digit number with this method
takes 1040 seconds, much longer than the age of the
universe (1017 seconds)
Source: Artur Ekert, Clarendon Laboratories, Oxford University
ACM 97
Difficulty in Factoring
Number N of L decimal digits: N is of the order 10L
The trial division method: dividing N by 2,3,5... N1/2
Number of divisions required: N1/2 = 10L/2
Grows Exponentially with L
If a computer can perform 1010 divisions per second,
factoring a 100 decimal digit number with this method
takes 1040 seconds, much longer than the age of the
universe (1017 seconds)
Source: Artur Ekert, Clarendon Laboratories, Oxford University
ACM 97
Difficulty in Factoring
Number N of L decimal digits: N is of the order 10L
The trial division method: dividing N by 2,3,5... N1/2
Number of divisions required: N1/2 = 10L/2
Grows Exponentially with L
If a computer can perform 1010 divisions per second,
factoring a 100 decimal digit number with this method
takes 1040 seconds, much longer than the age of the
universe (1017 seconds)
Source: Artur Ekert, Clarendon Laboratories, Oxford University
ACM 97
The Traveling Salesman
Problem:
To find the shortest path from start to end going
through all the points only once.
4
3
1
0
6
2
Source: Dr. Leonard M. Adleman
5
ACM 97
Step 1:
Generate random paths
Randomly ligate together
pieces of DNA
2
0
3
1
4
6
5
DNA Ligase
0
1
0
2
1
3
4
1
2
3
4
1
2
3
4
6
5
ACM 97
Step 2:
Keep only paths starting
with 0 and ending with 6
0
1
0
Use the Polymerase Chain
Reaction
2
1
1
2
3
3
1
2
4
4
6
5
3
4
PCR 0-6
0
1
3
0
0
1
1
2
3
2
4
4
6
6
4
5
6
ACM 97
Step 3:
Separate the PCR products
by PAGE
Keep only paths that enter
exactly 7 vertices
0
1
2
0
0
3
4
2
1
4
2
5
6
6
5
4
5
6
PAGE
0
0
1
1
2
2
3
5
4
4
5
5
6
6
ACM 97
Step 4:
Isolate DNA by sequential
affinity purification
Keep only paths that enter
all 7 vertices at least once
0
1
2
3
4
5
6
0
1
2
5
4
5
6
Affinity Purification
0
1
2
3
4
5
6
ACM 97
Hybrid Fourier Transform
Processor
Digital From
Computer
Spatial
Light
Modulator
Output
Plane
Optical
System
Digital To
Computer
Collimating
Lens
Laser
performs
Fourier Transform
Creates a coherent,
monochromatic light
source
Incoming light
creates desired
input object
ACM 97
Hybrid Fourier Transform
Processor
Digital From
Computer
Spatial
Light
Modulator
Output
Plane
Optical
System
Digital To
Computer
Collimating
Lens
Laser
performs
Fourier Transform
Creates a coherent,
monochromatic light
source
Incoming light
creates desired
input object
ACM 97
Hybrid Fourier Transform
Processor
Digital From
Computer
Spatial
Light
Modulator
Output
Plane
Optical
System
Digital To
Computer
Collimating
Lens
Laser
performs
Fourier Transform
Creates a coherent,
monochromatic light
source
Incoming light
creates desired
input object
ACM 97
The Future:
Communicate with Photons,
but Compute with Electrons
ACM 97
ACM 97