libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2007, 2008, 2009 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 00044 /** @brief Embarrassingly parallel algorithm for random access 00045 * iterators, using hand-crafted parallelization by equal splitting 00046 * the work. 00047 * 00048 * @param begin Begin iterator of element sequence. 00049 * @param end End iterator of element sequence. 00050 * @param o User-supplied functor (comparator, predicate, adding 00051 * functor, ...) 00052 * @param f Functor to "process" an element with op (depends on 00053 * desired functionality, e. g. for std::for_each(), ...). 00054 * @param r Functor to "add" a single result to the already 00055 * processed elements (depends on functionality). 00056 * @param base Base value for reduction. 00057 * @param output Pointer to position where final result is written to 00058 * @param bound Maximum number of elements processed (e. g. for 00059 * std::count_n()). 00060 * @return User-supplied functor (that may contain a part of the result). 00061 */ 00062 template<typename RandomAccessIterator, 00063 typename Op, 00064 typename Fu, 00065 typename Red, 00066 typename Result> 00067 Op 00068 for_each_template_random_access_ed(RandomAccessIterator begin, 00069 RandomAccessIterator end, 00070 Op o, Fu& f, Red r, Result base, 00071 Result& output, 00072 typename std::iterator_traits 00073 <RandomAccessIterator>:: 00074 difference_type bound) 00075 { 00076 typedef std::iterator_traits<RandomAccessIterator> traits_type; 00077 typedef typename traits_type::difference_type difference_type; 00078 const difference_type length = end - begin; 00079 Result *thread_results; 00080 bool* constructed; 00081 00082 thread_index_t num_threads = 00083 __gnu_parallel::min<difference_type>(get_max_threads(), length); 00084 00085 # pragma omp parallel num_threads(num_threads) 00086 { 00087 # pragma omp single 00088 { 00089 num_threads = omp_get_num_threads(); 00090 thread_results = static_cast<Result*>( 00091 ::operator new(num_threads * sizeof(Result))); 00092 constructed = new bool[num_threads]; 00093 } 00094 00095 thread_index_t iam = omp_get_thread_num(); 00096 00097 // Neutral element. 00098 Result* reduct = static_cast<Result*>(::operator new(sizeof(Result))); 00099 00100 difference_type 00101 start = equally_split_point(length, num_threads, iam), 00102 stop = equally_split_point(length, num_threads, iam + 1); 00103 00104 if (start < stop) 00105 { 00106 new(reduct) Result(f(o, begin + start)); 00107 ++start; 00108 constructed[iam] = true; 00109 } 00110 else 00111 constructed[iam] = false; 00112 00113 for (; start < stop; ++start) 00114 *reduct = r(*reduct, f(o, begin + start)); 00115 00116 thread_results[iam] = *reduct; 00117 } //parallel 00118 00119 for (thread_index_t i = 0; i < num_threads; ++i) 00120 if (constructed[i]) 00121 output = r(output, thread_results[i]); 00122 00123 // Points to last element processed (needed as return value for 00124 // some algorithms like transform). 00125 f.finish_iterator = begin + length; 00126 00127 delete[] thread_results; 00128 delete[] constructed; 00129 00130 return o; 00131 } 00132 00133 } // end namespace 00134 00135 #endif /* _GLIBCXX_PARALLEL_PAR_LOOP_H */