A distributed property map adaptor is a property map whose stored values are distributed across multiple non-overlapping memory spaces on different processes. Values local to the current process are stored within a local property map and may be immediately accessed via get and put. Values stored on remote processes may also be accessed via get and put, but the behavior differs slightly:
- put operations update a local ghost cell and send a "put" message to the process that owns the value. The owner is free to update its own "official" value or may ignore the put request.
- get operations returns the contents of the local ghost cell. If no ghost cell is available, one is created using a (customizable) default value.
Using distributed property maps requires a bit more care than using local, sequential property maps. While the syntax and semantics are similar, distributed property maps may contain out-of-date information that can only be guaranteed to be synchronized by calling the synchronize function in all processes.
To address the issue of out-of-date values, distributed property maps are supplied with a reduction operation. The reduction operation has two roles:
- When a value is needed for a remote key but no value is immediately available, the reduction operation provides a suitable default. For instance, a distributed property map storing distances may have a reduction operation that returns an infinite value as the default, whereas a distributed property map for vertex colors may return white as the default.
- When a value is received from a remote process, the process owning the key associated with that value must determine which value---the locally stored value, the value received from a remote process, or some combination of the two---will be stored as the "official" value in the property map. The reduction operation transforms the local and remote values into the "official" value to be stored.
Distributed property maps meet the requirements of the Readable Property Map and, potentially, the Writable Property Map and Read/Write Property Map concepts. Distributed property maps do not, however, meet the requirements of the Lvalue Property Map concept, because elements residing in another process are not directly addressible. There are several forms of distributed property maps:
The distributed property map adaptor creates a distributed property map from a local property map, a process group over which distribution should occur, and a global descriptor type that indexes the distributed property map.
template<
typename ProcessGroup, typename LocalPropertyMap, typename Key,
typename GhostCells =
std::vector<
std::map<typename property_traits<LocalPropertyMap>::key_type,
typename property_traits<LocalPropertyMap>::value_type> >
>
class distributed_property_map
{
public:
distributed_property_map();
distributed_property_map(const ProcessGroup& pg,
const LocalPropertyMap& pm);
template<typename Reduce>
distributed_property_map(const ProcessGroup& pg,
const LocalPropertyMap& pm,
const Reduce& reduce,
const shared_ptr<GhostCells>& ghost_cells =
shared_ptr<GhostCells>());
template<typename Reduce> void set_reduce(const Reduce& reduce);
};
reference get(distributed_property_map pm, const key_type& key);
void
put(distributed_property_map pm, const key_type& key, const value_type& value);
local_put(distributed_property_map pm, const key_type& key, const value_type& value);
void synchronize(distributed_property_map& pm);
template<typename Key, typename ProcessGroup, typename LocalPropertyMap>
distributed_property_map<ProcessGroup, LocalPropertyMap, Key>
make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap);
template<typename Key, typename ProcessGroup, typename LocalPropertyMap,
typename Reduce>
distributed_property_map<ProcessGroup, LocalPropertyMap, Key>
make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap,
Reduce reduce);
template<typename Key, typename ProcessGroup, typename LocalPropertyMap,
typename Reduce, typename GhostCells>
distributed_property_map<ProcessGroup, LocalPropertyMap, Key, GhostCells>
make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap,
Reduce reduce,
boost::shared_ptr<GhostCells> ghost_cells);
distributed_property_map();
Default-construct a distributed property map. The property map is in an invalid state, and may only be used if it is reassigned to a valid property map.
distributed_property_map(const ProcessGroup& pg,
const LocalPropertyMap& pm);
template<typename Reduce>
distributed_property_map(const ProcessGroup& pg,
const LocalPropertyMap& pm,
const Reduce& reduce,
const shared_ptr<GhostCells>& ghost_cells =
shared_ptr<GhostCells>());
Construct a property map from a process group and a local property map. If a reduce operation is not supplied, a default of basic_reduce<value_type> will be used. If no predefined set of ghost_cells are supplied, a new set of ghost cells will be created.
template<typename Reduce> void set_reduce(const Reduce& reduce);
Replace the current reduction operation with the new operation reduce.
reference get(distributed_property_map pm, const key_type& key);
Retrieves the element in pm associated with the given key. If the key refers to data stored locally, returns the actual value associated with the key. If the key refers to nonlocal data, returns the value of the ghost cell, which will be created by the reduction value if no ghost cell exists and which may be out-of-date with respect to the value in the owning process.
void put(distributed_property_map pm, const key_type& key, const value_type& value);
Places the given value associated with key into property map pm. If the key refers to data stored locally, the value is immediately updates. If the key refers to data stored in a remote process, updates (or creates) a local ghost cell containing this value for the key and sends the new value to the owning process. Note that the owning process may reject this value based on the reduction operation, but this will not be detected until the next synchronization step.
void local_put(distributed_property_map pm, const key_type& key, const value_type& value);
Equivalent to put(pm, key, value), except that no message is sent to the owning process when the value is changed for a nonlocal key.
void synchronize(distributed_property_map& pm);
Synchronize the values stored in the distributed property maps. Each process much execute synchronize at the same time, after which the ghost cells in every process will reflect the actual value stored in the owning process.
template<typename Key, typename ProcessGroup, typename LocalPropertyMap>
distributed_property_map<ProcessGroup, LocalPropertyMap, Key>
make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap);
template<typename Key, typename ProcessGroup, typename LocalPropertyMap,
typename Reduce>
distributed_property_map<ProcessGroup, LocalPropertyMap, Key>
make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap,
Reduce reduce);
template<typename Key, typename ProcessGroup, typename LocalPropertyMap,
typename Reduce, typename GhostCells>
distributed_property_map<ProcessGroup, LocalPropertyMap, Key, GhostCells>
make_distributed_property_map(const ProcessGroup& pg, LocalPropertyMap pmap,
Reduce reduce,
boost::shared_ptr<GhostCells> ghost_cells);
Create a distributed property map over process group pg and local property map pmap. Default reduction operations and ghost cells will be generated if not provided.
The distributed iterator property map adaptor permits the creation of distributed property maps from random access iterators using the same syntax as non-distributed iterator property maps. The specialization is based on a local property map, which contains the indices for local descriptors and is typically returned to describe the vertex indices of a distributed graph.
template<typename RandomAccessIterator, typename ProcessGroup,
typename GlobalKey, typename LocalMap, typename ValueType,
typename Reference>
class iterator_property_map<RandomAccessIterator,
local_property_map<ProcessGroup, GlobalKey, LocalMap>,
ValueType, Reference>
{
public:
typedef local_property_map<ProcessGroup, GlobalKey, LocalMap> index_map_type;
iterator_property_map();
iterator_property_map(RandomAccessIterator iter, const index_map_type& id);
};
reference get(iterator_property_map pm, const key_type& key);
void put(iterator_property_map pm, const key_type& key, const value_type& value);
template<typename RandomAccessIterator, typename ProcessGroup,
typename GlobalKey, typename LocalMap>
iterator_property_map<RandomAccessIterator,
local_property_map<ProcessGroup, GlobalKey, LocalMap> >
make_iterator_property_map(RandomAccessIterator iter,
local_property_map<ProcessGroup, GlobalKey, LocalMap> id);
iterator_property_map();
Default-constructs a distributed iterator property map. The property map is in an invalid state, and must be reassigned before it may be used.
iterator_property_map(RandomAccessIterator iter, const index_map_type& id);
Constructs a distributed iterator property map using the property map id to map global descriptors to local indices. The random access iterator sequence [iter, iter + n) must be a valid range, where [0, n) is the range of local indices.
reference get(iterator_property_map pm, const key_type& key);
Returns the value associated with the given key from the distributed property map.
void put(iterator_property_map pm, const key_type& key, const value_type& value);
Associates the value with the given key in the distributed property map.
template<typename RandomAccessIterator, typename ProcessGroup,
typename GlobalKey, typename LocalMap, typename ValueType,
typename Reference>
iterator_property_map<RandomAccessIterator,
local_property_map<ProcessGroup, GlobalKey, LocalMap>,
ValueType, Reference>
make_iterator_property_map(RandomAccessIterator iter,
local_property_map<ProcessGroup, GlobalKey, LocalMap>,
ValueType, Reference> id);
Creates a distributed iterator property map using the given iterator iter and local index property map id.
The distributed safe iterator property map adaptor permits the creation of distributed property maps from random access iterators using the same syntax as non-distributed safe iterator property maps. The specialization is based on a local property map, which contains the indices for local descriptors and is typically returned to describe the vertex indices of a distributed graph. Safe iterator property maps check the indices of accesses to ensure that they are not out-of-bounds before attempting to access an value.
template<typename RandomAccessIterator, typename ProcessGroup,
typename GlobalKey, typename LocalMap, typename ValueType,
typename Reference>
class safe_iterator_property_map<RandomAccessIterator,
local_property_map<ProcessGroup, GlobalKey, LocalMap>,
ValueType, Reference>
{
public:
typedef local_property_map<ProcessGroup, GlobalKey, LocalMap> index_map_type;
safe_iterator_property_map();
safe_iterator_property_map(RandomAccessIterator iter, std::size_t n,
const index_map_type& id);
};
reference get(safe_iterator_property_map pm, const key_type& key);
void put(safe_iterator_property_map pm, const key_type& key, const value_type& value);
template<typename RandomAccessIterator, typename ProcessGroup,
typename GlobalKey, typename LocalMap, typename ValueType,
typename Reference>
safe_iterator_property_map<RandomAccessIterator,
local_property_map<ProcessGroup, GlobalKey, LocalMap>,
ValueType, Reference>
make_safe_iterator_property_map(RandomAccessIterator iter,
std::size_t n,
local_property_map<ProcessGroup, GlobalKey, LocalMap>,
ValueType, Reference> id);
safe_iterator_property_map();
Default-constructs a distributed safe iterator property map. The property map is in an invalid state, and must be reassigned before it may be used.
safe_iterator_property_map(RandomAccessIterator iter, std::size_t n,
const index_map_type& id);
Constructs a distributed safe iterator property map using the property map id to map global descriptors to local indices. The random access iterator sequence [iter, iter + n).
reference get(safe_iterator_property_map pm, const key_type& key);
Returns the value associated with the given key from the distributed property map.
void put(safe_iterator_property_map pm, const key_type& key, const value_type& value);
Associates the value with the given key in the distributed property map.
template<typename RandomAccessIterator, typename ProcessGroup,
typename GlobalKey, typename LocalMap, typename ValueType,
typename Reference>
safe_iterator_property_map<RandomAccessIterator,
local_property_map<ProcessGroup, GlobalKey, LocalMap>,
ValueType, Reference>
make_safe_iterator_property_map(RandomAccessIterator iter,
std::size_t n,
local_property_map<ProcessGroup, GlobalKey, LocalMap>,
ValueType, Reference> id);
Creates a distributed safe iterator property map using the given iterator iter and local index property map id. The indices in id must
A property map adaptor that accesses an underlying property map whose key type is the local part of the Key type for the local subset of keys. Local property maps are typically used by distributed graph types for vertex index properties.
template<typename ProcessGroup, typename GlobalKey, typename LocalMap>
class local_property_map
{
public:
typedef typename property_traits<LocalMap>::value_type value_type;
typedef GlobalKey key_type;
typedef typename property_traits<LocalMap>::reference reference;
typedef typename property_traits<LocalMap>::category category;
explicit
local_property_map(const ProcessGroup& process_group = ProcessGroup(),
const LocalMap& local_map = LocalMap());
reference operator[](const key_type& key);
};
reference get(const local_property_map& pm, key_type key);
void put(local_property_map pm, const key_type& key, const value_type& value);
| ProcessGroup: | the type of the process group over which the global keys are distributed. |
|---|---|
| GlobalKey: | The key_type of the local property map, which must model the Global Descriptor concept. The process ID type of the GlobalKey parameter must match the process ID type of the ProcessGroup, and the local descriptor type of the GlobalKey must be convertible to the key_type of the LocalMap. |
| LocalMap: | the type of the property map that will store values for keys local to this processor. The value_type of this property map will become the value_type of the local property map. The local property map models the same property map concepts as the LocalMap. |
explicit
local_property_map(const ProcessGroup& process_group = ProcessGroup(),
const LocalMap& local_map = LocalMap());
Constructs a local property map whose keys are distributed across the given process group and which accesses the given local map.
reference operator[](const key_type& key);
Access the value associated with the given key, which must be local to this process.
reference get(const local_property_map& pm, key_type key);
Return the value associated with the given key, which must be local to this process.
void put(local_property_map pm, const key_type& key, const value_type& value);
Set the value associated with the given key, which must be local to this process.
Copyright (C) 2004, 2005 The Trustees of Indiana University.
Authors: Douglas Gregor and Andrew Lumsdaine