Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
hit_topology.c
Go to the documentation of this file.
1 
16 /*
17  * <license>
18  *
19  * Hitmap v1.2
20  *
21  * This software is provided to enhance knowledge and encourage progress in the scientific
22  * community. It should be used only for research and educational purposes. Any reproduction
23  * or use for commercial purpose, public redistribution, in source or binary forms, with or
24  * without modifications, is NOT ALLOWED without the previous authorization of the copyright
25  * holder. The origin of this software must not be misrepresented; you must not claim that you
26  * wrote the original software. If you use this software for any purpose (e.g. publication),
27  * a reference to the software package and the authors must be included.
28  *
29  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS "AS IS" AND ANY
30  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
31  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
32  * THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
33  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
34  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
36  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
37  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38  *
39  * Copyright (c) 2007-2015, Trasgo Group, Universidad de Valladolid.
40  * All rights reserved.
41  *
42  * More information on http://trasgo.infor.uva.es/
43  *
44  * </license>
45 */
46 
47 #include <stdio.h>
48 #include <math.h>
49 #include <stdlib.h>
50 
51 #include <hit_topology.h>
52 #include <hit_com.h>
53 
54 /* INTEGER POWER OF 2 MACRO*/
55 #define pow2(x) ( 1<<(x) )
56 
57 
58 /* EXTERN VARIABLES */
59 /* 1.2 PHYSICAL TOPOLOGY: TO BE INITIALIZED BY THE SPECIFIC PARALLEL INTERFACE FUNCTION */
60 HitPTopology *HIT_TOPOLOGY_INFO = NULL;
61 
62 /* 1.3 NULL TOPOLOGY */
63 HitPTopology HIT_PTOPOLOGY_NULL = HIT_PTOPOLOGY_NULL_STATIC;
65 
66 /* 2.2 NULL VRANKS */
69 
70 /* 2.3. CONSTANT FOR THE LEADER */
71 HitRanks HIT_RANK_LEADER = {{0,0,0,0}};
72 
73 /* 3.1. MPI: DUPLICATE COMMUNICATOR FOR A DUPLICATED TOPOLOGY */
74 HitPTopology *hit_ptopDup( HitPTopology *in ) {
75  if ( in != NULL ) in->numUses ++;
76  return in;
77 }
78 
79 /* 3.2. MPI: SPLIT COMMUNICATOR FOR TOPOLOGIES WITH GROUPS, OR NON-ACTIVE PROCESSORS */
80 HitPTopology *hit_ptopSplit( HitPTopology *in, int group ) {
81  if ( in == NULL ) return in;
82 
83  HitPTopology *ptopo;
84  // @arturo Ago 2015: New allocP interface
85  // hit_malloc( ptopo, sizeof( HitPTopology ),HitPTopology*);
86  hit_malloc( ptopo, HitPTopology, 1 );
87  *ptopo = HIT_PTOPOLOGY_NULL;
88 
89 
90  int result = MPI_Comm_split( in->comm, group, in->selfRank, &(ptopo->comm) );
91  hit_mpiTestError( result, "Error using MPI_Comm_split" );
92  MPI_Comm_rank( ptopo->comm, &(ptopo->selfRank) );
93  MPI_Comm_size( ptopo->comm, &(ptopo->numProcs) );
94 
95  // @arturo 2015/01/03
96  ptopo->next = in;
97  ptopo->global = in->global;
98  // @arturo 2015/01/07
99  MPI_Group globalGroup, localGroup;
100  MPI_Comm_group( in->global->comm, &globalGroup );
101  MPI_Comm_group( ptopo->comm, &localGroup ),
102  MPI_Group_difference( globalGroup, localGroup, &(ptopo->antiCommGroup) );
103 
104  ptopo->numUses = 1;
105  return ptopo;
106 }
107 
108 /* 3.3. MPI: FREE PTOPOLOGY */
109 void hit_ptopFree( HitPTopology **in ) {
110  if ( (*in) == NULL )
111  hit_errInternal( __FUNCTION__, "Trying to free a null pointer", "", __FILE__, __LINE__);
112 
113 #ifdef DEBUG
114 fprintf(stderr, "hit_ptopFree PTOP %d, %d, %d\n", (*in)->numUses, (*in)->selfRank, (*in)->numProcs );
115 #endif
116 
117  if ( (*in)->numUses < 1 )
118  hit_errInternal( __FUNCTION__, "Trying to free a null physical topology", "", __FILE__, __LINE__);
119 
120  ((*in)->numUses)--;
121  if ( (*in)->numUses < 1 ) {
122  MPI_Comm_free( &((*in)->comm) );
123  hit_free( *in );
124  *in = NULL;
125  }
126 }
127 
128 /* 4. FREE TOPOLOGY */
129 void hit_topFree( HitTopology topo ) {
130  if ( topo.pTopology == NULL )
131  hit_errInternal( __FUNCTION__, "Trying to free a null topology", "", __FILE__, __LINE__);
132 
133  hit_ptopFree( &(topo.pTopology) );
134 }
135 
136 
137 /* 5. Hit PREDEFINED TOPOLOGY FUNCTIONS */
138 /* 5.1 Hit PLAIN TOPOLOGY */
139 HitTopology hit_topology_plug_topPlain( HitPTopology *ptopo ) {
141 
142  res.type = HIT_TOPOLOGY_PLAIN;
143  res.numDims = 1;
144  res.card[0] = ptopo->numProcs;
145  res.self.rank[0] = ptopo->selfRank;
146  // @arturo 2015/01/22
147  //res.linearRank = ptopo->selfRank;
148  res.active = ( ptopo->selfRank < ptopo->numProcs ) ? 1 : 0;
149 
150  res.pTopology = hit_ptopDup( ptopo );
151 
152  return res;
153 }
154 
155 /* 5.2. Hit PLAIN TOPOLOGY WHICH RESTRICTS NUMBER OF ACTIVE PROCESSORS TO A POWER OF 2 */
158 
160  res.numDims = 1;
161 
162  res.card[0] = (int)( pow2( (int)log2( ptopo->numProcs ) ) );
163  res.self.rank[0] = ptopo->selfRank;
164  // @arturo 2015/01/22
165  //res.linearRank = ptopo->selfRank;
166  res.active = ( ptopo->selfRank < res.card[0] ) ? 1 : 0;
167 
168  /* IF NOT ALL PROCESSORS ARE ACTIVE, SPLIT PHISICAL TOPOLOGY */
169  if ( res.card[0] == ptopo->numProcs ) res.pTopology = hit_ptopDup( ptopo );
170  else res.pTopology = hit_ptopSplit( ptopo, res.active );
171 
172  return res;
173 }
174 
175 /* 5.3. Hit SQUARE TOPOLOGY */
176 HitTopology hit_topology_plug_topSquare( HitPTopology *ptopo ) {
178 
180 
181  /* SQUARE ROOT OF NUM PROCS. */
182  double dsize = sqrt( (double)(ptopo->numProcs) );
183  int size = (int)dsize;
184 
185  /* DIMENSIONS AND SIZES */
186  res.numDims = 2;
187  res.card[0] = size;
188  res.card[1] = size;
189 
190  /* GET FIRST COORDINATE */
191  // @arturo 2015/01/22
192  //res.linearRank = ptopo->selfRank;
193  res.self.rank[0] = ptopo->selfRank / size;
194  res.self.rank[1] = ptopo->selfRank % size;
195  res.active = ( res.self.rank[0] < size ) ? 1 : 0;
196 
197  /* IF NOT ALL PROCESSORS ARE ACTIVE, SPLIT PHISICAL TOPOLOGY */
198  if ( dsize == (double)size ) res.pTopology = hit_ptopDup( ptopo );
199  else res.pTopology = hit_ptopSplit( ptopo, res.active );
200 
201  /* RETURN RESULT */
202  return res;
203 }
204 
205 
206 /* 5.4. Hit COMPLETE 2D ARRAY TOPOLOGY */
210 
211  int low, high;
212  int product;
213 
214  /* 1. START AS NEAR AS POSSIBLE TO THE SQUARE ROOT */
215  low = high = (int)sqrt( (double)(ptopo->numProcs) );
216  product = low*high;
217 
218  /* 2. MOVE UP/DOWN TO SEARCH THE NEAREST FACTORS */
219  while ( product != ptopo->numProcs ) {
220  if (product < ptopo->numProcs) {
221  high++;
222  product = product + low;
223  }
224  else {
225  low--;
226  if (low==1) { high=ptopo->numProcs; product=ptopo->numProcs; }
227  else product = product - high;
228  }
229  }
230 
231  /* 3. BUILD RESULT */
232  res.numDims = 2;
233  res.card[0] = high;
234  res.card[1] = low;
235  res.self.rank[0] = ptopo->selfRank / low;
236  res.self.rank[1] = ptopo->selfRank % low;
237  // @arturo 2015/01/22
238  //res.linearRank = ptopo->selfRank;
239  res.active = ( res.self.rank[0] < res.card[0] ) ? 1 : 0;
240 
241  res.pTopology = hit_ptopDup( ptopo );
242 
243  /* 4. RETURN RESULT */
244  return res;
245 }
246 
247 
248 /* 5.5. Hit NAS ARRAY TOPOLOGY */
249 HitTopology hit_topology_plug_topArrayDims( HitPTopology *ptopo , int dims ) {
250 
253 
254  int cards[dims];
255  int oldcards[dims];
256  int logs[dims];
257  int logn;
258  int i,j;
259  int goon;
260  int product;
261 
262 
263  /* LOG2 of number of processors */
264  logn = (int)floor(log((double)(ptopo->numProcs))/log(2.0));
265 
266  /* Assign the log2 to the dimensions */
267  for(i=0;i<dims;i++){
268  logs[i] = logn / dims + ((logn % dims > i) ? 1 : 0 );
269  cards[i] = pow2(logs[i]);
270  }
271 
272  /* Assign the rest of the processors */
273  do{
274  /* Set old cards */
275  for(i=0;i<dims;i++) oldcards[i] = cards[i];
276 
277  /* Increase one dimension if possible */
278  for(i=0;i<dims;i++){
279  product = 1;
280  for(j=0;j<dims;j++){
281  product *= cards[j] + ( j == i ? 1 : 0 );
282  }
283  if( product <= ptopo->numProcs ) cards[i]++;
284  }
285 
286  /* Check out condition */
287  goon = 0;
288  for(i=0;i<dims;i++){
289  if(cards[i] != oldcards[i]) goon = 1;
290  }
291 
292  } while(goon);
293 
294  /* 3. BUILD RESULT */
295  res.numDims = dims;
296  for(i=0;i<dims;i++) res.card[i] = cards[i];
297 
298  res.self = hit_topRanksInternal(res,ptopo->selfRank);
299  // @arturo 2015/01/22
300  //res.linearRank = ptopo->selfRank;
301 
302  /* Check if active */
303  product = 1;
304  for(i=0;i<dims;i++){
305  product *= cards[i];
306  }
307  res.active = ( ptopo->selfRank < product ) ? 1 : 0;
308 
309  /* IF NOT ALL PROCESSORS ARE ACTIVE, SPLIT PHISICAL TOPOLOGY */
310  if ( product == ptopo->numProcs ) res.pTopology = hit_ptopDup( ptopo );
311  else res.pTopology = hit_ptopSplit( ptopo, res.active );
312 
313  /* 4. RETURN RESULT */
314  return res;
315 }
316 
317 
318 /* 5.6 Hit DUMMY TOPOLOGY*/
319 HitTopology hit_topology_plug_topDummyDims( HitPTopology *ptopo, int dims, int* virprocelems ) {
320 
322 
323  if (dims > HIT_MAXDIMS)
324  hit_errInternal( __FUNCTION__, "Trying to use a number of dimensions greater above the maximum\n. Increment HIT_MAXDIMS and recompile Hitmap", "", __FILE__, __LINE__);
325 
326  if (dims == 0)
327  hit_errInternal( __FUNCTION__, "You cannot define a number of dimensions equal to zero", "", __FILE__, __LINE__);
328 
330  res.numDims = 1;
331  int i;
332  for (i = 0; (i < dims)||(i < HIT_MAXDIMS); i++)
333  res.card[i] = virprocelems[i];
334 
335  for (i = 0; (i < dims)||(i < HIT_MAXDIMS); i++)
336  res.self.rank[i] = 0; //XXX
337 
338  int totalProcNumber=1;
339  for (i = 0; (i < dims)||(i < HIT_MAXDIMS); i++)
340  totalProcNumber *= virprocelems[i]; //FIXME ¿qué pasa si el numero de elementos que nos pasan en una dimension dada es cero?
341 
342  res.active = 1;
343 
344  //Since hit_layout_wrapper checks if the pTopology is null,
345  // we will have to fake it.
346  HitPTopology *ptopo2;
347 
348  hit_malloc( ptopo2, HitPTopology, 1 );
349  *ptopo2 = HIT_PTOPOLOGY_NULL;
350  ptopo2->numUses = 1;
351  ptopo2->numProcs = totalProcNumber;
352  ptopo2->selfRank = 0;
353  ptopo2->comm = MPI_COMM_SELF; //This is a hack since hit_ptopoIsNull() from hit_layout_wrapper checks if the comm is MPI_COMM_NULL
354  res.pTopology = ptopo2;
355 
356  return res;
357 }
358 
359 
360 /* 6.1. TOPOLOGY CARDINALITY */
362 
363  // @arturo Feb 2013: BUG Corrected, For NULL TOPOLOGY it should return 0
364  if ( hit_topDims(topo) < 1 ) return 0;
365 
366  int card = 1;
367  int i;
368  for(i=0;i<hit_topDims(topo);i++){
369  card *= hit_topDimCard(topo, i);
370  }
371  return card;
372 }
373 
374 
375 /* 6.2. COMPUTE NEIGHBORS */
376 int hit_topDimNeighbor( HitTopology topo, int dim, int shift ) {
377  /* 1. OUT OF DIMENSION */
378  if ( dim < 0 || dim > topo.numDims-1 ) return HIT_RANK_NULL;
379 
380  /* 2. OUT OF RANGE FOR NON-PERIODIC */
381  int newDimRank = topo.self.rank[dim] + shift;
382  // @arturo 2015/01/22
383  //if ( ! topo.periods[dim] && ( newDimRank < 0 || newDimRank > topo.card[dim]-1 ) )
384  if ( newDimRank < 0 || newDimRank > topo.card[dim]-1 )
385  return HIT_RANK_NULL;
386 
387  /* 3. ADJUST PERIODIC */
388  // @arturo 2015/01/22
389  /*
390  if ( topo.periods[dim] && newDimRank < 0 ) newDimRank = newDimRank + topo.card[dim];
391  else if ( topo.periods[dim] && newDimRank > topo.card[dim]-1 )
392  newDimRank = newDimRank - topo.card[dim];
393  */
394 
395  /* 4. COMPUTE NEIGHBOUR RANK */
396  int acumCard = 1;
397  int newRank = 0;
398  int i;
399  for ( i=topo.numDims-1; i>=0; i--) {
400  /* IF COMPUTING THE SELECTED DIMENSION: USE THE NEW NEIGHBOUR RANK */
401  if ( i == dim ) newRank = newRank + newDimRank * acumCard;
402  /* ELSE, THE ORIGINAL RANK */
403  else newRank = newRank + topo.self.rank[i] * acumCard;
404 
405  /* UPDATE ACUMULATED CARDINALITY */
406  acumCard = acumCard * topo.card[i];
407  }
408 
409  /* 5. RETURN NEW RANK */
410  return newRank;
411 }
412 
413 
414 /* 6.3. MULTIDIMENSIONAL RANKS TO LINEAL */
416 
417  if(hit_ranksCmp(ranks,HIT_RANKS_NULL)) return HIT_RANK_NULL;
418 
419  int linear = 0;
420  int acumCard = 1;
421 
422  int dim;
423 
424  for(dim=topo.numDims-1; dim>=0; dim--) {
425  if (ranks.rank[dim] == HIT_RANK_NULL) return HIT_RANK_NULL;
426  linear = linear + acumCard * ranks.rank[dim];
427  acumCard = acumCard * topo.card[dim];
428  }
429 
430  // @arturo 2015/01/07 Skip inactive processors out of the geometry
431  if ( linear < 0 || linear >= acumCard ) return HIT_RANK_NULL;
432 
433  return linear;
434 }
435 
436 
437 /* 6.4. LINEAL TO MULTIDIMENSIONAL RANKS */
438 HitRanks hit_topRanksInternal( HitTopology topo, int linealRank ){
439 
440  if (linealRank == HIT_RANK_NULL) return HIT_RANKS_NULL;
441  // @arturo 2015/01/07 Skip inactive processors out of the geometry
442  if (linealRank < 0) return HIT_RANKS_NULL;
443 
444  HitRanks res = HIT_RANKS_NULL;
445  int acumCard;
446  int dim;
447 
448  acumCard = 1;
449  for(dim=topo.numDims-1; dim>=0; dim--) {
450  res.rank[dim] = (linealRank / acumCard) % topo.card[dim];
451  acumCard *= topo.card[dim];
452  }
453 
454  // @arturo 2015/01/07 Skip inactive processors out of the geometry
455  if ( linealRank >= acumCard ) return HIT_RANKS_NULL;
456 
457  return res;
458 }
459 
HitTopology hit_topology_plug_topSquare(HitPTopology *topo)
Definition: hit_topology.c:176
#define hit_free(ptr)
Definition: hit_allocP.h:152
HitPTopology HIT_PTOPOLOGY_NULL
Definition: hit_topology.c:63
HitRanks HIT_RANK_LEADER
Definition: hit_topology.c:71
HitTopology hit_topology_plug_topPlainPower2(HitPTopology *topo)
Definition: hit_topology.c:156
HitPTopology * hit_ptopSplit(HitPTopology *in, int group)
Definition: hit_topology.c:80
#define HIT_TOPOLOGY_DUMMYDIMS
Definition: hit_topology.h:281
int hit_topRankInternal(HitTopology topo, HitRanks ranks)
Definition: hit_topology.c:415
#define hit_topDimCard(topo, i)
Definition: hit_topology.h:413
int rank[HIT_MAXDIMS]
Definition: hit_topology.h:135
HitPTopology * pTopology
Definition: hit_topology.h:253
HitPTopology * HIT_TOPOLOGY_INFO
Definition: hit_topology.c:60
#define HIT_TOPOLOGY_ARRAY2DCOMP
Definition: hit_topology.h:271
HitTopology hit_topology_plug_topDummyDims(HitPTopology *topo, int dims, int *virprocelems)
Definition: hit_topology.c:319
#define HIT_RANK_NULL_STATIC
Definition: hit_topology.h:144
HitRanks HIT_RANKS_NULL
Definition: hit_topology.c:68
#define pow2(x)
Definition: hit_topology.c:55
#define hit_ranksCmp(a, b)
Definition: hit_topology.h:220
#define HIT_MAXDIMS
Definition: hit_shape.h:72
int HIT_RANK_NULL
Definition: hit_topology.c:67
HitPTopology * hit_ptopDup(HitPTopology *in)
Definition: hit_topology.c:74
HitRanks self
Definition: hit_topology.h:249
int dims[2]
Definition: SWpar_ref.c:187
#define HIT_TOPOLOGY_PLAIN_POWER2
Definition: hit_topology.h:287
#define hit_topDims(topo)
Definition: hit_topology.h:407
HitRanks hit_topRanksInternal(HitTopology topo, int linealRank)
Definition: hit_topology.c:438
#define hit_mpiTestError(ok, cad)
Definition: hit_com.h:62
#define HIT_TOPOLOGY_ARRAYDIMS
Definition: hit_topology.h:276
void hit_topFree(HitTopology topo)
Definition: hit_topology.c:129
int size[2]
Definition: SWcommon.c:57
HitTopology hit_topology_plug_topPlain(HitPTopology *topo)
Definition: hit_topology.c:139
#define hit_malloc(ptr, type, nmemb)
Definition: hit_allocP.h:93
void hit_ptopFree(HitPTopology **in)
Definition: hit_topology.c:109
HitTopology hit_topology_plug_topArrayDims(HitPTopology *topo, int dims)
Definition: hit_topology.c:249
#define HIT_TOPOLOGY_PLAIN
Definition: hit_topology.h:261
int card[HIT_MAXDIMS]
Definition: hit_topology.h:246
int hit_topDimNeighbor(HitTopology topo, int dim, int shift)
Definition: hit_topology.c:376
int hit_topCard(HitTopology topo)
Definition: hit_topology.c:361
#define HIT_RANKS_NULL_STATIC
Definition: hit_topology.h:154
#define HIT_TOPOLOGY_SQUARE
Definition: hit_topology.h:266
HitTopology hit_topology_plug_topArray2DComplete(HitPTopology *topo)
Definition: hit_topology.c:207
HitTopology HIT_TOPOLOGY_NULL
Definition: hit_topology.c:64
#define HIT_TOPOLOGY_NULL_STATIC
Definition: hit_topology.h:298
#define hit_errInternal(routine, text, extraParam, file, numLine)
Definition: hit_error.h:63