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

Parent Directory | 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