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 2453 - (view) (download)

1 : lamonts 2453 /* sequential version of the merge sort for the spatial indices */
2 :     void Diderot_Spatial_SeqMergeSort(@PREFIX@World_t *wrld, uint32_t * indices, uint32_t * tmpIndices, int low, int high, uint32_t dim)
3 : lamonts 2422 {
4 :    
5 : lamonts 2453 if (low >= high)
6 :     return;
7 : lamonts 2422
8 : lamonts 2453 int mid = (low + high) / 2;
9 :    
10 :     //Sort two sub-arrays first so that they are placed into the temporary
11 :     //indices array.
12 :     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 : lamonts 2422 }
61 : lamonts 2453 }
62 :     /* 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 :     if(low > high + 1)
72 :     high = low;
73 :     else
74 :     high = high + 1;
75 : lamonts 2422
76 : lamonts 2453 while (low < high)
77 :     {
78 :     int mid = (low + high) / 2;
79 :     Diderot_real_t pivot = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[mid]],dim);
80 :     if (pivot < searchValue)
81 :     low = mid + 1;
82 :     else
83 :     high = mid;
84 :     }
85 :     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 : lamonts 2422
90 : lamonts 2453 SpatialWorkerArgs_t * retWorker = 0;
91 :     pthread_mutex_lock (&sched->lock);
92 :     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);
107 :     return retWorker;
108 : lamonts 2422 }
109 : lamonts 2453 /* 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 : lamonts 2422 {
112 : lamonts 2453 // 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 : lamonts 2422
123 : lamonts 2453 //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 :     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 : lamonts 2422 }
333 : lamonts 2453 }
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 : lamonts 2422 }
349 : lamonts 2453 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 : lamonts 2422
364 : lamonts 2453 uint32_t len = @SPATIAL_DIMENSION@ * wrld->numStrands;
365 : lamonts 2422
366 : lamonts 2453 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 : lamonts 2422
380 : lamonts 2453 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 : lamonts 2422 }
403 : lamonts 2453 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 :     }

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