#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <utility>
#include "tbb/task.h"
#include "tbb/task_scheduler_init.h"
#include "tbb/tick_count.h"
#include "tbb/blocked_range.h"
#include "tbb/concurrent_vector.h"
#include "tbb/concurrent_queue.h"
#include "tbb/concurrent_hash_map.h"
#include "tbb/parallel_while.h"
#include "tbb/parallel_for.h"
#include "tbb/parallel_reduce.h"
#include "tbb/parallel_scan.h"
#include "tbb/pipeline.h"
#include "tbb/atomic.h"
#include "tbb/mutex.h"
#include "tbb/spin_mutex.h"
#include "tbb/queuing_mutex.h"
#include "tbb/tbb_thread.h"

Include dependency graph for Fibonacci.cpp:

Classes
class	ConcurrentHashSerialFibTask
	task for serial method using shared concurrent_hash_map
struct	FibTask
	task class which computes Fibonacci numbers by Lucas formula
class	InputFilter
	filter to fills queue
struct	IntHashCompare
	Hash comparer.
struct	IntRange
	A closed range of int.
struct	Matrix2x2
	Matrix 2x2 class.
class	MultiplyFilter
	filter to process queue
struct	parallel_forFibBody
	Functor for parallel_for which fills the queue.
struct	parallel_reduceFibBody
	Functor for parallel_reduce.
struct	parallel_scanFibBody
	Functor for parallel_scan.
class	parallel_whileFibBody
	Functor for parallel_while which process the queue.
struct	QueueInsertTask
	Parallel queue's filling task.
struct	QueueProcessTask
	Parallel queue's processing task.
struct	QueueStream
	Stream of matrices.
class	SharedSerialFibBody< class >
	Template task class which computes Fibonacci numbers with shared globals.
Typedefs
typedef value(*	MeasureFunc )(int)
typedef concurrent_hash_map < int, value, IntHashCompare >	NumbersTable
	NumbersTable type based on concurrent_hash_map.
typedef long long	value
	type used for Fibonacci number computations
Functions
value	ConcurrentHashSerialFib (int n)
	Root function.
int	main (int argc, char *argv[])
	program entry
void	Matrix2x2Multiply (const value a[2][2], const value b[2][2], value c[2][2])
	Raw arrays matrices multiply.
value	Measure (const char *name, MeasureFunc func, int n)
	Measure ticks count in loop [2..n].
value	parallel_reduceFib (int n)
	Root function.
value	parallel_scanFib (int n)
	Root function.
value	ParallelPipeFib (int n)
	Root function.
value	ParallelQueueFib (int n)
	Root function.
value	ParallelTaskFib (int n)
	Root function.
value	SerialFib (int n)
	Plain serial sum.
value	SerialMatrixFib (int n)
	Serial n-1 matrices multiplication.
value	SerialQueueFib (int n)
	Introducing of queue method in serial.
value	SerialRecursiveFib (int n)
	Recursive summing. Just for complete list of serial algorithms, not used.
value	SerialVectorFib (int n)
	Trying to use concurrent_vector.
template<class M >
value	SharedSerialFib (int n)
	Root function.
Variables
static const Matrix2x2	Matrix1110 (1, 1, 1, 0)
	Default matrix to multiply.
value	SharedA = 0
	Shared glabals.
value	SharedB = 1
int	SharedI = 1
int	SharedN
static tick_count	t0
	Tick count for start.
static bool	Verbose = false
	Verbose output flag.

Typedef Documentation

typedef value(* MeasureFunc)(int)

Definition at line 530 of file Fibonacci.cpp.

typedef concurrent_hash_map<int, value, IntHashCompare> NumbersTable

Definition at line 193 of file Fibonacci.cpp.

typedef long long value

Definition at line 69 of file Fibonacci.cpp.

Function Documentation

value ConcurrentHashSerialFib ( int n )

Definition at line 221 of file Fibonacci.cpp.

References tbb::task_list::push_back().

Referenced by main().

{
    NumbersTable Fib; 
    bool okay;
    okay = Fib.insert( make_pair(0, 0) ); assert(okay); // assign initial values
    okay = Fib.insert( make_pair(1, 1) ); assert(okay);

    task_list list;
    // allocate tasks
    list.push_back(*new(task::allocate_root()) ConcurrentHashSerialFibTask(Fib, n));
    list.push_back(*new(task::allocate_root()) ConcurrentHashSerialFibTask(Fib, n));
    task::spawn_root_and_wait(list);
    NumbersTable::const_accessor fresult;
    okay = Fib.find( fresult, n );
    assert(okay);
    return fresult->second;
}

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

Definition at line 544 of file Fibonacci.cpp.

References ConcurrentHashSerialFib(), IntRange::high, IntRange::low, Measure(), NThread, ntrial, parallel_reduceFib(), parallel_scanFib(), ParallelPipeFib(), ParallelQueueFib(), ParallelTaskFib(), SerialFib(), SerialMatrixFib(), SerialQueueFib(), SerialVectorFib(), IntRange::set_from_string(), and Verbose.

{
    if(argc>1) Verbose = true;
    int NumbersCount = argc>1 ? strtol(argv[1],0,0) : 500;
    IntRange NThread(1,4);// Number of threads to use.
    if(argc>2) NThread.set_from_string(argv[2]);
    unsigned long ntrial = argc>3? (unsigned long)strtoul(argv[3],0,0) : 1;
    value result, sum;

    if(Verbose) printf("Fibonacci numbers example. Generating %d numbers..\n",  NumbersCount);

    result = Measure("Serial loop", SerialFib, NumbersCount);
    sum = Measure("Serial matrix", SerialMatrixFib, NumbersCount); assert(result == sum);
    sum = Measure("Serial vector", SerialVectorFib, NumbersCount); assert(result == sum);
    sum = Measure("Serial queue", SerialQueueFib, NumbersCount); assert(result == sum);
    // now in parallel
    for( unsigned long i=0; i<ntrial; ++i ) {
        for(int threads = NThread.low; threads <= NThread.high; threads *= 2)
        {
            task_scheduler_init scheduler_init(threads);
            if(Verbose) printf("\nThreads number is %d\n", threads);

            sum = Measure("Shared serial (mutex)\t", SharedSerialFib<mutex>, NumbersCount); assert(result == sum);
            sum = Measure("Shared serial (spin_mutex)", SharedSerialFib<spin_mutex>, NumbersCount); assert(result == sum);
            sum = Measure("Shared serial (queuing_mutex)", SharedSerialFib<queuing_mutex>, NumbersCount); assert(result == sum);
            sum = Measure("Shared serial (Conc.HashTable)", ConcurrentHashSerialFib, NumbersCount); assert(result == sum);
            sum = Measure("Parallel while+for/queue", ParallelQueueFib, NumbersCount); assert(result == sum);
            sum = Measure("Parallel pipe/queue\t", ParallelPipeFib, NumbersCount); assert(result == sum);
            sum = Measure("Parallel reduce\t\t", parallel_reduceFib, NumbersCount); assert(result == sum);
            sum = Measure("Parallel scan\t\t", parallel_scanFib, NumbersCount); assert(result == sum);
            sum = Measure("Parallel tasks\t\t", ParallelTaskFib, NumbersCount); assert(result == sum);
        }

    #ifdef __GNUC__
        if(Verbose) printf("Fibonacci number #%d modulo 2^64 is %lld\n\n", NumbersCount, result);
    #else
        if(Verbose) printf("Fibonacci number #%d modulo 2^64 is %I64d\n\n", NumbersCount, result);
    #endif
    }
    if(!Verbose) printf("TEST PASSED\n");
    return 0;
}

void Matrix2x2Multiply	(	const value	a[2][2],
		const value	b[2][2],
		value	c[2][2]
	)

Referenced by SerialMatrixFib().

value Measure	(	const char *	name,
		MeasureFunc	func,
		int	n
	)

Definition at line 532 of file Fibonacci.cpp.

References t0, and Verbose.

Referenced by main().

{
    value result;
    if(Verbose) printf("%s",name);
    t0 = tick_count::now();
    for(int number = 2; number <= n; number++)
        result = func(number);
    if(Verbose) printf("\t- in %f msec\n", (tick_count::now() - t0).seconds()*1000);
    return result;
}

value parallel_reduceFib ( int n )

Definition at line 417 of file Fibonacci.cpp.

References tbb::parallel_reduce(), parallel_reduceFibBody::sum, and Matrix2x2::v.

Referenced by main().

{
    parallel_reduceFibBody b;
    parallel_reduce(blocked_range<int>(2, n, 3), b); // do parallel reduce on range [2, n) for b
    return b.sum.v[0][0];
}

value parallel_scanFib ( int n )

Definition at line 452 of file Fibonacci.cpp.

References tbb::parallel_scan(), parallel_scanFibBody::sum, and Matrix2x2::v.

Referenced by main().

{
    parallel_scanFibBody b;
    parallel_scan(blocked_range<int>(1/*one less, because body skip first*/, n, 3), b);
    return b.sum.v[0][0];
}

value ParallelPipeFib ( int n )

Definition at line 373 of file Fibonacci.cpp.

References tbb::pipeline::add_filter(), tbb::pipeline::clear(), M, Matrix1110, InputFilter::Queue, and tbb::pipeline::run().

Referenced by main().

{
    InputFilter input( n-1 );
    MultiplyFilter process;
    // Create the pipeline
    pipeline pipeline;
    // add filters
    pipeline.add_filter( input ); // first
    pipeline.add_filter( process ); // second

    input.Queue.push( Matrix1110 );
    // Run the pipeline
    pipeline.run( n ); // must be larger then max threads number
    pipeline.clear(); // do not forget clear the pipeline

    assert( input.Queue.unsafe_size()==1 );
    Matrix2x2 M; 
    bool result = input.Queue.try_pop( M ); // get last element
    assert( result );
    return M.v[0][0]; // get value
}

value ParallelQueueFib ( int n )

Definition at line 320 of file Fibonacci.cpp.

References M, QueueStream::producer_is_done, tbb::task_list::push_back(), QueueStream::Queue, and stream.

Referenced by main().

{
    QueueStream stream;
    stream.producer_is_done = false;
    task_list list;
    list.push_back(*new(task::allocate_root()) QueueInsertTask( n, stream ));
    list.push_back(*new(task::allocate_root()) QueueProcessTask( stream ));
    // If there is only a single thread, the first task in the list runs to completion
    // before the second task in the list starts.
    task::spawn_root_and_wait(list);
    assert(stream.Queue.unsafe_size() == 1); // it is easy to lose some work
    Matrix2x2 M; 
    bool result = stream.Queue.try_pop( M ); // get last matrix
    assert( result );
    return M.v[0][0]; // and result number
}

value ParallelTaskFib ( int n )

Definition at line 493 of file Fibonacci.cpp.

Referenced by main().

                             { 
    value sum;
    FibTask& a = *new(task::allocate_root()) FibTask(n, sum);
    task::spawn_root_and_wait(a);
    return sum;
}

value SerialFib ( int n )

Definition at line 90 of file Fibonacci.cpp.

Referenced by main().

{
    if(n < 2)
        return n;
    value a = 0, b = 1, sum; int i;
    for( i = 2; i <= n; i++ )
    {   // n is really index of Fibonacci number
        sum = a + b; a = b; b = sum;
    }
    return sum;
}

value SerialMatrixFib ( int n )

Definition at line 102 of file Fibonacci.cpp.

References Matrix2x2Multiply().

Referenced by main().

{
    value c[2][2], a[2][2] = {{1, 1}, {1, 0}}, b[2][2] = {{1, 1}, {1, 0}}; int i;
    for(i = 2; i < n; i++)
    {   // Using condition to prevent copying of values
        if(i & 1) Matrix2x2Multiply(a, c, b);
        else      Matrix2x2Multiply(a, b, c);
    }
    return (i & 1) ? c[0][0] : b[0][0]; // get result from upper left cell
}

value SerialQueueFib ( int n )

Definition at line 123 of file Fibonacci.cpp.

References Matrix1110, and Matrix2x2::v.

Referenced by main().

{
    concurrent_queue<Matrix2x2> Q;
    for(int i = 1; i < n; i++)
        Q.push(Matrix1110);
    Matrix2x2 A, B;
    while(true) {
        while( !Q.try_pop(A) ) this_tbb_thread::yield();
        if(Q.empty()) break;
        while( !Q.try_pop(B) ) this_tbb_thread::yield();
        Q.push(A * B);
    }
    return A.v[0][0];
}

value SerialRecursiveFib ( int n )

Definition at line 113 of file Fibonacci.cpp.

{
    value result;
    if(n < 2)
        result = n;
    else
        result = SerialRecursiveFib(n - 1) + SerialRecursiveFib(n - 2);
    return result;
}

value SerialVectorFib ( int n )

Definition at line 138 of file Fibonacci.cpp.

References tbb::concurrent_vector< T, A >::grow_by(), and tbb::concurrent_vector< T, A >::grow_to_at_least().

Referenced by main().

{
    concurrent_vector<value> A;
    A.grow_by(2);
    A[0] = 0; A[1] = 1;
    for( int i = 2; i <= n; i++)
    {
        A.grow_to_at_least(i+1);
        A[i] = A[i-1] + A[i-2];
    }
    return A[n];
}

template<class M >

value SharedSerialFib ( int n )

Definition at line 178 of file Fibonacci.cpp.

References M, tbb::parallel_for(), SharedA, SharedB, SharedI, and SharedN.

{
    SharedA = 0; SharedB = 1; SharedI = 1; SharedN = n; M mutex;
    parallel_for( blocked_range<int>(0,4,1), SharedSerialFibBody<M>( mutex ) );
    return SharedB;
}