CnC
default_tuner.h
00001 /* *******************************************************************************
00002  *  Copyright (c) 2007-2014, Intel Corporation
00003  *
00004  *  Redistribution and use in source and binary forms, with or without
00005  *  modification, are permitted provided that the following conditions are met:
00006  *
00007  *  * Redistributions of source code must retain the above copyright notice,
00008  *    this list of conditions and the following disclaimer.
00009  *  * Redistributions in binary form must reproduce the above copyright
00010  *    notice, this list of conditions and the following disclaimer in the
00011  *    documentation and/or other materials provided with the distribution.
00012  *  * Neither the name of Intel Corporation nor the names of its contributors
00013  *    may be used to endorse or promote products derived from this software
00014  *    without specific prior written permission.
00015  *
00016  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
00017  *  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00018  *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00019  *  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
00020  *  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00021  *  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
00022  *  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
00023  *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
00024  *  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
00025  *  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00026  ********************************************************************************/
00027 
00028 /*
00029   CnC tuner interface(s).
00030 */
00031 
00032 #ifndef CNC_DEFAULT_TUNER_H_ALREADY_INCLUDED
00033 #define CNC_DEFAULT_TUNER_H_ALREADY_INCLUDED
00034 
00035 #include <cnc/internal/cnc_api.h>
00036 #include <cnc/default_partitioner.h>
00037 #include <cnc/internal/step_delayer.h>
00038 #include <cnc/internal/cnc_tag_hash_compare.h>
00039 #include <cnc/internal/no_range.h>
00040 #include <cnc/internal/no_tag_table.h>
00041 #include <cnc/internal/hash_tag_table.h>
00042 #include <cnc/internal/item_properties.h>
00043 #include <cnc/internal/item_properties.h>
00044 #include <cnc/internal/dist/distributor.h>
00045 #include <cnc/internal/tbbcompat.h>
00046 #include <tbb/atomic.h>
00047 #include <tbb/concurrent_unordered_set.h>
00048 //#include <tbb/concurrent_hash_map.h>
00049 
00050 namespace CnC {
00051 
00052     template< class T > class context;
00053     namespace Internal {
00054         template< class Tag, class Range, class StepColl, class RangeStepI, class TIR, bool deps > struct range_step;
00055     }
00056 
00057     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00058     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00059 
00060     // Key-words tuning
00061     enum {
00062         COMPUTE_ON_LOCAL       = -2,  ///< let tuner::compute_on return COMPUTE_ON_LOCAL if the step should be executed locally
00063         COMPUTE_ON_ROUND_ROBIN = -3,  ///< let tuner::compute_on return COMPUTE_ON_ROUND_ROBIN to let the scheduler distribute it in a round-robin fashion
00064         COMPUTE_ON_ALL         = -4,  ///< let tuner::compute_on return COMPUTE_ON_ALL if the step should be executed on all processes, as well as locally
00065         COMPUTE_ON_ALL_OTHERS  = -5,  ///< let tuner::compute_on return COMPUTE_ON_ALL_OTHERS if the step should be executed on all processes, but not locally    
00066         PRODUCER_UNKNOWN    = -6,  ///< producer process of dependent item is unknown
00067         PRODUCER_LOCAL      = -7,  ///< producer process of dependent item is local process
00068         CONSUMER_UNKNOWN    = -8,  ///< consumer process of given item is unkown
00069         CONSUMER_LOCAL      = -9,  ///< consumer process of given item is the local process
00070         CONSUMER_ALL        = -10, ///< all processes consume given item
00071         CONSUMER_ALL_OTHERS = -11, ///< all processes but this consume given item
00072         NO_GETCOUNT         = Internal::item_properties::NO_GET_COUNT,   ///< no get-count specified
00073         AFFINITY_HERE       = Internal::scheduler_i::AFFINITY_HERE       ///< default affinity to current thread
00074     };
00075 
00076     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00077     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00078 
00079     /// Functionality that might be needed to implement all kinds of tuners.
00080     /// Always try to use higher level tuners which derive from this.
00081     /// Always use virtual inheritance (see higher level tuners).
00082     class tuner_base
00083     {
00084     public:
00085         /// returns id/rank of calling process
00086         /// defaults to 0 if running on one process only.
00087         inline static int myPid()
00088         {
00089             return Internal::distributor::myPid();
00090         }
00091         /// return total number of processes participating in this programm execution
00092         /// defaults to 1 if running on one process only.
00093         inline static int numProcs()
00094         {
00095             return Internal::distributor::numProcs();
00096         }
00097         /// returns number of threads used by scheduler in given context
00098         template< typename Ctxt >
00099         inline static int numThreads( const Ctxt & ctxt )
00100         {
00101             return ctxt.numThreads();
00102         }
00103     };
00104 
00105 
00106     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00107     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00108 
00109     /// \brief Default (NOP) implementations of the step_tuner interface.
00110     ///
00111     /// Also defines the interface a user-provided tuner must satisfy.
00112     /// Derive your tuner from this (to avoid implementing the entire interface).
00113     ///
00114     /// It is recommended that your tuner does not implement the methods as templates.
00115     /// Instead, you should use the actual types that it expects.
00116     ///
00117     /// \#include <cnc/default_tuner.h>
00118     template< bool check_deps = true >
00119     struct /*CNC_API*/ step_tuner : public virtual tuner_base
00120     {
00121         /// \brief Allows definition of priorities to individual steps (which are identified by the tag).
00122         /// \return the default implementation always return 1.
00123         /// \param tag the tag which identifies the step to be executed
00124         /// \param arg the argument as passed to context< Derived >::prescribed (usually the context)
00125         /// \see also CNCROOT/samples/floyd_warshall
00126         template< typename Tag, typename Arg >
00127         int priority( const Tag & tag, Arg & arg ) const
00128         {
00129             return 1;
00130         }
00131 
00132         /// \brief Allows declaration of data dependencies (to items) of
00133         /// given step (identified by the tag).
00134         ///
00135         /// When a step-instance is prescribed through a corresponding
00136         /// tag_collection::put, this method will be called.  You can
00137         /// declare dependencies to items by calling
00138         /// dC.depends( item_collection, dependent_item_tag )
00139         /// for every item the step is going to 'get' in its execute
00140         /// method. The actual step execution will be delayed until
00141         /// all dependencies can be satisfied.  The default
00142         /// implementation does nothing (NOP). Your implementation
00143         /// must accept dC by reference (T&).
00144         /// \param tag the tag which identifies the step to be executed.
00145         /// \param arg the argument as passed to context< Derived >::prescribed
00146         ///            (usually the context)
00147         /// \param dC  opaque object (must be by reference!) providing method depends
00148         ///            to declare item dependencies
00149         template< typename Tag, typename Arg, typename T >
00150         void depends( const Tag & tag, Arg & arg, T & dC ) const
00151         {
00152         }
00153 
00154         /// \brief Returns whether the step should be pre-scheduled 
00155         ///
00156         /// Pre-scheduling provides an alternative method for detecting
00157         /// data dependencies, in particular if it is combined with
00158         /// item_collection::unsafe_get and context::flush_gets() in the
00159         /// step-code.
00160         ///
00161         /// The step instance will be run immediately when prescribed
00162         /// by a tag_collection::put. All items that are not yet
00163         /// available when accessed by the blocking
00164         /// item_collection::get() and/or non-blocking
00165         /// item_collection::unsafe_get() methods will automatically
00166         /// be treated as dependent items. The pre-run will end at the
00167         /// first unsuccessful blocking get or at
00168         /// context::flush_gets() (if any items got through
00169         /// item_collection::unsafe_get() were unavailable). Execution
00170         /// stops by throwing an exception, similar to un unsuccessful
00171         /// item_collection::get(). The step execution will be delayed
00172         /// until all detected dependencies can be satisfied.
00173         /// \note If all dependent items are available in the pre-scheduling
00174         ///       execution the step gets fully executed. This can lead to
00175         ///       very deep call-stacks if items are always available and
00176         ///       new control is produced in steps.
00177         bool preschedule() const
00178         {
00179             return false;
00180         }
00181                   
00182         /// \brief Tell the scheduler the preferred thread for executing given step
00183         ///
00184         /// Not all schedulers might actually evaluate this call (see \ref scheduler);
00185         /// it involves a virtual function call whenever a step is (re-)scheduled.
00186         /// This feature is most useful in combination with 
00187         /// the CNC_PIN_THREADS environment variable (\ref priorpin).
00188         /// \return thread id or AFFINITY_HERE (default)
00189         template< typename Tag, typename Arg >
00190         int affinity( const Tag & /*tag*/, Arg & /*arg*/ ) const
00191         {
00192             return AFFINITY_HERE;
00193         }
00194 
00195         /// \brief tell the scheduler on which process to run the step
00196         /// (or range of steps) (distCnC)
00197         ///
00198         /// return process id where the step will be executed, or
00199         /// COMPUTE_ON_ROUND_ROBIN, or COMPUTE_ON_LOCAL, or
00200         /// COMPUTE_ON_ALL, or COMPUTE_ON_ALL_OTHERS
00201         template< typename Tag, typename Arg >
00202         int compute_on( const Tag & /*tag*/, Arg & /*arg*/ ) const
00203         {
00204             return COMPUTE_ON_ROUND_ROBIN;
00205         }
00206 
00207         /// \brief true if steps launched through ranges consume items
00208         /// or need global locking, false otherwise.
00209         ///
00210         /// Avoiding checks for dependencies and global locks saves
00211         /// overhead and will perform better (e.g. for parallel_for).
00212         /// Safe execution (with checks) is the default (check_deps
00213         /// template argument).
00214         static const bool check_deps_in_ranges = check_deps;
00215 
00216         /// \brief check for cancelation of given step
00217         ///
00218         /// \return true if step was canceled, false otherwise (default)
00219         /// \note Must be thread-safe.
00220         /// Runtime will try to not execute the step, but it might still get executed.
00221         /// Best effort - but no guarantees.
00222         /// Canceling steps makes all determinism guarantees void.
00223         ///
00224         /// For distributed memory your implementation might require to sync its state
00225         /// across processes. Currently there is no API exposed to do that conveniently.
00226         /// However, an example implementatino CnC::cancel_tuner is provided which
00227         /// works on distributed memory.
00228         /// \see also CNCROOT/samples/floyd_warshall
00229         template< typename Tag, typename Arg >
00230         int was_canceled( const Tag & /*tag*/, Arg & /*arg*/ ) const
00231         {
00232             return false;
00233         }
00234 
00235         /// \brief check if given step-instance needs to be executed sequentially
00236         /// \return false by default, if true, step-instance gets queued for execution
00237         ///         in a sequential phase (after all workers are quienscent)
00238         template< typename Tag, typename Arg >
00239         bool sequentialize( const Tag & /*tag*/, Arg & /*arg*/ ) const
00240         {
00241             return false;
00242         }
00243     };
00244 
00245     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00246 
00247     /// \brief Default (NOP) implementations of the pfor_tuner interface.
00248     ///
00249     /// Also defines the interface a user-provided step-tuner must satisfy.
00250     /// Derive your tuner from this (to avoid implementing the entire interface).
00251     ///
00252     /// It is recommended that your tuner does not implement the methods as templates.
00253     /// Instead, you should use the actual types that it expects.
00254     ///
00255     /// \#include <cnc/default_tuner.h>
00256     template< bool check_deps = true, typename Partitioner = default_partitioner<>  >
00257     struct /*CNC_API*/ pfor_tuner : public virtual tuner_base
00258     {
00259         template< typename Tag, typename Arg >
00260         int priority( const Tag & tag, Arg & arg ) const
00261         {
00262             return 1;
00263         }
00264 
00265         template< typename Tag, typename Arg, typename T >
00266         void depends( const Tag & tag, Arg & arg, T & dC ) const
00267         {
00268         }
00269 
00270         bool preschedule() const
00271         {
00272             return false;
00273         }
00274 
00275         template< typename Tag, typename Arg >
00276         int affinity( const Tag & /*tag*/, Arg & /*arg*/ ) const
00277         {
00278             return AFFINITY_HERE;
00279         }
00280 
00281         static const bool check_deps_in_ranges = check_deps;
00282 
00283         typedef Partitioner partitioner_type;
00284 
00285         partitioner_type partitioner() const
00286         {
00287             return typename pfor_tuner< check_deps, Partitioner >::partitioner_type();
00288         }
00289     };
00290 
00291     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00292     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00293 
00294     namespace CT {
00295 #ifdef _DIST_CNC_
00296         static const char SINGLE  = 0; // single tag
00297         static const char ALL     = 1; // cancel all
00298         static const char RESET   = 2; // reset
00299 #endif
00300     }
00301 
00302     /// \brief Step tuner with convenient cancelation capabilities
00303     ///
00304     /// Allows cancelation of individual step-instances by their tags as well as
00305     /// canceling all instances at once. All cancelation requests are "active" until
00306     /// unsafe_reset() is called (or the tuner is destructed).
00307     ///
00308     /// To use it, you need a cancel_tuner object in your context which you pass
00309     /// to the constructor of the respective step_collection.
00310     ///
00311     /// It works on distributed memory but might perform poorly if used frequently.
00312     ///
00313     /// \param Tag tag-type
00314     /// \param check_deps if false, avoid some mechanics to handle unavailable items
00315     /// \param Hasher hash-functor for Tag, defaults to tbb::tbb_hash< Tag >
00316     /// \param Equality equality operator for Tag, defaults to std::equal_to< Tag >
00317     /// \note It is assumed that cancelation per instance happens relatively rarely. Hence
00318     ///       no automatic garbage collection of the tags is provided. If you cancel individual
00319     ///       step-instances frequently, it is recommended to prune the internal data structure
00320     ///       from time to time in a safe state through unsafe_reset().
00321     /// \see also CNCROOT/samples/floyd_warshall
00322     template< typename Tag, bool check_deps = true,
00323               typename Hasher = cnc_hash< Tag >, typename Equality = cnc_equal< Tag > >
00324     class cancel_tuner : public step_tuner< check_deps >, public Internal::distributable
00325     {
00326     public:
00327         template< typename C >
00328         cancel_tuner( C & ctxt )
00329             : Internal::distributable( "cancel_tuner" ), m_context( ctxt ), m_canceledTags(), m_cancelAll()
00330         {
00331             m_context.subscribe( this );
00332             m_cancelAll = false;
00333         }
00334 
00335         ~cancel_tuner()
00336         {
00337             m_context.unsubscribe( this );
00338         }
00339 
00340         /// \brief cancel given step (identified by tag)
00341         void cancel( const Tag & t, bool from_msg = false  )
00342         {
00343             if( ! m_cancelAll ) {
00344 #ifdef _DIST_CNC_
00345                 if( !from_msg && Internal::distributor::numProcs() > 1 ) {
00346                     serializer * _ser = m_context.new_serializer( this );
00347                     (*_ser) & CT::SINGLE & t;
00348                     m_context.bcast_msg( _ser ); 
00349                 }
00350 #endif
00351                 m_canceledTags.insert( t );
00352             }
00353         }
00354 
00355         /// \brief cancel all steps
00356         void cancel_all( bool from_msg = false )
00357         {
00358 #ifdef _DIST_CNC_
00359             if( !from_msg && Internal::distributor::numProcs() > 1 ) {
00360                 serializer * _ser = m_context.new_serializer( this );
00361                 (*_ser) & CT::ALL;
00362                 m_context.bcast_msg( _ser ); 
00363             }
00364 #endif
00365             m_cancelAll = true;
00366         }
00367 
00368         void unsafe_reset( )
00369         {
00370             unsafe_reset( true );
00371         }
00372 
00373         /// \brief implements/overwrites step_tuner::was_canceled(...)
00374         template< typename Arg >
00375         int was_canceled( const Tag & tag, Arg & /*arg*/ ) const
00376         {
00377             return m_cancelAll == true || m_canceledTags.count( tag ) > 0;
00378         }
00379 
00380         // from distributable
00381         virtual void recv_msg( serializer * ser )
00382         {
00383 #ifdef _DIST_CNC_
00384             CNC_ASSERT( Internal::distributor::active() );
00385             char _msg;
00386             (*ser) & _msg;
00387             switch( _msg ) {
00388             case CT::SINGLE :
00389                 Tag _tag;
00390                 (*ser) & _tag;
00391                 this->cancel( _tag, true );
00392                 break;
00393             case CT::ALL :
00394                 this->cancel_all( true );
00395                 break;
00396             case CT::RESET :
00397                 this->unsafe_reset( false );
00398                 break;
00399             default:
00400                 CNC_ABORT( "Unexpected message received (cancel_tuner)." );
00401             }
00402 #endif
00403         }
00404 
00405     private:
00406         /// \brief reset all current cancel states
00407         /// \note not thread-safe, to be called in safe state only
00408         ///       (between program start or calling context::wait() and putting the first tag or item).
00409         virtual void unsafe_reset( bool dist )
00410         {
00411 #ifdef _DIST_CNC_
00412             if( dist && Internal::distributor::numProcs() > 1 ) {
00413                 serializer * _ser = m_context.new_serializer( this );
00414                 (*_ser) & CT::RESET;
00415                 m_context.bcast_msg( _ser ); 
00416             }
00417 #endif
00418             m_canceledTags.clear();
00419             m_cancelAll = false;
00420         }
00421 
00422         Internal::distributable_context & m_context;
00423         tbb::concurrent_unordered_set< Tag, Hasher, Equality > m_canceledTags;
00424         tbb::atomic< bool > m_cancelAll;
00425     };
00426 
00427 
00428     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00429     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00430 
00431     /// \brief Default implementations of the item-tuner interface for item-collections
00432     ///
00433     /// Usually you will not need to use this directly for anything else than documentation and interface.
00434     template< template< typename T, typename I, typename A > class TT >
00435     struct item_tuner : public virtual tuner_base
00436     {
00437         /// \brief Class which manages item creation/uncreation..
00438         ///
00439         /// item_allocator::type must provide 
00440         ///        item_type * create( const item_type & org ) const;
00441         ///        void uncreate( item_type * item ) const;
00442         ///
00443         /// Only C++0x allows template aliasing, need to use an indirection
00444         template< typename Item >
00445         struct item_allocator
00446         {
00447             //            typedef CnC::Internal::item_manager_default< Item > type;
00448             typedef tbb::scalable_allocator< Item > type;
00449         };
00450 
00451         /// \brief Defines the type of the internal data store.
00452         ///
00453         /// It forwards the functionality of the template parameter template.
00454         /// The expected interface of the template is not yet exposed.
00455         /// Use hashmap_tuner or vector_tuner to derive your own tuner.
00456         template< typename Tag, typename Item, typename Coll >
00457         struct table_type : public TT< Tag, Item, Coll >
00458         {
00459             table_type( const Coll * c, size_t sz = 0 ) : TT< Tag, Item, Coll >( c, sz ) {}
00460         };
00461         
00462         /// \brief Initialize the internal storage.
00463         ///
00464         /// Can be used to configure the storage table.
00465         /// Called in the collection constructor.
00466         template< typename Tag, typename Item, typename Coll >
00467         void init_table( TT< Tag, Item, Coll > & stbl ) const
00468         {}
00469 
00470         /// \brief Allows specifying the number of gets to the given item.
00471         ///
00472         /// After get_count() many 'get()'s the item can be removed from the collection.
00473         /// By default, the item is not removed until the collection is deleted.
00474         /// Gets by the environment are ignored, use CnC::NO_GETCOUNT for items 
00475         /// which are consumed by the environment.
00476         /// \param tag the tag which identifies the item
00477         /// \return number of expected gets to this item, or CNC::NO_GETCOUNT
00478         template< typename Tag >
00479         int get_count( const Tag & tag ) const
00480         {
00481             return NO_GETCOUNT;
00482         }
00483 
00484         /// \brief Tells the scheduler on which process(es) this item is going to be consumed
00485         ///
00486         /// return process id where the item will be consumed (get), or CONSUMER_UNKNOWN (default)
00487         ///     or std::vector<int>, containing all ids of consuming processes.
00488         ///        To indicate that the consumer processes are unknown, return an empty vector.
00489         ///        The vector must contain special values like CONSUMER_LOCAL.
00490         /// If not CnC::CONSUMER_UKNOWN (or empty vector), this declaration will overwrite what
00491         /// the step-tuner might declare in depends.
00492         /// Providing this method leads to the most efficient communication pattern for
00493         /// to getting the data to where it is needed.
00494         /// \param tag the tag which identifies the item
00495         template< typename Tag >
00496         int consumed_on( const Tag & tag ) const
00497         {
00498             return CONSUMER_UNKNOWN;
00499         }
00500 
00501         /// \brief Tells the scheduler on which process(es) this item is going to be produced
00502         ///
00503         /// return process id where the item will be produced. If unknown return CnC::PRODUCER_UNKNOWN.
00504         /// return PRODUCER_LOCAL if local process is the owner.
00505         /// Implementing this method reduces the communication cost for locating and sending data.
00506         /// Implementing item_tuner::consumed_on is more efficient, but might be more complicated.
00507         /// Will be evaluated only if item_tuner::consumed_on returns CnC::CONSUMER_UNKNOWN
00508         /// \param tag the tag which identifies the item
00509         template< typename Tag >
00510         int produced_on( const Tag & tag ) const
00511         {
00512             return PRODUCER_UNKNOWN;
00513         }
00514     };
00515 
00516     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00517 
00518     namespace Internal {
00519         template< typename Tag, typename ItemT, typename Coll > class hash_item_table;
00520         template< typename Tag, typename ItemT, typename Coll > class vec_item_table;
00521     }
00522 
00523     /// \brief The tuner base for hashmap-based item-tuners.
00524     ///
00525     /// The internal hash-map uses cnc_tag_hash_compare. If your
00526     /// tag-type is not supported by default, you need to provide a
00527     /// template specialization for it.
00528     struct hashmap_tuner : public item_tuner< Internal::hash_item_table >
00529     {
00530     };
00531 
00532     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00533 
00534     /// \brief The tuner base for vector-based item-tuners.
00535     ///
00536     /// Your tags must be convertable to and from size_t.  You must
00537     /// provide the maximum value before accessing the collection
00538     /// (constructor or set_max).  The runtime will allocate as many
00539     /// slots. Hence, use this only if your tags-space is dense,
00540     /// without a large offset and if it is not too large.
00541     struct vector_tuner : public item_tuner< Internal::vec_item_table >
00542     {
00543     };
00544 
00545     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00546     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00547 
00548     /// \brief Default implementations of the tag-tuner interface for tag-collections
00549     ///
00550     /// Use this if you are going put ranges. Optional argument is a custom partitioner. 
00551     /// Ranges don't work with memoization (yet)
00552     template< typename Range = Internal::no_range, typename Partitioner = default_partitioner<> >
00553     struct tag_tuner : public virtual tuner_base
00554     {
00555         /// A tag tuner must provide the type of the range, default is no range
00556         typedef Range range_type;
00557         /// A tag tuner must provide a tag-table type; default is no tag-table
00558         typedef Internal::no_tag_table tag_table_type;
00559         /// \brief The type of the partitioner
00560         typedef Partitioner partitioner_type;
00561 
00562         /// \brief return a partitioner for range-based features, such as parallel_for
00563         /// \see default_partitioner for the expected signature of partitioners
00564         /// overwrite partitioner() if it doesn't come with default-constructor or
00565         /// if the default constructor is insufficient.
00566         partitioner_type partitioner() const
00567         {
00568             return typename tag_tuner< Range, Partitioner >::partitioner_type();
00569         }
00570 
00571         /// return true if tag memoization is wanted; returns false by default (with no_tag_table)
00572         bool preserve_tags() const
00573         {
00574             return false;
00575         };
00576     };
00577 
00578     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00579     
00580     /// Use this if your tag-collection should preserve tags (memoization)
00581     /// \note Memoization doesn't work with ranges (yet)
00582     template< typename Tag, typename H = cnc_hash< Tag >, typename E = cnc_equal< Tag > >
00583     struct preserve_tuner : public tag_tuner< Internal::no_range, default_partitioner<> >
00584     {
00585         /// A tag tuner must provide a tag-table type; default is no tag-table
00586         typedef Internal::hash_tag_table< Tag, H, E > tag_table_type;
00587 
00588         bool preserve_tags() const
00589         {
00590             return true;
00591         };
00592     };
00593 
00594     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00595     // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00596 
00597     namespace Internal {
00598         template< typename Tuner >
00599         const Tuner & get_default_tuner()
00600         {
00601             static tbb::atomic< Tuner * > s_tuner;
00602             if( s_tuner == NULL ) {
00603                 Tuner * _tmp = new Tuner;
00604                 if( s_tuner.compare_and_swap( _tmp, NULL ) != NULL ) delete _tmp;
00605             }
00606             return *s_tuner;
00607         }
00608     }
00609 
00610 } // end namespace CnC
00611 
00612 #endif //CNC_DEFAULT_TUNER_H_ALREADY_INCLUDED