 |
Shadowrun: Awakened 29 September 2011 - Build 871
|
parallel_reduce.h
Go to the documentation of this file.
00001 /* 00002 Copyright 2005-2010 Intel Corporation. All Rights Reserved. 00003 00004 This file is part of Threading Building Blocks. 00005 00006 Threading Building Blocks is free software; you can redistribute it 00007 and/or modify it under the terms of the GNU General Public License 00008 version 2 as published by the Free Software Foundation. 00009 00010 Threading Building Blocks is distributed in the hope that it will be 00011 useful, but WITHOUT ANY WARRANTY; without even the implied warranty 00012 of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00013 GNU General Public License for more details. 00014 00015 You should have received a copy of the GNU General Public License 00016 along with Threading Building Blocks; if not, write to the Free Software 00017 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 00018 00019 As a special exception, you may use this file as part of a free software 00020 library without restriction. Specifically, if other files instantiate 00021 templates or use macros or inline functions from this file, or you compile 00022 this file and link it with other files to produce an executable, this 00023 file does not by itself cause the resulting executable to be covered by 00024 the GNU General Public License. This exception does not however 00025 invalidate any other reasons why the executable file might be covered by 00026 the GNU General Public License. 00027 */ 00028 00029 #ifndef __TBB_parallel_reduce_H 00030 #define __TBB_parallel_reduce_H 00031 00032 #include "task.h" 00033 #include "aligned_space.h" 00034 #include "partitioner.h" 00035 #include <new> 00036 00037 namespace tbb { 00038 00040 namespace internal { 00041 00043 void __TBB_EXPORTED_FUNC itt_store_pointer_with_release_v3( void* dst, void* src ); 00044 00046 void* __TBB_EXPORTED_FUNC itt_load_pointer_with_acquire_v3( const void* src ); 00047 00048 template<typename T> inline void parallel_reduce_store_body( T*& dst, T* src ) { 00049 #if TBB_USE_THREADING_TOOLS 00050 itt_store_pointer_with_release_v3(&dst,src); 00051 #else 00052 __TBB_store_with_release(dst,src); 00053 #endif /* TBB_USE_THREADING_TOOLS */ 00054 } 00055 00056 template<typename T> inline T* parallel_reduce_load_body( T*& src ) { 00057 #if TBB_USE_THREADING_TOOLS 00058 return static_cast<T*>(itt_load_pointer_with_acquire_v3(&src)); 00059 #else 00060 return __TBB_load_with_acquire(src); 00061 #endif /* TBB_USE_THREADING_TOOLS */ 00062 } 00063 00065 00066 typedef char reduction_context; 00067 00069 00070 template<typename Body> 00071 class finish_reduce: public task { 00073 Body* my_body; 00074 bool has_right_zombie; 00075 const reduction_context my_context; 00076 aligned_space<Body,1> zombie_space; 00077 finish_reduce( char context_ ) : 00078 my_body(NULL), 00079 has_right_zombie(false), 00080 my_context(context_) 00081 { 00082 } 00083 task* execute() { 00084 if( has_right_zombie ) { 00085 // Right child was stolen. 00086 Body* s = zombie_space.begin(); 00087 my_body->join( *s ); 00088 s->~Body(); 00089 } 00090 if( my_context==1 ) 00091 parallel_reduce_store_body( static_cast<finish_reduce*>(parent())->my_body, my_body ); 00092 return NULL; 00093 } 00094 template<typename Range,typename Body_, typename Partitioner> 00095 friend class start_reduce; 00096 }; 00097 00099 00100 template<typename Range, typename Body, typename Partitioner> 00101 class start_reduce: public task { 00102 typedef finish_reduce<Body> finish_type; 00103 Body* my_body; 00104 Range my_range; 00105 typename Partitioner::partition_type my_partition; 00106 reduction_context my_context; 00107 /*override*/ task* execute(); 00108 template<typename Body_> 00109 friend class finish_reduce; 00110 00112 start_reduce( const Range& range, Body* body, Partitioner& partitioner ) : 00113 my_body(body), 00114 my_range(range), 00115 my_partition(partitioner), 00116 my_context(0) 00117 { 00118 } 00120 00121 start_reduce( start_reduce& parent_, split ) : 00122 my_body(parent_.my_body), 00123 my_range(parent_.my_range,split()), 00124 my_partition(parent_.my_partition,split()), 00125 my_context(2) 00126 { 00127 my_partition.set_affinity(*this); 00128 parent_.my_context = 1; 00129 } 00131 /*override*/ void note_affinity( affinity_id id ) { 00132 my_partition.note_affinity( id ); 00133 } 00134 00135 public: 00136 static void run( const Range& range, Body& body, Partitioner& partitioner ) { 00137 if( !range.empty() ) { 00138 #if !__TBB_TASK_GROUP_CONTEXT || TBB_JOIN_OUTER_TASK_GROUP 00139 task::spawn_root_and_wait( *new(task::allocate_root()) start_reduce(range,&body,partitioner) ); 00140 #else 00141 // Bound context prevents exceptions from body to affect nesting or sibling algorithms, 00142 // and allows users to handle exceptions safely by wrapping parallel_for in the try-block. 00143 task_group_context context; 00144 task::spawn_root_and_wait( *new(task::allocate_root(context)) start_reduce(range,&body,partitioner) ); 00145 #endif /* __TBB_TASK_GROUP_CONTEXT && !TBB_JOIN_OUTER_TASK_GROUP */ 00146 } 00147 } 00148 #if __TBB_TASK_GROUP_CONTEXT 00149 static void run( const Range& range, Body& body, Partitioner& partitioner, task_group_context& context ) { 00150 if( !range.empty() ) 00151 task::spawn_root_and_wait( *new(task::allocate_root(context)) start_reduce(range,&body,partitioner) ); 00152 } 00153 #endif /* __TBB_TASK_GROUP_CONTEXT */ 00154 }; 00155 00156 template<typename Range, typename Body, typename Partitioner> 00157 task* start_reduce<Range,Body,Partitioner>::execute() { 00158 if( my_context==2 ) { 00159 finish_type* p = static_cast<finish_type*>(parent() ); 00160 if( !parallel_reduce_load_body(p->my_body) ) { 00161 my_body = new( p->zombie_space.begin() ) Body(*my_body,split()); 00162 p->has_right_zombie = true; 00163 } 00164 } 00165 if( !my_range.is_divisible() || my_partition.should_execute_range(*this) ) { 00166 (*my_body)( my_range ); 00167 if( my_context==1 ) 00168 parallel_reduce_store_body(static_cast<finish_type*>(parent())->my_body, my_body ); 00169 return my_partition.continue_after_execute_range(); 00170 } else { 00171 finish_type& c = *new( allocate_continuation()) finish_type(my_context); 00172 recycle_as_child_of(c); 00173 c.set_ref_count(2); 00174 bool delay = my_partition.decide_whether_to_delay(); 00175 start_reduce& b = *new( c.allocate_child() ) start_reduce(*this,split()); 00176 my_partition.spawn_or_delay(delay,b); 00177 return this; 00178 } 00179 } 00180 00182 00186 template<typename Range, typename Value, typename RealBody, typename Reduction> 00187 class lambda_reduce_body { 00188 00189 //FIXME: decide if my_real_body, my_reduction, and identity_element should be copied or referenced 00190 // (might require some performance measurements) 00191 00192 const Value& identity_element; 00193 const RealBody& my_real_body; 00194 const Reduction& my_reduction; 00195 Value my_value; 00196 lambda_reduce_body& operator= ( const lambda_reduce_body& other ); 00197 public: 00198 lambda_reduce_body( const Value& identity, const RealBody& body, const Reduction& reduction ) 00199 : identity_element(identity) 00200 , my_real_body(body) 00201 , my_reduction(reduction) 00202 , my_value(identity) 00203 { } 00204 lambda_reduce_body( const lambda_reduce_body& other ) 00205 : identity_element(other.identity_element) 00206 , my_real_body(other.my_real_body) 00207 , my_reduction(other.my_reduction) 00208 , my_value(other.my_value) 00209 { } 00210 lambda_reduce_body( lambda_reduce_body& other, tbb::split ) 00211 : identity_element(other.identity_element) 00212 , my_real_body(other.my_real_body) 00213 , my_reduction(other.my_reduction) 00214 , my_value(other.identity_element) 00215 { } 00216 void operator()(Range& range) { 00217 my_value = my_real_body(range, const_cast<const Value&>(my_value)); 00218 } 00219 void join( lambda_reduce_body& rhs ) { 00220 my_value = my_reduction(const_cast<const Value&>(my_value), const_cast<const Value&>(rhs.my_value)); 00221 } 00222 Value result() const { 00223 return my_value; 00224 } 00225 }; 00226 00227 } // namespace internal 00229 00230 // Requirements on Range concept are documented in blocked_range.h 00231 00250 00252 00253 template<typename Range, typename Body> 00254 void parallel_reduce( const Range& range, Body& body ) { 00255 internal::start_reduce<Range,Body, const __TBB_DEFAULT_PARTITIONER>::run( range, body, __TBB_DEFAULT_PARTITIONER() ); 00256 } 00257 00259 00260 template<typename Range, typename Body> 00261 void parallel_reduce( const Range& range, Body& body, const simple_partitioner& partitioner ) { 00262 internal::start_reduce<Range,Body,const simple_partitioner>::run( range, body, partitioner ); 00263 } 00264 00266 00267 template<typename Range, typename Body> 00268 void parallel_reduce( const Range& range, Body& body, const auto_partitioner& partitioner ) { 00269 internal::start_reduce<Range,Body,const auto_partitioner>::run( range, body, partitioner ); 00270 } 00271 00273 00274 template<typename Range, typename Body> 00275 void parallel_reduce( const Range& range, Body& body, affinity_partitioner& partitioner ) { 00276 internal::start_reduce<Range,Body,affinity_partitioner>::run( range, body, partitioner ); 00277 } 00278 00279 #if __TBB_TASK_GROUP_CONTEXT 00280 00281 00282 template<typename Range, typename Body> 00283 void parallel_reduce( const Range& range, Body& body, const simple_partitioner& partitioner, task_group_context& context ) { 00284 internal::start_reduce<Range,Body,const simple_partitioner>::run( range, body, partitioner, context ); 00285 } 00286 00288 00289 template<typename Range, typename Body> 00290 void parallel_reduce( const Range& range, Body& body, const auto_partitioner& partitioner, task_group_context& context ) { 00291 internal::start_reduce<Range,Body,const auto_partitioner>::run( range, body, partitioner, context ); 00292 } 00293 00295 00296 template<typename Range, typename Body> 00297 void parallel_reduce( const Range& range, Body& body, affinity_partitioner& partitioner, task_group_context& context ) { 00298 internal::start_reduce<Range,Body,affinity_partitioner>::run( range, body, partitioner, context ); 00299 } 00300 #endif /* __TBB_TASK_GROUP_CONTEXT */ 00301 00305 00306 00307 template<typename Range, typename Value, typename RealBody, typename Reduction> 00308 Value parallel_reduce( const Range& range, const Value& identity, const RealBody& real_body, const Reduction& reduction ) { 00309 internal::lambda_reduce_body<Range,Value,RealBody,Reduction> body(identity, real_body, reduction); 00310 internal::start_reduce<Range,internal::lambda_reduce_body<Range,Value,RealBody,Reduction>,const __TBB_DEFAULT_PARTITIONER> 00311 ::run(range, body, __TBB_DEFAULT_PARTITIONER() ); 00312 return body.result(); 00313 } 00314 00316 00317 template<typename Range, typename Value, typename RealBody, typename Reduction> 00318 Value parallel_reduce( const Range& range, const Value& identity, const RealBody& real_body, const Reduction& reduction, 00319 const simple_partitioner& partitioner ) { 00320 internal::lambda_reduce_body<Range,Value,RealBody,Reduction> body(identity, real_body, reduction); 00321 internal::start_reduce<Range,internal::lambda_reduce_body<Range,Value,RealBody,Reduction>,const simple_partitioner> 00322 ::run(range, body, partitioner ); 00323 return body.result(); 00324 } 00325 00327 00328 template<typename Range, typename Value, typename RealBody, typename Reduction> 00329 Value parallel_reduce( const Range& range, const Value& identity, const RealBody& real_body, const Reduction& reduction, 00330 const auto_partitioner& partitioner ) { 00331 internal::lambda_reduce_body<Range,Value,RealBody,Reduction> body(identity, real_body, reduction); 00332 internal::start_reduce<Range,internal::lambda_reduce_body<Range,Value,RealBody,Reduction>,const auto_partitioner> 00333 ::run( range, body, partitioner ); 00334 return body.result(); 00335 } 00336 00338 00339 template<typename Range, typename Value, typename RealBody, typename Reduction> 00340 Value parallel_reduce( const Range& range, const Value& identity, const RealBody& real_body, const Reduction& reduction, 00341 affinity_partitioner& partitioner ) { 00342 internal::lambda_reduce_body<Range,Value,RealBody,Reduction> body(identity, real_body, reduction); 00343 internal::start_reduce<Range,internal::lambda_reduce_body<Range,Value,RealBody,Reduction>,affinity_partitioner> 00344 ::run( range, body, partitioner ); 00345 return body.result(); 00346 } 00347 00348 #if __TBB_TASK_GROUP_CONTEXT 00349 00350 00351 template<typename Range, typename Value, typename RealBody, typename Reduction> 00352 Value parallel_reduce( const Range& range, const Value& identity, const RealBody& real_body, const Reduction& reduction, 00353 const simple_partitioner& partitioner, task_group_context& context ) { 00354 internal::lambda_reduce_body<Range,Value,RealBody,Reduction> body(identity, real_body, reduction); 00355 internal::start_reduce<Range,internal::lambda_reduce_body<Range,Value,RealBody,Reduction>,const simple_partitioner> 00356 ::run( range, body, partitioner, context ); 00357 return body.result(); 00358 } 00359 00361 00362 template<typename Range, typename Value, typename RealBody, typename Reduction> 00363 Value parallel_reduce( const Range& range, const Value& identity, const RealBody& real_body, const Reduction& reduction, 00364 const auto_partitioner& partitioner, task_group_context& context ) { 00365 internal::lambda_reduce_body<Range,Value,RealBody,Reduction> body(identity, real_body, reduction); 00366 internal::start_reduce<Range,internal::lambda_reduce_body<Range,Value,RealBody,Reduction>,const auto_partitioner> 00367 ::run( range, body, partitioner, context ); 00368 return body.result(); 00369 } 00370 00372 00373 template<typename Range, typename Value, typename RealBody, typename Reduction> 00374 Value parallel_reduce( const Range& range, const Value& identity, const RealBody& real_body, const Reduction& reduction, 00375 affinity_partitioner& partitioner, task_group_context& context ) { 00376 internal::lambda_reduce_body<Range,Value,RealBody,Reduction> body(identity, real_body, reduction); 00377 internal::start_reduce<Range,internal::lambda_reduce_body<Range,Value,RealBody,Reduction>,affinity_partitioner> 00378 ::run( range, body, partitioner, context ); 00379 return body.result(); 00380 } 00381 #endif /* __TBB_TASK_GROUP_CONTEXT */ 00382 00383 00384 } // namespace tbb 00385 00386 #endif /* __TBB_parallel_reduce_H */ 00387
