Parallelization of Low-Communication Processes
Finding Clusters of Primes
Tapping the large amounts of idle time on numerous workstations and parallelizing large, but simply structured computational efforts is a cheap method of advancing to the limits of computationally feasible tasks. Known systems like PVM are able to function under quite general conditions, however, they achieve considerable complexity. The goal of this project at the Seminar for Applied Mathematics (SAM) of ETH was to parallelize an arbitrary number of workstations for distributed computations with low communication. In particular, we want to exploit the simple situation of a large computational effort that splits naturally into highly independent subtasks producing low data traffic. It was possible to come up with a small but robust system taking advantage of this simple, yet important situation. A typical class of problems of this type are exhaustive-search problems.
Currently, we are applying our parallelization concept to an algorithm
involving sieving techniques for locating and counting clusters of
prime numbers. Whereas the distribution of primes seems to be fairly
regular (if the Riemann hypothesis is true), the distribution of twin
primes and longer clusters is largely unknown and is characterized by
large-scale anomalies. Collecting experimental data on these anomalies
is one of the reasons for the interest in clusters of primes.
Initial Report 2001 (9 pages):
Two New Clusters of 18 Primes (2 pages):
Experimental PARI code (1 page):
Finding Clusters of Primes, I. Progress Report 2003 - 2005 (15 pages):
Finding Clusters of Primes, II. Progress Report 2006 - 2013 (16 pages):
PMP: Poor Man's Parallelizer. User Guide (5 pages):