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

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