123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371 |
- // Copyright (C) 2005-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
- // Andrew Lumsdaine
- #ifndef BOOST_GRAPH_DISTRIBUTED_BOMAN_ET_AL_GRAPH_COLORING_HPP
- #define BOOST_GRAPH_DISTRIBUTED_BOMAN_ET_AL_GRAPH_COLORING_HPP
- #ifndef BOOST_GRAPH_USE_MPI
- #error "Parallel BGL files should not be included unless <boost/graph/use_mpi.hpp> has been included"
- #endif
- #include <boost/graph/graph_traits.hpp>
- #include <boost/graph/parallel/algorithm.hpp>
- #include <boost/property_map/property_map.hpp>
- #include <boost/graph/parallel/process_group.hpp>
- #include <functional>
- #include <vector>
- #include <utility>
- #include <boost/graph/iteration_macros.hpp>
- #include <boost/optional.hpp>
- #include <boost/assert.hpp>
- #include <boost/graph/parallel/container_traits.hpp>
- #include <boost/graph/properties.hpp>
- #ifdef PBGL_ACCOUNTING
- # include <boost/graph/accounting.hpp>
- #endif // PBGL_ACCOUNTING
- namespace boost { namespace graph { namespace distributed {
- /**************************************************************************
- * This source file implements the distributed graph coloring algorithm *
- * by Boman et al in: *
- * *
- * Erik G. Boman, Doruk Bozdag, Umit Catalyurek, Assefaw H. Gebremedhin,*
- * and Fredrik Manne. A Scalable Parallel Graph Coloring Algorithm for *
- * Distributed Memory Computers. [unpublished preprint?] *
- * *
- **************************************************************************/
- #ifdef PBGL_ACCOUNTING
- struct boman_et_al_graph_coloring_stats_t
- {
- /* The size of the blocks to step through (i.e., the parameter s). */
- std::size_t block_size;
-
- /* Total wall-clock time used by the algorithm.*/
- accounting::time_type execution_time;
- /* The number of conflicts that occurred during execution. */
- std::size_t conflicts;
- /* The number of supersteps. */
- std::size_t supersteps;
- /* The number of colors used. */
- std::size_t num_colors;
- template<typename OutputStream>
- void print(OutputStream& out)
- {
- out << "Problem = \"Coloring\"\n"
- << "Algorithm = \"Boman et al\"\n"
- << "Function = boman_et_al_graph_coloring\n"
- << "(P) Block size = " << block_size << "\n"
- << "Wall clock time = " << accounting::print_time(execution_time)
- << "\nConflicts = " << conflicts << "\n"
- << "Supersteps = " << supersteps << "\n"
- << "(R) Colors = " << num_colors << "\n";
- }
- };
- static boman_et_al_graph_coloring_stats_t boman_et_al_graph_coloring_stats;
- #endif
- namespace detail {
- template<typename T>
- struct graph_coloring_reduce
- {
- BOOST_STATIC_CONSTANT(bool, non_default_resolver = true);
- template<typename Key>
- T operator()(const Key&) const { return (std::numeric_limits<T>::max)(); }
- template<typename Key> T operator()(const Key&, T, T y) const { return y; }
- };
- }
- template<typename Color>
- struct first_fit_color
- {
- template<typename T>
- Color operator()(const std::vector<T>& marked, T marked_true)
- {
- Color k = 0;
- while (k < (Color)marked.size() && marked[k] == marked_true)
- ++k;
- return k;
- }
- };
- template<typename DistributedGraph, typename ColorMap, typename ChooseColor,
- typename VertexOrdering, typename VertexIndexMap>
- typename property_traits<ColorMap>::value_type
- boman_et_al_graph_coloring
- (const DistributedGraph& g,
- ColorMap color,
- typename graph_traits<DistributedGraph>::vertices_size_type s,
- ChooseColor choose_color,
- VertexOrdering ordering, VertexIndexMap vertex_index)
- {
- using namespace boost::graph::parallel;
- using boost::parallel::all_reduce;
- typename property_map<DistributedGraph, vertex_owner_t>::const_type
- owner = get(vertex_owner, g);
- typedef typename process_group_type<DistributedGraph>::type
- process_group_type;
- typedef typename process_group_type::process_id_type process_id_type;
- typedef typename graph_traits<DistributedGraph>::vertex_descriptor Vertex;
- typedef typename graph_traits<DistributedGraph>::vertices_size_type
- vertices_size_type;
- typedef typename property_traits<ColorMap>::value_type color_type;
- typedef unsigned long long iterations_type;
- typedef typename std::vector<Vertex>::iterator vertex_set_iterator;
- typedef std::pair<Vertex, color_type> message_type;
- #ifdef PBGL_ACCOUNTING
- boman_et_al_graph_coloring_stats.block_size = s;
- boman_et_al_graph_coloring_stats.execution_time = accounting::get_time();
- boman_et_al_graph_coloring_stats.conflicts = 0;
- boman_et_al_graph_coloring_stats.supersteps = 0;
- #endif
- // Initialize color map
- color_type no_color = (std::numeric_limits<color_type>::max)();
- BGL_FORALL_VERTICES_T(v, g, DistributedGraph)
- put(color, v, no_color);
- color.set_reduce(detail::graph_coloring_reduce<color_type>());
-
- // Determine if we'll be using synchronous or asynchronous communication.
- typedef typename process_group_type::communication_category
- communication_category;
- static const bool asynchronous =
- is_convertible<communication_category, boost::parallel::immediate_process_group_tag>::value;
- process_group_type pg = process_group(g);
- // U_i <- V_i
- std::vector<Vertex> vertices_to_color(vertices(g).first, vertices(g).second);
- iterations_type iter_num = 1, outer_iter_num = 1;
- std::vector<iterations_type> marked;
- std::vector<iterations_type> marked_conflicting(num_vertices(g), 0);
- std::vector<bool> sent_to_processors;
- std::size_t rounds = vertices_to_color.size() / s
- + (vertices_to_color.size() % s == 0? 0 : 1);
- rounds = all_reduce(pg, rounds, boost::parallel::maximum<std::size_t>());
- #ifdef PBGL_GRAPH_COLORING_DEBUG
- std::cerr << "Number of rounds = " << rounds << std::endl;
- #endif
- while (rounds > 0) {
- if (!vertices_to_color.empty()) {
- // Set of conflicting vertices
- std::vector<Vertex> conflicting_vertices;
- vertex_set_iterator first = vertices_to_color.begin();
- while (first != vertices_to_color.end()) {
- // For each subset of size s (or smaller for the last subset)
- vertex_set_iterator start = first;
- for (vertices_size_type counter = s;
- first != vertices_to_color.end() && counter > 0;
- ++first, --counter) {
- // This vertex hasn't been sent to anyone yet
- sent_to_processors.assign(num_processes(pg), false);
- sent_to_processors[process_id(pg)] = true;
- // Mark all of the colors that we see
- BGL_FORALL_OUTEDGES_T(*first, e, g, DistributedGraph) {
- color_type k = get(color, target(e, g));
- if (k != no_color) {
- if (k >= (color_type)marked.size()) marked.resize(k + 1, 0);
- marked[k] = iter_num;
- }
- }
- // Find a color for this vertex
- put(color, *first, choose_color(marked, iter_num));
- #ifdef PBGL_GRAPH_COLORING_DEBUG
- std::cerr << "Chose color " << get(color, *first) << " for vertex "
- << *first << std::endl;
- #endif
- // Send this vertex's color to the owner of the edge target.
- BGL_FORALL_OUTEDGES_T(*first, e, g, DistributedGraph) {
- if (!sent_to_processors[get(owner, target(e, g))]) {
- send(pg, get(owner, target(e, g)), 17,
- message_type(source(e, g), get(color, source(e, g))));
- sent_to_processors[get(owner, target(e, g))] = true;
- }
- }
- ++iter_num;
- }
- // Synchronize for non-immediate process groups.
- if (!asynchronous) {
- --rounds;
- synchronize(pg);
- }
- // Receive boundary colors from other processors
- while (optional<std::pair<process_id_type, int> > stp = probe(pg)) {
- BOOST_ASSERT(stp->second == 17);
- message_type msg;
- receive(pg, stp->first, stp->second, msg);
- cache(color, msg.first, msg.second);
- #ifdef PBGL_GRAPH_COLORING_DEBUG
- std::cerr << "Cached color " << msg.second << " for vertex "
- << msg.first << std::endl;
- #endif
- }
- // Compute the set of conflicting vertices
- // [start, first) contains all vertices in this subset
- for (vertex_set_iterator vi = start; vi != first; ++vi) {
- Vertex v = *vi;
- BGL_FORALL_OUTEDGES_T(v, e, g, DistributedGraph) {
- Vertex w = target(e, g);
- if (get(owner, w) != process_id(pg) // boundary vertex
- && marked_conflicting[get(vertex_index, v)] != outer_iter_num
- && get(color, v) == get(color, w)
- && ordering(v, w)) {
- conflicting_vertices.push_back(v);
- marked_conflicting[get(vertex_index, v)] = outer_iter_num;
- put(color, v, no_color);
- #ifdef PBGL_GRAPH_COLORING_DEBUG
- std::cerr << "Vertex " << v << " has a conflict with vertex "
- << w << std::endl;
- #endif
- break;
- }
- }
- }
- #ifdef PBGL_ACCOUNTING
- boman_et_al_graph_coloring_stats.conflicts +=
- conflicting_vertices.size();
- #endif
- }
- if (asynchronous) synchronize(pg);
- else {
- while (rounds > 0) {
- synchronize(pg);
- --rounds;
- }
- }
- conflicting_vertices.swap(vertices_to_color);
- ++outer_iter_num;
- } else {
- if (asynchronous) synchronize(pg);
- else {
- while (rounds > 0) {
- synchronize(pg);
- --rounds;
- }
- }
- }
- // Receive boundary colors from other processors
- while (optional<std::pair<process_id_type, int> > stp = probe(pg)) {
- BOOST_ASSERT(stp->second == 17);
- message_type msg;
- receive(pg, stp->first, stp->second, msg);
- cache(color, msg.first, msg.second);
- }
- rounds = vertices_to_color.size() / s
- + (vertices_to_color.size() % s == 0? 0 : 1);
- rounds = all_reduce(pg, rounds, boost::parallel::maximum<std::size_t>());
- #ifdef PBGL_ACCOUNTING
- ++boman_et_al_graph_coloring_stats.supersteps;
- #endif
- }
- // Determine the number of colors used.
- color_type num_colors = 0;
- BGL_FORALL_VERTICES_T(v, g, DistributedGraph) {
- color_type k = get(color, v);
- BOOST_ASSERT(k != no_color);
- if (k != no_color) {
- if (k >= (color_type)marked.size()) marked.resize(k + 1, 0); // TBD: perf?
- if (marked[k] != iter_num) {
- marked[k] = iter_num;
- ++num_colors;
- }
- }
- }
- num_colors =
- all_reduce(pg, num_colors, boost::parallel::maximum<color_type>());
- #ifdef PBGL_ACCOUNTING
- boman_et_al_graph_coloring_stats.execution_time =
- accounting::get_time() - boman_et_al_graph_coloring_stats.execution_time;
-
- boman_et_al_graph_coloring_stats.conflicts =
- all_reduce(pg, boman_et_al_graph_coloring_stats.conflicts,
- std::plus<color_type>());
- boman_et_al_graph_coloring_stats.num_colors = num_colors;
- #endif
- return num_colors;
- }
- template<typename DistributedGraph, typename ColorMap, typename ChooseColor,
- typename VertexOrdering>
- inline typename property_traits<ColorMap>::value_type
- boman_et_al_graph_coloring
- (const DistributedGraph& g, ColorMap color,
- typename graph_traits<DistributedGraph>::vertices_size_type s,
- ChooseColor choose_color, VertexOrdering ordering)
- {
- return boman_et_al_graph_coloring(g, color, s, choose_color, ordering,
- get(vertex_index, g));
- }
- template<typename DistributedGraph, typename ColorMap, typename ChooseColor>
- inline typename property_traits<ColorMap>::value_type
- boman_et_al_graph_coloring
- (const DistributedGraph& g,
- ColorMap color,
- typename graph_traits<DistributedGraph>::vertices_size_type s,
- ChooseColor choose_color)
- {
- typedef typename graph_traits<DistributedGraph>::vertex_descriptor
- vertex_descriptor;
- return boman_et_al_graph_coloring(g, color, s, choose_color,
- std::less<vertex_descriptor>());
- }
- template<typename DistributedGraph, typename ColorMap>
- inline typename property_traits<ColorMap>::value_type
- boman_et_al_graph_coloring
- (const DistributedGraph& g,
- ColorMap color,
- typename graph_traits<DistributedGraph>::vertices_size_type s = 100)
- {
- typedef typename property_traits<ColorMap>::value_type Color;
- return boman_et_al_graph_coloring(g, color, s, first_fit_color<Color>());
- }
- } } } // end namespace boost::graph::distributed
- namespace boost { namespace graph {
- using distributed::boman_et_al_graph_coloring;
- } } // end namespace boost::graph
- #endif // BOOST_GRAPH_DISTRIBUTED_BOMAN_ET_AL_GRAPH_COLORING_HPP
|