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