workstealing.h

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 /** @file parallel/workstealing.h
00032  *  @brief Parallelization of embarrassingly parallel execution by
00033  *  means of work-stealing.
00034  *
00035  *  Work stealing is described in
00036  *
00037  *  R. D. Blumofe and C. E. Leiserson.
00038  *  Scheduling multithreaded computations by work stealing.
00039  *  Journal of the ACM, 46(5):720–748, 1999.
00040  *
00041  *  This file is a GNU parallel extension to the Standard C++ Library.
00042  */
00043 
00044 // Written by Felix Putze.
00045 
00046 #ifndef _GLIBCXX_PARALLEL_WORKSTEALING_H
00047 #define _GLIBCXX_PARALLEL_WORKSTEALING_H 1
00048 
00049 #include <parallel/parallel.h>
00050 #include <parallel/random_number.h>
00051 #include <parallel/compatibility.h>
00052 
00053 namespace __gnu_parallel
00054 {
00055 
00056 #define _GLIBCXX_JOB_VOLATILE volatile
00057 
00058 /** @brief One job for a certain thread. */
00059 template<typename _DifferenceTp>
00060   struct Job
00061   {
00062     typedef _DifferenceTp difference_type;
00063 
00064     /** @brief First element.
00065      *
00066      *  Changed by owning and stealing thread. By stealing thread,
00067      *  always incremented. */
00068     _GLIBCXX_JOB_VOLATILE difference_type first;
00069 
00070     /** @brief Last element.
00071      *
00072      *  Changed by owning thread only. */
00073     _GLIBCXX_JOB_VOLATILE difference_type last;
00074 
00075     /** @brief Number of elements, i. e. @c last-first+1.
00076      *
00077      *  Changed by owning thread only. */
00078     _GLIBCXX_JOB_VOLATILE difference_type load;
00079   };
00080 
00081 /** @brief Work stealing algorithm for random access iterators.
00082   *
00083   *  Uses O(1) additional memory. Synchronization at job lists is
00084   *  done with atomic operations.
00085   *  @param begin Begin iterator of element sequence.
00086   *  @param end End iterator of element sequence.
00087   *  @param op User-supplied functor (comparator, predicate, adding
00088   *  functor, ...).
00089   *  @param f Functor to "process" an element with op (depends on
00090   *  desired functionality, e. g. for std::for_each(), ...).
00091   *  @param r Functor to "add" a single result to the already
00092   *  processed elements (depends on functionality).
00093   *  @param base Base value for reduction.
00094   *  @param output Pointer to position where final result is written to
00095   *  @param bound Maximum number of elements processed (e. g. for
00096   *  std::count_n()).
00097   *  @return User-supplied functor (that may contain a part of the result).
00098   */
00099 template<typename RandomAccessIterator,
00100      typename Op,
00101      typename Fu,
00102      typename Red,
00103      typename Result>
00104   Op
00105   for_each_template_random_access_workstealing(RandomAccessIterator begin,
00106                            RandomAccessIterator end,
00107                            Op op, Fu& f, Red r,
00108                            Result base, Result& output,
00109                            typename std::iterator_traits
00110                            <RandomAccessIterator>::
00111                            difference_type bound)
00112   {
00113     _GLIBCXX_CALL(end - begin)
00114 
00115     typedef std::iterator_traits<RandomAccessIterator> traits_type;
00116     typedef typename traits_type::difference_type difference_type;
00117     
00118     const _Settings& __s = _Settings::get();
00119 
00120     difference_type chunk_size = static_cast<difference_type>(__s.workstealing_chunk_size);
00121 
00122     // How many jobs?
00123     difference_type length = (bound < 0) ? (end - begin) : bound;
00124 
00125     // To avoid false sharing in a cache line.
00126     const int stride = __s.cache_line_size * 10 / sizeof(Job<difference_type>) + 1;
00127 
00128     // Total number of threads currently working.
00129     thread_index_t busy = 0;
00130 
00131     Job<difference_type> *job;
00132 
00133     omp_lock_t output_lock;
00134     omp_init_lock(&output_lock);
00135 
00136     // Write base value to output.
00137     output = base;
00138 
00139     // No more threads than jobs, at least one thread.
00140     thread_index_t num_threads =
00141         __gnu_parallel::max<thread_index_t>(1,
00142             __gnu_parallel::min<difference_type>(length, get_max_threads()));
00143 
00144 #   pragma omp parallel shared(busy) num_threads(num_threads)
00145       {
00146 
00147 #       pragma omp single
00148           {
00149             num_threads = omp_get_num_threads();
00150 
00151             // Create job description array.
00152             job = new Job<difference_type>[num_threads * stride];
00153           }
00154 
00155         // Initialization phase.
00156 
00157         // Flags for every thread if it is doing productive work.
00158         bool iam_working = false;
00159 
00160         // Thread id.
00161         thread_index_t iam = omp_get_thread_num();
00162 
00163         // This job.
00164         Job<difference_type>& my_job = job[iam * stride];
00165 
00166         // Random number (for work stealing).
00167         thread_index_t victim;
00168 
00169         // Local value for reduction.
00170         Result result = Result();
00171 
00172         // Number of elements to steal in one attempt.
00173         difference_type steal;
00174 
00175         // Every thread has its own random number generator
00176         // (modulo num_threads).
00177         random_number rand_gen(iam, num_threads);
00178 
00179         // This thread is currently working.
00180 #       pragma omp atomic
00181           ++busy;
00182 
00183         iam_working = true;
00184 
00185         // How many jobs per thread? last thread gets the rest.
00186         my_job.first =
00187             static_cast<difference_type>(iam * (length / num_threads));
00188 
00189         my_job.last = (iam == (num_threads - 1)) ?
00190             (length - 1) : ((iam + 1) * (length / num_threads) - 1);
00191         my_job.load = my_job.last - my_job.first + 1;
00192 
00193         // Init result with first value (to have a base value for reduction).
00194         if (my_job.first <= my_job.last)
00195           {
00196             // Cannot use volatile variable directly.
00197             difference_type my_first = my_job.first;
00198             result = f(op, begin + my_first);
00199             ++my_job.first;
00200             --my_job.load;
00201           }
00202 
00203         RandomAccessIterator current;
00204 
00205 #       pragma omp barrier
00206 
00207         // Actual work phase
00208         // Work on own or stolen start
00209         while (busy > 0)
00210           {
00211             // Work until no productive thread left.
00212 #           pragma omp flush(busy)
00213 
00214             // Thread has own work to do
00215             while (my_job.first <= my_job.last)
00216               {
00217                 // fetch-and-add call
00218                 // Reserve current job block (size chunk_size) in my queue.
00219                 difference_type current_job =
00220                   fetch_and_add<difference_type>(&(my_job.first), chunk_size);
00221 
00222                 // Update load, to make the three values consistent,
00223                 // first might have been changed in the meantime
00224                 my_job.load = my_job.last - my_job.first + 1;
00225                 for (difference_type job_counter = 0;
00226                      job_counter < chunk_size && current_job <= my_job.last;
00227                      ++job_counter)
00228                   {
00229                     // Yes: process it!
00230                     current = begin + current_job;
00231                     ++current_job;
00232 
00233                     // Do actual work.
00234                     result = r(result, f(op, current));
00235                   }
00236 
00237 #               pragma omp flush(busy)
00238               }
00239 
00240             // After reaching this point, a thread's job list is empty.
00241             if (iam_working)
00242               {
00243                 // This thread no longer has work.
00244 #               pragma omp atomic
00245                 --busy;
00246 
00247                 iam_working = false;
00248               }
00249 
00250             difference_type supposed_first, supposed_last, supposed_load;
00251             do
00252               {
00253                 // Find random nonempty deque (not own), do consistency check.
00254                 yield();
00255 #               pragma omp flush(busy)
00256                 victim = rand_gen();
00257                 supposed_first = job[victim * stride].first;
00258                 supposed_last = job[victim * stride].last;
00259                 supposed_load = job[victim * stride].load;
00260               }
00261             while (busy > 0
00262               && ((supposed_load <= 0)
00263                 || ((supposed_first + supposed_load - 1) != supposed_last)));
00264 
00265             if (busy == 0)
00266               break;
00267 
00268             if (supposed_load > 0)
00269               {
00270                 // Has work and work to do.
00271                 // Number of elements to steal (at least one).
00272                 steal = (supposed_load < 2) ? 1 : supposed_load / 2;
00273 
00274                 // Push victim's start forward.
00275                 difference_type stolen_first =
00276                     fetch_and_add<difference_type>(
00277                         &(job[victim * stride].first), steal);
00278                 difference_type stolen_try =
00279                     stolen_first + steal - difference_type(1);
00280 
00281                 my_job.first = stolen_first;
00282                 my_job.last = __gnu_parallel::min(stolen_try, supposed_last);
00283                 my_job.load = my_job.last - my_job.first + 1;
00284 
00285                 // Has potential work again.
00286 #               pragma omp atomic
00287                   ++busy;
00288                 iam_working = true;
00289 
00290 #               pragma omp flush(busy)
00291               }
00292 #           pragma omp flush(busy)
00293           } // end while busy > 0
00294             // Add accumulated result to output.
00295         omp_set_lock(&output_lock);
00296         output = r(output, result);
00297         omp_unset_lock(&output_lock);
00298       }
00299 
00300     delete[] job;
00301 
00302     // Points to last element processed (needed as return value for
00303     // some algorithms like transform)
00304     f.finish_iterator = begin + length;
00305 
00306     omp_destroy_lock(&output_lock);
00307 
00308     return op;
00309   }
00310 } // end namespace
00311 
00312 #endif

Generated on Wed Dec 31 12:49:06 2008 for libstdc++ by  doxygen 1.5.6