Home My Page Projects Code Snippets Project Openings diderot
Summary Activity Tracker Tasks SCM

SCM Repository

[diderot] Diff of /branches/lamont/src/compiler/c-target/fragments/par-kdtree.in
ViewVC logotype

Diff of /branches/lamont/src/compiler/c-target/fragments/par-kdtree.in

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 2573, Mon Mar 31 16:05:10 2014 UTC revision 2574, Mon Mar 31 17:20:11 2014 UTC
# Line 6  Line 6 
6          printTree(newNode->left);          printTree(newNode->left);
7      }      }
8  }  }
9    /* Swaps the values at two addresses */
10    void Diderot_KDTree_SwapValuesUInt(uint32_t * a, uint32_t *b){
11        uint32_t temp;
12        temp = *a;
13        *a = *b;
14        *b = temp;
15    }
16    /* Swaps the values at two addresses */
17    void Diderot_KDTree_SwapValues(int * a, int *b){
18        int temp;
19        temp = *a;
20        *a = *b;
21        *b = temp;
22    }
23  /* sequential version of the merge sort for the spatial indices */  /* sequential version of the merge sort for the spatial indices */
24  /*void Diderot_Spatial_SeqMergeSort(@PREFIX@World_t *wrld, uint32_t * indices, uint32_t * tmpIndices, int low, int high, uint32_t dim)  void Diderot_Spatial_SeqMergeSort(@PREFIX@World_t *wrld, uint32_t * indices, uint32_t * tmpIndices, int low, int high, uint32_t dim)
25  {  {
26    
27          if (low >= high)          if (low >= high)
# Line 24  Line 37 
37          // Once temporary indice array contains the two sorted sub-arrays          // Once temporary indice array contains the two sorted sub-arrays
38          // they are merged into indice array          // they are merged into indice array
39      Diderot_Spatial_SeqMerge(wrld,indices,tmpIndices,low, mid, mid + 1, high,low,dim);      Diderot_Spatial_SeqMerge(wrld,indices,tmpIndices,low, mid, mid + 1, high,low,dim);
40  }*/  }
41  /* sequential version of the merge operation for the spatial indices */  /* sequential version of the merge operation for the spatial indices */
42  /* Note: Sub-arrays are adjacent to each other in the  /* Note: Sub-arrays are adjacent to each other in the
43     the sequential version but not necessarily for the parallel version;     the sequential version but not necessarily for the parallel version;
44     therefore, sub-arrays boundaries must be specified     therefore, sub-arrays boundaries must be specified
45     explicitly.*/     explicitly.*/
46  /*void Diderot_Spatial_SeqMerge(@PREFIX@World_t *wrld, uint32_t * indices, uint32_t * tmpIndices, int lowL, int highL, int lowR, int highR, int low, uint32_t dim)  void Diderot_Spatial_SeqMerge(@PREFIX@World_t *wrld, uint32_t * indices, uint32_t * tmpIndices, int lowL, int highL, int lowR, int highR, int low, uint32_t dim)
47  {  {
48          int high = low + highL - lowL + highR - lowR + 1;          int high = low + highL - lowL + highR - lowR + 1;
49    
# Line 84  Line 97 
97                  high = mid;                  high = mid;
98          }          }
99          return low;          return low;
100  }*/  }
101  /* Assigns a worker to perform a spatial task (merge sort, merge,or tree node construction) */  /* Assigns a worker to perform a spatial task (merge sort, merge,or tree node construction) */
102  SpatialWorkerArgs_t * Diderot_Grab_SpatailWorker(SpatialScheduler_t* sched,ParSpatialWorkerType workerType,void * nodeData, bool * donePtr){  SpatialWorkerArgs_t * Diderot_Grab_SpatailWorker(SpatialScheduler_t* sched,ParSpatialWorkerType workerType,void * nodeData, bool * donePtr){
103    
# Line 109  Line 122 
122      return retWorker;      return retWorker;
123  }  }
124  /* parallel version of the merge sort for the spatial indices */  /* parallel version of the merge sort for the spatial indices */
125  /*void Diderot_Spatial_ParMergeSort(@PREFIX@World_t *wrld,SpatialScheduler_t * sched,uint32_t * indices, uint32_t * tmpIndices, int low, int high, int depth, uint32_t  dim)  void Diderot_Spatial_ParMergeSort(@PREFIX@World_t *wrld,SpatialScheduler_t * sched,uint32_t * indices, uint32_t * tmpIndices, int low, int high, int depth, uint32_t  dim)
126  {  {
127          bool isDone = false;          bool isDone = false;
128      // If the depth is less than zero or there's not enough work to perform in parallel      // If the depth is less than zero or there's not enough work to perform in parallel
# Line 150  Line 163 
163                  Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices,low, mid, mid + 1, high, low, depth,dim);                  Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices,low, mid, mid + 1, high, low, depth,dim);
164            }            }
165    
166  }*/  }
167  /* parallel version of the merge operation for the spatial indices */  /* parallel version of the merge operation for the spatial indices */
168  /*void Diderot_Spatial_ParMerge(@PREFIX@World_t *wrld,SpatialScheduler_t * sched,uint32_t * indices, uint32_t * tmpIndices,int lowL, int highL, int lowR, int highR, int low, int depth, int dim)  void Diderot_Spatial_ParMerge(@PREFIX@World_t *wrld,SpatialScheduler_t * sched,uint32_t * indices, uint32_t * tmpIndices,int lowL, int highL, int lowR, int highR, int low, int depth, int dim)
169  {  {
170      int nL = highL - lowL + 1;      int nL = highL - lowL + 1;
171      int nR = highR - lowR + 1;      int nR = highR - lowR + 1;
# Line 218  Line 231 
231                      pthread_mutex_unlock (&worker->lock);                      pthread_mutex_unlock (&worker->lock);
232             }             }
233     }     }
234  }*/  }
235  /*The worker function for all the workers */  /*The worker function for all the workers */
236  void treeWorker(SpatialWorkerArgs_t * workerArg){  void treeWorker(SpatialWorkerArgs_t * workerArg){
237    
# Line 236  Line 249 
249                       workerArg->sched->jobsRunning -=1;                       workerArg->sched->jobsRunning -=1;
250                  }else {                  }else {
251                      workerArg->sched->buildIsDone = true;                      workerArg->sched->buildIsDone = true;
252                    //  printTree(workerArg->wrld->spatialTree->root);                      printTree(workerArg->wrld->spatialTree->root);
253                      for(unsigned int i = 0; i < workerArg->sched->numWorkers; i++){                      for(unsigned int i = 0; i < workerArg->sched->numWorkers; i++){
254                          if(i != workerArg->id)                          if(i != workerArg->id)
255                              pthread_cond_signal (&workerArg->sched->workerData[i].runWait);                              pthread_cond_signal (&workerArg->sched->workerData[i].runWait);
# Line 300  Line 313 
313          }          }
314  }  }
315  /* Finds the median strand in an array of strands based on the given axis*/  /* Finds the median strand in an array of strands based on the given axis*/
316  /*@STRANDTY@ * find_median(@PREFIX@World_t *wrld, SpatialScheduler_t * sched, int start, int end, int idx, int * mid){  @STRANDTY@ * find_median_sort(@PREFIX@World_t *wrld, SpatialScheduler_t * sched, int start, int end, int idx, int * mid){
317    
318          int startIdx = start + (idx * wrld->numStrands);          int startIdx = start + (idx * wrld->numStrands);
319          int endIdx = end + (idx * wrld->numStrands);          int endIdx = end + (idx * wrld->numStrands);
# Line 311  Line 324 
324                  *mid = start;                  *mid = start;
325                  return wrld->inState[wrld->spatialIndices[startIdx]];                  return wrld->inState[wrld->spatialIndices[startIdx]];
326          }          }
327  int count = 0;  /*int count = 0;
328  bool error=false;  bool error=false;
329     for(int i = startIdx + 1; i < endIdx; i++){     for(int i = startIdx + 1; i < endIdx; i++){
330    
# Line 323  Line 336 
336            }            }
337            count++;            count++;
338      }      }
339    
340      if(error)      if(error)
341          exit(1);          exit(1); */
342          *mid = start + (end-start)/2;          *mid = start + (end-start)/2;
343      if(midIdx >  (2 * wrld->numStrands)) {      /*if(midIdx >  (2 * wrld->numStrands)) {
344          printf("MidIdx is bigger = %d\n",midIdx);          printf("MidIdx is bigger = %d\n",midIdx);
345          exit(1);          exit(1);*/
     }  
346          return wrld->inState[wrld->spatialIndices[midIdx]];          return wrld->inState[wrld->spatialIndices[midIdx]];
347  }*/  }
348  /*void preSort(@PREFIX@World_t *wrld, SpatialScheduler_t * sched,int start, int len, int axis)  void preSort(@PREFIX@World_t *wrld, SpatialScheduler_t * sched,int start, int len, int axis)
349  {  {
350      if(!len) return;      if(!len) return;
351      int startIdx = start + (axis * wrld->numStrands);      int startIdx = start + (axis * wrld->numStrands);
# Line 344  Line 357 
357      int mid = start + ((start + len)-start)/2;      int mid = start + ((start + len)-start)/2;
358      preSort(wrld,sched,start,mid - start, axis);      preSort(wrld,sched,start,mid - start, axis);
359      preSort(wrld,sched,mid + 1,start + len - (mid+ 1), axis);      preSort(wrld,sched,mid + 1,start + len - (mid+ 1), axis);
 }*/  
   
 /* Swaps the values at two addresses */  
 void Diderot_KDTree_SwapValues(uint32_t * a, uint32_t *b){  
     int temp;  
     temp = *a;  
     *a = *b;  
     *b = temp;  
360  }  }
361    
362  @STRANDTY@ * find_median(@PREFIX@World_t *wrld,int start, int end, int dim){  @STRANDTY@ * find_median(@PREFIX@World_t *wrld,int start, int end, int dim){
363    
364      if(end <= start) return NULL;      if(end <= start) return NULL;
# Line 366  Line 372 
372    
373          //printf("Pivot = %f\n",pivot);          //printf("Pivot = %f\n",pivot);
374    
375          Diderot_KDTree_SwapValues(&wrld->spatialIndices[mid],&wrld->spatialIndices[end -1]);          Diderot_KDTree_SwapValuesUInt(&wrld->spatialIndices[mid],&wrld->spatialIndices[end -1]);
376    
377          for (store = curr = start; curr < end; curr++) {          for (store = curr = start; curr < end; curr++) {
378              Diderot_real_t currVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[curr]],dim);              Diderot_real_t currVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[curr]],dim);
379              if (currVal < pivot) {              if (currVal < pivot) {
380                  if (curr != store)                  if (curr != store)
381                      Diderot_KDTree_SwapValues(&wrld->spatialIndices[curr], &wrld->spatialIndices[store]);                      Diderot_KDTree_SwapValuesUInt(&wrld->spatialIndices[curr], &wrld->spatialIndices[store]);
382                  store++;                  store++;
383              }              }
384          }          }
385          Diderot_KDTree_SwapValues(&wrld->spatialIndices[store],&wrld->spatialIndices[end -1]);          Diderot_KDTree_SwapValuesUInt(&wrld->spatialIndices[store],&wrld->spatialIndices[end -1]);
386    
387          /* median has duplicate values */          /* median has duplicate values */
388          Diderot_real_t storeVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[store]],dim);          Diderot_real_t storeVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[store]],dim);
# Line 470  Line 476 
476     // double spatialTotalTimeS = (airTime() - spatialST0);     // double spatialTotalTimeS = (airTime() - spatialST0);
477      // if(spatialTotalTimeS >= 0.03)      // if(spatialTotalTimeS >= 0.03)
478      //    printf("maybe fixed parallel time to sort=%f\n",spatialTotalTimeS);      //    printf("maybe fixed parallel time to sort=%f\n",spatialTotalTimeS);
479     // double spatialST0 = airTime();      double spatialST0 = airTime();
480     // preSort(wrld,sched,0,*(tree->numOfStrands),0);      preSort(wrld,sched,0,*(tree->numOfStrands),0);
481     // double spatialTotalTimeS = (airTime() - spatialST0);     double spatialTotalTimeS = (airTime() - spatialST0);
482      // if(spatialTotalTimeS >= 0.03)      // if(spatialTotalTimeS >= 0.03)
483       //   printf("maybe fixed parallel time to sort=%f\n",spatialTotalTimeS);      printf("maybe fixed parallel time to sort=%f\n",spatialTotalTimeS);
   
484    
485        exit(1);
486      tree->root = Diderot_KDTree_BuildHelper(wrld, wrld->spatialSched,0,*(tree->numOfStrands),0);      tree->root = Diderot_KDTree_BuildHelper(wrld, wrld->spatialSched,0,*(tree->numOfStrands),0);
487     // printf("!!!!!!DONE!!!!\n");     // printf("!!!!!!DONE!!!!\n");
488      pthread_mutex_lock(&sched->lock);      pthread_mutex_lock(&sched->lock);

Legend:
Removed from v.2573  
changed lines
  Added in v.2574

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0