**Navigation**

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

# Difference between revisions of "Parallel computing"

m |
m |
||

Line 3: | Line 3: | ||

==Example 1== | ==Example 1== | ||

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

− | {| | + | {| class="wikitable" |

− | + | ! Step !! Input 1 !! Operation !! Input 2 !! Result !! 1440<br>x 365 | |

− | |||

− | |||

− | |||

− | |||

− | |||

|- | |- | ||

− | | 1 | + | | 1 || 5 || x || 1440 || 7200 || |

− | | 5 | ||

− | | x | ||

− | | 1440 | ||

− | | 7200 | ||

− | | | ||

|- | |- | ||

− | | 2 | + | | 2 || 60 || x || 1440 || 86400 || |

− | | 60 | ||

− | | x | ||

− | | 1440 | ||

− | | 86400 | ||

− | | | ||

|- | |- | ||

− | | 3 | + | | 3 || 300 || x || 1440 || 432000 || |

− | | 300 | ||

− | | x | ||

− | | 1440 | ||

− | | 432000 | ||

− | | | ||

|- | |- | ||

− | | 4 | + | | 4 || 7200 || + || 86400 || 93600 || |

− | | 7200 | ||

− | | + | ||

− | | 86400 | ||

− | | 93600 | ||

− | | | ||

|- | |- | ||

− | | 5 | + | | 5 || 93600 || + || 432000 || 525600 || ← result |

− | | 93600 | ||

− | | + | ||

− | | 432000 | ||

− | | 525600 | ||

− | | | ||

|} | |} | ||

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. | 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. | ||

Line 53: | Line 23: | ||

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

==[[GIMPS]]== | ==[[GIMPS]]== | ||

− | 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 seperate machine. | + | Like other [[:Category:distributed computing project|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 seperate machine. |

There are some GIMPS [[worktype|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]]). | There are some GIMPS [[worktype|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]]). |

## Revision as of 14:03, 24 January 2019

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**.

## Contents

## 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.

## GIMPS

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 seperate 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).