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 2569, Tue Mar 25 20:26:57 2014 UTC revision 2570, Wed Mar 26 21:52:00 2014 UTC
# Line 27  Line 27 
27    
28      //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
29      //has a duplicate copy of the current sorted axis      //has a duplicate copy of the current sorted axis
30          int offSet = (dim + 1) == wrld->spatialTree->dim ? -(dim * wrld->numStrands) : ((dim + 1) * wrld->numStrands);          int offSet = (dim + 1) * wrld->numStrands;
31        bool setOffSet = (dim + 1) != wrld->spatialTree->dim;
32      // Bottom-up implementation      // Bottom-up implementation
33          for (;low <= high; low++)          for (;low <= high; low++)
34          {          {
35                          if (lowL > highL){                          if (lowL > highL){
36                                  indices[low] = tmpIndices[lowR];                                  indices[low] = tmpIndices[lowR];
37                    if(setOffSet){
38                                  indices[low + offSet] = tmpIndices[lowR];                                  indices[low + offSet] = tmpIndices[lowR];
39                                  tmpIndices[low + offSet] = tmpIndices[lowR];                                  tmpIndices[low + offSet] = tmpIndices[lowR];
40                    }
41                                  lowR++;                                  lowR++;
42                          }else if (lowR > highR) {                          }else if (lowR > highR) {
43                                  indices[low] = tmpIndices[lowL];                                  indices[low] = tmpIndices[lowL];
44                    if(setOffSet){
45                                  indices[low + offSet] = tmpIndices[lowL];                                  indices[low + offSet] = tmpIndices[lowL];
46                                  tmpIndices[low + offSet] = tmpIndices[lowL];                                  tmpIndices[low + offSet] = tmpIndices[lowL];
47                    }
48                                  lowL++;                                  lowL++;
49                          }else {                          }else {
50                                  Diderot_real_t lowLValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowL]],dim);                                  Diderot_real_t lowLValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowL]],dim);
51                                  Diderot_real_t lowRValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowR]],dim);                                  Diderot_real_t lowRValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowR]],dim);
52                                  if(lowLValue < lowRValue){                                  if(lowLValue < lowRValue){
53                                          indices[low] = tmpIndices[lowL];                                          indices[low] = tmpIndices[lowL];
54                                            if(setOffSet){
55                                          indices[low + offSet] = tmpIndices[lowL];                                          indices[low + offSet] = tmpIndices[lowL];
56                                          tmpIndices[low + offSet] = tmpIndices[lowL];                                          tmpIndices[low + offSet] = tmpIndices[lowL];
57                        }
58                                          lowL++;                                          lowL++;
59                                  }else {                                  }else {
60                                          indices[low] = tmpIndices[lowR];                                          indices[low] = tmpIndices[lowR];
61                                            if(setOffSet) {
62                                          indices[low + offSet] = tmpIndices[lowR];                                          indices[low + offSet] = tmpIndices[lowR];
63                                          tmpIndices[low + offSet] = tmpIndices[lowR];                                          tmpIndices[low + offSet] = tmpIndices[lowR];
64                        }
65                                          lowR++;                                          lowR++;
66                                  }                                  }
67                          }                          }
# Line 137  Line 145 
145                     Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,low, mid,depth,dim);                     Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,low, mid,depth,dim);
146                     Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,mid + 1, high, depth,dim);                     Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,mid + 1, high, depth,dim);
147              }else {              }else {
                printf("<2>\n");  
148                     Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,mid + 1, high, depth,dim);                     Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,mid + 1, high, depth,dim);
149              //Wait until the worker has completed its task              //Wait until the worker has completed its task
150                      pthread_mutex_lock (&worker->lock);                      pthread_mutex_lock (&worker->lock);
# Line 182  Line 189 
189    
190          int mid = low + (midL - lowL) + (midR - lowR);          int mid = low + (midL - lowL) + (midR - lowR);
191    
192            indices[mid] = tmpIndices[midL];
193    
194            if((dim + 1) < wrld->spatialTree->dim)
195            {
196          //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
197          //has a duplicate copy of the current sorted axis          //has a duplicate copy of the current sorted axis
198              int offSet = (dim + 1) == wrld->spatialTree->dim ? -(dim * wrld->numStrands) : ((dim + 1) * wrld->numStrands);               int offSet = ((dim + 1) * wrld->numStrands);
         indices[mid] = tmpIndices[midL];  
199              indices[mid + offSet] = tmpIndices[midL];              indices[mid + offSet] = tmpIndices[midL];
200                  tmpIndices[mid + offSet] = tmpIndices[midL];                  tmpIndices[mid + offSet] = tmpIndices[midL];
201            }
202    
203              depth--;              depth--;
204    
# Line 224  Line 235 
235          {          {
236          //Wait until a task is assigned to the worker          //Wait until a task is assigned to the worker
237              pthread_mutex_lock (&workerArg->sched->lock);              pthread_mutex_lock (&workerArg->sched->lock);
             if(workerArg->sched->leaderId == workerArg->id) {  
                 workerArg->sched->numWorkers +=1;  
             }  
238              if(!workerArg->sched->buildIsDone){              if(!workerArg->sched->buildIsDone){
239                  if(workerArg->sched->numRunning > 0)                  if(workerArg->sched->numRunning - 1 > 0)
240                  {                  {
241                     workerArg->isIdle = true;                     workerArg->isIdle = true;
242                     workerArg->sched->numRunning-=1;                     workerArg->sched->numRunning-=1;
# Line 274  Line 282 
282                                                node->depth,                                                node->depth,
283                                                node->dim);                                                node->dim);
284              }else if(workerArg->workerType == TREE_WORKER){              }else if(workerArg->workerType == TREE_WORKER){
285                      TreeNode_t * node = (TreeNode_t *)workerArg->data;                      KDNode_t*  node = (KDNode_t  *)workerArg->data;
286                      node->parent->right = Diderot_KDTree_BuildHelper(workerArg->wrld,                  if((node->start + node->len)- 1> workerArg->wrld->numStrands){
287                        printf("worker=%d, PROBLEM start = %d len = %d\n",workerArg->id,node->start,node->len);
288                        exit(1);
289                    }
290                        node->right = Diderot_KDTree_BuildHelper(workerArg->wrld,
291                                                        workerArg->sched,                                                        workerArg->sched,
292                                                            node->start,                                                            node->start,
293                                                            node->len,                                                            node->len,
# Line 304  Line 316 
316                  *mid = start;                  *mid = start;
317                  return wrld->inState[wrld->spatialIndices[startIdx]];                  return wrld->inState[wrld->spatialIndices[startIdx]];
318          }          }
319    /* int count = 0;
320      double spatialT0 = airTime();  bool error=false;
321     // Diderot_Spatial_SeqMergeSort(wrld,wrld->spatialIndices, wrld->spatialTmpIndices, startIdx,endIdx-1,idx);     for(int i = startIdx + 1; i < endIdx; i++){
322          Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices, wrld->spatialTmpIndices, startIdx,endIdx-1,33360,idx);  
323      double spatialTotalTime = (airTime() - spatialT0);            Diderot_real_t t1 = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[i-1]],idx);
324           if(spatialTotalTime >= 0.03)            Diderot_real_t t2 = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[i]],idx);
325      printf("time to sort=%f\n",spatialTotalTime);            if(t1 > t2){
326                  printf("Problem start=%d, end=%d curr=%d, t1=%f t2=%f\n",start,end,count,t1,t2);
327                 error = true;
328              }
329              count++;
330        }
331        if(error)
332            exit(1); */
333          *mid = start + (end-start)/2;          *mid = start + (end-start)/2;
334        if(midIdx >  (2 * wrld->numStrands)) {
335            printf("MidIdx is bigger = %d\n",midIdx);
336            exit(1);
337        }
338          return wrld->inState[wrld->spatialIndices[midIdx]];          return wrld->inState[wrld->spatialIndices[midIdx]];
339  }  }
340  /* A recursive tree building function */  /* A recursive tree building function */
# Line 324  Line 345 
345          @STRANDTY@ * n;          @STRANDTY@ * n;
346          if (!len) return 0;          if (!len) return 0;
347          int mid;          int mid;
348    
349          if ((n = find_median(wrld,sched,start,start + len,axis,&mid))) {          if ((n = find_median(wrld,sched,start,start + len,axis,&mid))) {
350    
351            printf("Start=%d,Len=%d,Mid=%d\n",start,len,mid);
352    
353                  pthread_mutex_lock (&sched->lock);                  pthread_mutex_lock (&sched->lock);
354              newNode = Diderot_KDTree_GrabNode(wrld->spatialTree);              newNode = Diderot_KDTree_GrabNode(wrld->spatialTree);
355          pthread_mutex_unlock (&sched->lock);          pthread_mutex_unlock (&sched->lock);
# Line 338  Line 363 
363                      newNode->right = Diderot_KDTree_BuildHelper(wrld,sched,mid + 1,start + len - (mid+ 1), axis);                      newNode->right = Diderot_KDTree_BuildHelper(wrld,sched,mid + 1,start + len - (mid+ 1), axis);
364          }else{          }else{
365              //Have a woker build the right side of the tree.              //Have a woker build the right side of the tree.
366              TreeNode_t node;                  newNode->axis = axis;
367                  node.axis = axis;              newNode->len = start + len - (mid + 1);
368              node.len = start + len - (mid + 1);              newNode->start = mid + 1;
             node.start = mid + 1;  
                 node.parent = newNode;  
369    
370                  SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,TREE_WORKER,(void *)&node,&isDone);                  SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,TREE_WORKER,(void *)newNode,&isDone);
371    
372    
373                    if((newNode->start + newNode->len)- 1> wrld->numStrands){
374                        if(worker)
375                        printf("INSIDE BUILD worker=%d, PROBLEM start = %d len = %d\n",worker->id,newNode->start,newNode->len);
376                        else
377                        printf("INSIDE BUILD no worker, PROBLEM start = %d len = %d\n",newNode->start,newNode->len);
378                        exit(1);
379                    }
380    
381                      if(!worker){                      if(!worker){
382                          newNode->left  = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);                          newNode->left  = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);
# Line 371  Line 403 
403          treeWorker(&sched->workerData[id]);          treeWorker(&sched->workerData[id]);
404          return;          return;
405      }      }
     printf("Start Build\n");  
406      double spatialT0  = airTime();      double spatialT0  = airTime();
407      KDTree_t * tree  = wrld->spatialTree;      KDTree_t * tree  = wrld->spatialTree;
408        int numStrands = *(tree->numOfStrands);
409      memcpy(wrld->spatialTmpIndices,wrld->spatialIndices, sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);      memcpy(wrld->spatialTmpIndices,wrld->spatialIndices, sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
410      Diderot_KDTree_PoolClear(tree);      Diderot_KDTree_PoolClear(tree);
411        /* Sort the position data */
412        double spatialST0 = airTime();
413        Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,0,numStrands -1,33390,0);
414        if(@SPATIAL_DIMENSION@ > 1){
415            Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,wrld->numStrands,(2 * wrld->numStrands)-1,33390,1);
416            if(@SPATIAL_DIMENSION@ > 2){
417                Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,wrld->numStrands * 2,(3 * wrld->numStrands)-1,33390,2);
418            }
419        }
420        double spatialTotalTimeS = (airTime() - spatialST0);
421         if(spatialTotalTimeS >= 0.03)
422            printf("maybe fixed parallel time to sort=%f\n",spatialTotalTimeS);
423    
424      tree->root = Diderot_KDTree_BuildHelper(wrld, wrld->spatialSched,0,*(tree->numOfStrands),0);      tree->root = Diderot_KDTree_BuildHelper(wrld, wrld->spatialSched,0,*(tree->numOfStrands),0);
425        printf("!!!!!!DONE!!!!\n");
426        pthread_mutex_lock(&sched->lock);
427            sched->numWorkers +=1;
428        pthread_mutex_unlock(&sched->lock);
429      treeWorker(&sched->workerData[id]);      treeWorker(&sched->workerData[id]);
430          //printTree(tree->root);          //printTree(tree->root);
431          *(spatialTotalTime) = *(spatialTotalTime) + (airTime() - spatialT0);          *(spatialTotalTime) = *(spatialTotalTime) + (airTime() - spatialT0);

Legend:
Removed from v.2569  
changed lines
  Added in v.2570

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