/* Copyright (C) 2010 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: Jeremiah Willcock                                             *//*           Andrew Lumsdaine                                              */ #include "common.h"#include <mpi.h>#include <stdint.h>#include <inttypes.h>#include <stdlib.h>#include <stddef.h>#include <string.h>#include <stdio.h>#include <assert.h> int validate_bfs_result(const csr_graph* const g, const int64_t root, const int64_t* const pred, const int64_t nvisited) {  int validation_passed = 1;  int root_is_mine = (VERTEX_OWNER(root) == rank);   const size_t nlocalverts = g->nlocalverts;  const size_t nlocaledges = g->nlocaledges;  const int64_t nglobalverts = g->nglobalverts;   /* Check that root is its own parent. */  if (root_is_mine) {    if (pred[VERTEX_LOCAL(root)] != root) {      fprintf(stderr, "%d: Validation error: parent of root vertex %" PRId64 " is %" PRId64 ", not the root itself.\n", rank, root, pred[VERTEX_LOCAL(root)]);      validation_passed = 0;    }  }   /* Check that nothing else is its own parent, and check for in-range   * values. */  int any_range_errors = 0;  size_t i;  for (i = 0; i < nlocalverts; ++i) {    int64_t v = VERTEX_TO_GLOBAL(i);    assert (VERTEX_OWNER(v) == rank);    assert (VERTEX_LOCAL(v) == i);    if (v != root && pred[i] == v) {      fprintf(stderr, "%d: Validation error: parent of non-root vertex %" PRId64 " is itself.\n", rank, v);      validation_passed = 0;    }    if (pred[i] < -1 || pred[i] >= nglobalverts) {      fprintf(stderr, "%d: Validation error: parent of vertex %" PRId64 " is out-of-range value %" PRId64 ".\n", rank, v, pred[i]);      validation_passed = 0;      any_range_errors = 1;    }  }  MPI_Allreduce(MPI_IN_PLACE, &any_range_errors, 1, MPI_INT, MPI_LOR, MPI_COMM_WORLD);   /* Check that nvisited is correct. */  int64_t nvisited_actual = 0;  for (i = 0; i < nlocalverts; ++i) {    if (pred[i] != -1) ++nvisited_actual;  }  MPI_Allreduce(MPI_IN_PLACE, &nvisited_actual, 1, INT64_T_MPI_TYPE, MPI_SUM, MPI_COMM_WORLD);  if (nvisited_actual != nvisited) {    fprintf(stderr, "%d: Validation error: claimed visit count %" PRId64 " is different from actual count %" PRId64 ".\n", rank, nvisited, nvisited_actual);    validation_passed = 0;  }   if (!any_range_errors) { /* Other parts of validation assume in-range values */     /* Check that there is an edge from each vertex to its claimed     * predecessor. */    size_t i;    for (i = 0; i < nlocalverts; ++i) {      int64_t v = VERTEX_TO_GLOBAL(i);      int64_t p = pred[i];      if (p == -1) continue;      int found_pred_edge = 0;      if (v == p) found_pred_edge = 1; /* Root vertex */      size_t ei, ei_end = g->rowstarts[i + 1];      for (ei = g->rowstarts[i]; ei < ei_end; ++ei) {        int64_t w = g->column[ei];        if (w == p) {          found_pred_edge = 1;          break;        }      }      if (!found_pred_edge) {        fprintf(stderr, "%d: Validation error: no graph edge from vertex %" PRId64 " to its parent %" PRId64 ".\n", rank, v, p);        validation_passed = 0;      }    }     /* Create a vertex depth map to use for later validation. */    int64_t* depth = (int64_t*)xmalloc(nlocalverts * sizeof(int64_t));    { /* Scope some code that has a lot of temporary variables. */      int64_t* pred_depth = (int64_t*)xmalloc(nlocalverts * sizeof(int64_t)); /* Depth of predecessor vertex for each local vertex */      size_t i;      for (i = 0; i < nlocalverts; ++i) depth[i] = INT64_MAX;      if (root_is_mine) depth[VERTEX_LOCAL(root)] = 0;      /* Send each vertex that appears in the local part of the predecessor map       * to its owner; record the original locations so we can put the answers       * into pred_depth. */      /* Do a histogram sort by owner (this same kind of sort is used other       * places as well).  First, count the number of vertices going to each       * destination. */      int* num_preds_per_owner = (int*)xcalloc(size, sizeof(int)); /* Uses zero-init */      for (i = 0; i < nlocalverts; ++i) {        ++num_preds_per_owner[pred[i] == -1 ? size - 1 : VERTEX_OWNER(pred[i])];      }      int64_t* preds_per_owner = (int64_t*)xmalloc(nlocalverts * sizeof(int64_t)); /* Predecessors sorted by owner */      int64_t* preds_per_owner_results_offsets = (int64_t*)xmalloc(nlocalverts * sizeof(int64_t)); /* Indices into pred_depth to write */      /* Second, do a prefix sum to get the displacements of the different       * owners in the outgoing array. */      int* pred_owner_displs = (int*)xmalloc((size + 1) * sizeof(int));      pred_owner_displs[0] = 0;      int r;      for (r = 0; r < size; ++r) {        pred_owner_displs[r + 1] = pred_owner_displs[r] + num_preds_per_owner[r];      }      /* Last, put the vertices into the correct positions in the array, based       * on their owners and the counts and displacements computed earlier. */      int* pred_owner_offsets = (int*)xmalloc((size + 1) * sizeof(int));      memcpy(pred_owner_offsets, pred_owner_displs, (size + 1) * sizeof(int));      for (i = 0; i < nlocalverts; ++i) {        int* offset_ptr = &pred_owner_offsets[pred[i] == -1 ? size - 1 : VERTEX_OWNER(pred[i])];        preds_per_owner[*offset_ptr] = pred[i];        preds_per_owner_results_offsets[*offset_ptr] = i;        ++*offset_ptr;      }      for (r = 0; r < size; ++r) {        assert (pred_owner_offsets[r] == pred_owner_displs[r + 1]);      }      free(pred_owner_offsets);       /* Send around the number of vertices that will be sent to each destination. */      int* num_my_preds_per_sender = (int*)xmalloc(size * sizeof(int));      MPI_Alltoall(num_preds_per_owner, 1, MPI_INT,                   num_my_preds_per_sender, 1, MPI_INT,                   MPI_COMM_WORLD);      int* my_preds_per_sender_displs = (int*)xmalloc((size + 1) * sizeof(int));      my_preds_per_sender_displs[0] = 0;      for (r = 0; r < size; ++r) {        my_preds_per_sender_displs[r + 1] = my_preds_per_sender_displs[r] + num_my_preds_per_sender[r];      }      /* Send around the actual vertex data (list of depth requests that will       * be responded to at each BFS iteration). */      int64_t* my_depth_requests = (int64_t*)xmalloc(my_preds_per_sender_displs[size] * sizeof(int64_t));      int64_t* my_depth_replies = (int64_t*)xmalloc(my_preds_per_sender_displs[size] * sizeof(int64_t));      MPI_Alltoallv(preds_per_owner, num_preds_per_owner, pred_owner_displs, INT64_T_MPI_TYPE,                    my_depth_requests, num_my_preds_per_sender, my_preds_per_sender_displs, INT64_T_MPI_TYPE,                    MPI_COMM_WORLD);       int64_t* pred_depth_raw = (int64_t*)xmalloc(nlocalverts * sizeof(int64_t)); /* Depth of predecessor vertex for each local vertex, ordered by source proc */       /* Do a mini-BFS (naively) over just the predecessor graph (hopefully a       * tree) produced by the real BFS; fill in the depth map. */      while (1) {        int any_changed = 0;        int i;        /* Create and send the depth values requested by other nodes.  The list         * of requests is sent once, and are stored on the receiver so the         * replies can be sent (possibly with updated depth values) at every         * iteration. */        for (i = 0; i < my_preds_per_sender_displs[size]; ++i) {          my_depth_replies[i] = (my_depth_requests[i] == -1 ? INT64_MAX : depth[VERTEX_LOCAL(my_depth_requests[i])]);        }        MPI_Alltoallv(my_depth_replies, num_my_preds_per_sender, my_preds_per_sender_displs, INT64_T_MPI_TYPE,                      pred_depth_raw, num_preds_per_owner, pred_owner_displs, INT64_T_MPI_TYPE,                      MPI_COMM_WORLD);        {          size_t i;          /* Put the received depths into the local array. */          for (i = 0; i < nlocalverts; ++i) {            pred_depth[preds_per_owner_results_offsets[i]] = pred_depth_raw[i];          }          /* Check those values to determine if they violate any correctness           * conditions. */          for (i = 0; i < nlocalverts; ++i) {            int64_t v = VERTEX_TO_GLOBAL(i);            if (v == root) {              /* The depth and predecessor for this were checked earlier. */            } else if (depth[i] == INT64_MAX && pred_depth[i] == INT64_MAX) {              /* OK -- depth should be filled in later. */            } else if (depth[i] == INT64_MAX && pred_depth[i] != INT64_MAX) {              depth[i] = pred_depth[i] + 1;              any_changed = 1;            } else if (depth[i] != pred_depth[i] + 1) {              fprintf(stderr, "%d: Validation error: BFS predecessors do not form a tree; see vertices %" PRId64 " (depth %" PRId64 ") and %" PRId64 " (depth %" PRId64 ").\n", rank, v, depth[i], pred[i], pred_depth[i]);              validation_passed = 0;            } else {              /* Vertex already has its correct depth value. */            }          }        }        MPI_Allreduce(MPI_IN_PLACE, &any_changed, 1, MPI_INT, MPI_LOR, MPI_COMM_WORLD);        if (!any_changed) break;      }       free(num_preds_per_owner);      free(num_my_preds_per_sender);      free(preds_per_owner);      free(preds_per_owner_results_offsets);      free(my_preds_per_sender_displs);      free(my_depth_requests);      free(my_depth_replies);      free(pred_owner_displs);      free(pred_depth);      free(pred_depth_raw);    }     /* Check that all edges connect vertices whose depths differ by at most     * one. */    {      int64_t maxlocaledges = 0;      MPI_Allreduce((void*)&nlocaledges, &maxlocaledges, 1, INT64_T_MPI_TYPE, MPI_MAX, MPI_COMM_WORLD);      /* We break the total list of overall edges into chunks to reduce the       * amount of data to be sent at a time (since we are using MPI_Alltoallv       * to send data collectively). */      const int edge_chunk_size = (1 << 23); /* Reduce memory usage */      int num_edge_groups = (maxlocaledges + edge_chunk_size - 1) / edge_chunk_size;      int eg;      for (eg = 0; eg < num_edge_groups; ++eg) {        size_t first_edge_index = (size_t)(eg * edge_chunk_size);        if (first_edge_index > nlocaledges) first_edge_index = nlocaledges;        size_t last_edge_index = (size_t)((eg + 1) * edge_chunk_size);        if (last_edge_index > nlocaledges) last_edge_index = nlocaledges;        /* Sort the edge targets in this chunk by their owners (histogram         * sort); see the BFS code above for details of the steps of the         * algorithm. */        int* num_edge_targets_by_owner = (int*)xcalloc(size, sizeof(int)); /* Uses zero-init */        size_t ei;        for (ei = first_edge_index; ei < last_edge_index; ++ei) {          ++num_edge_targets_by_owner[VERTEX_OWNER(g->column[ei])];        }        int* edge_targets_by_owner_displs = (int*)xmalloc((size + 1) * sizeof(int));        edge_targets_by_owner_displs[0] = 0;        int i;        for (i = 0; i < size; ++i) {          edge_targets_by_owner_displs[i + 1] = edge_targets_by_owner_displs[i] + num_edge_targets_by_owner[i];        }        int64_t* edge_targets_by_owner = (int64_t*)xmalloc(edge_targets_by_owner_displs[size] * sizeof(int64_t));        int64_t* edge_targets_by_owner_indices = (int64_t*)xmalloc(edge_targets_by_owner_displs[size] * sizeof(int64_t)); /* Source indices for where to write the targets */        int* edge_targets_by_owner_offsets = (int*)xmalloc((size + 1) * sizeof(int));        memcpy(edge_targets_by_owner_offsets, edge_targets_by_owner_displs, (size + 1) * sizeof(int));        for (ei = first_edge_index; ei < last_edge_index; ++ei) {          edge_targets_by_owner[edge_targets_by_owner_offsets[VERTEX_OWNER(g->column[ei])]] = g->column[ei];          edge_targets_by_owner_indices[edge_targets_by_owner_offsets[VERTEX_OWNER(g->column[ei])]] = ei;          ++edge_targets_by_owner_offsets[VERTEX_OWNER(g->column[ei])];        }        for (i = 0; i < size; ++i) {          assert (edge_targets_by_owner_offsets[i] == edge_targets_by_owner_displs[i + 1]);        }        free(edge_targets_by_owner_offsets);         /* Send around the number of data elements that will be sent later. */        int* num_incoming_targets_by_src = (int*)xmalloc(size * sizeof(int));        MPI_Alltoall(num_edge_targets_by_owner, 1, MPI_INT,                     num_incoming_targets_by_src, 1, MPI_INT,                     MPI_COMM_WORLD);        int* incoming_targets_by_src_displs = (int*)xmalloc((size + 1) * sizeof(int));        incoming_targets_by_src_displs[0] = 0;        for (i = 0; i < size; ++i) {          incoming_targets_by_src_displs[i + 1] = incoming_targets_by_src_displs[i] + num_incoming_targets_by_src[i];        }         int64_t* target_depth_requests = (int64_t*)xmalloc(incoming_targets_by_src_displs[size] * sizeof(int64_t));        int64_t* target_depth_replies = (int64_t*)xmalloc(incoming_targets_by_src_displs[size] * sizeof(int64_t));         /* Send the actual requests for the depths of edge targets. */        MPI_Alltoallv(edge_targets_by_owner, num_edge_targets_by_owner, edge_targets_by_owner_displs, INT64_T_MPI_TYPE,                      target_depth_requests, num_incoming_targets_by_src, incoming_targets_by_src_displs, INT64_T_MPI_TYPE,                      MPI_COMM_WORLD);         free(edge_targets_by_owner);         /* Fill in the replies for the requests sent to me. */        for (i = 0; i < incoming_targets_by_src_displs[size]; ++i) {          assert (VERTEX_OWNER(target_depth_requests[i]) == rank);          target_depth_replies[i] = depth[VERTEX_LOCAL(target_depth_requests[i])];        }         free(target_depth_requests);         int64_t* target_depth_raw = (int64_t*)xmalloc((last_edge_index - first_edge_index) * sizeof(int64_t));         /* Send back the replies. */        MPI_Alltoallv(target_depth_replies, num_incoming_targets_by_src, incoming_targets_by_src_displs, INT64_T_MPI_TYPE,                      target_depth_raw, num_edge_targets_by_owner, edge_targets_by_owner_displs, INT64_T_MPI_TYPE,                      MPI_COMM_WORLD);         free(target_depth_replies);        free(num_incoming_targets_by_src);        free(num_edge_targets_by_owner);        free(incoming_targets_by_src_displs);        free(edge_targets_by_owner_displs);         int64_t* target_depth = (int64_t*)xmalloc((last_edge_index - first_edge_index) * sizeof(int64_t));         /* Put the replies into the proper order (original order of the edges).         * */        for (ei = 0; ei < last_edge_index - first_edge_index; ++ei) {          target_depth[edge_targets_by_owner_indices[ei] - first_edge_index] = target_depth_raw[ei];        }         free(target_depth_raw);        free(edge_targets_by_owner_indices);         /* Check the depth relationship of the endpoints of each edge in the         * current chunk. */        size_t src_i = 0;        for (ei = first_edge_index; ei < last_edge_index; ++ei) {          while (ei >= g->rowstarts[src_i + 1]) {            ++src_i;          }          int64_t src = VERTEX_TO_GLOBAL(src_i);          int64_t src_depth = depth[src_i];          int64_t tgt = g->column[ei];          int64_t tgt_depth = target_depth[ei - first_edge_index];          if (src_depth != INT64_MAX && tgt_depth == INT64_MAX) {            fprintf(stderr, "%d: Validation error: edge connects vertex %" PRId64 " in the BFS tree (depth %" PRId64 ") to vertex %" PRId64 " outside the tree.\n", rank, src, src_depth, tgt);            validation_passed = 0;          } else if (src_depth == INT64_MAX && tgt_depth != INT64_MAX) {            /* Skip this for now; this problem will be caught when scanning             * reversed copy of this edge.  Set the failure flag, though,             * just in case. */            validation_passed = 0;          } else if (src_depth - tgt_depth < -1 ||                     src_depth - tgt_depth > 1) {            fprintf(stderr, "%d: Validation error: depths of edge endpoints %" PRId64 " (depth %" PRId64 ") and %" PRId64 " (depth %" PRId64 ") are too far apart (abs. val. > 1).\n", rank, src, src_depth, tgt, tgt_depth);            validation_passed = 0;          }        }        free(target_depth);      }    }     free(depth);   } /* End of part skipped by range errors */    /* Collect the global validation result. */  MPI_Allreduce(MPI_IN_PLACE, &validation_passed, 1, MPI_INT, MPI_LAND, MPI_COMM_WORLD);  return validation_passed;}