 |
Background:
Commodity computers are undergoing a fundamental change, unprecedented
since the advent of computers in the 1940s. In the first chapter of
computer history that spanned from 1946 through 2003, clock frequency
had been improving at a stunning exponential rate. Beginning in 2004,
clock frequency is hardly improving and is not expected to improve much
due to implementation issues, such as power consumption. The main way
around the problem has been to build multi CPU machines.
Despite their theoretical advantages, computers with multiple CPUs have
been slow to gain popular acceptance. One reason is that programming
computers with even 2 CPUs can be much more complex and error-prone than
programming a traditional single-CPU computer. Breaking this impasse
would effectively unlock the power of multi-CPU computers and,
therefore, make computers with dozens, hundreds or even thousands of
CPUs useful in practice.
UMIACS' Uzi Vishkin along with colleagues at the University of
Maryland's A. James Clark School of Engineering are doing just this.
They have just put together a prototype system made up of 64 parallel
processors. To understand what gives their system a unique advantage recall that the
essence of every computer program is an algorithm. Since 1979 Vishkin was part of a community that developed the single
most successful mathematical theory of parallel algorithms.
There was a big battle of ideas in the 1980s on how to think
algorithmically in parallel. Their approach, called PRAM (for parallel
random access machine/model) won.
By 1990, the theory appeared in big chapters in standard textbooks
taught in most computer science programs.
However, this turned into a roller coaster. In the early 1990s it became
clear that it would not be possible to build a machine that will
effectively support the mathematical model using the fabrication
technology of the time.
Many concluded that the algorithmic approach is leading to a dead-end
and will never be of any use.
The problem was that the only way to build parallel computers back then
was as multi chips, and the bandwidth between chips was insufficient.
Now, for the good news. The number of transistors on a single chip keeps
increasing at an exponential rate (as before 2004) and is expected to
reach tens of billions by 2010, up from tens of thousands 30 years
earlier. This growth by a factor of one million (!) allows now to put a
supercomputer on a single chip. This supercomputer can have a 1000
processors as well as a powerful high-bandwidth interconnection network.
This finally allows taking advantage of the older PRAM theory and
explains Prof. Leiserson's (MIT) statement in the press release that the
UMD approach unifies yesterday's theory with today's reality.
Their algorithms then allow programmers to easily use this power,
resulting in performance that can be 100 times faster than that found in
current desktop PCs.
| |
|
|
