* The program runs with one process per node and multiple threads per process. * The program uses the master-worker pattern for load balancing. Each process * in the program is an independent worker process. Each worker process * calculates a series of groups of sieves, as assigned by the master thread. * Within each group of sieves, the threads of the worker process calculate the * individual sieves in parallel. *
* The groups of sieves are determined by the pj.schedule property * specified on the command line; the default is to divide the sieves evenly * among the worker processes (i.e. no load balancing). For further information * about the pj.schedule property, see class {@linkplain * edu.rit.pj.PJProperties PJProperties}. *
* Within each group of sieves, the individual sieves are partitioned among the * threads of the worker process using the parallel loop schedule specified by * the last command line argument. If this argument is missing, the default is * to divide the individual sieves evenly among the threads (i.e. no load * balancing). For further information, see the parse() method in class * {@linkplain edu.rit.pj.IntegerSchedule IntegerSchedule}. *
* Usage: java -Dpj.np=Kp -Dpj.nt=Kt [
* -Dpj.schedule=procschedule ] edu.rit.hyb.prime.PrimeCountFunctionHyb
* x primefile [ thrschedule ]
*
Kp = Number of parallel processes
*
Kt = Number of parallel threads per process
*
procschedule = Load balancing schedule for processes
*
x = Argument of prime counting function, 0 <= x <=
* 263-1
*
primefile = Prime file name
*
thrschedule = Load balancing schedule for threads
*
* The computation is performed in parallel in multiple processors. The program
* measures the total running time.
*
* @author Alan Kaminsky
* @version 19-Mar-2012
*/
public class PrimeCountFunctionHyb
{
// Prevent construction.
private PrimeCountFunctionHyb()
{
}
// Shared global variables.
// Sieve in one-million-number chunks.
static final int CHUNK = 1000000;
// World communicator.
static Comm world;
static int rank;
// Command line arguments.
static long x;
static File primeFile;
static LongSchedule thrSchedule;
// Parallel team.
static ParallelTeam team;
// Per-thread sieves.
static Sieve[] sieves;
// List of 32-bit primes.
static Prime32List primeList;
// Per-process prime counter.
static SharedLong primeCount = new SharedLong (0);
// Main program.
/**
* Main program.
*/
public static void main
(String[] args)
throws Exception
{
// Start timing.
long t1 = System.currentTimeMillis();
// World communicator.
Comm.init (args);
world = Comm.world();
rank = world.rank();
// Parse command line arguments.
if (args.length < 2 || args.length > 3) usage();
x = Long.parseLong (args[0]);
if (x < 0) usage();
primeFile = new File (args[1]);
thrSchedule =
args.length == 3 ?
LongSchedule.parse (args[2]) :
LongSchedule.fixed();
// Set up parallel team and per-thread sieves.
team = new ParallelTeam();
sieves = new Sieve [team.getThreadCount()];
for (int i = 0; i < sieves.length; ++ i)
{
sieves[i] = new Sieve (0, CHUNK);
}
// Set up list of 32-bit primes.
primeList = new Prime32List (primeFile);
// Compute sieves in parallel using a two-level schedule for load
// balancing. First-level schedule controlled by -Dpj.schedule.
new WorkerTeam().execute (new WorkerRegion()
{
public void run() throws Exception
{
// Determine number of sieves to calculate.
long ns = (x + CHUNK - 1)/CHUNK;
execute (0, ns - 1, new WorkerLongForLoop()
{
public void run (final long lb, final long ub)
throws Exception
{
team.execute (new ParallelRegion()
{
public void run() throws Exception
{
execute (lb, ub, new LongForLoop()
{
// Per-thread variables plus extra padding.
Sieve thrSieve;
long thrPrimeCount;
long p0, p1, p2, p3, p4, p5, p6, p7;
long p8, p9, pa, pb, pc, pd, pe, pf;
// Second-level schedule controlled by last
// command line argument.
public LongSchedule schedule()
{
return thrSchedule;
}
// Initialize per-thread variables.
public void start()
{
thrSieve = sieves[getThreadIndex()];
thrPrimeCount = 0;
}
// Calculate all sieves.
public void run (long first, long last)
throws Exception
{
for (long lb = first; lb <= last; ++ lb)
{
// Get an iterator for the odd
// primes.
LongIterator iter =
primeList.iterator();
// Calculate the sieve.
thrSieve.lb (lb*CHUNK);
thrSieve.initialize();
thrSieve.sieveOut (iter);
// Count primes <= x left in the
// sieve.
iter = thrSieve.iterator();
long p;
while ((p = iter.next()) != 0 &&
p <= x)
{
++ thrPrimeCount;
}
}
}
// Reduce per-thread prime count into
// per-process prime count.
public void finish()
{
primeCount.addAndGet (thrPrimeCount);
}
});
}
});
}
});
}
});
// Reduce per-process prime counts into process 0.
LongItemBuf buf = LongBuf.buffer (primeCount.longValue());
world.reduce (0, buf, LongOp.SUM);
// Stop timing.
long t2 = System.currentTimeMillis();
// Print the answer. (Add 1 because 2 is a prime.)
if (rank == 0) System.out.println ("pi("+x+") = "+(buf.item + 1));
System.out.println ((t2-t1)+" msec "+rank);
}
// Hidden operations.
/**
* Print a usage message and exit.
*/
private static void usage()
{
System.err.println ("Usage: java -Dpj.np=