Sierra Toolkit  Version of the Day
Rebalance.cpp
1 /*--------------------------------------------------------------------*/
2 /* Copyright 2001, 2008, 2009, 2010 Sandia Corporation. */
3 /* Under the terms of Contract DE-AC04-94AL85000, there is a */
4 /* non-exclusive license for use of this work by or on behalf */
5 /* of the U.S. Government. Export of this program may require */
6 /* a license from the United States Government. */
7 /*--------------------------------------------------------------------*/
8 
9 // Copyright 2001,2002 Sandia Corporation, Albuquerque, NM.
10 
11 #include <memory>
12 #include <stdexcept>
13 #include <vector>
14 #include <string>
15 
16 #include <stk_util/environment/ReportHandler.hpp>
17 #include <stk_util/parallel/ParallelReduce.hpp>
18 
19 #include <stk_mesh/base/BulkData.hpp>
20 #include <stk_mesh/base/MetaData.hpp>
21 #include <stk_mesh/base/GetEntities.hpp>
22 #include <stk_mesh/base/FieldData.hpp>
23 #include <stk_mesh/fem/FEMMetaData.hpp>
24 
27 
28 using namespace stk_classic;
29 using namespace stk_classic::rebalance;
30 
31 namespace {
32 
33 bool balance_comm_spec_domain( Partition * partition,
34  mesh::EntityProcVec & rebal_spec )
35 {
36  bool rebalancingHasOccurred = false;
37  {
38  int num_elems = partition->num_elems();
39  int tot_elems;
40  all_reduce_sum(partition->parallel(), &num_elems, &tot_elems, 1);
41 
42  if (tot_elems) {
43  partition->determine_new_partition(rebalancingHasOccurred);
44  }
45  }
46  if (rebalancingHasOccurred) partition->get_new_partition(rebal_spec);
47 
48  return rebalancingHasOccurred;
49 }
50 
51 
52 /*
53  * Traversing the migrating elements in reverse order produces a simplistic
54  * attempt at lowest-rank element proc greedy partitioning of dependents
55  * which seems to often work in practice. Some logic could be added here
56  * as needed to enforce more deterministic dependent partitions.
57  */
58 
59 void rebalance_dependent_entities( const mesh::BulkData & bulk_data ,
60  const Partition * partition,
61  const mesh::EntityRank & dep_rank,
62  mesh::EntityProcVec & entity_procs,
63  const stk_classic::mesh::EntityRank rank)
64 {
65 
67  const stk_classic::mesh::EntityRank element_rank = (rank != stk_classic::mesh::InvalidEntityRank) ? rank :
68  fem_meta.element_rank();
69 
70  if (dep_rank == element_rank) return;
71  // Create a map of ids of migrating elements to their owner proc and a vector of the migrating elements.
72  std::map<mesh::EntityId, unsigned> elem_procs;
73  mesh::EntityVector owned_moving_elems;
74  mesh::EntityProcVec::iterator ep_iter = entity_procs.begin(),
75  ep_end = entity_procs.end();
76  for( ; ep_end != ep_iter; ++ep_iter ) {
77  if( element_rank == ep_iter->first->entity_rank() )
78  {
79  const mesh::EntityId elem_id = ep_iter->first->identifier();
80  elem_procs[elem_id] = ep_iter->second;
81  owned_moving_elems.push_back(ep_iter->first);
82  }
83  }
84  // TODO: Determine if this "dumb" greedy approach is adequate and the cost/benefit
85  // of doing something more sophisticated
86 
87  // This reverse traversal of elements overwrites assignment of procs for
88  // dependents resulting in the last assignment winning.
89 
90  // For all dep-rank entities related to migrating elements, pack their info in to
91  // dep_entity_procs.
92  std::map<mesh::EntityId, unsigned> dep_entity_procs;
93  mesh::EntityVector::reverse_iterator r_iter = owned_moving_elems.rbegin(),
94  r_end = owned_moving_elems.rend();
95  for( ; r_end != r_iter; ++r_iter )
96  {
97  const mesh::EntityId elem_id = (*r_iter)->identifier();
98  mesh::EntityVector related_entities;
99  mesh::EntityVector elems(1);
100  elems[0] = *r_iter;
101  stk_classic::mesh::get_entities_through_relations(elems, dep_rank, related_entities);
102  for( size_t j = 0; j < related_entities.size(); ++j ) {
103  dep_entity_procs[related_entities[j]->identifier()] = elem_procs[elem_id];
104  }
105  }
106 
107 
108  std::map<mesh::EntityId, unsigned>::const_iterator c_iter = dep_entity_procs.begin(),
109  c_end = dep_entity_procs.end();
110  for( ; c_end != c_iter; ++c_iter )
111  {
112  mesh::Entity * de = bulk_data.get_entity( dep_rank, c_iter->first );
113  if( parallel_machine_rank(partition->parallel()) == de->owner_rank() )
114  {
115  stk_classic::mesh::EntityProc dep_proc(de, c_iter->second);
116  entity_procs.push_back(dep_proc);
117  }
118  }
119 }
120 
121 
122 bool full_rebalance(mesh::BulkData & bulk_data ,
123  Partition * partition,
124  const stk_classic::mesh::EntityRank rank)
125 {
126  mesh::EntityProcVec cs_elem;
127  bool rebalancingHasOccurred = balance_comm_spec_domain( partition, cs_elem );
128 
129  if(rebalancingHasOccurred && partition->partition_dependents_needed() )
130  {
132 
133  const stk_classic::mesh::EntityRank node_rank = fem_meta.node_rank();
134  const stk_classic::mesh::EntityRank edge_rank = fem_meta.edge_rank();
135  const stk_classic::mesh::EntityRank face_rank = fem_meta.face_rank();
136  const stk_classic::mesh::EntityRank elem_rank = fem_meta.element_rank();
137  const stk_classic::mesh::EntityRank cons_rank = elem_rank+1;
138 
139  // Don't know the rank of the elements rebalanced, assume all are dependent.
140  rebalance_dependent_entities( bulk_data, partition, node_rank, cs_elem, rank );
141  if (stk_classic::mesh::InvalidEntityRank != edge_rank && rank != edge_rank)
142  rebalance_dependent_entities( bulk_data, partition, edge_rank, cs_elem, rank );
143  if (stk_classic::mesh::InvalidEntityRank != face_rank && rank != face_rank)
144  rebalance_dependent_entities( bulk_data, partition, face_rank, cs_elem, rank );
145  if (stk_classic::mesh::InvalidEntityRank != elem_rank && rank != elem_rank)
146  rebalance_dependent_entities( bulk_data, partition, elem_rank, cs_elem, rank );
147  if (stk_classic::mesh::InvalidEntityRank != cons_rank && rank != cons_rank)
148  rebalance_dependent_entities( bulk_data, partition, cons_rank, cs_elem, rank );
149  }
150 
151  if ( rebalancingHasOccurred )
152  {
153  bulk_data.modification_begin();
154  bulk_data.change_entity_owner( cs_elem );
155  bulk_data.modification_end();
156  }
157 
158  //: Finished
159  return rebalancingHasOccurred;
160 }
161 } // namespace
162 
163 
165  const mesh::Selector & selector ,
166  const VectorField * rebal_coord_ref ,
167  const ScalarField * rebal_elem_weight_ref ,
168  Partition & partition,
169  const stk_classic::mesh::EntityRank rank)
170 {
172  const stk_classic::mesh::EntityRank element_rank = (rank != stk_classic::mesh::InvalidEntityRank) ? rank :
173  fem_meta.element_rank();
174 
175  mesh::EntityVector rebal_elem_ptrs;
176  mesh::EntityVector entities;
177 
179  bulk_data.buckets(element_rank),
180  entities);
181 
182  for (mesh::EntityVector::iterator iA = entities.begin() ; iA != entities.end() ; ++iA ) {
183  if(rebal_elem_weight_ref)
184  {
185  double * const w = mesh::field_data( *rebal_elem_weight_ref, **iA );
186  ThrowRequireMsg( NULL != w,
187  "Rebalance weight field is not defined on entities but should be defined on all entities.");
188  // Should this be a throw instead???
189  if ( *w <= 0.0 ) {
190  *w = 1.0 ;
191  }
192  }
193  rebal_elem_ptrs.push_back( *iA );
194  }
195 
196  (&partition)->set_mesh_info(
197  rebal_elem_ptrs,
198  rebal_coord_ref,
199  rebal_elem_weight_ref);
200 
201  bool rebalancingHasOccurred = full_rebalance(bulk_data, &partition, rank);
202 
203  return rebalancingHasOccurred;
204 }
EntityRank face_rank() const
Returns the face rank which changes depending on spatial dimension.
bool rebalance(mesh::BulkData &bulk_data, const mesh::Selector &selector, const VectorField *coord_ref, const ScalarField *elem_weight_ref, Partition &partition, const stk_classic::mesh::EntityRank rank=stk_classic::mesh::InvalidEntityRank)
Rebalance with a Partition object.
Definition: Rebalance.cpp:164
FEMMetaData is a class that implements a Finite Element Method skin on top of the Sierra Tool Kit Met...
Definition: FEMMetaData.hpp:54
virtual int get_new_partition(stk_classic::mesh::EntityProcVec &new_partition)=0
Perform communication to create new partition.
FieldTraits< field_type >::data_type * field_data(const field_type &f, const Bucket::iterator i)
Pointer to the field data array.
Definition: FieldData.hpp:116
void all_reduce_sum(ParallelMachine comm, const double *local, double *global, unsigned count)
Parallel summation to all processors.
ParallelMachine parallel() const
Return the parallel communicator for this partition entity.
Definition: Partition.hpp:111
EntityRank element_rank() const
Returns the element rank which is always equal to spatial dimension.
This is a class for selecting buckets based on a set of meshparts and set logic.
Definition: Selector.hpp:112
const std::vector< Bucket * > & buckets(EntityRank rank) const
Query all buckets of a given entity rank.
Definition: BulkData.hpp:195
Entity * get_entity(EntityRank entity_rank, EntityId entity_id) const
Get entity with a given key.
Definition: BulkData.hpp:211
std::pair< Entity *, unsigned > EntityProc
Pairing of an entity with a processor rank.
Definition: Types.hpp:111
Field with defined data type and multi-dimensions (if any)
Definition: Field.hpp:118
void get_selected_entities(const Selector &selector, const std::vector< Bucket * > &input_buckets, std::vector< Entity * > &entities)
Get entities in selected buckets (selected by the given selector instance), and sorted by ID...
Definition: GetEntities.cpp:77
unsigned parallel_machine_rank(ParallelMachine parallel_machine)
Member function parallel_machine_rank ...
Definition: Parallel.cpp:29
bool modification_end()
Parallel synchronization of modifications and transition to the guaranteed parallel consistent state...
bool modification_begin()
Begin a modification phase during which the mesh bulk data could become parallel inconsistent. This is a parallel synchronous call. The first time this method is called the mesh meta data is verified to be committed and parallel consistent. An exception is thrown if this verification fails.
Definition: BulkData.cpp:172
Manager for an integrated collection of entities, entity relations, and buckets of field data...
Definition: BulkData.hpp:49
virtual bool partition_dependents_needed() const =0
Query whether element dependents need to be rebalanced outside this Partition.
A fundamental unit within the discretization of a problem domain, including but not limited to nodes...
Definition: Entity.hpp:120
Initialized with a list of mesh entities unique to each processor.
Definition: Partition.hpp:81
Sierra Toolkit.
EntityRank edge_rank() const
Returns the edge rank which changes depending on spatial dimension.
void get_entities_through_relations(const std::vector< Entity *> &entities, std::vector< Entity *> &entities_related)
Query which mesh entities have a relation to all of the input mesh entities.
Definition: Relation.cpp:156
void change_entity_owner(const std::vector< EntityProc > &arg_change)
Give away ownership of entities to other parallel processes.
virtual unsigned num_elems() const =0
Return the total number of mesh entities in all lists.
For partitioning of mesh entities over a processing grid.
Static functions for dynamic load balancing.
EntityRank node_rank() const
Returns the node rank, which is always zero.
static FEMMetaData & get(const MetaData &meta)
Getter for FEMMetaData off of a MetaData object.
unsigned owner_rank() const
Parallel processor rank of the processor which owns this entity.
Definition: Entity.hpp:175
virtual void determine_new_partition(bool &RebalancingNeeded)=0
determine New Partition.