quicksort parallelo in c

Question

Dopo un sacco di ricerca di un'implementazione di quicksort in parallelo in c, sto per immergermi e codificarlo da solo. (Ho bisogno di ordinare una matrice di circa 1 milione di stringhe di testo.) Sembra che tutte le implementazioni che ho trovato dividano il lavoro all'interno della funzione qsort stessa, il che crea un'enorme quantità di sovraccarico nel partizionamento della quantità relativamente piccola di lavoro per thread .

Non sarebbe molto più veloce dividere il milione di stringhe per il numero di thread (nel mio caso, 24 thread) e farli lavorare su una sezione, quindi eseguire un mergesort? Certo, questo ha lo svantaggio teorico che non è un ordinamento sul posto, ma con le gocce di memoria disponibili non è un problema. La macchina su cui gira ha 12 (molto veloci) core fisici/24 logici e 192 GB (sì, gigabyte) di memoria. Attualmente, anche su questa macchina, l'ordinamento richiede quasi 8 minuti!

Answer 1

Non sarebbe molto più veloce per dividere 1 milione di corde per il numero di fili (nel mio caso, 24 thread), e li hanno ogni opera su una sezione, e poi fare un Mergesort ?

È una buona idea.

Ma è possibile effettuare alcune osservazioni scrivendo programmi giocattolo per quick-sort e merge-sort e sfruttare i loro comportamenti algoritmici/di esecuzione.

Ad esempio. quick-sort ordinamenti mentre il processo dividing (pivot elemento verrà inserito nella sua posizione finale al termine di tale iterazione) e merge-sort ordinamenti mentre merging (l'ordinamento viene eseguito dopo che l'intero working set è suddiviso in unità molto granulari dove può essere direttamente confrontato con altri granulari-unità (== o strcmp()).

Mescolando algoritmi basati sulla natura del set di lavoro è una buona idea.

quanto riguarda l'ordinamento parallelo, ecco la mia parallel merge-sort per iniziare.

#include <stdio.h> 
#include <pthread.h> 
#include <stdlib.h> 

#define NOTHREADS 2 

/* 

gcc -ggdb -lpthread parallel-mergesort.c 


NOTE: 
The mergesort boils downs to this.. 
Given two sorted array's how do we merge this? 

We need a new array to hold the result of merging 
otherwise it is not possible to do it using array, 
so we may need a linked list 

*/ 

int a[] = {10, 8, 5, 2, 3, 6, 7, 1, 4, 9}; 

typedef struct node { 
int i; 
int j; 
} NODE; 

void merge(int i, int j) 
{ 
     int mid = (i+j)/2; 
     int ai = i; 
     int bi = mid+1; 

     int newa[j-i+1], newai = 0; 

     while(ai <= mid && bi <= j) { 
       if (a[ai] > a[bi]) 
         newa[newai++] = a[bi++]; 
       else      
         newa[newai++] = a[ai++]; 
     } 

     while(ai <= mid) { 
       newa[newai++] = a[ai++]; 
     } 

     while(bi <= j) { 
       newa[newai++] = a[bi++]; 
     } 

     for (ai = 0; ai < (j-i+1) ; ai++) 
       a[i+ai] = newa[ai]; 

} 

void * mergesort(void *a) 
{ 
       NODE *p = (NODE *)a; 
       NODE n1, n2; 
       int mid = (p->i+p->j)/2; 
       pthread_t tid1, tid2; 
       int ret; 

       n1.i = p->i; 
       n1.j = mid; 

       n2.i = mid+1; 
       n2.j = p->j; 

       if (p->i >= p->j) return; 

       ret = pthread_create(&tid1, NULL, mergesort, &n1); 
       if (ret) { 
         printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, ret);  
         exit(1); 
       } 


       ret = pthread_create(&tid2, NULL, mergesort, &n2); 
       if (ret) { 
         printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, ret);  
         exit(1); 
       } 

       pthread_join(tid1, NULL); 
       pthread_join(tid2, NULL); 

       merge(p->i, p->j); 
       pthread_exit(NULL); 
} 


int main() 
{ 
       int i; 
       NODE m; 
       m.i = 0; 
       m.j = 9; 
       pthread_t tid; 

       int ret; 

       ret=pthread_create(&tid, NULL, mergesort, &m); 
       if (ret) { 
         printf("%d %s - unable to create thread - ret - %d\n", __LINE__, __FUNCTION__, ret);  
         exit(1); 
       } 

       pthread_join(tid, NULL); 

       for (i = 0; i < 10; i++) 
           printf ("%d ", a[i]); 

       printf ("\n"); 

       // pthread_exit(NULL); 
       return 0; 
} 

Buona fortuna!

Answer 2

Quicksort comporta un passaggio iniziale su un elenco, che ordina l'elenco in sezioni più alte e più basse del pivot.

Perché non farlo in un thread e quindi generare un altro thread e delegarlo a metà mentre il thread extant prende l'altra metà e così via e così via?

Answer 3

Hai considerato l'utilizzo di un algoritmo di ordinamento progettato specificamente per ordinare le stringhe? Sembra che potrebbe essere un'idea migliore del tentativo di implementare un quicksort personalizzato. La scelta specifica degli algoritmi dipende probabilmente dalla lunghezza delle stringhe e da quanto siano diverse, ma una radix sort probabilmente non è una scommessa sbagliata.

Un rapido google search ha rilevato an article sull'ordinamento di stringhe. Non l'ho letto ma Sedgewick e Bentley conoscono davvero le loro cose. Secondo l'abstract, il loro algoritmo è un amalgama di Quicksort e radix sort.

Un'altra possibile soluzione consiste nel racchiudere un algoritmo di ordinamento parallelo da C++.L'implementazione STL di GNU ha uno parallel mode, che contiene un'implementazione parallela di Quicksort. Questa è probabilmente la soluzione più semplice.

Answer 4

Per rendere fattibile l'accesso rapido alla memoria multi-thread, è necessario ottimizzare la maggior parte del lavoro di ordinamento all'interno delle cache non condivise (L1 & L2). La mia scommessa è che il quicksort a thread singolo sarà più veloce del thread muli a meno che non siate disposti a impiegare un sacco di lavoro.

Un approccio al test potrebbe essere un thread per ordinare la metà superiore e un altro per ordinare il più basso.

Per quanto riguarda una speciale procedura di ordinamento adattata alle stringhe, il concetto mi sembra strano. Voglio dire, non ci sono molti casi in cui l'ordinamento di un vettore di sole stringhe (o interi) è particolarmente utile. Di solito i dati saranno organizzati in una tabella con colonne e righe e dovrai ordinare le righe di una colonna contenente lettere e, se sono uguali, ordinerai usando una colonna aggiuntiva contenente un timestamp o una classifica o qualcos'altro. Quindi la routine di ordinamento dovrebbe essere in grado di gestire un set di regole di ordinamento multilivello in grado di specificare qualsiasi tipo di dati (booleano, intero, date, stringhe, virgola mobile ecc.) In qualsiasi direzione (crescente o decrescente) presente nelle colonne della tabella.