libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file parallel/par_loop.h 00026 * @brief Parallelization of embarrassingly parallel execution by 00027 * means of equal splitting. 00028 * This file is a GNU parallel extension to the Standard C++ Library. 00029 */ 00030 00031 // Written by Felix Putze. 00032 00033 #ifndef _GLIBCXX_PARALLEL_PAR_LOOP_H 00034 #define _GLIBCXX_PARALLEL_PAR_LOOP_H 1 00035 00036 #include <omp.h> 00037 #include <parallel/settings.h> 00038 #include <parallel/base.h> 00039 #include <parallel/equally_split.h> 00040 00041 namespace __gnu_parallel 00042 { 00043 /** @brief Embarrassingly parallel algorithm for random access 00044 * iterators, using hand-crafted parallelization by equal splitting 00045 * the work. 00046 * 00047 * @param __begin Begin iterator of element sequence. 00048 * @param __end End iterator of element sequence. 00049 * @param __o User-supplied functor (comparator, predicate, adding 00050 * functor, ...) 00051 * @param __f Functor to "process" an element with __op (depends on 00052 * desired functionality, e. g. for std::for_each(), ...). 00053 * @param __r Functor to "add" a single __result to the already 00054 * processed elements (depends on functionality). 00055 * @param __base Base value for reduction. 00056 * @param __output Pointer to position where final result is written to 00057 * @param __bound Maximum number of elements processed (e. g. for 00058 * std::count_n()). 00059 * @return User-supplied functor (that may contain a part of the result). 00060 */ 00061 template<typename _RAIter, 00062 typename _Op, 00063 typename _Fu, 00064 typename _Red, 00065 typename _Result> 00066 _Op 00067 __for_each_template_random_access_ed(_RAIter __begin, _RAIter __end, 00068 _Op __o, _Fu& __f, _Red __r, 00069 _Result __base, _Result& __output, 00070 typename std::iterator_traits<_RAIter>::difference_type __bound) 00071 { 00072 typedef std::iterator_traits<_RAIter> _TraitsType; 00073 typedef typename _TraitsType::difference_type _DifferenceType; 00074 const _DifferenceType __length = __end - __begin; 00075 _Result *__thread_results; 00076 bool* __constructed; 00077 00078 _ThreadIndex __num_threads = __gnu_parallel::min<_DifferenceType> 00079 (__get_max_threads(), __length); 00080 00081 # pragma omp parallel num_threads(__num_threads) 00082 { 00083 # pragma omp single 00084 { 00085 __num_threads = omp_get_num_threads(); 00086 __thread_results = static_cast<_Result*> 00087 (::operator new(__num_threads * sizeof(_Result))); 00088 __constructed = new bool[__num_threads]; 00089 } 00090 00091 _ThreadIndex __iam = omp_get_thread_num(); 00092 00093 // Neutral element. 00094 _Result* __reduct; 00095 00096 _DifferenceType 00097 __start = __equally_split_point(__length, __num_threads, __iam), 00098 __stop = __equally_split_point(__length, __num_threads, __iam + 1); 00099 00100 if (__start < __stop) 00101 { 00102 __reduct = new _Result(__f(__o, __begin + __start)); 00103 ++__start; 00104 __constructed[__iam] = true; 00105 } 00106 else 00107 __constructed[__iam] = false; 00108 00109 for (; __start < __stop; ++__start) 00110 *__reduct = __r(*__reduct, __f(__o, __begin + __start)); 00111 00112 if (__constructed[__iam]) 00113 { 00114 ::new(&__thread_results[__iam]) _Result(*__reduct); 00115 delete __reduct; 00116 } 00117 } //parallel 00118 00119 for (_ThreadIndex __i = 0; __i < __num_threads; ++__i) 00120 if (__constructed[__i]) 00121 { 00122 __output = __r(__output, __thread_results[__i]); 00123 __thread_results[__i].~_Result(); 00124 } 00125 00126 // Points to last element processed (needed as return value for 00127 // some algorithms like transform). 00128 __f._M_finish_iterator = __begin + __length; 00129 00130 ::operator delete(__thread_results); 00131 00132 delete[] __constructed; 00133 00134 return __o; 00135 } 00136 00137 } // end namespace 00138 00139 #endif /* _GLIBCXX_PARALLEL_PAR_LOOP_H */