Sacado Package Browser (Single Doxygen Collection)  Version of the Day
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
view/BoxElemPart.cpp
Go to the documentation of this file.
1 /*
2 //@HEADER
3 // ************************************************************************
4 //
5 // Kokkos: Manycore Performance-Portable Multidimensional Arrays
6 // Copyright (2012) Sandia Corporation
7 //
8 // Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9 // the U.S. Government retains certain rights in this software.
10 //
11 // Redistribution and use in source and binary forms, with or without
12 // modification, are permitted provided that the following conditions are
13 // met:
14 //
15 // 1. Redistributions of source code must retain the above copyright
16 // notice, this list of conditions and the following disclaimer.
17 //
18 // 2. Redistributions in binary form must reproduce the above copyright
19 // notice, this list of conditions and the following disclaimer in the
20 // documentation and/or other materials provided with the distribution.
21 //
22 // 3. Neither the name of the Corporation nor the names of the
23 // contributors may be used to endorse or promote products derived from
24 // this software without specific prior written permission.
25 //
26 // THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27 // EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29 // PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30 // CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31 // EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32 // PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33 // PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34 // LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35 // NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36 // SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37 //
38 // Questions? Contact H. Carter Edwards (hcedwar@sandia.gov)
39 //
40 // ************************************************************************
41 //@HEADER
42 */
43 
44 #include <utility>
45 #include <iostream>
46 #include <sstream>
47 #include <stdexcept>
48 #include <limits>
49 #include <BoxElemPart.hpp>
50 
51 //----------------------------------------------------------------------------
52 
53 namespace Kokkos {
54 namespace Example {
55 
56 void box_partition( const unsigned global_size ,
57  const unsigned global_rank ,
58  const unsigned global_box[][2] ,
59  unsigned box[][2] )
60 {
61  box[0][0] = global_box[0][0] ; box[0][1] = global_box[0][1] ;
62  box[1][0] = global_box[1][0] ; box[1][1] = global_box[1][1] ;
63  box[2][0] = global_box[2][0] ; box[2][1] = global_box[2][1] ;
64 
65  unsigned ip = 0 ;
66  unsigned np = global_size ;
67 
68  while ( 1 < np ) {
69 
70  // P = [ ip + j * portion , ip + ( j + 1 ) * portion )
71 
72  unsigned jip , jup ;
73 
74  {
75  const unsigned part = ( 0 == ( np % 5 ) ) ? 5 : (
76  ( 0 == ( np % 3 ) ) ? 3 : 2 );
77 
78  const unsigned portion = np / part ;
79 
80  if ( 2 < part || global_rank < ip + portion ) {
81  jip = portion * size_t( double( global_rank - ip ) / double(portion) );
82  jup = jip + portion ;
83  }
84  else {
85  jip = portion ;
86  jup = np ;
87  }
88  }
89 
90  // Choose axis with largest count:
91 
92  const unsigned nb[3] = {
93  box[0][1] - box[0][0] ,
94  box[1][1] - box[1][0] ,
95  box[2][1] - box[2][0] };
96 
97  const unsigned axis = nb[2] > nb[1] ? ( nb[2] > nb[0] ? 2 : 0 )
98  : ( nb[1] > nb[0] ? 1 : 0 );
99 
100  box[ axis ][1] = box[ axis ][0] + unsigned( double(nb[axis]) * ( double(jup) / double(np) ));
101  box[ axis ][0] = box[ axis ][0] + unsigned( double(nb[axis]) * ( double(jip) / double(np) ));
102 
103  np = jup - jip ;
104  ip = ip + jip ;
105  }
106 }
107 
108 } /* namespace Example */
109 } /* namespace Kokkos */
110 
111 //----------------------------------------------------------------------------
112 
113 namespace Kokkos {
114 namespace Example {
115 
116 void BoxElemPart::local( const unsigned rank ,
117  unsigned uses_elem[][2] ,
118  unsigned owns_node[][2] ,
119  unsigned uses_node[][2] ) const
120 {
122 
124 
125  for ( unsigned i = 0 ; i < 3 ; ++i ) {
126  owns_node[i][0] = uses_elem[i][0] ;
127  owns_node[i][1] = uses_elem[i][1] + ( m_global_elem_box[i][1] == uses_elem[i][1] ? 1 : 0 );
128  }
129  }
130  else {
131 
132  const unsigned global_vert[3][2] =
133  { { 0 , m_global_elem_box[0][1] + 1 },
134  { 0 , m_global_elem_box[1][1] + 1 },
135  { 0 , m_global_elem_box[2][1] + 1 } };
136 
137  Kokkos::Example::box_partition( m_global_size , rank , global_vert , owns_node );
138 
139  for ( unsigned i = 0 ; i < 3 ; ++i ) {
140  uses_elem[i][0] = global_vert[i][0] == owns_node[i][0] ? owns_node[i][0] : owns_node[i][0] - 1 ;
141  uses_elem[i][1] = global_vert[i][1] == owns_node[i][1] ? owns_node[i][1] - 1 : owns_node[i][1] ;
142  }
143  }
144 
145  for ( unsigned i = 0 ; i < 3 ; ++i ) {
146  uses_node[i][0] = uses_elem[i][0] ;
147  uses_node[i][1] = uses_elem[i][1] + 1 ;
148  }
149 
151  for ( unsigned i = 0 ; i < 3 ; ++i ) {
152  owns_node[i][0] = 2 * owns_node[i][0] ;
153  uses_node[i][0] = 2 * uses_node[i][0] ;
154  owns_node[i][1] = 2 * owns_node[i][1] - 1 ;
155  uses_node[i][1] = 2 * uses_node[i][1] - 1 ;
156  }
157  }
158 }
159 
161  const BoxElemPart::ElemOrder elem_order ,
162  const BoxElemPart::Decompose decompose ,
163  const unsigned global_size ,
164  const unsigned global_rank ,
165  const unsigned elem_nx ,
166  const unsigned elem_ny ,
167  const unsigned elem_nz )
168 {
169  m_global_size = global_size ;
170  m_global_rank = global_rank ;
171  m_elem_order = elem_order ;
172  m_decompose = decompose ;
173 
174  m_global_elem_box[0][0] = 0 ; m_global_elem_box[0][1] = elem_nx ;
175  m_global_elem_box[1][0] = 0 ; m_global_elem_box[1][1] = elem_ny ;
176  m_global_elem_box[2][0] = 0 ; m_global_elem_box[2][1] = elem_nz ;
177 
178  m_global_node_box[0][0] = 0 ; m_global_node_box[0][1] = 0 ;
179  m_global_node_box[1][0] = 0 ; m_global_node_box[1][1] = 0 ;
180  m_global_node_box[2][0] = 0 ; m_global_node_box[2][1] = 0 ;
181 
182  if ( ElemLinear == elem_order ) {
183  m_global_node_box[0][1] = elem_nx + 1 ;
184  m_global_node_box[1][1] = elem_ny + 1 ;
185  m_global_node_box[2][1] = elem_nz + 1 ;
186  }
187  else if ( ElemQuadratic == elem_order ) {
188  m_global_node_box[0][1] = 2 * elem_nx + 1 ;
189  m_global_node_box[1][1] = 2 * elem_ny + 1 ;
190  m_global_node_box[2][1] = 2 * elem_nz + 1 ;
191  }
192 
193  //----------------------------------------
194 
196 
199 
200  //----------------------------------------
201 
202  size_t elem_count = Kokkos::Example::box_count( m_uses_elem_box );
203  size_t node_count = Kokkos::Example::box_count( m_owns_node_box[0] );
204 
205  m_owns_node[0][0] = global_rank ;
206  m_owns_node[0][1] = node_count ;
207  m_owns_node_count = 1 ;
208  m_send_node_count = 0 ;
209 
210  for ( unsigned rr = 1 ; rr < m_global_size ; ++rr ) {
211 
212  const unsigned rank = ( m_global_rank + rr ) % m_global_size ;
213 
214  unsigned elem_box[3][2] , o_node_box[3][2] , u_node_box[3][2] ;
215 
216  // Boxes for process 'rank'
217  local( rank , elem_box , o_node_box , u_node_box );
218 
219  // Box that this process uses but is owned by process 'rank'
221 
223 
224  if ( m_owns_node[ m_owns_node_count ][1] ) {
225  m_owns_node[ m_owns_node_count ][0] = rank ;
227  }
228 
229  // Box that this process owns and is used by process 'rank'
231 
233 
234  if ( m_send_node[ m_send_node_count ][1] ) {
235  m_send_node[ m_send_node_count ][0] = rank ;
237  }
238 
239  // Error checking:
240 
241  unsigned test_box[3][2] ;
242 
243  elem_count += Kokkos::Example::box_count( elem_box );
244  node_count += Kokkos::Example::box_count( o_node_box );
245 
246  {
247  Kokkos::Example::box_intersect( test_box , m_owns_node_box[0] , o_node_box );
248 
249  if ( Kokkos::Example::box_count( test_box ) ) {
250  std::cout << "owns_node[" << m_global_rank << "]{"
251  << " [" << m_owns_node_box[0][0][0] << "," << m_owns_node_box[0][0][1] << ")"
252  << " [" << m_owns_node_box[0][1][0] << "," << m_owns_node_box[0][1][1] << ")"
253  << " [" << m_owns_node_box[0][2][0] << "," << m_owns_node_box[0][2][1] << ")"
254  << "} intersects"
255  << " owns_node[" << rank << "]{"
256  << " [" << o_node_box[0][0] << "," << o_node_box[0][1] << ")"
257  << " [" << o_node_box[1][0] << "," << o_node_box[1][1] << ")"
258  << " [" << o_node_box[2][0] << "," << o_node_box[2][1] << ")"
259  << "}" << std::endl ;
260  }
261  }
262 
263  if ( DecomposeElem == decompose ) {
264 
265  Kokkos::Example::box_intersect( test_box , m_uses_elem_box , elem_box );
266 
267  if ( Kokkos::Example::box_count( test_box ) ) {
268 
269  std::cout << "ElemBox[" << m_global_rank << "]{"
270  << " [" << m_uses_elem_box[0][0] << "," << m_uses_elem_box[0][1] << ")"
271  << " [" << m_uses_elem_box[1][0] << "," << m_uses_elem_box[1][1] << ")"
272  << " [" << m_uses_elem_box[2][0] << "," << m_uses_elem_box[2][1] << ")"
273  << "} intersects"
274  << " ElemBox[" << rank << "]{"
275  << " [" << elem_box[0][0] << "," << elem_box[0][1] << ")"
276  << " [" << elem_box[1][0] << "," << elem_box[1][1] << ")"
277  << " [" << elem_box[2][0] << "," << elem_box[2][1] << ")"
278  << "}" << std::endl ;
279  }
280  }
281  }
282 
283  // Sentinal values at the end of the owns and send lists:
284 
285  m_owns_node[ m_owns_node_count ][0] = ~0u ;
286  m_owns_node[ m_owns_node_count ][1] = ~0u ;
287  m_owns_node_box[ m_owns_node_count ][0][0] = 0u ; m_owns_node_box[ m_owns_node_count ][0][0] = ~0u ;
288  m_owns_node_box[ m_owns_node_count ][1][0] = 0u ; m_owns_node_box[ m_owns_node_count ][1][0] = ~0u ;
289  m_owns_node_box[ m_owns_node_count ][2][0] = 0u ; m_owns_node_box[ m_owns_node_count ][2][0] = ~0u ;
290 
291  m_send_node[ m_send_node_count ][0] = ~0u ;
292  m_send_node[ m_send_node_count ][1] = ~0u ;
293  m_send_node_box[ m_send_node_count ][0][0] = 0u ; m_send_node_box[ m_send_node_count ][0][0] = ~0u ;
294  m_send_node_box[ m_send_node_count ][1][0] = 0u ; m_send_node_box[ m_send_node_count ][1][0] = ~0u ;
295  m_send_node_box[ m_send_node_count ][2][0] = 0u ; m_send_node_box[ m_send_node_count ][2][0] = ~0u ;
296 
297  {
298  size_t count = 0 ;
299  for ( unsigned i = 0 ; i < m_owns_node_count ; ++i ) {
300  count += m_owns_node[i][1] ;
301  }
302  if ( count != Kokkos::Example::box_count( m_uses_node_box ) ) {
303  std::cout << "Node uses count = " << Kokkos::Example::box_count( m_uses_node_box )
304  << " error count = " << count << std::endl ;
305  }
306  }
307 
308  if ( global_node_count != node_count ) {
309  std::cout << "Node count = " << global_node_count << " overlap error count = " << node_count << std::endl ;
310  }
311 
312  if ( DecomposeElem == decompose && global_elem_count != elem_count ) {
313  std::cout << "Elem count = " << global_elem_count << " overlap error count = " << elem_count << std::endl ;
314  }
315 }
316 
317 void BoxElemPart::print( std::ostream & s ) const
318 {
319  s << "BoxElemPart P[" << m_global_rank << ":" << m_global_size << "]"
320  << std::endl
321  << " elem_box {"
322  << " [" << m_uses_elem_box[0][0] << "," << m_uses_elem_box[0][1] << ")"
323  << " [" << m_uses_elem_box[1][0] << "," << m_uses_elem_box[1][1] << ")"
324  << " [" << m_uses_elem_box[2][0] << "," << m_uses_elem_box[2][1] << ")"
325  << " } / {"
326  << " [" << m_global_elem_box[0][0] << "," << m_global_elem_box[0][1] << ")"
327  << " [" << m_global_elem_box[1][0] << "," << m_global_elem_box[1][1] << ")"
328  << " [" << m_global_elem_box[2][0] << "," << m_global_elem_box[2][1] << ")"
329  << " }"
330  << std::endl
331  << " node_box {"
332  << " [" << m_owns_node_box[0][0][0] << "," << m_owns_node_box[0][0][1] << ")"
333  << " [" << m_owns_node_box[0][1][0] << "," << m_owns_node_box[0][1][1] << ")"
334  << " [" << m_owns_node_box[0][2][0] << "," << m_owns_node_box[0][2][1] << ")"
335  << " } / {"
336  << " [" << m_uses_node_box[0][0] << "," << m_uses_node_box[0][1] << ")"
337  << " [" << m_uses_node_box[1][0] << "," << m_uses_node_box[1][1] << ")"
338  << " [" << m_uses_node_box[2][0] << "," << m_uses_node_box[2][1] << ")"
339  << " } / {"
340  << " [" << m_global_node_box[0][0] << "," << m_global_node_box[0][1] << ")"
341  << " [" << m_global_node_box[1][0] << "," << m_global_node_box[1][1] << ")"
342  << " [" << m_global_node_box[2][0] << "," << m_global_node_box[2][1] << ")"
343  << " }"
344  << std::endl ;
345 
346  for ( unsigned i = 1 ; i < m_owns_node_count ; ++i ) {
347  s << " P[" << m_owns_node[i][0] << "]"
348  << " recv node_box {"
349  << " [" << m_owns_node_box[i][0][0] << "," << m_owns_node_box[i][0][1] << ")"
350  << " [" << m_owns_node_box[i][1][0] << "," << m_owns_node_box[i][1][1] << ")"
351  << " [" << m_owns_node_box[i][2][0] << "," << m_owns_node_box[i][2][1] << ")"
352  << " }"
353  << std::endl ;
354  }
355 
356  for ( unsigned i = 0 ; i < m_send_node_count ; ++i ) {
357  s << " P[" << m_send_node[i][0] << "]"
358  << " send node_box {"
359  << " [" << m_send_node_box[i][0][0] << "," << m_send_node_box[i][0][1] << ")"
360  << " [" << m_send_node_box[i][1][0] << "," << m_send_node_box[i][1][1] << ")"
361  << " [" << m_send_node_box[i][2][0] << "," << m_send_node_box[i][2][1] << ")"
362  << " }"
363  << std::endl ;
364  }
365 }
366 
367 } /* namespace Example */
368 } /* namespace Kokkos */
369 
370 //----------------------------------------------------------------------------
371 
372 
unsigned m_owns_node[PROC_NEIGH_MAX][2]
KOKKOS_INLINE_FUNCTION size_t global_elem_count() const
void print(std::ostream &s) const
BoxElemPart(const ElemOrder elem_order, const Decompose decompose, const unsigned global_size, const unsigned global_rank, const unsigned elem_nx, const unsigned elem_ny, const unsigned elem_nz)
KOKKOS_INLINE_FUNCTION size_t box_count(const unsigned box[][2])
Definition: BoxElemPart.hpp:69
unsigned m_send_node_box[PROC_NEIGH_MAX][3][2]
void box_partition(const unsigned global_size, const unsigned global_rank, const unsigned global_box[][2], unsigned box[][2])
Definition: BoxElemPart.cpp:56
KOKKOS_INLINE_FUNCTION void box_intersect(unsigned box[][2], const unsigned boxA[][2], const unsigned boxB[][2])
Definition: BoxElemPart.hpp:57
unsigned m_send_node[PROC_NEIGH_MAX][2]
unsigned m_owns_node_box[PROC_NEIGH_MAX][3][2]
unsigned m_global_elem_box[3][2]
unsigned m_global_node_box[3][2]
void local(const unsigned rank, unsigned uses_elem[][2], unsigned owns_node[][2], unsigned uses_node[][2]) const
KOKKOS_INLINE_FUNCTION size_t global_node_count() const