CnC
 All Classes Namespaces Functions Variables Typedefs Enumerator Friends Groups Pages
cnc.h
1 //********************************************************************************
2 // Copyright (c) 2007-2013 Intel Corporation. All Rights Reserved. **
3 // **
4 // The source code contained or described herein and all documents related to **
5 // the source code ("Material") are owned by Intel Corporation or its suppliers **
6 // or licensors. Title to the Material remains with Intel Corporation or its **
7 // suppliers and licensors. The Material contains trade secrets and proprietary **
8 // and confidential information of Intel or its suppliers and licensors. The **
9 // Material is protected by worldwide copyright and trade secret laws and **
10 // treaty provisions. No part of the Material may be used, copied, reproduced, **
11 // modified, published, uploaded, posted, transmitted, distributed, or **
12 // disclosed in any way without Intel's prior express written permission. **
13 // **
14 // No license under any patent, copyright, trade secret or other intellectual **
15 // property right is granted to or conferred upon you by disclosure or delivery **
16 // of the Materials, either expressly, by implication, inducement, estoppel or **
17 // otherwise. Any license under such intellectual property rights must be **
18 // express and approved by Intel in writing. **
19 //********************************************************************************
20 
21 #ifndef _CnC_H_ALREADY_INCLUDED_
22 #define _CnC_H_ALREADY_INCLUDED_
23 
24 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
25 // Workaround for overzealous compiler warnings
26 # pragma warning (push)
27 # pragma warning (disable: 4251 4275 4290)
28 #endif
29 
30 #include <cnc/internal/tag_collection_base.h>
31 #include <cnc/internal/item_collection_base.h>
32 #include <cnc/internal/context_base.h>
33 #include <cnc/internal/no_range.h>
34 
35 /// \brief CnC API
36 namespace CnC {
37 
38  typedef int error_type;
39 
40  // forward declarations
41  template< class T > class context;
42  struct debug;
43  template< typename Tag, typename Tuner > class tag_collection;
44  template< typename Tag, typename Item, typename Tuner > class item_collection;
45 
46  /// Steps return CNC_Success if execution was successful
47  const int CNC_Success = 0;
48  /// Steps return CNC_Failure if execution failed
49  const int CNC_Failure = 1;
50 
51  /// \brief A step collection is logical set of step instances.
52  ///
53  /// A step-collection must be prescribed by a tag-collection and it
54  /// can be part of consumer/producer relationships with item-collections.
55  /// Additionally, it can be the controller in control-dependencies (e.g. produce tags).
56  template< typename UserStep, typename Tuner = step_tuner<> >
57  class step_collection : public Internal::traceable
58  {
59  public:
60  /// the type of the step as provided by the user
61  typedef UserStep step_type;
62  /// the type of the tuner as provided by the user
63  typedef Tuner tuner_type;
64 
65  /// \brief constructor which registers collection with given context
66  ///
67  /// \param ctxt the context this collection belongs to
68  /// \param name an optional name, used for debug output and tracing
69  /// \param userStep an optional user step argument, a copy will be created through copy-construction
70  /// \param tnr an optional tuner object which must persist throughout the lifetime of the step-collection
71  /// by default a default-constructed tuner will be used.
72  template< typename Derived >
73  step_collection( context< Derived > & ctxt, const std::string & name, const step_type & userStep, const tuner_type & tnr );
74  template< typename Derived >
76  template< typename Derived >
77  step_collection( context< Derived > & ctxt, const std::string & name );
78  template< typename Derived >
79  step_collection( context< Derived > & ctxt, const tuner_type & tnr, const std::string & name = std::string() );
80  template< typename Derived >
81  step_collection( context< Derived > & ctxt, const std::string & name, const step_type & userStep );
82 
83  /// Declare this step-collecation as consumer of given item-collection
84  template< typename DataTag, typename Item, typename ITuner >
86 
87  /// Declare this step-collecation as producer for given item-collection
88  template< typename DataTag, typename Item, typename ITuner >
90 
91  /// Declare this step-collecation as controller of given tag-collection
92  template< typename ControlTag, typename TTuner >
94 
95  private:
96  const step_type m_userStep;
97  const tuner_type & m_tuner;
98  template< class Tag, class Step, class Arg, class TTuner, class STuner > friend class Internal::step_launcher;
99  };
100 
101  /// \brief A tag collection is a set of tags of the same type. It is
102  /// used to prescribe steps. By default, tags are not stored.
103  ///
104  /// Tag must provide copy and default constructors and the assigment
105  /// operator.
106  ///
107  /// If Tag is not convertable into size_t, a suitable hash_compare
108  /// class must be provided which satisifies the requirements for
109  /// tbb::concurrent_hash_map. The default cnc_tag_hash_compare works
110  /// for types that can be converted to size_t and have an
111  /// operator==. You can provide specialized templates for
112  /// cnc_hash and/or cnc_equal or cnc_tag_hash_compare
113  /// or specify and implement your own compatible class.
114  template< typename Tag, typename Tuner = tag_tuner<> >
115  class /*CNC_API*/ tag_collection
116  {
117  public:
118  /// the tag type
119  typedef Tag tag_type;
120 
121  /// \brief constructor which registers collection with given context
122  ///
123  /// \param ctxt the context this collection belongs to
124  /// \param name an optional name, used for debug output and tracing
125  /// \param tnr an optional tuner object which must persist throughout the lifetime of the tag-collection
126  /// by default a default-constructed tuner will be used.
127  template< class Derived >
128  tag_collection( context< Derived > & ctxt, const std::string & name, const Tuner & tnr );
129  template< class Derived >
130  tag_collection( context< Derived > & ctxt, const std::string & name = std::string() );
131  template< class Derived >
132  tag_collection( context< Derived > & ctxt, const Tuner & tnr );
133 
134  /// \brief Declare the prescription relationship between the tag collection
135  /// and a step collection.
136  ///
137  /// \param s class representing step collection. s is required to
138  /// provide the following const method, where Arg a is the optional
139  /// parameter described below.
140  /// \code
141  /// int execute( const Tag & tag, Arg & a ) const;
142  /// \endcode
143  /// A copy of s will be created by calling its copy constructor.
144  ///
145  /// \param arg This argument will be the parameter passed to
146  /// Step::execute and the tuner methods. The object must exist as
147  /// long as instances of the given step might be executed. Usually
148  /// arg will be the containing context.
149  ///
150  /// \return 0 if succeeded, error code otherwise
151  template< typename UserStep, typename STuner, typename Arg >
152  error_type prescribes( const step_collection< UserStep, STuner > & s, Arg & arg );
153 
154  /// \brief prescribe the associated step. If we are preserving tags for this collection, make a copy of the tag and store it in the collection.
155  /// \param t the tag to be put
156  void put( const Tag & t );
157 
158  /// \brief prescribe an entire range of tags
159  ///
160  /// \param r A range, which is potentially splittible through a partitioner.
161  /// Following the TBB range/splittable concept, extended by STL container requirements,
162  /// a range R must provide the following interface:
163  /// - R::R( const R& ) : Copy constructor.
164  /// - int size() : return number of elements (tags) in range
165  /// - const_iterator : forward iterator (operator++, operator tag_type() const)
166  /// to make it work with tbb::blocked_range, the cast operator is used instead of operator*().
167  /// - const_iterator begin() const : first member of range
168  /// - const_iterator end() const : Exclusive upper bound on range
169  /// Using it with the default_partitioner also requires
170  /// - R::R( R& r, tbb::split ) : Split r into two subranges.
171  /// - bool R::is_divisible() const : true if range can be partitioned into two subranges.
172  void put_range( const typename Tuner::range_type & r );
173  void put_range( const Internal::no_range & ) const;
174 
175  /// const forward iterator as in STL
176  typedef typename Tuner::tag_table_type::const_iterator const_iterator;
177 
178  /// \brief returns begin() as in STL containers
179  /// \note iteration through collections is not thread safe;
180  /// use it only between calls to CnC::context::wait() and putting tags
181  const_iterator begin() const;
182 
183  /// \brief returns end() as in STL containers
184  /// \note iteration through collections is not thread safe;
185  /// use it only between calls to CnC::context::wait() and putting tags
186  const_iterator end() const;
187 
188  /// \brief removes all of the tag instances from the collection
189  /// \note not thread-safe, to be called in safe state only
190  /// (between program start or calling context::wait() and putting the first tag or item).
191  void unsafe_reset();
192 
193  /// returns number of elements in collection
194  size_t size();
195 
196  /// returns true if size()==0, false otherwise
197  bool empty();
198 
199  private:
200  Internal::tag_collection_base< Tag, Tuner > m_tagCollection;
201  //template< class T > friend class context;
202  friend struct ::CnC::debug;
203  };
204 
205  /// \brief An item collection is a mapping from tags to items.
206  ///
207  /// Tag and Item must provide copy and default constructors and the
208  /// assigment operator.
209  ///
210  /// Th last template argument is an optional tuner. The tuner provides
211  /// tuning hints, such as the type of the data store or information about
212  /// its use in distributed environments. Most importantly it tells the runtime
213  /// and compiler which type of data store it should use. By default that's
214  /// a hash-map (hashmap_tuner). For non default-supported tag types (e.g. those that are
215  /// not convertable into size_t) a suitable cnc_hash template
216  /// specialization must be provided. If in addition your type does not support std::equal_to
217  /// you also need to specialize cnc_equal.
218  /// For the vector-based data store (vector_tuner) that's not
219  /// necessary, but the tag-type must then be convertible to and from size_t.
220  /// \see CnC::item_tuner for more information.
221  ///
222  /// The CnC runtime will make a copy of your item when it is 'put' into
223  /// the item_collection. The CnC runtime will delete the copied item
224  /// copy once the get-count reaches 0 (or, if no get-count was
225  /// provided, once the collection is destroyed). If the item-type is a
226  /// pointer type, the runtime will not delete the memory the item
227  /// points to. If you store pointeres, you have to care for the appropriate
228  /// garbage collection, e.g. you might consider using smart pointers.
229  template< typename Tag, typename Item, typename Tuner = hashmap_tuner >
230  class /*CNC_API*/ item_collection
231  {
232  public:
233  /// the tag type
234  typedef Tag tag_ype;
235 
236  /// const forward iterator as in STL
237  class const_iterator;
238 
239  /// \brief constructor which registers collection with given context
240  ///
241  /// \param ctxt the context this collection belongs to
242  /// \param name an optional name, used for debug output and tracing
243  /// \param tnr a tuner object which must persist throughout the lifetime of the step-collection
244  /// by default a default-constructed tuner will be used.
245  template< class Derived >
246  item_collection( context< Derived > & ctxt, const std::string & name, const Tuner & tnr );
247  template< class Derived >
248  item_collection( context< Derived > & ctxt, const std::string & name = std::string() );
249  template< class Derived >
250  item_collection( context< Derived > & ctxt, const Tuner & tnr );
251 
252  ~item_collection();
253 
254  /// \brief Declares the maxium tag value.
255  ///
256  /// Must be called prior to accessing the collection if the data store is a vector.
257  /// Useful only for dense tag-spaces.
258  /// \param mx the largest tag-value ever used for this collection
259  void set_max( size_t mx );
260 
261  /// \brief make copies of the item and the tag and store them in the collection.
262  /// \param tag the tag identifying the item
263  /// \param item the item to be copied and stored
264  void put( const Tag & tag, const Item & item );
265 
266  /// \brief get an item
267  /// \param tag the tag identifying the item
268  /// \param item reference to item to store result in
269  /// \throw DataNotReady throws exception if data not yet available.
270  void get( const Tag & tag, Item & item ) const;
271 
272  /// \brief try to get an item and store it in given object (non-blocking)
273  ///
274  /// \attention This method is unsafe: you can create non-deterministic results if you decide to
275  /// to perform semantically relevant actions if an item is unavailable (returns false)
276  ///
277  /// If the item is unavailable, it does not change item.
278  /// Make sure you call flush_gets() after last call to this method (of any item collection) within a step.
279  /// In any case, you must check the return value before accessing the item.
280  /// \param tag the tag identifying the item
281  /// \param item reference to item to store result in
282  /// \return true if item is available
283  /// \throw DataNotReady might throw exception if data not available (yet)
284  bool unsafe_get( const Tag & tag, Item & item ) const;
285 
286  /// \brief returns begin() as in STL containers
287  /// \note iteration through collections is not thread safe;
288  /// use it only between calls to CnC::context::wait() and putting tags
289  const_iterator begin() const;
290 
291  /// \brief returns end() as in STL containers
292  /// \note iteration through collections is not thread safe;
293  /// use it only between calls to CnC::context::wait() and putting tags
294  const_iterator end() const;
295 
296  /// \brief removes all of the item instances from the collection
297  /// \note not thread-safe, to be called in safe state only
298  /// (between program start or calling context::wait() and putting the first tag or item).
299  void unsafe_reset();
300 
301  /// returns number of elements in collection
302  size_t size();
303 
304  /// returns true if size()==0, false otherwise
305  bool empty();
306 
307  private:
308  typedef Internal::item_collection_base< Tag, Item, Tuner > base_coll_type;
309  base_coll_type m_itemCollection;
310  friend struct ::CnC::debug;
311  friend class Internal::step_delayer;
312  friend class const_iterator;
313  };
314 
315  namespace Internal {
316  class distributor;
317  template< class T > class creator;
318  template< class Index, class Functor, class Tuner > class pfor_context;
319  }
320 
321  /// \brief CnC context bringing together collections (for steps, items and tags).
322  ///
323  /// The user needs to derive his or her own context from the CnC::context.
324  /// The template argument to context is the user's context class itself.
325  ///
326  /// For example,
327  /// @code
328  /// struct my_context : public CnC::context< my_context >
329  /// {
330  /// CnC::step_collection< FindPrimes > steps;
331  /// CnC::tag_collection< int > oddNums;
332  /// CnC::item_collection< int,int > primes;
333  /// my_context()
334  /// : CnC::context< my_context >(),
335  /// steps( this ),
336  /// oddNums( this ),
337  /// primes( this )
338  /// {
339  /// oddNums.prescribes( steps );
340  /// }
341  /// };
342  /// @endcode
343  ///
344  /// Several contexts can be created and executed simultaneously.
345  ///
346  /// Execution starts as soon as a step(-instance) is prescribed through putting a tag.
347  /// All ready steps will be executed even if CnC::context::wait() is never be called.
348  ///
349  /// It is recommended to declare collections as members of a context derived from CnC::context.
350  /// This yields more maintanable code and future versions of CnC may require this convention.
351  template< class Derived >
352  class /*CNC_API*/ context : private Internal::context_base
353  {
354  public:
355  /// default constructor
356  context();
357  /// destructor
358  virtual ~context();
359 
360  /// \brief wait until all the steps prescribed by this context have completed execution.
361  /// \return 0 if succeeded, error code otherwise
362  error_type wait();
363 
364  /// \brief used with the preschedule tuner to finalize 'gets' in the pre-execution of a step
365  ///
366  /// Call this after last call to the non-blocking item_collection::unsafe_get method.
367  void flush_gets();
368 
369  /// reset all collections of this context
370  /// \note not thread-safe, to be called in safe state only
371  /// (between program start or calling context::wait() and putting the first tag or item).
372  void unsafe_reset();
373 
374  /// (distCnC) overload this if default construction on remote processes is not enough.
375  virtual void serialize( serializer & ){}
376 
377  private:
378  virtual void unsafe_reset( bool );
379  context( bool );
380  virtual int factory_id();
381  template< class Range, class Coll >
382  void divide_and_put( Range & range, int grain, Coll * coll, Internal::scheduler_i * sched );
383  friend struct ::CnC::debug;
384  friend class ::CnC::Internal::distributor;
385  friend class ::CnC::tuner_base;
386  template< typename Tag, bool check_deps, typename Hasher, typename Equality > friend class ::CnC::cancel_tuner;
387  template< class T > friend class ::CnC::Internal::creator;
388  template< class Index, class Functor, class Tuner > friend class ::CnC::Internal::pfor_context;
389  };
390 
391  /// \brief Execute f( i ) for every i in {first <= i=first+step*x < last and 0 <= x}.
392  ///
393  /// For different values of i, function execution might occur in parallel.
394  /// Returns functor object ocne all iterations have been executed.
395  /// Type Index must support operator+.
396  /// Executes on the local process only. No distribution to other processes supported.
397  /// \param first starting index of parallel iteration
398  /// \param last iteration stops before reaching last
399  /// \param incr increment index by this value in each iteration
400  /// \param f function to be executed
401  /// \param tuner defaults to pfor_tuner<>
402  template< class Index, class Functor >
403  void parallel_for( Index first, Index last, Index incr, const Functor & f );
404  template< class Index, class Functor, class Tuner >
405  void parallel_for( Index first, Index last, Index incr, const Functor & f, const Tuner & t );
406 
407 } // namespace cnc
408 
409 #include <cnc/internal/step_collection.h>
410 #include <cnc/internal/tag_collection.h>
411 #include <cnc/internal/item_collection.h>
412 #include <cnc/internal/context.h>
413 #include <cnc/internal/parallel_for.h>
414 #include <cnc/internal/hash_item_table.h>
415 #include <cnc/internal/vec_item_table.h>
416 
417 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
418 # pragma warning (pop)
419 # pragma warning( disable : 4355 )
420 #endif // warnings 4251 4275 4290 are back, 4355 is hidden
421 
422 #endif // _CnC_H_ALREADY_INCLUDED_