1.. Copyright (C) 2004-2008 The Trustees of Indiana University. 2 Use, modification and distribution is subject to the Boost Software 3 License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at 4 http://www.boost.org/LICENSE_1_0.txt) 5 6=============================== 7|Logo| Distributed Property Map 8=============================== 9 10A distributed property map adaptor is a property map whose stored 11values are distributed across multiple non-overlapping memory spaces 12on different processes. Values local to the current process are stored 13within a local property map and may be immediately accessed via 14``get`` and ``put``. Values stored on remote processes may also be 15accessed via ``get`` and ``put``, but the behavior differs slightly: 16 17 - ``put`` operations update a local ghost cell and send a "put" 18 message to the process that owns the value. The owner is free to 19 update its own "official" value or may ignore the put request. 20 21 - ``get`` operations returns the contents of the local ghost 22 cell. If no ghost cell is available, one is created using a 23 (customizable) default value. 24 25Using distributed property maps requires a bit more care than using 26local, sequential property maps. While the syntax and semantics are 27similar, distributed property maps may contain out-of-date 28information that can only be guaranteed to be synchronized by 29calling the ``synchronize`` function in all processes. 30 31To address the issue of out-of-date values, distributed property 32maps support multiple `consistency models`_ and may be supplied with a 33`reduction operation`_. 34 35Distributed property maps meet the requirements of the `Readable 36Property Map`_ and, potentially, the `Writable Property Map`_ and 37`Read/Write Property Map`_ concepts. Distributed property maps do 38*not*, however, meet the requirements of the `Lvalue Property Map`_ 39concept, because elements residing in another process are not 40directly addressible. There are several forms of distributed property 41maps: 42 43 - `Distributed property map adaptor`_ 44 - `Distributed iterator property map`_ 45 - `Distributed safe iterator property map`_ 46 - `Local property map`_ 47 48------------------ 49Consistency models 50------------------ 51 52Distributed property maps offer many consistency models, which affect 53how the values read from and written to remote keys relate to the 54"official" value for that key stored in the owning process. The 55consistency model of a distributed property map can be set with the 56member function ``set_consistency_model`` to a bitwise-OR of the 57flags in the ``boost::parallel::consistency_model`` enumeration. The 58individual flags are: 59 60 - ``cm_forward``: The default consistency model, which propagates 61 values forward from ``put`` operations on remote processors to 62 the owner of the value being changed. 63 64 - ``cm_backward``: After all values have been forwarded or flushed 65 to the owning processes, each process receives updates values for 66 each of its ghost cells. After synchronization, the values in 67 ghost cells are guaranteed to match the values stored on the 68 owning processor. 69 70 - ``cm_bidirectional``: A combination of both ``cm_forward`` and 71 ``cm_backward``. 72 73 - ``cm_flush``: At the beginning of synchronization, all of the 74 values stored locally in ghost cells are sent to their owning 75 processors. 76 77 - ``cm_reset``: Executes a ``reset()`` operation after 78 synchronization, setting the values in each ghost cell to their 79 default value. 80 81 - ``cm_clear``: Executes a ``clear()`` operation after 82 synchronizing, eliminating all ghost cells. 83 84 85There are several common combinations of flags that result in 86interesting consistency models. Some of these combinations are: 87 88 - ``cm_forward``: By itself, the forward consistency model enables 89 algorithms such as `Dijkstra's shortest paths`_ and 90 `Breadth-First Search`_ to operate correctly. 91 92 - ``cm_flush & cm_reset``: All updates values are queued locally, 93 then flushed during the synchronization step. Once the flush has 94 occurred, the ghost cells are restored to their default 95 values. This consistency model is used by the PageRank_ 96 implementation to locally accumulate rank for each node. 97 98 99------------------- 100Reduction operation 101------------------- 102 103The reduction operation maintains consistency by determining how 104multiple writes to a property map are resolved and what the property 105map should do if unknown values are requested. More specifically, a 106reduction operation is used in two cases: 107 108 1. When a value is needed for a remote key but no value is 109 immediately available, the reduction operation provides a 110 suitable default. For instance, a distributed property map 111 storing distances may have a reduction operation that returns 112 an infinite value as the default, whereas a distributed 113 property map for vertex colors may return white as the 114 default. 115 116 2. When a value is received from a remote process, the process 117 owning the key associated with that value must determine which 118 value---the locally stored value, the value received from a 119 remote process, or some combination of the two---will be 120 stored as the "official" value in the property map. The 121 reduction operation transforms the local and remote values 122 into the "official" value to be stored. 123 124The reduction operation of a distributed property map can be set with 125the ``set_reduce`` method of ``distributed_property_map``. The reduce 126operation is a function object with two signatures. The first 127signature takes a (remote) key and returns a default value for it, 128whereas the second signatures takes a key and two values (local first, 129then remote) and will return the combined value that will be stored in 130the local property map. Reduction operations must also contain a 131static constant ``non_default_resolver", which states whether the 132reduction operation's default value actually acts like a default 133value. It should be ``true`` when the default is meaningful (e.g., 134infinity for a distance) and ``false`` when the default should not be 135used. 136 137The following reduction operation is used by the distributed PageRank 138algorithm. The default rank for a remote node is 0. Rank is 139accumulated locally, and then the reduction operation combines local 140and remote values by adding them. Combined with a consistency model 141that flushes all values to the owner and then resets the values 142locally in each step, the resulting property map will compute partial 143sums on each processor and then accumulate the results on the owning 144processor. The PageRank reduction operation is defined as follows. 145 146:: 147 148 template<typename T> 149 struct rank_accumulate_reducer { 150 static const bool non_default_resolver = true; 151 152 // The default rank of an unknown node 153 template<typename K> 154 T operator()(const K&) const { return T(0); } 155 156 template<typename K> 157 T operator()(const K&, const T& x, const T& y) const { return x + y; } 158 }; 159 160 161-------------------------------- 162Distributed property map adaptor 163-------------------------------- 164 165The distributed property map adaptor creates a distributed property 166map from a local property map, a `process group`_ over which 167distribution should occur, and a `global descriptor`_ type that 168indexes the distributed property map. 169 170 171Synopsis 172~~~~~~~~ 173 174:: 175 176 template<typename ProcessGroup, typename LocalPropertyMap, typename Key, 177 typename GhostCellS = gc_mapS> 178 class distributed_property_map 179 { 180 public: 181 typedef ... ghost_regions_type; 182 183 distributed_property_map(); 184 185 distributed_property_map(const ProcessGroup& pg, 186 const LocalPropertyMap& pm); 187 188 template<typename Reduce> 189 distributed_property_map(const ProcessGroup& pg, 190 const LocalPropertyMap& pm, 191 const Reduce& reduce); 192 193 template<typename Reduce> void set_reduce(const Reduce& reduce); 194 void set_consistency_model(int model); 195 196 void flush(); 197 void reset(); 198 void clear(); 199 }; 200 201 reference get(distributed_property_map pm, const key_type& key); 202 203 void 204 put(distributed_property_map pm, const key_type& key, const value_type& value); 205 local_put(distributed_property_map pm, const key_type& key, const value_type& value); 206 207 void request(distributed_property_map pm, const key_type& key); 208 209 void synchronize(distributed_property_map& pm); 210 211 template<typename Key, typename ProcessGroup, typename LocalPropertyMap> 212 distributed_property_map<ProcessGroup, LocalPropertyMap, Key> 213 make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap); 214 215 template<typename Key, typename ProcessGroup, typename LocalPropertyMap, 216 typename Reduce> 217 distributed_property_map<ProcessGroup, LocalPropertyMap, Key> 218 make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap, 219 Reduce reduce); 220 221Template parameters 222~~~~~~~~~~~~~~~~~~~ 223 224**ProcessGroup**: 225 The type of the process group over which the 226 property map is distributed and is also the medium for 227 communication. 228 229 230**LocalPropertyMap**: 231 The type of the property map that will store values 232 for keys local to this processor. The ``value_type`` of this 233 property map will become the ``value_type`` of the distributed 234 property map. The distributed property map models the same property 235 map concepts as the ``LocalPropertyMap``, with one exception: a 236 distributed property map cannot be an `Lvalue Property Map`_ 237 (because remote values are not addressable), and is therefore 238 limited to `Read/Write Property Map`_. 239 240 241**Key**: 242 The ``key_type`` of the distributed property map, which 243 must model the `Global Descriptor`_ concept. The process ID type of 244 the ``Key`` parameter must match the process ID type of the 245 ``ProcessGroup``, and the local descriptor type of the ``Key`` must 246 be convertible to the ``key_type`` of the ``LocalPropertyMap``. 247 248 249**GhostCellS**: 250 A selector type that indicates how ghost cells should be stored in 251 the distributed property map. There are either two or three 252 options, depending on your compiler: 253 254 - ``boost::parallel::gc_mapS`` (default): Uses an STL ``map`` to 255 store the ghost cells for each process. 256 257 - ``boost::parallel::gc_vector_mapS``: Uses a sorted STL 258 ``vector`` to store the ghost cells for each process. This 259 option works well when there are likely to be few insertions 260 into the ghost cells; for instance, if the only ghost cells used 261 are for neighboring vertices, the property map can be 262 initialized with cells for each neighboring vertex, providing 263 faster lookups than a ``map`` and using less space. 264 265 - ``boost::parallel::gc_hash_mapS``: Uses the GCC ``hash_map`` to 266 store ghost cells. This option may improve performance over 267 ``map`` for large problems sizes, where the set of ghost cells 268 cannot be predetermined. 269 270 271Member functions 272~~~~~~~~~~~~~~~~ 273 274:: 275 276 distributed_property_map(); 277 278Default-construct a distributed property map. The property map is in 279an invalid state, and may only be used if it is reassigned to a valid 280property map. 281 282------------------------------------------------------------------------------ 283 284:: 285 286 distributed_property_map(const ProcessGroup& pg, 287 const LocalPropertyMap& pm); 288 289 template<typename Reduce> 290 distributed_property_map(const ProcessGroup& pg, 291 const LocalPropertyMap& pm, 292 const Reduce& reduce); 293 294Construct a property map from a process group and a local property 295map. If a ``reduce`` operation is not supplied, a default of 296``basic_reduce<value_type>`` will be used. 297 298------------------------------------------------------------------------------ 299 300:: 301 302 template<typename Reduce> void set_reduce(const Reduce& reduce); 303 304Replace the current reduction operation with the new operation 305``reduce``. 306 307------------------------------------------------------------------------------ 308 309:: 310 311 void set_consistency_model(int model); 312 313Sets the consistency model of the distributed property map, which will 314take effect on the next synchronization step. See the section 315`Consistency models`_ for a description of the effect of various 316consistency model flags. 317 318------------------------------------------------------------------------------ 319 320:: 321 322 void flush(); 323 324Emits a message sending the contents of all local ghost cells to the 325owners of those cells. 326 327------------------------------------------------------------------------------ 328 329:: 330 331 void reset(); 332 333Replaces the values stored in each of the ghost cells with the default 334value generated by the reduction operation. 335 336------------------------------------------------------------------------------ 337 338:: 339 340 void clear(); 341 342Removes all ghost cells from the property map. 343 344 345Free functions 346~~~~~~~~~~~~~~ 347 348:: 349 350 reference get(distributed_property_map pm, const key_type& key); 351 352Retrieves the element in ``pm`` associated with the given ``key``. If 353the key refers to data stored locally, returns the actual value 354associated with the key. If the key refers to nonlocal data, returns 355the value of the ghost cell. If no ghost cell exists, the behavior 356depends on the current reduction operation: if a reduction operation 357has been set and has ``non_default_resolver`` set ``true``, then a 358ghost cell will be created according to the default value provided by 359the reduction operation. Otherwise, the call to ``get`` will abort 360because no value exists for this remote cell. To avoid this problem, 361either set a reduction operation that generates default values, 362``request()`` the value and then perform a synchronization step, or 363``put`` a value into the cell before reading it. 364 365------------------------------------------------------------------------------ 366 367:: 368 369 void 370 put(distributed_property_map pm, const key_type& key, const value_type& value); 371 372Places the given ``value`` associated with ``key`` into property map 373``pm``. If the key refers to data stored locally, the value is 374immediately updates. If the key refers to data stored in a remote 375process, updates (or creates) a local ghost cell containing this 376value for the key and sends the new value to the owning process. Note 377that the owning process may reject this value based on the reduction 378operation, but this will not be detected until the next 379synchronization step. 380 381------------------------------------------------------------------------------ 382 383:: 384 385 void 386 local_put(distributed_property_map pm, const key_type& key, const value_type& value); 387 388Equivalent to ``put(pm, key, value)``, except that no message is sent 389to the owning process when the value is changed for a nonlocal key. 390 391------------------------------------------------------------------------------ 392 393:: 394 395 void synchronize(distributed_property_map& pm); 396 397Synchronize the values stored in the distributed property maps. Each 398process much execute ``synchronize`` at the same time, after which 399the ghost cells in every process will reflect the actual value stored 400in the owning process. 401 402------------------------------------------------------------------------------ 403 404:: 405 406 void request(distributed_property_map pm, const key_type& key); 407 408Request that the element "key" be available after the next 409synchronization step. For a non-local key, this means establishing a 410ghost cell and requesting. 411 412------------------------------------------------------------------------------ 413 414:: 415 416 template<typename Key, typename ProcessGroup, typename LocalPropertyMap> 417 distributed_property_map<ProcessGroup, LocalPropertyMap, Key> 418 make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap); 419 420 template<typename Key, typename ProcessGroup, typename LocalPropertyMap, 421 typename Reduce> 422 distributed_property_map<ProcessGroup, LocalPropertyMap, Key> 423 make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap, 424 Reduce reduce); 425 426Create a distributed property map over process group ``pg`` and local 427property map ``pmap``. A default reduction operation will be generated 428if it is not provided. 429 430--------------------------------- 431Distributed iterator property map 432--------------------------------- 433 434The distributed iterator property map adaptor permits the creation of 435distributed property maps from random access iterators using the same 436syntax as non-distributed iterator property maps. The specialization 437is based on a `local property map`_, which contains the 438indices for local descriptors and is typically returned to describe 439the vertex indices of a distributed graph. 440 441Synopsis 442~~~~~~~~ 443 444:: 445 446 template<typename RandomAccessIterator, typename ProcessGroup, 447 typename GlobalKey, typename LocalMap, typename ValueType, 448 typename Reference> 449 class iterator_property_map<RandomAccessIterator, 450 local_property_map<ProcessGroup, GlobalKey, LocalMap>, 451 ValueType, Reference> 452 { 453 public: 454 typedef local_property_map<ProcessGroup, GlobalKey, LocalMap> index_map_type; 455 456 iterator_property_map(); 457 iterator_property_map(RandomAccessIterator iter, const index_map_type& id); 458 }; 459 460 reference get(iterator_property_map pm, const key_type& key); 461 void put(iterator_property_map pm, const key_type& key, const value_type& value); 462 463 template<typename RandomAccessIterator, typename ProcessGroup, 464 typename GlobalKey, typename LocalMap> 465 iterator_property_map<RandomAccessIterator, 466 local_property_map<ProcessGroup, GlobalKey, LocalMap> > 467 make_iterator_property_map(RandomAccessIterator iter, 468 local_property_map<ProcessGroup, GlobalKey, LocalMap> id); 469 470 471Member functions 472~~~~~~~~~~~~~~~~ 473 474:: 475 476 iterator_property_map(); 477 478Default-constructs a distributed iterator property map. The property 479map is in an invalid state, and must be reassigned before it may be 480used. 481 482------------------------------------------------------------------------------ 483 484:: 485 486 iterator_property_map(RandomAccessIterator iter, const index_map_type& id); 487 488Constructs a distributed iterator property map using the property map 489``id`` to map global descriptors to local indices. The random access 490iterator sequence ``[iter, iter + n)`` must be a valid range, where 491``[0, n)`` is the range of local indices. 492 493Free functions 494~~~~~~~~~~~~~~ 495 496:: 497 498 reference get(iterator_property_map pm, const key_type& key); 499 500Returns the value associated with the given ``key`` from the 501distributed property map. 502 503------------------------------------------------------------------------------ 504 505:: 506 507 void put(iterator_property_map pm, const key_type& key, const value_type& value); 508 509Associates the value with the given key in the distributed property map. 510 511------------------------------------------------------------------------------ 512 513:: 514 515 template<typename RandomAccessIterator, typename ProcessGroup, 516 typename GlobalKey, typename LocalMap, typename ValueType, 517 typename Reference> 518 iterator_property_map<RandomAccessIterator, 519 local_property_map<ProcessGroup, GlobalKey, LocalMap>, 520 ValueType, Reference> 521 make_iterator_property_map(RandomAccessIterator iter, 522 local_property_map<ProcessGroup, GlobalKey, LocalMap>, 523 ValueType, Reference> id); 524 525Creates a distributed iterator property map using the given iterator 526``iter`` and local index property map ``id``. 527 528-------------------------------------- 529Distributed safe iterator property map 530-------------------------------------- 531 532The distributed safe iterator property map adaptor permits the 533creation of distributed property maps from random access iterators 534using the same syntax as non-distributed safe iterator property 535maps. The specialization is based on a `local property map`_, which 536contains the indices for local descriptors and is typically returned 537to describe the vertex indices of a distributed graph. Safe iterator 538property maps check the indices of accesses to ensure that they are 539not out-of-bounds before attempting to access an value. 540 541Synopsis 542~~~~~~~~ 543 544:: 545 546 template<typename RandomAccessIterator, typename ProcessGroup, 547 typename GlobalKey, typename LocalMap, typename ValueType, 548 typename Reference> 549 class safe_iterator_property_map<RandomAccessIterator, 550 local_property_map<ProcessGroup, GlobalKey, LocalMap>, 551 ValueType, Reference> 552 { 553 public: 554 typedef local_property_map<ProcessGroup, GlobalKey, LocalMap> index_map_type; 555 556 safe_iterator_property_map(); 557 safe_iterator_property_map(RandomAccessIterator iter, std::size_t n, 558 const index_map_type& id); 559 }; 560 561 reference get(safe_iterator_property_map pm, const key_type& key); 562 void put(safe_iterator_property_map pm, const key_type& key, const value_type& value); 563 564 template<typename RandomAccessIterator, typename ProcessGroup, 565 typename GlobalKey, typename LocalMap, typename ValueType, 566 typename Reference> 567 safe_iterator_property_map<RandomAccessIterator, 568 local_property_map<ProcessGroup, GlobalKey, LocalMap>, 569 ValueType, Reference> 570 make_safe_iterator_property_map(RandomAccessIterator iter, 571 std::size_t n, 572 local_property_map<ProcessGroup, GlobalKey, LocalMap>, 573 ValueType, Reference> id); 574 575Member functions 576~~~~~~~~~~~~~~~~ 577 578:: 579 580 safe_iterator_property_map(); 581 582Default-constructs a distributed safe iterator property map. The property 583map is in an invalid state, and must be reassigned before it may be 584used. 585 586------------------------------------------------------------------------------ 587 588:: 589 590 safe_iterator_property_map(RandomAccessIterator iter, std::size_t n, 591 const index_map_type& id); 592 593Constructs a distributed safe iterator property map using the property map 594``id`` to map global descriptors to local indices. The random access 595iterator sequence ``[iter, iter + n)``. 596 597Free functions 598~~~~~~~~~~~~~~ 599 600:: 601 602 reference get(safe_iterator_property_map pm, const key_type& key); 603 604Returns the value associated with the given ``key`` from the 605distributed property map. 606 607------------------------------------------------------------------------------ 608 609:: 610 611 void put(safe_iterator_property_map pm, const key_type& key, const value_type& value); 612 613Associates the value with the given key in the distributed property map. 614 615------------------------------------------------------------------------------ 616 617:: 618 619 template<typename RandomAccessIterator, typename ProcessGroup, 620 typename GlobalKey, typename LocalMap, typename ValueType, 621 typename Reference> 622 safe_iterator_property_map<RandomAccessIterator, 623 local_property_map<ProcessGroup, GlobalKey, LocalMap>, 624 ValueType, Reference> 625 make_safe_iterator_property_map(RandomAccessIterator iter, 626 std::size_t n, 627 local_property_map<ProcessGroup, GlobalKey, LocalMap>, 628 ValueType, Reference> id); 629 630Creates a distributed safe iterator property map using the given iterator 631``iter`` and local index property map ``id``. The indices in ``id`` must 632 633------------------ 634Local property map 635------------------ 636 637A property map adaptor that accesses an underlying property map whose 638key type is the local part of the ``Key`` type for the local subset 639of keys. Local property maps are typically used by distributed graph 640types for vertex index properties. 641 642Synopsis 643~~~~~~~~ 644 645:: 646 647 template<typename ProcessGroup, typename GlobalKey, typename LocalMap> 648 class local_property_map 649 { 650 public: 651 typedef typename property_traits<LocalMap>::value_type value_type; 652 typedef GlobalKey key_type; 653 typedef typename property_traits<LocalMap>::reference reference; 654 typedef typename property_traits<LocalMap>::category category; 655 656 explicit 657 local_property_map(const ProcessGroup& process_group = ProcessGroup(), 658 const LocalMap& local_map = LocalMap()); 659 660 reference operator[](const key_type& key); 661 }; 662 663 reference get(const local_property_map& pm, key_type key); 664 void put(local_property_map pm, const key_type& key, const value_type& value); 665 666Template parameters 667~~~~~~~~~~~~~~~~~~~ 668 669:ProcessGroup: the type of the process group over which the global 670 keys are distributed. 671 672:GlobalKey: The ``key_type`` of the local property map, which 673 must model the `Global Descriptor`_ concept. The process ID type of 674 the ``GlobalKey`` parameter must match the process ID type of the 675 ``ProcessGroup``, and the local descriptor type of the ``GlobalKey`` 676 must be convertible to the ``key_type`` of the ``LocalMap``. 677 678:LocalMap: the type of the property map that will store values 679 for keys local to this processor. The ``value_type`` of this 680 property map will become the ``value_type`` of the local 681 property map. The local property map models the same property 682 map concepts as the ``LocalMap``. 683 684Member functions 685~~~~~~~~~~~~~~~~ 686 687:: 688 689 explicit 690 local_property_map(const ProcessGroup& process_group = ProcessGroup(), 691 const LocalMap& local_map = LocalMap()); 692 693Constructs a local property map whose keys are distributed across the 694given process group and which accesses the given local map. 695 696------------------------------------------------------------------------------ 697 698:: 699 700 reference operator[](const key_type& key); 701 702Access the value associated with the given key, which must be local 703to this process. 704 705Free functions 706~~~~~~~~~~~~~~ 707 708:: 709 710 reference get(const local_property_map& pm, key_type key); 711 712Return the value associated with the given key, which must be local 713to this process. 714 715------------------------------------------------------------------------------ 716 717:: 718 719 void put(local_property_map pm, const key_type& key, const value_type& value); 720 721Set the value associated with the given key, which must be local to 722this process. 723 724----------------------------------------------------------------------------- 725 726Copyright (C) 2004, 2005 The Trustees of Indiana University. 727 728Authors: Douglas Gregor and Andrew Lumsdaine 729 730.. |Logo| image:: pbgl-logo.png 731 :align: middle 732 :alt: Parallel BGL 733 :target: http://www.osl.iu.edu/research/pbgl 734 735.. _Readable Property Map: http://www.boost.org/libs/property_map/ReadablePropertyMap.html 736.. _Writable Property Map: http://www.boost.org/libs/property_map/WritablePropertyMap.html 737.. _Read/Write Property Map: http://www.boost.org/libs/property_map/ReadWritePropertyMap.html 738.. _Lvalue Property Map: http://www.boost.org/libs/property_map/LvaluePropertyMap.html 739.. _Process Group: process_group.html 740.. _Global Descriptor: GlobalDescriptor.html 741.. _Dijkstra's shortest paths: dijkstra_shortest_paths.html 742.. _Breadth-First Search: breadth_first_search.html 743.. _PageRank: page_rank.html 744 745
