FM / parallel

/usr/include/boost/property_map/parallel/

/usr/include/boost/property_map/parallel

Name	Size	Mode	Actions
detail/	-	0755	rm
impl/	-	0755	rm
basic_reduce.hpp	1206	0644	edit dl rm
caching_property_map.hpp	2955	0644	edit dl rm
distributed_property_map.hpp	24246	0644	edit dl rm
global_index_map.hpp	2231	0644	edit dl rm
local_property_map.hpp	3299	0644	edit dl rm
parallel_property_maps.hpp	8866	0644	edit dl rm
process_group.hpp	3555	0644	edit dl rm
simple_trigger.hpp	3527	0644	edit dl rm
unsafe_serialize.hpp	2675	0644	edit dl rm
vector_property_map.hpp	3871	0644	edit dl rm

Edit: /usr/include/boost/property_map/parallel/distributed_property_map.hpp (24246B)

// Use, modification and distribution is subject to the Boost Software
// License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)

//  Authors: Douglas Gregor
//           Nick Edmonds
//           Andrew Lumsdaine

// The placement of this #include probably looks very odd relative to
// the #ifndef/#define pair below. However, this placement is
// extremely important to allow the various property map headers to be
// included in any order.
#include <boost/property_map/property_map.hpp>

#ifndef BOOST_PARALLEL_DISTRIBUTED_PROPERTY_MAP_HPP
#define BOOST_PARALLEL_DISTRIBUTED_PROPERTY_MAP_HPP

#include <boost/assert.hpp>
#include <boost/type_traits/is_base_and_derived.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/weak_ptr.hpp>
#include <boost/optional.hpp>
#include <boost/property_map/parallel/process_group.hpp>
#include <boost/function/function1.hpp>
#include <vector>
#include <set>
#include <boost/property_map/parallel/basic_reduce.hpp>
#include <boost/property_map/parallel/detail/untracked_pair.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/property_map/parallel/local_property_map.hpp>
#include <map>
#include <boost/version.hpp>
#include <boost/property_map/parallel/unsafe_serialize.hpp>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/sequenced_index.hpp>

// Serialization functions for constructs we use
#include <boost/serialization/utility.hpp>

namespace boost { namespace parallel {

namespace detail {
  /**************************************************************************
   * Metafunction that degrades an Lvalue Property Map category tag to
   * a Read Write Property Map category tag.
   **************************************************************************/
  template<bool IsLvaluePropertyMap>
  struct make_nonlvalue_property_map
  {
    template<typename T> struct apply { typedef T type; };
  };

template<>
  struct make_nonlvalue_property_map<true>
  {
    template<typename>
    struct apply
    {
      typedef read_write_property_map_tag type;
    };
  };

/**************************************************************************
   * Performs a "put" on a property map so long as the property map is
   * a Writable Property Map or a mutable Lvalue Property Map. This
   * is required because the distributed property map's message
   * handler handles "put" messages even for a const property map,
   * although receipt of a "put" message is ill-formed.
   **************************************************************************/
  template<bool IsLvaluePropertyMap>
  struct maybe_put_in_lvalue_pm
  {
    template<typename PropertyMap, typename Key, typename Value>
    static inline void
    do_put(PropertyMap, const Key&, const Value&)
    { BOOST_ASSERT(false); }
  };

template<>
  struct maybe_put_in_lvalue_pm<true>
  {
    template<typename PropertyMap, typename Key, typename Value>
    static inline void
    do_put(PropertyMap pm, const Key& key, const Value& value)
    {
      using boost::put;

put(pm, key, value);
    }
  };

template<typename PropertyMap, typename Key, typename Value>
  inline void
  maybe_put_impl(PropertyMap pm, const Key& key, const Value& value,
                 writable_property_map_tag)
  {
    using boost::put;

put(pm, key, value);
  }

template<typename PropertyMap, typename Key, typename Value>
  inline void
  maybe_put_impl(PropertyMap pm, const Key& key, const Value& value,
                 lvalue_property_map_tag)
  {
    typedef typename property_traits<PropertyMap>::value_type value_type;
    typedef typename property_traits<PropertyMap>::reference reference;
    // DPG TBD: Some property maps are improperly characterized as
    // lvalue_property_maps, when in fact they do not provide true
    // references. The most typical example is those property maps
    // built from vector<bool> and its iterators, which deal with
    // proxies. We don't want to mischaracterize these as not having a
    // "put" operation, so we only consider an lvalue_property_map as
    // constant if its reference is const value_type&. In fact, this
    // isn't even quite correct (think of a
    // vector<bool>::const_iterator), but at present C++ doesn't
    // provide us with any alternatives.
    typedef is_same<const value_type&, reference> is_constant;

maybe_put_in_lvalue_pm<(!is_constant::value)>::do_put(pm, key, value);
  }

template<typename PropertyMap, typename Key, typename Value>
  inline void
  maybe_put_impl(PropertyMap, const Key&, const Value&, ...)
  { BOOST_ASSERT(false); }

template<typename PropertyMap, typename Key, typename Value>
  inline void
  maybe_put(PropertyMap pm, const Key& key, const Value& value)
  {
    maybe_put_impl(pm, key, value,
                   typename property_traits<PropertyMap>::category());
  }
} // end namespace detail

/** The consistency model used by the distributed property map. */
enum consistency_model {
  cm_forward = 1 << 0,
  cm_backward = 1 << 1,
  cm_bidirectional = cm_forward | cm_backward,
  cm_flush = 1 << 2,
  cm_reset = 1 << 3,
  cm_clear = 1 << 4
};

/** Distributed property map adaptor.
 *
 *  The 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 @c get and @c put. Values stored on
 *  remote processes may also be access via @c get and @c put, but the
 *  behavior differs slightly:
 *
 *  - @c 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.
 *
 *  - @c get operations returns the contents of the local ghost
 *    cell. If no ghost cell is available, one is created using the
 *    default value provided by the "reduce" operation. See, e.g.,
 *    @ref basic_reduce and @ref property_reduce.
 *
 * 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 @ref 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.
 *
 * @tparam ProcessGroup the type of the process group over which the
 * property map is distributed and is also the medium for
 * communication.
 *
 * @tparam StorageMap the type of the property map that will
 * store values for keys local to this processor. The @c value_type of
 * this property map will become the @c value_type of the distributed
 * property map. The distributed property map models the same property
 * map concepts as the @c LocalPropertyMap, with one exception: a
 * distributed property map cannot be an LvaluePropertyMap (because
 * remote values are not addressable), and is therefore limited to
 * ReadWritePropertyMap.
 */
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
class distributed_property_map
{
 public:
  /// The key type of the property map.
  typedef typename property_traits<GlobalMap>::key_type key_type;

/// The value type of the property map.
  typedef typename property_traits<StorageMap>::value_type value_type;
  typedef typename property_traits<StorageMap>::reference  reference;
  typedef ProcessGroup                        process_group_type;

private:
  typedef distributed_property_map            self_type;
  typedef typename property_traits<StorageMap>::category local_category;
  typedef typename property_traits<StorageMap>::key_type local_key_type;
  typedef typename property_traits<GlobalMap>::value_type owner_local_pair;
  typedef typename ProcessGroup::process_id_type process_id_type;

enum property_map_messages {
    /** A request to store a value in a property map. The message
     * contains a std::pair<key, data>.
     */
    property_map_put,

/** A request to retrieve a particular value in a property
     *  map. The message contains a key. The owner of that key will
     *  reply with a value.
     */
    property_map_get,

/** A request to update values stored on a remote processor. The
     * message contains a vector of keys for which the source
     * requests updated values. This message will only be transmitted
     * during synchronization.
     */
    property_map_multiget,

/** A request to store values in a ghost cell. This message
     * contains a vector of key/value pairs corresponding to the
     * sequence of keys sent to the source processor.
     */
    property_map_multiget_reply,

/** The payload containing a vector of local key-value pairs to be
     * put into the remote property map. A key-value std::pair will be
     * used to store each local key-value pair.
     */
    property_map_multiput
  };

// Code from Joaquín M López Muñoz to work around unusual implementation of
  // std::pair in VC++ 10:
  template<typename First,typename Second>
  class pair_first_extractor {
    typedef std::pair<First,Second> value_type;

public:
    typedef First result_type;
    const result_type& operator()(const value_type& x) const {
      return x.first;
    }

result_type& operator()(value_type& x) const {
      return x.first;
    }
  };

public:
  /// The type of the ghost cells
  typedef multi_index::multi_index_container<
            std::pair<key_type, value_type>,
            multi_index::indexed_by<
              multi_index::sequenced<>,
              multi_index::hashed_unique<
                pair_first_extractor<key_type, value_type>
              >
            >
          > ghost_cells_type;

/// Iterator into the ghost cells
  typedef typename ghost_cells_type::iterator iterator;

/// Key-based index into the ghost cells
  typedef typename ghost_cells_type::template nth_index<1>::type
    ghost_cells_key_index_type;

/// Iterator into the ghost cells (by key)
  typedef typename ghost_cells_key_index_type::iterator key_iterator;

/** The property map category.  A distributed property map cannot be
   * an Lvalue Property Map, because values on remote processes cannot
   * be addresses.
   */
  typedef typename detail::make_nonlvalue_property_map<
    (is_base_and_derived<lvalue_property_map_tag, local_category>::value
     || is_same<lvalue_property_map_tag, local_category>::value)>
    ::template apply<local_category>::type category;

/** Default-construct a distributed property map.  This function
   * creates an initialized property map that must be assigned to a
   * valid value before being used. It is only provided here because
   * property maps must be Default Constructible.
   */
  distributed_property_map() {}

/** Construct a distributed property map.  Builds a distributed
   * property map communicating over the given process group and using
   * the given local property map for storage. Since no reduction
   * operation is provided, the default reduction operation @c
   * basic_reduce<value_type> is used.
   */
  distributed_property_map(const ProcessGroup& pg, const GlobalMap& global,
                           const StorageMap& pm)
    : data(new data_t(pg, global, pm, basic_reduce<value_type>(), false))
  {
    typedef handle_message<basic_reduce<value_type> > Handler;

data->ghost_cells.reset(new ghost_cells_type());
    Handler handler(data);
    data->process_group.replace_handler(handler, true);
    data->process_group.template get_receiver<Handler>()
      ->setup_triggers(data->process_group);
  }

/** Construct a distributed property map.  Builds a distributed
   * property map communicating over the given process group and using
   * the given local property map for storage. The given @p reduce
   * parameter is used as the reduction operation.
   */
  template<typename Reduce>
  distributed_property_map(const ProcessGroup& pg, const GlobalMap& global,
                           const StorageMap& pm,
                           const Reduce& reduce);

~distributed_property_map();

/// Set the reduce operation of the distributed property map.
  template<typename Reduce>
  void set_reduce(const Reduce& reduce);

// Set the consistency model for the distributed property map
  void set_consistency_model(int model);

// Get the consistency model
  int get_consistency_model() const { return data->model; }

// Set the maximum number of ghost cells that we are allowed to
  // maintain. If 0, all ghost cells will be retained.
  void set_max_ghost_cells(std::size_t max_ghost_cells);

// Clear out all ghost cells
  void clear();

// Reset the values in all ghost cells to the default value
  void reset();

// Flush all values destined for remote processors
  void flush();

reference operator[](const key_type& key) const
  {
    owner_local_pair p = get(data->global, key);

if (p.first == process_id(data->process_group)) {
      return data->storage[p.second];
    } else {
      return cell(key);
    }
  }

process_group_type process_group() const
  {
    return data->process_group.base();
  }

StorageMap&       base()       { return data->storage; }
  const StorageMap& base() const { return data->storage; }

/** Sends a "put" request.
   * \internal
   *
   */
  void
  request_put(process_id_type p, const key_type& k, const value_type& v) const
  {
    send(data->process_group, p, property_map_put,
         boost::parallel::detail::make_untracked_pair(k, v));
  }

/** Access the ghost cell for the given key.
   * \internal
   */
  value_type& cell(const key_type& k, bool request_if_missing = true) const;

/** Perform synchronization
   * \internal
   */
  void do_synchronize();

const GlobalMap& global() const { return data->global; }
  GlobalMap&       global()       { return data->global; }

struct data_t
  {
    data_t(const ProcessGroup& pg, const GlobalMap& global,
           const StorageMap& pm, const function1<value_type, key_type>& dv,
           bool has_default_resolver)
      : process_group(pg), global(global), storage(pm),
        ghost_cells(), max_ghost_cells(1000000), get_default_value(dv),
        has_default_resolver(has_default_resolver), model(cm_forward) { }

/// The process group
    ProcessGroup process_group;

/// A mapping from the keys of this property map to the global
    /// descriptor.
    GlobalMap global;

/// Local property map
    StorageMap storage;

/// The ghost cells
    shared_ptr<ghost_cells_type> ghost_cells;

/// The maximum number of ghost cells we are permitted to hold. If
    /// zero, we are permitted to have an infinite number of ghost
    /// cells.
    std::size_t max_ghost_cells;

/// Default value for remote ghost cells, as defined by the
    /// reduction operation.
    function1<value_type, key_type> get_default_value;

/// True if this resolver is the "default" resolver, meaning that
    /// we should not be able to get() a default value; it needs to be
    /// request()ed first.
    bool has_default_resolver;

// Current consistency model
    int model;

// Function that resets all of the ghost cells to their default
    // values. It knows the type of the resolver, so we can eliminate
    // a large number of calls through function pointers.
    void (data_t::*reset)();

// Clear out all ghost cells
    void clear();

// Flush all values destined for remote processors
    void flush();

// Send out requests to "refresh" the values of ghost cells that
    // we're holding.
    void refresh_ghost_cells();

private:
    template<typename Resolver> void do_reset();

friend class distributed_property_map;
  };
  friend struct data_t;

shared_ptr<data_t> data;

private:
  // Prunes the least recently used ghost cells until we have @c
  // max_ghost_cells or fewer ghost cells.
  void prune_ghost_cells() const;

/** Handles incoming messages.
   *
   * This function object is responsible for handling all incoming
   * messages for the distributed property map.
   */
  template<typename Reduce>
  struct handle_message
  {
    explicit handle_message(const shared_ptr<data_t>& data,
                            const Reduce& reduce = Reduce())
      : data_ptr(data), reduce(reduce) { }

void operator()(process_id_type source, int tag);

/// Individual message handlers
    void
    handle_put(int source, int tag,
               const boost::parallel::detail::untracked_pair<key_type, value_type>& data,
               trigger_receive_context);

value_type
    handle_get(int source, int tag, const key_type& data,
               trigger_receive_context);

void
    handle_multiget(int source, int tag,
                    const std::vector<key_type>& data,
                    trigger_receive_context);

void
    handle_multiget_reply
      (int source, int tag,
       const std::vector<boost::parallel::detail::untracked_pair<key_type, value_type> >& msg,
       trigger_receive_context);

void
    handle_multiput
      (int source, int tag,
       const std::vector<unsafe_pair<local_key_type, value_type> >& data,
       trigger_receive_context);

void setup_triggers(process_group_type& pg);

private:
    weak_ptr<data_t> data_ptr;
    Reduce reduce;
  };

/* Sets up the next stage in a multi-stage synchronization, for
     bidirectional consistency. */
  struct on_synchronize
  {
    explicit on_synchronize(const shared_ptr<data_t>& data) : data_ptr(data) { }

void operator()();

private:
    weak_ptr<data_t> data_ptr;
  };
};

/* An implementation helper macro for the common case of naming
   distributed property maps with all of the normal template
   parameters. */
#define PBGL_DISTRIB_PMAP                                       \
  distributed_property_map<ProcessGroup, GlobalMap, StorageMap>

/* Request that the value for the given remote key be retrieved in
   the next synchronization round. */
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
inline void
request(const PBGL_DISTRIB_PMAP& pm,
        typename PBGL_DISTRIB_PMAP::key_type const& key)
{
  if (get(pm.data->global, key).first != process_id(pm.data->process_group))
    pm.cell(key, false);
}

/** Get the value associated with a particular key.  Retrieves the
 * value associated with the given key. If the key denotes a
 * locally-owned object, it returns the value from the local property
 * map; if the key denotes a remotely-owned object, retrieves the
 * value of the ghost cell for that key, which may be the default
 * value provided by the reduce operation.
 *
 * Complexity: For a local key, O(1) get operations on the underlying
 * property map. For a non-local key, O(1) accesses to the ghost cells.
 */
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
inline
typename PBGL_DISTRIB_PMAP::value_type
get(const PBGL_DISTRIB_PMAP& pm,
    typename PBGL_DISTRIB_PMAP::key_type const& key)
{
  using boost::get;

typename property_traits<GlobalMap>::value_type p =
    get(pm.data->global, key);

if (p.first == process_id(pm.data->process_group)) {
    return get(pm.data->storage, p.second);
  } else {
    return pm.cell(key);
  }
}

/** Put a value associated with the given key into the property map.
 * When the key denotes a locally-owned object, this operation updates
 * the underlying local property map. Otherwise, the local ghost cell
 * is updated and a "put" message is sent to the processor owning this
 * key.
 *
 * Complexity: For a local key, O(1) put operations on the underlying
 * property map. For a nonlocal key, O(1) accesses to the ghost cells
 * and will send O(1) messages of size O(sizeof(key) + sizeof(value)).
 */
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void
put(const PBGL_DISTRIB_PMAP& pm,
    typename PBGL_DISTRIB_PMAP::key_type const & key,
    typename PBGL_DISTRIB_PMAP::value_type const & value)
{
  using boost::put;

typename property_traits<GlobalMap>::value_type p =
    get(pm.data->global, key);

if (p.first == process_id(pm.data->process_group)) {
    put(pm.data->storage, p.second, value);
  } else {
    if (pm.data->model & cm_forward)
      pm.request_put(p.first, key, value);

pm.cell(key, false) = value;
  }
}

/** Put a value associated with a given key into the local view of the
 * property map. This operation is equivalent to @c put, but with one
 * exception: no message will be sent to the owning processor in the
 * case of a remote update. The effect is that any value written via
 * @c local_put for a remote key may be overwritten in the next
 * synchronization round.
 */
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void
local_put(const PBGL_DISTRIB_PMAP& pm,
          typename PBGL_DISTRIB_PMAP::key_type const & key,
          typename PBGL_DISTRIB_PMAP::value_type const & value)
{
  using boost::put;

typename property_traits<GlobalMap>::value_type p =
    get(pm.data->global, key);

if (p.first == process_id(pm.data->process_group))
    put(pm.data->storage, p.second, value);
  else pm.cell(key, false) = value;
}

/** Cache the value associated with the given remote key. If the key
 *  is local, ignore the operation. */
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
inline void
cache(const PBGL_DISTRIB_PMAP& pm,
      typename PBGL_DISTRIB_PMAP::key_type const & key,
      typename PBGL_DISTRIB_PMAP::value_type const & value)
{
  typename ProcessGroup::process_id_type id = get(pm.data->global, key).first;

if (id != process_id(pm.data->process_group)) pm.cell(key, false) = value;
}

/// Synchronize the property map.
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
void
synchronize(PBGL_DISTRIB_PMAP& pm)
{
  pm.do_synchronize();
}

/// Create a distributed property map.
template<typename ProcessGroup, typename GlobalMap, typename StorageMap>
inline distributed_property_map<ProcessGroup, GlobalMap, StorageMap>
make_distributed_property_map(const ProcessGroup& pg, GlobalMap global,
                              StorageMap storage)
{
  typedef distributed_property_map<ProcessGroup, GlobalMap, StorageMap>
    result_type;
  return result_type(pg, global, storage);
}

/**
 * \overload
 */
template<typename ProcessGroup, typename GlobalMap, typename StorageMap,
         typename Reduce>
inline distributed_property_map<ProcessGroup, GlobalMap, StorageMap>
make_distributed_property_map(const ProcessGroup& pg, GlobalMap global,
                              StorageMap storage, Reduce reduce)
{
  typedef distributed_property_map<ProcessGroup, GlobalMap, StorageMap>
    result_type;
  return result_type(pg, global, storage, reduce);
}

} } // end namespace boost::parallel

#include <boost/property_map/parallel/impl/distributed_property_map.ipp>

#undef PBGL_DISTRIB_PMAP

#endif // BOOST_PARALLEL_DISTRIBUTED_PROPERTY_MAP_HPP

// Copyright (C) 2004-2008 The Trustees of Indiana University. // Use, modification and distribution is subject to the Boost Software // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) // Authors: Douglas Gregor // Nick Edmonds // Andrew Lumsdaine // The placement of this #include probably looks very odd relative to // the #ifndef/#define pair below. However, this placement is // extremely important to allow the various property map headers to be // included in any order. #include #ifndef BOOST_PARALLEL_DISTRIBUTED_PROPERTY_MAP_HPP #define BOOST_PARALLEL_DISTRIBUTED_PROPERTY_MAP_HPP #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // Serialization functions for constructs we use #include namespace boost { namespace parallel { namespace detail { /************************************************************************** * Metafunction that degrades an Lvalue Property Map category tag to * a Read Write Property Map category tag. **************************************************************************/ template struct make_nonlvalue_property_map { template struct apply { typedef T type; }; }; template<> struct make_nonlvalue_property_map { template struct apply { typedef read_write_property_map_tag type; }; }; /************************************************************************** * Performs a "put" on a property map so long as the property map is * a Writable Property Map or a mutable Lvalue Property Map. This * is required because the distributed property map's message * handler handles "put" messages even for a const property map, * although receipt of a "put" message is ill-formed. **************************************************************************/ template struct maybe_put_in_lvalue_pm { template static inline void do_put(PropertyMap, const Key&, const Value&) { BOOST_ASSERT(false); } }; template<> struct maybe_put_in_lvalue_pm { template static inline void do_put(PropertyMap pm, const Key& key, const Value& value) { using boost::put; put(pm, key, value); } }; template inline void maybe_put_impl(PropertyMap pm, const Key& key, const Value& value, writable_property_map_tag) { using boost::put; put(pm, key, value); } template inline void maybe_put_impl(PropertyMap pm, const Key& key, const Value& value, lvalue_property_map_tag) { typedef typename property_traits::value_type value_type; typedef typename property_traits::reference reference; // DPG TBD: Some property maps are improperly characterized as // lvalue_property_maps, when in fact they do not provide true // references. The most typical example is those property maps // built from vector and its iterators, which deal with // proxies. We don't want to mischaracterize these as not having a // "put" operation, so we only consider an lvalue_property_map as // constant if its reference is const value_type&. In fact, this // isn't even quite correct (think of a // vector::const_iterator), but at present C++ doesn't // provide us with any alternatives. typedef is_same is_constant; maybe_put_in_lvalue_pm<(!is_constant::value)>::do_put(pm, key, value); } template inline void maybe_put_impl(PropertyMap, const Key&, const Value&, ...) { BOOST_ASSERT(false); } template inline void maybe_put(PropertyMap pm, const Key& key, const Value& value) { maybe_put_impl(pm, key, value, typename property_traits::category()); } } // end namespace detail /** The consistency model used by the distributed property map. */ enum consistency_model { cm_forward = 1 << 0, cm_backward = 1 << 1, cm_bidirectional = cm_forward | cm_backward, cm_flush = 1 << 2, cm_reset = 1 << 3, cm_clear = 1 << 4 }; /** Distributed property map adaptor. * * The 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 @c get and @c put. Values stored on * remote processes may also be access via @c get and @c put, but the * behavior differs slightly: * * - @c 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. * * - @c get operations returns the contents of the local ghost * cell. If no ghost cell is available, one is created using the * default value provided by the "reduce" operation. See, e.g., * @ref basic_reduce and @ref property_reduce. * * 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 @ref 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. * * @tparam ProcessGroup the type of the process group over which the * property map is distributed and is also the medium for * communication. * * @tparam StorageMap the type of the property map that will * store values for keys local to this processor. The @c value_type of * this property map will become the @c value_type of the distributed * property map. The distributed property map models the same property * map concepts as the @c LocalPropertyMap, with one exception: a * distributed property map cannot be an LvaluePropertyMap (because * remote values are not addressable), and is therefore limited to * ReadWritePropertyMap. */ template class distributed_property_map { public: /// The key type of the property map. typedef typename property_traits::key_type key_type; /// The value type of the property map. typedef typename property_traits::value_type value_type; typedef typename property_traits::reference reference; typedef ProcessGroup process_group_type; private: typedef distributed_property_map self_type; typedef typename property_traits::category local_category; typedef typename property_traits::key_type local_key_type; typedef typename property_traits::value_type owner_local_pair; typedef typename ProcessGroup::process_id_type process_id_type; enum property_map_messages { /** A request to store a value in a property map. The message * contains a std::pair. */ property_map_put, /** A request to retrieve a particular value in a property * map. The message contains a key. The owner of that key will * reply with a value. */ property_map_get, /** A request to update values stored on a remote processor. The * message contains a vector of keys for which the source * requests updated values. This message will only be transmitted * during synchronization. */ property_map_multiget, /** A request to store values in a ghost cell. This message * contains a vector of key/value pairs corresponding to the * sequence of keys sent to the source processor. */ property_map_multiget_reply, /** The payload containing a vector of local key-value pairs to be * put into the remote property map. A key-value std::pair will be * used to store each local key-value pair. */ property_map_multiput }; // Code from Joaquín M López Muñoz to work around unusual implementation of // std::pair in VC++ 10: template class pair_first_extractor { typedef std::pair value_type; public: typedef First result_type; const result_type& operator()(const value_type& x) const { return x.first; } result_type& operator()(value_type& x) const { return x.first; } }; public: /// The type of the ghost cells typedef multi_index::multi_index_container< std::pair, multi_index::indexed_by< multi_index::sequenced<>, multi_index::hashed_unique< pair_first_extractor > > > ghost_cells_type; /// Iterator into the ghost cells typedef typename ghost_cells_type::iterator iterator; /// Key-based index into the ghost cells typedef typename ghost_cells_type::template nth_index<1>::type ghost_cells_key_index_type; /// Iterator into the ghost cells (by key) typedef typename ghost_cells_key_index_type::iterator key_iterator; /** The property map category. A distributed property map cannot be * an Lvalue Property Map, because values on remote processes cannot * be addresses. */ typedef typename detail::make_nonlvalue_property_map< (is_base_and_derived::value || is_same::value)> ::template apply::type category; /** Default-construct a distributed property map. This function * creates an initialized property map that must be assigned to a * valid value before being used. It is only provided here because * property maps must be Default Constructible. */ distributed_property_map() {} /** Construct a distributed property map. Builds a distributed * property map communicating over the given process group and using * the given local property map for storage. Since no reduction * operation is provided, the default reduction operation @c * basic_reduce is used. */ distributed_property_map(const ProcessGroup& pg, const GlobalMap& global, const StorageMap& pm) : data(new data_t(pg, global, pm, basic_reduce(), false)) { typedef handle_message > Handler; data->ghost_cells.reset(new ghost_cells_type()); Handler handler(data); data->process_group.replace_handler(handler, true); data->process_group.template get_receiver() ->setup_triggers(data->process_group); } /** Construct a distributed property map. Builds a distributed * property map communicating over the given process group and using * the given local property map for storage. The given @p reduce * parameter is used as the reduction operation. */ template distributed_property_map(const ProcessGroup& pg, const GlobalMap& global, const StorageMap& pm, const Reduce& reduce); ~distributed_property_map(); /// Set the reduce operation of the distributed property map. template void set_reduce(const Reduce& reduce); // Set the consistency model for the distributed property map void set_consistency_model(int model); // Get the consistency model int get_consistency_model() const { return data->model; } // Set the maximum number of ghost cells that we are allowed to // maintain. If 0, all ghost cells will be retained. void set_max_ghost_cells(std::size_t max_ghost_cells); // Clear out all ghost cells void clear(); // Reset the values in all ghost cells to the default value void reset(); // Flush all values destined for remote processors void flush(); reference operator[](const key_type& key) const { owner_local_pair p = get(data->global, key); if (p.first == process_id(data->process_group)) { return data->storage[p.second]; } else { return cell(key); } } process_group_type process_group() const { return data->process_group.base(); } StorageMap& base() { return data->storage; } const StorageMap& base() const { return data->storage; } /** Sends a "put" request. * \internal * */ void request_put(process_id_type p, const key_type& k, const value_type& v) const { send(data->process_group, p, property_map_put, boost::parallel::detail::make_untracked_pair(k, v)); } /** Access the ghost cell for the given key. * \internal */ value_type& cell(const key_type& k, bool request_if_missing = true) const; /** Perform synchronization * \internal */ void do_synchronize(); const GlobalMap& global() const { return data->global; } GlobalMap& global() { return data->global; } struct data_t { data_t(const ProcessGroup& pg, const GlobalMap& global, const StorageMap& pm, const function1& dv, bool has_default_resolver) : process_group(pg), global(global), storage(pm), ghost_cells(), max_ghost_cells(1000000), get_default_value(dv), has_default_resolver(has_default_resolver), model(cm_forward) { } /// The process group ProcessGroup process_group; /// A mapping from the keys of this property map to the global /// descriptor. GlobalMap global; /// Local property map StorageMap storage; /// The ghost cells shared_ptr ghost_cells; /// The maximum number of ghost cells we are permitted to hold. If /// zero, we are permitted to have an infinite number of ghost /// cells. std::size_t max_ghost_cells; /// Default value for remote ghost cells, as defined by the /// reduction operation. function1 get_default_value; /// True if this resolver is the "default" resolver, meaning that /// we should not be able to get() a default value; it needs to be /// request()ed first. bool has_default_resolver; // Current consistency model int model; // Function that resets all of the ghost cells to their default // values. It knows the type of the resolver, so we can eliminate // a large number of calls through function pointers. void (data_t::*reset)(); // Clear out all ghost cells void clear(); // Flush all values destined for remote processors void flush(); // Send out requests to "refresh" the values of ghost cells that // we're holding. void refresh_ghost_cells(); private: template void do_reset(); friend class distributed_property_map; }; friend struct data_t; shared_ptr data; private: // Prunes the least recently used ghost cells until we have @c // max_ghost_cells or fewer ghost cells. void prune_ghost_cells() const; /** Handles incoming messages. * * This function object is responsible for handling all incoming * messages for the distributed property map. */ template struct handle_message { explicit handle_message(const shared_ptr& data, const Reduce& reduce = Reduce()) : data_ptr(data), reduce(reduce) { } void operator()(process_id_type source, int tag); /// Individual message handlers void handle_put(int source, int tag, const boost::parallel::detail::untracked_pair& data, trigger_receive_context); value_type handle_get(int source, int tag, const key_type& data, trigger_receive_context); void handle_multiget(int source, int tag, const std::vector& data, trigger_receive_context); void handle_multiget_reply (int source, int tag, const std::vector >& msg, trigger_receive_context); void handle_multiput (int source, int tag, const std::vector >& data, trigger_receive_context); void setup_triggers(process_group_type& pg); private: weak_ptr data_ptr; Reduce reduce; }; /* Sets up the next stage in a multi-stage synchronization, for bidirectional consistency. */ struct on_synchronize { explicit on_synchronize(const shared_ptr& data) : data_ptr(data) { } void operator()(); private: weak_ptr data_ptr; }; }; /* An implementation helper macro for the common case of naming distributed property maps with all of the normal template parameters. */ #define PBGL_DISTRIB_PMAP \ distributed_property_map /* Request that the value for the given remote key be retrieved in the next synchronization round. */ template inline void request(const PBGL_DISTRIB_PMAP& pm, typename PBGL_DISTRIB_PMAP::key_type const& key) { if (get(pm.data->global, key).first != process_id(pm.data->process_group)) pm.cell(key, false); } /** Get the value associated with a particular key. Retrieves the * value associated with the given key. If the key denotes a * locally-owned object, it returns the value from the local property * map; if the key denotes a remotely-owned object, retrieves the * value of the ghost cell for that key, which may be the default * value provided by the reduce operation. * * Complexity: For a local key, O(1) get operations on the underlying * property map. For a non-local key, O(1) accesses to the ghost cells. */ template inline typename PBGL_DISTRIB_PMAP::value_type get(const PBGL_DISTRIB_PMAP& pm, typename PBGL_DISTRIB_PMAP::key_type const& key) { using boost::get; typename property_traits::value_type p = get(pm.data->global, key); if (p.first == process_id(pm.data->process_group)) { return get(pm.data->storage, p.second); } else { return pm.cell(key); } } /** Put a value associated with the given key into the property map. * When the key denotes a locally-owned object, this operation updates * the underlying local property map. Otherwise, the local ghost cell * is updated and a "put" message is sent to the processor owning this * key. * * Complexity: For a local key, O(1) put operations on the underlying * property map. For a nonlocal key, O(1) accesses to the ghost cells * and will send O(1) messages of size O(sizeof(key) + sizeof(value)). */ template void put(const PBGL_DISTRIB_PMAP& pm, typename PBGL_DISTRIB_PMAP::key_type const & key, typename PBGL_DISTRIB_PMAP::value_type const & value) { using boost::put; typename property_traits::value_type p = get(pm.data->global, key); if (p.first == process_id(pm.data->process_group)) { put(pm.data->storage, p.second, value); } else { if (pm.data->model & cm_forward) pm.request_put(p.first, key, value); pm.cell(key, false) = value; } } /** Put a value associated with a given key into the local view of the * property map. This operation is equivalent to @c put, but with one * exception: no message will be sent to the owning processor in the * case of a remote update. The effect is that any value written via * @c local_put for a remote key may be overwritten in the next * synchronization round. */ template void local_put(const PBGL_DISTRIB_PMAP& pm, typename PBGL_DISTRIB_PMAP::key_type const & key, typename PBGL_DISTRIB_PMAP::value_type const & value) { using boost::put; typename property_traits::value_type p = get(pm.data->global, key); if (p.first == process_id(pm.data->process_group)) put(pm.data->storage, p.second, value); else pm.cell(key, false) = value; } /** Cache the value associated with the given remote key. If the key * is local, ignore the operation. */ template inline void cache(const PBGL_DISTRIB_PMAP& pm, typename PBGL_DISTRIB_PMAP::key_type const & key, typename PBGL_DISTRIB_PMAP::value_type const & value) { typename ProcessGroup::process_id_type id = get(pm.data->global, key).first; if (id != process_id(pm.data->process_group)) pm.cell(key, false) = value; } /// Synchronize the property map. template void synchronize(PBGL_DISTRIB_PMAP& pm) { pm.do_synchronize(); } /// Create a distributed property map. template inline distributed_property_map make_distributed_property_map(const ProcessGroup& pg, GlobalMap global, StorageMap storage) { typedef distributed_property_map result_type; return result_type(pg, global, storage); } /** * \overload */ template inline distributed_property_map make_distributed_property_map(const ProcessGroup& pg, GlobalMap global, StorageMap storage, Reduce reduce) { typedef distributed_property_map result_type; return result_type(pg, global, storage, reduce); } } } // end namespace boost::parallel #include #undef PBGL_DISTRIB_PMAP #endif // BOOST_PARALLEL_DISTRIBUTED_PROPERTY_MAP_HPP