00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027 #include "VRB.h"
00028 #include "Utility/PAssert.h"
00029
00030 #ifdef __VRB_DIAGNOSTIC__
00031 #include <stdio.h>
00032 #include <stdlib.h>
00033 #endif
00034
00035
00036
00037
00038
00039 static void
00040 recurseCoordinateVRB(int dim,
00041 const int *strides, const int* sizes, const int *offsets,
00042 int nprocs, int firstProc, int *procs );
00043
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068 void
00069 vnodeRecursiveBisection(int dim, const int *sizes, int nprocs, int *procs)
00070 {
00071 int i;
00072
00073
00074 int *offsets = new int[dim];
00075 for (i=0; i<dim; ++i)
00076 offsets[i] = 0;
00077
00078
00079 int *strides = new int[dim];
00080 strides[dim-1] = 1;
00081 for (i=dim-2; i>=0; --i)
00082 strides[i] = strides[i+1]*sizes[i+1];
00083
00084
00085 recurseCoordinateVRB(dim,strides,sizes,offsets,nprocs,0,procs);
00086
00087
00088 delete [] offsets;
00089 delete [] strides;
00090 }
00091
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107 static void
00108 assign(int dim, const int *strides, const int *sizes, const int *offsets,
00109 int x, int *procs)
00110 {
00111
00112 PAssert(dim>0);
00113 PAssert(sizes);
00114 PAssert(offsets);
00115 PAssert(procs);
00116
00117 int i;
00118
00119 #ifdef __VRB__DIAGNOSTIC__
00120 printf("---------- assign ----------\n");
00121 printf("dim=%d, sizes=",dim);
00122 for (i=0; i<dim; ++i)
00123 printf(" %d",sizes[i]);
00124 printf(", offsets=");
00125 for (i=0; i<dim; ++i)
00126 printf(" %d",offsets[i]);
00127 printf(", strides=");
00128 for (i=0; i<dim; ++i)
00129 printf(" %d",strides[i]);
00130 printf(", procs=%lx\n",procs);
00131 printf("----------------------------\n");
00132 #endif
00133
00134
00135 if ( dim==1 )
00136
00137 for (int i=0; i<sizes[0]; ++i)
00138 procs[offsets[0]+i] = x;
00139
00140
00141 else
00142 {
00143
00144 for (i=0; i<sizes[0]; ++i)
00145 assign(dim-1,strides+1,sizes+1,offsets+1,x,procs+(offsets[0]+i)*strides[0]);
00146 }
00147 }
00148
00150
00151
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166
00167
00168 static void
00169 recurseCoordinateVRB(int dim,
00170 const int* strides, const int* sizes, const int *offsets,
00171 int nprocs, int firstProc, int *procs )
00172 {
00173
00174 PAssert(dim>0);
00175 PAssert(sizes);
00176 PAssert(nprocs>0);
00177 PAssert(procs);
00178 PAssert(firstProc>=0);
00179 for (int i=0; i<dim; ++i)
00180 {
00181 PAssert(sizes[i]>0);
00182 PAssert(offsets[i]>=0);
00183 }
00184
00185 #ifdef __VRB_DIAGNOSTIC__
00186 printf("---------- RecurseCoordinateVRB ----------\n");
00187 printf("dim= %d, sizes=",dim);
00188 for (i=0; i<dim; ++i)
00189 printf(" %d",sizes[i]);
00190 printf(", offsets=");
00191 for (i=0; i<dim; ++i)
00192 printf(" %d",offsets[i]);
00193 printf(", nprocs= %d, firstProc= %d\n",nprocs,firstProc);
00194 printf("------------------------------------------\n");
00195 #endif
00196
00197
00198 if ( nprocs == 1 )
00199 {
00200
00201
00202 assign(dim,strides,sizes,offsets,firstProc,procs);
00203 }
00204
00205
00206
00207
00208 else
00209 {
00210 int d;
00211
00212
00213 int totalVnodes = sizes[0];
00214 for (d=1; d<dim; ++d)
00215 totalVnodes *= sizes[d];
00216 PAssert(totalVnodes>=nprocs);
00217
00218
00219 int leftProcs = nprocs/2;
00220 int rightProcs = nprocs-leftProcs;
00221
00222
00223
00224 int splitDim = 0;
00225 for (d=1; d<dim; ++d)
00226 if ( sizes[d] > sizes[splitDim] )
00227 splitDim = d;
00228
00229
00230 int splitSize = sizes[splitDim];
00231
00232
00233
00234
00235
00236
00237 int leftVnodes = 0;
00238
00239
00240 double outOfBalance = splitSize/(double)rightProcs;
00241
00242
00243
00244 int crossSize = 1;
00245 for (d=0; d<dim; ++d)
00246 if ( d != splitDim )
00247 crossSize *= sizes[d];
00248
00249
00250 for (int l=1; l<splitSize; ++l)
00251 {
00252
00253 int r = splitSize - l;
00254 double b = l/(double)leftProcs - r/(double)rightProcs;
00255
00256
00257 if ( b<0 )
00258 b=-b;
00259
00260
00261
00262
00263
00264 if ( (b < outOfBalance) &&
00265 (l*crossSize>=leftProcs) &&
00266 (r*crossSize>=rightProcs) )
00267 {
00268
00269 leftVnodes = l;
00270 outOfBalance = b;
00271 }
00272 }
00273
00274
00275 PAssert(leftVnodes>0);
00276
00277
00278
00279
00280
00281 int *newSizes = new int[dim];
00282 for (d=0; d<dim; ++d)
00283 newSizes[d] = sizes[d];
00284
00285
00286 int *newOffsets = new int[dim];
00287 for (d=0; d<dim; ++d)
00288 newOffsets[d] = offsets[d];
00289
00290
00291 newSizes[splitDim] = leftVnodes;
00292
00293
00294 recurseCoordinateVRB(dim,strides,newSizes,newOffsets,leftProcs,firstProc,procs);
00295
00296
00297 newSizes[splitDim] = splitSize - leftVnodes;
00298 newOffsets[splitDim] += leftVnodes;
00299
00300
00301 recurseCoordinateVRB(dim,strides,newSizes,newOffsets,rightProcs,firstProc+leftProcs,procs);
00302
00303
00304 delete [] newSizes;
00305 delete [] newOffsets;
00306 }
00307 }
00308
00310
00311 #ifdef __VRB_DIAGNOSTIC__
00312
00313
00314
00315
00316
00317 static void
00318 print(int dim, const int *sizes, const int *procs)
00319 {
00320 if ( dim == 1 )
00321 {
00322 for ( int i=0; i<*sizes; ++i)
00323 printf("%4d",procs[i]);
00324 }
00325 else
00326 {
00327 int skip = 1;
00328 int i;
00329 for (i=1; i<dim; ++i)
00330 skip *= sizes[i];
00331 for (i=0; i<sizes[0]; ++i)
00332 {
00333 print(dim-1,sizes+1,procs+skip*i);
00334 printf("\n");
00335 }
00336 printf("\n");
00337 }
00338 }
00339
00341
00342 int
00343 main(int argc, char *argv[])
00344 {
00345
00346 int dim = argc-2;
00347 PAssert(dim>0);
00348
00349
00350 int nprocs = atoi(argv[1]);
00351 PAssert(nprocs>0);
00352
00353
00354 int *sizes = new int[dim];
00355 int totalVnodes = 1;
00356 for ( int d = 0; d<dim; ++d )
00357 {
00358 sizes[d] = atoi(argv[d+2]);
00359 totalVnodes *= sizes[d];
00360 }
00361 int *procs = new int[totalVnodes];
00362
00363
00364 vnodeRecursiveBisection(dim,sizes,nprocs,procs);
00365
00366
00367 print(dim,sizes,procs);
00368
00369 return 0;
00370 }
00371
00372 #endif
00373
00374
00375
00376
00377
00378