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.

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):
http://www.asgard.ethz.ch/day/ws0001/waldvoge.phtml

Initial Report 2001 (9 pages):
clprimes01.pdf

Two New Clusters of 18 Primes (2 pages):
cl18.pdf

Experimental PARI code (1 page):
paricode.gp

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