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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2582 - (view) (download)

1 : lamonts 2571 //Debugging purpoes
2 :     void printTree(KDNode_t* newNode){
3 :     if(newNode != NULL){
4 :     printf("id=%d\n",newNode->strandId);
5 :     printTree(newNode->right);
6 :     printTree(newNode->left);
7 :     }
8 :     }
9 : lamonts 2574 /* 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 : lamonts 2453 /* sequential version of the merge sort for the spatial indices */
24 : lamonts 2574 void Diderot_Spatial_SeqMergeSort(@PREFIX@World_t *wrld, uint32_t * indices, uint32_t * tmpIndices, int low, int high, uint32_t dim)
25 : lamonts 2422 {
26 :    
27 : lamonts 2453 if (low >= high)
28 :     return;
29 : lamonts 2422
30 : lamonts 2453 int mid = (low + high) / 2;
31 :    
32 :     //Sort two sub-arrays first so that they are placed into the temporary
33 :     //indices array.
34 :     Diderot_Spatial_SeqMergeSort(wrld,tmpIndices,indices, low, mid,dim);
35 :     Diderot_Spatial_SeqMergeSort(wrld,tmpIndices,indices, mid + 1, high,dim);
36 :    
37 :     // Once temporary indice array contains the two sorted sub-arrays
38 :     // they are merged into indice array
39 :     Diderot_Spatial_SeqMerge(wrld,indices,tmpIndices,low, mid, mid + 1, high,low,dim);
40 : lamonts 2574 }
41 : lamonts 2453 /* sequential version of the merge operation for the spatial indices */
42 :     /* Note: Sub-arrays are adjacent to each other in the
43 :     the sequential version but not necessarily for the parallel version;
44 :     therefore, sub-arrays boundaries must be specified
45 :     explicitly.*/
46 : lamonts 2574 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 : lamonts 2453 {
48 :     int high = low + highL - lowL + highR - lowR + 1;
49 :    
50 :     //Note: The offset is needed for the way the tree is built. We need to make sure the next axis to be sorted
51 :     //has a duplicate copy of the current sorted axis
52 : lamonts 2572 int offSet = (dim + 1) == wrld->spatialTree->dim ? -(dim * wrld->numStrands) : ((dim + 1) * wrld->numStrands);
53 : lamonts 2453 // Bottom-up implementation
54 :     for (;low <= high; low++)
55 :     {
56 :     if (lowL > highL){
57 :     indices[low] = tmpIndices[lowR];
58 : lamonts 2572 indices[low + offSet] = tmpIndices[lowR];
59 :     tmpIndices[low + offSet] = tmpIndices[lowR];
60 : lamonts 2453 lowR++;
61 :     }else if (lowR > highR) {
62 :     indices[low] = tmpIndices[lowL];
63 : lamonts 2572 indices[low + offSet] = tmpIndices[lowL];
64 :     tmpIndices[low + offSet] = tmpIndices[lowL];
65 : lamonts 2453 lowL++;
66 :     }else {
67 :     Diderot_real_t lowLValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowL]],dim);
68 :     Diderot_real_t lowRValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowR]],dim);
69 :     if(lowLValue < lowRValue){
70 :     indices[low] = tmpIndices[lowL];
71 : lamonts 2572 indices[low + offSet] = tmpIndices[lowL];
72 :     tmpIndices[low + offSet] = tmpIndices[lowL];
73 : lamonts 2453 lowL++;
74 :     }else {
75 :     indices[low] = tmpIndices[lowR];
76 : lamonts 2572 indices[low + offSet] = tmpIndices[lowR];
77 :     tmpIndices[low + offSet] = tmpIndices[lowR];
78 : lamonts 2453 lowR++;
79 :     }
80 :     }
81 : lamonts 2422 }
82 : lamonts 2453 }
83 :     int Diderot_BinarySearch(@PREFIX@World_t *wrld,uint32_t *tmpIndices, int low, int high, Diderot_real_t searchValue, int dim)
84 :     {
85 :     if(low > high + 1)
86 :     high = low;
87 :     else
88 :     high = high + 1;
89 : lamonts 2422
90 : lamonts 2453 while (low < high)
91 :     {
92 :     int mid = (low + high) / 2;
93 :     Diderot_real_t pivot = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[mid]],dim);
94 :     if (pivot < searchValue)
95 :     low = mid + 1;
96 :     else
97 :     high = mid;
98 :     }
99 :     return low;
100 : lamonts 2574 }
101 : lamonts 2582 SpatialWorkerArgs_t * Diderot_Grab_SpatailWorkerSort(SpatialScheduler_t* sched,ParSpatialWorkerType workerType,int start, int end, int axis){
102 :    
103 :     SpatialWorkerArgs_t * retWorker = 0;
104 :     pthread_mutex_lock (&sched->lock);
105 :     for(int i = sched->nextWorker; i < sched->numWorkers; i++){
106 :     if(sched->workerData[i].isIdle){
107 :     sched->workerData[i].isIdle = false;
108 :     sched->workerData[i].start = start;
109 :     sched->workerData[i].end = end;
110 :     sched->workerData[i].axis = axis;
111 :     sched->workerData[i].workerType = workerType;
112 :     retWorker = &sched->workerData[i];
113 :     sched->jobsRunning +=1;
114 :     pthread_cond_signal (&sched->workerData[i].runWait);
115 :     sched->nextWorker++;
116 :     if(sched->nextWorker == sched->numWorkers-1)
117 :     sched->nextWorker = 0;
118 :     break;
119 :     }
120 :     }
121 :     pthread_mutex_unlock (&sched->lock);
122 :     return retWorker;
123 :     }
124 :    
125 :    
126 : lamonts 2453 /* Assigns a worker to perform a spatial task (merge sort, merge,or tree node construction) */
127 : lamonts 2562 SpatialWorkerArgs_t * Diderot_Grab_SpatailWorker(SpatialScheduler_t* sched,ParSpatialWorkerType workerType,void * nodeData, bool * donePtr){
128 : lamonts 2422
129 : lamonts 2453 SpatialWorkerArgs_t * retWorker = 0;
130 :     pthread_mutex_lock (&sched->lock);
131 : lamonts 2565 for(int i = sched->nextWorker; i < sched->numWorkers; i++){
132 : lamonts 2453 if(sched->workerData[i].isIdle){
133 :     sched->workerData[i].isIdle = false;
134 :     sched->workerData[i].data = nodeData;
135 : lamonts 2562 sched->workerData[i].isDone = donePtr;
136 : lamonts 2453 sched->workerData[i].workerType = workerType;
137 :     retWorker = &sched->workerData[i];
138 : lamonts 2571 sched->jobsRunning +=1;
139 : lamonts 2453 pthread_cond_signal (&sched->workerData[i].runWait);
140 :     sched->nextWorker++;
141 : lamonts 2565 if(sched->nextWorker == sched->numWorkers-1)
142 : lamonts 2453 sched->nextWorker = 0;
143 :     break;
144 :     }
145 :     }
146 :     pthread_mutex_unlock (&sched->lock);
147 :     return retWorker;
148 : lamonts 2422 }
149 : lamonts 2453 /* parallel version of the merge sort for the spatial indices */
150 : lamonts 2574 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)
151 : lamonts 2422 {
152 : lamonts 2562 bool isDone = false;
153 : lamonts 2453 // If the depth is less than zero or there's not enough work to perform in parallel
154 :     // then run the sequential version.
155 :     if (high - low + 1 <= sched->seqThreshold || depth <= 0)
156 :     {
157 : lamonts 2572 Diderot_Spatial_SeqMergeSort(wrld,indices,tmpIndices,low,high,dim);
158 : lamonts 2453 return;
159 :     }
160 :     if(low < high) {
161 :     int mid = (low + high) / 2;
162 :     depth--;
163 : lamonts 2422
164 : lamonts 2453 //Assign a worker to do the upper half the merge sort.
165 :     MergetSortNode_t node;
166 :     node.low=low;
167 :     node.high = mid;
168 :     node.indices = tmpIndices;
169 :     node.tmpIndices = indices;
170 :     node.depth = depth;
171 :     node.dim = dim;
172 :    
173 : lamonts 2562 SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,MERGESORT_WORKER,(void *)&node,&isDone);
174 : lamonts 2453
175 :     //If a worker is not avaliable then this worker will perform both halves.
176 :     if(!worker){
177 :     Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,low, mid,depth,dim);
178 :     Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,mid + 1, high, depth,dim);
179 :     }else {
180 : lamonts 2570 Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,mid + 1, high, depth,dim);
181 : lamonts 2453 //Wait until the worker has completed its task
182 :     pthread_mutex_lock (&worker->lock);
183 : lamonts 2562 while(!isDone)
184 : lamonts 2570 pthread_cond_wait (&worker->done,&worker->lock);
185 :     pthread_mutex_unlock (&worker->lock);
186 :     }
187 :     //Merge the two sorted lists.
188 :     Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices,low, mid, mid + 1, high, low, depth,dim);
189 : lamonts 2453 }
190 :    
191 : lamonts 2574 }
192 : lamonts 2453 /* parallel version of the merge operation for the spatial indices */
193 : lamonts 2574 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)
194 : lamonts 2453 {
195 :     int nL = highL - lowL + 1;
196 :     int nR = highR - lowR + 1;
197 : lamonts 2562 bool isDone = false;
198 : lamonts 2453
199 :     // If the depth is less than zero or there's not enough work to perform in parallel
200 :     // then run the sequential version.
201 :     if (nL + nR <= sched->seqThreshold || depth <= 0)
202 : lamonts 2570 {
203 :     Diderot_Spatial_SeqMerge(wrld,indices,tmpIndices,lowL, highL, lowR, highR,low,dim);
204 : lamonts 2453 return;
205 :     }
206 :    
207 :     if (nL < nR)
208 :     {
209 :     Diderot_KDTree_SwapValues(&lowL,&lowR);
210 :     Diderot_KDTree_SwapValues(&highL,&highR);
211 :     Diderot_KDTree_SwapValues(&nL,&nR);
212 :     }
213 :     if(nL == 0) return;
214 :     else
215 :     {
216 :     int midL = (lowL + highL) / 2;
217 :    
218 :     Diderot_real_t pivot = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[midL]],dim);
219 :    
220 :     int midR = Diderot_BinarySearch(wrld,tmpIndices, lowR, highR, pivot,dim);
221 :    
222 : lamonts 2562 int mid = low + (midL - lowL) + (midR - lowR);
223 : lamonts 2453
224 :     indices[mid] = tmpIndices[midL];
225 :    
226 : lamonts 2572 //Note: The offset is needed for the way the tree is built. We need to make sure the next axis to be sorted
227 :     //has a duplicate copy of the current sorted axis
228 :     int offSet = (dim + 1) == wrld->spatialTree->dim ? -(dim * wrld->numStrands) : ((dim + 1) * wrld->numStrands);
229 :     indices[mid + offSet] = tmpIndices[midL];
230 :     tmpIndices[mid + offSet] = tmpIndices[midL];
231 :    
232 :     depth--;
233 : lamonts 2453
234 :     //Have a worker perform the upper half of the merge
235 :     MergeNode_t node;
236 :     node.depth = depth;
237 :     node.lowL = lowL;
238 :     node.highL= midL - 1;
239 :     node.lowR = lowR;
240 : lamonts 2562 node.indices = indices;
241 :     node.tmpIndices = tmpIndices;
242 : lamonts 2453 node.highR = midR - 1;
243 :     node.low = low;
244 :     node.dim = dim;
245 :    
246 : lamonts 2562 SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,MERGE_WORKER,(void *)&node,&isDone);
247 : lamonts 2453
248 :     if(!worker){
249 :     Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, lowL, midL-1, lowR, midR -1, low, depth,dim);
250 :     Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, midL + 1, highL, midR, highR, mid + 1, depth,dim);
251 :     }else {
252 :     Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, midL + 1, highL, midR, highR, mid + 1, depth,dim);
253 :     pthread_mutex_lock (&worker->lock);
254 : lamonts 2562 while(!isDone)
255 : lamonts 2453 pthread_cond_wait (&worker->done,&worker->lock);
256 :     pthread_mutex_unlock (&worker->lock);
257 :     }
258 :     }
259 : lamonts 2574 }
260 : lamonts 2453 /*The worker function for all the workers */
261 :     void treeWorker(SpatialWorkerArgs_t * workerArg){
262 :    
263 :     while(!workerArg->sched->buildIsDone)
264 :     {
265 :     //Wait until a task is assigned to the worker
266 :     pthread_mutex_lock (&workerArg->sched->lock);
267 : lamonts 2582 if(!workerArg->sched->buildIsDone){
268 : lamonts 2571 if(workerArg->sched->numRunning - 1 > 0 || workerArg->sched->jobsRunning > 0)
269 : lamonts 2566 {
270 :     workerArg->sched->numRunning-=1;
271 : lamonts 2582 if(workerArg->isIdle)
272 :     pthread_cond_wait (&workerArg->runWait,&workerArg->sched->lock);
273 : lamonts 2571 if(!workerArg->isIdle)
274 :     workerArg->sched->jobsRunning -=1;
275 : lamonts 2566 }else {
276 :     workerArg->sched->buildIsDone = true;
277 : lamonts 2574 printTree(workerArg->wrld->spatialTree->root);
278 : lamonts 2566 for(unsigned int i = 0; i < workerArg->sched->numWorkers; i++){
279 :     if(i != workerArg->id)
280 :     pthread_cond_signal (&workerArg->sched->workerData[i].runWait);
281 :     }
282 : lamonts 2582 workerArg->sched->stopTime = (airTime() - workerArg->sched->startTime);
283 :     printf("NEW maybe fixed parallel time to sort=%f\n",workerArg->sched->stopTime);
284 :     exit(1);
285 :    
286 : lamonts 2566 }
287 :     workerArg->sched->numRunning+=1;
288 :     }
289 : lamonts 2453 pthread_mutex_unlock (&workerArg->sched->lock);
290 : lamonts 2562 if(workerArg->sched->buildIsDone){
291 : lamonts 2582 workerArg->isIdle = true;
292 : lamonts 2562 break;
293 :     }
294 : lamonts 2453 //Based on the worker type perform the assigned task.
295 :     if(workerArg->workerType == MERGESORT_WORKER){
296 :     MergetSortNode_t * node = (MergetSortNode_t *)workerArg->data;
297 : lamonts 2582 //printf("<1>\n");
298 :     Diderot_Spatial_ParMergeSort(workerArg->wrld,
299 : lamonts 2453 workerArg->sched,
300 :     node->indices,
301 :     node->tmpIndices,
302 :     node->low,
303 :     node->high,
304 :     node->depth,
305 : lamonts 2582 node->dim);
306 : lamonts 2453
307 :     }else if(workerArg->workerType == MERGE_WORKER) {
308 :     MergeNode_t * node = (MergeNode_t *)workerArg->data;
309 : lamonts 2582 //printf("<2>\n");
310 :     Diderot_Spatial_ParMerge(workerArg->wrld,
311 : lamonts 2453 workerArg->sched,
312 :     node->indices,
313 :     node->tmpIndices,
314 :     node->lowL,
315 :     node->highL,
316 :     node->lowR,
317 :     node->highR,
318 :     node->low,
319 :     node->depth,
320 : lamonts 2582 node->dim);
321 : lamonts 2453 }else if(workerArg->workerType == TREE_WORKER){
322 : lamonts 2570 KDNode_t* node = (KDNode_t *)workerArg->data;
323 : lamonts 2571 /* if((node->start + node->len)- 1> workerArg->wrld->numStrands || node->strandId > workerArg->wrld->numStrands){
324 :     printf("worker=%d, PROBLEM start = %d len = %d id=%d\n",workerArg->id,node->start,node->len,node->strandId);
325 : lamonts 2570 exit(1);
326 : lamonts 2571 }*/
327 : lamonts 2582 printf("Should not be called\n");
328 : lamonts 2570 node->right = Diderot_KDTree_BuildHelper(workerArg->wrld,
329 : lamonts 2453 workerArg->sched,
330 :     node->start,
331 :     node->len,
332 :     node->axis);
333 :    
334 : lamonts 2582 }else if(workerArg->workerType == SORT_WORKER){
335 :     // printf("<3>\n");
336 :     preSort(workerArg->wrld,
337 :     workerArg->sched,
338 :     workerArg->start,
339 :     workerArg->end,
340 :     workerArg->axis);
341 :     }
342 : lamonts 2453 //Notify any worker waiting for this task to be completed.
343 : lamonts 2566 if(workerArg->workerType == MERGESORT_WORKER ||
344 :     workerArg->workerType == MERGE_WORKER) {
345 :     pthread_mutex_lock (&workerArg->lock);
346 :     *(workerArg->isDone)= true;
347 :     pthread_cond_signal (&workerArg->done);
348 :     pthread_mutex_unlock (&workerArg->lock);
349 :     }
350 : lamonts 2577 workerArg->isIdle = true;
351 : lamonts 2453 }
352 :     }
353 :     /* Finds the median strand in an array of strands based on the given axis*/
354 : lamonts 2574 @STRANDTY@ * find_median_sort(@PREFIX@World_t *wrld, SpatialScheduler_t * sched, int start, int end, int idx, int * mid){
355 : lamonts 2453
356 :     int startIdx = start + (idx * wrld->numStrands);
357 :     int endIdx = end + (idx * wrld->numStrands);
358 :     int midIdx = startIdx + (endIdx - startIdx)/2;
359 :    
360 :     if(end <= start) return NULL;
361 :     if(end == start + 1) {
362 :     *mid = start;
363 :     return wrld->inState[wrld->spatialIndices[startIdx]];
364 :     }
365 : lamonts 2574 /*int count = 0;
366 : lamonts 2570 bool error=false;
367 :     for(int i = startIdx + 1; i < endIdx; i++){
368 :    
369 :     Diderot_real_t t1 = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[i-1]],idx);
370 :     Diderot_real_t t2 = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[i]],idx);
371 :     if(t1 > t2){
372 :     printf("Problem start=%d, end=%d curr=%d, t1=%f t2=%f\n",start,end,count,t1,t2);
373 :     error = true;
374 :     }
375 :     count++;
376 :     }
377 : lamonts 2574
378 : lamonts 2570 if(error)
379 : lamonts 2574 exit(1); */
380 : lamonts 2453 *mid = start + (end-start)/2;
381 : lamonts 2574 /*if(midIdx > (2 * wrld->numStrands)) {
382 : lamonts 2570 printf("MidIdx is bigger = %d\n",midIdx);
383 : lamonts 2574 exit(1);*/
384 : lamonts 2453 return wrld->inState[wrld->spatialIndices[midIdx]];
385 : lamonts 2574 }
386 :     void preSort(@PREFIX@World_t *wrld, SpatialScheduler_t * sched,int start, int len, int axis)
387 : lamonts 2572 {
388 :     if(!len) return;
389 :     int startIdx = start + (axis * wrld->numStrands);
390 :     int endIdx = (start + len) + (axis * wrld->numStrands);
391 :    
392 : lamonts 2582 // printf("Begin sorting Leader=%d\n",sched->leaderId);
393 : lamonts 2572 Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,startIdx,endIdx- 1,333960,axis);
394 : lamonts 2582 // printf("Done sorting\n");
395 : lamonts 2572 axis = (axis + 1) % wrld->spatialTree->dim;
396 :     int mid = start + ((start + len)-start)/2;
397 : lamonts 2582
398 :     SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorkerSort(sched,SORT_WORKER,mid + 1,start + len - (mid+ 1), axis);
399 :    
400 :     if(!worker){
401 :     preSort(wrld,sched,start,mid - start, axis);
402 :     preSort(wrld,sched,mid + 1,start + len - (mid+ 1), axis);
403 :     }else {
404 :     // printf("<1>\n");
405 :     preSort(wrld,sched,start,mid - start, axis);
406 :     }
407 : lamonts 2574 }
408 : lamonts 2572 @STRANDTY@ * find_median(@PREFIX@World_t *wrld,int start, int end, int dim){
409 :    
410 :     if(end <= start) return NULL;
411 :     if(end == start + 1) return wrld->inState[wrld->spatialIndices[start]];;
412 :     int curr, store, mid = start + (end-start)/2;
413 :     Diderot_real_t pivot;
414 :     int count = 0;
415 :     while(true) {
416 :    
417 :     pivot = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[mid]],dim);
418 :    
419 :     //printf("Pivot = %f\n",pivot);
420 :    
421 : lamonts 2574 Diderot_KDTree_SwapValuesUInt(&wrld->spatialIndices[mid],&wrld->spatialIndices[end -1]);
422 : lamonts 2572
423 :     for (store = curr = start; curr < end; curr++) {
424 :     Diderot_real_t currVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[curr]],dim);
425 :     if (currVal < pivot) {
426 :     if (curr != store)
427 : lamonts 2574 Diderot_KDTree_SwapValuesUInt(&wrld->spatialIndices[curr], &wrld->spatialIndices[store]);
428 : lamonts 2572 store++;
429 :     }
430 :     }
431 : lamonts 2574 Diderot_KDTree_SwapValuesUInt(&wrld->spatialIndices[store],&wrld->spatialIndices[end -1]);
432 : lamonts 2572
433 :     /* median has duplicate values */
434 :     Diderot_real_t storeVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[store]],dim);
435 :     Diderot_real_t midVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[mid]],dim);
436 :     if (storeVal == midVal){
437 :     return wrld->inState[wrld->spatialIndices[mid]];
438 :     }
439 :     if (store > mid) end = store;
440 :     else start = store;
441 :    
442 :    
443 :     }
444 :     return NULL;
445 :     }
446 :    
447 :     static int count = 0;
448 : lamonts 2453 /* A recursive tree building function */
449 :     KDNode_t * Diderot_KDTree_BuildHelper(@PREFIX@World_t *wrld, SpatialScheduler_t * sched,int start, int len, int axis)
450 :     {
451 :     KDNode_t* newNode = NULL;
452 : lamonts 2562 bool isDone = false;
453 : lamonts 2453 @STRANDTY@ * n;
454 :     if (!len) return 0;
455 : lamonts 2572 int end = start + len;
456 :     int mid = start + (end-start)/2;
457 : lamonts 2570
458 : lamonts 2572 if ((n = find_median(wrld,start,start + len,axis))) {
459 : lamonts 2570 pthread_mutex_lock (&sched->lock);
460 : lamonts 2572 newNode = Diderot_KDTree_GrabNode(wrld->spatialTree);
461 : lamonts 2563 pthread_mutex_unlock (&sched->lock);
462 : lamonts 2453 newNode->strandId = n->strandId;
463 :     axis = (axis + 1) % wrld->spatialTree->dim;
464 :    
465 :     // If the depth is less than zero or there's not enough work to perform in parallel
466 :     // then run the sequential version.
467 :     if(len < sched->seqThreshold){
468 :     newNode->left = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);
469 :     newNode->right = Diderot_KDTree_BuildHelper(wrld,sched,mid + 1,start + len - (mid+ 1), axis);
470 :     }else{
471 :     //Have a woker build the right side of the tree.
472 : lamonts 2570 newNode->axis = axis;
473 :     newNode->len = start + len - (mid + 1);
474 :     newNode->start = mid + 1;
475 : lamonts 2453
476 : lamonts 2571 /*if((newNode->start + newNode->len)- 1> wrld->numStrands | newNode->strandId > wrld->numStrands){
477 :     printf("BCALL: INSIDE BUILD no worker, PROBLEM start = %d len = %d before len = %d before start=%d it should be=%d\n",newNode->start,newNode->len,len,start,start + len - (mid + 1));
478 :     } */
479 : lamonts 2453
480 : lamonts 2571 SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,TREE_WORKER,newNode,&isDone);
481 : lamonts 2570
482 : lamonts 2571
483 :     /* if((newNode->start + newNode->len)- 1> wrld->numStrands | newNode->strandId > wrld->numStrands){
484 : lamonts 2570 if(worker)
485 : lamonts 2571 printf("INSIDE BUILD worker=%d, PROBLEM start = %d len = %d before len = %d before start=%d it should be=%d\n",worker->id,newNode->start,newNode->len,len,start,start + len - (mid + 1));
486 : lamonts 2570 else
487 : lamonts 2571 printf("INSIDE BUILD no worker, PROBLEM start = %d len = %d before len = %d before start=%d it should be=%d\n",newNode->start,newNode->len,len,start,start + len - (mid + 1));
488 : lamonts 2570 exit(1);
489 : lamonts 2571 }*/
490 : lamonts 2570
491 : lamonts 2453 if(!worker){
492 :     newNode->left = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);
493 :     newNode->right = Diderot_KDTree_BuildHelper(wrld,sched,mid + 1,start + len - (mid+ 1), axis);
494 :     }else {
495 :     newNode->left = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);
496 :     }
497 : lamonts 2422 }
498 : lamonts 2453 }
499 :     return newNode;
500 :     }
501 : lamonts 2562 void Diderot_KDTree_Build(@PREFIX@World_t *wrld, uint32_t id, double * spatialTotalTime)
502 : lamonts 2453 {
503 :     SpatialScheduler_t * sched = wrld->spatialSched;
504 : lamonts 2562 if(sched->leaderId != id) {
505 : lamonts 2453 treeWorker(&sched->workerData[id]);
506 :     return;
507 : lamonts 2422 }
508 : lamonts 2571 sched->startTime = airTime();
509 : lamonts 2453 KDTree_t * tree = wrld->spatialTree;
510 : lamonts 2570 int numStrands = *(tree->numOfStrands);
511 : lamonts 2572 // memcpy(wrld->spatialTmpIndices,wrld->spatialIndices, sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
512 : lamonts 2453 Diderot_KDTree_PoolClear(tree);
513 : lamonts 2570 /* Sort the position data */
514 : lamonts 2572 /*double spatialST0 = airTime();
515 : lamonts 2570 Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,0,numStrands -1,33390,0);
516 :     if(@SPATIAL_DIMENSION@ > 1){
517 :     Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,wrld->numStrands,(2 * wrld->numStrands)-1,33390,1);
518 :     if(@SPATIAL_DIMENSION@ > 2){
519 :     Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,wrld->numStrands * 2,(3 * wrld->numStrands)-1,33390,2);
520 :     }
521 : lamonts 2572 }*/
522 : lamonts 2571 // double spatialTotalTimeS = (airTime() - spatialST0);
523 :     // if(spatialTotalTimeS >= 0.03)
524 :     // printf("maybe fixed parallel time to sort=%f\n",spatialTotalTimeS);
525 : lamonts 2582 // double spatialST0 = airTime();
526 : lamonts 2574 preSort(wrld,sched,0,*(tree->numOfStrands),0);
527 : lamonts 2582 // double spatialTotalTimeS = (airTime() - spatialST0);
528 :     // if(spatialTotalTimeS >= 0.03)
529 : lamonts 2570
530 : lamonts 2582 pthread_mutex_lock(&sched->lock);
531 :     sched->numWorkers +=1;
532 :     pthread_mutex_unlock(&sched->lock);
533 :     treeWorker(&sched->workerData[id]);
534 :    
535 : lamonts 2453 tree->root = Diderot_KDTree_BuildHelper(wrld, wrld->spatialSched,0,*(tree->numOfStrands),0);
536 : lamonts 2571 // printf("!!!!!!DONE!!!!\n");
537 : lamonts 2570 pthread_mutex_lock(&sched->lock);
538 :     sched->numWorkers +=1;
539 :     pthread_mutex_unlock(&sched->lock);
540 : lamonts 2566 treeWorker(&sched->workerData[id]);
541 : lamonts 2565 //printTree(tree->root);
542 : lamonts 2571 *(spatialTotalTime) = *(spatialTotalTime) + sched->stopTime;
543 :     //printf("Build Done\n");
544 : lamonts 2453 }
545 :     void Diderot_KDTree_Init(@PREFIX@World_t *wrld)
546 :     {
547 :     Diderot_KDTree_Alloc(&wrld->spatialTree,&wrld->numStrands,@SPATIAL_DIMENSION@);
548 :     wrld->spatialIndices= NEWVEC(uint32_t,@SPATIAL_DIMENSION@ * wrld->numStrands);
549 :     wrld->spatialTmpIndices= NEWVEC(uint32_t,@SPATIAL_DIMENSION@ * wrld->numStrands);
550 : lamonts 2422
551 : lamonts 2453 uint32_t len = @SPATIAL_DIMENSION@ * wrld->numStrands;
552 : lamonts 2422
553 : lamonts 2453 SpatialScheduler_t * scheduler = (SpatialScheduler_t *)CheckedAlloc(sizeof(SpatialScheduler_t));
554 :     if ((pthread_mutex_init (&scheduler->lock, 0)) != 0){
555 :     printf("Error in initializing the spatial scheduler's lock");
556 :     exit(EXIT_FAILURE);
557 :     }
558 :     int nWorkers = wrld->sched->numWorkers;
559 :     SpatialWorkerArgs_t * workerArgs = NEWVEC(SpatialWorkerArgs_t, nWorkers);
560 :     scheduler->workerData=workerArgs;
561 :     scheduler->nextWorker = 0;
562 : lamonts 2562 scheduler->numRunning= 0;
563 : lamonts 2453 scheduler->seqThreshold = SPATIAL_SEQ_THERSHOLD;
564 :     scheduler->numWorkers = nWorkers;
565 :     scheduler->buildIsDone = false;
566 :     wrld->spatialSched = scheduler;
567 : lamonts 2422
568 : lamonts 2453 for(unsigned int i = 0; i < nWorkers; i++){
569 : lamonts 2582 workerArgs[i].isIdle = true;
570 : lamonts 2453 workerArgs[i].data= 0;
571 :     workerArgs[i].sched = scheduler;
572 :     workerArgs[i].wrld = wrld;
573 :     workerArgs[i].id = i;
574 :     if ((pthread_cond_init (&(workerArgs[i].runWait), 0)) != 0){
575 :     printf("Error in initializing the scheduler lock");
576 :     exit(EXIT_FAILURE);
577 :     }
578 :     if ((pthread_cond_init (&(workerArgs[i].done), 0)) != 0){
579 :     printf("Error in initializing the done condition var ");
580 :     exit(EXIT_FAILURE);
581 :     }
582 :     if ((pthread_mutex_init (&(workerArgs[i].lock), 0)) != 0){
583 :     printf("Error in initializing the worker lock");
584 :     exit(EXIT_FAILURE);
585 :     }
586 :     }
587 :     for(uint32_t i = 0; i < len; i++){
588 :     wrld->spatialIndices[i]= i % wrld->numStrands;
589 :     }
590 : lamonts 2422 }
591 : lamonts 2453 void Diderot_KDTree_Realloc(@PREFIX@World_t *wrld)
592 :     {
593 :     wrld->spatialIndices= (uint32_t*)CheckedAlloc(sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
594 :     wrld->spatialTmpIndices= (uint32_t*)CheckedAlloc(sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
595 :     uint32_t len = @SPATIAL_DIMENSION@ * wrld->numStrands;
596 :     for(uint32_t i = 0; i < len; i++){
597 :     wrld->spatialIndices[i]= i % wrld->numStrands;
598 :     }
599 :     }

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