ceph/src/boost/libs/thread/doc/parallel.qbk

   1 [/
   2  / Copyright (c) 2014 Vicente J. Botet Escriba
   3  /
   4  / Distributed under the Boost Software License, Version 1.0. (See accompanying
   5  / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6  /]
   7
   8 [//////////////////////////////////////////////////////////]
   9 [section:parallel Parallel - Fork-Join -- EXPERIMENTAL]
  10
  11 [section:fork_join Fork-Join]
  12
  13 [warning These features are experimental and subject to change in future versions. There are not too much tests yet, so it is possible that you can find out some trivial bugs :(]
  14
  15 [note These features are based on the [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4088.pdf [* n4088 - Task Region R3]] C++1y proposal from P. Halpern, A. Robison, A. Laksberg, H. Sutter, et al.  The text that follows has been adapted from this paper to show the differences.]
  16
  17 The major difference respect to the standard proposal is that we are able to use a common executor for several task regions.
  18
  19 [note
  20 Up to now, Boost.Thread doesn't implement the parallel algorithms as defined in [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4105.pdf [* n4105 - Information technology – Programming languages, their environments and system software interfaces – Technical Specification for C++ Extensions for Parallelism]].
  21 ]
  22
  23 [////////////////////]
  24 [section Introduction]
  25
  26
  27 This module introduces a C++11/c++14 library function template `task_region` and a library class `task_region_handle`
  28 with member functions `run` and `wait` that together enable developers to write expressive and portable fork-join
  29 parallel code.
  30
  31 The working draft for the Parallelism TS [@http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4105.pdf [*N4105]] augments the STL algorithms with the inclusion of parallel execution policies. Programmers use these as a basis to write additional high-level algorithms that can be implemented in terms of the provided parallel algorithms. However, the scope of n4105 does not include lower-level mechanisms to express arbitrary fork-join parallelism
  32
  33 The `task_region`, `run` and the `wait` functions provided by this library are based on the `task_group` concept that is a part of the common subset of the PPL and the TBB libraries.
  34
  35 [endsect] [/ Introduction]
  36
  37
  38 [/////////////////////////]
  39 [section:tutorial Tutorial]
  40
  41 Consider an example of a parallel traversal of a tree, where a user-provided function compute is applied to each node of the tree, returning the sum of the results:
  42
  43   template<typename Func>
  44   int traverse(node *n, Func&& compute)
  45   {
  46     int left = 0, right = 0;
  47     task_region([&](task_region_handle& tr) {
  48       if (n->left)
  49         tr.run([&] { left = traverse(n->left, compute); });
  50       if (n->right)
  51         tr.run([&] { right = traverse(n->right, compute); });
  52     });
  53     return compute(n) + left + right;
  54   }
  55
  56 The example above demonstrates the use of two of the functions proposed in this paper, `task_region` and
  57 `task_region_handle::run`.
  58 The `task_region` function delineates a region in a program code potentially containing invocations of tasks
  59 spawned by the `run` member function of the `task_region_handle` class.
  60
  61 The run function spawns a task, a unit of work that is allowed to execute in parallel with respect to the caller.
  62 Any parallel tasks spawned by `run` within the `task_region` are joined back to a single thread of execution at
  63 the end of the `task_region`.
  64
  65 `run` takes a user-provided function object `f` and starts it asynchronously - i.e. it may return before the
  66 execution of `f` completes. The implementation's scheduler may choose to run `f` immediately or delay running
  67 `f` until compute resources become available.
  68
  69 A `task_region_handle` can be constructed only by `task_region` because it has no public constructors.
  70 Thus, `run` can be invoked (directly or indirectly) only from a user-provided function passed to `task_region`:
  71
  72   void g();
  73   void f(task_region_handle& tr)
  74   {
  75     tr.run(g); // OK, invoked from within task_region in h
  76   }
  77   void h()
  78   {
  79     task_region(f);
  80   }
  81
  82   int main()
  83   {
  84     task_region_handle tr; // Error: no public constructor
  85     tr.run(g); // No way to call run outside of a task_region
  86     return 0;
  87   }
  88
  89 [endsect] [/ Tutorial]
  90
  91 [////////////////]
  92 [section:examples Examples]
  93
  94 [section:fib Parallel Fibonacci]
  95
  96
  97 This is surely the worst implementation of the Fibonacci function. Anyway, here it is, as it is simple and shows the fork-join structure clearly. `Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)`, so the task decomposition is trivial.
  98
  99   int fib_task_region(int n)
 100   {
 101     using boost::experimental::parallel::task_region;
 102     using boost::experimental::parallel::task_region_handle;
 103
 104     if (n == 0) return 0;
 105     if (n == 1) return 1;
 106
 107     int n1;
 108     int n2;
 109
 110     task_region([&](task_region_handle& trh)
 111         {
 112           trh.run([&]
 113               {
 114                 n1 = fib_task_region(n - 1);
 115               });
 116
 117           n2 = fib_task_region(n - 2);
 118         });
 119
 120     return n1 + n2;
 121   }
 122
 123   int main()
 124   {
 125     for (int i = 0; i<10; ++i) {
 126       std::cout << fib_task_region(i) << " ";
 127     }
 128     std::cout << std::endl;
 129   }
 130
 131 [endsect] [/ Fib]
 132 [section:fibex Parallel Fibonacci - Specific executor]
 133
 134 The previous example make use of an implementation defined way to spawn the tasks. Often the user wants to master how the task must be spawned. There is an overload of `task_region` that accept an additional `Executor` parameter and a function that takes as parameter a `task_region_handle_gen<Executor>`. `task_region_handle_gen<Executor>` run uses this executor to spawn the tasks.
 135
 136   template <class Ex>
 137   int fib_task_region_gen( Ex& ex, int n)
 138   {
 139     using boost::experimental::parallel::task_region;
 140     using boost::experimental::parallel::task_region_handle_gen;
 141
 142     if (n == 0) return 0;
 143     if (n == 1) return 1;
 144
 145     int n1;
 146     int n2;
 147
 148     task_region(ex, [&](task_region_handle_gen<Ex>& trh) // (2)
 149         {
 150           trh.run([&]
 151               {
 152                 n1 = fib_task_region(n - 1);
 153               });
 154
 155           n2 = fib_task_region(n - 2);
 156         });
 157
 158     return n1 + n2;
 159   }
 160
 161   int main()
 162   {
 163     boost::basic_thread_pool tp; // (1)
 164     for (int i = 0; i<10; ++i) {
 165       std::cout << fib_task_region_gen(tp,i) << " ";
 166     }
 167     std::cout << std::endl;
 168     return 0;
 169   }
 170
 171
 172 The specific executor is declared in line (1) and it is used in line (2).
 173
 174 [endsect] [/ Fib ex]
 175
 176
 177
 178
 179 [section:quick_sort Parallel Accumulate]
 180
 181
 182 [endsect] [/ Accumulate]
 183
 184 [section:quick_sort Parallel Quick Sort]
 185
 186
 187
 188 [endsect] [/ QuickSort]
 189 [endsect] [/ Examples]
 190
 191
 192 [////////////////////////]
 193 [section:rationale Design Rationale]
 194
 195
 196 [endsect] [/ Design Rationale]
 197 [endsect] [/ Fork-Join]
 198
 199 [/////////////////////]
 200 [section:ref Reference -- EXPERIMENTAL]
 201
 202 [/////////////////////////]
 203 [section:v1 Parallel V1]
 204
 205 [section:exception_list Header `<experimental/exception_list.hpp>`]
 206
 207   namespace boost
 208   {
 209   namespace experimental
 210   {
 211   namespace parallel
 212   {
 213   inline namespace v1
 214   {
 215
 216     class exception_list;
 217
 218   } // v1
 219   } // parallel
 220   } // experimental
 221   } // boost
 222
 223
 224 [/////////////////////////]
 225 [section:exception_list Class `exception_list`]
 226
 227   namespace boost
 228   {
 229   namespace experimental
 230   {
 231   namespace parallel
 232   {
 233   inline namespace v1
 234   {
 235
 236     class exception_list: public std::exception
 237     {
 238     public:
 239       typedef 'implementation defined' const_iterator;
 240
 241       ~exception_list() noexcept {}
 242
 243       void add(exception_ptr const& e);
 244       size_t size() const noexcept;
 245       const_iterator begin() const noexcept;
 246       const_iterator end() const noexcept;
 247       const char* what() const noexcept;
 248
 249     };
 250
 251   } // v1
 252   } // parallel
 253   } // experimental
 254   } // boost
 255
 256
 257 [endsect] [/ exception_list]
 258
 259 [endsect] [/ exception_list.hpp]
 260
 261 [endsect] [/ Parallel V1]
 262
 263 [////////////////////////////////////////////////////////////////////]
 264 [section:v2 Parallel V2]
 265 [////////////////////////////////////////////////////////////////////]
 266 [section:concepts Concepts]
 267 [////////////////////////////////////////////////////////////////////]
 268 [section:regionCallable Concept `Region_Callable`]
 269
 270 [endsect] [/ Region_Callable]
 271 [////////////////////////////////////////////////////////////////////]
 272 [section:taskCallable Concept `Task_Callable`]
 273
 274
 275 [endsect] [/ Task_Callable]
 276 [////////////////////////////////////////////////////////////////////]
 277 [endsect] [/ Concepts]
 278 [////////////////////////////////////////////////////////////////////]
 279 [section:task_region Header `<experimental/task_region.hpp>`]
 280
 281   namespace boost
 282   {
 283   namespace experimental
 284   {
 285   namespace parallel
 286   {
 287   inline namespace v2
 288   {
 289
 290     class task_canceled_exception;
 291
 292     template <class Executor>
 293     class task_region_handle_gen;
 294
 295     using default_executor = 'implementation defined';
 296
 297     class task_region_handle;
 298
 299     template <typename Executor, typename F>
 300       void task_region_final(Executor& ex, F&& f);
 301     template <typename F>
 302       void task_region_final(F&& f);
 303
 304     template <typename Executor, typename F>
 305       void task_region(Executor& ex, F&& f);
 306     template <typename F>
 307       void task_region(F&& f);
 308
 309   } // v2
 310   } // parallel
 311   } // experimental
 312   } // boost
 313
 314
 315 [////////////////////////////////////////////////////////////////////]
 316 [section:task_canceled_exception Class `task_canceled_exception `]
 317
 318   namespace boost
 319   {
 320   namespace experimental
 321   {
 322   namespace parallel
 323   {
 324   inline namespace v2
 325   {
 326
 327     class task_canceled_exception: public std::exception
 328     {
 329     public:
 330       task_canceled_exception() noexcept;
 331       task_canceled_exception(const task_canceled_exception&) noexcept;
 332       task_canceled_exception& operator=(const task_canceled_exception&) noexcept;
 333       virtual const char* what() const noexcept;
 334     };
 335
 336   } // v2
 337   } // parallel
 338   } // experimental
 339   } // boost
 340
 341 [endsect] [/ task_canceled_exception]
 342 [////////////////////////////////////////////////////////////////////]
 343 [section:task_region_handle_gen Template Class `task_region_handle_gen<>`]
 344
 345   namespace boost
 346   {
 347   namespace experimental
 348   {
 349   namespace parallel
 350   {
 351   inline namespace v2
 352   {
 353
 354     template <class Executor>
 355     class task_region_handle_gen
 356     {
 357     protected:
 358       task_region_handle_gen(Executor& ex);
 359
 360       ~task_region_handle_gen();
 361
 362     public:
 363       task_region_handle_gen(const task_region_handle_gen&) = delete;
 364       task_region_handle_gen& operator=(const task_region_handle_gen&) = delete;
 365       task_region_handle_gen* operator&() const = delete;
 366
 367       template<typename F>
 368       void run(F&& f);
 369
 370       void wait();
 371     };
 372
 373   } // v2
 374   } // parallel
 375   } // experimental
 376   } // boost
 377
 378 [endsect] [/ task_region_handle_gen]
 379 [////////////////////////////////////////////////////////////////////]
 380 [section:default_executor Class `default_executor `]
 381
 382   namespace boost
 383   {
 384   namespace experimental
 385   {
 386   namespace parallel
 387   {
 388   inline namespace v2
 389   {
 390
 391     using default_executor = 'implementation defined';
 392
 393   } // v2
 394   } // parallel
 395   } // experimental
 396   } // boost
 397
 398 [endsect] [/ default_executor]
 399 [////////////////////////////////////////////////////////////////////]
 400 [section:task_region_handle Class `task_region_handle `]
 401
 402   namespace boost
 403   {
 404   namespace experimental
 405   {
 406   namespace parallel
 407   {
 408   inline namespace v2
 409   {
 410
 411     class task_region_handle :
 412       public task_region_handle_gen<default_executor>
 413     {
 414     protected:
 415       task_region_handle();
 416       task_region_handle(const task_region_handle&) = delete;
 417       task_region_handle& operator=(const task_region_handle&) = delete;
 418       task_region_handle* operator&() const = delete;
 419
 420     };
 421
 422   } // v2
 423   } // parallel
 424   } // experimental
 425   } // boost
 426
 427 [endsect] [/ task_region_handle]
 428 [////////////////////////////////////////////////////////////////////]
 429 [section:task_region_final Template Function `task_region_final `]
 430
 431   namespace boost
 432   {
 433   namespace experimental
 434   {
 435   namespace parallel
 436   {
 437   inline namespace v2
 438   {
 439
 440     template <typename Executor, typename F>
 441       void task_region_final(Executor& ex, F&& f);
 442     template <typename F>
 443       void task_region_final(F&& f);
 444
 445   } // v2
 446   } // parallel
 447   } // experimental
 448   } // boost
 449
 450 [endsect] [/ task_region_final]
 451 [////////////////////////////////////////////////////////////////////]
 452 [section:task_region Template Function `task_region `]
 453
 454   namespace boost
 455   {
 456   namespace experimental
 457   {
 458   namespace parallel
 459   {
 460   inline namespace v2
 461   {
 462
 463     template <typename Executor, typename F>
 464       void task_region(Executor& ex, F&& f);
 465     template <typename F>
 466       void task_region(F&& f);
 467
 468   } // v2
 469   } // parallel
 470   } // experimental
 471   } // boost
 472
 473 [endsect] [/ task_region]
 474
 475
 476
 477
 478 [endsect] [/ task_region.hpp]
 479 [endsect] [/ Parallel V2]
 480 [endsect] [/ Reference]
 481
 482 [endsect] [/ Parallel]