Record speedups for parallel processing.

Record Speedups for Parallel Processing 

In computer circles, the full potential of parallel processing has always seemed out of reach. In theory, 1,000 processors working simulataneously -- with each taking on a small portion of the total computation -- could tackle a problem 1,000 times faster than one processor plodding through the problem step by step as most computers do now. In computer lingo, the 1,000-processor machine would then have a "speedup" of 1,000. This would be akin to constructing a building with 1,000 workers rather than just one.

But most computer scientists have been slow to harvest the fruits of this division of labor, because they've believed that such ideal speedups--equal to the number of processors used -- were unattainable. This week researchers at Sandia National Laboratories in Albuquerque, N.M., shattered the skepticism by announcing that they have achieved record speedups of more than 1,000 on a 1,024-processor computer. By showing that it is possible to run a parallel machine at near-100 percent efficiency, they have ensured a prominent place for paralel processing in the future of computing.

This future had been in doubt because of the realization that what is gained by dividing up the computation is partly offset by the time it takes for processors to talk to one another and to perform "serial" tasks that simply can't be divvied up. The longheld belief has been that these chores will bog down a parallel machine so much that even with a billion processors, speedups of only 100 are the best anyone could hope for.

As a result, "there's been a psychological barrier to working with thousands of processors on a single problem," says Sandia computer scientist Robert E. Benner.

Now Benner and Sandia colleagues John L. Gustafson and Gary R. Montry have broken through this barrier by carefully crafting computer algorithms designed to get the most out of a parallel processing machine. They ran these programs on a recently acquired, state-of-the-art "hypercube" computer made by NCUBE Corp. of Beaverton Ore. With the hypercube architecture, processors are connected as if they were sitting at the corners of cubes that fit inside of one another.

The researchers first considered problems involving a few thousand equations -- the largest size that could be handled by a single processor -- and then divided the problem among increasing numbers of processing units. By judiciously arranging their programs to maximize parallel tasks and minimize serial ones, they achieved speedups of 502 to 637 on the 1,024-processor hypercube. This means that a problem that took 30 hours to run on one processor was completed in about 3 1/2 minutes with the hypercube.

But Benner and his colleagues also realized that they could use the machine most efficiently if they expanded the problem size and complexity while they added more processors. In problems involving wave propagatin, mechanics and fluid flow, they achieved speedups of 1,020, 1,019 and 1,011 respectively. These problems account for about half the kinds of scientific and engineering problems that normally concern Sandia researchers. One of the scientists' next projects is to see if other types of problems yield to their parallel processing approach as well.

"these guys did an outstanding job," says Alan Karp, a physicist based in Palo Alto, Calif. "They've shown that you can get almost all the speed that's [available to machine]."

In so doing, Benner's group was the first to meet a challenge issued by Karp in 1985, who says that at the time there had been a lot of talk about building computers with 1,000 or 10,000 processors, but that on one had shown that these machines would be able to do anything useful. To spur the development of multi-processors and their software, he challenged computer scientists to demonstrate a speedup of at least 200 on a general-purpose computer. "I didn't think anybody would [meet the challenge] so soon," he says.

With their speedups of 502 to 637 from the fixed-sized problems, Benner and his colleagues were also the recipients earlier this month of this first Gordon Bell Award, which was established to acknowledge important contributions to parallel processing applied to real problems. According to Karp, who was a judge in the Bell competition, second place went to a research consortium that achieved speedups of 458 on a 512-processor machine and 39 with 127 processors. The speedups of all remaining entries were 16 or less.

For the near term, the Sandia work shows the multiprocessors can solve problems as fast as current Cray supercomputers computers and other supercomputers that contain only a few processors at most -- but at about one-tenth the cost, making supercomputer power accessible to more people. And for the distant future, it paves the way for suceeding generations of parallel computers that may contain hundreds of thousands of processors. "By developing more of these massively parallel applications in the future," says Benner, "we're preparing for the day when we'll have a truly awesome machine to run them."