Debian Codegraph @

src/atlas/mesh/detail/PartitionGraph.cc

raw
1 /*
2 * (C) Copyright 2013 ECMWF.
3 *
4 * This software is licensed under the terms of the Apache Licence Version 2.0
5 * which can be obtained at http://www.apache.org/licenses/LICENSE-2.0.
6 * In applying this licence, ECMWF does not waive the privileges and immunities
7 * granted to it by virtue of its status as an intergovernmental organisation
8 * nor does it submit to any jurisdiction.
9 */
10
11 #include <iomanip>
12
13 #include "eckit/log/Bytes.h"
14 #include "eckit/types/FloatCompare.h"
15
16 #include "atlas/mesh/Elements.h"
17 #include "atlas/mesh/HybridElements.h"
18 #include "atlas/mesh/Mesh.h"
19 #include "atlas/mesh/Nodes.h"
20 #include "atlas/mesh/detail/MeshImpl.h"
21 #include "atlas/parallel/mpi/mpi.h"
22 #include "atlas/runtime/Log.h"
23 #include "atlas/util/Unique.h"
24
25 namespace atlas {
26 namespace mesh {
27 namespace detail {
28
29 //----------------------------------------------------------------------------------------------------------------------
30
31 PartitionGraph* build_partition_graph(const MeshImpl& mesh) {
32 ATLAS_TRACE("build_partition_graph...");
33 const auto& comm = mpi::comm(mesh.mpi_comm());
34 const int mpi_size = int(comm.size());
35
36 const util::Polygon& poly = mesh.polygon();
37
38 std::vector<double> polygon;
39 polygon.reserve(poly.size() * 2);
40
41 auto xy = array::make_view<double, 2>(mesh.nodes().xy());
42
43 for (idx_t node : poly) {
44 polygon.push_back(xy(node, XX));
45 polygon.push_back(xy(node, YY));
46 }
47
48 eckit::mpi::Buffer<double> recv_polygons(mpi_size);
49 comm.allGatherv(polygon.begin(), polygon.end(), recv_polygons);
50
51 using PolygonXY = std::vector<PointXY>;
52 std::vector<PolygonXY> polygons(mpi_size);
53 for (idx_t p = 0; p < mpi_size; ++p) {
54 for (idx_t j = 0; j < recv_polygons.counts[p] / 2; ++j) {
55 PointXY pxy(*(recv_polygons.begin() + recv_polygons.displs[p] + 2 * j + XX),
56 *(recv_polygons.begin() + recv_polygons.displs[p] + 2 * j + YY));
57 polygons[p].push_back(pxy);
58 }
59 }
60
61 std::map<uidx_t, std::set<idx_t>> uid_2_parts;
62 idx_t jpart = 0;
63 for (const PolygonXY& _polygon : polygons) {
64 for (const PointXY& pxy : _polygon) {
65 PointLonLat pll = pxy;
66 if (eckit::types::is_strictly_greater(0., pll.lon())) {
67 pll.lon() += 360.;
68 }
69 if (eckit::types::is_approximately_greater_or_equal(pll.lon(), 360.)) {
70 pll.lon() -= 360.;
71 }
72 uidx_t uid = util::unique_lonlat(pll.data());
73 uid_2_parts[uid].insert(jpart);
74 }
75 ++jpart;
76 }
77 std::vector<std::set<idx_t>> graph(mpi_size);
78 for (const auto& u2p : uid_2_parts) {
79 const std::set<idx_t>& parts = u2p.second;
80 for (idx_t jpart : parts) {
81 for (idx_t ipart : parts) {
82 if (jpart != ipart) {
83 graph[jpart].insert(ipart);
84 }
85 }
86 }
87 }
88
89 std::vector<idx_t> counts(mpi_size);
90 std::vector<idx_t> displs(mpi_size);
91 idx_t values_size = 0;
92 for (idx_t jpart = 0; jpart < mpi_size; ++jpart) {
93 counts[jpart] = graph[jpart].size();
94 displs[jpart] = values_size;
95 values_size += counts[jpart];
96 }
97 std::vector<idx_t> values;
98 values.reserve(values_size);
99 for (const std::set<idx_t>& graph_node : graph) {
100 for (idx_t v : graph_node) {
101 values.push_back(v);
102 }
103 }
104
105 return new PartitionGraph(values.data(), mpi_size, displs.data(), counts.data());
106 }
107
108 size_t PartitionGraph::footprint() const {
109 size_t size = sizeof(*this);
110 size += sizeof(idx_t) * displs_.capacity();
111 size += sizeof(idx_t) * counts_.capacity();
112 size += sizeof(idx_t) * values_.capacity();
113 return size;
114 }
115
116 idx_t PartitionGraph::size() const {
117 return displs_.size();
118 }
119
120 PartitionGraph::Neighbours PartitionGraph::nearestNeighbours(const idx_t partition) const {
121 return Neighbours(values_.data() + displs_[partition], values_.data() + displs_[partition] + counts_[partition]);
122 }
123
124 PartitionGraph::PartitionGraph() = default;
125
126 PartitionGraph::PartitionGraph(idx_t values[], idx_t rows, idx_t displs[], idx_t counts[]) {
127 displs_.assign(displs, displs + rows);
128 counts_.assign(counts, counts + rows);
129 values_.assign(values, values + displs[rows - 1] + counts[rows - 1]);
130
131 for (idx_t jpart = 0; jpart < rows; ++jpart) {
132 for (idx_t neighbour : nearestNeighbours(jpart)) {
133 bool found(false);
134 for (idx_t nextneighbour : nearestNeighbours(neighbour)) {
135 if (nextneighbour == jpart) {
136 found = true;
137 }
138 }
139 if (not found) {
140 values_.insert(values_.begin() + displs_[neighbour] + counts_[neighbour], jpart);
141 counts_[neighbour]++;
142 for (idx_t j = neighbour + 1; j < rows; ++j) {
143 displs_[j]++;
144 }
145 }
146 }
147 }
148
149 maximum_nearest_neighbours_ = 0;
150 for (idx_t n : counts_) {
151 maximum_nearest_neighbours_ = std::max(n, maximum_nearest_neighbours_);
152 }
153 }
154
155 idx_t PartitionGraph::maximumNearestNeighbours() const {
156 return maximum_nearest_neighbours_;
157 }
158
159 void PartitionGraph::print(std::ostream& os) const {
160 for (idx_t jpart = 0; jpart < size(); ++jpart) {
161 os << std::setw(3) << jpart << " : ";
162 for (idx_t v : nearestNeighbours(jpart)) {
163 os << std::setw(3) << v << " ";
164 }
165 os << '\n';
166 }
167 os << "partition graph maximum neighbours = " << maximumNearestNeighbours() << '\n';
168 os << "partition graph footprint = " << eckit::Bytes(footprint());
169 }
170
171 PartitionGraph::operator bool() const {
172 return size();
173 }
174
175 std::ostream& operator<<(std::ostream& s, const PartitionGraph& p) {
176 p.print(s);
177 return s;
178 }
179
180 //----------------------------------------------------------------------------------------------------------------------
181
182 } // namespace detail
183 } // namespace mesh
184 } // namespace atlas