GCC Code Coverage Report

Directory: ../../../builds/dumux-repositories/
File: /builds/dumux-repositories/dumux/dumux/linear/scotchbackend.hh
Date: 2024-09-21 20:52:54
Exec Total Coverage
Lines: 50 55 90.9%
Functions: 6 6 100.0%
Branches: 68 238 28.6%
Line Branch Exec Source
1 // -*- mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 // vi: set et ts=4 sw=4 sts=4:
3 //
4 // SPDX-FileCopyrightInfo: Copyright © DuMux Project contributors, see AUTHORS.md in root folder
5 // SPDX-License-Identifier: GPL-3.0-or-later
6 //
7
8 /*!
9 * \file
10 * \ingroup Linear
11 * \brief An interface to the scotch library for matrix reordering
12 * \note You need to have PTSCOTCH installed to use this feature
13 */
14 #ifndef DUMUX_SCOTCH_BACKEND_HH
15 #define DUMUX_SCOTCH_BACKEND_HH
16
17 #include <string>
18 #include <vector>
19 #include <iostream>
20
21 #include <dune/common/exceptions.hh>
22
23 #if HAVE_PTSCOTCH
24 #if HAVE_MPI
25 #include <mpi.h>
26 #endif
27 extern "C"
28 {
29 #include <stdint.h>
30 #include <ptscotch.h>
31 }
32 #else
33 #warning "PTSCOTCH was not found on your system. Dumux::ScotchBackend won't do anything."
34 #endif
35
36 namespace Dumux {
37
38 #if HAVE_PTSCOTCH
39
40 /*!
41 * \ingroup Linear
42 * \brief A wrapper around a SCOTCH graph object
43 */
44 template<class IndexType = int>
45 class ScotchGraph
46 {
47 public:
48 //! a graph represented by an adjacency list
49 using Graph = std::vector<std::vector<IndexType>>;
50
51 30 ScotchGraph(const Graph& graph)
52 60 {
53 // Number of local graph vertices
54
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 const SCOTCH_Num numNodes = graph.size();
55
56 // Data structures for graph input to SCOTCH
57 // add 1 for case that graph size is zero
58
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 vertTab_.reserve(numNodes + 1);
59
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 edgeTab_.reserve(20*numNodes);
60
61 // Build local graph input for SCOTCH
62 // (number of graph vertices (cells),
63 // number of edges connecting two vertices)
64 30 SCOTCH_Num numEdges = 0;
65
1/2
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
 30 vertTab_.push_back(0);
66
6/6
✓ Branch 0 taken 12866 times.
✓ Branch 1 taken 30 times.
✓ Branch 2 taken 12866 times.
✓ Branch 3 taken 30 times.
✓ Branch 4 taken 12866 times.
✓ Branch 5 taken 30 times.
 38658 for (auto vertex = graph.begin(); vertex != graph.end(); ++vertex)
67 {
68
1/2
✓ Branch 1 taken 12866 times.
✗ Branch 2 not taken.
 12866 numEdges += vertex->size();
69
2/4
✓ Branch 1 taken 12866 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12866 times.
✗ Branch 5 not taken.
 25732 vertTab_.push_back(vertTab_.back() + vertex->size());
70
5/12
✓ Branch 1 taken 12866 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 12866 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 12866 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 12866 times.
✗ Branch 11 not taken.
✓ Branch 13 taken 12866 times.
✗ Branch 14 not taken.
✗ Branch 15 not taken.
✗ Branch 16 not taken.
 64330 edgeTab_.insert(edgeTab_.end(), vertex->begin(), vertex->end());
71 }
72
73 // Shrink vectors to hopefully recover any unused memory
74
1/2
✗ Branch 0 not taken.
✓ Branch 1 taken 30 times.
 30 vertTab_.shrink_to_fit();
75
1/2
✓ Branch 0 taken 30 times.
✗ Branch 1 not taken.
 30 edgeTab_.shrink_to_fit();
76
77
2/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 30 times.
 30 if (SCOTCH_graphInit(&scotchGraph_) != 0)
78 ✗ DUNE_THROW(Dune::Exception, "Error initializing SCOTCH graph!");
79
80 // check graph's consistency (recommended before building)
81
2/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✗ Branch 3 not taken.
✓ Branch 4 taken 30 times.
 30 if (SCOTCH_graphCheck(&scotchGraph_) != 0)
82 ✗ DUNE_THROW(Dune::Exception, "Error within SCOTCH graph's consistency!");
83
84 // build graph
85 30 const SCOTCH_Num baseValue = 0; // C-style array indexing
86
5/10
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 30 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 30 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 30 times.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✓ Branch 13 taken 30 times.
 120 if (SCOTCH_graphBuild(&scotchGraph_, baseValue, numNodes, vertTab_.data(), vertTab_.data()+1, NULL, NULL, numEdges, edgeTab_.data(), NULL))
87 ✗ DUNE_THROW(Dune::Exception, "Error building SCOTCH graph!");
88 30 }
89
90 //! Clean-up the graph
91 30 ~ScotchGraph()
92 {
93 30 SCOTCH_graphExit(&scotchGraph_);
94 60 }
95
96 //! Get the raw point to the data (to pass to C interface)
97 SCOTCH_Graph* data()
98 { return &scotchGraph_; }
99
100 private:
101 SCOTCH_Graph scotchGraph_;
102 // we have to maintain these ourselves to keep the Scotch graph valid
103 std::vector<SCOTCH_Num> vertTab_;
104 std::vector<SCOTCH_Num> edgeTab_;
105 };
106
107 /*!
108 * \ingroup Linear
109 * \brief A wrapper around a SCOTCH strategy object
110 */
111 class ScotchGraphOrderStrategy
112 {
113 public:
114 26 ScotchGraphOrderStrategy(const std::string& strategy = "")
115 26 {
116
1/2
✗ Branch 1 not taken.
✓ Branch 2 taken 26 times.
 26 if (SCOTCH_stratInit(&strategy_) != 0)
117 ✗ DUNE_THROW(Dune::Exception, "Error initializing SCOTCH strategy!");
118
119 // Set SCOTCH strategy (if provided)
120
2/4
✓ Branch 0 taken 26 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
 52 if (!strategy.empty())
121 52 SCOTCH_stratGraphOrder(&strategy_, strategy.c_str());
122 26 }
123
124 //! Clean-up the strategy
125 ~ScotchGraphOrderStrategy()
126 26 {
127 26 SCOTCH_stratExit(&strategy_);
128 }
129
130 //! Get the raw point to the data (to pass to C interface)
131 SCOTCH_Strat* data()
132 26 { return &strategy_; }
133
134 private:
135 SCOTCH_Strat strategy_;
136 };
137
138 #endif // HAVE_PTSCOTCH
139
140 /*!
141 * \ingroup Linear
142 * \brief A reordering backend using the scotch library
143 * \note You need to have PTSCOTCH installed to use this feature
144 */
145 template<class IndexType>
146 class ScotchBackend
147 {
148 public:
149 //! the graph type
150 using Graph = std::vector<std::vector<IndexType>>;
151
152 //! Compute reordering (map[old] -> new) using
153 //! Gibbs-Poole-Stockmeyer (GPS) re-ordering
154 26 static std::vector<int> computeGPSReordering(const Graph& graph,
155 std::size_t numPasses = 5)
156 {
157 // Create strategy string for Gibbs-Poole-Stockmeyer ordering
158
3/10
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 26 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✓ Branch 8 taken 26 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
 52 std::string strategy = "g{pass= " + std::to_string(numPasses) + "}";
159
4/12
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 26 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 26 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 26 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 26 return computeReordering(graph, strategy);
160 }
161
162 //! Compute graph re-ordering
163 26 static std::vector<int> computeReordering(const Graph& graph,
164 std::string scotchStrategy = "")
165 {
166
2/6
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 26 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
 52 std::vector<int> permutation, inversePermutation;
167
4/12
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 26 times.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 26 times.
✓ Branch 8 taken 26 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 26 computeReordering(graph, permutation, inversePermutation, scotchStrategy);
168 26 return permutation;
169 }
170
171 //! Compute graph re-ordering
172 26 static void computeReordering(const Graph& graph,
173 std::vector<int>& permutation,
174 std::vector<int>& inversePermutation,
175 std::string scotchStrategy = "")
176 {
177 #if HAVE_PTSCOTCH
178 26 ScotchGraph<IndexType> scotchGraph(graph);
179
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 52 ScotchGraphOrderStrategy strategy(scotchStrategy);
180
181 // Vector to hold permutation vectors
182
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 const auto graphSize = graph.size();
183
2/4
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 26 times.
✗ Branch 5 not taken.
 78 std::vector<SCOTCH_Num> permutationIndices(graphSize);
184
3/10
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 26 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 26 times.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 78 std::vector<SCOTCH_Num> inversePermutationIndices(graphSize);
185
186 // Reset SCOTCH random number generator to produce deterministic partitions
187
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 SCOTCH_randomReset();
188
189 // Compute re-ordering
190
4/8
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 26 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 26 times.
✗ Branch 8 not taken.
✗ Branch 9 not taken.
✓ Branch 10 taken 26 times.
 78 if (SCOTCH_graphOrder(
191 scotchGraph.data(), strategy.data(), permutationIndices.data(),
192 inversePermutationIndices.data(), NULL, NULL, NULL
193 ))
194 ✗ DUNE_THROW(Dune::Exception, "Error reordering SCOTCH graph!");
195
196 // Copy permutation vectors
197
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 permutation.resize(graphSize);
198
1/2
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
 26 inversePermutation.resize(graphSize);
199
4/8
✓ Branch 0 taken 26 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 26 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 26 times.
✗ Branch 7 not taken.
 104 std::copy(permutationIndices.begin(), permutationIndices.end(),
200 permutation.begin());
201
5/10
✓ Branch 0 taken 26 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 26 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 26 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 26 times.
✗ Branch 9 not taken.
 130 std::copy(inversePermutationIndices.begin(), inversePermutationIndices.end(),
202 inversePermutation.begin());
203 #endif // HAVE_PTSCOTCH
204 26 }
205 };
206
207 } // end namespace Dumux
208
209 #endif
210