ceph/src/boost/libs/graph_parallel/include/boost/graph/distributed/boman_et_al_graph_coloring.hpp

   1 // Copyright (C) 2005-2008 The Trustees of Indiana University.
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   5 // http://www.boost.org/LICENSE_1_0.txt)
   6
   7 //  Authors: Douglas Gregor
   8 //           Andrew Lumsdaine
   9 #ifndef BOOST_GRAPH_DISTRIBUTED_BOMAN_ET_AL_GRAPH_COLORING_HPP
  10 #define BOOST_GRAPH_DISTRIBUTED_BOMAN_ET_AL_GRAPH_COLORING_HPP
  11
  12 #ifndef BOOST_GRAPH_USE_MPI
  13 #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
  14 #endif
  15
  16 #include <boost/graph/graph_traits.hpp>
  17 #include <boost/graph/parallel/algorithm.hpp>
  18 #include <boost/property_map/property_map.hpp>
  19 #include <boost/graph/parallel/process_group.hpp>
  20 #include <functional>
  21 #include <vector>
  22 #include <utility>
  23 #include <boost/graph/iteration_macros.hpp>
  24 #include <boost/optional.hpp>
  25 #include <boost/assert.hpp>
  26 #include <boost/graph/parallel/container_traits.hpp>
  27 #include <boost/graph/properties.hpp>
  28
  29 #ifdef PBGL_ACCOUNTING
  30 #  include <boost/graph/accounting.hpp>
  31 #endif // PBGL_ACCOUNTING
  32
  33 namespace boost { namespace graph { namespace distributed {
  34
  35 /**************************************************************************
  36  * This source file implements the distributed graph coloring algorithm   *
  37  * by Boman et al in:                                                     *
  38  *                                                                        *
  39  *   Erik G. Boman, Doruk Bozdag, Umit Catalyurek, Assefaw H. Gebremedhin,*
  40  *   and Fredrik Manne. A Scalable Parallel Graph Coloring Algorithm for  *
  41  *   Distributed Memory Computers. [unpublished preprint?]                *
  42  *                                                                        *
  43  **************************************************************************/
  44
  45 #ifdef PBGL_ACCOUNTING
  46 struct boman_et_al_graph_coloring_stats_t
  47 {
  48   /* The size of the blocks to step through (i.e., the parameter s). */
  49   std::size_t block_size;
  50
  51   /* Total wall-clock time used by the algorithm.*/
  52   accounting::time_type execution_time;
  53
  54   /* The number of conflicts that occurred during execution. */
  55   std::size_t conflicts;
  56
  57   /* The number of supersteps. */
  58   std::size_t supersteps;
  59
  60   /* The number of colors used. */
  61   std::size_t num_colors;
  62
  63   template<typename OutputStream>
  64   void print(OutputStream& out)
  65   {
  66     out << "Problem = \"Coloring\"\n"
  67         << "Algorithm = \"Boman et al\"\n"
  68         << "Function = boman_et_al_graph_coloring\n"
  69         << "(P) Block size = " << block_size << "\n"
  70         << "Wall clock time = " << accounting::print_time(execution_time)
  71         << "\nConflicts = " << conflicts << "\n"
  72         << "Supersteps = " << supersteps << "\n"
  73         << "(R) Colors = " << num_colors << "\n";
  74   }
  75 };
  76
  77 static boman_et_al_graph_coloring_stats_t boman_et_al_graph_coloring_stats;
  78 #endif
  79
  80 namespace detail {
  81   template<typename T>
  82   struct graph_coloring_reduce
  83   {
  84     BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
  85
  86     template<typename Key>
  87     T operator()(const Key&) const { return (std::numeric_limits<T>::max)(); }
  88
  89     template<typename Key> T operator()(const Key&, T, T y) const { return y; }
  90   };
  91 }
  92
  93 template<typename Color>
  94 struct first_fit_color
  95 {
  96   template<typename T>
  97   Color operator()(const std::vector<T>& marked, T marked_true)
  98   {
  99     Color k = 0;
 100     while (k < (Color)marked.size() && marked[k] == marked_true)
 101       ++k;
 102     return k;
 103   }
 104 };
 105
 106 template<typename DistributedGraph, typename ColorMap, typename ChooseColor,
 107          typename VertexOrdering, typename VertexIndexMap>
 108 typename property_traits<ColorMap>::value_type
 109 boman_et_al_graph_coloring
 110   (const DistributedGraph& g,
 111    ColorMap color,
 112    typename graph_traits<DistributedGraph>::vertices_size_type s,
 113    ChooseColor choose_color,
 114    VertexOrdering ordering, VertexIndexMap vertex_index)
 115 {
 116   using namespace boost::graph::parallel;
 117   using boost::parallel::all_reduce;
 118
 119   typename property_map<DistributedGraph, vertex_owner_t>::const_type
 120     owner = get(vertex_owner, g);
 121
 122   typedef typename process_group_type<DistributedGraph>::type
 123     process_group_type;
 124   typedef typename process_group_type::process_id_type process_id_type;
 125   typedef typename graph_traits<DistributedGraph>::vertex_descriptor Vertex;
 126   typedef typename graph_traits<DistributedGraph>::vertices_size_type
 127     vertices_size_type;
 128   typedef typename property_traits<ColorMap>::value_type color_type;
 129   typedef unsigned long long iterations_type;
 130   typedef typename std::vector<Vertex>::iterator vertex_set_iterator;
 131   typedef std::pair<Vertex, color_type> message_type;
 132
 133 #ifdef PBGL_ACCOUNTING
 134   boman_et_al_graph_coloring_stats.block_size = s;
 135   boman_et_al_graph_coloring_stats.execution_time = accounting::get_time();
 136   boman_et_al_graph_coloring_stats.conflicts = 0;
 137   boman_et_al_graph_coloring_stats.supersteps = 0;
 138 #endif
 139
 140   // Initialize color map
 141   color_type no_color = (std::numeric_limits<color_type>::max)();
 142   BGL_FORALL_VERTICES_T(v, g, DistributedGraph)
 143     put(color, v, no_color);
 144   color.set_reduce(detail::graph_coloring_reduce<color_type>());
 145
 146   // Determine if we'll be using synchronous or asynchronous communication.
 147   typedef typename process_group_type::communication_category
 148     communication_category;
 149   static const bool asynchronous =
 150     is_convertible<communication_category, boost::parallel::immediate_process_group_tag>::value;
 151   process_group_type pg = process_group(g);
 152
 153   // U_i <- V_i
 154   std::vector<Vertex> vertices_to_color(vertices(g).first, vertices(g).second);
 155
 156   iterations_type iter_num = 1, outer_iter_num = 1;
 157   std::vector<iterations_type> marked;
 158   std::vector<iterations_type> marked_conflicting(num_vertices(g), 0);
 159   std::vector<bool> sent_to_processors;
 160
 161   std::size_t rounds = vertices_to_color.size() / s
 162     + (vertices_to_color.size() % s == 0? 0 : 1);
 163   rounds = all_reduce(pg, rounds, boost::parallel::maximum<std::size_t>());
 164
 165 #ifdef PBGL_GRAPH_COLORING_DEBUG
 166   std::cerr << "Number of rounds = " << rounds << std::endl;
 167 #endif
 168
 169   while (rounds > 0) {
 170     if (!vertices_to_color.empty()) {
 171       // Set of conflicting vertices
 172       std::vector<Vertex> conflicting_vertices;
 173
 174       vertex_set_iterator first = vertices_to_color.begin();
 175       while (first != vertices_to_color.end()) {
 176         // For each subset of size s (or smaller for the last subset)
 177         vertex_set_iterator start = first;
 178         for (vertices_size_type counter = s;
 179              first != vertices_to_color.end() && counter > 0;
 180              ++first, --counter) {
 181           // This vertex hasn't been sent to anyone yet
 182           sent_to_processors.assign(num_processes(pg), false);
 183           sent_to_processors[process_id(pg)] = true;
 184
 185           // Mark all of the colors that we see
 186           BGL_FORALL_OUTEDGES_T(*first, e, g, DistributedGraph) {
 187             color_type k = get(color, target(e, g));
 188             if (k != no_color) {
 189               if (k >= (color_type)marked.size()) marked.resize(k + 1, 0);
 190               marked[k] = iter_num;
 191             }
 192           }
 193
 194           // Find a color for this vertex
 195           put(color, *first, choose_color(marked, iter_num));
 196
 197 #ifdef PBGL_GRAPH_COLORING_DEBUG
 198           std::cerr << "Chose color " << get(color, *first) << " for vertex "
 199                     << *first << std::endl;
 200 #endif
 201
 202           // Send this vertex's color to the owner of the edge target.
 203           BGL_FORALL_OUTEDGES_T(*first, e, g, DistributedGraph) {
 204             if (!sent_to_processors[get(owner, target(e, g))]) {
 205               send(pg, get(owner, target(e, g)), 17,
 206                    message_type(source(e, g), get(color, source(e, g))));
 207               sent_to_processors[get(owner, target(e, g))] = true;
 208             }
 209           }
 210
 211           ++iter_num;
 212         }
 213
 214         // Synchronize for non-immediate process groups.
 215         if (!asynchronous) {
 216           --rounds;
 217           synchronize(pg);
 218         }
 219
 220         // Receive boundary colors from other processors
 221         while (optional<std::pair<process_id_type, int> > stp = probe(pg)) {
 222           BOOST_ASSERT(stp->second == 17);
 223           message_type msg;
 224           receive(pg, stp->first, stp->second, msg);
 225           cache(color, msg.first, msg.second);
 226 #ifdef PBGL_GRAPH_COLORING_DEBUG
 227           std::cerr << "Cached color " << msg.second << " for vertex "
 228                     << msg.first << std::endl;
 229 #endif
 230         }
 231
 232         // Compute the set of conflicting vertices
 233         // [start, first) contains all vertices in this subset
 234         for (vertex_set_iterator vi = start; vi != first; ++vi) {
 235           Vertex v = *vi;
 236           BGL_FORALL_OUTEDGES_T(v, e, g, DistributedGraph) {
 237             Vertex w = target(e, g);
 238             if (get(owner, w) != process_id(pg) // boundary vertex
 239                 && marked_conflicting[get(vertex_index, v)] != outer_iter_num
 240                 && get(color, v) == get(color, w)
 241                 && ordering(v, w)) {
 242               conflicting_vertices.push_back(v);
 243               marked_conflicting[get(vertex_index, v)] = outer_iter_num;
 244               put(color, v, no_color);
 245 #ifdef PBGL_GRAPH_COLORING_DEBUG
 246               std::cerr << "Vertex " << v << " has a conflict with vertex "
 247                         << w << std::endl;
 248 #endif
 249               break;
 250             }
 251           }
 252         }
 253
 254 #ifdef PBGL_ACCOUNTING
 255         boman_et_al_graph_coloring_stats.conflicts +=
 256           conflicting_vertices.size();
 257 #endif
 258       }
 259
 260       if (asynchronous) synchronize(pg);
 261       else {
 262         while (rounds > 0) {
 263           synchronize(pg);
 264           --rounds;
 265         }
 266       }
 267       conflicting_vertices.swap(vertices_to_color);
 268       ++outer_iter_num;
 269     } else {
 270       if (asynchronous) synchronize(pg);
 271       else {
 272         while (rounds > 0) {
 273           synchronize(pg);
 274           --rounds;
 275         }
 276       }
 277     }
 278
 279     // Receive boundary colors from other processors
 280     while (optional<std::pair<process_id_type, int> > stp = probe(pg)) {
 281       BOOST_ASSERT(stp->second == 17);
 282       message_type msg;
 283       receive(pg, stp->first, stp->second, msg);
 284       cache(color, msg.first, msg.second);
 285     }
 286
 287     rounds = vertices_to_color.size() / s
 288       + (vertices_to_color.size() % s == 0? 0 : 1);
 289     rounds = all_reduce(pg, rounds, boost::parallel::maximum<std::size_t>());
 290
 291 #ifdef PBGL_ACCOUNTING
 292     ++boman_et_al_graph_coloring_stats.supersteps;
 293 #endif
 294   }
 295
 296   // Determine the number of colors used.
 297   color_type num_colors = 0;
 298   BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
 299     color_type k = get(color, v);
 300     BOOST_ASSERT(k != no_color);
 301     if (k != no_color) {
 302       if (k >= (color_type)marked.size()) marked.resize(k + 1, 0); // TBD: perf?
 303       if (marked[k] != iter_num) {
 304         marked[k] = iter_num;
 305         ++num_colors;
 306       }
 307     }
 308   }
 309
 310   num_colors =
 311     all_reduce(pg, num_colors, boost::parallel::maximum<color_type>());
 312
 313
 314 #ifdef PBGL_ACCOUNTING
 315   boman_et_al_graph_coloring_stats.execution_time =
 316     accounting::get_time() - boman_et_al_graph_coloring_stats.execution_time;
 317
 318   boman_et_al_graph_coloring_stats.conflicts =
 319     all_reduce(pg, boman_et_al_graph_coloring_stats.conflicts,
 320                std::plus<color_type>());
 321   boman_et_al_graph_coloring_stats.num_colors = num_colors;
 322 #endif
 323
 324   return num_colors;
 325 }
 326
 327
 328 template<typename DistributedGraph, typename ColorMap, typename ChooseColor,
 329          typename VertexOrdering>
 330 inline typename property_traits<ColorMap>::value_type
 331 boman_et_al_graph_coloring
 332   (const DistributedGraph& g, ColorMap color,
 333    typename graph_traits<DistributedGraph>::vertices_size_type s,
 334    ChooseColor choose_color, VertexOrdering ordering)
 335 {
 336   return boman_et_al_graph_coloring(g, color, s, choose_color, ordering,
 337                                     get(vertex_index, g));
 338 }
 339
 340 template<typename DistributedGraph, typename ColorMap, typename ChooseColor>
 341 inline typename property_traits<ColorMap>::value_type
 342 boman_et_al_graph_coloring
 343   (const DistributedGraph& g,
 344    ColorMap color,
 345    typename graph_traits<DistributedGraph>::vertices_size_type s,
 346    ChooseColor choose_color)
 347 {
 348   typedef typename graph_traits<DistributedGraph>::vertex_descriptor
 349     vertex_descriptor;
 350   return boman_et_al_graph_coloring(g, color, s, choose_color,
 351                                     std::less<vertex_descriptor>());
 352 }
 353
 354 template<typename DistributedGraph, typename ColorMap>
 355 inline typename property_traits<ColorMap>::value_type
 356 boman_et_al_graph_coloring
 357   (const DistributedGraph& g,
 358    ColorMap color,
 359    typename graph_traits<DistributedGraph>::vertices_size_type s = 100)
 360 {
 361   typedef typename property_traits<ColorMap>::value_type Color;
 362   return boman_et_al_graph_coloring(g, color, s, first_fit_color<Color>());
 363 }
 364
 365 } } } // end namespace boost::graph::distributed
 366
 367 namespace boost { namespace graph {
 368 using distributed::boman_et_al_graph_coloring;
 369 } } // end namespace boost::graph
 370
 371 #endif // BOOST_GRAPH_DISTRIBUTED_BOMAN_ET_AL_GRAPH_COLORING_HPP