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 2452, Sat Oct 5 00:43:58 2013 UTC revision 2453, Mon Oct 7 04:32:27 2013 UTC
# Line 1  Line 1 
1  typedef struct {  /* sequential version of the merge sort for the spatial indices */
2          @PREFIX@World_t *wrld;  void Diderot_Spatial_SeqMergeSort(@PREFIX@World_t *wrld, uint32_t * indices, uint32_t * tmpIndices, int low, int high, uint32_t dim)
         uint32_t id;  
 }SpatialWorkerArgs_t;  
   
 KDNode_t * Diderot_KDTree_BuildHelper(  
         KDTree_t * tree,  
         @STRANDTY@ ** strands,  
         uint32_t len,  
         uint32_t axis,  
         uint32_t dim)  
3  {  {
         @STRANDTY@ ** median;  
         KDNode_t * newNode = 0;  
4    
5          if(!len) return 0;          if (low >= high)
6                    return;
7    
8          if((median = Diderot_KDTree_FindMedian(strands,strands + len,axis,dim))) {          int mid = (low + high) / 2;
                 newNode = Diderot_KDTree_GrabNode(tree);  
                 newNode->strandId = median[0]->strandId;  
                 axis = (axis + 1) % tree->dim;  
                 newNode->left = Diderot_KDTree_BuildHelper(tree,strands, median - strands, axis,dim);  
                 newNode->right = Diderot_KDTree_BuildHelper(tree,median + 1, strands + len - (median + 1),axis,dim);  
         }  
         return newNode;  
 }  
 static void *@PREFIX@Tree_Worker (void *arg){  
9    
10          SpatialWorkerArgs_t *myArg = (SpatialWorkerArgs_t *)arg;          //Sort two sub-arrays first so that they are placed into the temporary
11      @PREFIX@World_t *wrld = myArg->wrld;          //indices array.
12      Diderot_Sched_t *sched = wrld->sched;          Diderot_Spatial_SeqMergeSort(wrld,tmpIndices,indices, low, mid,dim);
13            Diderot_Spatial_SeqMergeSort(wrld,tmpIndices,indices, mid + 1, high,dim);
14    
15            // Once temporary indice array contains the two sorted sub-arrays
16            // they are merged into indice array
17        Diderot_Spatial_SeqMerge(wrld,indices,tmpIndices,low, mid, mid + 1, high,low,dim);
18    }
19    /* sequential version of the merge operation for the spatial indices */
20    /* Note: Sub-arrays are adjacent to each other in the
21       the sequential version but not necessarily for the parallel version;
22       therefore, sub-arrays boundaries must be specified
23       explicitly.*/
24    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)
25    {
26            int high = low + highL - lowL + highR - lowR + 1;
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
29        //has a duplicate copy of the current sorted axis
30            int offSet = (dim + 1) == wrld->spatialTree->dim ? -(dim * wrld->numStrands) : ((dim + 1) * wrld->numStrands);
31    
32        // Bottom-up implementation
33            for (;low <= high; low++)
34            {
35                            if (lowL > highL){
36                                    indices[low] = tmpIndices[lowR];
37                                    indices[low + offSet] = tmpIndices[lowR];
38                                    tmpIndices[low + offSet] = tmpIndices[lowR];
39                                    lowR++;
40                            }else if (lowR > highR) {
41                                    indices[low] = tmpIndices[lowL];
42                                    indices[low + offSet] = tmpIndices[lowL];
43                                    tmpIndices[low + offSet] = tmpIndices[lowL];
44                                    lowL++;
45                            }else {
46                                    Diderot_real_t lowLValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowL]],dim);
47                                    Diderot_real_t lowRValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowR]],dim);
48                                    if(lowLValue < lowRValue){
49                                            indices[low] = tmpIndices[lowL];
50                                            indices[low + offSet] = tmpIndices[lowL];
51                                            tmpIndices[low + offSet] = tmpIndices[lowL];
52                                            lowL++;
53                                    }else {
54                                            indices[low] = tmpIndices[lowR];
55                                            indices[low + offSet] = tmpIndices[lowR];
56                                            tmpIndices[low + offSet] = tmpIndices[lowR];
57                                            lowR++;
58                                    }
59                            }
60  }  }
61  void Diderot_KDTree_Build(  }
62          @PREFIX@World_t *wrld)  /* Swaps the values at two addresses */
63    void Diderot_KDTree_SwapValues(int * a, int *b){
64            int temp;
65            temp = *a;
66            *a = *b;
67            *b = temp;
68    }
69    int Diderot_BinarySearch(@PREFIX@World_t *wrld,uint32_t *tmpIndices, int low, int high, Diderot_real_t searchValue, int dim)
70  {  {
71     Diderot_KDTree_PoolClear(tree);                  if(low > high + 1)
72     int nWorkers = sched->numWorkers;                          high = low;
73      WorkerArg_t *args = NEWVEC(WorkerArg_t, nWorkers);                  else
74      if (wrld->verboseFlg) fprintf (stderr, "initializing %d workers ...\n", nWorkers);                          high = high + 1;
75      double t0 = airTime();  
76      sched->numWorkers = nWorkers;          while (low < high)
77      sched->numIdle = 0;          {
78      sched->numSteps = 0;              int mid = (low + high) / 2;
79                Diderot_real_t pivot = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[mid]],dim);
80      for (int i = 0; i < nWorkers; i++) {              if (pivot < searchValue)
81          pthread_t pid;                  low = mid + 1;
82          args[i].wrld = wrld;              else
83          args[i].id = i;                  high = mid;
         if (pthread_create (&pid, NULL, @PREFIX@Worker, (void *)&(args[i])) != 0) {  
             fprintf (stderr, "unable to create worker thread\n");  
             exit (1);  
84          }          }
85          pthread_detach (pid);          return low;
86      }      }
87    /* 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){
89    
90    // wait for the computation to finish          SpatialWorkerArgs_t * retWorker = 0;
91      pthread_mutex_lock (&sched->lock);      pthread_mutex_lock (&sched->lock);
92          pthread_cond_wait (&sched->runWait, &sched->lock);                   for(int i = sched->nextWorker; i < sched->numWorkers-1; i++){
93                                    if(sched->workerData[i].isIdle){
94                                             sched->workerData[i].isIdle = false;
95                                             sched->workerData[i].data = nodeData;
96                                             sched->workerData[i].isDone = false;
97                                             sched->workerData[i].workerType = workerType;
98                                            retWorker = &sched->workerData[i];
99                                            pthread_cond_signal (&sched->workerData[i].runWait);
100                                            sched->nextWorker++;
101                                            if(sched->nextWorker == sched->numWorkers-2)
102                                                    sched->nextWorker = 0;
103                                            break;
104                                    }
105                     }
106      pthread_mutex_unlock (&sched->lock);      pthread_mutex_unlock (&sched->lock);
107        return retWorker;
108    }
109    /* 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)
111    {
112        // If the depth is less than zero or there's not enough work to perform in parallel
113        // then run the sequential version.
114        if (high - low + 1 <= sched->seqThreshold || depth <= 0)
115        {
116                Diderot_Spatial_SeqMergeSort(wrld,indices,tmpIndices, low, high,dim);
117            return;
118        }
119        if(low < high) {
120            int mid = (low + high) / 2;
121                depth--;
122    
123            //Assign a worker to do the upper half the merge sort.
124                MergetSortNode_t node;
125                node.low=low;
126                node.high = mid;
127                node.indices = tmpIndices;
128                node.tmpIndices = indices;
129                node.depth = depth;
130                node.dim = dim;
131    
132                SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,MERGESORT_WORKER,(void *)&node);
133    
134            //If a worker is not avaliable then this worker will perform both halves.
135                if(!worker){
136                       Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,low, mid,depth,dim);
137                       Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,mid + 1, high, depth,dim);
138                }else {
139                       Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,mid + 1, high, depth,dim);
140                //Wait until the worker has completed its task
141                        pthread_mutex_lock (&worker->lock);
142                        while(!worker->isDone)
143                                pthread_cond_wait (&worker->done,&worker->lock);
144                                pthread_mutex_unlock (&worker->lock);
145                    }
146                //Merge the two sorted lists.
147                        Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices,low, mid, mid + 1, high, low, depth,dim);
148              }
149    
150    }
151    /* parallel version of the merge operation for the spatial indices */
152    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)
153    {
154        int nL = highL - lowL + 1;
155        int nR = highR - lowR + 1;
156    
157        // If the depth is less than zero or there's not enough work to perform in parallel
158        // then run the sequential version.
159        if (nL + nR <= sched->seqThreshold || depth <= 0)
160        {
161                Diderot_Spatial_SeqMerge(wrld,indices,tmpIndices,lowL, highL, lowR, highR,low,dim);
162            return;
163        }
164    
165        if (nL < nR)
166        {
167                Diderot_KDTree_SwapValues(&lowL,&lowR);
168                Diderot_KDTree_SwapValues(&highL,&highR);
169                Diderot_KDTree_SwapValues(&nL,&nR);
170        }
171        if(nL == 0) return;
172        else
173        {
174            int midL = (lowL + highL) / 2;
175    
176            Diderot_real_t pivot = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[midL]],dim);
177    
178            int midR = Diderot_BinarySearch(wrld,tmpIndices, lowR, highR, pivot,dim);
179    
180                    int mid = low + (midL - lowL) + (midR - lowR);
181    
182            //Note: The offset is needed for the way the tree is built. We need to make sure the next axis to be sorted
183            //has a duplicate copy of the current sorted axis
184                int offSet = (dim + 1) == wrld->spatialTree->dim ? -(dim * wrld->numStrands) : ((dim + 1) * wrld->numStrands);
185            indices[mid] = tmpIndices[midL];
186                indices[mid + offSet] = tmpIndices[midL];
187                    tmpIndices[mid + offSet] = tmpIndices[midL];
188    
189                depth--;
190    
191            //Have a worker perform the upper half of the merge
192                MergeNode_t node;
193                    node.depth = depth;
194                node.lowL = lowL;
195                node.highL= midL - 1;
196                node.lowR = lowR;
197                    node.indices = indices;
198                    node.tmpIndices = tmpIndices;
199                node.highR = midR - 1;
200                node.low = low;
201                node.dim = dim;
202    
203                SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,MERGE_WORKER,(void *)&node);
204    
205                if(!worker){
206                        Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, lowL, midL-1, lowR, midR -1, low, depth,dim);
207                    Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, midL + 1, highL, midR, highR, mid + 1, depth,dim);
208                }else {
209                       Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, midL + 1, highL, midR, highR, mid + 1, depth,dim);
210                        pthread_mutex_lock (&worker->lock);
211                            while(!worker->isDone)
212                                    pthread_cond_wait (&worker->done,&worker->lock);
213                        pthread_mutex_unlock (&worker->lock);
214               }
215       }
216    }
217    /*The worker function for all the workers */
218    void treeWorker(SpatialWorkerArgs_t * workerArg){
219    
220            while(!workerArg->sched->buildIsDone)
221            {
222            //Wait until a task is assigned to the worker
223                pthread_mutex_lock (&workerArg->sched->lock);
224                    while(workerArg->isIdle && !workerArg->sched->buildIsDone){
225                        pthread_cond_wait (&workerArg->runWait,&workerArg->sched->lock);
226                    }
227                pthread_mutex_unlock (&workerArg->sched->lock);
228    
229                if(workerArg->sched->buildIsDone)break;
230    
231            //Based on the worker type perform the assigned task.
232                if(workerArg->workerType == MERGESORT_WORKER){
233                        MergetSortNode_t * node = (MergetSortNode_t *)workerArg->data;
234                            Diderot_Spatial_ParMergeSort(workerArg->wrld,
235                                                      workerArg->sched,
236                                                      node->indices,
237                                                      node->tmpIndices,
238                                                          node->low,
239                                                          node->high,
240                                                          node->depth,
241                                                          node->dim);
242    
243                }else if(workerArg->workerType == MERGE_WORKER) {
244                        MergeNode_t * node = (MergeNode_t *)workerArg->data;
245                        Diderot_Spatial_ParMerge(workerArg->wrld,
246                                                  workerArg->sched,
247                                                  node->indices,
248                                                  node->tmpIndices,
249                                                  node->lowL,
250                                                  node->highL,
251                                                  node->lowR,
252                                                  node->highR,
253                                                  node->low,
254                                                  node->depth,
255                                                  node->dim);
256                }else if(workerArg->workerType == TREE_WORKER){
257                        TreeNode_t * node = (TreeNode_t *)workerArg->data;
258                        node->parent->right = Diderot_KDTree_BuildHelper(workerArg->wrld,
259                                                          workerArg->sched,
260                                                              node->start,
261                                                              node->len,
262                                                          node->axis);
263    
264                }
265            //Notify any worker waiting for this task to be completed.
266                    pthread_mutex_lock (&workerArg->lock);
267                        workerArg->isDone = true;
268                   pthread_cond_signal (&workerArg->done);
269                pthread_mutex_unlock (&workerArg->lock);
270    
271                    //Notify the scheduler that the worker has become idle.
272            pthread_mutex_lock (&workerArg->sched->lock);
273                        workerArg->isIdle = true;
274                pthread_mutex_unlock (&workerArg->sched->lock);
275            }
276    }
277    /* Finds the median strand in an array of strands based on the given axis*/
278    @STRANDTY@ * find_median(@PREFIX@World_t *wrld, SpatialScheduler_t * sched, int start, int end, int idx, int * mid){
279    
280     tree->root = Diderot_KDTree_BuildHelper(tree,strands,*(tree->numOfStrands),0,tree->dim);          int startIdx = start + (idx * wrld->numStrands);
281            int endIdx = end + (idx * wrld->numStrands);
282            int midIdx = startIdx + (endIdx - startIdx)/2;
283    
284            if(end <= start) return NULL;
285            if(end == start + 1) {
286                    *mid = start;
287                    return wrld->inState[wrld->spatialIndices[startIdx]];
288  }  }
289            Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices, wrld->spatialTmpIndices, startIdx,endIdx-1,33453,idx);
290    
291            *mid = start + (end-start)/2;
292    
293            return wrld->inState[wrld->spatialIndices[midIdx]];
294    }
295    /* A recursive tree building function */
296    KDNode_t * Diderot_KDTree_BuildHelper(@PREFIX@World_t *wrld, SpatialScheduler_t * sched,int start, int len, int axis)
297    {
298            KDNode_t* newNode = NULL;
299            @STRANDTY@ * n;
300            if (!len) return 0;
301            int mid;
302            if ((n = find_median(wrld,sched,start,start + len,axis,&mid))) {
303                    newNode = Diderot_KDTree_GrabNode(wrld->spatialTree);
304                    newNode->strandId = n->strandId;
305                    axis = (axis + 1) % wrld->spatialTree->dim;
306    
307            // If the depth is less than zero or there's not enough work to perform in parallel
308            // then run the sequential version.
309            if(len < sched->seqThreshold){
310                        newNode->left  = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);
311                        newNode->right = Diderot_KDTree_BuildHelper(wrld,sched,mid + 1,start + len - (mid+ 1), axis);
312            }else{
313                //Have a woker build the right side of the tree.
314                TreeNode_t node;
315                        node.axis = axis;
316                node.len = start + len - (mid + 1);
317                node.start = mid + 1;
318                        node.parent = newNode;
319    
320                    SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,TREE_WORKER,(void *)&node);
321    
322                        if(!worker){
323                            newNode->left  = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);
324                            newNode->right = Diderot_KDTree_BuildHelper(wrld,sched,mid + 1,start + len - (mid+ 1), axis);
325                    }else {
326                            newNode->left  = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);
327                            pthread_mutex_lock (&worker->lock);
328                                while(!worker->isDone)
329                                        pthread_cond_wait (&worker->done,&worker->lock);
330                            pthread_mutex_unlock (&worker->lock);
331                    }
332            }
333            }
334            return newNode;
335    }
336    void Diderot_KDTree_Build(@PREFIX@World_t *wrld)
337    {
338        SpatialScheduler_t * sched  =  wrld->spatialSched;
339        int id;
340        //Assign each worker an id
341        pthread_mutex_lock (&wrld->spatialSched->lock);
342               id = sched->numRunning++;
343            pthread_mutex_unlock (&wrld->spatialSched->lock);
344    
345        if(id < sched->numWorkers-1) {
346            treeWorker(&sched->workerData[id]);
347            return;
348        }
349        KDTree_t * tree  = wrld->spatialTree;
350        memcpy(wrld->spatialTmpIndices,wrld->spatialIndices, sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
351        Diderot_KDTree_PoolClear(tree);
352        tree->root = Diderot_KDTree_BuildHelper(wrld, wrld->spatialSched,0,*(tree->numOfStrands),0);
353        wrld->spatialSched->buildIsDone=true;
354            for(unsigned int i = 0; i < sched->numWorkers-1; i++){
355                     pthread_cond_signal (&sched->workerData[i].runWait);
356            }
357    }
358    void Diderot_KDTree_Init(@PREFIX@World_t *wrld)
359    {
360        Diderot_KDTree_Alloc(&wrld->spatialTree,&wrld->numStrands,@SPATIAL_DIMENSION@);
361        wrld->spatialIndices= NEWVEC(uint32_t,@SPATIAL_DIMENSION@ * wrld->numStrands);
362        wrld->spatialTmpIndices= NEWVEC(uint32_t,@SPATIAL_DIMENSION@ * wrld->numStrands);
363    
364        uint32_t len =  @SPATIAL_DIMENSION@ * wrld->numStrands;
365    
366        SpatialScheduler_t * scheduler = (SpatialScheduler_t *)CheckedAlloc(sizeof(SpatialScheduler_t));
367        if ((pthread_mutex_init (&scheduler->lock, 0)) != 0){
368            printf("Error in initializing the spatial scheduler's lock");
369                exit(EXIT_FAILURE);
370        }
371        int nWorkers = wrld->sched->numWorkers;
372            SpatialWorkerArgs_t * workerArgs = NEWVEC(SpatialWorkerArgs_t, nWorkers);
373        scheduler->workerData=workerArgs;
374        scheduler->nextWorker = 0;
375        scheduler->seqThreshold = SPATIAL_SEQ_THERSHOLD;
376        scheduler->numWorkers = nWorkers;
377        scheduler->buildIsDone = false;
378        wrld->spatialSched = scheduler;
379    
380        for(unsigned int i = 0; i < nWorkers; i++){
381                  workerArgs[i].isIdle = true;
382                  workerArgs[i].data= 0;
383                  workerArgs[i].sched = scheduler;
384              workerArgs[i].wrld = wrld;
385              workerArgs[i].id = i;
386                  if ((pthread_cond_init (&(workerArgs[i].runWait), 0)) != 0){
387                             printf("Error in initializing the scheduler lock");
388                             exit(EXIT_FAILURE);
389                     }
390                  if ((pthread_cond_init (&(workerArgs[i].done), 0)) != 0){
391                             printf("Error in initializing the done condition var ");
392                             exit(EXIT_FAILURE);
393                     }
394                     if ((pthread_mutex_init (&(workerArgs[i].lock), 0)) != 0){
395                             printf("Error in initializing the worker lock");
396                             exit(EXIT_FAILURE);
397                     }
398             }
399        for(uint32_t  i = 0; i < len; i++){
400            wrld->spatialIndices[i]= i % wrld->numStrands;
401        }
402    }
403    void Diderot_KDTree_Realloc(@PREFIX@World_t *wrld)
404    {
405        wrld->spatialIndices= (uint32_t*)CheckedAlloc(sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
406        wrld->spatialTmpIndices= (uint32_t*)CheckedAlloc(sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
407        uint32_t len =  @SPATIAL_DIMENSION@ * wrld->numStrands;
408        for(uint32_t  i = 0; i < len; i++){
409                wrld->spatialIndices[i]= i % wrld->numStrands;
410        }
411    }

Legend:
Removed from v.2452  
changed lines
  Added in v.2453

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