Skip to content

Rebooting Computing

October 27, 2014


How to beat the end of Moore’s Law

Screen Shot 2014-10-27 at 2.25.21 PM

Elie Track and Tom Conte were co-chairs of the recently-held Third IEEE workshop on Rebooting Computing. Tom is a computer architect at Georgia Tech. A year ago he became the 2014 President-Elect of the IEEE Computer Society, which according to both the press release and Conte’s Wikipedia page entails that he “currently serves as the 2015 President.” I guess that is one way to stay focused on the future. Track is president of the IEEE Council on Superconductivity. A year ago he founded nVizix, a startup to develop photovoltaic power, and serves as CEO. He is also a senior partner at Hypres, a superconducting electronics company.

Today I wish to relate some of what happened last week at the meeting.

The meeting was held in Santa Cruz and had about forty participants. I was honored to be one of them. The problem we were given to consider is simple to state:

Computers are growing in importance every day, in all aspects of our lives. Yet the never-ending increase in their performance and the corresponding decrease in their price seems to be near the end.

Essentially this is saying that Moore’s Law, named for Gordon Moore, is about to end.

Well “about” is a bit tricky. Some would argue it has already ended: computers continue to have more transistors, but the clock rate of a processor has stayed much the same. Some argue that it will end in a few decades. Yet others claim that it could go on for a while longer. Lawrence Krauss and Glenn Starkman see the limit still six hundred—yes 600—years away. This is based on the physics of the Universe and the famous Bekenstein bound. I wonder if this limit has any reality when we consider smartphones, tablets, and laptops?

In 2005, Gordon Moore stated: “It can’t continue forever.” Herbert Stein’s Law says:

“If something cannot go on forever, it will stop.”

I love this law.

The Main Issues

The workshop was divided into four groups—see here for the program.

  • Security
  • Parallelism
  • Human Computer Interaction
  • Randomness and Approximation

Let me say something about each of these areas. Security is one of the most difficult areas in all of computing. The reason is that it is essentially a game between the builders of systems and the attackers. Under standard adversarial modeling, the attackers win provided there is one hole in the system. Those at meeting discussed at length how this makes security difficult—impossible?—to achieve. The relationship to the end of Moore’s Law is weaker than in the other groups. Whether computers continue to gain in price-performance, security will continue to be a huge problem.

Parallelism is a long-studied problem. Making sequential programs into parallel ones is a famously difficult problem. It is gaining importance precisely because of the end of Moore’s Law. The failure to make faster single processors is giving us chips that have several and soon hundreds of processors. The central question is, how can we possibly use these many processors to speed up our algorithms? What I like about this problem is it is really a theory type question: Can we build parallel algorithms for tasks that seem inherently sequential?

Human Computer Interaction (HCI) is about helping humans, us, to use computers to do our work. Gregory Abowd of Georgia Tech gave a great talk on this issue. His idea is that future computing is all about three things:

  1. Clouds
  2. Crowds
  3. Shrouds

Of course “clouds” refers to the rise of cloud computing, which is already an important area. And “crowds” refers not only to organized crowdsourcing but also to rising use of social media to gather information, try experiments, make decisions, and more.

The last, “shrouds,” is a strange use of the word, I think. Gregory means by “shrouds” the computerized smart devices that we will soon be surrounded with every day. Now it may just be a smartphone, but soon it will include watches, glasses, implants, and who knows what else. Ken’s recent TEDxBuffalo talk covered the same topic, including evidence that human-computer partnerships made better chess moves than computers acting alone, at least until very recently.

The last area is randomness and approximation. This sounds near and dear to theory, and it is. Well, the workshop folks mean it in a slightly different manner. The rough idea is that if it is impossible to run a processor faster, then perhaps we can get around that by changing the way processors work. Today’s processors are made to compute exactly. Yes they can make errors, but they are very rare. The new idea is to run the processor’s much faster to the point where they will make random errors and also be unable to compute to high precision. The belief is that perhaps this could then be used to make them more useful.

The fundamental question is: If we have fast processors that are making lots of errors, can we use them to get better overall performance? The answer is unknown. But the mere possibility is intriguing. It makes a nice contrast:

Today we operate like this:

Design approximate algorithms that run on exact processors. Can we switch this around: Design algorithms that operate on approximate processors?

I note that in the narrow area of just communication the answer is yes: It is better to have a very fast channel that has a reasonable error rate, than a slower exact channel. This is the whole point of error correction. Is there some theory like this for computation?

Open Problems

There are several theory-type issues here. What really are the ultimate limits of computation? Can we exploit more parallelism? This seems related to the class {\mathsf{NC}}, for example. And finally, can we exploit approximate computing to solve traditional problems?

A New Twist on Flexagons?

October 22, 2014


For Martin Gardner’s 100th birthday

Martin Gardner
Global Science source

Martin Gardner introduced many including myself to the joys of Discrete Mathematics. His glorious monthly column “Mathematical Games” for Scientific American included some continuous mathematics too, of course; one could say it was on “Concrete Mathematics.” However, I conjecture—based on a quick flip of the several books I own of his columns—that the symbols {\epsilon,\delta} in a calculus context never appeared in them.

Yesterday was the 100{{}^{th}} anniversary of Gardner’s birth. Dick and I wish to join the many others marking this centennial and thanking him for all he did to make math fun for so many. Read more…

A New Provable Factoring Algorithm

October 18, 2014


Factoring, factoring, the whole day through, keeps on my mind—apologies to Hoagy Carmichael and Stuart Gorrell

MichaelRubinstein
Waterloo Mathematics source

Michael Rubinstein is an expert on number theory, who is on the faculty of the University of Waterloo. He is one of the organizers of a 61{^{st}}-birthday symposium being held December 15–19 in Princeton for my friend and former colleague, Peter Sarnak. I guess it is a matter of taste for a number theorist whether to observe a birthday with a lot of factors (60) or a prime (59 or 61). Rubinstein also does extensive experimental mathematics and lists several code libraries below his publications on his website, which also has interesting articles on the math, history, and practice of musical tuning.

Today Ken and I wish to discuss a paper of his on one of my favorite problems: integer factoring.
Read more…

TEDx Time In Buffalo

October 13, 2014


Our own Ken joins the team for TEDx

images

Adrienne Bermingham is the manager of this year’s TEDx Buffalo event, which will be held this Tuesday at the Montante Center of Canisius College in downtown Buffalo.

Today I wish to proudly announce that our own Ken Regan is one of the presenters at this year’s event.
Read more…

More on Testing Dyson’s Conjecture

October 11, 2014


Applying deep number theory to algorithms

AlanBakerLectern
FullWiki source

Alan Baker won the Fields Medal in 1970 for his work on algebraic and transcendental numbers. He greatly extended a theorem of Aleksandr Gelfond and Theodor Schneider which had solved the seventh problem on David Hilbert’s famous list. Baker’s extension says that if {\alpha_1,\dots,\alpha_k} are algebraic numbers other than {0} or {1}, and if {\beta_1,\dots,\beta_k} are irrational algebraic numbers that together with {1} are linearly independent over the rationals, then the product of {\alpha_i^{\beta_i}} for {i = 1} to {k} is transcendental. Hilbert had stated the {k=1} case, which Gelfond and Schneider solved, and believed it would be harder than the Riemann Hypothesis.

Today Ken and I want to talk about computing numbers to high precision and their relationship to our recent discussion of Freeman Dyson’s challenge. Read more…

How To Add Numbers

October 5, 2014


It’s harder than you think

Unknown

William Kahan is a numerical analyst and an expert on all things about floating point numbers. He won the 1989 Turing award for his pioneering work on how to implement floating point computations correctly. He has also been a tireless advocate for the care needed to avoid insidious numerical bugs, and his strong feelings come out in a 1997 interview for Dr. Dobbs’ Journal.

Today I want to talk about one of his results on how to sum a series of numbers.
Read more…

The Busy Beaver Problem

October 1, 2014


Can the impossible become practical?

TiborRado
Complex analysts gallery source

Tibor Radó was a mathematician who was the PhD advisor to a number of computer scientists. They include Shen Lin, Paul Young, and several others. All were his students while he was at Ohio State University. He is not the Rado of the Erdős-Ko-Rado theorem—that is Richard Rado, without an accent. Tibor Radó had an Erdős Number of 3, through Lin and then Ron Graham.

Today we want to continue to talk about the famous “Busy Beaver” problem which we mentioned in our discussion on the Microsoft SVC lab closing. Read more…

Follow

Thank you for subscribing to “Gödel's Lost Letter and P=NP”

You’ll get an email with a link to confirm your sub. If you don’t get it, please contact us