Topics Register • News • History • How to • Sequences statistics • Template prototypes

Parallel computing

From Prime-Wiki
Jump to: navigation, search

Not everything that a computer does requires all other tasks to be done in order first. Some tasks can be done at the same time as others. When a single processor, multiple processors, or multiple cores perform 2 or more operations (similar or different) at once, that is parallel computing.

Example 1

To multiply 365 by 1440 by hand (long multiplication), an individual could proceed as shown in the table.

Step Input 1 Operation Input 2 Result 1440
x 365
1 5 x 1440 7200
2 60 x 1440 86400
3 300 x 1440 432000
4 7200 + 86400 93600
5 93600 + 432000 525600 ← result

But, if the first 3 steps do not depend on each other, they could all be done in parallel. This would cut a 5 step procedure to 3. If the numbers were each 100 digits long and 10 individuals (or cores in a computer) worked in parallel for the multiplication (and the addition steps) the speed up would be dramatic compared to a sole worker.

Example 2

An astrophysists wants to build a model of the solar system (1 sun, 8 planets, 100 moons, and 9891 asteroids and dwarf planets) and run it for the equivalent of 100,000,000 years. A single processing core would have to calculate the positions for each of the 10,000 objects, then repeat again for the next time interval. However, if the scientist had access to a supercomputer with 10,000 cores, one could be designated for each body. Then for each time interval, each core would calculate for that body, then the data would be exchanged, and the next iteration could begin.

By using parallel computing, the solar system model would run about 10,000 times faster than running on a single core.


Like other distributed computing projects, GIMPS uses a form of parallel computing. Since the Lucas-Lehmer test for one exponent does not depend on the results from others, they can be run in parallel. And, because there is no need to exchange data on each step, it is feasible to process each number on a physically separate machine.

There are some GIMPS tasks that are not practical to parallelize. While the Lucas-Lehmer test does not require any input from the trial factoring test, if trial factoring finds a factor, there is no need to run the L-L test (because it would be known to be composite). So, routinely running TF and L-L in parallel would waste computer time (over 60% of the exponents that GIMPS tests are found to have a factor by TF or P-1).

External links