multithreaded merge sort σε c-Επείγον

[mhche]

Καλημέρα, μήπως ξέρει κάνεις αν υπάρχει κάπου ο κώδικας της multithreaded merge sort σε c.

Ή αν μπορεί να με βοηθήσει κάποιος.

Ευχαριστώ πολύ,

[nucleus]

*I, ME AND MYSELF !!!: Threaded Merge Sort

με POSIX threads.

[mhche]

*I, ME AND MYSELF !!!: Threaded Merge Sort

με POSIX threads.

Ευχαριστώ πολύ,αλλά νομίζω πως οι γνώσεις μου απέχουν απ'αυτό.

Προσπαθώ να φτιάξω κάτι τέτοιο,όπου θα δημιουργώ δύο πίνακες με τυχαίες τιμές και έπειτα με πολυνηματική mergesort να τους ταξινομώ.

Ο παρακάτω κώδικας μου βγάζει segmentation fault(core dumped)

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define NUM_THREADS 2

int* x;
int* y; //sorted array
int n;

struct index{int p,r;};

void* merge_sort(void* param){
    struct index* pr = (struct index*) param;
    int p = pr->p,  r = pr->r , ret1,ret2;
    if (p==r)
        pthread_exit(0);

    pthread_t thread1,thread2;
    struct index pr1,pr2;
    int q = (p+r)/2;
    pr1.p = p;    pr1.r = q;
    pr2.p = q+1;  pr2.r = r;

    ret1 = pthread_create(&thread1,NULL,merge_sort,(void*) &pr1);
    if (ret1>0)
        printf("failed to create new thread 1\n");

    ret2 = pthread_create(&thread2,NULL,merge_sort,(void*) &pr2);
    if (ret2>0)
        printf("failed to create new thread 2\n");

    pthread_join(thread1,NULL);
    pthread_join(thread2,NULL);

    int k = p ,i = p ,j = q+1;

    while (i<=q && j<=r){
        if (x[i] < x[j])
            y[k++] = x[i++];
        else
            y[k++] = x[j++];
    }
    for (; i<=q ; i++)
        y[k++] = x[i];
    for (; j<=r ; j++)
        y[k++] = x[j];

    for (i= p ; i <= r ;i++)
        x[i] = y[i];

    pthread_exit(0);
    return NULL;
}
int main()
{

#    define SIZE 16384
    int i, A[SIZE],B[SIZE];

    for (i = 0; i < SIZE; i++){
        A[i] = rand() % 10000;
        B[i] = rand() % 10000;
    }

    merge_sort(A);
    merge_sort(;

    printf("after sort A: %d ", A[18],'\n');
    printf("after sort B: %d ", B[165],'\n');

    return 0;
}

[nucleus]

# define SIZE 16384

Preprocessor directive μέσα στην main *slap* :S.Αυτό είναι σε λάθος σημείο πρέπει να μπει μαζί με το άλλο define που έχεις στην αρχή εκτός και αν το έχεις ήδη διορθώσει οπότε συγνώμη για το slap.

Μήπως τα pr1 και pr2 πρέπει να είναι πίνακες με δομές τύπου index?

Επίσης είσαι σίγουρος ότι τα 2 printf δουλεύουν σωστά?

[mhche]

# define SIZE 16384

Preprocessor directive μέσα στην main *slap* :S.Αυτό είναι σε λάθος σημείο πρέπει να μπει μαζί με το άλλο define που έχεις στην αρχή εκτός και αν το έχεις ήδη διορθώσει οπότε συγνώμη για το slap.

Μήπως τα pr1 και pr2 πρέπει να είναι πίνακες με δομές τύπου index?

Επίσης είσαι σίγουρος ότι τα 2 printf δουλεύουν σωστά?

Δεν είναι λάθος το define στη main, όσο και αν θες να με *slap*

Ούτε τα pr είναι λάθος,τα printf δεν έχουν κάποια σχέση,περισσότερο αναγνωριστικά είναι.

Το λάθος είναι όταν καλώ την merge_sort,ώστε να ταξινομηθεί ο πίνακας.

Στην αρχή τα int* x,int* y εκεί κάτι γίνεται λάθος,μάλλον κάνει stack overflow γιαυτό περνω και το λάθος.

[nucleus]

Δεν έχεις κάνει πουθενά malloc για τα x και y.Δοκίμασε και μην ξεχάσεις και την free πάντα όταν τελειώσεις με τα x και y

Επίσης αφού κάνεις pthread_join γιατί κάνεις και pthread_exit(0)? Βγάλε το pthread_exit(0)

[mhche]

Δεν έχεις κάνει πουθενά malloc για τα x και y.Δοκίμασε και μην ξεχάσεις και την free πάντα όταν τελειώσεις με τα x και y

Επίσης αφού κάνεις pthread_join γιατί κάνεις και pthread_exit(0)? Βγάλε το pthread_exit(0)

malloc γιατί,αφου στην συνάρτηση μου υπάρχουν αυτά, τι να κάνω malloc όλη την συνάρτηση;

αν δεν κάνω pthread_exit(0) θα μου κρατάει την flag απ το thread πάνω στην ουσία,δλδ θα το χω κλειδωμένο

Νομίζω πως η συνάρτηση μου δεν είναι δυναμική,μάλλον αυτό πρέπει να ναι το λάθος.Ο,τι παίρνει καρφωτά τα x,y και δεν μου προσφέρει τίποτα στην ουσία.

[nucleus]

Τα x και y είναι πίνακες int οπότε πρέπει να κάνεις malloc μέσα στην merge_sort για να έχουν το σωστό μέγεθος το οποίο είναι δυναμικό.

Ποιό flag?Αφού κάνεις join δεν χρειάζεται το pthread_exit πριν το return δοκίμασε το.

Σίγουρα η υλοποίηση του merge sort που χρησιμοποιείς δουλεύει σωστά?

[mhche]

Τα x και y είναι πίνακες int οπότε πρέπει να κάνεις malloc μέσα στην merge_sort για να έχουν το σωστό μέγεθος το οποίο είναι δυναμικό.

Ποιό flag?Αφού κάνεις join δεν χρειάζεται το pthread_exit πριν το return δοκίμασε το.

Σίγουρα η υλοποίηση του merge sort που χρησιμοποιείς δουλεύει σωστά?

Μάλλον η τελευταία ερώτηση σου είναι και το λάθος

Εγκατέλειψα την προηγούμενη προσπάθεια,και είμαι σε μια πιο απλή που δουλεύει

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
//#define NUM_THREADS 2
#define size 16384

//pthread_t thread[NUM_THREADS];
//pthread_mutex_t UpdateMutex;

void MERGE (int low,int mid,int high, int* a)
{
    int h,i,j,k;
    int b[size];
    h=low;
    i=low;
    j=mid+1;
    while ((h<=mid)&&(j<=high)){
            if (a[h]<=a[j]){ b[i]=a[h]; h++;}
            else { b[i]=a[j]; j++;}
            i++;}
        if(h>mid)
        { 
            for (k=j;k<=high;k++){ b[i]=a[k]; i=i+1;}        
        }
        else
        {
            for(k=h;k<=mid;k++){ b[i]=a[k]; i++;}
        }
        for(k=low;k<=high;k++) {a[k]=b[k];}
}

void MERGESORT(int low,int high,int* a)
{  
    //pthread_mutex_lock (&UpdateMutex);
    int mid;
    if (low<high)
    {

        mid=(low+high)/2;
        MERGESORT(low,mid,a);
        MERGESORT(mid+1,high,a);
        MERGE(low,mid,high,a);

    }
    //pthread_mutex_unlock(&UpdateMutex);
}

int main ()
{

int i;

int A[16384],B[16384];

for (i=0;i<size;i++){
A[i] = rand() %10000;
B[i] = rand() %10000;     
}

MERGESORT(0,size,A);
MERGESORT(0,size,;

printf("A %i\n",A[1383]);  
printf("B %i\n",B[1633]);
return 0;
}

Το θέμα εδώ είναι, πως δεν ξέρω ακόμα πως να βάλω σωστά τα νήματα.

[nucleus]

Mέσα στην void MERGESORT(int low,int high,int* a)

Θα φτιάχνεις 2 νήματα που το καθένα θα εκτελεί μια αναδρομική κλήση της MERGESORT

Και το ερώτημα που αφήνετε σαν άσκηση στον αναγνώστη είναι.

Πρέπει ή όχι να αλλαχθεί και η θέση της MERGE(low,mid,high,a) και αν ναι που πρέπει να πάει?

[mhche]

Mέσα στην void MERGESORT(int low,int high,int* a)

Θα φτιάχνεις 2 νήματα που το καθένα θα εκτελεί μια αναδρομική κλήση της MERGESORT

Και το ερώτημα που αφήνετε σαν άσκηση στον αναγνώστη είναι.

Πρέπει ή όχι να αλλαχθεί και η θέση της MERGE(low,mid,high,a) και αν ναι που πρέπει να πάει?

Μπορώ να αφήσω πολλά περισσότερα ερωτήματα,απο τόσο κάτι απλό

Λοιπόν,

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#define NUM_THREADS 2
#define size 16384

pthread_t thread[NUM_THREADS];
pthread_mutex_t UpdateMutex;

int A[size],B[size];

void *merge(int low,int mid,int high, int* a)
{
    int h,i,j,k;
    int temp[size];
    h=low;
    i=low;
    j=mid+1;
    while ((h<=mid)&&(j<=high)){
            if (a[h]<=a[j]){ temp[i]=a[h]; h++;}
            else { temp[i]=a[j]; j++;}
            i++;}
        if(h>mid)
        {for (k=j;k<=high;k++){ temp[i]=a[k]; i=i+1;}}
        else
        {for(k=h;k<=mid;k++){temp[i]=a[k]; i++;}}
        for(k=low;k<=high;k++) {a[k]=temp[k];}
}


void *mergesort(int low,int high,int *arg) {
  int i,id,mid;
  id= *(int *) arg;
  for ( i=id * (size/NUM_THREADS); i<(id+1)*(size/NUM_THREADS); i++ ) {
   pthread_mutex_lock(&UpdateMutex);
    if (low<high)
    {
        mid=(low+high)/2;
        mergesort(low,mid,arg);
        mergesort(mid+1,high,arg);
        merge(low,mid,high,arg);

    }
  pthread_mutex_unlock(&UpdateMutex);
  }
  return NULL;
}


void *mymerge(void *arg) {
     int i;
   for (i=0; i<NUM_THREADS; i++)
        pthread_create(&thread[i], NULL, mergesort(0,size,,&arg);

   for (i=0; i<NUM_THREADS; i++)
          pthread_join(thread[i], NULL);
}

int main ()
{
   int i,j;

for (i=0;i<100;i++){ A[i] = rand() %10000; B[i] = rand() %10000;}

pthread_mutex_init (&UpdateMutex, NULL);

pthread_create(&thread[NUM_THREADS], NULL,  mymerge, NULL); 

printf("A1  %i\n", B[0]);

return 0;
}

Έφτιαξα αυτό,όπως φαίνεται όμως εδώ

pthread_create(&thread, NULL, mergesort(0,size,,&arg);

πάει για τον έναν πίνακα

πως θα το κάνω για οποιονδήποτε;

[nucleus]

Θα τον περάσεις σαν όρισμα στην mymerge

[chameleon]

Αφήστε ρε τα PThreads για τέτοιες απλές εργασίες.

Δοκίμασε OpenMP

Είναι εύκολο στο στήσιμο.

Υποστηρίζεται απ' όλους τους σοβαρούς compilers (προφανώς και gcc) και σε περίπτωση που κάποιος δεν το υποστηρίζει απλά τρέχει σαν single threaded.

Πόσο απλός ο κώδικας;

Τόσο:

#omp parallel for
for(int i = 0; i < SIZE; i++) ....

Αυτόματα ο compiler γράφει κώδικα και δημιουργεί τόσα threads όσα είναι και τα core του επεξεργαστή σου.

Super Cool?

Ναι. Και δεν αλλάζεις τίποτα από κώδικα. Απλά προσθέτεις την ντιρεκτίβα #omp parallel for

[chameleon]

Τα πρώτα πολύ απλά παραδείγματα, που όμως σε καλύπτουν 100% σε αυτό που θέλεις να κάνεις, θα τα βρεις στη Wikipedia.

OpenMP - Wikipedia, the free encyclopedia

[mhche]

Αφήστε ρε τα PThreads για τέτοιες απλές εργασίες.

Δοκίμασε OpenMP

Είναι εύκολο στο στήσιμο.

Υποστηρίζεται απ' όλους τους σοβαρούς compilers (προφανώς και gcc) και σε περίπτωση που κάποιος δεν το υποστηρίζει απλά τρέχει σαν single threaded.

Πόσο απλός ο κώδικας;

Τόσο:

#omp parallel for
for(int i = 0; i < SIZE; i++) ....

Αυτόματα ο compiler γράφει κώδικα και δημιουργεί τόσα threads όσα είναι και τα core του επεξεργαστή σου.

Super Cool?

Ναι. Και δεν αλλάζεις τίποτα από κώδικα. Απλά προσθέτεις την ντιρεκτίβα #omp parallel for

Τα πρώτα πολύ απλά παραδείγματα, που όμως σε καλύπτουν 100% σε αυτό που θέλεις να κάνεις, θα τα βρεις στη Wikipedia.

OpenMP - Wikipedia, the free encyclopedia

Σε ευχαριστώ για την απάντηση σου, πραγματικά χρήσιμο.

Απλά αυτός ήταν ο σκοπός της εργασίας που ήθελα να κάνω.