primes.cpp File Reference

#include <cassert>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <cstdlib>
#include <cctype>
#include "tbb/parallel_reduce.h"
#include "tbb/task_scheduler_init.h"
#include "tbb/tick_count.h"

Include dependency graph for primes.cpp:

Go to the source code of this file.

Classes
class	Multiples
struct	NumberRange
	A closed range of Number.
class	Sieve
	Loop body for parallel_reduce.
class	SieveRange
	Range of a sieve window.
Typedefs
typedef unsigned long	Number
Functions
int	main (int argc, char *argv[])
Number	ParallelCountPrimes (Number n)
	Count number of primes between 0 and n.
static Number	ParseCommandLine (int argc, char *argv[])
	Parse the command line.
Number	SerialCountPrimes (Number n)
	Count number of primes between 0 and n.
static void	WaitForUser ()
Variables
static Number	GrainSize = 1000
	Grainsize parameter.
static NumberRange	NThread (0, 4)
	Number of threads to use.
static bool	PauseFlag = false
	If true, then at end wait for user to hit return.
static bool	PrintPrimes = false
	If true, then print primes on stdout.

---

Typedef Documentation

typedef unsigned long Number

Definition at line 48 of file primes.cpp.

---

Function Documentation

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 373 of file primes.cpp.

References NumberRange::high, tbb::task_scheduler_init::initialize(), NumberRange::low, NThread, ParallelCountPrimes(), ParseCommandLine(), PauseFlag, SerialCountPrimes(), t0, and WaitForUser().

                                   {
    Number n = ParseCommandLine(argc,argv);

    // Try different numbers of threads
    for( Number p=NThread.low; p<=NThread.high; ++p ) {
        task_scheduler_init init(task_scheduler_init::deferred);
        // If p!=0, we are doing a parallel run
        if( p ) 
            init.initialize(p);

        Number count;
        tick_count t0 = tick_count::now();
        if( p==0 ) {
            count = SerialCountPrimes(n);
        } else {
            count = ParallelCountPrimes(n);
        }
        tick_count t1 = tick_count::now();

        printf("#primes from [2..%lu] = %lu (%.2f sec with ",
            (unsigned long)n, (unsigned long)count, (t1-t0).seconds());
        if( p ) 
            printf("%lu-way parallelism)\n", p );
        else 
            printf("serial code)\n");
    }
    if( PauseFlag ) {
        WaitForUser();
    }
    return 0;
}

Number ParallelCountPrimes

(

Number

n

)

This is the parallel version.

Definition at line 289 of file primes.cpp.

References Sieve::count, GrainSize, Multiples::m, Sieve::multiples, Multiples::n_factor, tbb::parallel_reduce(), PrintPrimes, and test::s.

Referenced by main().

                                       {
    // Two is special case
    Number count = n>=2;
    if( n>=3 ) {
        Sieve s(n);
        count += s.multiples.n_factor;
        if( PrintPrimes ) 
            printf("---\n");
        // Explicit grain size and simple_partitioner() used here instead of automatic grainsize 
        // determination becase we want SieveRange to be decomposed down to GrainSize or smaller.  
        // Doing so improves odds that the working set fits in cache when evaluating Sieve::operator().
        parallel_reduce( SieveRange( s.multiples.m, n, s.multiples.m, GrainSize ), s, simple_partitioner() );
        count += s.count;
    }
    return count;
}

static Number ParseCommandLine	(	int	argc,
		char *	argv[]
	)		[static]

Definition at line 341 of file primes.cpp.

References GrainSize, NumberRange::high, NumberRange::low, NThread, PauseFlag, and NumberRange::set_from_string().

                                                         {
    Number n = 100000000;
    int i = 1;
    if( i<argc && strcmp( argv[i], "pause" )==0 ) {
        PauseFlag = true;
        ++i;
    }
    if( i<argc && !isdigit(argv[i][0]) ) { 
        // Command line is garbled.
        fprintf(stderr,"Usage: %s [['pause'] n [nthread [grainsize]]]\n", argv[0]);
        fprintf(stderr,"where n is a positive integer [%lu]\n",n);
        fprintf(stderr,"      nthread is a non-negative integer, or range of the form low:high [%ld:%lu]\n",NThread.low,NThread.high);
        fprintf(stderr,"      grainsize is an optional postive integer [%lu]\n",GrainSize);
        exit(1);
    }
    if( i<argc )
        n = strtol(argv[i++],0,0);
    if( i<argc )
        NThread.set_from_string(argv[i++]);
    if( i<argc )
        GrainSize = strtol(argv[i++],0,0);
    return n;
}

Number SerialCountPrimes

(

Number

n

)

This is the serial version.

Definition at line 163 of file primes.cpp.

References Multiples::find_primes_in_window(), Multiples::m, Multiples::n_factor, and PrintPrimes.

Referenced by main().

                                     {
    // Two is special case
    Number count = n>=2;
    if( n>=3 ) {
        Multiples multiples(n);
        count += multiples.n_factor;
        if( PrintPrimes ) 
            printf("---\n");
        Number window_size = multiples.m;
        for( Number j=multiples.m; j<=n; j+=window_size ) { 
            if( j+window_size>n+1 ) 
                window_size = n+1-j;
            count += multiples.find_primes_in_window( j, window_size );
        }
    }
    return count;
}

static void WaitForUser

(

)

[static]

Definition at line 365 of file primes.cpp.

Referenced by main().

                          {
    char c;
    printf("Press return to continue\n");
    do {
        c = getchar();
    } while( c!='\n' );
}

---

Variable Documentation

Number GrainSize = 1000 [static]

Definition at line 54 of file primes.cpp.

Referenced by ParallelCountPrimes(), and ParseCommandLine().

NumberRange NThread(0, 4) [static]

Referenced by main(), and ParseCommandLine().

bool PauseFlag = false [static]

Definition at line 338 of file primes.cpp.

Referenced by main(), and ParseCommandLine().

bool PrintPrimes = false [static]

Definition at line 51 of file primes.cpp.

Referenced by ParallelCountPrimes(), and SerialCountPrimes().