src/ck-cp/arrayRedistributor.h

   1 /**
   2
   3     A system for exposing application and runtime "control points"
   4     to the dynamic optimization framework.
   5
   6 */
   7 #ifndef __ARRAYREDISTRIBUTOR_H__
   8 #define __ARRAYREDISTRIBUTOR_H__
   9
  10 #include <vector>
  11 #include <list>
  12 #include <map>
  13 #include <cmath>
  14 //#include "ControlPoints.decl.h"
  15
  16 #include<pup_stl.h>
  17
  18
  19 #if CMK_WITH_CONTROLPOINT
  20
  21
  22 /**
  23  * \addtogroup ControlPointFramework
  24  *   @{
  25  */
  26
  27
  28 /// A message containing a chunk of a data array used when redistributing to a different set of active chares
  29 class redistributor2DMsg : public CMessage_redistributor2DMsg {
  30  public:
  31   int top;
  32   int left;
  33   int height;
  34   int width;
  35   int new_chare_cols;
  36   int  new_chare_rows;
  37   int which_array;
  38   double *data;
  39 };
  40
  41
  42
  43 /// Integer Maximum
  44 static int maxi(int a, int b){
  45   if(a>b)
  46     return a;
  47   else
  48     return b;
  49 }
  50
  51 /// Integer Minimum
  52 static int mini(int a, int b){
  53   if(a<b)
  54     return a;
  55   else
  56     return b;
  57 }
  58
  59
  60 /// A chare group that can redistribute user data arrays. It is used by binding it to a user's Chare Array
  61 class redistributor2D: public CBase_redistributor2D {
  62  public:
  63
  64   std::map<int,double*> data_arrays;
  65   std::map<int,int> data_arrays_sizes;
  66
  67   /// The array associated with this data redistribution
  68   CProxyElement_ArrayElement associatedArray;
  69
  70   int incoming_count;
  71   std::map<int,double*> data_arrays_incoming;
  72   std::map<int,int> data_arrays_incoming_sizes;
  73
  74   /// Is this array element active
  75   bool thisElemActive;
  76
  77   bool resizeGranulesHasBeenCalled;
  78
  79   CkVec<redistributor2DMsg *> bufferedMsgs;
  80
  81  private:
  82
  83
  84   void *fakeMemoryUsage;
  85
  86
  87   CkCallback dataRedistributedCallback;
  88
  89   int x_chares; // number of active chares in x dimension
  90   int y_chares; // number of active chares in y dimension
  91
  92   int data_width;  // The width of the global array, not the local piece
  93   int data_height; // The height of the global array, not the local piece
  94
  95   int data_x_ghost; // The padding in the x dimension on each side of the data
  96   int data_y_ghost; // The padding in the y dimension on each side of the data
  97
  98
  99  public:
 100
 101   void pup(PUP::er &p) {
 102     p | data_arrays_sizes;
 103     p | data_arrays_incoming_sizes;
 104     p | incoming_count;
 105     p | associatedArray;
 106     p | thisElemActive;
 107
 108     p | dataRedistributedCallback;
 109
 110     p | resizeGranulesHasBeenCalled;
 111
 112     p | x_chares;
 113     p | y_chares;
 114     p | data_width;
 115     p | data_height;
 116     p | data_x_ghost;
 117     p | data_y_ghost;
 118
 119     if(p.isPacking() && fakeMemoryUsage!=NULL)
 120       free(fakeMemoryUsage);
 121
 122     fakeMemoryUsage = NULL;
 123
 124     ////////////////////////////////
 125     // when packing, iterate through data_arrays
 126     // when unpacking
 127
 128     {
 129       std::map<int,int>::iterator iter;
 130       for(iter = data_arrays_sizes.begin(); iter != data_arrays_sizes.end(); iter++){
 131         int whichArray = iter->first;
 132         int arraySize = iter->second;
 133
 134         //      CkPrintf("Pupping data array %d\n",whichArray);
 135         p | whichArray;
 136
 137         if(p.isUnpacking())
 138           data_arrays[whichArray] = new double[arraySize];
 139
 140         PUParray(p,data_arrays[whichArray] ,arraySize);
 141
 142         if(p.isPacking())
 143           delete[] data_arrays[whichArray];
 144
 145       }
 146     }
 147
 148
 149     ///////////////////////////////
 150     {
 151       std::map<int,int>::iterator iter;
 152       for(iter = data_arrays_incoming_sizes.begin(); iter != data_arrays_incoming_sizes.end(); iter++){
 153         int whichArray = iter->first;
 154         int arraySize = iter->second;
 155
 156         //      CkPrintf("Pupping incoming array %d\n",whichArray);
 157         p | whichArray;
 158
 159         if(p.isUnpacking() && data_arrays_incoming_sizes[whichArray] > 0)
 160           data_arrays_incoming[whichArray] = new double[arraySize];
 161
 162         PUParray(p,data_arrays_incoming[whichArray],arraySize);
 163
 164         if(p.isPacking())
 165           delete[] data_arrays_incoming[whichArray];
 166
 167       }
 168     }
 169
 170     //    CkPrintf("pup redistributor2D\n");
 171   }
 172
 173
 174   void ckJustMigrated(){
 175     //   CkPrintf("redistributor element %02d %02d migrated to %d", thisIndex.x, thisIndex.y, CkMyPe());
 176   }
 177
 178
 179   // ------------ Some routines for computing the array bounds for this chare  ------------
 180
 181   // The index in the global array for my top row
 182   int top_data_idx();
 183
 184   int bottom_data_idx();
 185
 186   int left_data_idx();
 187
 188   int right_data_idx();
 189
 190   int top_neighbor();
 191
 192   int bottom_neighbor();
 193
 194   int left_neighbor();
 195
 196   int right_neighbor();
 197
 198
 199   /// the width of the non-ghost part of the local partition
 200   int mywidth();
 201
 202
 203   // the height of the non-ghost part of the local partition
 204   int myheight();
 205
 206
 207
 208   // ------------ Some routines for computing the array bounds for arbitrary chares  ------------
 209
 210   int top_data_idx(int y, int y_total){
 211     return (data_height * y) / y_total;
 212   }
 213
 214   int bottom_data_idx(int y, int y_total){
 215     return ((data_height * (y+1)) / y_total) - 1;
 216   }
 217
 218   int left_data_idx(int x, int x_total){
 219     return (data_width * x) / x_total;
 220   }
 221
 222   int right_data_idx(int x, int x_total){
 223     return ((data_width * (x+1)) / x_total) - 1;
 224   }
 225
 226
 227   int top_data_idx(int y){
 228     return (data_height * y) / y_chares;
 229   }
 230
 231   int bottom_data_idx(int y){
 232     return ((data_height * (y+1)) / y_chares) - 1;
 233   }
 234
 235   int left_data_idx(int x){
 236     return (data_width * x) / x_chares;
 237   }
 238
 239   int right_data_idx(int x){
 240     return ((data_width * (x+1)) / x_chares) - 1;
 241   }
 242
 243   /// Return which chare array element(x index) owns the global data item i
 244   int who_owns_idx_x(int i){
 245     int w=0;
 246     while(1){
 247       if( i >= left_data_idx(w) && i <= right_data_idx(w) ){
 248         return w;
 249       }
 250       w++;
 251     }
 252   }
 253
 254   /// Return which chare array element(y index) owns the global data item i
 255   int who_owns_idx_y(int i){
 256     int w=0;
 257     while(1){
 258       if( i >= top_data_idx(w) && i <= bottom_data_idx(w) ){
 259         return w;
 260       }
 261       w++;
 262     }
 263   }
 264
 265
 266
 267
 268
 269   // Convert a local column,row id (0 to mywidth()-1, 0 to myheight()-1) to the index in the padded array
 270   int local_to_padded(int x, int y){
 271     CkAssert(thisElemActive);
 272     CkAssert(x < (mywidth()+data_x_ghost) && x >= (0-data_x_ghost) && y < (myheight()+data_y_ghost) && y >= (0-data_y_ghost) );
 273     return (mywidth()+2*data_x_ghost)*(y+data_y_ghost)+x+data_x_ghost;
 274   }
 275
 276   // get a data value
 277   double data_local(int which, int x, int y){
 278     CkAssert(local_to_padded(x,y) < data_arrays_sizes[which]);
 279     return data_arrays[which][local_to_padded(x,y)];
 280   }
 281
 282
 283   // Convert a local column id (0 to mywidth-1) to the global column id (0 to data_width-1)
 284   int local_to_global_x(int x){
 285     return left_data_idx() + x;
 286   }
 287
 288   // Convert a local row id (0 to myheight-1) to the global row id (0 to data_height-1)
 289   int local_to_global_y(int y){
 290     return top_data_idx() + y;
 291   }
 292
 293   int global_array_width(){
 294     return data_width;
 295   }
 296
 297   int global_array_height(){
 298     return data_height;
 299   }
 300
 301   int global_array_size(){
 302     return global_array_width() * global_array_height();
 303   }
 304
 305   int my_array_width(){
 306     return mywidth()+2*data_x_ghost;
 307   }
 308
 309   int my_array_height(){
 310     return myheight()+2*data_y_ghost;
 311   }
 312
 313   // Total size of arrays including ghost layers
 314   int my_array_size(){
 315     return my_array_width() * my_array_height();
 316   }
 317
 318   /// Create an array. If multiple arrays are needed, each should have its own index
 319   template <typename t> t* createDataArray(int which=0) {
 320     t* data = new t[my_array_size()];
 321     data_arrays[which] = data;
 322     data_arrays_sizes[which] = my_array_size();
 323
 324     if(thisIndex.x==0 && thisIndex.y==0)
 325       CkPrintf("data_arrays_sizes[which] set to %d\n", data_arrays_sizes[which] );
 326
 327
 328     CkAssert(data_arrays[which] != NULL);
 329 #if DEBUG > 2
 330     CkPrintf("Allocated array of size %d at %p\n", my_array_size(), data_arrays[which] );
 331 #endif
 332     return data;
 333   }
 334
 335   template <typename t> t* getDataArray(int which=0) {
 336     return data_arrays[which];
 337   }
 338
 339   /// Constructor takes in the dimensions of the array, including any desired ghost layers
 340   /// The local part of the arrays will have (mywidth+x_ghosts*2)*(myheight+y_ghosts*2) elements
 341   void setInitialDimensions(int width, int height, int x_chares_, int y_chares_, int x_ghosts=0, int y_ghosts=0){
 342     data_width = width;      // These values cannot change after this method is called.
 343     data_height = height;
 344     data_x_ghost = x_ghosts;
 345     data_y_ghost = y_ghosts;
 346
 347     setDimensions(x_chares_, y_chares_);
 348
 349   }
 350
 351
 352   void setDimensions( int x_chares_, int y_chares_){
 353     x_chares = x_chares_;
 354     y_chares = y_chares_;
 355
 356
 357     if( thisIndex.x < x_chares && thisIndex.y < y_chares ){
 358       thisElemActive = true;
 359     } else {
 360       thisElemActive = false;
 361     }
 362
 363   }
 364
 365
 366   redistributor2D(){
 367     incoming_count = 0;
 368     fakeMemoryUsage = NULL;
 369     CkAssert(bufferedMsgs.size() == 0);
 370   }
 371
 372
 373   redistributor2D(CkMigrateMessage*){
 374     CkAssert(bufferedMsgs.size() == 0);
 375   }
 376
 377
 378   void startup(){
 379 #if DEBUG > 3
 380    CkPrintf("redistributor 2D startup %03d,%03d\n", thisIndex.x, thisIndex.y);
 381 #endif
 382
 383     contribute();
 384   }
 385
 386
 387   void printArrays(){
 388 #if DEBUG > 2
 389     CkAssert(data_arrays.size()==2);
 390     for(std::map<int,double*>::iterator diter = data_arrays.begin(); diter != data_arrays.end(); diter++){
 391       int which_array = diter->first;
 392       double *data = diter->second;
 393       CkPrintf("%d,%d data_arrays[%d] = %p\n", thisIndex.x, thisIndex.y, which_array, data);
 394     }
 395 #endif
 396   }
 397
 398
 399   // Called on all elements involved with the new granularity or containing part of the old data
 400   void resizeGranules(int new_active_chare_cols, int new_active_chare_rows){
 401 #if DEBUG>1
 402     CkPrintf("Resize Granules called for elem %d,%d\n", thisIndex.x, thisIndex.y);
 403 #endif
 404
 405     resizeGranulesHasBeenCalled = true;
 406
 407     const bool previouslyActive = thisElemActive;
 408     const int old_top = top_data_idx();
 409     const int old_left = left_data_idx();
 410     const int old_bottom = top_data_idx()+myheight()-1;
 411     const int old_right = left_data_idx()+mywidth()-1;
 412     const int old_myheight = myheight();
 413     const int old_mywidth = mywidth();
 414
 415     setDimensions(new_active_chare_cols, new_active_chare_rows); // update dimensions & thisElemActive
 416
 417     const int new_mywidth = mywidth();
 418     const int new_myheight = myheight();
 419
 420     // Transpose Data
 421     // Assume only one new owner of my data
 422
 423     if(previouslyActive){
 424
 425       // Send all my data to any blocks that will need it
 426
 427       int newOwnerXmin = who_owns_idx_x(old_left);
 428       int newOwnerXmax = who_owns_idx_x(old_right);
 429       int newOwnerYmin = who_owns_idx_y(old_top);
 430       int newOwnerYmax = who_owns_idx_y(old_bottom);
 431
 432       for(int newx=newOwnerXmin; newx<=newOwnerXmax; newx++){
 433         for(int newy=newOwnerYmin; newy<=newOwnerYmax; newy++){
 434
 435           // Determine overlapping region between my data and this destination
 436 #if DEBUG > 2
 437           CkPrintf("newy(%d)*new_myheight(%d)=%d, old_top=%d\n",newy,new_myheight,newy*new_myheight,old_top);
 438 #endif
 439           // global range for overlapping area
 440           int global_top = maxi(top_data_idx(newy),old_top);
 441           int global_left = maxi(left_data_idx(newx),old_left);
 442           int global_bottom = mini(bottom_data_idx(newy),old_bottom);
 443           int global_right = mini(right_data_idx(newx),old_right);
 444           int w = global_right-global_left+1;
 445           int h = global_bottom-global_top+1;
 446
 447           CkAssert(w*h>0);
 448
 449           int x_offset = global_left - old_left;
 450           int y_offset = global_top - old_top;
 451
 452 #if DEBUG > 2
 453           CkPrintf("w=%d h=%d x_offset=%d y_offset=%d\n", w, h, x_offset, y_offset);
 454 #endif
 455
 456           std::map<int,double*>::iterator diter;
 457           for(diter =data_arrays.begin(); diter != data_arrays.end(); diter++){
 458
 459             redistributor2DMsg* msg = new(w*h) redistributor2DMsg;
 460             //      CkPrintf("Created message msg %p\n", msg);
 461
 462             int which_array = diter->first;
 463             double *t = diter->second;
 464             int s = data_arrays_sizes[which_array];
 465
 466             for(int j=0; j<h; j++){
 467               for(int i=0; i<w; i++){
 468                 CkAssert(j*w+i < w*h);
 469                 CkAssert((data_x_ghost*2+old_mywidth)*(j+y_offset+data_y_ghost)+(i+ x_offset+data_x_ghost) < s);
 470                 msg->data[j*w+i] = t[(data_x_ghost*2+old_mywidth)*(j+y_offset+data_y_ghost)+(i+ x_offset+data_x_ghost)];
 471               }
 472             }
 473
 474             msg->top = global_top;
 475             msg->left = global_left;
 476             msg->height = h;
 477             msg->width = w;
 478             msg->new_chare_cols = new_active_chare_cols;
 479             msg->new_chare_rows = new_active_chare_rows;
 480             msg->which_array = which_array;
 481
 482             //      CkPrintf("Sending message msg %p\n", msg);
 483             thisProxy(newx, newy).receiveTransposeData(msg);
 484
 485           }
 486
 487         }
 488
 489
 490       }
 491     }
 492
 493     if(!thisElemActive){
 494 #if DEBUG > 2
 495       CkPrintf("Element %d,%d is no longer active\n", thisIndex.x, thisIndex.y);
 496 #endif
 497
 498       // Free my arrays
 499       for(std::map<int,double*>::iterator diter = data_arrays.begin(); diter != data_arrays.end(); diter++){
 500         int which_array = diter->first;
 501         delete data_arrays[which_array];
 502         data_arrays[which_array] = NULL;
 503         data_arrays_sizes[which_array] = 0;
 504       }
 505       continueToNextStep();
 506
 507     }
 508
 509
 510     // Call receiveTransposeData for any buffered messages.
 511     int size = bufferedMsgs.size();
 512     for(int i=0;i<size;i++){
 513       redistributor2DMsg *msg = bufferedMsgs[i];
 514       //     CkPrintf("Delivering buffered receiveTransposeData(msg=%p) i=%d\n", msg, i);
 515       receiveTransposeData(msg); // this will delete the message
 516     }
 517     bufferedMsgs.removeAll();
 518
 519     int newPe = (thisIndex.y * new_active_chare_cols + thisIndex.x) % CkNumPes();
 520     if(newPe == CkMyPe()){
 521       //      CkPrintf("Keeping %02d , %02d on PE %d\n", thisIndex.x, thisIndex.y, newPe);
 522     }
 523     else{
 524       // CkPrintf("Migrating %02d , %02d to PE %d\n", thisIndex.x, thisIndex.y, newPe);
 525       migrateMe(newPe);
 526     }
 527     // CANNOT CALL ANYTHING AFTER MIGRATE ME
 528   }
 529
 530
 531   void continueToNextStep(){
 532 #if DEBUG > 2
 533     CkPrintf("Elem %d,%d is ready to continue\n", thisIndex.x, thisIndex.y);
 534 #endif
 535
 536     resizeGranulesHasBeenCalled = false;
 537
 538     for(std::map<int,double*>::iterator diter =data_arrays.begin(); diter != data_arrays.end(); diter++){
 539       int which_array = diter->first;
 540       double *data = diter->second;
 541       if( ! ((data==NULL && !thisElemActive) || (data!=NULL && thisElemActive) )){
 542         CkPrintf("[%d] ERROR: ! ((data==NULL && !thisElemActive) || (data!=NULL && thisElemActive) )",CkMyPe());
 543         CkPrintf("[%d] ERROR: data=%p thisElemActive=%d  (perhaps continueToNextStep was called too soon)\n",CkMyPe(), data, (int)thisElemActive );
 544
 545         CkAbort("ERROR");
 546       }
 547     }
 548
 549
 550 #if USE_EXTRAMEMORY
 551 #error NO USE_EXTRAMEMORY ALLOWED YET
 552     if(thisElemActive){
 553
 554       long totalArtificialMemory = controlPoint("Artificial Memory Usage", 100, 500);
 555       long artificialMemoryPerChare = totalArtificialMemory *1024*1024 / x_chares / y_chares;
 556
 557       CkPrintf("Allocating fake memory of %d MB (of the total %d MB) (xchares=%d y_chares=%d)\n", artificialMemoryPerChare/1024/1024, totalArtificialMemory, x_chares, y_chares);
 558       free(fakeMemoryUsage);
 559       fakeMemoryUsage = malloc(artificialMemoryPerChare);
 560       CkAssert(fakeMemoryUsage != NULL);
 561     } else {
 562       free(fakeMemoryUsage);
 563       fakeMemoryUsage = NULL;
 564     }
 565 #endif
 566
 567
 568
 569     incoming_count = 0; // prepare for future granularity change
 570     contribute();
 571   }
 572
 573
 574
 575
 576
 577
 578
 579   void receiveTransposeData(redistributor2DMsg *msg){
 580
 581     // buffer this message until resizeGranules Has Been Called
 582     if(!resizeGranulesHasBeenCalled){
 583       bufferedMsgs.push_back(msg);
 584       //      CkPrintf("Buffering receiveTransposeData(msg=%p)\n", msg);
 585       return;
 586     }
 587
 588     CkAssert(resizeGranulesHasBeenCalled);
 589
 590     int top_new = top_data_idx(thisIndex.y, msg->new_chare_rows);
 591     int bottom_new = bottom_data_idx(thisIndex.y, msg->new_chare_rows);
 592     int left_new = left_data_idx(thisIndex.x, msg->new_chare_cols);
 593     int right_new = right_data_idx(thisIndex.x, msg->new_chare_cols);
 594
 595     int new_height = bottom_new - top_new + 1;
 596     int new_width = right_new - left_new + 1;
 597
 598     if(incoming_count == 0){
 599       // Allocate new arrays
 600       std::map<int,double*>::iterator diter;
 601       for(diter =data_arrays.begin(); diter != data_arrays.end(); diter++){
 602         int w = diter->first;
 603         data_arrays_incoming[w] = new double[(new_width+2*data_x_ghost)*(new_height+2*data_y_ghost)];
 604         data_arrays_incoming_sizes[w] = (new_width+2*data_x_ghost)*(new_height+2*data_y_ghost);
 605
 606         //      CkPrintf("data_arrays_incoming_sizes[%d] set to %d\n", w, data_arrays_incoming_sizes[w] );
 607
 608       }
 609     }
 610
 611
 612     // Copy values from the incoming array to the appropriate place in data_arrays_incoming
 613     // Current top left of my new array
 614
 615
 616     double *localData = data_arrays_incoming[msg->which_array];
 617     int s = data_arrays_incoming_sizes[msg->which_array];
 618
 619     //    CkPrintf("%d,%d data_arrays_incoming.size() = %d\n", thisIndex.x, thisIndex.y, data_arrays_incoming.size() );
 620     //    CkPrintf("msg->which_array=%d   localData=%p   s=%d\n", msg->which_array, localData, s);
 621     CkAssert(localData != NULL);
 622
 623     for(int j=0; j<msg->height; j++){
 624       for(int i=0; i<msg->width; i++){
 625
 626         if( (msg->top+j >= top_new) && (msg->top+j <= bottom_new) && (msg->left+i >= left_new) && (msg->left+i <= right_new) ) {
 627           CkAssert(j*msg->width+i<msg->height*msg->width);
 628           CkAssert((msg->top+j-top_new)*new_width+(msg->left+i-left_new) < new_width*new_height);
 629           CkAssert((msg->top+j-top_new)*new_width+(msg->left+i-left_new) >= 0);
 630
 631           CkAssert((msg->top+j-top_new+data_y_ghost)*(new_width+2*data_x_ghost)+(msg->left+i-left_new+data_x_ghost) < s);
 632           localData[(msg->top+j-top_new+data_y_ghost)*(new_width+2*data_x_ghost)+(msg->left+i-left_new+data_x_ghost)] = msg->data[j*msg->width+i];
 633           incoming_count++;
 634
 635         }
 636
 637       }
 638     }
 639
 640     //    CkPrintf("Deleting message msg %p\n", msg);
 641     delete msg;
 642
 643
 644     if(incoming_count == new_height*new_width*data_arrays.size()){
 645
 646       std::map<int,double*>::iterator diter;
 647       for(diter =data_arrays.begin(); diter != data_arrays.end(); diter++){
 648         int w = diter->first;
 649         delete[] data_arrays[w];
 650         data_arrays[w] = data_arrays_incoming[w];
 651         data_arrays_sizes[w] = data_arrays_incoming_sizes[w];
 652         data_arrays_incoming[w] = NULL;
 653         data_arrays_incoming_sizes[w] = 0;
 654
 655         //        if(thisIndex.x==0 && thisIndex.y==0)
 656           //          CkPrintf("data_arrays_incoming_sizes[%d] set to %d\n",w, data_arrays_incoming_sizes[w] );
 657
 658           //        if(thisIndex.x==0 && thisIndex.y==0)
 659           //  CkPrintf("data_arrays_sizes[%d] set to %d\n",w, data_arrays_sizes[w] );
 660
 661       }
 662
 663       continueToNextStep();
 664     }
 665
 666   }
 667 };
 668
 669 /** @} */
 670 #endif
 671 #endif