Loading [MathJax]/extensions/tex2jax.js
ug4
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
parallel_matrix.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2022: G-CSC, Goethe University Frankfurt
3 * Author: Felix Salfelder, 2022
4 *
5 * This file is part of UG4.
6 *
7 * UG4 is free software: you can redistribute it and/or modify it under the
8 * terms of the GNU Lesser General Public License version 3 (as published by the
9 * Free Software Foundation) with the following additional attribution
10 * requirements (according to LGPL/GPL v3 §7):
11 *
12 * (1) The following notice must be displayed in the Appropriate Legal Notices
13 * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14 *
15 * (2) The following notice must be displayed at a prominent place in the
16 * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17 *
18 * (3) The following bibliography is recommended for citation and must be
19 * preserved in all covered files:
20 * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21 * parallel geometric multigrid solver on hierarchically distributed grids.
22 * Computing and visualization in science 16, 4 (2013), 151-164"
23 * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24 * flexible software system for simulating pde based models on high performance
25 * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26 *
27 * This program is distributed in the hope that it will be useful,
28 * but WITHOUT ANY WARRANTY; without even the implied warranty of
29 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30 * GNU Lesser General Public License for more details.
31 */
32
33#ifndef UG_GRAPH_INTERFACE_PARALLEL_MATRIX_H
34#define UG_GRAPH_INTERFACE_PARALLEL_MATRIX_H
35
36#include "sparsematrix_boost.h"
37#include <boost/iterator/filter_iterator.hpp>
38
39namespace ug{
40
41namespace detail{
42
43class bglp_vertex_descriptor : public std::pair<int, int>{
44public:
46 bglp_vertex_descriptor(int a, int b) : std::pair<int, int>(a, b) {
47 }
48public:
49 int owner() const{ return first; }
50 int local() const{ return second; }
51};
52
54{
55 return p.owner();
56}
58{
59 return p.local();
60}
61
62} // detail
63
64// BGL style access to matrix
65// assign vertices to processes,
66// provide access to cross process entries
67template<class T>
69public: // types
71 typedef typename T::const_row_iterator const_row_iterator;
72private:
73 typedef std::vector<int> owners;
74 typedef std::vector<int> ghosts;
75 typedef typename boost::graph_traits<T>::vertex_iterator base_vertex_iterator;
76 typedef typename boost::graph_traits<T>::out_edge_iterator base_edge_iterator;
77 class vertex_iterator_ // facade?
78 : public std::iterator<std::input_iterator_tag, vertex_descriptor,
79 ptrdiff_t, vertex_descriptor, vertex_descriptor> { //
80 public:
81 explicit vertex_iterator_() : _owners(nullptr) {}
82 explicit vertex_iterator_(base_vertex_iterator b, owners const* o) : _base(b), _owners(o) {
83 }
84 bool operator==(vertex_iterator_ const& o) const{
85 return _base == o._base;
86 }
87 bool operator!=(vertex_iterator_ const& p) const{
88 return !operator==(p);
89 }
91 incomplete();
92 return *this;
93 }
95 ++_base;
96 return *this;
97 }
99 auto b = *_base;
100 assert(_owners);
101 return vertex_descriptor((*_owners)[b], *_base);
102 }
103 private:
107 };
108
111 int rank;
112#ifdef UG_PARALLEL
113 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
114 return v.owner() == rank;
115#else
116 return true;
117#endif
118 }
119 };
120
121public:
122 typedef boost::filter_iterator<filter_local, vertex_iterator_> vertex_iterator;
123 class adjacency_iterator // facade?
124 :public std::iterator<std::input_iterator_tag, vertex_descriptor, ptrdiff_t, vertex_descriptor, vertex_descriptor> { //
125 public:
126 typedef typename boost::graph_traits<T>::adjacency_iterator base;
127 public:
129 : _owners(nullptr), _ghosts(nullptr) {
130 }
131 adjacency_iterator(base b, owners const* o, ghosts const* g)
132 : _base(b), _owners(o), _ghosts(g) {
133 }
134 public:
135 bool operator==(adjacency_iterator const& o) const{
136 return _base == o._base;;
137 }
138 bool operator!=(adjacency_iterator const& p) const{
139 return !operator==(p);
140 }
142 incomplete();
143 return *this;
144 }
146 ++_base;
147 return *this;
148 }
150 int i = *_base;
151 int o = (*_owners)[i];
152 int l = (*_ghosts)[i];
153
154 return vertex_descriptor(o, l);
155 }
159 }; // adjacency_iterator
160
161 class edge;
162 class out_edge_iterator : public boost::iterator_facade<
163 out_edge_iterator,
164 base_edge_iterator,
165 std::input_iterator_tag,
166 edge, // <= reference
167 std::intmax_t // difference_type
168 >{ //
169 public:
171 : _owners(nullptr), _ghosts(nullptr), _matrix(nullptr) {
172 }
173 out_edge_iterator(base_edge_iterator b, owners const* o, ghosts const* g, T const* m)
174 : _base(b), _owners(o), _ghosts(g), _matrix(m) {
175 }
176 bool operator==(out_edge_iterator const& p) const{
177 return _base == p._base;
178 }
179 bool operator!=(out_edge_iterator const& p) const{
180 return !operator==(p);
181 }
183 ++_base;
184 return *this;
185 }
186 edge operator*() const;
187 private:
191 T const* _matrix;
192 };
193 class edge {
194 public:
197 public:
198
200 return _s;
201 }
203 return _t;
204 }
205
206 private:
209
210 }; // edge
211
212public:
213 explicit BGLParallelMatrix(T const* m=nullptr)
214 : _matrix(m) {
215 if(m){
216 refresh();
217 }else{ untested();
218 }
219 }
220// explicit BGLParallelMatrix(ug::ParallelMatrix<T> const& o)
221// : _matrix(o._matrix), _matrix_transpose(o._matrix_transpose) { untested();
222// }
228
229public: // interface
230 void refresh();
231
232 int num_rows() const {
233 return std::max(_matrix->num_rows(), _matrix->num_cols());
234 }
235 int num_cols() const { untested();
236 return num_rows();
237 }
238 int num_connections(int v) const {
239 if(v<_matrix->num_rows()){
240 return _matrix->num_connections(v);
241 }else{
242 assert(v<_matrix_transpose.num_rows());
243 return _matrix_transpose.num_connections(v);
244 }
245 }
246 int out_degree(int v) const {
247 // could call in_degree?
248 return in_degree(v);
249 }
250 int in_degree(int v) const {
251 // could use difference, requires zero-pruning in _matrix_transpose.
252 if(v<_matrix_transpose.num_rows()){
254 }else{
255 assert(_matrix);
256 assert(v<_matrix->num_rows());
257 return boost::out_degree(v, *_matrix);
258 }
259 }
260 int degree(int v) const { untested();
261 return 2*out_degree(v);
262 }
263
265 assert(_matrix);
266 auto p = boost::adjacent_vertices(row, *_matrix);
267 return adjacency_iterator(p.first, &_owners, &_ghosts);
268 }
270 assert(_matrix);
271 auto p = boost::adjacent_vertices(row, *_matrix);
272 return adjacency_iterator(p.second, &_owners, &_ghosts);
273 }
275 assert(_matrix);
276 auto p = boost::out_edges(row, *_matrix);
277 return out_edge_iterator(p.first, &_owners, &_ghosts, _matrix);
278 }
280 assert(_matrix);
281 auto p = boost::out_edges(row, *_matrix);
282 return out_edge_iterator(p.second, &_owners, &_ghosts, _matrix);
283 }
284
285#if 0
286 const_row_iterator begin_row(int row) const {
287 assert(_matrix);
288 if(row<_matrix->num_rows()){
289 }else{
290 row = 0;
291 }
292 return _matrix->begin_row(row);
293 }
294 const_row_iterator end_row(int row) const {
295 assert(_matrix);
296 if(row<_matrix->num_rows()){
297 return _matrix->end_row(row);
298 }else{
299 return _matrix->begin_row(0);
300 }
301 }
302#endif
303
305 assert(_matrix);
306 auto v = boost::vertices(*_matrix);
307 auto b = vertex_iterator_(v.first, &_owners);
308 auto e = vertex_iterator_(v.second, &_owners);
309 // filter_local f(_owners);
310 return vertex_iterator( b, e );
311 }
312
314 assert(_matrix);
315 auto v = boost::vertices(*_matrix);
316 auto e = vertex_iterator_(v.second, &_owners);
317 return vertex_iterator( e, e );
318 }
319
321 if(col<_matrix_transpose.num_rows()){
322 }else{
323 col = 0;
324 }
325 return _matrix_transpose.begin_row(col);
326 }
328 if(col<_matrix_transpose.num_rows()){
329 return _matrix_transpose.end_row(col);
330 }else{
331 return _matrix_transpose.begin_row(0);
332 }
333 }
334
335private:
336public: // BUG
337 T const* _matrix;
340private:
342}; // BGLParallelMatrix
343
344template<class T>
346{
347 auto e = *_base;
348 assert(_matrix);
349 auto s = boost::source(e, _matrix);
350 auto t = boost::target(e, _matrix);
351 typedef typename BGLParallelMatrix<T>::edge E;
352 vertex_descriptor v((*_owners)[s], (*_ghosts)[s]);
353 vertex_descriptor w((*_owners)[t], (*_ghosts)[t]);
354
355 return E(v, w);
356}
357
358template<class T>
360{
361 assert(_matrix);
362#ifdef UG_PARALLEL
363 assert(_matrix->num_rows() == _matrix->num_cols()); // for now.
364 int rank;
365 MPI_Comm_rank(MPI_COMM_WORLD, &rank);
366 _owners.resize(_matrix->num_rows(), rank);
367 _ghosts.resize(_matrix->num_rows()); // map slave nodes to master local index
368
369 int l = 0;
370 for(auto& i : _ghosts){
371 i = l++;
372 }
373
374 auto L = _matrix->layouts();
375 assert(L);
376
377 pcl::ProcessCommunicator pc = L->proc_comm();
378 // void PC::send_data(void* pBuffer, int bufferSize, int destProc, int tag) const;
379
380 // send indexmap to slaves
381 IndexLayout const& idx_master = L->master();
382 for(auto k = idx_master.begin(); k!=idx_master.end(); ++k){
383 IndexLayout::Interface const& I = idx_master.interface(k);
384 std::vector<int> mmap(I.size());
385 int dest = idx_master.proc_id(k);
386 auto b = mmap.begin();
387
388 for(auto i : I){
389 *b = i.elem;
390 ++b;
391 }
392 pc.send_data(mmap.data(), mmap.size()*sizeof(int), dest, 17);
393 }
394
395 IndexLayout const& idx_slave = L->slave();
396 for(auto k = idx_slave.begin(); k!=idx_slave.end(); ++k){
397 IndexLayout::Interface const& I = idx_slave.interface(k);
398 int srank = idx_slave.proc_id(k);
399
400 std::vector<int> mmap(I.size());
401 pc.receive_data(mmap.data(), mmap.size()*sizeof(int), srank, 17);
402// for(auto i : mmap){
403// std::cerr << "received " << rank << " from " << srank << " " << i << "\n";
404// }
405
406 int j=0;
407 for(auto i : I){
408 assert(_owners[i.elem] == rank); // only one owner per node.
409 _owners[i.elem] = srank;
410 ++j;
411 _ghosts[i.elem] = mmap[j];
412 }
413 }
414#endif
415}
416
417} // ug
418
419#endif // guard
parameterString p
parameterString s
You may add elements to this interface and iterate over them.
Definition pcl_communication_structs.h:207
size_t size() const
returns the number of elements that are stored in the interface.
Definition pcl_communication_structs.h:306
Definition pcl_process_communicator.h:70
void receive_data(void *pBuffOut, int bufferSize, int srcProc, int tag) const
receives data from srcPrc with the specified tag.
Definition pcl_process_communicator.cpp:511
void send_data(void *pBuffer, int bufferSize, int destProc, int tag) const
sends data with the given tag to the specified process.
Definition pcl_process_communicator.cpp:471
iterator end(size_t level=0)
returns the iterator to the last interface of the layout.
Definition pcl_communication_structs.h:492
Interface & interface(iterator iter)
returns the interface to the given iterator.
Definition pcl_communication_structs.h:505
iterator begin(size_t level=0)
returns the iterator to the first interface of the layout.
Definition pcl_communication_structs.h:486
int proc_id(iterator iter) const
returns the target process of the interface given in iterator
Definition pcl_communication_structs.h:509
Definition parallel_matrix.h:124
adjacency_iterator & operator++(int)
Definition parallel_matrix.h:141
adjacency_iterator(base b, owners const *o, ghosts const *g)
Definition parallel_matrix.h:131
bool operator==(adjacency_iterator const &o) const
Definition parallel_matrix.h:135
base _base
Definition parallel_matrix.h:156
owners const * _owners
Definition parallel_matrix.h:157
ghosts const * _ghosts
Definition parallel_matrix.h:158
adjacency_iterator()
Definition parallel_matrix.h:128
vertex_descriptor operator*() const
Definition parallel_matrix.h:149
bool operator!=(adjacency_iterator const &p) const
Definition parallel_matrix.h:138
boost::graph_traits< T >::adjacency_iterator base
Definition parallel_matrix.h:126
adjacency_iterator & operator++()
Definition parallel_matrix.h:145
Definition parallel_matrix.h:193
vertex_descriptor target() const
Definition parallel_matrix.h:202
vertex_descriptor _s
Definition parallel_matrix.h:207
edge(vertex_descriptor s, vertex_descriptor t)
Definition parallel_matrix.h:195
vertex_descriptor _t
Definition parallel_matrix.h:208
vertex_descriptor source() const
Definition parallel_matrix.h:199
Definition parallel_matrix.h:168
ghosts const * _ghosts
Definition parallel_matrix.h:190
bool operator==(out_edge_iterator const &p) const
Definition parallel_matrix.h:176
out_edge_iterator(base_edge_iterator b, owners const *o, ghosts const *g, T const *m)
Definition parallel_matrix.h:173
T const * _matrix
Definition parallel_matrix.h:191
base_edge_iterator _base
Definition parallel_matrix.h:188
owners const * _owners
Definition parallel_matrix.h:189
out_edge_iterator()
Definition parallel_matrix.h:170
bool operator!=(out_edge_iterator const &p) const
Definition parallel_matrix.h:179
out_edge_iterator & operator++()
Definition parallel_matrix.h:182
edge operator*() const
Definition parallel_matrix.h:345
Definition parallel_matrix.h:79
vertex_iterator_ & operator++(int)
Definition parallel_matrix.h:90
bool operator==(vertex_iterator_ const &o) const
Definition parallel_matrix.h:84
vertex_iterator_ & operator++()
Definition parallel_matrix.h:94
bool operator!=(vertex_iterator_ const &p) const
Definition parallel_matrix.h:87
vertex_iterator_(base_vertex_iterator b, owners const *o)
Definition parallel_matrix.h:82
ghosts const * _ghosts
Definition parallel_matrix.h:106
vertex_iterator_()
Definition parallel_matrix.h:81
owners const * _owners
Definition parallel_matrix.h:105
vertex_descriptor operator*() const
Definition parallel_matrix.h:98
base_vertex_iterator _base
Definition parallel_matrix.h:104
Definition parallel_matrix.h:68
std::vector< int > ghosts
Definition parallel_matrix.h:74
adjacency_iterator begin_adjacent_vertices(int row) const
Definition parallel_matrix.h:264
boost::graph_traits< T >::vertex_iterator base_vertex_iterator
Definition parallel_matrix.h:75
int in_degree(int v) const
Definition parallel_matrix.h:250
out_edge_iterator begin_out_edges(int row) const
Definition parallel_matrix.h:274
BGLParallelMatrix & operator=(BGLParallelMatrix const &o)
Definition parallel_matrix.h:223
const_row_iterator begin_col(int col) const
Definition parallel_matrix.h:320
vertex_iterator end_vertices() const
Definition parallel_matrix.h:313
int num_rows() const
Definition parallel_matrix.h:232
ghosts _ghosts
Definition parallel_matrix.h:339
adjacency_iterator end_adjacent_vertices(int row) const
Definition parallel_matrix.h:269
std::vector< int > owners
Definition parallel_matrix.h:73
boost::graph_traits< T >::out_edge_iterator base_edge_iterator
Definition parallel_matrix.h:76
boost::filter_iterator< filter_local, vertex_iterator_ > vertex_iterator
Definition parallel_matrix.h:122
T::const_row_iterator const_row_iterator
Definition parallel_matrix.h:71
vertex_iterator begin_vertices() const
Definition parallel_matrix.h:304
int num_cols() const
Definition parallel_matrix.h:235
T _matrix_transpose
Definition parallel_matrix.h:341
out_edge_iterator end_out_edges(int row) const
Definition parallel_matrix.h:279
int num_connections(int v) const
Definition parallel_matrix.h:238
int degree(int v) const
Definition parallel_matrix.h:260
T const * _matrix
Definition parallel_matrix.h:337
void refresh()
Definition parallel_matrix.h:359
int out_degree(int v) const
Definition parallel_matrix.h:246
detail::bglp_vertex_descriptor vertex_descriptor
Definition parallel_matrix.h:70
BGLParallelMatrix(T const *m=nullptr)
Definition parallel_matrix.h:213
owners _owners
Definition parallel_matrix.h:338
const_row_iterator end_col(int col) const
Definition parallel_matrix.h:327
Definition parallel_matrix.h:43
bglp_vertex_descriptor(int a, int b)
Definition parallel_matrix.h:46
int local() const
Definition parallel_matrix.h:50
int owner() const
Definition parallel_matrix.h:49
bglp_vertex_descriptor()
Definition parallel_matrix.h:45
#define untested()
Definition lua_table_handle.cpp:15
std::pair< typename graph_traits< T >::adjacency_iterator, typename graph_traits< T >::adjacency_iterator > adjacent_vertices(size_t v, ug::BidirectionalMatrix< T > const &M)
Definition bidirectional_boost.h:108
std::pair< SM_out_edge_iterator< typename T::value_type >, SM_out_edge_iterator< typename T::value_type > > out_edges(size_t v, ug::BidirectionalMatrix< T > const &g)
Definition bidirectional_boost.h:136
int out_degree(int v, ug::BidirectionalMatrix< T > const &M)
Definition bidirectional_boost.h:76
std::pair< counting_iterator< size_t >, counting_iterator< size_t > > vertices(ug::BidirectionalMatrix< T > const &M)
Definition bidirectional_boost.h:60
size_t target(SM_edge< typename T::value_type > const &e, ug::BidirectionalMatrix< T > const &m)
Definition bidirectional_boost.h:100
size_t source(SM_edge< typename T::value_type > const &e, ug::BidirectionalMatrix< T > const &)
Definition bidirectional_boost.h:94
Definition smart_pointer.h:814
int local(bglp_vertex_descriptor p)
Definition parallel_matrix.h:57
int owner(bglp_vertex_descriptor p)
Definition parallel_matrix.h:53
the ug namespace
const_row_iterator end_row(size_t row) const
const_row_iterator begin_row(size_t row) const
Definition parallel_matrix.h:109
bool operator()(vertex_descriptor v) const
Definition parallel_matrix.h:110
#define incomplete()
Definition trace.h:10