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 2571, Thu Mar 27 13:56:00 2014 UTC revision 2572, Sat Mar 29 18:10:27 2014 UTC
# Line 8  Line 8 
8  }  }
9    
10  /* sequential version of the merge sort for the spatial indices */  /* sequential version of the merge sort for the spatial indices */
11  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)
12  {  {
13    
14          if (low >= high)          if (low >= high)
# Line 24  Line 24 
24          // Once temporary indice array contains the two sorted sub-arrays          // Once temporary indice array contains the two sorted sub-arrays
25          // they are merged into indice array          // they are merged into indice array
26      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);
27  }  }*/
28  /* sequential version of the merge operation for the spatial indices */  /* sequential version of the merge operation for the spatial indices */
29  /* Note: Sub-arrays are adjacent to each other in the  /* Note: Sub-arrays are adjacent to each other in the
30     the sequential version but not necessarily for the parallel version;     the sequential version but not necessarily for the parallel version;
31     therefore, sub-arrays boundaries must be specified     therefore, sub-arrays boundaries must be specified
32     explicitly.*/     explicitly.*/
33  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)
34  {  {
35          int high = low + highL - lowL + highR - lowR + 1;          int high = low + highL - lowL + highR - lowR + 1;
36    
37      //Note: The offset is needed for the way the tree is built. We need to make sure the next axis to be sorted      //Note: The offset is needed for the way the tree is built. We need to make sure the next axis to be sorted
38      //has a duplicate copy of the current sorted axis      //has a duplicate copy of the current sorted axis
39          int offSet = (dim + 1) * wrld->numStrands;      int offSet = (dim + 1) == wrld->spatialTree->dim ? -(dim * wrld->numStrands) : ((dim + 1) * wrld->numStrands);
     bool setOffSet = (dim + 1) != wrld->spatialTree->dim;  
40      // Bottom-up implementation      // Bottom-up implementation
41          for (;low <= high; low++)          for (;low <= high; low++)
42          {          {
43                          if (lowL > highL){                          if (lowL > highL){
44                                  indices[low] = tmpIndices[lowR];                                  indices[low] = tmpIndices[lowR];
                 if(setOffSet){  
45                          indices[low + offSet] = tmpIndices[lowR];                          indices[low + offSet] = tmpIndices[lowR];
46                                      tmpIndices[low + offSet] = tmpIndices[lowR];                                      tmpIndices[low + offSet] = tmpIndices[lowR];
                 }  
47                                  lowR++;                                  lowR++;
48                          }else if (lowR > highR) {                          }else if (lowR > highR) {
49                                  indices[low] = tmpIndices[lowL];                                  indices[low] = tmpIndices[lowL];
                 if(setOffSet){  
50                                      indices[low + offSet] = tmpIndices[lowL];                                      indices[low + offSet] = tmpIndices[lowL];
51                                      tmpIndices[low + offSet] = tmpIndices[lowL];                                      tmpIndices[low + offSet] = tmpIndices[lowL];
                 }  
52                                  lowL++;                                  lowL++;
53                          }else {                          }else {
54                                  Diderot_real_t lowLValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowL]],dim);                                  Diderot_real_t lowLValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowL]],dim);
55                                  Diderot_real_t lowRValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowR]],dim);                                  Diderot_real_t lowRValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowR]],dim);
56                                  if(lowLValue < lowRValue){                                  if(lowLValue < lowRValue){
57                                          indices[low] = tmpIndices[lowL];                                          indices[low] = tmpIndices[lowL];
                                         if(setOffSet){  
58                         indices[low + offSet] = tmpIndices[lowL];                         indices[low + offSet] = tmpIndices[lowL];
59                                             tmpIndices[low + offSet] = tmpIndices[lowL];                                             tmpIndices[low + offSet] = tmpIndices[lowL];
                     }  
60                                          lowL++;                                          lowL++;
61                                  }else {                                  }else {
62                                          indices[low] = tmpIndices[lowR];                                          indices[low] = tmpIndices[lowR];
                                         if(setOffSet) {  
63                         indices[low + offSet] = tmpIndices[lowR];                         indices[low + offSet] = tmpIndices[lowR];
64                                             tmpIndices[low + offSet] = tmpIndices[lowR];                                             tmpIndices[low + offSet] = tmpIndices[lowR];
                     }  
65                                          lowR++;                                          lowR++;
66                                  }                                  }
67                          }                          }
68          }          }
69  }  }
 /* Swaps the values at two addresses */  
 void Diderot_KDTree_SwapValues(int * a, int *b){  
         int temp;  
         temp = *a;  
         *a = *b;  
         *b = temp;  
 }  
70  int Diderot_BinarySearch(@PREFIX@World_t *wrld,uint32_t *tmpIndices, int low, int high, Diderot_real_t searchValue, int dim)  int Diderot_BinarySearch(@PREFIX@World_t *wrld,uint32_t *tmpIndices, int low, int high, Diderot_real_t searchValue, int dim)
71  {  {
72                  if(low > high + 1)                  if(low > high + 1)
# Line 100  Line 84 
84                  high = mid;                  high = mid;
85          }          }
86          return low;          return low;
87  }  }*/
88  /* 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) */
89  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){
90    
# Line 125  Line 109 
109      return retWorker;      return retWorker;
110  }  }
111  /* parallel version of the merge sort for the spatial indices */  /* parallel version of the merge sort for the spatial indices */
112  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)
113  {  {
114          bool isDone = false;          bool isDone = false;
115      // 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 166  Line 150 
150                  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);
151            }            }
152    
153  }  }*/
154  /* parallel version of the merge operation for the spatial indices */  /* parallel version of the merge operation for the spatial indices */
155  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)
156  {  {
157      int nL = highL - lowL + 1;      int nL = highL - lowL + 1;
158      int nR = highR - lowR + 1;      int nR = highR - lowR + 1;
# Line 201  Line 185 
185    
186          indices[mid] = tmpIndices[midL];          indices[mid] = tmpIndices[midL];
187    
         if((dim + 1) < wrld->spatialTree->dim)  
         {  
188               //Note: The offset is needed for the way the tree is built. We need to make sure the next axis to be sorted               //Note: The offset is needed for the way the tree is built. We need to make sure the next axis to be sorted
189               //has a duplicate copy of the current sorted axis               //has a duplicate copy of the current sorted axis
190               int offSet = ((dim + 1) * wrld->numStrands);          int offSet = (dim + 1) == wrld->spatialTree->dim ? -(dim * wrld->numStrands) : ((dim + 1) * wrld->numStrands);
191              indices[mid + offSet] = tmpIndices[midL];              indices[mid + offSet] = tmpIndices[midL];
192              tmpIndices[mid + offSet] = tmpIndices[midL];              tmpIndices[mid + offSet] = tmpIndices[midL];
         }  
193    
194          depth--;          depth--;
195    
# Line 237  Line 218 
218                      pthread_mutex_unlock (&worker->lock);                      pthread_mutex_unlock (&worker->lock);
219             }             }
220     }     }
221  }  }*/
222  /*The worker function for all the workers */  /*The worker function for all the workers */
223  void treeWorker(SpatialWorkerArgs_t * workerArg){  void treeWorker(SpatialWorkerArgs_t * workerArg){
224    
# Line 273  Line 254 
254          //Based on the worker type perform the assigned task.          //Based on the worker type perform the assigned task.
255              if(workerArg->workerType == MERGESORT_WORKER){              if(workerArg->workerType == MERGESORT_WORKER){
256                      MergetSortNode_t * node = (MergetSortNode_t *)workerArg->data;                      MergetSortNode_t * node = (MergetSortNode_t *)workerArg->data;
257                          Diderot_Spatial_ParMergeSort(workerArg->wrld,                          /*Diderot_Spatial_ParMergeSort(workerArg->wrld,
258                                                    workerArg->sched,                                                    workerArg->sched,
259                                                    node->indices,                                                    node->indices,
260                                                    node->tmpIndices,                                                    node->tmpIndices,
261                                                        node->low,                                                        node->low,
262                                                        node->high,                                                        node->high,
263                                                        node->depth,                                                        node->depth,
264                                                        node->dim);                                                        node->dim);*/
265    
266              }else if(workerArg->workerType == MERGE_WORKER) {              }else if(workerArg->workerType == MERGE_WORKER) {
267                      MergeNode_t * node = (MergeNode_t *)workerArg->data;                      MergeNode_t * node = (MergeNode_t *)workerArg->data;
268                      Diderot_Spatial_ParMerge(workerArg->wrld,                    /*  Diderot_Spatial_ParMerge(workerArg->wrld,
269                                                workerArg->sched,                                                workerArg->sched,
270                                                node->indices,                                                node->indices,
271                                                node->tmpIndices,                                                node->tmpIndices,
# Line 294  Line 275 
275                                                node->highR,                                                node->highR,
276                                                node->low,                                                node->low,
277                                                node->depth,                                                node->depth,
278                                                node->dim);                                                node->dim);*/
279              }else if(workerArg->workerType == TREE_WORKER){              }else if(workerArg->workerType == TREE_WORKER){
280                      KDNode_t*  node = (KDNode_t  *)workerArg->data;                      KDNode_t*  node = (KDNode_t  *)workerArg->data;
281                 /* if((node->start + node->len)- 1> workerArg->wrld->numStrands || node->strandId  > workerArg->wrld->numStrands){                 /* if((node->start + node->len)- 1> workerArg->wrld->numStrands || node->strandId  > workerArg->wrld->numStrands){
# Line 319  Line 300 
300          }          }
301  }  }
302  /* 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*/
303  @STRANDTY@ * find_median(@PREFIX@World_t *wrld, SpatialScheduler_t * sched, int start, int end, int idx, int * mid){  /*@STRANDTY@ * find_median(@PREFIX@World_t *wrld, SpatialScheduler_t * sched, int start, int end, int idx, int * mid){
304    
305          int startIdx = start + (idx * wrld->numStrands);          int startIdx = start + (idx * wrld->numStrands);
306          int endIdx = end + (idx * wrld->numStrands);          int endIdx = end + (idx * wrld->numStrands);
# Line 330  Line 311 
311                  *mid = start;                  *mid = start;
312                  return wrld->inState[wrld->spatialIndices[startIdx]];                  return wrld->inState[wrld->spatialIndices[startIdx]];
313          }          }
314  /* int count = 0;  int count = 0;
315  bool error=false;  bool error=false;
316     for(int i = startIdx + 1; i < endIdx; i++){     for(int i = startIdx + 1; i < endIdx; i++){
317    
# Line 343  Line 324 
324            count++;            count++;
325      }      }
326      if(error)      if(error)
327          exit(1); */          exit(1);
328          *mid = start + (end-start)/2;          *mid = start + (end-start)/2;
329     /* if(midIdx >  (2 * wrld->numStrands)) {      if(midIdx >  (2 * wrld->numStrands)) {
330          printf("MidIdx is bigger = %d\n",midIdx);          printf("MidIdx is bigger = %d\n",midIdx);
331          exit(1);          exit(1);
332      }*/      }
333          return wrld->inState[wrld->spatialIndices[midIdx]];          return wrld->inState[wrld->spatialIndices[midIdx]];
334    }*/
335    /*void preSort(@PREFIX@World_t *wrld, SpatialScheduler_t * sched,int start, int len, int axis)
336    {
337        if(!len) return;
338        int startIdx = start + (axis * wrld->numStrands);
339        int endIdx = (start + len) + (axis * wrld->numStrands);
340    
341        Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,startIdx,endIdx- 1,333960,axis);
342    
343        axis = (axis + 1) % wrld->spatialTree->dim;
344        int mid = start + ((start + len)-start)/2;
345        preSort(wrld,sched,start,mid - start, axis);
346        preSort(wrld,sched,mid + 1,start + len - (mid+ 1), axis);
347    }*/
348    
349    /* Swaps the values at two addresses */
350    void Diderot_KDTree_SwapValues(uint32_t * a, uint32_t *b){
351        int temp;
352        temp = *a;
353        *a = *b;
354        *b = temp;
355    }
356    @STRANDTY@ * find_median(@PREFIX@World_t *wrld,int start, int end, int dim){
357    
358        if(end <= start) return NULL;
359        if(end == start + 1) return wrld->inState[wrld->spatialIndices[start]];;
360        int curr, store, mid =  start + (end-start)/2;
361        Diderot_real_t pivot;
362        int count = 0;
363        while(true) {
364    
365            pivot = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[mid]],dim);
366    
367            //printf("Pivot = %f\n",pivot);
368    
369            Diderot_KDTree_SwapValues(&wrld->spatialIndices[mid],&wrld->spatialIndices[end -1]);
370    
371            for (store = curr = start; curr < end; curr++) {
372                Diderot_real_t currVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[curr]],dim);
373                if (currVal < pivot) {
374                    if (curr != store)
375                        Diderot_KDTree_SwapValues(&wrld->spatialIndices[curr], &wrld->spatialIndices[store]);
376                    store++;
377                }
378  }  }
379            Diderot_KDTree_SwapValues(&wrld->spatialIndices[store],&wrld->spatialIndices[end -1]);
380    
381            /* median has duplicate values */
382            Diderot_real_t storeVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[store]],dim);
383            Diderot_real_t midVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[mid]],dim);
384            if (storeVal  == midVal){
385                return wrld->inState[wrld->spatialIndices[mid]];
386            }
387            if (store > mid)    end = store;
388            else        start = store;
389    
390    
391        }
392        return NULL;
393    }
394    
395    static int count = 0;
396  /* A recursive tree building function */  /* A recursive tree building function */
397  KDNode_t * Diderot_KDTree_BuildHelper(@PREFIX@World_t *wrld, SpatialScheduler_t * sched,int start, int len, int axis)  KDNode_t * Diderot_KDTree_BuildHelper(@PREFIX@World_t *wrld, SpatialScheduler_t * sched,int start, int len, int axis)
398  {  {
# Line 358  Line 400 
400          bool isDone = false;          bool isDone = false;
401          @STRANDTY@ * n;          @STRANDTY@ * n;
402          if (!len) return 0;          if (!len) return 0;
403          int mid;      int end = start + len;
404            int mid = start + (end-start)/2;
         if ((n = find_median(wrld,sched,start,start + len,axis,&mid))) {  
405    
406            if ((n = find_median(wrld,start,start + len,axis))) {
407          pthread_mutex_lock (&sched->lock);          pthread_mutex_lock (&sched->lock);
408              newNode = Diderot_KDTree_GrabNode(wrld->spatialTree);              newNode = Diderot_KDTree_GrabNode(wrld->spatialTree);
409          pthread_mutex_unlock (&sched->lock);          pthread_mutex_unlock (&sched->lock);
# Line 414  Line 456 
456      sched->startTime = airTime();      sched->startTime = airTime();
457      KDTree_t * tree  = wrld->spatialTree;      KDTree_t * tree  = wrld->spatialTree;
458      int numStrands = *(tree->numOfStrands);      int numStrands = *(tree->numOfStrands);
459      memcpy(wrld->spatialTmpIndices,wrld->spatialIndices, sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);    //  memcpy(wrld->spatialTmpIndices,wrld->spatialIndices, sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
460      Diderot_KDTree_PoolClear(tree);      Diderot_KDTree_PoolClear(tree);
461      /* Sort the position data */      /* Sort the position data */
462      double spatialST0 = airTime();      /*double spatialST0 = airTime();
463      Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,0,numStrands -1,33390,0);      Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,0,numStrands -1,33390,0);
464      if(@SPATIAL_DIMENSION@ > 1){      if(@SPATIAL_DIMENSION@ > 1){
465          Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,wrld->numStrands,(2 * wrld->numStrands)-1,33390,1);          Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,wrld->numStrands,(2 * wrld->numStrands)-1,33390,1);
466          if(@SPATIAL_DIMENSION@ > 2){          if(@SPATIAL_DIMENSION@ > 2){
467              Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,wrld->numStrands * 2,(3 * wrld->numStrands)-1,33390,2);              Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,wrld->numStrands * 2,(3 * wrld->numStrands)-1,33390,2);
468          }          }
469      }      }*/
470     // double spatialTotalTimeS = (airTime() - spatialST0);     // double spatialTotalTimeS = (airTime() - spatialST0);
471      // if(spatialTotalTimeS >= 0.03)      // if(spatialTotalTimeS >= 0.03)
472      //    printf("maybe fixed parallel time to sort=%f\n",spatialTotalTimeS);      //    printf("maybe fixed parallel time to sort=%f\n",spatialTotalTimeS);
473       // double spatialST0 = airTime();
474       // preSort(wrld,sched,0,*(tree->numOfStrands),0);
475       // double spatialTotalTimeS = (airTime() - spatialST0);
476        // if(spatialTotalTimeS >= 0.03)
477         //   printf("maybe fixed parallel time to sort=%f\n",spatialTotalTimeS);
478    
479    
480      tree->root = Diderot_KDTree_BuildHelper(wrld, wrld->spatialSched,0,*(tree->numOfStrands),0);      tree->root = Diderot_KDTree_BuildHelper(wrld, wrld->spatialSched,0,*(tree->numOfStrands),0);
481     // printf("!!!!!!DONE!!!!\n");     // printf("!!!!!!DONE!!!!\n");

Legend:
Removed from v.2571  
changed lines
  Added in v.2572

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