// 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
|
