← Back to branch summary

~ubuntu-branches/ubuntu/trusty/deal.ii/trusty

« back to all changes in this revision

Viewing changes to contrib/tbb/tbb22_20090809oss/include/tbb/parallel_do.h

  • Committer: Bazaar Package Importer
  • Author(s): Adam C. Powell, IV, Adam C. Powell, IV, Denis Barbier
  • Date: 2010-07-29 13:47:01 UTC
  • mfrom: (3.1.3 sid)
  • Revision ID: james.westby@ubuntu.com-20100729134701-akb8jb3stwge8tcm
Tags: 6.3.1-1
http://bugs.debian.org/562332
[ Adam C. Powell, IV ]
* Changed to source format 3.0 (quilt).
* Changed maintainer to debian-science with Adam Powell as uploader.
* Added source lintian overrides about Adam Powell's name.
* Added Vcs info on git repository.
* Bumped Standards-Version.
* Changed stamp-patch to patch target and fixed its application criterion.
* Moved make_dependencies and expand_instantiations to a versioned directory
  to avoid shlib package conflicts.

[ Denis Barbier ]
* New upstream release (closes: #562332).
  + Added libtbb support.
  + Forward-ported all patches.
* Updates for new PETSc version, including workaround for different versions
  of petsc and slepc.
* Add debian/watch.
* Update to debhelper 7.
* Added pdebuild patch.

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/tbb/tbb22_20090809oss/include/tbb/parallel_do.h
 
1
/*
 
2
    Copyright 2005-2009 Intel Corporation.  All Rights Reserved.
 
3
 
 
4
    This file is part of Threading Building Blocks.
 
5
 
 
6
    Threading Building Blocks is free software; you can redistribute it
 
7
    and/or modify it under the terms of the GNU General Public License
 
8
    version 2 as published by the Free Software Foundation.
 
9
 
 
10
    Threading Building Blocks is distributed in the hope that it will be
 
11
    useful, but WITHOUT ANY WARRANTY; without even the implied warranty
 
12
    of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
13
    GNU General Public License for more details.
 
14
 
 
15
    You should have received a copy of the GNU General Public License
 
16
    along with Threading Building Blocks; if not, write to the Free Software
 
17
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 
18
 
 
19
    As a special exception, you may use this file as part of a free software
 
20
    library without restriction.  Specifically, if other files instantiate
 
21
    templates or use macros or inline functions from this file, or you compile
 
22
    this file and link it with other files to produce an executable, this
 
23
    file does not by itself cause the resulting executable to be covered by
 
24
    the GNU General Public License.  This exception does not however
 
25
    invalidate any other reasons why the executable file might be covered by
 
26
    the GNU General Public License.
 
27
*/
 
28
 
 
29
#ifndef __TBB_parallel_do_H
 
30
#define __TBB_parallel_do_H
 
31
 
 
32
#include "task.h"
 
33
#include "aligned_space.h"
 
34
#include <iterator>
 
35
 
 
36
namespace tbb {
 
37
 
 
38
//! @cond INTERNAL
 
39
namespace internal {
 
40
    template<typename Body, typename Item> class parallel_do_feeder_impl;
 
41
    template<typename Body> class do_group_task;
 
42
 
 
43
    //! Strips its template type argument from 'cv' and '&' qualifiers
 
44
    template<typename T>
 
45
    struct strip { typedef T type; };
 
46
    template<typename T>
 
47
    struct strip<T&> { typedef T type; };
 
48
    template<typename T>
 
49
    struct strip<const T&> { typedef T type; };
 
50
    template<typename T>
 
51
    struct strip<volatile T&> { typedef T type; };
 
52
    template<typename T>
 
53
    struct strip<const volatile T&> { typedef T type; };
 
54
    // Most of the compilers remove cv-qualifiers from non-reference function argument types. 
 
55
    // But unfortunately there are those that don't.
 
56
    template<typename T>
 
57
    struct strip<const T> { typedef T type; };
 
58
    template<typename T>
 
59
    struct strip<volatile T> { typedef T type; };
 
60
    template<typename T>
 
61
    struct strip<const volatile T> { typedef T type; };
 
62
} // namespace internal
 
63
//! @endcond
 
64
 
 
65
//! Class the user supplied algorithm body uses to add new tasks
 
66
/** \param Item Work item type **/
 
67
template<typename Item>
 
68
class parallel_do_feeder: internal::no_copy
 
69
{
 
70
    parallel_do_feeder() {}
 
71
    virtual ~parallel_do_feeder () {}
 
72
    virtual void internal_add( const Item& item ) = 0;
 
73
    template<typename Body_, typename Item_> friend class internal::parallel_do_feeder_impl;
 
74
public:
 
75
    //! Add a work item to a running parallel_do.
 
76
    void add( const Item& item ) {internal_add(item);}
 
77
};
 
78
 
 
79
//! @cond INTERNAL
 
80
namespace internal {
 
81
    //! For internal use only.
 
82
    /** Selects one of the two possible forms of function call member operator.
 
83
        @ingroup algorithms **/
 
84
    template<class Body, typename Item>
 
85
    class parallel_do_operator_selector
 
86
    {
 
87
        typedef parallel_do_feeder<Item> Feeder;
 
88
        template<typename A1, typename A2, typename CvItem >
 
89
        static void internal_call( const Body& obj, A1& arg1, A2&, void (Body::*)(CvItem) const ) {
 
90
            obj(arg1);
 
91
        }
 
92
        template<typename A1, typename A2, typename CvItem >
 
93
        static void internal_call( const Body& obj, A1& arg1, A2& arg2, void (Body::*)(CvItem, parallel_do_feeder<Item>&) const ) {
 
94
            obj(arg1, arg2);
 
95
        }
 
96
 
 
97
    public:
 
98
        template<typename A1, typename A2 >
 
99
        static void call( const Body& obj, A1& arg1, A2& arg2 )
 
100
        {
 
101
            internal_call( obj, arg1, arg2, &Body::operator() );
 
102
        }
 
103
    };
 
104
 
 
105
    //! For internal use only.
 
106
    /** Executes one iteration of a do.
 
107
        @ingroup algorithms */
 
108
    template<typename Body, typename Item>
 
109
    class do_iteration_task: public task
 
110
    {
 
111
        typedef parallel_do_feeder_impl<Body, Item> feeder_type;
 
112
 
 
113
        Item my_value;
 
114
        feeder_type& my_feeder;
 
115
 
 
116
        do_iteration_task( const Item& value, feeder_type& feeder ) : 
 
117
            my_value(value), my_feeder(feeder)
 
118
        {}
 
119
 
 
120
        /*override*/ 
 
121
        task* execute()
 
122
        {
 
123
            parallel_do_operator_selector<Body, Item>::call(*my_feeder.my_body, my_value, my_feeder);
 
124
            return NULL;
 
125
        }
 
126
 
 
127
        template<typename Body_, typename Item_> friend class parallel_do_feeder_impl;
 
128
    }; // class do_iteration_task
 
129
 
 
130
    template<typename Iterator, typename Body, typename Item>
 
131
    class do_iteration_task_iter: public task
 
132
    {
 
133
        typedef parallel_do_feeder_impl<Body, Item> feeder_type;
 
134
 
 
135
        Iterator my_iter;
 
136
        feeder_type& my_feeder;
 
137
 
 
138
        do_iteration_task_iter( const Iterator& iter, feeder_type& feeder ) : 
 
139
            my_iter(iter), my_feeder(feeder)
 
140
        {}
 
141
 
 
142
        /*override*/ 
 
143
        task* execute()
 
144
        {
 
145
            parallel_do_operator_selector<Body, Item>::call(*my_feeder.my_body, *my_iter, my_feeder);
 
146
            return NULL;
 
147
        }
 
148
 
 
149
        template<typename Iterator_, typename Body_, typename Item_> friend class do_group_task_forward;    
 
150
        template<typename Body_, typename Item_> friend class do_group_task_input;    
 
151
        template<typename Iterator_, typename Body_, typename Item_> friend class do_task_iter;    
 
152
    }; // class do_iteration_task_iter
 
153
 
 
154
    //! For internal use only.
 
155
    /** Implements new task adding procedure.
 
156
        @ingroup algorithms **/
 
157
    template<class Body, typename Item>
 
158
    class parallel_do_feeder_impl : public parallel_do_feeder<Item>
 
159
    {
 
160
        /*override*/ 
 
161
        void internal_add( const Item& item )
 
162
        {
 
163
            typedef do_iteration_task<Body, Item> iteration_type;
 
164
 
 
165
            iteration_type& t = *new (task::self().allocate_additional_child_of(*my_barrier)) iteration_type(item, *this);
 
166
 
 
167
            t.spawn( t );
 
168
        }
 
169
    public:
 
170
        const Body* my_body;
 
171
        empty_task* my_barrier;
 
172
 
 
173
        parallel_do_feeder_impl()
 
174
        {
 
175
            my_barrier = new( task::allocate_root() ) empty_task();
 
176
            __TBB_ASSERT(my_barrier, "root task allocation failed");
 
177
        }
 
178
 
 
179
#if __TBB_EXCEPTIONS
 
180
        parallel_do_feeder_impl(tbb::task_group_context &context)
 
181
        {
 
182
            my_barrier = new( task::allocate_root(context) ) empty_task();
 
183
            __TBB_ASSERT(my_barrier, "root task allocation failed");
 
184
        }
 
185
#endif
 
186
 
 
187
        ~parallel_do_feeder_impl()
 
188
        {
 
189
            my_barrier->destroy(*my_barrier);
 
190
        }
 
191
    }; // class parallel_do_feeder_impl
 
192
 
 
193
 
 
194
    //! For internal use only
 
195
    /** Unpacks a block of iterations.
 
196
        @ingroup algorithms */
 
197
    
 
198
    template<typename Iterator, typename Body, typename Item>
 
199
    class do_group_task_forward: public task
 
200
    {
 
201
        static const size_t max_arg_size = 4;         
 
202
 
 
203
        typedef parallel_do_feeder_impl<Body, Item> feeder_type;
 
204
 
 
205
        feeder_type& my_feeder;
 
206
        Iterator my_first;
 
207
        size_t my_size;
 
208
        
 
209
        do_group_task_forward( Iterator first, size_t size, feeder_type& feeder ) 
 
210
            : my_feeder(feeder), my_first(first), my_size(size)
 
211
        {}
 
212
 
 
213
        /*override*/ task* execute()
 
214
        {
 
215
            typedef do_iteration_task_iter<Iterator, Body, Item> iteration_type;
 
216
            __TBB_ASSERT( my_size>0, NULL );
 
217
            task_list list;
 
218
            task* t; 
 
219
            size_t k=0; 
 
220
            for(;;) {
 
221
                t = new( allocate_child() ) iteration_type( my_first, my_feeder );
 
222
                ++my_first;
 
223
                if( ++k==my_size ) break;
 
224
                list.push_back(*t);
 
225
            }
 
226
            set_ref_count(int(k+1));
 
227
            spawn(list);
 
228
            spawn_and_wait_for_all(*t);
 
229
            return NULL;
 
230
        }
 
231
 
 
232
        template<typename Iterator_, typename Body_, typename _Item> friend class do_task_iter;
 
233
    }; // class do_group_task_forward
 
234
 
 
235
    template<typename Body, typename Item>
 
236
    class do_group_task_input: public task
 
237
    {
 
238
        static const size_t max_arg_size = 4;         
 
239
        
 
240
        typedef parallel_do_feeder_impl<Body, Item> feeder_type;
 
241
 
 
242
        feeder_type& my_feeder;
 
243
        size_t my_size;
 
244
        aligned_space<Item, max_arg_size> my_arg;
 
245
 
 
246
        do_group_task_input( feeder_type& feeder ) 
 
247
            : my_feeder(feeder), my_size(0)
 
248
        {}
 
249
 
 
250
        /*override*/ task* execute()
 
251
        {
 
252
            typedef do_iteration_task_iter<Item*, Body, Item> iteration_type;
 
253
            __TBB_ASSERT( my_size>0, NULL );
 
254
            task_list list;
 
255
            task* t; 
 
256
            size_t k=0; 
 
257
            for(;;) {
 
258
                t = new( allocate_child() ) iteration_type( my_arg.begin() + k, my_feeder );
 
259
                if( ++k==my_size ) break;
 
260
                list.push_back(*t);
 
261
            }
 
262
            set_ref_count(int(k+1));
 
263
            spawn(list);
 
264
            spawn_and_wait_for_all(*t);
 
265
            return NULL;
 
266
        }
 
267
 
 
268
        ~do_group_task_input(){
 
269
            for( size_t k=0; k<my_size; ++k)
 
270
                (my_arg.begin() + k)->~Item();
 
271
        }
 
272
 
 
273
        template<typename Iterator_, typename Body_, typename Item_> friend class do_task_iter;
 
274
    }; // class do_group_task_input
 
275
    
 
276
    //! For internal use only.
 
277
    /** Gets block of iterations and packages them into a do_group_task.
 
278
        @ingroup algorithms */
 
279
    template<typename Iterator, typename Body, typename Item>
 
280
    class do_task_iter: public task
 
281
    {
 
282
        typedef parallel_do_feeder_impl<Body, Item> feeder_type;
 
283
 
 
284
    public:
 
285
        do_task_iter( Iterator first, Iterator last , feeder_type& feeder ) : 
 
286
            my_first(first), my_last(last), my_feeder(feeder)
 
287
        {}
 
288
 
 
289
    private:
 
290
        Iterator my_first;
 
291
        Iterator my_last;
 
292
        feeder_type& my_feeder;
 
293
 
 
294
        /* Do not merge run(xxx) and run_xxx() methods. They are separated in order
 
295
            to make sure that compilers will eliminate unused argument of type xxx
 
296
            (that is will not put it on stack). The sole purpose of this argument 
 
297
            is overload resolution.
 
298
            
 
299
            An alternative could be using template functions, but explicit specialization 
 
300
            of member function templates is not supported for non specialized class 
 
301
            templates. Besides template functions would always fall back to the least 
 
302
            efficient variant (the one for input iterators) in case of iterators having 
 
303
            custom tags derived from basic ones. */
 
304
        /*override*/ task* execute()
 
305
        {
 
306
            typedef typename std::iterator_traits<Iterator>::iterator_category iterator_tag;
 
307
            return run( (iterator_tag*)NULL );
 
308
        }
 
309
 
 
310
        /** This is the most restricted variant that operates on input iterators or
 
311
            iterators with unknown tags (tags not derived from the standard ones). **/
 
312
        inline task* run( void* ) { return run_for_input_iterator(); }
 
313
        
 
314
        task* run_for_input_iterator() {
 
315
            typedef do_group_task_input<Body, Item> block_type;
 
316
 
 
317
            block_type& t = *new( allocate_additional_child_of(*my_feeder.my_barrier) ) block_type(my_feeder);
 
318
            size_t k=0; 
 
319
            while( !(my_first == my_last) ) {
 
320
                new (t.my_arg.begin() + k) Item(*my_first);
 
321
                ++my_first;
 
322
                if( ++k==block_type::max_arg_size ) {
 
323
                    if ( !(my_first == my_last) )
 
324
                        recycle_to_reexecute();
 
325
                    break;
 
326
                }
 
327
            }
 
328
            if( k==0 ) {
 
329
                destroy(t);
 
330
                return NULL;
 
331
            } else {
 
332
                t.my_size = k;
 
333
                return &t;
 
334
            }
 
335
        }
 
336
 
 
337
        inline task* run( std::forward_iterator_tag* ) { return run_for_forward_iterator(); }
 
338
 
 
339
        task* run_for_forward_iterator() {
 
340
            typedef do_group_task_forward<Iterator, Body, Item> block_type;
 
341
 
 
342
            Iterator first = my_first;
 
343
            size_t k=0; 
 
344
            while( !(my_first==my_last) ) {
 
345
                ++my_first;
 
346
                if( ++k==block_type::max_arg_size ) {
 
347
                    if ( !(my_first==my_last) )
 
348
                        recycle_to_reexecute();
 
349
                    break;
 
350
                }
 
351
            }
 
352
            return k==0 ? NULL : new( allocate_additional_child_of(*my_feeder.my_barrier) ) block_type(first, k, my_feeder);
 
353
        }
 
354
        
 
355
        inline task* run( std::random_access_iterator_tag* ) { return run_for_random_access_iterator(); }
 
356
 
 
357
        task* run_for_random_access_iterator() {
 
358
            typedef do_group_task_forward<Iterator, Body, Item> block_type;
 
359
            typedef do_iteration_task_iter<Iterator, Body, Item> iteration_type;
 
360
            
 
361
            size_t k = static_cast<size_t>(my_last-my_first); 
 
362
            if( k > block_type::max_arg_size ) {
 
363
                Iterator middle = my_first + k/2;
 
364
 
 
365
                empty_task& c = *new( allocate_continuation() ) empty_task;
 
366
                do_task_iter& b = *new( c.allocate_child() ) do_task_iter(middle, my_last, my_feeder);
 
367
                recycle_as_child_of(c);
 
368
 
 
369
                my_last = middle;
 
370
                c.set_ref_count(2);
 
371
                c.spawn(b);
 
372
                return this;
 
373
            }else if( k != 0 ) {
 
374
                task_list list;
 
375
                task* t; 
 
376
                size_t k1=0; 
 
377
                for(;;) {
 
378
                    t = new( allocate_child() ) iteration_type(my_first, my_feeder);
 
379
                    ++my_first;
 
380
                    if( ++k1==k ) break;
 
381
                    list.push_back(*t);
 
382
                }
 
383
                set_ref_count(int(k+1));
 
384
                spawn(list);
 
385
                spawn_and_wait_for_all(*t);
 
386
            }
 
387
            return NULL;
 
388
        }
 
389
    }; // class do_task_iter
 
390
 
 
391
    //! For internal use only.
 
392
    /** Implements parallel iteration over a range.
 
393
        @ingroup algorithms */
 
394
    template<typename Iterator, typename Body, typename Item> 
 
395
    void run_parallel_do( Iterator first, Iterator last, const Body& body
 
396
#if __TBB_EXCEPTIONS
 
397
        , task_group_context& context
 
398
#endif
 
399
        )
 
400
    {
 
401
        typedef do_task_iter<Iterator, Body, Item> root_iteration_task;
 
402
#if __TBB_EXCEPTIONS
 
403
        parallel_do_feeder_impl<Body, Item> feeder(context);
 
404
#else
 
405
        parallel_do_feeder_impl<Body, Item> feeder;
 
406
#endif
 
407
        feeder.my_body = &body;
 
408
 
 
409
        root_iteration_task &t = *new( feeder.my_barrier->allocate_child() ) root_iteration_task(first, last, feeder);
 
410
 
 
411
        feeder.my_barrier->set_ref_count(2);
 
412
        feeder.my_barrier->spawn_and_wait_for_all(t);
 
413
    }
 
414
 
 
415
    //! For internal use only.
 
416
    /** Detects types of Body's operator function arguments.
 
417
        @ingroup algorithms **/
 
418
    template<typename Iterator, typename Body, typename Item> 
 
419
    void select_parallel_do( Iterator first, Iterator last, const Body& body, void (Body::*)(Item) const
 
420
#if __TBB_EXCEPTIONS
 
421
        , task_group_context& context 
 
422
#endif // __TBB_EXCEPTIONS 
 
423
        )
 
424
    {
 
425
        run_parallel_do<Iterator, Body, typename strip<Item>::type>( first, last, body
 
426
#if __TBB_EXCEPTIONS
 
427
            , context
 
428
#endif // __TBB_EXCEPTIONS 
 
429
            );
 
430
    }
 
431
 
 
432
    //! For internal use only.
 
433
    /** Detects types of Body's operator function arguments.
 
434
        @ingroup algorithms **/
 
435
    template<typename Iterator, typename Body, typename Item, typename _Item> 
 
436
    void select_parallel_do( Iterator first, Iterator last, const Body& body, void (Body::*)(Item, parallel_do_feeder<_Item>&) const
 
437
#if __TBB_EXCEPTIONS
 
438
        , task_group_context& context 
 
439
#endif // __TBB_EXCEPTIONS
 
440
        )
 
441
    {
 
442
        run_parallel_do<Iterator, Body, typename strip<Item>::type>( first, last, body
 
443
#if __TBB_EXCEPTIONS
 
444
            , context
 
445
#endif // __TBB_EXCEPTIONS
 
446
            );
 
447
    }
 
448
 
 
449
} // namespace internal
 
450
//! @endcond
 
451
 
 
452
 
 
453
/** \page parallel_do_body_req Requirements on parallel_do body
 
454
    Class \c Body implementing the concept of parallel_do body must define:
 
455
    - \code 
 
456
        B::operator()( 
 
457
                cv_item_type item,
 
458
                parallel_do_feeder<item_type>& feeder
 
459
        ) const
 
460
        
 
461
        OR
 
462
 
 
463
        B::operator()( cv_item_type& item ) const
 
464
      \endcode                                                      Process item. 
 
465
                                                                    May be invoked concurrently  for the same \c this but different \c item.
 
466
                                                        
 
467
    - \code item_type( const item_type& ) \endcode 
 
468
                                                                    Copy a work item.
 
469
    - \code ~item_type() \endcode                            Destroy a work item
 
470
**/
 
471
 
 
472
/** \name parallel_do
 
473
    See also requirements on \ref parallel_do_body_req "parallel_do Body". **/
 
474
//@{
 
475
//! Parallel iteration over a range, with optional addition of more work.
 
476
/** @ingroup algorithms */
 
477
template<typename Iterator, typename Body> 
 
478
void parallel_do( Iterator first, Iterator last, const Body& body )
 
479
{
 
480
    if ( first == last )
 
481
        return;
 
482
#if __TBB_EXCEPTIONS
 
483
    task_group_context context;
 
484
#endif // __TBB_EXCEPTIONS
 
485
    internal::select_parallel_do( first, last, body, &Body::operator()
 
486
#if __TBB_EXCEPTIONS
 
487
        , context
 
488
#endif // __TBB_EXCEPTIONS
 
489
        );
 
490
}
 
491
 
 
492
#if __TBB_EXCEPTIONS
 
493
//! Parallel iteration over a range, with optional addition of more work and user-supplied context
 
494
/** @ingroup algorithms */
 
495
template<typename Iterator, typename Body> 
 
496
void parallel_do( Iterator first, Iterator last, const Body& body, task_group_context& context  )
 
497
{
 
498
    if ( first == last )
 
499
        return;
 
500
    internal::select_parallel_do( first, last, body, &Body::operator(), context );
 
501
}
 
502
#endif // __TBB_EXCEPTIONS
 
503
 
 
504
//@}
 
505
 
 
506
} // namespace 
 
507
 
 
508
#endif /* __TBB_parallel_do_H */