[I2 logo] [RWTH logo] MOVES: Software Modeling and Verification
(Informatik 2)
Computer Science / RWTH / I2 / Research / Skil / Examples / Psrs
Printer-friendly
Skil Sample Applications

Parallel Sorting by Regular Sampling



#include "Par/par.c"
#include "Array/array.h"


typedef struct _VarArr
        {
           int *fields ;
           int  cnt    ;
        }
        *VarArr ;


typedef struct _MultArr
        {
           VarArr *vs  ;
           int     cnt ;
        }
        *MultArr ;



static void pck_f (VarArr v, Buff buff)
{
   char *FName = "pck_f" ;

   if (! v)
   {
      buff->len  = 0    ;
      buff->buff = NULL ;
   }
   else
   {
      buff->len  = (v->cnt + 1) * sizeof (int)                      ;
      buff->buff = (char *) VRealloc (buff->buff, buff->len, FName) ;

      memcpy (buff->buff,                 & v->cnt,          sizeof (int)) ;
      memcpy (buff->buff + sizeof (int), v->fields, v->cnt * sizeof (int)) ;
   }

   return ;
}


static void upck_f (Buff buff, VarArr *vptr)
{
   char   *FName = "upck_f" ;
   VarArr  v     = *vptr    ;

   memcpy (& v->cnt, buff->buff, sizeof (int))                            ;
   v->fields = (int *) VRealloc (v->fields, v->cnt * sizeof (int), FName) ;
   memcpy (v->fields, buff->buff + sizeof (int), v->cnt * sizeof(int))    ;

   return ;
}


static VarArr ident_f (VarArr v, Index ix)
{
   return (v) ;
}


static VarArr dup_f (VarArr v)
{
   char   *FName = "dup_f" ;
   VarArr  ret             ;

   ret = (VarArr) VMalloc (sizeof (struct _VarArr), FName) ;

   ret->cnt    = v->cnt                                         ;
   ret->fields = (int *) VMalloc (v->cnt * sizeof (int), FName) ;
   memcpy (ret->fields, v->fields, v->cnt * sizeof (int))       ;

   return (ret) ;
}


static int *def_lowerbd (int procNr)
{
   int *res = (int *) VMalloc (2 * sizeof (int), "def_lowerbd") ;

   res[0] = 0      ;
   res[1] = procId ;

   return (res) ;
}


static VarArr init_f1 (int size, Index ix)
{
   VarArr  res               ;
   char   *FName = "init_f1" ;
   int     i                 ;
   int    *fs                ;

   fs = (int *) VMalloc (size * sizeof (int), FName) ;

   for (i = 0 ; i < size ; i++)
      fs[i] = (netSize - procId) * size + size - i ;

   res = (VarArr) VMalloc (sizeof (struct _VarArr), FName) ;

   res->fields = fs   ;
   res->cnt    = size ;

   return (res) ;
}


static VarArr init_f2 (Index ix)
{
   VarArr  res               ;
   char   *FName = "init_f2" ;
   int     i                 ;
   int    *fs                ;

   fs = (int *) VMalloc (netSize * sizeof (int), FName) ;

   for (i = 0 ; i < netSize ; i++)
      fs[i] = 0 ;

   res = (VarArr) VMalloc (sizeof (struct _VarArr), FName) ;

   res->fields = fs      ;
   res->cnt    = netSize ;

   return (res) ;
}


static MultArr init_f3 (Index ix)
{
   MultArr  res               ;
   VarArr   crt               ;
   char    *FName = "init_f3" ;
   int      i                 ;
   int     *fs                ;

   res = (MultArr) VMalloc (sizeof (struct _MultArr), FName) ;

   res->vs  = (VarArr *) VMalloc (netSize * sizeof (VarArr), FName) ;
   res->cnt = netSize ;

   for (i = 0 ; i < netSize ; i++)
   {
      crt = (VarArr) VMalloc (sizeof (struct _VarArr), FName) ;

      crt->fields = NULL ;
      crt->cnt    = 0    ;

      res->vs[i]  = crt  ;
   }

   return (res) ;
}


static VarArr null_f (Index ix)
{
   VarArr  res              ;
   char   *FName = "null_f" ;

   res = (VarArr) VMalloc (sizeof (struct _VarArr), FName) ;

   res->fields = NULL ;
   res->cnt    = 0    ;

   return (res) ;
}


static void destroy_f1 (VarArr v)
{
   VFree (v->fields) ;
   VFree (v)         ;

   return ;
}


static void destroy_f3 (MultArr m)
{
   int    i   ;
   VarArr crt ;

   for (i = 0 ; i < netSize ; i++)
   {
      crt = m->vs[i]      ;
      VFree (crt->fields) ;
      VFree (crt)         ;
   }

   VFree (m->vs) ;
   VFree (m)     ;

   return ;
}


static int *perm_f (int i, Index ix)
{
   Index ret ;

   ret[0] =  ix[0]                ;
   ret[1] = (ix[1] + i) % netSize ;

   return (ret) ;
}


static VarArr append_f (VarArr v1, VarArr v2)
{
   char *FName = "append_f" ;

   if (! v1 || v1->cnt == 0)
      return (v2) ;

   if (! v2 || v2->cnt == 0)
      return (v1) ;

   v1->fields = (int *) VRealloc (v1->fields, (v1->cnt + v2->cnt) *
                                              sizeof (int), FName)   ;
   memcpy (v1->fields + v1->cnt, v2->fields, v2->cnt * sizeof (int)) ;
   v1->cnt += v2->cnt                                                ;

   return (v1) ;
}


static int lt (int *x, int *y)
{
   return (*x - *y) ;
}


static VarArr sort_f (VarArr v, Index ix)
{
   qsort ((void *) v->fields, v->cnt, sizeof (int),
          (int (*) (void *, void *)) lt) ;

   return (v) ;
}


static VarArr sample_f (array <VarArr> b, int samplegap, VarArr v, Index ix)
{
   int     i, j, cnt, bcnt    ;
   VarArr  bv                 ;
   Bounds  bds                ;
   int    *fs, *bfs           ;
   char   *FName = "sample_f" ;
   Index   ix                 ;

   bds   = array_part_bounds (b)  ;
   ix[0] = bds->lowerBd[0]        ;
   ix[1] = bds->lowerBd[1]        ;
   bv    = array_get_elem (b, ix) ;
   cnt   = v->cnt                 ;
   fs    = v->fields              ;
   bcnt  = bv->cnt                ;
   bfs   = bv->fields             ;

   for (i = 0, j = 0 ; i < cnt && j < bcnt ; i += samplegap, j++)
      bfs[j] = fs[i] ;

   return (v) ;
}


static int *bin_search (int *vect, int len, int val)
{
   int l, r, m ;

   l = 0   ;
   r = len ;

   while (1)
   {
      m = (l + r) / 2 ;

      if (val < vect[m])
         r = m - 1 ;
      else
         l = m + 1 ;

      if ((vect[m-1] <= val && vect[m] > val) || l > r)
         break ;
   }

   return (vect + m) ;
} 


static VarArr get_ith_subarray (int i, int *pivots, VarArr p_el, VarArr v,
                                Index ix)
{
   int  *low, *high                 ;
   char *FName = "get_ith_subarray" ;

   if (i == 0)
   {
      low  = v->fields                               ;
      high = bin_search (v->fields, v->cnt, *pivots) ;
   }
   else if (i == netSize - 1)
   {
      low  = bin_search (v->fields, v->cnt, pivots[i-1]) ;
      high = v->fields + v->cnt                          ;
   }
   else
   {
      low  = bin_search (v->fields, v->cnt, pivots[i-1]) ;
      high = bin_search (v->fields, v->cnt, pivots[i]  ) ;
   }

   p_el->cnt = high - low                                                      ;
   p_el->fields = (int*) VRealloc (p_el->fields, p_el->cnt *sizeof(int), FName);
   memcpy (p_el->fields, low, p_el->cnt * sizeof (int))                        ;

   return (v) ;
}


static VarArr copy_ith_subarray (int i, MultArr m_el, VarArr v, Index ix)
{
   VarArr  tmp   = m_el->vs[i]         ;
   char   *FName = "copy_ith_subarray" ;

   tmp->cnt = v->cnt                                                          ;
   tmp->fields = (int *) VRealloc (tmp->fields, v->cnt * sizeof (int), FName) ;
   memcpy (tmp->fields, v->fields, v->cnt * sizeof (int))                     ;

   return (v) ;
}


static MultArr merge_subarrays (VarArr a_el, MultArr m, Index ix)
{
   char   *FName = "merge_subarrays" ;
   int     len, i, crtpos, cnt       ;
   VarArr  v                         ;
   int    *crts                      ;
   int     min, minslot              ;

   cnt = m->cnt ;

   for (i = 0, len = 0 ; i < cnt ; i++)
      if (v = m->vs[i])
         len += v->cnt ;

   a_el->cnt    = len                                                        ;
   a_el->fields = (int *) VRealloc (a_el->fields, len * sizeof (int), FName) ;

   crts = (int *) VMalloc (cnt * sizeof (int), FName) ;

   for (i = 0 ; i < cnt ; i++)
      crts[i] = 0 ;

   for (crtpos = 0 ; crtpos < len ; crtpos++)
   {
      for (i = 0, minslot = -1 ; i < cnt ; i++)
      {
         v = m->vs[i] ;

         if (crts[i] < v->cnt)
            if (minslot == -1)
            {
               minslot = i                  ;
               min     = v->fields[crts[i]] ;
            }
            else
               if (v->fields[crts[i]] < min)
               {
                  minslot = i                  ;
                  min     = v->fields[crts[i]] ;
               }
      }

      a_el->fields[crtpos] = min ;
      crts[minslot]++            ;
   }

   VFree (crts) ;

   return (m) ;
}


static void psrs (array <VarArr> a, int a_partsize)
{
   array <VarArr>   b, p                     ;
   array <MultArr>  m                        ;
   Index            totalsize, blocksize, ix ;
   VarArr           v, a_el, p_el            ;
   MultArr          m_el                     ;
   int             *pivots, *fs              ;
   char            *FName = "psrs"           ;
   int              i, j, cnt                ;

   array_map (sort_f, a, a) ;

   if (netSize == 1)
      return ;

   totalsize[0] = 1       ;
   totalsize[1] = netSize ;

   blocksize[0] = 0 ;
   blocksize[1] = 1 ;

   b = array_create (1, totalsize, blocksize, def_lowerbd, init_f2) ;

   array_map (sample_f (b, a_blocksize/netSize), a, a) ;

   v = array_fold (ident_f, append_f, b, pck_f, upck_f, dup_f) ;

   ix[0] = 0 ;
   ix[1] = 0 ;

   sort_f (v, ix) ;

   cnt    = v->cnt                                                ;
   fs     = v->fields                                             ;
   pivots = (int *) VMalloc ((netSize - 1) * sizeof (int), FName) ;

   for (i = 3 * netSize / 2 - 1, j = 0 ; i < cnt && j < netSize - 1 ;
        i += netSize, j++)
      pivots[j] = fs[i] ;

   p = array_create (1, totalsize, blocksize, def_lowerbd, null_f ) ;
   m = array_create (1, totalsize, blocksize, def_lowerbd, init_f3) ;

   ix[0] = 0      ;
   ix[1] = procId ;

   p_el = array_get_elem (p, ix) ;
   m_el = array_get_elem (m, ix) ;
   a_el = array_get_elem (a, ix) ;

   for (i = 0 ; i < netSize ; i++)
   {
      array_map (get_ith_subarray ((i+procId) % netSize, pivots, p_el), a, a) ;
      array_permute_blocks (p, perm_f (i), pck_f, upck_f)                     ;
      array_map (copy_ith_subarray (i, m_el), p, p)                           ;
   }

   array_map (merge_subarrays (a_el), m, m) ;

   VFree (pivots) ;

   array_destroy (m, destroy_f3) ;
   array_destroy (p, destroy_f1) ;

   array_destroy (b, destroy_f1) ;

   return ;
}


int main (int argc, char **argv)
{
   array <VarArr>  a                    ;
   int             size                 ;
   char           *FName = "main"       ;
   Index           totalsize, blocksize ;
   VarArr          v                    ;

   par_init   () ;
   array_init () ;

   size = atoi (argv[1]) ;

   totalsize[0] = 1       ;
   totalsize[1] = netSize ;

   blocksize[0] = 0 ;
   blocksize[1] = 1 ;

   a = array_create (1, totalsize, blocksize, def_lowerbd, init_f1 (size/netSize)) ;

   psrs (a, size/netSize) ;

   array_destroy (a, destroy_f1) ;

   array_close () ;
   par_close   () ;

   return (0) ;
}


Back to the Skil home page

Valid HTML 4.01 Strict! Valid CSS!