openmpsort.h File Reference

#include <stddef.h>

Include dependency graph for openmpsort.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
void	qsort_openmp (void *base, size_t nmemb, size_t size, int(*compar)(const void *, const void *))

Function Documentation

qsort_openmp()

void qsort_openmp	(	void *	base,
		size_t	nmemb,
		size_t	size,
		int(*)(const void *, const void *)	compar
	)

Definition at line 205 of file openmpsort.c.

                                                                   {
    int Nt = omp_get_max_threads();
    ptrdiff_t * Anmemb = ta_malloc("Anmemb", ptrdiff_t, Nt);
    ptrdiff_t * Anmemb_old = ta_malloc("Anmemb_old", ptrdiff_t, Nt);
 
    void ** Abase_store = ta_malloc("Abase", void *, Nt);
    void ** Atmp_store = ta_malloc("Atmp", void *, Nt);
    void ** Abase = Abase_store;
    void ** Atmp = Atmp_store;
 
    /*Should I use indirect sorting?*/
    int indirect = 0;
    if(size > 32)
        indirect = 1;
    void * tmp;
    /*NOTE: if this allocation becomes a problem,
     * switch to glibc's quicksort (serial!) */
    if(indirect)
        tmp = mymalloc("qsort",2*nmemb*sizeof(void *) + size);
    else
        tmp = mymalloc("qsort", size * nmemb);
 
#pragma omp parallel
    {
        int tid = omp_get_thread_num();
        /* actual number of threads*/
        int Nt = omp_get_num_threads();
 
        /* domain decomposition */
        ptrdiff_t start = tid * nmemb / Nt;
        ptrdiff_t end = (tid + 1) * nmemb / Nt;
        /* save decoposition to global array for merging */
        Anmemb[tid] = end - start;
        Anmemb_old[tid] = end - start;
        Abase[tid] = ((char*) base) + start * size;
        Atmp[tid] = ((char*) tmp) + start * size;
 
        struct msort_param p;
        p.t = ((char **) Atmp)[tid];
        p.s = size;
        p.var = 4;
        p.cmp = compar;
        /*For large arrays we use an indirect sort following glibc*/
        if(indirect)
        {
            /* Indirect sorting: copy everything in this thread to the new pointer space,
             * which is after the tmp space. */
            char *ip = (char *) Abase[tid];
            void **tp = (void **) ((char *)tmp + (nmemb + start)* sizeof (void *));
            void **t = tp;
            void *end = (void *) (tp + Anmemb[tid]);
 
            while ((void *) t < end)
            {
              *t++ = ip;
              ip += size;
            }
            p.s = sizeof (void *);
            p.var = 3;
            Abase[tid] = tp;
            Atmp[tid] = ((char*) tmp) + start * p.s;
            p.t = ((char **)Atmp)[tid];
        }
        else {
            /*Copied from glibc*/
            if ((size & (sizeof (uint32_t) - 1)) == 0
                && ((char *) base - (char *) 0) % __alignof__ (uint32_t) == 0)
              {
                if (size == sizeof (uint32_t))
                  p.var = 0;
                else if (size == sizeof (uint64_t)
                         && ((char *) base - (char *) 0) % __alignof__ (uint64_t) == 0)
                  p.var = 1;
                else if ((size & (sizeof (unsigned long) - 1)) == 0
                         && ((char *) base - (char *) 0)
                            % __alignof__ (unsigned long) == 0)
                  p.var = 2;
              }
            /*End copied from glibc*/
        }
        msort_with_tmp (&p, Abase[tid], Anmemb[tid]);
        /* now each sub array is sorted, kick start the merging */
        int sep;
        for (sep = 1; sep < Nt; sep *=2 ) {
            int color = tid / sep;
            int key = tid % sep;
#if 0
            if(tid == 0) {
                printf("sep = %d Abase[0] %p base %p, Atmp[0] %p tmp %p\n",
                        sep, Abase[0], base, Atmp[0], tmp);
                printf("base 73134 = %d 73135 = %d\n", ((int*) base)[73134], ((int*) base)[73135]);
                printf("tmp  73134 = %d 73135 = %d\n", ((int*) tmp )[73134], ((int*) tmp )[73135]);
            }
#endif
#pragma omp barrier
            /* only group leaders work */
            if(key == 0 && color % 2 == 0) {
                int nextT = tid + sep;
                /*merge with next guy */
                /* only even leaders arrives to this point*/
                if(nextT >= Nt) {
                    /* no next guy, copy directly.*/
                    merge(Abase[tid], Anmemb[tid], NULL, 0, Atmp[tid], p.s, compar, indirect);
                }  else {
#if 0
                    printf("%d + %d merging with %td/%td:%td %td/%td:%td\n", tid, nextT,
                            ((char*)Abase[tid] - (char*) base) / size,
                            ((char*)Abase[tid] - (char*) tmp) / size,
                            Anmemb[tid],
                            ((char*)Abase[nextT] - (char*) base) / size,
                            ((char*)Abase[nextT] - (char*) tmp) / size,
                            Anmemb[nextT]);
#endif
                    merge(Abase[tid], Anmemb[tid], Abase[nextT], Anmemb[nextT], Atmp[tid], p.s, compar, indirect);
                    /* merge two lists */
                    Anmemb[tid] = Anmemb[tid] + Anmemb[nextT];
                    Anmemb[nextT] = 0;
                }
            }
 
            /* now swap Abase and Atmp for next merge */
#pragma omp barrier
            if(tid == 0) {
                void ** a = Abase;
                Abase = Atmp;
                Atmp = a;
            }
            /* at this point Abase contains the sorted array */
        }
#pragma omp barrier
        /* output was written to the tmp rather than desired location, copy it */
        if((!indirect && Abase[0] != base)
                || (indirect && Abase[0] != (char *) tmp + nmemb * sizeof(void *))) {
            memmove(Atmp[tid], Abase[tid], Anmemb_old[tid] * p.s);
        }
    }
 
    ta_free(Atmp_store);
    ta_free(Abase_store);
    ta_free(Anmemb_old);
    ta_free(Anmemb);
 
    /*Copied from glibc*/
    /* tp[0] .. tp[n - 1] is now sorted, copy around entries of
       the original array (done serially).  Knuth vol. 3 (2nd ed.) exercise 5.2-10.  */
    if(indirect) {
        char *kp, *ip;
        size_t i;
        void **tp = (void **) ((char *) tmp + nmemb * sizeof (void *));
        void *tmp_storage = (void *) (tp + nmemb);
        for (i = 0, ip = (char *) base; i < nmemb; i++, ip += size)
          if ((kp = ((char **)tp)[i]) != ip)
            {
              size_t j = i;
              char *jp = ip;
              memcpy (tmp_storage, ip, size);
 
              do {
                size_t k = (kp - (char *) base) / size;
                tp[j] = jp;
                memcpy (jp, kp, size);
                j = k;
                jp = kp;
                kp = ((char **)tp)[k];
              } while (kp != ip);
 
              tp[j] = jp;
              memcpy (jp, tmp_storage, size);
            }
    }
    myfree(tmp);
}

References msort_param::cmp, merge(), msort_with_tmp(), myfree, mymalloc, msort_param::s, msort_param::t, ta_free, ta_malloc, and msort_param::var.

Here is the call graph for this function: