Skip to Main Content
Intel Threading Building Blocks
book

Intel Threading Building Blocks

by James Reinders
July 2007
Intermediate to advanced content levelIntermediate to advanced
332 pages
10h 4m
English
O'Reilly Media, Inc.
Content preview from Intel Threading Building Blocks

ParallelPrime

This example is a parallel version of the Sieve of Eratosthenes, which finds prime numbers, written using parallel_reduce. This program computes prime numbers up to n. The algorithm here is a fairly efficient version of the Sieve of Eratosthenes, even though the Sieve is not the most efficient way to find primes. Figure 11-5 shows how the Sieve of Eratosthenes finds primes through an elimination process.

The parallel version demonstrates how to use parallel_reduce, and in particular, how to exploit lazy splitting.

Finding primes via the Sieve of Eratosthenes

Figure 11-5. Finding primes via the Sieve of Eratosthenes

For comparison purposes, let’s look at a serial version of the Sieve in Example 11-21.

Tip

Aha! Parallel and serial versions of code differ in the middle, and clever coding can have a shared driver and can share low-level routines, leaving only a little code different.

Example 11-21. Serial version of count primes

//! Count number of primes between 0 and n
/** This is the serial version. */
Number SerialCountPrimes( Number n ) {
    // 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;
}

The equivalent code to do this ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Intel® Xeon Phi™ Coprocessor Architecture and Tools: The Guide for Application Developers

Intel® Xeon Phi™ Coprocessor Architecture and Tools: The Guide for Application Developers

Rezaur Rahman

Publisher Resources

ISBN: 9780596514808Errata Page