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 2561, Thu Mar 6 17:45:45 2014 UTC revision 2562, Mon Mar 10 04:10:03 2014 UTC
# Line 85  Line 85 
85          return low;          return low;
86  }  }
87  /* 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) */
88  SpatialWorkerArgs_t * Diderot_Grab_SpatailWorker(SpatialScheduler_t* sched,ParSpatialWorkerType workerType,void * nodeData){  SpatialWorkerArgs_t * Diderot_Grab_SpatailWorker(SpatialScheduler_t* sched,ParSpatialWorkerType workerType,void * nodeData, bool * donePtr){
89    
90          SpatialWorkerArgs_t * retWorker = 0;          SpatialWorkerArgs_t * retWorker = 0;
91          pthread_mutex_lock (&sched->lock);          pthread_mutex_lock (&sched->lock);
# Line 93  Line 93 
93                                  if(sched->workerData[i].isIdle){                                  if(sched->workerData[i].isIdle){
94                                           sched->workerData[i].isIdle = false;                                           sched->workerData[i].isIdle = false;
95                                           sched->workerData[i].data = nodeData;                                           sched->workerData[i].data = nodeData;
96                                           sched->workerData[i].isDone = false;                                           sched->workerData[i].isDone = donePtr;
97                                           sched->workerData[i].workerType = workerType;                                           sched->workerData[i].workerType = workerType;
98                                          retWorker = &sched->workerData[i];                                          retWorker = &sched->workerData[i];
99                                          pthread_cond_signal (&sched->workerData[i].runWait);                                          pthread_cond_signal (&sched->workerData[i].runWait);
# Line 109  Line 109 
109  /* parallel version of the merge sort for the spatial indices */  /* parallel version of the merge sort for the spatial indices */
110  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)
111  {  {
112            bool isDone = false;
113      // 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
114      // then run the sequential version.      // then run the sequential version.
115      if (high - low + 1 <= sched->seqThreshold || depth <= 0)      if (high - low + 1 <= sched->seqThreshold || depth <= 0)
# Line 129  Line 130 
130              node.depth = depth;              node.depth = depth;
131              node.dim = dim;              node.dim = dim;
132    
133              SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,MERGESORT_WORKER,(void *)&node);              SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,MERGESORT_WORKER,(void *)&node,&isDone);
134    
135          //If a worker is not avaliable then this worker will perform both halves.          //If a worker is not avaliable then this worker will perform both halves.
136              if(!worker){              if(!worker){
# Line 139  Line 140 
140                     Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,mid + 1, high, depth,dim);                     Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,mid + 1, high, depth,dim);
141              //Wait until the worker has completed its task              //Wait until the worker has completed its task
142                      pthread_mutex_lock (&worker->lock);                      pthread_mutex_lock (&worker->lock);
143                      while(!worker->isDone)                      while(!isDone)
144                              pthread_cond_wait (&worker->done,&worker->lock);                              pthread_cond_wait (&worker->done,&worker->lock);
145                              pthread_mutex_unlock (&worker->lock);                              pthread_mutex_unlock (&worker->lock);
146                  }                  }
# Line 153  Line 154 
154  {  {
155      int nL = highL - lowL + 1;      int nL = highL - lowL + 1;
156      int nR = highR - lowR + 1;      int nR = highR - lowR + 1;
157        bool isDone = false;
158    
159      // 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
160      // then run the sequential version.      // then run the sequential version.
# Line 200  Line 202 
202              node.low = low;              node.low = low;
203              node.dim = dim;              node.dim = dim;
204    
205              SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,MERGE_WORKER,(void *)&node);              SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,MERGE_WORKER,(void *)&node,&isDone);
206    
207              if(!worker){              if(!worker){
208                      Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, lowL, midL-1, lowR, midR -1, low, depth,dim);                      Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, lowL, midL-1, lowR, midR -1, low, depth,dim);
# Line 208  Line 210 
210              }else {              }else {
211                     Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, midL + 1, highL, midR, highR, mid + 1, depth,dim);                     Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, midL + 1, highL, midR, highR, mid + 1, depth,dim);
212                      pthread_mutex_lock (&worker->lock);                      pthread_mutex_lock (&worker->lock);
213                          while(!worker->isDone)                          while(!isDone)
214                                  pthread_cond_wait (&worker->done,&worker->lock);                                  pthread_cond_wait (&worker->done,&worker->lock);
215                      pthread_mutex_unlock (&worker->lock);                      pthread_mutex_unlock (&worker->lock);
216             }             }
# Line 221  Line 223 
223          {          {
224          //Wait until a task is assigned to the worker          //Wait until a task is assigned to the worker
225              pthread_mutex_lock (&workerArg->sched->lock);              pthread_mutex_lock (&workerArg->sched->lock);
226                            workerArg->isIdle = true;
227                  while(workerArg->isIdle && !workerArg->sched->buildIsDone){                  while(workerArg->isIdle && !workerArg->sched->buildIsDone){
228                      pthread_cond_wait (&workerArg->runWait,&workerArg->sched->lock);                      pthread_cond_wait (&workerArg->runWait,&workerArg->sched->lock);
229                  }                  }
230              pthread_mutex_unlock (&workerArg->sched->lock);              pthread_mutex_unlock (&workerArg->sched->lock);
231    
232              if(workerArg->sched->buildIsDone)break;              if(workerArg->sched->buildIsDone){
233                            workerArg->isIdle = false;
234                    break;
235                }
236          //Based on the worker type perform the assigned task.          //Based on the worker type perform the assigned task.
237              if(workerArg->workerType == MERGESORT_WORKER){              if(workerArg->workerType == MERGESORT_WORKER){
238                      MergetSortNode_t * node = (MergetSortNode_t *)workerArg->data;                      MergetSortNode_t * node = (MergetSortNode_t *)workerArg->data;
# Line 264  Line 269 
269              }              }
270          //Notify any worker waiting for this task to be completed.          //Notify any worker waiting for this task to be completed.
271                  pthread_mutex_lock (&workerArg->lock);                  pthread_mutex_lock (&workerArg->lock);
272                      workerArg->isDone = true;                   *(workerArg->isDone)= true;
273                 pthread_cond_signal (&workerArg->done);                 pthread_cond_signal (&workerArg->done);
274              pthread_mutex_unlock (&workerArg->lock);              pthread_mutex_unlock (&workerArg->lock);
   
                 //Notify the scheduler that the worker has become idle.  
         pthread_mutex_lock (&workerArg->sched->lock);  
                     workerArg->isIdle = true;  
             pthread_mutex_unlock (&workerArg->sched->lock);  
275          }          }
276  }  }
277  /* 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*/
# Line 296  Line 296 
296  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)
297  {  {
298          KDNode_t* newNode = NULL;          KDNode_t* newNode = NULL;
299            bool isDone = false;
300          @STRANDTY@ * n;          @STRANDTY@ * n;
301          if (!len) return 0;          if (!len) return 0;
302          int mid;          int mid;
# Line 317  Line 318 
318              node.start = mid + 1;              node.start = mid + 1;
319                      node.parent = newNode;                      node.parent = newNode;
320    
321                  SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,TREE_WORKER,(void *)&node);                  SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,TREE_WORKER,(void *)&node,&isDone);
322    
323                      if(!worker){                      if(!worker){
324                          newNode->left  = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);                          newNode->left  = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);
# Line 325  Line 326 
326                  }else {                  }else {
327                          newNode->left  = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);                          newNode->left  = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);
328                          pthread_mutex_lock (&worker->lock);                          pthread_mutex_lock (&worker->lock);
329                              while(!worker->isDone)                              while(!isDone)
330                                      pthread_cond_wait (&worker->done,&worker->lock);                                      pthread_cond_wait (&worker->done,&worker->lock);
331                          pthread_mutex_unlock (&worker->lock);                          pthread_mutex_unlock (&worker->lock);
332                  }                  }
# Line 333  Line 334 
334          }          }
335          return newNode;          return newNode;
336  }  }
337  void Diderot_KDTree_Build(@PREFIX@World_t *wrld)  void printTree(KDNode_t* newNode){
338            if(newNode != NULL){
339                    printf("id=%d\n",newNode->strandId);
340                    printTree(newNode->right);
341                    printTree(newNode->left);
342            }
343    }
344    void Diderot_KDTree_Build(@PREFIX@World_t *wrld, uint32_t id, double * spatialTotalTime)
345  {  {
346      SpatialScheduler_t * sched  =  wrld->spatialSched;      SpatialScheduler_t * sched  =  wrld->spatialSched;
347      int id;      if(sched->leaderId != id) {
     //Assign each worker an id  
     pthread_mutex_lock (&wrld->spatialSched->lock);  
            id = sched->numRunning++;  
         pthread_mutex_unlock (&wrld->spatialSched->lock);  
   
     if(id < sched->numWorkers-1) {  
348          treeWorker(&sched->workerData[id]);          treeWorker(&sched->workerData[id]);
349          return;          return;
350      }      }
351        double spatialT0  = airTime();
352      KDTree_t * tree  = wrld->spatialTree;      KDTree_t * tree  = wrld->spatialTree;
353      memcpy(wrld->spatialTmpIndices,wrld->spatialIndices, sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);      memcpy(wrld->spatialTmpIndices,wrld->spatialIndices, sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
354      Diderot_KDTree_PoolClear(tree);      Diderot_KDTree_PoolClear(tree);
# Line 354  Line 357 
357          for(unsigned int i = 0; i < sched->numWorkers-1; i++){          for(unsigned int i = 0; i < sched->numWorkers-1; i++){
358                   pthread_cond_signal (&sched->workerData[i].runWait);                   pthread_cond_signal (&sched->workerData[i].runWait);
359          }          }
360            printTree(tree->root);
361            *(spatialTotalTime) = *(spatialTotalTime) + (airTime() - spatialT0);
362  }  }
363  void Diderot_KDTree_Init(@PREFIX@World_t *wrld)  void Diderot_KDTree_Init(@PREFIX@World_t *wrld)
364  {  {
# Line 372  Line 377 
377          SpatialWorkerArgs_t * workerArgs = NEWVEC(SpatialWorkerArgs_t, nWorkers);          SpatialWorkerArgs_t * workerArgs = NEWVEC(SpatialWorkerArgs_t, nWorkers);
378      scheduler->workerData=workerArgs;      scheduler->workerData=workerArgs;
379      scheduler->nextWorker = 0;      scheduler->nextWorker = 0;
380        scheduler->numRunning= 0;
381      scheduler->seqThreshold = SPATIAL_SEQ_THERSHOLD;      scheduler->seqThreshold = SPATIAL_SEQ_THERSHOLD;
382      scheduler->numWorkers = nWorkers;      scheduler->numWorkers = nWorkers;
383      scheduler->buildIsDone = false;      scheduler->buildIsDone = false;
384      wrld->spatialSched = scheduler;      wrld->spatialSched = scheduler;
385    
386      for(unsigned int i = 0; i < nWorkers; i++){      for(unsigned int i = 0; i < nWorkers; i++){
387                workerArgs[i].isIdle = true;                workerArgs[i].isIdle = false;
388                workerArgs[i].data= 0;                workerArgs[i].data= 0;
389                workerArgs[i].sched = scheduler;                workerArgs[i].sched = scheduler;
390            workerArgs[i].wrld = wrld;            workerArgs[i].wrld = wrld;

Legend:
Removed from v.2561  
changed lines
  Added in v.2562

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