IN 1989, Danny Hillis made a bold prediction. By 1995, he said, more of the world’s data would be handled by “parallel-processing computers” than by conventional computers. So confident was the colourful American scientist that he staked the future of his company, Thinking Machines, on just such a parallel computer called the Connection Machine.
Constructed from tens of thousands of interlinked microprocessors, the Connection Machine became a showcase for what parallel processing could do. By carving up huge jobs such as car-crash simulations into lots of small tasks and solving them simultaneously, the Connection Machine boasted the power of the fastest supercomputers for a tenth of the price. Not a bad selling pitch.
But Hillis’s prediction failed to materialise. In August 1994, Thinking Machines filed for protection from its creditors. The company is now back in profit, but only at the price of abandoning production of the Connection Machine and turning itself into a software house. Hillis now works for the Disney Corporation as a special effects consultant.
Advertisement
Yet no sooner was his company going down the tubes than others with less vision but more commercial nous were turning Hillis’s prediction into reality. The results look likely to make 1996 the year in which parallel processing finally takes off. “The whole field is in a state of rapid transition,” says Bill McColl, head of the parallel processing consultancy Oxford Parallel, based in the University of Oxford’s Computing Laboratory. “Before the end of 1996, you’ll even be able to buy multiprocessor PCs.”
This revolution is happening because of breakthroughs in processor technology, the emergence of mass market hardware and software, and new thinking about computer architecture. It is certainly not before time.
Brought to their knees
The conventional design of a computer, essentially unchanged in 50 years, is creaking under the strain. Known as the von Neumann model, after its designer the American-Hungarian mathematician John von Neumann, it solves problems by performing the instructions in a program one at a time in strict sequence. It sounds plodding and laborious, and it is. What makes conventional computers seem quick is just the sheer speed of modern microchips.
This speed has masked the increasing inadequacy of the von Neumann model. But now the crunch has come because of the massive demands that people are putting on their machines. Animators want to mass-produce full-colour, all-action cartoons to film quality standards, pharmaceuticals companies want to model the structure and behaviour of drugs at a molecular level, and cable TV companies want to feed multimedia services to tens of thousands of customers simultaneously. Such tasks bring all but the biggest, most expensive serial computers to their knees.
Parallel processing seems like the obvious solution, yet until recently, the mere mention of parallel processing would provoke shaking heads and rolling eyes among computer scientists. The reason is that parallel processing requires rather more than sticking a handful of microprocessors in a machine that used to have just one. This is mere “multiprocessing”, where some parts of a problem, adding large decimal numbers, say, can be handed over to specialised chips. It certainly helps, but truly parallel computers offer a far greater reward. In theory, their speed is unlimited. If you want to solve your problems a hundred times faster, then just wire in a hundred times as many processors.
The problem, of course, is how to divide the work so that those dozens, hundreds or even thousands of processors can solve their part of the problem and combine them to give the correct answer. It is generally impossible to break down a problem such as simulating a collision between galaxies into neat packages of precisely the same difficulty. Some processors will inevitably be given a tougher time than others, and they need to be able to tell their neighbours how they are getting on. It is this communications problem that has given parallel programming its fearsome reputation and made designing the hardware and software one of the biggest challenges in computer science.
From the 1960s, many research teams have wrestled with this problem and, naturally, each believed its approach was the right one. The outcome was baffling in its diversity: distributed memory machines, shared memory multiprocessors, workstation clusters, languages with weird names like PVM, MPI and Occam – which once seemed a promising approach to parallel programming.
Unfortunately, a common problem with many of these solutions was that they threw away one of the key advantages of parallel processing: “scalability”, that is, if the programs were run on a machine with ten times as many processors, the machine did not produce results ten times as fast. By the 1980s, however, computer scientists had discovered some languages that did seem to offer scalability. Most famous among these was Occam, which was most strongly linked with the Transputer, an early attempt at a chip designed for parallel processing which never fulfilled its full promise.
But with no industry standards in sight, most potential users of parallel processors responded with a weary “Wake us up when it’s all over”. And so, while the von Neumann model might be old hat, it still had its uses. “For sequential computing, it has given the two parts of the computing industry what they need,” says McColl. “The hardware industry has a stable architecture around which it can innovate, and software companies can spend time developing applications they know will run on virtually any machine, and which aren’t going to be made obsolete by the next hardware innovation.” On most of the early parallel systems, programmers had the time-consuming and tedious job of tailoring software to each machine.
Fast and cheap
All that is now beginning to change. Something approaching a standard parallel architecture is now emerging, and at its heart is a new generation of off-the-shelf “commodity” chips churned out in their thousands by companies such as Digital, Intel and MIPS. These have been designed to be as happy working in concert as working alone, making them perfect for low-cost parallel computers.
Even working singly, these chips are astonishingly powerful. Intel’s P6 chip, now called the Pentium Pro, is capable of around 200 million floating-point operations per second (1 flop is the addition of two large decimal numbers). The MIPS R8000 and Digital’s Alpha EV5 processors are even faster, capable of between 300 and 600 Mflops. Bring just a handful of these together and you get a desk-sized box with the computing clout that was once only possible with a supercomputer the size of a large shed.
Today’s fastest serial leviathans operate at up to 10 Gflops. By contrast, the parallel processing Power Challenge L machine, now being marketed by Silicon Graphics, links up to six R8000 processors to achieve a peak performance of 2 Gflops from a box just 60 centimetres high. Better still, the cost per Mflop is far lower than that possible from serial supercomputers: around $pound;100 per Mflop compared with upwards of £1000 per Mflop. Recent advances in design have also allowed these mass-market machines to offer that key advantage of parallelism, scalability.
Suddenly, all those years of struggling to connect the many elements of the machines have paid off. “Early massively parallel processing designs with very simple interconnect schemes did not deliver the promised performance,” says John Fleming, head of marketing at supercomputer makers Cray Research. Cray is now experimenting with a doughnut shaped array of processors, with connections running in three dimensions. This arrangement, says Fleming, gives optimal performance for systems that contain around 2000 processors.
In November, the company launched a parallel computer based on this research, the T3E. The most basic version links 16 Digital Alpha EV5s to give a peak performance of 10 Gflops, while a 1024-processor machine – that is, around sixty times as many processors – gives around sixty times the performance. The price is also impressive: between £50 and £70 per Mflop.
While off-the-shelf microprocessors and new architectures are transforming parallel processing hardware, software designers are attacking the notorously difficult problem of developing programs for such machines. The dearth of commercially useful programs has long been recognised as a major barrier to the spread of parallel processing. One of the key problems has been the lack of a standard parallel computer design around which software designers can work. In a perfect world, programs written for a prototype parallel machine would run on all parallel machines.
The perfect world may now have been created by Les Valiant at Harvard University and McColl in Oxford. They have come up with the Bulk Synchronous Parallel model of parallel processing. Just as the von Neumann model breaks down any serial computer into its bare essentials, such as input and output, memory and central processor, so the BSP model captures the essence of any parallel machine.
The demands of synchrony
The BSP model also cuts through the problem of “synchronous message passing”, which was a nightmarish facet of a number of the languages developed for programming parallel computers. McColl likens synchronous message passing to making a telephone call. Each processor phones its neighbours when it has something to say, and the neighbours respond then and there. “That’s easy to do when there are only two of you, but imagine trying to arrange a conference call between 1000 people,” says McColl. “It was that sort of complexity the programmer had to deal with.”
The BSP model cuts out the need for processors to communicate in synchrony, using a technique similar to electronic mail. When we send an e-mail message, the recipient does not have to be at home. The message is stored in an electronic “pigeon hole” until the recipient has the time to download and read it, along with any other e-mail that has built up. Each processor acts like a pigeon hole, storing results until its neighbours are ready to receive them. “That means we’re no longer at the mercy of the demands of synchrony,” says McColl. “By compressing the time delay we can still get programs running very quickly.”
Once the software developer has analysed both the task and the parallel machine according to the BSP model, a library of BSP-based software tools developed by McColl and his colleagues can be used to produce programs for the machine. McColl says that as well as being much simpler and scalable, programs written using the BSP model are portable, that is, they will work on other parallel machines. “Our work on the BSP model has shown for the first time that it is possible to develop parallel software that will run unchanged, with optimal performance, on any parallel architecture.”
This is not a modest claim and it is being put to the test as part of a Europe-wide initiative funded as part of the Esprit III programme and designed to give industry a head start in exploiting parallel computing. Known as Europort, its aim is to “port” – that is, convert – standard serial programs into parallel programs. And impressive results of real commercial value are already emerging.
At a symposium on computational chemistry held in France in November last year, for example, the pharmaceuticals company Bayer demonstrated the dramatic speed-up in drug development made possible by switching to parallel processing. The company’s researchers wanted to know more about the molecular interactions of an anti-Aids drug known as DMP-323. Usually, the company would look for answers by modelling the interactions on standard serial workstations. This time, however, Bayer used a 23-Gflops machine called the Power Challenge array made by Silicon Graphics. “When our chemists ask us questions like these, it takes months for us to give them answers using our current sysems,” says Felix Reichel, a computational chemist at Bayer’s Leverkusen laboratories, Germany. This time, he says, “we had the answers in two and a half days”.
Kid’s stuff
While many Europort projects have tackled such well-known computationally intensive problems, others have been more unusual. It may look like kid’s stuff, but computerised, full-colour animation is a major undertaking. A single film-quality frame needs the manipulation of around 10 million pixels, and a single 25-minute cartoon needs tens of thousands of frames. Animation companies need as much computer power as they can lay their hands on. In one Europort project, Cambridge Animation Systems (CAS) worked with Perihelion Distributed Software to develop parallel processing software for animation. This involves colouring a character, adding all the layers of background and foreground and bringing in special effects such as smoke.
By switching to parallel processing, CAS can now offer animators rendering speeds limited only by the number of processors available. With a commercial product offering to do in three hours what normally take three working days, CAS’s software sales have rocketed, with Steven Spielberg’s Dreamworks studio and Warner Brothers among its customers. “It’s now the most successful animation system in the world,” says Richard Ashton of CAS.
Much of the demand for parallel processing will come from those companies that are hoping to exploit the much-vaunted network of multimedia services that will one day be piped into our homes. The success of such services depends on being able to meet the demands of thousands of people simultaneously – a natural task for a parallel-processing machine.
In Cambridge, trials are under way of a network that supplies hundreds of homes with everything from video-on-demand to home banking. ICL’s massively parallel PimSERVER machine has been installed to respond to all the customer demands in the trials, for example, taking compressed multimedia data out of storage and sending it down the line to people’s homes.
According to Graham Gill, interactive multimedia marketing manager at ICL, speed of response is not the only advantage of using parallel processing here. “The most important is scalability. As the number of end users increases, it’s a simple matter to add in more processors.” Parallel machines are also less likely to crash catastrophically at times of heavy demand, adds Gill: “If a processor fails, the PimSERVER will still carry on and try to reconnect those connected to the failed processor to working ones”.
With both parallel hardware and software now starting to appear in quantity, parallel processing looks ready to explode onto the commercial market. However, much of the revolution will take place away from the public gaze, according to Adrian Colbrook of high-tech consultancy Smith System Engineering, which is coordinating the Europort initiative. “Most everyday tasks will still be done by serial machines,” he says. “It will be people like banks creating data warehouses and interactive service providers who will be making use of the technology.” And as ever, there will be the “power users”, the national research laboratories, weather forecasters and government defence centres, with their insatiable appetite for more computing power.
By the end of this year, the US government’s Sandia National Laboratories in New Mexico plans to have built the apotheosis of parallel processing power – the teraflops machine. Named after its target speed of over 1012 floating point operations a second, the teraflops machine will be ten times faster than any computer on Earth. Yet that performance will be achieved using off-the-shelf Pentium Pro chips, 9000 of them working in concert. The main task of the machine will carry out simulations to check the safety of nuclear weapons, but if past history is any guide, aircraft designers and drugs companies will soon follow suit. Add to them the Gflops even small companies will soon be demanding and suddenly Danny Hillis begins to look like a true visionary.