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 2562 - (download) (annotate)
Mon Mar 10 04:10:03 2014 UTC (5 years, 4 months ago) by lamonts
File size: 16341 byte(s)
Fixed bug with queryPool not allocating correctly and fixed deadlock of spatail data structure
/* 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++;
				}
			}
	}
}
/* Swaps the values at two addresses */ 
void Diderot_KDTree_SwapValues(int * a, int *b){
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
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;
}
/* 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-1; 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];
	 		 		pthread_cond_signal (&sched->workerData[i].runWait);
	 		 		sched->nextWorker++;
		 		 	if(sched->nextWorker == sched->numWorkers-2)
		 		 		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);

        //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] = tmpIndices[midL];
    	    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);
	    		workerArg->isIdle = true;
	        	while(workerArg->isIdle && !workerArg->sched->buildIsDone){
	            	pthread_cond_wait (&workerArg->runWait,&workerArg->sched->lock);
	        	}
	    pthread_mutex_unlock (&workerArg->sched->lock);

	    if(workerArg->sched->buildIsDone){
			workerArg->isIdle = false; 
	    	break;
	    }
        //Based on the worker type perform the assigned task. 
	    if(workerArg->workerType == MERGESORT_WORKER){
	    	    MergetSortNode_t * node = (MergetSortNode_t *)workerArg->data;
	        	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;
	    	    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){
	    	    TreeNode_t * node = (TreeNode_t *)workerArg->data;
	    	    node->parent->right = Diderot_KDTree_BuildHelper(workerArg->wrld,
	    					      workerArg->sched,
	    						  node->start,
	    						  node->len,
	    					      node->axis);

	    }
        //Notify any worker waiting for this task to be completed. 
		pthread_mutex_lock (&workerArg->lock);
		 *(workerArg->isDone)= true;
	     pthread_cond_signal (&workerArg->done);
	    pthread_mutex_unlock (&workerArg->lock);
	}
}
/* Finds the median strand in an array of strands based on the given axis*/  
@STRANDTY@ * find_median(@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]];
	}
	Diderot_Spatial_ParMergeSort(wrld,sched,wrld->spatialIndices, wrld->spatialTmpIndices, startIdx,endIdx-1,33453,idx);

	*mid = start + (end-start)/2;

	return wrld->inState[wrld->spatialIndices[midIdx]];
}
/* 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 mid;
	if ((n = find_median(wrld,sched,start,start + len,axis,&mid))) {
		newNode = Diderot_KDTree_GrabNode(wrld->spatialTree); 
		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. 
            TreeNode_t node;
        	node.axis = axis;
     	    node.len = start + len - (mid + 1);
     	    node.start = mid + 1;
        	node.parent = newNode;

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

        	    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);
    	  	        pthread_mutex_lock (&worker->lock);
    	  	            while(!isDone)
    	  	  	            pthread_cond_wait (&worker->done,&worker->lock);
    	  	        pthread_mutex_unlock (&worker->lock);
    	        }
        }
	}
	return newNode;
}
void printTree(KDNode_t* newNode){
	if(newNode != NULL){
		printf("id=%d\n",newNode->strandId); 
		printTree(newNode->right); 
		printTree(newNode->left); 
	}
}
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; 
    }
    double spatialT0  = airTime();
    KDTree_t * tree  = wrld->spatialTree; 
    memcpy(wrld->spatialTmpIndices,wrld->spatialIndices, sizeof(uint32_t)*@SPATIAL_DIMENSION@ * wrld->numStrands);
    Diderot_KDTree_PoolClear(tree); 	
    tree->root = Diderot_KDTree_BuildHelper(wrld, wrld->spatialSched,0,*(tree->numOfStrands),0);
    wrld->spatialSched->buildIsDone=true;        
   	for(unsigned int i = 0; i < sched->numWorkers-1; i++){
		 pthread_cond_signal (&sched->workerData[i].runWait);
	}
	printTree(tree->root); 
	*(spatialTotalTime) = *(spatialTotalTime) + (airTime() - spatialT0);   
}
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 = false;
	      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