Looking Back, Looking Forward

For the last few months I've been using a couple of pictures in talks that I give. They're a pretty stark reminder of the reality of Moore's law.

This is a picture of me in about 1970. My mom insists that I was 14, which would have been 1969, but I think it was more likely a year later. This was taken at the Physics department of the University of Calgary where I had a part-time job writing software on a PDP-8/I for the ISIS-II satellite. In the background is the machine that I wrote software for. There are a couple of 9-track tape drives, a couple of DECtape drives, a flatbed plotter, a paper-tape reader, an A/D panel, a display and immediatly to the right of me is the front panel for the CPU, which occupied the bottom half of one whole rack. The CPU was pretty hot for its day: about 1/4 MHz. It had 8K of RAM that was eventually upgraded to 12K.

This is another picture of me. It's on my Sun employee ID card. It's a java-based smart card. You can see the smart card reader contacts on the bottom of the card. The CPU+memory chip is imbedded in the plastic next to it. Woven into the card is the antenna for the RF network connection.

Of course, the interesting thing here is not the pictures of me, or the demonstration of the toll the years have taken on my hairline. It's the technology in the background. I find it amazing that the hot machine on the left, capable of doing all sorts of interesting things with satellite telelemetry (including making high resolution photographs, which was a neat trick with only 8K!), has less horsepower than the cheap piece of disposable plastic on the right. What will it mean when todays large hot machine fits into a volume smaller than a grain of rice?

Today's hot lab machine, that would be used in places where the PDP-8/I was used, runs about 4GHz, which is about 2¹⁴ times faster. So that's 14 doublings in 33 years, or about one doubling in 28 months. These two data points give a rate for Moore's law that is somewhat slower than the numbers that folks often use (18-24 months), but it's still pretty fast.

The exponential nature of Moore's law can really be nonintuitive. My favorite is a cool proof, due to Ed Fredkin, that P==NP. Yes! It's true! P does really equal NP. (If you don't know what I'm talking about, look here and here.) Well... The proof only works if you assume that you have a CPU whose clock rate accelerates exponentially - it's a pretty easy proof since this assumption turns exponential time algorithms into polynomial time algorithms). Where can you buy such a crazy machine? Anywhere! If you upgrade the machine on your desk every couple of years, it'll be twice as fast. What you experience is a machine in front of you that accelerates exponentially. Moore's law makes P=NP.

This has a number of interesting implications:

• One is that folks making security standards need to be careful about setting limits on key lengths: while it is true that for most decent encryption/signature algorithms, the length of time needed to crack the key is exponential in the length of the key; it is also true that the speed of CPUs is increasing exponentially, so the time until a standard with a fixed key length is obsolete is linear in the length of the key.
• Another is that there's a different strategy for completing long running calculations. Say you have some calculation that will take 1000 years to complete. You could start your machine running today and come back in 1000 years, but there is a better way: go to the beach for 14 years (if the Moore's law doubling period is 18 months), buy a new machine, and solve the problem in a single year.
• Another is that one of these days "AI" will really work. Read HAL's Legacy: 2001's Computer as Dream and Reality for an interesting perspective on this.

The computer revolution has only just begun. What will it mean when (not if) your wristwatch is smarter than you are?

January 2, 2004