The Algorithm Design Manual Second Edition

7.10

War Story: Going Nowhere Fast

In Section

2.8

(page

51

), I related our efforts to build a fast program to test Waring’s

conjecture for pyramidal numbers. At that point, my code was fast enough that

it could complete the job in a few weeks running in the background of a desktop

workstation. This option did not appeal to my supercomputing colleague, however.

“Why don’t we do it in parallel?” he suggested. “After all, you have an outer

loop doing the same calculation on each integer from 1 to 1,000,000,000. I can split

this range of numbers into different intervals and run each range on a different

processor. Watch, it will be easy.”

---

7 . 1 0

W A R S T O R Y : G O I N G N O W H E R E F A S T

269

He set to work trying to do our computations on an Intel IPSC-860 hypercube

using 32 nodes with 16 megabytes of memory per node—very big iron for the time.

However, instead of getting answers, I was treated to a regular stream of e-mail

about system reliability over the next few weeks:

• “Our code is running fine, except one processor died last night. I will rerun.”

• “This time the machine was rebooted by accident, so our long-standing job

was killed.”

• “We have another problem. The policy on using our machine is that nobody

can command the entire machine for more than thirteen hours, under any

condition.”

Still, eventually, he rose to the challenge. Waiting until the machine was stable,

he locked out 16 processors (half the computer), divided the integers from 1 to

1,000,000,000 into 16 equal-sized intervals, and ran each interval on its own pro-

cessor. He spent the next day fending off angry users who couldn’t get their work

done because of our rogue job. The instant the first processor completed analyzing

the numbers from 1 to 62,500,000, he announced to all the people yelling at him

that the rest of the processors would soon follow.

But they didn’t. He failed to realize that the time to test each integer in-

creased as the numbers got larger. After all, it would take longer to test whether

1,000,000,000 could be expressed as the sum of three pyramidal numbers than it

would for 100. Thus, at slower and slower intervals each new processor would an-

nounce its completion. Because of the architecture of the hypercube, he couldn’t

return any of the processors until our entire job was completed. Eventually, half

the machine and most of its users were held hostage by one, final interval.

What conclusions can be drawn from this? If you are going to parallelize a

problem, be sure to balance the load carefully among the processors. Proper load

balancing, using either back-of-the-envelope calculations or the partition algorithm

we will develop in Section

8.5

(page

294

), would have significantly reduced the time

we needed the machine, and his exposure to the wrath of his colleagues.