diff options
Diffstat (limited to 'src/boost/libs/graph_parallel/test/ssca.cpp')
| -rw-r--r-- | src/boost/libs/graph_parallel/test/ssca.cpp | 1263 |
1 files changed, 1263 insertions, 0 deletions
diff --git a/src/boost/libs/graph_parallel/test/ssca.cpp b/src/boost/libs/graph_parallel/test/ssca.cpp new file mode 100644 index 00000000..0930e4d0 --- /dev/null +++ b/src/boost/libs/graph_parallel/test/ssca.cpp @@ -0,0 +1,1263 @@ +// Copyright 2004 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: Nick Edmonds +// Andrew Lumsdaine + +#include <boost/graph/use_mpi.hpp> + +#define CSR + +#ifdef CSR +# include <boost/graph/distributed/compressed_sparse_row_graph.hpp> +#else +# include <boost/graph/distributed/adjacency_list.hpp> +#endif + +#include <boost/test/minimal.hpp> +#include <boost/graph/distributed/mpi_process_group.hpp> +#include <boost/graph/distributed/queue.hpp> + +#include <boost/graph/parallel/distribution.hpp> +#include <boost/lexical_cast.hpp> +#include <boost/bind.hpp> +#include <sys/time.h> +#include <time.h> + +#include <boost/random.hpp> +#include <boost/property_map/parallel/distributed_property_map.hpp> + +#include <boost/random/linear_congruential.hpp> + +#include <boost/graph/distributed/graphviz.hpp> +#include <boost/graph/graph_traits.hpp> +#include <boost/graph/iteration_macros.hpp> + +#include <boost/graph/parallel/algorithm.hpp> +#include <boost/graph/breadth_first_search.hpp> +#include <boost/pending/queue.hpp> + +#include <boost/graph/rmat_graph_generator.hpp> +#include <boost/graph/distributed/betweenness_centrality.hpp> +#include <boost/graph/distributed/filtered_graph.hpp> +#include <boost/graph/parallel/container_traits.hpp> + +#include <boost/graph/properties.hpp> + +#include <algorithm> +#include <vector> +#include <string> +#include <iostream> +#include <iomanip> +#include <fstream> +#include <string> +#include <sstream> +#include <stdint.h> + +using namespace boost; + +// #define DEBUG + +typedef rand48 RandomGenerator; + +/**************************************************************************** + * Timing + ****************************************************************************/ +#ifndef PBGL_ACCOUNTING + +typedef double time_type; + +inline time_type get_time() +{ + timeval tp; + gettimeofday(&tp, 0); + return tp.tv_sec + tp.tv_usec / 1000000.0; +} + +std::string print_time(time_type t) +{ + std::ostringstream out; + out << std::setiosflags(std::ios::fixed) << std::setprecision(2) << t; + return out.str(); +} + +#endif // PBGL_ACCOUNTING + +/**************************************************************************** + * Edge weight generator iterator * + ****************************************************************************/ +template<typename F, typename RandomGenerator> +class generator_iterator +{ +public: + typedef std::input_iterator_tag iterator_category; + typedef typename F::result_type value_type; + typedef const value_type& reference; + typedef const value_type* pointer; + typedef void difference_type; + + explicit + generator_iterator(RandomGenerator& gen, const F& f = F()) + : f(f), gen(&gen) + { + value = this->f(gen); + } + + reference operator*() const { return value; } + pointer operator->() const { return &value; } + + generator_iterator& operator++() + { + value = f(*gen); + return *this; + } + + generator_iterator operator++(int) + { + generator_iterator temp(*this); + ++(*this); + return temp; + } + + bool operator==(const generator_iterator& other) const + { return f == other.f; } + + bool operator!=(const generator_iterator& other) const + { return !(*this == other); } + +private: + F f; + RandomGenerator* gen; + value_type value; +}; + +template<typename F, typename RandomGenerator> +inline generator_iterator<F, RandomGenerator> +make_generator_iterator( RandomGenerator& gen, const F& f) +{ return generator_iterator<F, RandomGenerator>(gen, f); } + +template<typename Graph, typename DistanceMap, typename WeightMap, typename ColorMap> +struct ssca_visitor : bfs_visitor<> +{ + typedef typename property_traits<WeightMap>::value_type Weight; + typedef typename property_traits<ColorMap>::value_type ColorValue; + typedef color_traits<ColorValue> Color; + + ssca_visitor(DistanceMap& distance, const WeightMap& weight, ColorMap& color, + Weight max_) + : distance(distance), weight(weight), color(color), max_(max_) {} + + template<typename Edge> + void tree_edge(Edge e, const Graph& g) + { + int new_distance = get(weight, e) == (std::numeric_limits<Weight>::max)() ? + (std::numeric_limits<Weight>::max)() : get(distance, source(e, g)) + get(weight, e); + + put(distance, target(e, g), new_distance); + if (new_distance > max_) + put(color, target(e, g), Color::black()); + } + + private: + DistanceMap& distance; + const WeightMap& weight; + ColorMap& color; + Weight max_; +}; + +// Generate source vertices for approximate BC +template <typename Graph, typename Buffer> +void +generate_sources(const Graph& g, Buffer sources, + typename graph_traits<Graph>::vertices_size_type num_sources) +{ + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + typedef typename graph_traits<Graph>::vertices_size_type vertices_size_type; + typedef typename graph_traits<Graph>::vertex_iterator vertex_iterator; + + typedef typename boost::graph::parallel::process_group_type<Graph>::type + process_group_type; + process_group_type pg = g.process_group(); + + typename process_group_type::process_id_type id = process_id(pg); + typename process_group_type::process_size_type p = num_processes(pg); + + // Don't feel like adding a special case for num_sources < p + assert(num_sources >= p); + + minstd_rand gen; + uniform_int<vertices_size_type> rand_vertex(0, num_vertices(g) - 1); + std::vector<vertex_descriptor> all_sources, local_sources; + vertices_size_type local_vertices = vertices_size_type(floor((double)num_sources / p)); + local_vertices += (id < (num_sources - (p * local_vertices)) ? 1 : 0); + + while (local_vertices > 0) { + vertex_iterator iter = vertices(g).first; + std::advance(iter, rand_vertex(gen)); + + if (out_degree(*iter, g) != 0 + && std::find(local_sources.begin(), local_sources.end(), *iter) == local_sources.end()) { + local_sources.push_back(*iter); + --local_vertices; + } + } + all_gather(pg, local_sources.begin(), local_sources.end(), all_sources); + std::sort(all_sources.begin(), all_sources.end()); + for (typename std::vector<vertex_descriptor>::iterator iter = all_sources.begin(); + iter != all_sources.end(); ++iter) + sources.push(*iter); +} + +// Kernel 2 - Classify large sets +template <typename Graph, typename WeightMap> +void classify_sets(const Graph& g, const WeightMap& weight_map, + std::vector<std::pair<typename graph_traits<Graph>::vertex_descriptor, + typename graph_traits<Graph>::vertex_descriptor> > & global_S) +{ + typedef typename boost::graph::parallel::process_group_type<Graph>::type + process_group_type; + process_group_type pg = g.process_group(); + + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + std::vector<std::pair<vertex_descriptor, vertex_descriptor> > S; + + time_type start = get_time(); + +#ifdef CSR + typedef typename property_map<Graph, vertex_owner_t>::const_type OwnerMap; + typedef typename property_map<Graph, vertex_local_t>::const_type LocalMap; + OwnerMap owner = get(vertex_owner, g); + LocalMap local = get(vertex_local, g); +#endif + + int max_ = 0; + BGL_FORALL_EDGES_T(e, g, Graph) { +#ifdef CSR + if (get(owner, source(e, g)) == process_id(pg)) { +#endif + int w = get(weight_map, e); + if (w > max_) { + max_ = w; + S.clear(); + } + + if (w >= max_) + S.push_back(std::make_pair(source(e, g), target(e, g))); +#ifdef CSR + } +#endif + } + + int global_max = all_reduce(pg, max_, boost::parallel::maximum<int>()); + if (max_ < global_max) + S.clear(); + + global_S.clear(); + + all_gather(pg, S.begin(), S.end(), global_S); + + // This is probably unnecessary as long as the sets of edges owned by procs is disjoint + std::sort(global_S.begin(), global_S.end()); + std::unique(global_S.begin(), global_S.end()); + + synchronize(pg); + + time_type end = get_time(); + + if (process_id(pg) == 0) { + std::cerr << " Distributed Graph: " << print_time(end - start) << std::endl + << " Max int weight = " << global_max << std::endl; + } +} + +template <typename ProcessGroup, typename Graph, typename WeightMap, + typename EdgeVector> +void seq_classify_sets(const ProcessGroup& pg, const Graph& g, + const WeightMap& weight_map, EdgeVector& S) +{ + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; + typedef typename property_traits<WeightMap>::value_type edge_weight_type; + + time_type start = get_time(); + + edge_weight_type max_ = 0; + BGL_FORALL_EDGES_T(e, g, Graph) { + edge_weight_type w = get(weight_map, e); + if (w > max_) { + max_ = w; + S.clear(); + } + + if (w >= max_) + S.push_back(e); + } + + synchronize(pg); + + time_type end = get_time(); + + if (process_id(pg) == 0) + std::cerr << " Non-Distributed Graph: " << print_time(end - start) << std::endl + << " Max int weight = " << max_ << std::endl; +} + +// Kernel 3 - Graph Extraction +template <typename Graph, typename OwnerMap, typename LocalMap, + typename WeightMap, typename DistanceMap, typename ColorMap, + typename EdgeVector> +void subgraph_extraction(Graph& g, const OwnerMap& owner, const LocalMap& local, + const WeightMap& weight_map, DistanceMap distances, + ColorMap color_map, const EdgeVector& S, + int subGraphEdgeLength) +{ + // Nick: I think turning the vertex black when the maximum distance is + // exceeded will prevent BFS from exploring beyond the subgraph. + // Unfortunately we can't run subgraph extraction in parallel + // because the subgraphs may overlap + + typedef typename property_traits<ColorMap>::value_type ColorValue; + typedef color_traits<ColorValue> Color; + + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + + typedef typename boost::graph::parallel::process_group_type<Graph>::type + process_group_type; + + typedef boost::graph::distributed::distributed_queue<process_group_type, + OwnerMap, queue<vertex_descriptor> > queue_t; + + process_group_type pg = g.process_group(); + typename process_group_type::process_id_type id = process_id(pg); + + queue_t Q(pg, owner); + + EdgeVector sources(S.begin(), S.end()); + +#ifdef DEBUG + std::vector<std::vector<vertex_descriptor> > subgraphs; +#endif + + synchronize(pg); + + typedef typename std::vector<std::pair<vertex_descriptor, vertex_descriptor> >::iterator + source_iterator; + + time_type start = get_time(); + for (source_iterator iter = sources.begin(); iter != sources.end(); ++iter) { + // Reinitialize distance and color maps every BFS + BGL_FORALL_VERTICES_T(v, g, Graph) { + if (get(owner, v) == id) { + local_put(color_map, v, Color::white()); + local_put(distances, v, (std::numeric_limits<int>::max)()); + } + } + + vertex_descriptor u = iter->first, v = iter->second; + + local_put(distances, u, 0); + local_put(distances, v, 0); + + while (!Q.empty()) Q.pop(); + if (get(owner, u) == id) + Q.push(u); + + local_put(color_map, u, Color::gray()); + + breadth_first_search(g, v, Q, + ssca_visitor<Graph, DistanceMap, WeightMap, ColorMap> + (distances, weight_map, color_map, subGraphEdgeLength), + color_map); + + // At this point all vertices with distance > 0 in addition to the + // starting vertices compose the subgraph. +#ifdef DEBUG + subgraphs.push_back(std::vector<vertex_descriptor>()); + std::vector<vertex_descriptor>& subgraph = subgraphs.back(); + + BGL_FORALL_VERTICES_T(v, g, Graph) { + if (get(distances, v) < (std::numeric_limits<int>::max)()) + subgraph.push_back(v); + } +#endif + } + + synchronize(pg); + + time_type end = get_time(); + +#ifdef DEBUG + for (unsigned int i = 0; i < subgraphs.size(); i++) { + all_gather(pg, subgraphs[i].begin(), subgraphs[i].end(), subgraphs[i]); + std::sort(subgraphs[i].begin(), subgraphs[i].end()); + subgraphs[i].erase(std::unique(subgraphs[i].begin(), subgraphs[i].end()), + subgraphs[i].end()); + } + + if (process_id(pg) == 0) + for (int i = 0; abs(i) < subgraphs.size(); i++) { + std::cerr << "Subgraph " << i << " :\n"; + for (int j = 0; abs(j) < subgraphs[i].size(); j++) + std::cerr << " " << get(local, subgraphs[i][j]) << "@" + << get(owner, subgraphs[i][j]) << std::endl; + } +#endif + + if (process_id(pg) == 0) + std::cerr << " Distributed Graph: " << print_time(end - start) << std::endl; +} + +template <typename ProcessGroup, typename Graph, typename WeightMap, + typename DistanceMap, typename ColorMap, typename EdgeVector> +void seq_subgraph_extraction(const ProcessGroup& pg, const Graph& g, + const WeightMap& weight_map, DistanceMap distances, + ColorMap color_map, const EdgeVector& S, + int subGraphEdgeLength) +{ + // Nick: I think turning the vertex black when the maximum distance is + // exceeded will prevent BFS from exploring beyond the subgraph. + + using boost::graph::distributed::mpi_process_group; + + typedef typename property_traits<ColorMap>::value_type ColorValue; + typedef color_traits<ColorValue> Color; + + typedef typename graph_traits<Graph>::edge_descriptor edge_descriptor; + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + + boost::queue<vertex_descriptor> Q; + + std::vector<edge_descriptor> sources(S.begin(), S.end()); + +#ifdef DEBUG + std::vector<std::vector<vertex_descriptor> > subgraphs; +#endif + + synchronize(pg); + + typedef ProcessGroup process_group_type; + + typename process_group_type::process_id_type id = process_id(pg); + typename process_group_type::process_size_type p = num_processes(pg); + + time_type start = get_time(); + + for (int i = id; i < sources.size(); i += p) { + + // Reinitialize distance and color maps every BFS + BGL_FORALL_VERTICES_T(v, g, Graph) { + put(color_map, v, Color::white()); + put(distances, v, (std::numeric_limits<int>::max)()); + } + + vertex_descriptor u = source(sources[i], g), + v = target(sources[i], g); + + put(distances, u, 0); + put(distances, v, 0); + + while (!Q.empty()) Q.pop(); + Q.push(u); + + put(color_map, u, Color::gray()); + + breadth_first_search(g, v, Q, + ssca_visitor<Graph, DistanceMap, WeightMap, ColorMap> + (distances, weight_map, color_map, subGraphEdgeLength), + color_map); + +#ifdef DEBUG + subgraphs.push_back(std::vector<vertex_descriptor>()); + std::vector<vertex_descriptor>& subgraph = subgraphs.back(); + + BGL_FORALL_VERTICES_T(v, g, Graph) { + if (get(distances, v) < (std::numeric_limits<int>::max)()) + subgraph.push_back(v); + } +#endif + } + + synchronize(pg); + + time_type end = get_time(); + +#ifdef DEBUG + std::vector<vertex_descriptor> ser_subgraphs; + + for (int i = 0; i < subgraphs.size(); ++i) { + for (int j = 0; j < subgraphs[i].size(); ++j) + ser_subgraphs.push_back(subgraphs[i][j]); + ser_subgraphs.push_back(graph_traits<Graph>::null_vertex()); + } + + all_gather(pg, ser_subgraphs.begin(), ser_subgraphs.end(), ser_subgraphs); + + int i = 0; + typename std::vector<vertex_descriptor>::iterator iter(ser_subgraphs.begin()); + + while (iter != ser_subgraphs.end()) { + std::cerr << "Subgraph " << i << " :\n"; + while (*iter != graph_traits<Graph>::null_vertex()) { + std::cerr << " " << *iter << std::endl; + ++iter; + } + ++i; + ++iter; + } +#endif + + if (process_id(pg) == 0) + std::cerr << " Non-Distributed Graph: " << print_time(end - start) << std::endl; +} + +template <typename ProcessGroup, typename Graph, typename CentralityMap> +void +extract_max_bc_vertices(const ProcessGroup& pg, const Graph& g, const CentralityMap& centrality, + std::vector<typename graph_traits<Graph>::vertex_descriptor>& max_bc_vec) +{ + using boost::graph::parallel::process_group; + using boost::parallel::all_gather; + using boost::parallel::all_reduce; + + // Find set of vertices with highest BC score + typedef typename property_traits<CentralityMap>::value_type centrality_type; + std::vector<centrality_type> max_bc_vertices; + centrality_type max_ = 0; + + max_bc_vec.clear(); + + BGL_FORALL_VERTICES_T(v, g, Graph) { + if (get(centrality, v) == max_) + max_bc_vec.push_back(v); + else if (get(centrality, v) > max_) { + max_ = get(centrality, v); + max_bc_vec.clear(); + max_bc_vec.push_back(v); + } + } + + centrality_type global_max = all_reduce(pg, max_, boost::parallel::minimum<int>()); + + if (global_max > max_) + max_bc_vec.clear(); + + all_gather(pg, max_bc_vec.begin(), max_bc_vec.end(), max_bc_vec); +} + + +// Function object to filter edges divisible by 8 +// EdgeWeightMap::value_type must be integral! +template <typename EdgeWeightMap> +struct edge_weight_not_divisible_by_eight { + typedef typename property_traits<EdgeWeightMap>::value_type weight_type; + + edge_weight_not_divisible_by_eight() { } + edge_weight_not_divisible_by_eight(EdgeWeightMap weight) : m_weight(weight) { } + template <typename Edge> + bool operator()(const Edge& e) const { + return (get(m_weight, e) & ((std::numeric_limits<weight_type>::max)() - 7)) != get(m_weight, e); + } + + EdgeWeightMap m_weight; +}; + +// +// Vertex and Edge properties +// +#ifdef CSR +typedef int weight_type; + +struct WeightedEdge { + WeightedEdge(weight_type weight = 0) : weight(weight) { } + + weight_type weight; +}; + +struct VertexProperties { + VertexProperties(int distance = 0, default_color_type color = white_color) + : distance(distance), color(color) { } + + int distance; + default_color_type color; +}; +#endif + +template <typename RandomGenerator, typename ProcessGroup, typename vertices_size_type, + typename edges_size_type> +void +run_non_distributed_graph_tests(RandomGenerator& gen, const ProcessGroup& pg, + vertices_size_type n, edges_size_type m, + std::size_t maxEdgeWeight, uint64_t seed, + int K4Alpha, double a, double b, double c, double d, + int subGraphEdgeLength, bool show_degree_dist, + bool full_bc, bool verify) +{ +#ifdef CSR + typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge> + seqGraph; +#else + typedef adjacency_list<vecS, vecS, directedS, + // Vertex properties + property<vertex_distance_t, int, + property<vertex_color_t, default_color_type> >, + // Edge properties + property<edge_weight_t, int> > seqGraph; +#endif + + // Generate sequential graph for non_distributed betweenness centrality + // Reseed the PRNG to get the same graph + gen.seed(seed); + + synchronize(pg); + + time_type start = get_time(); + +#ifdef CSR + seqGraph sg(edges_are_sorted, + sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, n, m, a, b, c, d), + sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)), + n); +#else + seqGraph sg(unique_rmat_iterator<RandomGenerator, seqGraph>(gen, n, m, a, b, c, d), + unique_rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)), + n); +#endif + + // Not strictly necessary to synchronize here, but it make sure that the + // time we measure is the time needed for all copies of the graph to be + // constructed + synchronize(pg); + + time_type end = get_time(); + + if (process_id(pg) == 0) + std::cerr<< "Kernel 1:\n" + << " Non-Distributed Graph: " << print_time(end - start) << std::endl; + + std::map<int, int> degree_dist; + if ( show_degree_dist ) { + BGL_FORALL_VERTICES_T(v, sg, seqGraph) { + degree_dist[out_degree(v, sg)]++; + } + + std::cerr << "Degree - Fraction of vertices of that degree\n"; + for (std::map<int, int>::iterator iter = degree_dist.begin(); + iter != degree_dist.end(); ++iter) + std::cerr << " " << iter->first << " - " << double(iter->second) / num_vertices(sg) << std::endl << std::endl; + } + + // + // Kernel 2 - Classify large sets + // + std::vector<graph_traits<seqGraph>::edge_descriptor> seqS; + + if (process_id(pg) == 0) + std::cerr << "Kernel 2:\n"; + + seq_classify_sets(pg, sg, +#ifdef CSR + get(&WeightedEdge::weight, sg), +#else + get(edge_weight, sg), +#endif + seqS); + + // + // Kernel 3 - Graph Extraction + // +#ifdef CSR + typedef weight_type weight_t; + weight_t unit_weight(1); +#else + int unit_weight(1);; +#endif + + if (process_id(pg) == 0) + std::cerr << "Kernel 3:\n"; + + seq_subgraph_extraction(pg, sg, +#ifdef CSR +// get(&WeightedEdge::weight, sg), + ref_property_map<graph_traits<seqGraph>::edge_descriptor, weight_t>(unit_weight), + get(&VertexProperties::distance, sg), + get(&VertexProperties::color, sg), +#else +// get(edge_weight, sg), + ref_property_map<graph_traits<seqGraph>::edge_descriptor, int>(unit_weight), + get(vertex_distance, sg), + get(vertex_color, sg), +#endif + seqS, subGraphEdgeLength); + +#ifdef CSR + typedef property_map<seqGraph, weight_type WeightedEdge::*>::type seqEdgeWeightMap; + edge_weight_not_divisible_by_eight<seqEdgeWeightMap> sg_filter(get(&WeightedEdge::weight, sg)); +#else + typedef property_map<seqGraph, edge_weight_t>::type seqEdgeWeightMap; + edge_weight_not_divisible_by_eight<seqEdgeWeightMap> sg_filter(get(edge_weight, sg)); +#endif + + typedef filtered_graph<const seqGraph, edge_weight_not_divisible_by_eight<seqEdgeWeightMap> > + filteredSeqGraph; + + filteredSeqGraph fsg(sg, sg_filter); + + std::vector<graph_traits<seqGraph>::vertex_descriptor> max_seq_bc_vec; + + // Non-Distributed Centrality Map + typedef property_map<seqGraph, vertex_index_t>::const_type seqIndexMap; + typedef iterator_property_map<std::vector<int>::iterator, seqIndexMap> seqCentralityMap; + + std::vector<int> non_distributed_centralityS(num_vertices(sg), 0); + seqCentralityMap non_distributed_centrality(non_distributed_centralityS.begin(), + get(vertex_index, sg)); + + vertices_size_type n0 = 0; + BGL_FORALL_VERTICES_T(v, fsg, filteredSeqGraph) { + if (out_degree(v, fsg) == 0) ++n0; + } + + if (process_id(pg) == 0) + std::cerr << "Kernel 4:\n"; + + // Run Betweenness Centrality + if (full_bc) { + + // Non-Distributed Graph BC + start = get_time(); + non_distributed_brandes_betweenness_centrality(pg, fsg, non_distributed_centrality); + extract_max_bc_vertices(pg, fsg, non_distributed_centrality, max_seq_bc_vec); + end = get_time(); + + edges_size_type nonDistributedExactTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start))); + + if (process_id(pg) == 0) + std::cerr << " non-Distributed Graph Exact = " << print_time(end - start) << " (" + << nonDistributedExactTEPs << " TEPs)\n"; + } + + // Non-Distributed Graph Approximate BC + std::vector<int> nonDistributedApproxCentralityS(num_vertices(sg), 0); + seqCentralityMap nonDistributedApproxCentrality(nonDistributedApproxCentralityS.begin(), + get(vertex_index, sg)); + + queue<typename graph_traits<filteredSeqGraph>::vertex_descriptor> sources; + { + minstd_rand gen; + uniform_int<vertices_size_type> rand_vertex(0, num_vertices(fsg) - 1); + int remaining_sources = floor(pow(2, K4Alpha)); + std::vector<typename graph_traits<filteredSeqGraph>::vertex_descriptor> temp_sources; + + while (remaining_sources > 0) { + typename graph_traits<filteredSeqGraph>::vertex_descriptor v = + vertex(rand_vertex(gen), fsg); + + if (out_degree(v, fsg) != 0 + && std::find(temp_sources.begin(), temp_sources.end(), v) == temp_sources.end()) { + temp_sources.push_back(v); + --remaining_sources; + } + } + + for (int i = 0; i < temp_sources.size(); ++i) + sources.push(temp_sources[i]); + } + + start = get_time(); + non_distributed_brandes_betweenness_centrality(pg, fsg, buffer(sources). + centrality_map(nonDistributedApproxCentrality)); + extract_max_bc_vertices(pg, fsg, nonDistributedApproxCentrality, max_seq_bc_vec); + end = get_time(); + + edges_size_type nonDistributedApproxTEPs = edges_size_type(floor(7 * n * pow(2, K4Alpha) / (end - start))); + + if (process_id(pg) == 0) + std::cerr << " Non-Distributed Graph Approximate (" << floor(pow(2, K4Alpha)) << " sources) = " + << print_time(end - start) << " (" << nonDistributedApproxTEPs << " TEPs)\n"; + + // Verify Correctness of Kernel 4 + if (full_bc && verify && process_id(pg) == 0) { + + std::vector<int> seq_centralityS(num_vertices(fsg), 0); + seqCentralityMap seq_centrality(seq_centralityS.begin(), get(vertex_index, fsg)); + + max_seq_bc_vec.clear(); + property_traits<seqCentralityMap>::value_type max_ = 0; + + start = get_time(); + brandes_betweenness_centrality(fsg, seq_centrality); + + typedef filtered_graph<const seqGraph, edge_weight_not_divisible_by_eight<seqEdgeWeightMap> > + filteredSeqGraph; + + BGL_FORALL_VERTICES_T(v, fsg, filteredSeqGraph ) { + if (get(seq_centrality, v) == max_) + max_seq_bc_vec.push_back(v); + else if (get(seq_centrality, v) > max_) { + max_ = get(seq_centrality, v); + max_seq_bc_vec.clear(); + max_seq_bc_vec.push_back(v); + } + } + + end = get_time(); + + edges_size_type sequentialTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start))); + + std::cerr << " Sequential = " << print_time(end - start) << " (" << sequentialTEPs << " TEPs)\n"; + + typename ProcessGroup::process_id_type id = process_id(pg); + typename ProcessGroup::process_size_type p = num_processes(pg); + + assert((double)n/p == floor((double)n/p)); + + std::cerr << "\nVerifying non-scalable betweenness centrality...\n"; + + { + bool passed = true; + + // Verify non-scalable betweenness centrality + BGL_FORALL_VERTICES_T(v, sg, seqGraph) { + if (get(non_distributed_centrality, v) != get(seq_centrality, v)) { + std::cerr << " " << id << ": Error - centrality of " << v + << " does not match the sequential result (" + << get(non_distributed_centrality, v) << " vs. " + << get(seq_centrality, v) << ")\n"; + passed = false; + } + } + + if (passed) + std::cerr << " PASSED\n"; + } + + } + +} + +template <typename RandomGenerator, typename ProcessGroup, typename vertices_size_type, + typename edges_size_type> +void +run_distributed_graph_tests(RandomGenerator& gen, const ProcessGroup& pg, + vertices_size_type n, edges_size_type m, + std::size_t maxEdgeWeight, uint64_t seed, + int K4Alpha, double a, double b, double c, double d, + int subGraphEdgeLength, bool show_degree_dist, + bool emit_dot_file, bool full_bc, bool verify) +{ +#ifdef CSR + typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge, no_property, + distributedS<ProcessGroup> > Graph; +#else + typedef adjacency_list<vecS, + distributedS<ProcessGroup, vecS>, + directedS, + // Vertex properties + property<vertex_distance_t, int, + property<vertex_color_t, default_color_type> >, + // Edge properties + property<edge_weight_t, int> > Graph; +#endif + + gen.seed(seed); + + parallel::variant_distribution<ProcessGroup> distrib + = parallel::block(pg, n); + + typedef typename ProcessGroup::process_id_type process_id_type; + process_id_type id = process_id(pg); + + typedef typename property_map<Graph, vertex_owner_t>::const_type OwnerMap; + typedef typename property_map<Graph, vertex_local_t>::const_type LocalMap; + + typedef keep_local_edges<parallel::variant_distribution<ProcessGroup>, + process_id_type> + EdgeFilter; + + // + // Kernel 1 - Graph construction + // Nick: The benchmark specifies that we only have to time graph generation from + // edge tuples, the generator generates the edge tuples at graph construction + // time so we're timing some overhead in the random number generator, etc. + synchronize(pg); + + time_type start = get_time(); + +#ifdef CSR +// typedef sorted_unique_rmat_iterator<RandomGenerator, Graph, EdgeFilter> RMATIter; + typedef sorted_rmat_iterator<RandomGenerator, Graph, keep_all_edges> RMATIter; + + Graph g(//RMATIter(gen, n, m, a, b, c, d, false, true, EdgeFilter(distrib, id)), + RMATIter(gen, n, m, a, b, c, d, true, keep_all_edges()), + RMATIter(), + make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)), + n, pg, distrib); +#else + typedef unique_rmat_iterator<RandomGenerator, Graph, EdgeFilter> RMATIter; + Graph g(RMATIter(gen, n, m, a, b, c, d, true EdgeFilter(distrib, id)), + RMATIter(), + make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)), + n, pg, distrib); +#endif + + synchronize(pg); + + time_type end = get_time(); + + if (id == 0) + std::cerr<< "Kernel 1:\n" + << " Distributed Graph: " << print_time(end - start) << std::endl; + + if ( emit_dot_file ) + write_graphviz("ssca.dot", g); + + // + // Kernel 2 - Classify large sets + // + typedef typename graph_traits<Graph>::vertex_descriptor vertex_descriptor; + std::vector<std::pair<vertex_descriptor, vertex_descriptor> > S; + + if (id == 0) + std::cerr << "Kernel 2:\n"; + + classify_sets(g, +#ifdef CSR + get(&WeightedEdge::weight, g), +#else + get(edge_weight, g), +#endif + S); + + // + // Kernel 3 - Graph Extraction + // + OwnerMap owner = get(vertex_owner, g); + LocalMap local = get(vertex_local, g); + + if (id == 0) + std::cerr << "Kernel 3:\n"; + +#ifdef CSR + typedef weight_type weight_t; + weight_t unit_weight(1); +#else + int unit_weight(1);; +#endif + + subgraph_extraction(g, owner, local, +#ifdef CSR +// get(&WeightedEdge::weight, g), + ref_property_map<typename graph_traits<Graph>::edge_descriptor, weight_t>(unit_weight), + get(&VertexProperties::distance, g), + get(&VertexProperties::color, g), +#else +// get(edge_weight, g), + ref_property_map<graph_traits<Graph>::edge_descriptor, int>(unit_weight), + get(vertex_distance, g), + get(vertex_color, g), +#endif + S, subGraphEdgeLength); + + // + // Kernel 4 - Betweenness Centrality + // + + // Filter edges with weights divisible by 8 +#ifdef CSR + typedef typename property_map<Graph, weight_type WeightedEdge::*>::type EdgeWeightMap; + edge_weight_not_divisible_by_eight<EdgeWeightMap> filter(get(&WeightedEdge::weight, g)); +#else + typedef typename property_map<Graph, edge_weight_t>::type EdgeWeightMap; + edge_weight_not_divisible_by_eight<EdgeWeightMap> filter(get(edge_weight, g)); +#endif + + typedef filtered_graph<const Graph, edge_weight_not_divisible_by_eight<EdgeWeightMap> > + filteredGraph; + filteredGraph fg(g, filter); + + // Vectors of max BC scores for all tests + std::vector<typename graph_traits<Graph>::vertex_descriptor> max_bc_vec; + + // Distributed Centrality Map + typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap; + typedef iterator_property_map<std::vector<int>::iterator, IndexMap> CentralityMap; + + std::vector<int> centralityS(num_vertices(g), 0); + CentralityMap centrality(centralityS.begin(), get(vertex_index, g)); + + // Calculate number of vertices of degree 0 + vertices_size_type local_n0 = 0, n0; + BGL_FORALL_VERTICES_T(v, fg, filteredGraph) { + if (out_degree(v, g) == 0) local_n0++; + } + n0 = boost::parallel::all_reduce(pg, local_n0, std::plus<vertices_size_type>()); + + if (id == 0) + std::cerr << "Kernel 4:\n"; + + // Run Betweenness Centrality + if (full_bc) { + + // Distributed Graph Full BC + start = get_time(); + brandes_betweenness_centrality(fg, centrality); + extract_max_bc_vertices(pg, g, centrality, max_bc_vec); + end = get_time(); + + edges_size_type exactTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start))); + + if (id == 0) + std::cerr << " Exact = " << print_time(end - start) << " (" + << exactTEPs << " TEPs)\n"; + } + + // Distributed Graph Approximate BC + std::vector<int> approxCentralityS(num_vertices(g), 0); + CentralityMap approxCentrality(approxCentralityS.begin(), get(vertex_index, g)); + + queue<vertex_descriptor> sources; + generate_sources(g, sources, vertices_size_type(floor(pow(2, K4Alpha)))); + + start = get_time(); + brandes_betweenness_centrality(fg, buffer(sources).centrality_map(approxCentrality)); + extract_max_bc_vertices(pg, fg, approxCentrality, max_bc_vec); + end = get_time(); + + edges_size_type approxTEPs = edges_size_type(floor(7 * n * pow(2, K4Alpha) / (end - start))); + + if (id == 0) + std::cerr << " Approximate (" << floor(pow(2, K4Alpha)) << " sources) = " + << print_time(end - start) << " (" << approxTEPs << " TEPs)\n"; + + + // Verify Correctness of Kernel 4 + if (full_bc && verify && id == 0) { + + // Build non-distributed graph to verify against + typedef adjacency_list<vecS, vecS, directedS, + // Vertex properties + property<vertex_distance_t, int, + property<vertex_color_t, default_color_type> >, + // Edge properties + property<edge_weight_t, int> > seqGraph; + + gen.seed(seed); + +#ifdef CSR + seqGraph sg(sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(gen, n, m, a, b, c, d), + sorted_unique_rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)), + n); +#else + seqGraph sg(unique_rmat_iterator<RandomGenerator, seqGraph>(gen, n, m, a, b, c, d), + unique_rmat_iterator<RandomGenerator, seqGraph>(), + make_generator_iterator(gen, uniform_int<int>(0, maxEdgeWeight)), + n); +#endif + + typedef property_map<seqGraph, edge_weight_t>::type seqEdgeWeightMap; + edge_weight_not_divisible_by_eight<seqEdgeWeightMap> sg_filter(get(edge_weight, sg)); + + filtered_graph<const seqGraph, edge_weight_not_divisible_by_eight<seqEdgeWeightMap> > + fsg(sg, sg_filter); + + // Build sequential centrality map + typedef property_map<seqGraph, vertex_index_t>::const_type seqIndexMap; + typedef iterator_property_map<std::vector<int>::iterator, seqIndexMap> seqCentralityMap; + + std::vector<int> seq_centralityS(num_vertices(sg), 0); + seqCentralityMap seq_centrality(seq_centralityS.begin(), get(vertex_index, sg)); + + std::vector<graph_traits<seqGraph>::vertex_descriptor> max_seq_bc_vec; + + max_seq_bc_vec.clear(); + property_traits<seqCentralityMap>::value_type max_ = 0; + + start = get_time(); + brandes_betweenness_centrality(fsg, seq_centrality); + + typedef filtered_graph<const seqGraph, edge_weight_not_divisible_by_eight<seqEdgeWeightMap> > + filteredSeqGraph; + + BGL_FORALL_VERTICES_T(v, fsg, filteredSeqGraph ) { + if (get(seq_centrality, v) == max_) + max_seq_bc_vec.push_back(v); + else if (get(seq_centrality, v) > max_) { + max_ = get(seq_centrality, v); + max_seq_bc_vec.clear(); + max_seq_bc_vec.push_back(v); + } + } + + end = get_time(); + + edges_size_type sequentialTEPs = edges_size_type(floor(7 * n* (n - n0) / (end - start))); + + std::cerr << " Sequential = " << print_time(end - start) << " (" << sequentialTEPs << " TEPs)\n"; + + typename ProcessGroup::process_size_type p = num_processes(pg); + + assert((double)n/p == floor((double)n/p)); + + std::cerr << "\nVerifying betweenness centrality...\n"; + + { + bool passed = true; + + // Verify exact betweenness centrality + BGL_FORALL_VERTICES_T(v, g, Graph) { + if (get(centrality, v) != seq_centralityS[(n/p) * get(owner, v) + get(local, v)]) { + std::cerr << " " << id << ": Error - centrality of " << get(local, v) << "@" << get(owner, v) + << " does not match the sequential result (" << get(centrality, v) << " vs. " + << seq_centralityS[(n/p) * get(owner, v) + get(local, v)] << ")\n"; + passed = false; + } + } + + if (passed) + std::cerr << " PASSED\n"; + } + } +} + +void usage() +{ + std::cerr << "SSCA benchmark.\n\n" + << "Usage : ssca [options]\n\n" + << "Options are:\n" + << "\t--vertices v\t\t\tNumber of vertices in the graph\n" + << "\t--edges v\t\t\tNumber of edges in the graph\n" + << "\t--seed s\t\t\tSeed for synchronized random number generator\n" + << "\t--full-bc\t\t\tRun full (exact) Betweenness Centrality\n" + << "\t--max-weight miw\t\tMaximum integer edge weight\n" + << "\t--subgraph-edge-length sel\tEdge length of subgraphs to extract in Kernel 3\n" + << "\t--k4alpha k\t\t\tValue of K4Alpha in Kernel 4\n" + << "\t--scale s\t\t\tSCALE parameter for the SSCA benchmark (sets n, m, and C)\n" + << "\t--dot\t\t\t\tEmit a dot file containing the graph\n" + << "\t--verify\t\t\tVerify result\n" + << "\t--degree-dist\t\t\t Output degree distribution of graph\n" + << "\t--no-distributed-graph\t\tOmit distributed graph tests\n"; +} + +int test_main(int argc, char* argv[]) +{ + mpi::environment env(argc, argv); + + using boost::graph::distributed::mpi_process_group; + +#ifdef CSR + typedef compressed_sparse_row_graph<directedS, VertexProperties, WeightedEdge, no_property, + distributedS<mpi_process_group> > Graph; +#else + typedef adjacency_list<vecS, + distributedS<mpi_process_group, vecS>, + directedS, + // Vertex properties + property<vertex_distance_t, int, + property<vertex_color_t, default_color_type> >, + // Edge properties + property<edge_weight_t, int> > Graph; +#endif + + typedef graph_traits<Graph>::vertices_size_type vertices_size_type; + typedef graph_traits<Graph>::edges_size_type edges_size_type; + + RandomGenerator gen; + + // Default args + vertices_size_type n = 100; + edges_size_type m = 8*n; + uint64_t seed = 1; + int maxEdgeWeight = 100, + subGraphEdgeLength = 8, + K4Alpha = 0.5; + double a = 0.57, b = 0.19, c = 0.19, d = 0.05; + bool emit_dot_file = false, verify = false, full_bc = true, + distributed_graph = true, show_degree_dist = false, + non_distributed_graph = true; + + mpi_process_group pg; + + if (argc == 1) { + if (process_id(pg) == 0) + usage(); + exit(-1); + } + + // Parse args + for (int i = 1; i < argc; ++i) { + std::string arg = argv[i]; + + if (arg == "--vertices") + n = boost::lexical_cast<vertices_size_type>( argv[i+1] ); + + if (arg == "--seed") + seed = boost::lexical_cast<uint64_t>( argv[i+1] ); + + if (arg == "--full-bc") + full_bc = (argv[i+1]== "true"); + + if (arg == "--max-weight") + maxEdgeWeight = boost::lexical_cast<int>( argv[i+1] ); + + if (arg == "--subgraph-edge-length") + subGraphEdgeLength = boost::lexical_cast<int>( argv[i+1] ); + + if (arg == "--edges") + m = boost::lexical_cast<edges_size_type>( argv[i+1] ); + + if (arg == "--k4alpha") + K4Alpha = boost::lexical_cast<int>( argv[i+1] ); + + if (arg == "--dot") + emit_dot_file = true; + + if (arg == "--verify") + verify = true; + + if (arg == "--degree-dist") + show_degree_dist = true; + + if (arg == "--no-distributed-graph") + distributed_graph = false; + + if (arg == "--no-non-distributed-graph") + non_distributed_graph = false; + + if (arg == "--scale") { + vertices_size_type scale = boost::lexical_cast<vertices_size_type>( argv[i+1] ); + maxEdgeWeight = n = vertices_size_type(floor(pow(2, scale))); + m = 8 * n; + } + + if (arg == "--help") { + if (process_id(pg) == 0) + usage(); + exit(-1); + } + } + + if (non_distributed_graph) { + if (process_id(pg) == 0) + std::cerr << "Non-Distributed Graph Tests\n"; + + run_non_distributed_graph_tests(gen, pg, n, m, maxEdgeWeight, seed, K4Alpha, a, b, c, d, + subGraphEdgeLength, show_degree_dist, full_bc, verify); + } + + if (distributed_graph) { + if (process_id(pg) == 0) + std::cerr << "Distributed Graph Tests\n"; + + run_distributed_graph_tests(gen, pg, n, m, maxEdgeWeight, seed, K4Alpha, a, b, c, d, + subGraphEdgeLength, show_degree_dist, emit_dot_file, + full_bc, verify); + } + + return 0; +} |