|
|||
Unsolved problems in Computer Science In fifty years, computer science has made enormous strides. The first modern digital electronic computer was ENIAC, built in 1946 out of vacuum tubes. (It had a mean time to failure of about seven minutes. Then a tube filament somewhere in the system would blow and bring the system down.) Since then we've moved to the point where our entire world is run by computers, progress beyond the imagination of people in 1960. There is much yet we need to learn. The biggest unsolved problem in computer science is how to apply massively parallel computers to solve fundamentally serial problems. There exists a general solution for solving parallel problems with a serial computer: timesharing with semaphores, and iteration. And, of course, a fast serial computer is ideal for solving problems which are fundamentally serial. But there are physical limits on how powerful a serial processor can be -- and we're getting close to the theoretical limit. There are four physical limits which between them impose a ceiling: the speed of light, the size of an atom, the time it takes for an electron to change state, and Planck's constant. The speed of light limits the rate at which signals can propagate. (In half a nanosecond, light travels fifteen centimeters.) The size of an atom imposes a minimum size on a gate. The electron state change time imposes a minimum time that a transistor can take to change state. Planck's constant is also a hard limit but more esoteric, because it controls "tunneling". It forces you against the other three walls. The Heisenberg principle states that our knowledge of the position of an electron and its velocity vector will always involve some degree of error. More specifically, the product of the two errors will always be greater than Planck's constant. This is not a statement about our incompetence in producing measurement equipment; it is rather a fundamental statement about the nature of the electron (and, it turns out, all other particles). At the level of subatomic particles, the universe is stochastic, not deterministic. For one thing, at this scale Conservation of Energy is not quite as hard as you might think. Over the long run, taken as an average, energy is conserved. But for short durations it can vary. An electron can borrow energy from nowhere, as long as the product of the amount of energy and the duration of the loan is less than Planck's constant. A bipolar transistor works by creating a junction, and building (or collapsing) an electric field in the middle. If the field is present on the base, then electrons cannot travel from the emitter to the collector because they don't have enough energy to "climb the hill" in between. The transistor is "off". If the field has collapsed, then current can flow. The transistor is "on". The problem is that if the physical distance from emitter to collector is sufficiently short, and if the field on the base is sufficiently low (though still "off") then electrons can temporarily borrow enough energy to cross the barrier anyway. This is called "tunneling" and it's been experimentally confirmed. It's one of the many marvelous predictions made by Quantum Theory. This effect increases as the base becomes narrower, and at a certain point the transistor will leak as much current when off as it permits to flow when on, making the junction useless. Until recently, no-one had the ability to make a transistor small enough for this effect to kick in. But as geometries continue to shrink, this will begin to happen more and more. A Field Effect Transistor uses a different physical principle for switching, but it remains the case that it imposes a space between source and drain which may or may not conduct current, and if that space is sufficiently small, electrons will start to tunnel across it. This effect can be controlled as the barrier becomes narrower by making it taller, which is to say by making the electric charge on the base bigger (or the gate, in the case of a FET). This makes it so that a electron needs to borrow more energy to successfully tunnel, which means it keeps it for less time and can travel less distance. But that means you have to move more current in and out in order to make the transister change states, which makes the transistor switch slower. For forty years, "Moore's law" has governed the computer industry: Every three years, the speed of computers will double (cumulatively). That will soon end. Current technologies will top out in another factor of ten or so increase in speed (about ten years from now). There is a very speculative technology on the horizon which switches light beams instead of flows of electrons, which may relax some limits and give us as much as three more orders of magnitude in serial computation speed, possibly giving us a picosecond gate. Then it ends. (In one picosecond, light travels 30 microns [.03 millimeter].) But there is no theoretical limit on the power of a highly parallel computer. The difficulty is that we don't know how to apply the power of a parallel computer to solve serial problems. That is what we must learn. There are many kinds of problems which are fundamentally parallel to begin with, which can easily absorb enormous amounts of parallel computation capability with ease. The best example of that is 3D rendering, where each individual pixel can be computed independently of all the others, and where that computation itself can be pipelined. You could use ten or more processors per pixel, plus thousands of others doing overhead and bookkeeping and optimization. If you're rendering a 1600*1200 animation in real time, you could easily apply as many as twenty million processors with almost linear scaling. On the other hand, some problems are fundamentally serial: they involve calculating a lot of values but each calculation requires knowing the answer to the previous calculation. One possible approach (which is being explored now) is speculative computing. You start by estimating the result of the first step, quick and dirty. You then apply a million processors to the second step using various possible results of the first step, while one processor begins to fully calculate the first step. Then depending on the result found in the first step, you take the result found by the one of the million working on the second step whose assumed input was the right one. This is, obviously, enormously wasteful; yet it may not actually be all that wasteful if your computer has a thousand million processors available. (The most sophisticated modern microprocessors already do this to a very limited extent.) But there has to be a way to make it more efficient, not so much in the use of processors as in the decrease in time. With this horribly crude approach a million processors collapse compute time by a factor of two. It's got to be possible to do better than that. Highly parallel computers may also make it possible to solve problems we can't solve at all now with blazingly fast serial systems. Suppose that we could produce a computer with a clock rate of 2 KHz which had a million million processors. What could we do with it? Well, a lot of things: speech, object recognition from silhouettes, loads of things. Perhaps even intelligence (whatever that is). We know this because we each carry one inside our skulls. 2 KHz is a preposterously slow switching speed; our brains make it up in equally preposterous parallelism. And it is known that our brains use speculative computing, though the details are not understood. But our brains are capable of solving some kinds of extremely sophisticated problems in less than 400 cycles. No-one knows how. It will be a while before we can produce a parallel computer with only a million processors, but it's also the case that the ones we do produce will be considerably faster and more sophisticated than neurons. (And multi-thousand processor computers exist now.) The problem is that we only have the most primitive ideas of how to program such a beast, except when taking on problems which are fundamentally parallel anyway. This is the great problem for computer science in the first half of the twenty-first century. This page has been viewed 4760 times since 20010726. |
|||
