Parallelization of Low-Communication Processes

Jörg Waldvogel and Peter Leikauf,
Seminar for Applied Mathematics SAM,
Swiss Federal Institute of Technology ETH,
CH-8092 Zürich, Switzerland

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.

Proposal (1 page):
Initial Report 2001 (9 pages): clprimes01.pdf
Two New Clusters of 18 Primes (2 pages): cl18.pdf
Experimental PARI code (1 page):
Finding Clusters of Primes, I. Progress Report 2003 - 2005 (15 pages): clprimes03.pdf
Finding Clusters of Primes, II. Progress Report 2006 - 2013 (16 pages): clprimes05.pdf
PMP: Poor Man's Parallelizer. User Guide (5 pages): pmp.pdf