My Weblog

Blog about programming and math

Data Parallelism in C ( Parallel Merging )

I was trying to simulate data parallelism using threads in C. In data parallelism, we distribute the data across different processors ( threads in this case ) and run the same code on chunk of data. In this case, threads are not going to interact with each other. I thought of writing parallel merging. Here is excellent tutorial on parallel merge and I borrowed binary search because I was bit lazy to debug my upper_bound code. This code’s performance is not very good because it creates lot of threads and it deteriorates the performance ( The purpose here is data parallelism but I will write optimized merge sort ). We can change this behavior when our list is small then use sequential merging rather than creating more thread. There are couple of more problems where we can use data parallelism i.e. matrix multiplication , primes in given range. For finding primes in given range, say we have [ 1 .. 10 ] then I can ran two threads. I can assign [ 1.. 5 ] to first thread and [ 6 .. 10] to second thread and run Miller-Rabin in each thread to test the primality.Guy Blelloch page on nested data parallelism.

#include<cstdio>
#include<pthread.h>
#include<algorithm>
using namespace std;

int  T[20000] , M[20000];

struct data 
  { 
    int p_1 , r_1 , p_2 , r_2 , pos ;
  };
int bsearch( int value , int left, int right )
{
    long low  = left;
    long high = max( left, right + 1 );
    while( low < high )
    {
        long mid = ( low + high ) / 2;
        if ( value <= T[ mid ] ) high = mid;
        else low  = mid + 1; 
    }
    return high ;
}

void* pMerge ( void *args ) 
   {

          pthread_t tid[2];
          printf("id = %li\n" ,( unsigned long int )  pthread_self() );
          struct data* t =  ( struct data* ) ( args ) ;  
          int p_1 = t->p_1 , r_1 = t->r_1 , p_2 = t->p_2 , r_2 = t->r_2  , pos = t->pos ;
          int n_1 = r_1 - p_1 + 1 , n_2 = r_2 - p_2 + 1 ;
          if ( n_1 < n_2 ) 
          {
            swap ( p_1 , p_2 ) ;
            swap ( r_1 , r_2 ) ;
            swap ( n_1 , n_2 ) ;
          }
          if ( n_1 <=  0 ) return NULL ; 
          int q_1 = ( p_1 + r_1 ) >> 1 ;
          int q_2 = /*upper_bound ( &T[p_2] , &T[r_2] , T[q_1] ) - &T[p_2] ; */ bsearch ( T[q_1]  , p_2 , r_2 )  ;
          int q_3 = pos + ( q_1 - p_1 ) + ( q_2 - p_2 ) ;
          //printf("p_1 = %d r_1 = %d p_2 = %d r_2 = %d pos = %d  q_1 = %d q_2 = %d\n" , p_1 , r_2 , p_2 , r_2 , pos , q_1 , q_2 );
          M[q_3] = T[q_1] ;
          struct data m , n ;
          m.p_1 = p_1 , m.r_1 = q_1 - 1 , m.p_2 = p_2 , m.r_2 = q_2 - 1 ,  m.pos = pos ; 
          n.p_1 = q_1 + 1 , n.r_1 = r_1 , n.p_2 = q_2 , n.r_2 = r_2 , n.pos = q_3 + 1 ;
          pthread_create( &tid[0] , NULL , pMerge , &m );
          pthread_create( &tid[1] , NULL , pMerge , &n ); 
          pthread_join ( tid [ 0 ]  , NULL );
          pthread_join ( tid [ 1 ]  , NULL );
          return NULL; 
   } 


int main()
  {
        int m , n ;
        scanf("%d%d",&m , &n ) ;
        for(int i = 0 ; i < m ; i++ ) T[i] = ( int ) random() % 10000 ;
        for( int i = 0 ; i < n ; i++ ) T[i+m] = ( int ) random() % 10000 ;
        sort( &T[0], &T[m] );
        sort( &T[m] , &T[m+n] );
        pthread_t tid ;
        struct data d; 
        d.p_1 = 0 , d.r_1 = m-1 , d.p_2 = m , d.r_2 = m+n-1 , d.pos = 0 ; 
        pthread_create ( &tid , NULL , pMerge , &d );
        pthread_join ( tid , NULL );
        for( int i = 0 ; i < m+n ; i++ ) printf("%d " , M[i]);
        printf("\n" );
  }
Mukeshs-MacBook-Pro:GitRepo mukeshtiwari$ g++ ParallelMerge.cpp  -lpthread
Mukeshs-MacBook-Pro:GitRepo mukeshtiwari$ ./a.out 
10 1
id = 4325466112
id = 4326002688
id = 4326539264
id = 4327075840
id = 4327612416
id = 4328685568
id = 4328148992
id = 4329222144
id = 4329758720
id = 4331905024
id = 4332441600
id = 4332978176
id = 4330295296
id = 4330831872
id = 4331368448
id = 4333514752
id = 4334051328
id = 4334587904
id = 4329222144
id = 4332441600
id = 4329758720
id = 4327075840
id = 4330295296
492 886 1421 2362 2777 5386 6649 6915 7793 8335 9383 

If you have any comments or suggestion then please let me know.

Advertisements

December 27, 2012 - Posted by | Programming | , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: