partitioner.h

/*
    Copyright 2005-2009 Intel Corporation.  All Rights Reserved.

    The source code contained or described herein and all documents related
    to the source code ("Material") are owned by Intel Corporation or its
    suppliers or licensors.  Title to the Material remains with Intel
    Corporation or its suppliers and licensors.  The Material is protected
    by worldwide copyright laws and treaty provisions.  No part of the
    Material may be used, copied, reproduced, modified, published, uploaded,
    posted, transmitted, distributed, or disclosed in any way without
    Intel's prior express written permission.

    No license under any patent, copyright, trade secret or other
    intellectual property right is granted to or conferred upon you by
    disclosure or delivery of the Materials, either expressly, by
    implication, inducement, estoppel or otherwise.  Any license under such
    intellectual property rights must be express and approved by Intel in
    writing.
*/

#ifndef __TBB_partitioner_H
#define __TBB_partitioner_H

#include "task.h"

namespace tbb {
class affinity_partitioner;

namespace internal {
size_t __TBB_EXPORTED_FUNC get_initial_auto_partitioner_divisor();


class affinity_partitioner_base_v3: no_copy {
    friend class tbb::affinity_partitioner;

    affinity_id* my_array;
    size_t my_size;
    affinity_partitioner_base_v3() : my_array(NULL), my_size(0) {}
    ~affinity_partitioner_base_v3() {resize(0);}

    void __TBB_EXPORTED_METHOD resize( unsigned factor );
    friend class affinity_partition_type;
};

class partition_type_base {
public:
    void set_affinity( task & ) {}
    void note_affinity( task::affinity_id ) {}
    task* continue_after_execute_range( task& ) {return NULL;}
    bool decide_whether_to_delay() {return false;}
    void spawn_or_delay( bool, task& a, task& b ) {
        a.spawn(b);
    }
};

class affinity_partition_type;

template<typename Range, typename Body, typename Partitioner> class start_for;
template<typename Range, typename Body, typename Partitioner> class start_reduce;
template<typename Range, typename Body> class start_reduce_with_affinity;
template<typename Range, typename Body, typename Partitioner> class start_scan;

} // namespace internal


class simple_partitioner {
public:
    simple_partitioner() {}
private:
    template<typename Range, typename Body, typename Partitioner> friend class internal::start_for;
    template<typename Range, typename Body, typename Partitioner> friend class internal::start_reduce;
    template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;

    class partition_type: public internal::partition_type_base {
    public:
        bool should_execute_range(const task& ) {return false;}
        partition_type( const simple_partitioner& ) {}
        partition_type( const partition_type&, split ) {}
    };
};


class auto_partitioner {
public:
    auto_partitioner() {}

private:
    template<typename Range, typename Body, typename Partitioner> friend class internal::start_for;
    template<typename Range, typename Body, typename Partitioner> friend class internal::start_reduce;
    template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;

    class partition_type: public internal::partition_type_base {
        size_t num_chunks;
        static const size_t VICTIM_CHUNKS = 4;
public:
        bool should_execute_range(const task &t) {
            if( num_chunks<VICTIM_CHUNKS && t.is_stolen_task() )
                num_chunks = VICTIM_CHUNKS;
            return num_chunks==1;
        }
        partition_type( const auto_partitioner& ) : num_chunks(internal::get_initial_auto_partitioner_divisor()) {}
        partition_type( partition_type& pt, split ) {
            num_chunks = pt.num_chunks /= 2u;
        }
    };
};

class affinity_partitioner: internal::affinity_partitioner_base_v3 {
public:
    affinity_partitioner() {}

private:
    template<typename Range, typename Body, typename Partitioner> friend class internal::start_for;
    template<typename Range, typename Body> friend class internal::start_reduce_with_affinity;
    template<typename Range, typename Body, typename Partitioner> friend class internal::start_scan;

    typedef internal::affinity_partition_type partition_type;
    friend class internal::affinity_partition_type;
};

namespace internal {

class affinity_partition_type: public no_copy {
    static const unsigned factor = 16;
    static const size_t VICTIM_CHUNKS = 4;

    internal::affinity_id* my_array;
    task_list delay_list;
    unsigned map_begin, map_end;
    size_t num_chunks;
public:
    affinity_partition_type( affinity_partitioner& ap ) {
        __TBB_ASSERT( (factor&(factor-1))==0, "factor must be power of two" ); 
        ap.resize(factor);
        my_array = ap.my_array;
        map_begin = 0;
        map_end = unsigned(ap.my_size);
        num_chunks = internal::get_initial_auto_partitioner_divisor();
    }
    affinity_partition_type(affinity_partition_type& p, split) : my_array(p.my_array) {
        __TBB_ASSERT( p.map_end-p.map_begin<factor || (p.map_end-p.map_begin)%factor==0, NULL );
        num_chunks = p.num_chunks /= 2;
        unsigned e = p.map_end;
        unsigned d = (e - p.map_begin)/2;
        if( d>factor ) 
            d &= 0u-factor;
        map_end = e;
        map_begin = p.map_end = e-d;
    }

    bool should_execute_range(const task &t) {
        if( num_chunks < VICTIM_CHUNKS && t.is_stolen_task() )
            num_chunks = VICTIM_CHUNKS;
        return num_chunks == 1;
    }

    void set_affinity( task &t ) {
        if( map_begin<map_end )
            t.set_affinity( my_array[map_begin] );
    }
    void note_affinity( task::affinity_id id ) {
        if( map_begin<map_end ) 
            my_array[map_begin] = id;
    }
    task* continue_after_execute_range( task& t ) {
        task* first = NULL;
        if( !delay_list.empty() ) {
            first = &delay_list.pop_front();
            while( !delay_list.empty() ) {
                t.spawn(*first);
                first = &delay_list.pop_front();
            }
        }
        return first;
    }
    bool decide_whether_to_delay() {
        // The possible underflow caused by "-1u" is deliberate
        return (map_begin&(factor-1))==0 && map_end-map_begin-1u<factor;
    }
    void spawn_or_delay( bool delay, task& a, task& b ) {
        if( delay )  
            delay_list.push_back(b);
        else 
            a.spawn(b);
    }

    ~affinity_partition_type() {
        // The delay_list can be non-empty if an exception is thrown.
        while( !delay_list.empty() ) {
            task& t = delay_list.pop_front();
            t.destroy(t);
        } 
    }
};

} // namespace internal


} // namespace tbb

#endif /* __TBB_partitioner_H */

---

Copyright © 2005-2009 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.