Loading [MathJax]/extensions/tex2jax.js
Note: this is documentation for an old release. View the latest documentation at docs.fenicsproject.org/v0.1.0/v0.9.0/cpp
DOLFINx  0.1.0
DOLFINx C++ interface
All Classes Namespaces Functions Variables Typedefs Enumerations Pages
partition.h
1 // Copyright (C) 2020 Garth N. Wells
2 //
3 // This file is part of DOLFINx (https://www.fenicsproject.org)
4 //
5 // SPDX-License-Identifier: LGPL-3.0-or-later
6 
7 #pragma once
8 
9 #include <algorithm>
10 #include <cstdint>
11 #include <dolfinx/common/MPI.h>
12 #include <dolfinx/common/Timer.h>
13 #include <dolfinx/graph/AdjacencyList.h>
14 #include <functional>
15 #include <mpi.h>
16 #include <utility>
17 #include <vector>
18 
19 namespace dolfinx::graph
20 {
21 
33 using partition_fn = std::function<graph::AdjacencyList<std::int32_t>(
34  MPI_Comm comm, int nparts, const AdjacencyList<std::int64_t>& local_graph,
35  std::int32_t num_ghost_nodes, bool ghosting)>;
36 
49 partition_graph(const MPI_Comm comm, int nparts,
50  const AdjacencyList<std::int64_t>& local_graph,
51  std::int32_t num_ghost_nodes, bool ghosting);
52 
56 namespace build
57 {
69 std::tuple<graph::AdjacencyList<std::int64_t>, std::vector<int>,
70  std::vector<std::int64_t>, std::vector<int>>
71 distribute(MPI_Comm comm, const graph::AdjacencyList<std::int64_t>& list,
72  const graph::AdjacencyList<std::int32_t>& destinations);
73 
81 std::vector<std::int64_t>
82 compute_ghost_indices(MPI_Comm comm,
83  const std::vector<std::int64_t>& global_indices,
84  const std::vector<int>& ghost_owners);
85 
95 template <typename T>
96 xt::xtensor<T, 2> distribute_data(MPI_Comm comm,
97  const std::vector<std::int64_t>& indices,
98  const xt::xtensor<T, 2>& x);
99 
111 std::vector<std::int64_t>
114 
123 std::vector<std::int32_t>
124 compute_local_to_local(const std::vector<std::int64_t>& local0_to_global,
125  const std::vector<std::int64_t>& local1_to_global);
126 } // namespace build
127 
128 //---------------------------------------------------------------------------
129 // Implementation
130 //---------------------------------------------------------------------------
131 template <typename T>
132 xt::xtensor<T, 2>
133 build::distribute_data(MPI_Comm comm, const std::vector<std::int64_t>& indices,
134  const xt::xtensor<T, 2>& x)
135 {
136  common::Timer timer("Fetch float data from remote processes");
137 
138  const std::int64_t num_points_local = x.shape(0);
139  const int size = dolfinx::MPI::size(comm);
140  const int rank = dolfinx::MPI::rank(comm);
141  std::vector<std::int64_t> global_sizes(size);
142  MPI_Allgather(&num_points_local, 1, MPI_INT64_T, global_sizes.data(), 1,
143  MPI_INT64_T, comm);
144  std::vector<std::int64_t> global_offsets(size + 1, 0);
145  std::partial_sum(global_sizes.begin(), global_sizes.end(),
146  global_offsets.begin() + 1);
147 
148  // Build index data requests
149  std::vector<int> number_index_send(size, 0);
150  std::vector<int> index_owner(indices.size());
151  std::vector<int> index_order(indices.size());
152  std::iota(index_order.begin(), index_order.end(), 0);
153  std::sort(index_order.begin(), index_order.end(),
154  [&indices](int a, int b) { return (indices[a] < indices[b]); });
155 
156  int p = 0;
157  for (std::size_t i = 0; i < index_order.size(); ++i)
158  {
159  int j = index_order[i];
160  while (indices[j] >= global_offsets[p + 1])
161  ++p;
162  index_owner[j] = p;
163  number_index_send[p]++;
164  }
165 
166  // Compute send displacements
167  std::vector<int> disp_index_send(size + 1, 0);
168  std::partial_sum(number_index_send.begin(), number_index_send.end(),
169  disp_index_send.begin() + 1);
170 
171  // Pack global index send data
172  std::vector<std::int64_t> indices_send(disp_index_send.back());
173  std::vector<int> disp_tmp = disp_index_send;
174  for (std::size_t i = 0; i < indices.size(); ++i)
175  {
176  const int owner = index_owner[i];
177  indices_send[disp_tmp[owner]++] = indices[i];
178  }
179 
180  // Send/receive number of indices to communicate to each process
181  std::vector<int> number_index_recv(size);
182  MPI_Alltoall(number_index_send.data(), 1, MPI_INT, number_index_recv.data(),
183  1, MPI_INT, comm);
184 
185  // Compute receive displacements
186  std::vector<int> disp_index_recv(size + 1, 0);
187  std::partial_sum(number_index_recv.begin(), number_index_recv.end(),
188  disp_index_recv.begin() + 1);
189 
190  // Send/receive global indices
191  std::vector<std::int64_t> indices_recv(disp_index_recv.back());
192  MPI_Alltoallv(indices_send.data(), number_index_send.data(),
193  disp_index_send.data(), MPI_INT64_T, indices_recv.data(),
194  number_index_recv.data(), disp_index_recv.data(), MPI_INT64_T,
195  comm);
196 
197  assert(x.shape(1) != 0);
198  // Pack point data to send back (transpose)
199  xt::xtensor<T, 2> x_return({indices_recv.size(), x.shape(1)});
200  for (int p = 0; p < size; ++p)
201  {
202  for (int i = disp_index_recv[p]; i < disp_index_recv[p + 1]; ++i)
203  {
204  const std::int32_t index_local = indices_recv[i] - global_offsets[rank];
205  assert(index_local >= 0);
206  for (std::size_t j = 0; j < x.shape(1); ++j)
207  x_return(i, j) = x(index_local, j);
208  }
209  }
210 
211  MPI_Datatype compound_type;
212  MPI_Type_contiguous(x.shape(1), dolfinx::MPI::mpi_type<T>(), &compound_type);
213  MPI_Type_commit(&compound_type);
214 
215  // Send back point data
216  xt::xtensor<T, 2> my_x(
217  {static_cast<std::size_t>(disp_index_send.back()), x.shape(1)});
218  MPI_Alltoallv(x_return.data(), number_index_recv.data(),
219  disp_index_recv.data(), compound_type, my_x.data(),
220  number_index_send.data(), disp_index_send.data(), compound_type,
221  comm);
222 
223  return my_x;
224 }
225 
226 } // namespace dolfinx::graph
dolfinx::graph::partition_graph
AdjacencyList< std::int32_t > partition_graph(const MPI_Comm comm, int nparts, const AdjacencyList< std::int64_t > &local_graph, std::int32_t num_ghost_nodes, bool ghosting)
Partition graph across processes using the default graph partitioner.
Definition: partition.cpp:21
dolfinx::graph
Graph data structures and algorithms.
Definition: AdjacencyList.h:18
dolfinx::graph::build::compute_local_to_local
std::vector< std::int32_t > compute_local_to_local(const std::vector< std::int64_t > &local0_to_global, const std::vector< std::int64_t > &local1_to_global)
Compute a local0-to-local1 map from two local-to-global maps with common global indices.
Definition: partition.cpp:313
dolfinx::graph::AdjacencyList
This class provides a static adjacency list data structure. It is commonly used to store directed gra...
Definition: AdjacencyList.h:46
dolfinx::MPI::rank
static int rank(MPI_Comm comm)
Return process rank for the communicator.
Definition: MPI.cpp:77
dolfinx::graph::build::compute_local_to_global_links
std::vector< std::int64_t > compute_local_to_global_links(const graph::AdjacencyList< std::int64_t > &global, const graph::AdjacencyList< std::int32_t > &local)
Given an adjacency list with global, possibly non-contiguous, link indices and a local adjacency list...
Definition: partition.cpp:276
dolfinx::MPI::size
static int size(MPI_Comm comm)
Return size of the group (number of processes) associated with the communicator.
Definition: MPI.cpp:85
dolfinx::graph::partition_fn
std::function< graph::AdjacencyList< std::int32_t >(MPI_Comm comm, int nparts, const AdjacencyList< std::int64_t > &local_graph, std::int32_t num_ghost_nodes, bool ghosting)> partition_fn
Signature of functions for computing the parallel partitioning of a distributed graph.
Definition: partition.h:35
dolfinx::graph::build::distribute_data
xt::xtensor< T, 2 > distribute_data(MPI_Comm comm, const std::vector< std::int64_t > &indices, const xt::xtensor< T, 2 > &x)
Distribute data to process ranks where it it required.
Definition: partition.h:133
dolfinx::graph::build::distribute
std::tuple< graph::AdjacencyList< std::int64_t >, std::vector< int >, std::vector< std::int64_t >, std::vector< int > > distribute(MPI_Comm comm, const graph::AdjacencyList< std::int64_t > &list, const graph::AdjacencyList< std::int32_t > &destinations)
Distribute adjacency list nodes to destination ranks. The global index of each node is assumed to be ...
Definition: partition.cpp:31
dolfinx::common::Timer
A timer can be used for timing tasks. The basic usage is.
Definition: Timer.h:30
dolfinx::graph::build::compute_ghost_indices
std::vector< std::int64_t > compute_ghost_indices(MPI_Comm comm, const std::vector< std::int64_t > &global_indices, const std::vector< int > &ghost_owners)
Compute ghost indices in a global IndexMap space, from a list of arbitrary global indices,...
Definition: partition.cpp:160