Line data Source code
1 : /*
2 : * Copyright (c) 2010-2015: G-CSC, Goethe University Frankfurt
3 : * Author: Sebastian Reiter
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 __H__LIB_GRID__DISTRIBUTED_GRID__
34 : #define __H__LIB_GRID__DISTRIBUTED_GRID__
35 :
36 : #include <map>
37 : #include <vector>
38 : #include "parallel_grid_layout.h"
39 : #include "lib_grid/multi_grid.h"
40 : #include "common/util/owned_pointer.h"
41 : #include "distro_adjuster.h"
42 :
43 : namespace ug
44 : {
45 :
46 : /// \addtogroup lib_grid_parallelization
47 : /// @{
48 :
49 : /// the states with which elements are marked in ug::DistributedGridManager
50 : /** Note that the constants are directly related to the constants enumerated
51 : * in InterfaceNodeTypes.
52 : * Please also note that the constants are currently stored in bytes. No
53 : * value using more than 8 bits is thus allowed.
54 : */
55 : enum ElementStatusTypes
56 : {
57 : ES_NONE = INT_NONE,
58 : ES_H_MASTER = INT_H_MASTER,
59 : ES_H_SLAVE = INT_H_SLAVE,
60 : ES_V_MASTER = INT_V_MASTER,
61 : ES_V_SLAVE = INT_V_SLAVE,
62 :
63 : //ES_GHOST = 1 << 5,//currently unused
64 : ES_SCHEDULED_FOR_INTERFACE = 1 << 6,
65 : ES_IN_INTERFACE = 1 << 7
66 : };
67 :
68 :
69 : /// manages the layouts and interfaces which are associated with a distributed grid.
70 : /** The DistributedGridManager is a grid observer, which manages the GridLayoutMap
71 : * of a distributed grid. New elements are automatically added to interfaces as
72 : * required and erased elements are automatically removed from interfaces.
73 : *
74 : * Note that while a DistributedGridManager observes a grid, one may only
75 : * create new elements in the associated grid between calls to
76 : * begin_ordered_element_insertion() and end_ordered_element_insertion().
77 : *
78 : * Similarly elements of the associated grid may only be erased during calls to
79 : * begin_element_deletion() and end_element_deletion().
80 : *
81 : * Those barriers are important, so that distributed grid managers can insert
82 : * associated elements on different processes in the same order without communicating.
83 : *
84 : * Note that only one layer of elements may be created / erased between calls to
85 : * begin_ordered_element_insertion / end_ordered_... etc...
86 : */
87 : class DistributedGridManager : public GridObserver
88 : {
89 : public:
90 : DistributedGridManager();
91 : DistributedGridManager(MultiGrid& grid);
92 : virtual ~DistributedGridManager();
93 :
94 : // assignment
95 : void assign(MultiGrid& grid);
96 :
97 : inline MultiGrid* get_assigned_grid() {return m_pGrid;}
98 : inline const MultiGrid* get_assigned_grid() const {return m_pGrid;}
99 :
100 : // layout access
101 : /** if you change the layout externally, be sure to call
102 : * DistributedGrid::layout_changed() afterwards.*/
103 : inline GridLayoutMap& grid_layout_map() {return m_gridLayoutMap;}
104 0 : inline const GridLayoutMap& grid_layout_map() const {return m_gridLayoutMap;}
105 :
106 : /// call this method if you altered the layout externally.
107 : /** This should be done as seldom as possible.
108 : * If you only added elements you may set addedElemsOnly to true.
109 : * The complexity in this case is proportional to the number of elements
110 : * in the layout.
111 : * If you removed elements or if you are unsure what operations have been
112 : * performed on the layout, you have to set addedElemsOnly to false
113 : * (the default value). Complexity in this case is proportional to the
114 : * number of elements in the underlying grid (or numer of elements in
115 : * the layout - whichever is higher).*/
116 : void grid_layouts_changed(bool addedElemsOnly = false);
117 :
118 : /// returns the status of the given object.
119 : /** The status gives information about the type of interfaces in which a node
120 : * lies. The returned value is an or combination of the constants enumerated
121 : * in InterfaceNodeTypes and ElementStatusTypes.
122 : * \sa contains_status
123 : * \{ */
124 : byte get_status(GridObject* go) const;
125 : inline byte get_status(Vertex* vrt) const {return elem_info(vrt).get_status();}
126 : inline byte get_status(Edge* edge) const {return elem_info(edge).get_status();}
127 : inline byte get_status(Face* face) const {return elem_info(face).get_status();}
128 : inline byte get_status(Volume* vol) const {return elem_info(vol).get_status();}
129 : /** \} */
130 :
131 : /// returns true if the status of the given object contains the given status.
132 : /** status can be an or-combination of constants enumerated in InterfaceNodeTypes
133 : * and ElementStatusTypes.*/
134 : template <class TGeomObj>
135 : bool contains_status(TGeomObj* o, byte status) const {return (get_status(o) & status) == status;}
136 :
137 : /// returns true if the element is a ghost
138 : /** ghost elements are vertical masters that are in no other interfaces.
139 : * Those elements shouldn't be refined.*/
140 : template<class TElem>
141 : inline bool is_ghost(TElem* elem) const;
142 :
143 : /// returns true if the element is contained in a horizontal interface
144 : template<class TElem>
145 : inline bool is_in_horizontal_interface(TElem* elem) const;
146 :
147 : /// returns true if the element is contained in a vertical interface
148 : template<class TElem>
149 : inline bool is_in_vertical_interface(TElem* elem) const;
150 :
151 : // element creation
152 : /// call this method before you start creating new elements in the associated grid.
153 : /** You shouldn't add new interfaces to the associated communication-set
154 : * between begin_ and end_element_creation.*/
155 : void begin_ordered_element_insertion();
156 :
157 : /// call this method when you're done with element creation.
158 : /** Elements will not be added to the associated \sa GridCommunicationSet
159 : * until this method is called.*/
160 : void end_ordered_element_insertion();
161 :
162 : // element deletion
163 : /// call this method before you start deleting elements in the associated grid
164 : void begin_element_deletion();
165 :
166 : /// call this method after you're done deleting elements from the associated grid
167 : void end_element_deletion();
168 :
169 : /// returns true if an element is in one or more interfaces
170 : template <class TElem>
171 : bool is_interface_element(TElem* elem);
172 :
173 : /** returns a list of pairs (procID, index) that tells for each element
174 : * where in which interfaces it lies.
175 : * \param statusType may be any or-combination of values enumerated in ElementStatusTypes.*/
176 : template <class TElem>
177 : void collect_interface_entries(
178 : std::vector<std::pair<int, size_t> >& vEntriesOut,
179 : TElem* elem, byte statusType, bool clearContainer = true);
180 :
181 :
182 : /// Enables or disables interface managment. Use with care!
183 : /** Interface managment is enabled by default. If you intend to completly
184 : * restructure the grid and its interfaces, it may be beneficial to
185 : * disable interface management before doing so. You should then use the method
186 : * grid_layouts_changed to inform the DistributedGridManager that you
187 : * modified the interfaces externally.*/
188 : void enable_interface_management(bool bEnable) {m_interfaceManagementEnabled = bEnable;}
189 :
190 :
191 : /// set a global distribution adjuster
192 : /** A distribution adjuster may be used to manually adjust how elements are distributed
193 : * by the domain distribution. For example, in the circumstances that led to the implementation
194 : * of this feature, it was necessary to distribute certain vertices to all processes which held
195 : * elements of a specific subset (regardless of whether those processes had any elements
196 : * connected to these vertices or not).
197 : * During the distribution process, the adjuster's adjust() method is called at the end of
198 : * SelectElementsForTargetPartition() in distribution.cpp.
199 : *
200 : * @warning This is a highly experimental feature and as such not guaranteed to work properly.
201 : */
202 : void set_distro_adjuster(SmartPtr<DistroAdjuster> adj) {m_spDistroAdjuster = adj;}
203 :
204 : /// get the distribution adjuster
205 : SmartPtr<DistroAdjuster> distro_adjuster() {return m_spDistroAdjuster;}
206 :
207 : ////////////////////////////////
208 : // grid callbacks
209 : virtual void grid_to_be_destroyed(Grid* grid);
210 :
211 : // vertex callbacks
212 : virtual void vertex_created(Grid* grid, Vertex* vrt,
213 : GridObject* pParent = NULL,
214 : bool replacesParent = false);
215 :
216 : virtual void edge_created(Grid* grid, Edge* e,
217 : GridObject* pParent = NULL,
218 : bool replacesParent = false);
219 :
220 : virtual void face_created(Grid* grid, Face* f,
221 : GridObject* pParent = NULL,
222 : bool replacesParent = false);
223 :
224 : virtual void volume_created(Grid* grid, Volume* v,
225 : GridObject* pParent = NULL,
226 : bool replacesParent = false);
227 :
228 : virtual void vertex_to_be_erased(Grid* grid, Vertex* vrt,
229 : Vertex* replacedBy = NULL);
230 :
231 : virtual void edge_to_be_erased(Grid* grid, Edge* e,
232 : Edge* replacedBy = NULL);
233 :
234 : virtual void face_to_be_erased(Grid* grid, Face* f,
235 : Face* replacedBy = NULL);
236 :
237 : virtual void volume_to_be_erased(Grid* grid, Volume* vol,
238 : Volume* replacedBy = NULL);
239 :
240 : protected:
241 : /// performs registration and deregistration at a grid.
242 : /** call set_grid(NULL) to unregister the observer from a grid.*/
243 : void set_grid(Grid* grid);
244 :
245 : /// free's all grid related data
246 : void free_grid_data();
247 :
248 : template <class TGeomObj>
249 : void reset_elem_infos();
250 :
251 : /* Currently unused. See implementation for more details.
252 : template <class TElem>
253 : void set_preliminary_ghost_states();
254 :
255 : void update_ghost_states();
256 : */
257 :
258 : template <class TGeomObj, class TLayoutMap>
259 : void update_elem_info(TLayoutMap& layoutMap, int nodeType,
260 : byte newStatus, bool addStatus = false);
261 :
262 : template <class TGeomObj>
263 : void update_all_elem_infos();
264 :
265 : /// vertex_created, edge_created, ... callbacks call this method.
266 : template <class TElem>
267 : void handle_created_element(TElem* pElem, GridObject* pParent,
268 : bool replacesParent);
269 :
270 : template <class TElem, class TScheduledElemMap, class TParent>
271 : void schedule_element_for_insertion(TScheduledElemMap& elemMap,
272 : TElem* elem,
273 : TParent* pParent);
274 :
275 : void clear_scheduled_elements();
276 :
277 : template <class TScheduledElemMap>
278 : void perform_ordered_element_insertion(TScheduledElemMap& elemMap);
279 :
280 : template <class TElem>
281 : void add_element_to_interface(TElem* pElem, int procID);
282 :
283 : template <class TElem>
284 : void element_to_be_erased(TElem* elem);
285 :
286 : /** Note that the content of the given vector may be extended during this method.*/
287 : template <class TElem>
288 : void create_missing_constrained_h_interfaces(std::vector<TElem*>& newConstrainedElems);
289 :
290 : protected:
291 : /// Be careful when creating copies of ElementInfo.
292 : /** Ownership of the internal data-object is transfered to the new copy.
293 : * The old instance will thus point to a NULL pointer instead of the data
294 : * object after the copy operation.
295 : */
296 : template <class TGeomObj>
297 : class ElementInfo
298 : {
299 : public:
300 : // types
301 : typedef typename GridLayoutMap::template Types<TGeomObj>
302 : ::Interface Interface;
303 : typedef typename Interface::iterator InterfaceElemIter;
304 : //typedef std::pair<Interface*, InterfaceElemIter> Entry;
305 :
306 : struct Entry{
307 : Entry() {}
308 : Entry(Interface* intfc, InterfaceElemIter intfcElemIter, int intfcType) :
309 : m_interface(intfc), m_interfaceElemIter(intfcElemIter),
310 : m_interfaceType(intfcType) {}
311 :
312 : Interface* m_interface;
313 : InterfaceElemIter m_interfaceElemIter;
314 : int m_interfaceType;
315 : };
316 :
317 : typedef std::list<Entry> EntryList;
318 : typedef typename EntryList::iterator EntryIterator;
319 : typedef typename EntryList::const_iterator ConstEntryIterator;
320 :
321 : // methods
322 : ElementInfo() {}
323 :
324 : ~ElementInfo() {if(has_data()) m_data.reset();}
325 :
326 : void reset()
327 : {
328 : if(has_data()){
329 : //todo: reuse m_data
330 : m_data.reset();
331 : }
332 : }
333 :
334 : void add_entry(Interface* interface,
335 : InterfaceElemIter iter,
336 : int intfcType) {data().m_entries.push_back(Entry(interface, iter, intfcType));}
337 :
338 : void remove_entry(Interface* interface) {data().m_entries.erase(find_entry(interface));}
339 :
340 : /// Note: This method may only be called if is_interface_entry() returns true.
341 : /** \{ */
342 : inline EntryIterator entries_begin() {assert(has_data()); return m_data->m_entries.begin();}
343 : inline EntryIterator entries_end() {assert(has_data()); return m_data->m_entries.end();}
344 :
345 : inline ConstEntryIterator entries_begin() const {assert(has_data()); return m_data->m_entries.begin();}
346 : inline ConstEntryIterator entries_end() const {assert(has_data()); return m_data->m_entries.end();}
347 : /** \} */
348 :
349 : size_t get_local_id(EntryIterator iter) const {return iter->m_interface->get_local_id(iter->m_interfaceElemIter);}
350 : size_t get_local_id(ConstEntryIterator iter) const {return iter->m_interface->get_local_id(iter->m_interfaceElemIter);}
351 : int get_target_proc(EntryIterator iter) const {return iter->m_interface->get_target_proc();}
352 : int get_target_proc(ConstEntryIterator iter) const {return iter->m_interface->get_target_proc();}
353 : Interface* get_interface(EntryIterator iter) {return iter->m_interface;}
354 : int get_interface_type(EntryIterator iter) const {return iter->m_interfaceType;}
355 : int get_interface_type(ConstEntryIterator iter) const {return iter->m_interfaceType;}
356 :
357 : /// Note: This method may only be called if is_interface_entry() returns true.
358 : EntryIterator find_entry(Interface* interface)
359 : { assert(has_data());
360 : for(EntryIterator iter = entries_begin(); iter != entries_end(); ++iter){
361 : if(iter->m_interface == interface)
362 : return iter;
363 : }
364 : return entries_end();
365 : }
366 :
367 : void set_status(byte status)
368 : {
369 : if(!has_data() && (status == ES_NONE))
370 : return;
371 : data().m_status = status;
372 : }
373 : byte get_status() const
374 : {
375 0 : if(!has_data()) return ES_NONE;
376 0 : return m_data->m_status;
377 : }
378 :
379 : bool is_interface_element()
380 : {
381 : if(!has_data()) return false;
382 : return !m_data->m_entries.empty();
383 : }
384 :
385 : protected:
386 : struct Data{
387 : Data() : m_status(ES_NONE) {}
388 : EntryList m_entries;
389 : byte m_status;
390 : };
391 :
392 : /// returns the data object. Creates it if necessary.
393 : inline Data& data()
394 : {
395 : if(!has_data())
396 : m_data.get() = new Data;
397 : return *m_data;
398 : }
399 :
400 0 : inline bool has_data() const {return m_data.get() != NULL;}
401 :
402 : /// OwnedPtr is required to transfer ownership of the data-ptr during copy-operations.
403 : /** Since ElementInfo objects are stored in attachments, they will be copied
404 : * from time to time. Ownership is thereby transfered to the new copy.
405 : */
406 : OwnedPtr<Data> m_data;
407 : };
408 :
409 : typedef ElementInfo<Vertex> ElemInfoVrt;
410 : typedef ElementInfo<Edge> ElemInfoEdge;
411 : typedef ElementInfo<Face> ElemInfoFace;
412 : typedef ElementInfo<Volume> ElemInfoVol;
413 :
414 : typedef Attachment<ElemInfoVrt> AElemInfoVrt;
415 : typedef Attachment<ElemInfoEdge> AElemInfoEdge;
416 : typedef Attachment<ElemInfoFace> AElemInfoFace;
417 : typedef Attachment<ElemInfoVol> AElemInfoVol;
418 :
419 : /// Used to schedule an element for insertion during ordered-insertion-mode.
420 : /** For each interface in which the parent lies, an instance of
421 : * this class is added to scheduledElementMap of the parents type.
422 : * The local ID of the parent will be used as key.
423 : * The type of layout into which the element shall be inserted can
424 : * be retrieved from the status of the associated geomObj.*/
425 : struct ScheduledElement
426 : {
427 : ScheduledElement(GridObject* obj, int procID) :
428 : geomObj(obj), connectedProcID(procID) {}
429 :
430 : GridObject* geomObj;
431 : int connectedProcID;
432 : };
433 :
434 : typedef std::multimap<size_t, ScheduledElement> ScheduledElemMap;
435 :
436 : protected:
437 : inline ElemInfoVrt& elem_info(Vertex* ele) {return m_aaElemInfoVRT[ele];}
438 : inline ElemInfoEdge& elem_info(Edge* ele) {return m_aaElemInfoEDGE[ele];}
439 : inline ElemInfoFace& elem_info(Face* ele) {return m_aaElemInfoFACE[ele];}
440 : inline ElemInfoVol& elem_info(Volume* ele) {return m_aaElemInfoVOL[ele];}
441 :
442 : inline const ElemInfoVrt& elem_info(Vertex* ele) const {return m_aaElemInfoVRT[ele];}
443 : inline const ElemInfoEdge& elem_info(Edge* ele) const {return m_aaElemInfoEDGE[ele];}
444 : inline const ElemInfoFace& elem_info(Face* ele) const {return m_aaElemInfoFACE[ele];}
445 : inline const ElemInfoVol& elem_info(Volume* ele) const {return m_aaElemInfoVOL[ele];}
446 :
447 : inline void got_new_constrained_vertical(Vertex* v) {m_newConstrainedVerticalVrts.push_back(v);}
448 : inline void got_new_constrained_vertical(Edge* e) {m_newConstrainedVerticalEdges.push_back(e);}
449 : inline void got_new_constrained_vertical(Face* f) {m_newConstrainedVerticalFaces.push_back(f);}
450 : inline void got_new_constrained_vertical(Volume*) {UG_THROW("There are no constrained volumes!");}
451 :
452 :
453 : protected:
454 : MultiGrid* m_pGrid;
455 : GridLayoutMap m_gridLayoutMap;
456 :
457 : bool m_interfaceManagementEnabled;///<only for debug purposes
458 :
459 : bool m_bOrderedInsertionMode;
460 : bool m_bElementDeletionMode;
461 :
462 : AElemInfoVrt m_aElemInfoVrt;
463 : AElemInfoEdge m_aElemInfoEdge;
464 : AElemInfoFace m_aElemInfoFace;
465 : AElemInfoVol m_aElemInfoVol;
466 :
467 : Grid::VertexAttachmentAccessor<AElemInfoVrt> m_aaElemInfoVRT;
468 : Grid::EdgeAttachmentAccessor<AElemInfoEdge> m_aaElemInfoEDGE;
469 : Grid::FaceAttachmentAccessor<AElemInfoFace> m_aaElemInfoFACE;
470 : Grid::VolumeAttachmentAccessor<AElemInfoVol> m_aaElemInfoVOL;
471 :
472 : ScheduledElemMap m_vrtMap; ///< holds all elements that were scheduled by vertices
473 : ScheduledElemMap m_edgeMap; ///< holds all elements that were scheduled by edges
474 : ScheduledElemMap m_faceMap; ///< holds all elements that were scheduled by faces
475 : ScheduledElemMap m_volMap; ///< holds all elements that were scheduled by volumes
476 :
477 : std::vector<Vertex*> m_newConstrainedVerticalVrts;
478 : std::vector<Edge*> m_newConstrainedVerticalEdges;
479 : std::vector<Face*> m_newConstrainedVerticalFaces;
480 :
481 : SmartPtr<DistroAdjuster> m_spDistroAdjuster;
482 : };
483 :
484 : /// @}
485 :
486 : }// end of namespace
487 :
488 : ////////////////////////////////
489 : // include implementation
490 : #include "distributed_grid_impl.hpp"
491 :
492 : #endif
|
