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

SCM Repository

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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 2583 - (download) (annotate)
Thu Apr 10 19:50:28 2014 UTC (5 years, 5 months ago) by lamonts
File size: 24727 byte(s)
Made presort parallel
//Debugging purpoes 
void printTree(KDNode_t* newNode){
    if(newNode != NULL){
        printf("id=%d\n",newNode->strandId); 
        printTree(newNode->right); 
        printTree(newNode->left); 
    }
}
/* Swaps the values at two addresses */ 
void Diderot_KDTree_SwapValuesUInt(uint32_t * a, uint32_t *b){
    uint32_t temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
/* Swaps the values at two addresses */ 
void Diderot_KDTree_SwapValues(int * a, int *b){
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}
/* sequential version of the merge sort for the spatial indices */ 
void Diderot_Spatial_SeqMergeSort(@PREFIX@World_t *wrld, uint32_t * indices, uint32_t * tmpIndices, int low, int high, uint32_t dim)
{

	if (low >= high)
		return;

	int mid = (low + high) / 2;

	//Sort two sub-arrays first so that they are placed into the temporary
	//indices array.
	Diderot_Spatial_SeqMergeSort(wrld,tmpIndices,indices, low, mid,dim);
	Diderot_Spatial_SeqMergeSort(wrld,tmpIndices,indices, mid + 1, high,dim);

	// Once temporary indice array contains the two sorted sub-arrays
	// they are merged into indice array
    Diderot_Spatial_SeqMerge(wrld,indices,tmpIndices,low, mid, mid + 1, high,low,dim);
}
/* sequential version of the merge operation for the spatial indices */ 
/* Note: Sub-arrays are adjacent to each other in the 
   the sequential version but not necessarily for the parallel version;
   therefore, sub-arrays boundaries must be specified
   explicitly.*/ 
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)
{
	int high = low + highL - lowL + highR - lowR + 1;

    //Note: The offset is needed for the way the tree is built. We need to make sure the next axis to be sorted 
    //has a duplicate copy of the current sorted axis 
    int offSet = (dim + 1) == wrld->spatialTree->dim ? -(dim * wrld->numStrands) : ((dim + 1) * wrld->numStrands);
    // Bottom-up implementation
	for (;low <= high; low++)
	{
			if (lowL > highL){
				indices[low] = tmpIndices[lowR];
            	indices[low + offSet] = tmpIndices[lowR];
				tmpIndices[low + offSet] = tmpIndices[lowR];
				lowR++;
			}else if (lowR > highR) {
				indices[low] = tmpIndices[lowL];
				indices[low + offSet] = tmpIndices[lowL];
				tmpIndices[low + offSet] = tmpIndices[lowL];
				lowL++;
			}else {
				Diderot_real_t lowLValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowL]],dim);
				Diderot_real_t lowRValue = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[lowR]],dim);
				if(lowLValue < lowRValue){
					indices[low] = tmpIndices[lowL];
                    indices[low + offSet] = tmpIndices[lowL];
					tmpIndices[low + offSet] = tmpIndices[lowL];
					lowL++;
				}else {
					indices[low] = tmpIndices[lowR];
                    indices[low + offSet] = tmpIndices[lowR];
					tmpIndices[low + offSet] = tmpIndices[lowR];
					lowR++;
				}
			}
	}
}
int Diderot_BinarySearch(@PREFIX@World_t *wrld,uint32_t *tmpIndices, int low, int high, Diderot_real_t searchValue, int dim)
{
		if(low > high + 1)
			high = low;
		else
			high = high + 1;

        while (low < high)
        {
            int mid = (low + high) / 2;
            Diderot_real_t pivot = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[mid]],dim);
            if (pivot < searchValue)
                low = mid + 1;
            else
                high = mid;
        }
        return low;
}
SpatialWorkerArgs_t * Diderot_Grab_SpatailWorkerSort(SpatialScheduler_t* sched,ParSpatialWorkerType workerType,int start, int end, int axis){

    SpatialWorkerArgs_t * retWorker = 0;
    pthread_mutex_lock (&sched->lock);
         for(int i = sched->nextWorker; i < sched->numWorkers; i++){
                if(sched->workerData[i].isIdle){
                     sched->workerData[i].isIdle = false;
                     sched->workerData[i].start = start; 
                     sched->workerData[i].end = end; 
                     sched->workerData[i].axis = axis; 
                     sched->workerData[i].workerType = workerType;
                    retWorker = &sched->workerData[i];
                     sched->jobsRunning +=1; 
                    pthread_cond_signal (&sched->workerData[i].runWait);
                    sched->nextWorker++;
                    if(sched->nextWorker == sched->numWorkers-1)
                        sched->nextWorker = 0;
                    break;
                }
         }
    pthread_mutex_unlock (&sched->lock);
    return retWorker;
}


/* Assigns a worker to perform a spatial task (merge sort, merge,or tree node construction) */ 
SpatialWorkerArgs_t * Diderot_Grab_SpatailWorker(SpatialScheduler_t* sched,ParSpatialWorkerType workerType,void * nodeData, bool * donePtr){

	SpatialWorkerArgs_t * retWorker = 0;
	pthread_mutex_lock (&sched->lock);
	 	 for(int i = sched->nextWorker; i < sched->numWorkers; i++){
	 		 	if(sched->workerData[i].isIdle){
	 		 		 sched->workerData[i].isIdle = false;
	 		 		 sched->workerData[i].data = nodeData;
	 		 		 sched->workerData[i].isDone = donePtr;
	 		 		 sched->workerData[i].workerType = workerType;
	 		 		retWorker = &sched->workerData[i];
                     sched->jobsRunning +=1; 
	 		 		pthread_cond_signal (&sched->workerData[i].runWait);
	 		 		sched->nextWorker++;
		 		 	if(sched->nextWorker == sched->numWorkers-1)
		 		 		sched->nextWorker = 0;
		 		 	break;
	 		 	}
	 	 }
	pthread_mutex_unlock (&sched->lock);
    return retWorker;
}
/* parallel version of the merge sort for the spatial indices */ 
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)
{
	bool isDone = false; 
    // If the depth is less than zero or there's not enough work to perform in parallel 
    // then run the sequential version. 
    if (high - low + 1 <= sched->seqThreshold || depth <= 0)
    {
	    Diderot_Spatial_SeqMergeSort(wrld,indices,tmpIndices,low,high,dim);
        return;
    }
    if(low < high) {
        int mid = (low + high) / 2;
	    depth--;

        //Assign a worker to do the upper half the merge sort. 
	    MergetSortNode_t node;
	    node.low=low;
	    node.high = mid;
	    node.indices = tmpIndices;
	    node.tmpIndices = indices;
	    node.depth = depth;
	    node.dim = dim;

	    SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,MERGESORT_WORKER,(void *)&node,&isDone);

        //If a worker is not avaliable then this worker will perform both halves. 
	    if(!worker){
	    	   Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,low, mid,depth,dim);
	    	   Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,mid + 1, high, depth,dim);
	    }else {
	 	    Diderot_Spatial_ParMergeSort(wrld,sched,tmpIndices,indices,mid + 1, high, depth,dim);
            //Wait until the worker has completed its task 
	 	    pthread_mutex_lock (&worker->lock);
    	  	    while(!isDone)
	 		        pthread_cond_wait (&worker->done,&worker->lock);
	 		pthread_mutex_unlock (&worker->lock);
	    }
        //Merge the two sorted lists. 
		Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices,low, mid, mid + 1, high, low, depth,dim);
	  }

}
/* parallel version of the merge operation for the spatial indices */ 
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)
{
    int nL = highL - lowL + 1;
    int nR = highR - lowR + 1;
    bool isDone = false; 

    // If the depth is less than zero or there's not enough work to perform in parallel 
    // then run the sequential version.
    if (nL + nR <= sched->seqThreshold || depth <= 0)
    {    
    	Diderot_Spatial_SeqMerge(wrld,indices,tmpIndices,lowL, highL, lowR, highR,low,dim);
        return;
    }

    if (nL < nR)
    {
    	    Diderot_KDTree_SwapValues(&lowL,&lowR);
    	    Diderot_KDTree_SwapValues(&highL,&highR);
    	    Diderot_KDTree_SwapValues(&nL,&nR);
    }
    if(nL == 0) return;
    else
    {
        int midL = (lowL + highL) / 2;

        Diderot_real_t pivot = Diderot_KDTree_GetPosValue(wrld->inState[tmpIndices[midL]],dim);
        
     	int midR = Diderot_BinarySearch(wrld,tmpIndices, lowR, highR, pivot,dim);

        int mid = low + (midL - lowL) + (midR - lowR);

        indices[mid] = tmpIndices[midL];

        //Note: The offset is needed for the way the tree is built. We need to make sure the next axis to be sorted 
        //has a duplicate copy of the current sorted axis 
        int offSet = (dim + 1) == wrld->spatialTree->dim ? -(dim * wrld->numStrands) : ((dim + 1) * wrld->numStrands);
        indices[mid + offSet] = tmpIndices[midL];
        tmpIndices[mid + offSet] = tmpIndices[midL];
    	
        depth--;

        //Have a worker perform the upper half of the merge 
    	    MergeNode_t node;
        	node.depth = depth;
    	    node.lowL = lowL;
    	    node.highL= midL - 1;
    	    node.lowR = lowR;
			node.indices = indices;
			node.tmpIndices = tmpIndices;
    	    node.highR = midR - 1;
    	    node.low = low;
    	    node.dim = dim;

    	    SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,MERGE_WORKER,(void *)&node,&isDone);

    	    if(!worker){
    		    Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, lowL, midL-1, lowR, midR -1, low, depth,dim);
            	Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, midL + 1, highL, midR, highR, mid + 1, depth,dim);
    	    }else {
        	   Diderot_Spatial_ParMerge(wrld,sched,indices,tmpIndices, midL + 1, highL, midR, highR, mid + 1, depth,dim);
    	  	    pthread_mutex_lock (&worker->lock);
    	  	        while(!isDone)
    	  	  	        pthread_cond_wait (&worker->done,&worker->lock);
    	  	    pthread_mutex_unlock (&worker->lock);
    	   }
   }
}
/*The worker function for all the workers */ 
void treeWorker(SpatialWorkerArgs_t * workerArg){

	while(!workerArg->sched->buildIsDone)
	{
        //Wait until a task is assigned to the worker 
	    pthread_mutex_lock (&workerArg->sched->lock);
            if(!workerArg->sched->buildIsDone){
                if(workerArg->sched->numRunning - 1 > 0 || workerArg->sched->jobsRunning > 0)
                {
                   workerArg->sched->numRunning-=1; 
                   if(workerArg->isIdle)
                        pthread_cond_wait (&workerArg->runWait,&workerArg->sched->lock);
                   if(!workerArg->isIdle)
                     workerArg->sched->jobsRunning -=1; 
                }else {
                    workerArg->sched->buildIsDone = true; 
                    printTree(workerArg->wrld->spatialTree->root);
                    for(unsigned int i = 0; i < workerArg->sched->numWorkers; i++){
                        if(i != workerArg->id)
                            pthread_cond_signal (&workerArg->sched->workerData[i].runWait);
                    }
                    workerArg->sched->stopTime = (airTime() - workerArg->sched->startTime);
                    printf("NEW maybe fixed parallel time to sort=%f\n",workerArg->sched->stopTime);
                    exit(1); 
   
                }
                workerArg->sched->numRunning+=1;
            }
	    pthread_mutex_unlock (&workerArg->sched->lock);
	    if(workerArg->sched->buildIsDone){
			workerArg->isIdle = true; 
	    	break;
	    }
        //Based on the worker type perform the assigned task. 
	    if(workerArg->workerType == MERGESORT_WORKER){
	    	    MergetSortNode_t * node = (MergetSortNode_t *)workerArg->data;
                //printf("<1>\n"); 
	        	Diderot_Spatial_ParMergeSort(workerArg->wrld,
	    			                  workerArg->sched,
	       				          node->indices,
	       				          node->tmpIndices,
	    				              node->low,
	    				              node->high,
	    				              node->depth,
	    				              node->dim);

	    }else if(workerArg->workerType == MERGE_WORKER) {
	    	    MergeNode_t * node = (MergeNode_t *)workerArg->data;
                //printf("<2>\n"); 
	    	    Diderot_Spatial_ParMerge(workerArg->wrld,
	    			              workerArg->sched,
   				              node->indices,
   				              node->tmpIndices,
   				              node->lowL,
   				              node->highL,
   				              node->lowR,
   				              node->highR,
   				              node->low,
   				              node->depth,
   				              node->dim);
	    }else if(workerArg->workerType == TREE_WORKER){
	    	    KDNode_t*  node = (KDNode_t  *)workerArg->data;
               /* if((node->start + node->len)- 1> workerArg->wrld->numStrands || node->strandId  > workerArg->wrld->numStrands){
                    printf("worker=%d, PROBLEM start = %d len = %d id=%d\n",workerArg->id,node->start,node->len,node->strandId); 
                    exit(1); 
                }*/ 
                printf("Should not be called\n"); 
	    	    node->right = Diderot_KDTree_BuildHelper(workerArg->wrld,
	    					      workerArg->sched,
	    						  node->start,
	    						  node->len,
	    					      node->axis);

	    }else if(workerArg->workerType == SORT_WORKER){
              //  printf("<3>\n"); 
                preSort(workerArg->wrld,
                        workerArg->sched,
                        workerArg->start,
                        workerArg->end,
                        workerArg->axis);
        }
        //Notify any worker waiting for this task to be completed. 
		if(workerArg->workerType == MERGESORT_WORKER || 
           workerArg->workerType == MERGE_WORKER) {
            pthread_mutex_lock (&workerArg->lock);
		       *(workerArg->isDone)= true;
	           pthread_cond_signal (&workerArg->done);
	       pthread_mutex_unlock (&workerArg->lock);
        }
        workerArg->isIdle = true; 
	}
}
/* Finds the median strand in an array of strands based on the given axis*/  
@STRANDTY@ * find_median_sort(@PREFIX@World_t *wrld, SpatialScheduler_t * sched, int start, int end, int idx, int * mid){

	int startIdx = start + (idx * wrld->numStrands);
	int endIdx = end + (idx * wrld->numStrands);
	int midIdx = startIdx + (endIdx - startIdx)/2;

	if(end <= start) return NULL;
	if(end == start + 1) {
		*mid = start;
		return wrld->inState[wrld->spatialIndices[startIdx]];
	}
/*int count = 0;
bool error=false; 
   for(int i = startIdx + 1; i < endIdx; i++){ 
          
          Diderot_real_t t1 = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[i-1]],idx);
          Diderot_real_t t2 = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[i]],idx);
          if(t1 > t2){
              printf("Problem start=%d, end=%d curr=%d, t1=%f t2=%f\n",start,end,count,t1,t2); 
             error = true; 
          }
          count++; 
    }

    if(error)
        exit(1); */ 
	*mid = start + (end-start)/2;
    /*if(midIdx >  (2 * wrld->numStrands)) {
        printf("MidIdx is bigger = %d\n",midIdx);
        exit(1);*/ 
	return wrld->inState[wrld->spatialIndices[midIdx]];
} 
void preSort(@PREFIX@World_t *wrld, SpatialScheduler_t * sched,int start, int len, int axis)
{
    if(!len) return; 
    int startIdx = start + (axis * wrld->numStrands);
    int endIdx = (start + len) + (axis * wrld->numStrands);

  //  printf("Begin sorting Leader=%d\n",sched->leaderId); 
    Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,startIdx,endIdx- 1,333960,axis);
  //  printf("Done sorting\n"); 
    axis = (axis + 1) % wrld->spatialTree->dim;
    int mid = start + ((start + len)-start)/2;

    if(len < sched->seqThreshold){
        preSort(wrld,sched,start,mid - start, axis);
        preSort(wrld,sched,mid + 1,start + len - (mid+ 1), axis);
    }else {

    SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorkerSort(sched,SORT_WORKER,mid + 1,start + len - (mid+ 1), axis);

    if(!worker){ 
        preSort(wrld,sched,start,mid - start, axis);
        preSort(wrld,sched,mid + 1,start + len - (mid+ 1), axis);
    }else {
       // printf("<1>\n");
        preSort(wrld,sched,start,mid - start, axis); 
    }
    }
}
@STRANDTY@ * find_median(@PREFIX@World_t *wrld,int start, int end, int dim){

    if(end <= start) return NULL;
    if(end == start + 1) return wrld->inState[wrld->spatialIndices[start]];;
    int curr, store, mid =  start + (end-start)/2;
    Diderot_real_t pivot;
    int count = 0; 
    while(true) {
        
        pivot = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[mid]],dim);

        //printf("Pivot = %f\n",pivot); 

        Diderot_KDTree_SwapValuesUInt(&wrld->spatialIndices[mid],&wrld->spatialIndices[end -1]);

        for (store = curr = start; curr < end; curr++) {
            Diderot_real_t currVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[curr]],dim); 
            if (currVal < pivot) {
                if (curr != store)
                    Diderot_KDTree_SwapValuesUInt(&wrld->spatialIndices[curr], &wrld->spatialIndices[store]);
                store++;
            }
        }
        Diderot_KDTree_SwapValuesUInt(&wrld->spatialIndices[store],&wrld->spatialIndices[end -1]);

        /* median has duplicate values */
        Diderot_real_t storeVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[store]],dim); 
        Diderot_real_t midVal = Diderot_KDTree_GetPosValue(wrld->inState[wrld->spatialIndices[mid]],dim);
        if (storeVal  == midVal){
            return wrld->inState[wrld->spatialIndices[mid]];
        }
        if (store > mid)    end = store;
        else        start = store;


    }
    return NULL;
}

static int count = 0; 
/* A recursive tree building function */ 
KDNode_t * Diderot_KDTree_BuildHelper(@PREFIX@World_t *wrld, SpatialScheduler_t * sched,int start, int len, int axis)
{
	KDNode_t* newNode = NULL;
	bool isDone = false; 
	@STRANDTY@ * n;
	if (!len) return 0;
    int end = start + len; 
	int mid = start + (end-start)/2;

	if ((n = find_median(wrld,start,start + len,axis))) {
        pthread_mutex_lock (&sched->lock);
            newNode = Diderot_KDTree_GrabNode(wrld->spatialTree); 
        pthread_mutex_unlock (&sched->lock);
		newNode->strandId = n->strandId; 
		axis = (axis + 1) % wrld->spatialTree->dim;

        // If the depth is less than zero or there's not enough work to perform in parallel 
        // then run the sequential version.
        if(len < sched->seqThreshold){
    		    newNode->left  = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);
    		    newNode->right = Diderot_KDTree_BuildHelper(wrld,sched,mid + 1,start + len - (mid+ 1), axis);
        }else{
            //Have a woker build the right side of the tree. 
        	newNode->axis = axis;
     	    newNode->len = start + len - (mid + 1);
     	    newNode->start = mid + 1;

          /*if((newNode->start + newNode->len)- 1> wrld->numStrands | newNode->strandId  > wrld->numStrands){
                    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)); 
                } */ 

  	        SpatialWorkerArgs_t * worker = Diderot_Grab_SpatailWorker(sched,TREE_WORKER,newNode,&isDone);


               /* if((newNode->start + newNode->len)- 1> wrld->numStrands | newNode->strandId  > wrld->numStrands){
                    if(worker)
                    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)); 
                    else 
                    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)); 
                    exit(1); 
                }*/ 

        	    if(!worker){
    		        newNode->left  = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);
    		        newNode->right = Diderot_KDTree_BuildHelper(wrld,sched,mid + 1,start + len - (mid+ 1), axis);
    	        }else {
    		        newNode->left  = Diderot_KDTree_BuildHelper(wrld,sched,start,mid - start, axis);
    	        }
        }
	}
	return newNode;
}
void Diderot_KDTree_Build(@PREFIX@World_t *wrld, uint32_t id, double * spatialTotalTime) 
{
    SpatialScheduler_t * sched  =  wrld->spatialSched; 
    if(sched->leaderId != id) { 
        treeWorker(&sched->workerData[id]); 
        return; 
    }
    sched->startTime = airTime();
    KDTree_t * tree  = wrld->spatialTree; 
    int numStrands = *(tree->numOfStrands); 
  //  memcpy(wrld->spatialTmpIndices,wrld->spatialIndices, sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
    Diderot_KDTree_PoolClear(tree); 	
    /* Sort the position data */ 
    /*double spatialST0 = airTime();
    Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,0,numStrands -1,33390,0);
    if(@SPATIAL_DIMENSION@ > 1){
        Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,wrld->numStrands,(2 * wrld->numStrands)-1,33390,1);
        if(@SPATIAL_DIMENSION@ > 2){
            Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices,wrld->spatialTmpIndices,wrld->numStrands * 2,(3 * wrld->numStrands)-1,33390,2);
        }
    }*/ 
   // double spatialTotalTimeS = (airTime() - spatialST0);   
    // if(spatialTotalTimeS >= 0.03)
    //    printf("maybe fixed parallel time to sort=%f\n",spatialTotalTimeS);  
   // double spatialST0 = airTime();
    preSort(wrld,sched,0,*(tree->numOfStrands),0); 
   // double spatialTotalTimeS = (airTime() - spatialST0);   
    // if(spatialTotalTimeS >= 0.03) 

    pthread_mutex_lock(&sched->lock); 
        sched->numWorkers +=1; 
    pthread_mutex_unlock(&sched->lock); 
    treeWorker(&sched->workerData[id]);  

    tree->root = Diderot_KDTree_BuildHelper(wrld, wrld->spatialSched,0,*(tree->numOfStrands),0);
   // printf("!!!!!!DONE!!!!\n"); 
    pthread_mutex_lock(&sched->lock); 
        sched->numWorkers +=1; 
    pthread_mutex_unlock(&sched->lock); 
    treeWorker(&sched->workerData[id]);  
	//printTree(tree->root); 
	*(spatialTotalTime) = *(spatialTotalTime) + sched->stopTime; 
	//printf("Build Done\n"); 
}
void Diderot_KDTree_Init(@PREFIX@World_t *wrld) 
{
    Diderot_KDTree_Alloc(&wrld->spatialTree,&wrld->numStrands,@SPATIAL_DIMENSION@);
    wrld->spatialIndices= NEWVEC(uint32_t,@SPATIAL_DIMENSION@ * wrld->numStrands); 
    wrld->spatialTmpIndices= NEWVEC(uint32_t,@SPATIAL_DIMENSION@ * wrld->numStrands); 

    uint32_t len =  @SPATIAL_DIMENSION@ * wrld->numStrands; 

    SpatialScheduler_t * scheduler = (SpatialScheduler_t *)CheckedAlloc(sizeof(SpatialScheduler_t));
    if ((pthread_mutex_init (&scheduler->lock, 0)) != 0){
        printf("Error in initializing the spatial scheduler's lock");
	    exit(EXIT_FAILURE);
    }
    int nWorkers = wrld->sched->numWorkers;
	SpatialWorkerArgs_t * workerArgs = NEWVEC(SpatialWorkerArgs_t, nWorkers);
    scheduler->workerData=workerArgs; 	
    scheduler->nextWorker = 0;
    scheduler->numRunning= 0; 
    scheduler->seqThreshold = SPATIAL_SEQ_THERSHOLD;
    scheduler->numWorkers = nWorkers;
    scheduler->buildIsDone = false; 
    wrld->spatialSched = scheduler; 

    for(unsigned int i = 0; i < nWorkers; i++){
	      workerArgs[i].isIdle = true;
	      workerArgs[i].data= 0;
	      workerArgs[i].sched = scheduler;
          workerArgs[i].wrld = wrld; 
          workerArgs[i].id = i; 
	      if ((pthread_cond_init (&(workerArgs[i].runWait), 0)) != 0){
	      		 printf("Error in initializing the scheduler lock");
	      		 exit(EXIT_FAILURE);
	      	 }
	      if ((pthread_cond_init (&(workerArgs[i].done), 0)) != 0){
	      		 printf("Error in initializing the done condition var ");
	      		 exit(EXIT_FAILURE);
	      	 }
	 	 if ((pthread_mutex_init (&(workerArgs[i].lock), 0)) != 0){
	 		 printf("Error in initializing the worker lock");
	 		 exit(EXIT_FAILURE);
	 	 }
	 }   
    for(uint32_t  i = 0; i < len; i++){
        wrld->spatialIndices[i]= i % wrld->numStrands; 
    }
}
void Diderot_KDTree_Realloc(@PREFIX@World_t *wrld) 
{
    wrld->spatialIndices= (uint32_t*)CheckedAlloc(sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
    wrld->spatialTmpIndices= (uint32_t*)CheckedAlloc(sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
    uint32_t len =  @SPATIAL_DIMENSION@ * wrld->numStrands; 
    for(uint32_t  i = 0; i < len; i++){
	    wrld->spatialIndices[i]= i % wrld->numStrands; 
    }
}

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