parallel/numeric

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
00017 // along with this library; see the file COPYING.  If not, write to
00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
00019 // MA 02111-1307, USA.
00020 
00021 // As a special exception, you may use this file as part of a free
00022 // software library without restriction.  Specifically, if other files
00023 // instantiate templates or use macros or inline functions from this
00024 // file, or you compile this file and link it with other files to
00025 // produce an executable, this file does not by itself cause the
00026 // resulting executable to be covered by the GNU General Public
00027 // License.  This exception does not however invalidate any other
00028 // reasons why the executable file might be covered by the GNU General
00029 // Public License.
00030 
00031 /**
00032  * @file parallel/numeric
00033 *
00034  * @brief Parallel STL function calls corresponding to stl_numeric.h.
00035  * The functions defined here mainly do case switches and
00036  * call the actual parallelized versions in other files.
00037  * Inlining policy: Functions that basically only contain one function call,
00038  * are declared inline.
00039  *  This file is a GNU parallel extension to the Standard C++ Library.
00040  */
00041 
00042 // Written by Johannes Singler and Felix Putze.
00043 
00044 #ifndef _GLIBCXX_PARALLEL_NUMERIC_H
00045 #define _GLIBCXX_PARALLEL_NUMERIC_H 1
00046 
00047 #include <numeric>
00048 #include <functional>
00049 #include <parallel/numericfwd.h>
00050 #include <parallel/iterator.h>
00051 #include <parallel/for_each.h>
00052 #include <parallel/for_each_selectors.h>
00053 #include <parallel/partial_sum.h>
00054 
00055 namespace std
00056 {
00057 namespace __parallel
00058 {
00059   // Sequential fallback.
00060   template<typename InputIterator, typename T>
00061     inline T
00062     accumulate(InputIterator begin, InputIterator end, T init, 
00063            __gnu_parallel::sequential_tag)
00064     { return _GLIBCXX_STD_P::accumulate(begin, end, init); }
00065 
00066   template<typename InputIterator, typename T, typename BinaryOperation>
00067     inline T
00068     accumulate(InputIterator begin, InputIterator end, T init,
00069            BinaryOperation binary_op, __gnu_parallel::sequential_tag)
00070     { return _GLIBCXX_STD_P::accumulate(begin, end, init, binary_op); }
00071 
00072   // Sequential fallback for input iterator case.
00073   template<typename InputIterator, typename T, typename IteratorTag>
00074     inline T
00075     accumulate_switch(InputIterator begin, InputIterator end,
00076               T init, IteratorTag) 
00077     { return accumulate(begin, end, init, __gnu_parallel::sequential_tag()); }
00078 
00079   template<typename InputIterator, typename T, typename BinaryOperation,
00080        typename IteratorTag>
00081     inline T
00082     accumulate_switch(InputIterator begin, InputIterator end, T init, 
00083               BinaryOperation binary_op, IteratorTag)
00084     { return accumulate(begin, end, init, binary_op, 
00085             __gnu_parallel::sequential_tag()); }
00086 
00087   // Parallel algorithm for random access iterators.
00088   template<typename _RandomAccessIterator, typename T,
00089        typename BinaryOperation>
00090     T
00091     accumulate_switch(_RandomAccessIterator begin, _RandomAccessIterator end, 
00092               T init, BinaryOperation binary_op, 
00093               random_access_iterator_tag, 
00094               __gnu_parallel::_Parallelism parallelism_tag  
00095               = __gnu_parallel::parallel_unbalanced)
00096     {
00097       if (_GLIBCXX_PARALLEL_CONDITION(
00098         static_cast<__gnu_parallel::sequence_index_t>(end - begin)
00099         >= __gnu_parallel::_Settings::get().accumulate_minimal_n
00100         && __gnu_parallel::is_parallel(parallelism_tag)))
00101     {
00102       T res = init;
00103       __gnu_parallel::accumulate_selector<_RandomAccessIterator>
00104         my_selector;
00105       __gnu_parallel::
00106 	    for_each_template_random_access(begin, end,
00107                         __gnu_parallel::nothing(),
00108                         my_selector,
00109                         __gnu_parallel::
00110                         accumulate_binop_reduct
00111                         <BinaryOperation>(binary_op),
00112                         res, res, -1, parallelism_tag);
00113       return res;
00114     }
00115       else
00116     return accumulate(begin, end, init, binary_op, 
00117               __gnu_parallel::sequential_tag());
00118     }
00119 
00120   // Public interface.
00121   template<typename InputIterator, typename T>
00122     inline T
00123     accumulate(InputIterator begin, InputIterator end, T init, 
00124            __gnu_parallel::_Parallelism parallelism_tag)
00125     {
00126       typedef std::iterator_traits<InputIterator> iterator_traits;
00127       typedef typename iterator_traits::value_type value_type;
00128       typedef typename iterator_traits::iterator_category iterator_category;
00129 
00130       return accumulate_switch(begin, end, init,
00131                    __gnu_parallel::plus<T, value_type>(),
00132                    iterator_category(), parallelism_tag);
00133     }
00134 
00135   template<typename InputIterator, typename T>
00136     inline T
00137     accumulate(InputIterator begin, InputIterator end, T init)
00138     {
00139       typedef std::iterator_traits<InputIterator> iterator_traits;
00140       typedef typename iterator_traits::value_type value_type;
00141       typedef typename iterator_traits::iterator_category iterator_category;
00142 
00143       return accumulate_switch(begin, end, init,
00144                    __gnu_parallel::plus<T, value_type>(),
00145                    iterator_category());
00146     }
00147 
00148   template<typename InputIterator, typename T, typename BinaryOperation>
00149     inline T
00150     accumulate(InputIterator begin, InputIterator end, T init, 
00151            BinaryOperation binary_op, 
00152            __gnu_parallel::_Parallelism parallelism_tag)
00153     {
00154       typedef iterator_traits<InputIterator> iterator_traits;
00155       typedef typename iterator_traits::iterator_category iterator_category;
00156       return accumulate_switch(begin, end, init, binary_op, 
00157                    iterator_category(), parallelism_tag);
00158     }
00159 
00160   template<typename InputIterator, typename T, typename BinaryOperation>
00161     inline T
00162     accumulate(InputIterator begin, InputIterator end, T init, 
00163            BinaryOperation binary_op) 
00164     {
00165       typedef iterator_traits<InputIterator> iterator_traits;
00166       typedef typename iterator_traits::iterator_category iterator_category;
00167       return accumulate_switch(begin, end, init, binary_op, 
00168                    iterator_category());
00169     }
00170 
00171 
00172   // Sequential fallback.
00173   template<typename InputIterator1, typename InputIterator2, typename T>
00174     inline T
00175     inner_product(InputIterator1 first1, InputIterator1 last1, 
00176           InputIterator2 first2, T init,
00177           __gnu_parallel::sequential_tag)
00178     { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init); }
00179 
00180   template<typename InputIterator1, typename InputIterator2, typename T,
00181        typename BinaryFunction1, typename BinaryFunction2>
00182     inline T
00183     inner_product(InputIterator1 first1, InputIterator1 last1, 
00184           InputIterator2 first2, T init, BinaryFunction1 binary_op1, 
00185           BinaryFunction2 binary_op2, __gnu_parallel::sequential_tag)
00186     { return _GLIBCXX_STD_P::inner_product(first1, last1, first2, init, 
00187                        binary_op1, binary_op2); }
00188 
00189   // Parallel algorithm for random access iterators.
00190   template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00191        typename T, typename BinaryFunction1, typename BinaryFunction2>
00192     T
00193     inner_product_switch(RandomAccessIterator1 first1,
00194              RandomAccessIterator1 last1,
00195              RandomAccessIterator2 first2, T init,
00196              BinaryFunction1 binary_op1,
00197              BinaryFunction2 binary_op2,
00198              random_access_iterator_tag,
00199              random_access_iterator_tag,
00200              __gnu_parallel::_Parallelism parallelism_tag
00201              = __gnu_parallel::parallel_unbalanced)
00202     {
00203       if (_GLIBCXX_PARALLEL_CONDITION((last1 - first1)
00204                       >= __gnu_parallel::_Settings::get().
00205                       accumulate_minimal_n
00206                       && __gnu_parallel::
00207                       is_parallel(parallelism_tag)))
00208     {
00209       T res = init;
00210       __gnu_parallel::
00211         inner_product_selector<RandomAccessIterator1,
00212         RandomAccessIterator2, T> my_selector(first1, first2);
00213       __gnu_parallel::
00214 	    for_each_template_random_access(first1, last1, binary_op2,
00215                         my_selector, binary_op1,
00216                         res, res, -1, parallelism_tag);
00217       return res;
00218     }
00219       else
00220     return inner_product(first1, last1, first2, init, 
00221                  __gnu_parallel::sequential_tag());
00222     }
00223 
00224   // No parallelism for input iterators.
00225   template<typename InputIterator1, typename InputIterator2, typename T,
00226        typename BinaryFunction1, typename BinaryFunction2,
00227        typename IteratorTag1, typename IteratorTag2>
00228     inline T
00229     inner_product_switch(InputIterator1 first1, InputIterator1 last1, 
00230              InputIterator2 first2, T init, 
00231              BinaryFunction1 binary_op1,
00232              BinaryFunction2 binary_op2, 
00233              IteratorTag1, IteratorTag2)
00234     { return inner_product(first1, last1, first2, init,
00235                binary_op1, binary_op2,
00236                __gnu_parallel::sequential_tag()); }
00237 
00238   template<typename InputIterator1, typename InputIterator2, typename T,
00239        typename BinaryFunction1, typename BinaryFunction2>
00240     inline T
00241     inner_product(InputIterator1 first1, InputIterator1 last1, 
00242           InputIterator2 first2, T init, BinaryFunction1 binary_op1, 
00243           BinaryFunction2 binary_op2, 
00244           __gnu_parallel::_Parallelism parallelism_tag)
00245     {
00246       typedef iterator_traits<InputIterator1> traits1_type;
00247       typedef typename traits1_type::iterator_category iterator1_category;
00248 
00249       typedef iterator_traits<InputIterator2> traits2_type;
00250       typedef typename traits2_type::iterator_category iterator2_category;
00251 
00252       return inner_product_switch(first1, last1, first2, init, binary_op1, 
00253                   binary_op2, iterator1_category(), 
00254                   iterator2_category(), parallelism_tag);
00255     }
00256 
00257   template<typename InputIterator1, typename InputIterator2, typename T,
00258        typename BinaryFunction1, typename BinaryFunction2>
00259     inline T
00260     inner_product(InputIterator1 first1, InputIterator1 last1, 
00261           InputIterator2 first2, T init, BinaryFunction1 binary_op1, 
00262           BinaryFunction2 binary_op2)
00263     {
00264       typedef iterator_traits<InputIterator1> traits1_type;
00265       typedef typename traits1_type::iterator_category iterator1_category;
00266 
00267       typedef iterator_traits<InputIterator2> traits2_type;
00268       typedef typename traits2_type::iterator_category iterator2_category;
00269 
00270       return inner_product_switch(first1, last1, first2, init, binary_op1, 
00271                   binary_op2, iterator1_category(),
00272                   iterator2_category());
00273     }
00274 
00275   template<typename InputIterator1, typename InputIterator2, typename T>
00276     inline T
00277     inner_product(InputIterator1 first1, InputIterator1 last1, 
00278           InputIterator2 first2, T init, 
00279           __gnu_parallel::_Parallelism parallelism_tag)
00280     {
00281       typedef iterator_traits<InputIterator1> traits_type1;
00282       typedef typename traits_type1::value_type value_type1;
00283       typedef iterator_traits<InputIterator2> traits_type2;
00284       typedef typename traits_type2::value_type value_type2;
00285 
00286       typedef typename
00287     __gnu_parallel::multiplies<value_type1, value_type2>::result
00288         multiplies_result_type;
00289       return inner_product(first1, last1, first2, init,
00290                            __gnu_parallel::plus<T, multiplies_result_type>(),
00291                            __gnu_parallel::
00292                multiplies<value_type1, value_type2>(),
00293                            parallelism_tag);
00294     }
00295 
00296   template<typename InputIterator1, typename InputIterator2, typename T>
00297     inline T
00298     inner_product(InputIterator1 first1, InputIterator1 last1, 
00299           InputIterator2 first2, T init)
00300     {
00301       typedef iterator_traits<InputIterator1> traits_type1;
00302       typedef typename traits_type1::value_type value_type1;
00303       typedef iterator_traits<InputIterator2> traits_type2;
00304       typedef typename traits_type2::value_type value_type2;
00305 
00306       typedef typename
00307     __gnu_parallel::multiplies<value_type1, value_type2>::result
00308         multiplies_result_type;
00309       return inner_product(first1, last1, first2, init,
00310                            __gnu_parallel::plus<T, multiplies_result_type>(),
00311                            __gnu_parallel::
00312                multiplies<value_type1, value_type2>());
00313     }
00314 
00315   // Sequential fallback.
00316   template<typename InputIterator, typename OutputIterator>
00317     inline OutputIterator
00318     partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
00319         __gnu_parallel::sequential_tag)
00320     { return _GLIBCXX_STD_P::partial_sum(begin, end, result); }
00321 
00322   // Sequential fallback.
00323   template<typename InputIterator, typename OutputIterator,
00324        typename BinaryOperation>
00325     inline OutputIterator
00326     partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
00327         BinaryOperation bin_op, __gnu_parallel::sequential_tag)
00328     { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
00329 
00330   // Sequential fallback for input iterator case.
00331   template<typename InputIterator, typename OutputIterator,
00332        typename BinaryOperation, typename IteratorTag1,
00333        typename IteratorTag2>
00334     inline OutputIterator
00335     partial_sum_switch(InputIterator begin, InputIterator end,
00336                OutputIterator result, BinaryOperation bin_op,
00337                IteratorTag1, IteratorTag2)
00338     { return _GLIBCXX_STD_P::partial_sum(begin, end, result, bin_op); }
00339 
00340   // Parallel algorithm for random access iterators.
00341   template<typename InputIterator, typename OutputIterator,
00342        typename BinaryOperation>
00343     OutputIterator
00344     partial_sum_switch(InputIterator begin, InputIterator end,
00345                OutputIterator result, BinaryOperation bin_op,
00346                random_access_iterator_tag, random_access_iterator_tag)
00347     {
00348       if (_GLIBCXX_PARALLEL_CONDITION(
00349         static_cast<__gnu_parallel::sequence_index_t>(end - begin)
00350         >= __gnu_parallel::_Settings::get().partial_sum_minimal_n))
00351     return __gnu_parallel::parallel_partial_sum(begin, end,
00352                             result, bin_op);
00353       else
00354     return partial_sum(begin, end, result, bin_op,
00355                __gnu_parallel::sequential_tag());
00356     }
00357 
00358   // Public interface.
00359   template<typename InputIterator, typename OutputIterator>
00360     inline OutputIterator
00361     partial_sum(InputIterator begin, InputIterator end, OutputIterator result)
00362     {
00363       typedef typename iterator_traits<InputIterator>::value_type value_type;
00364       return partial_sum(begin, end, result, std::plus<value_type>());
00365     }
00366 
00367   // Public interface
00368   template<typename InputIterator, typename OutputIterator,
00369        typename BinaryOperation>
00370     inline OutputIterator
00371     partial_sum(InputIterator begin, InputIterator end, OutputIterator result,
00372         BinaryOperation binary_op)
00373     {
00374       typedef iterator_traits<InputIterator> traitsi_type;
00375       typedef typename traitsi_type::iterator_category iteratori_category;
00376 
00377       typedef iterator_traits<OutputIterator> traitso_type;
00378       typedef typename traitso_type::iterator_category iteratoro_category;
00379 
00380       return partial_sum_switch(begin, end, result, binary_op,
00381                 iteratori_category(), iteratoro_category());
00382     }
00383 
00384   // Sequential fallback.
00385   template<typename InputIterator, typename OutputIterator>
00386     inline OutputIterator
00387     adjacent_difference(InputIterator begin, InputIterator end,
00388             OutputIterator result, __gnu_parallel::sequential_tag)
00389     { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result); }
00390 
00391   // Sequential fallback.
00392   template<typename InputIterator, typename OutputIterator,
00393        typename BinaryOperation>
00394     inline OutputIterator
00395     adjacent_difference(InputIterator begin, InputIterator end,
00396             OutputIterator result, BinaryOperation bin_op,
00397             __gnu_parallel::sequential_tag)
00398     { return _GLIBCXX_STD_P::adjacent_difference(begin, end, result, bin_op); }
00399 
00400   // Sequential fallback for input iterator case.
00401   template<typename InputIterator, typename OutputIterator,
00402        typename BinaryOperation, typename IteratorTag1,
00403        typename IteratorTag2>
00404     inline OutputIterator
00405     adjacent_difference_switch(InputIterator begin, InputIterator end,
00406                    OutputIterator result, BinaryOperation bin_op,
00407                  IteratorTag1, IteratorTag2)
00408     { return adjacent_difference(begin, end, result, bin_op,  
00409                  __gnu_parallel::sequential_tag()); }
00410 
00411   // Parallel algorithm for random access iterators.
00412   template<typename InputIterator, typename OutputIterator,
00413        typename BinaryOperation>
00414     OutputIterator
00415     adjacent_difference_switch(InputIterator begin, InputIterator end,
00416                    OutputIterator result, BinaryOperation bin_op,
00417                    random_access_iterator_tag, 
00418                    random_access_iterator_tag,
00419                    __gnu_parallel::_Parallelism parallelism_tag
00420                    = __gnu_parallel::parallel_balanced)
00421     {
00422       if (_GLIBCXX_PARALLEL_CONDITION(
00423         static_cast<__gnu_parallel::sequence_index_t>(end - begin)
00424         >= __gnu_parallel::_Settings::get().adjacent_difference_minimal_n
00425         && __gnu_parallel::is_parallel(parallelism_tag)))
00426     {
00427       bool dummy = true;
00428       typedef __gnu_parallel::iterator_pair<InputIterator, OutputIterator,
00429         random_access_iterator_tag> ip;
00430       *result = *begin;
00431       ip begin_pair(begin + 1, result + 1),
00432         end_pair(end, result + (end - begin));
00433       __gnu_parallel::adjacent_difference_selector<ip> functionality;
00434       __gnu_parallel::
00435 	    for_each_template_random_access(begin_pair, end_pair, bin_op,
00436                         functionality,
00437                         __gnu_parallel::dummy_reduct(),
00438                         dummy, dummy, -1, parallelism_tag);
00439       return functionality.finish_iterator;
00440     }
00441       else
00442     return adjacent_difference(begin, end, result, bin_op, 
00443                    __gnu_parallel::sequential_tag());
00444     }
00445 
00446   // Public interface.
00447   template<typename InputIterator, typename OutputIterator>
00448     inline OutputIterator
00449     adjacent_difference(InputIterator begin, InputIterator end,
00450             OutputIterator result,
00451             __gnu_parallel::_Parallelism parallelism_tag)
00452     {
00453       typedef iterator_traits<InputIterator> traits_type;
00454       typedef typename traits_type::value_type value_type;
00455       return adjacent_difference(begin, end, result, std::minus<value_type>(),
00456                  parallelism_tag);
00457     }
00458 
00459   template<typename InputIterator, typename OutputIterator>
00460     inline OutputIterator
00461     adjacent_difference(InputIterator begin, InputIterator end,
00462             OutputIterator result)
00463     {
00464       typedef iterator_traits<InputIterator> traits_type;
00465       typedef typename traits_type::value_type value_type;
00466       return adjacent_difference(begin, end, result, std::minus<value_type>());
00467     }
00468 
00469   template<typename InputIterator, typename OutputIterator,
00470        typename BinaryOperation>
00471     inline OutputIterator
00472     adjacent_difference(InputIterator begin, InputIterator end,
00473             OutputIterator result, BinaryOperation binary_op,
00474             __gnu_parallel::_Parallelism parallelism_tag)
00475     {
00476       typedef iterator_traits<InputIterator> traitsi_type;
00477       typedef typename traitsi_type::iterator_category iteratori_category;
00478 
00479       typedef iterator_traits<OutputIterator> traitso_type;
00480       typedef typename traitso_type::iterator_category iteratoro_category;
00481 
00482       return adjacent_difference_switch(begin, end, result, binary_op,
00483                     iteratori_category(), 
00484                     iteratoro_category(), parallelism_tag);
00485     }
00486 
00487   template<typename InputIterator, typename OutputIterator,
00488        typename BinaryOperation>
00489     inline OutputIterator
00490     adjacent_difference(InputIterator begin, InputIterator end,
00491             OutputIterator result, BinaryOperation binary_op)
00492     {
00493       typedef iterator_traits<InputIterator> traitsi_type;
00494       typedef typename traitsi_type::iterator_category iteratori_category;
00495 
00496       typedef iterator_traits<OutputIterator> traitso_type;
00497       typedef typename traitso_type::iterator_category iteratoro_category;
00498 
00499       return adjacent_difference_switch(begin, end, result, binary_op,
00500                     iteratori_category(), 
00501                     iteratoro_category());
00502     }
00503 } // end namespace
00504 } // end namespace
00505 
00506 #endif /* _GLIBCXX_NUMERIC_H */

Generated on Sat Oct 25 05:09:06 2008 for libstdc++ by  doxygen 1.5.6