Data Structure: Heap

Hi,

I’ve been seeing in the FERMI manual that it has an internal heap, and am interested in using it, because I use a heap data structure that put foreign attached to exemplify what I need, could I use this to replace the internal my? And the performance tends to decrease or increase?

-----heap.h-----

#ifndef HEAPH

#define HEAPH

#include "maze.h"

#define HEAPSIZE 100000

cell *heap[HEAPSIZE];

int heapsize;

int keylength;

void emptyheap(int length);

int testheap();

cell* popheap();

cell *topheap();

void deleteheap(cell *thiscell);

void insertheap(cell *thiscell);

#endif
-----heap.c-----

#include "include.h"

#include "heap.h"

cell *heap[HEAPSIZE];

int heapsize = 0;

int keylength = 3;

int keyless(cell *cell1, cell* cell2)

{

    int keyindex;

for (keyindex = 0; keyindex < keylength; ++keyindex)

    {

	if (cell1->key[keyindex] < cell2->key[keyindex])

	    return 1;

	else if (cell1->key[keyindex] > cell2->key[keyindex])

	    return 0;

    }

    return 0;

}

int testheap()

{

    int d;

for (d = heapsize/2; d > 0; d--)

    {

	assert(!keyless(heap[2*d],heap[d]));

	if (2*d+1 <= heapsize)

	    assert(!keyless(heap[2*d+1],heap[d]));

    }

}

void percolatedown(int hole, cell *tmp)

{

    int child;

if (heapsize != 0)

    {

	for (; 2*hole <= heapsize; hole = child)

        {

	    child = 2*hole;

	    if (child != heapsize && keyless(heap[child+1], heap[child]))

		++child;

	    if (keyless(heap[child], tmp))

            {

		heap[hole] = heap[child];

		heap[hole]->heapindex = hole;

            }

	    else

		break;

        }

	heap[hole] = tmp;

	heap[hole]->heapindex = hole;

    }

}

void percolateup(int hole, cell *tmp)

{

    if (heapsize != 0)

    {

	for (; hole > 1 && keyless(tmp, heap[hole/2]); hole /= 2)

        {

	    heap[hole] = heap[hole/2];

	    heap[hole]->heapindex = hole;

        }

	heap[hole] = tmp;

	heap[hole]->heapindex = hole;

    }

}

void percolateupordown(int hole, cell *tmp)

{

    if (heapsize != 0)

    {

	if (hole > 1 && keyless(tmp, heap[hole/2]))

	    percolateup(hole, tmp);

	else

	    percolatedown(hole, tmp);

    }

}

void emptyheap(int length)

{

    int i;

keylength = length;

    heapsize = 0;

}

cell *topheap()

{

    if (heapsize == 0)

	return NULL;

    return heap[1];

}

void deleteheap(cell *thiscell)

{

    if (thiscell->heapindex != 0 && thiscell->generated == mazeiteration)

    {

	percolateupordown(thiscell->heapindex, heap[heapsize--]);

	thiscell->heapindex = 0;

    }

}

cell* popheap()

{

    cell *thiscell;

if (heapsize == 0)

	return NULL;

    thiscell = heap[1];

    thiscell->heapindex = 0;

    percolatedown(1, heap[heapsize--]);

    return thiscell;

}

void insertheap(cell *thiscell)

{

    int hole;

if (thiscell->heapindex == 0 || thiscell->generated != mazeiteration)

    {

	thiscell->heapindex = 0;

#ifdef DEBUG

	assert(heapsize < HEAPSIZE-1);

#endif

	percolateup(++heapsize, thiscell);

    }

    else

	percolateupordown(thiscell->heapindex, heap[thiscell->heapindex]);

}

Thank you in advance for your help.

These are two different things that both go under the name “heap”. The heap that is the memory region used for dynamical allocations is not organized according to the data structure also called heap.

I’ve been looking now and yes, I noticed the difference is that once you could access the global memory as a heap so I was also thinking that maybe I had implemented such a structure to analyze the news of FERMI.

But since leaving for another question, I’ve been seeing this guy here: http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter33.html, where he has a parallel data structure, the do you think this structure that placed the code in another question needs to run well in the FERMI?

One question that came to me was the following the structure given above will be associated with a kernel only, the other kernels do not make access to it, so each one will exist solely for your own thread, not being an area shared with others. I think once the structure need not be shared and can be so right there that can tell me about it?