parallelsort paralelo en c

Question

Después de buscar mucho una implementación de quicksort paralelo en c, estoy a punto de sumergirme y codificarlo yo mismo. (Necesito ordenar una matriz de alrededor de 1 millón de cadenas de texto.) Parece que todas las implementaciones que he encontrado dividen el trabajo dentro de la función qsort, lo que crea una gran cantidad de sobrecarga en la partición de la cantidad relativamente pequeña de trabajo por hilo .

¿No sería mucho más rápido dividir el 1 millón de cadenas por el número de subprocesos (en mi caso, 24 subprocesos) y hacer que cada uno trabaje en una sección y luego hacer un mergesort? Por supuesto, esto tiene la desventaja teórica de que no es una ordenación en el lugar, pero con montones de memoria disponibles no es un problema. La máquina en la que se ejecuta tiene 12 (muy rápido) físico/24 núcleos lógicos y 192 GB (sí, gigabytes) de memoria. Actualmente, incluso en esta máquina, el género demora casi 8 minutos.

Answer 1

¿No sería mucho más rápido para dividir 1 millón de cuerdas por el número de hilos (en mi caso, 24 hilos), y ellos tienen cada obra en una sección, y luego hacer un mergesort ?

Es una buena idea.

Pero puede hacer algunas observaciones escribiendo programas de juguete para quick-sort y merge-sort y aproveche su comportamiento algorítmico/de ejecución.

Por ejemplo. quick-sort ordena mientras que dividing proceso (pivot elemento se pondrá en su lugar final al final de esa iteración) y merge-sort ordena mientras merging (clasificación se hace después de que todo el conjunto de trabajo se divide (dividido) en unidades muy granulares donde se pueden comparar directamente con otros granulares-unidades (== o strcmp()).

la confusión de algoritmos basados ​​en la naturaleza del conjunto de trabajo es una buena idea.

con respecto a la clasificación paralela, aquí está mi parallel merge-sort para que pueda comenzar.

#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; 
} 

¡Buena suerte!

Answer 2

Quicksort implica un pase inicial sobre una lista, que clasifica la lista en secciones que son más altas y más bajas que el pivote.

¿Por qué no hacer eso en un hilo, y luego engendrar otro hilo y delegarlo a la mitad mientras que el hilo existente toma la otra mitad, y así sucesivamente?

Answer 3

¿Ha considerado utilizar un algoritmo de clasificación diseñado específicamente para ordenar cadenas? Parece que podría ser una mejor idea que tratar de implementar una oferta rápida personalizada. La elección específica de los algoritmos probablemente depende de la longitud de las cadenas y cuán diferentes son, pero probablemente radix sort no sea una mala apuesta.

Un rápido google search apareció an article sobre la clasificación de cadenas. No lo he leído, pero Sedgewick y Bentley realmente saben lo que hacen. De acuerdo con el resumen, su algoritmo es una amalgama de clasificación Quicksort y radix.

Otra posible solución es envolver un algoritmo de clasificación paralelo de C++.La implementación de STL de GNU tiene un parallel mode, que contiene una implementación paralela de quicksort. Esta es probablemente la solución más fácil.

Answer 4

Para hacer que el acceso rápido a múltiples hilos sea posible, los accesos de memoria deben optimizarse de forma que la mayor parte del trabajo de clasificación se realice dentro de los cachés no compartidos (L1 & L2). Mi apuesta es que el quicksort de una sola hebra será más rápido que el de la hebra a menos que esté preparado para realizar una gran cantidad de trabajo.

Un enfoque para probar podría ser un hilo para ordenar la mitad superior y otro para clasificar el inferior.

En cuanto a una rutina de clasificación especial adaptada a cuerdas, el concepto me suena extraño. Quiero decir que no hay muchos casos en los que sea especialmente útil clasificar un vector de solo cadenas (o enteros). Por lo general, los datos se organizarán en una tabla con columnas y filas, y usted querrá ordenar las filas por una columna que contenga letras, y, si son iguales, clasificará utilizando una columna adicional que contenga una marca de tiempo o una clasificación o algo mas. Por lo tanto, la rutina de ordenamiento debe poder manejar un conjunto de reglas de clasificación de varios niveles que pueda especificar cualquier tipo de datos (booleanos, enteros, fechas, cadenas, punto flotante, etc.) en cualquier dirección (ascendente o descendente) presente en las columnas de la tabla.