parallel/numeric

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

Generated on 19 Jun 2018 for libstdc++ by  doxygen 1.6.1