OpenMP: clasificación rápida paralela

5 minutos de lectura

avatar de usuario
al azar

Intento usar OpenMP para paralelizar QuickSort en la parte de partición y en la parte QuickSort. Mi código C es el siguiente:

#include "stdlib.h"
#include "stdio.h"
#include "omp.h"

// parallel partition
int ParPartition(int *a, int p, int r) {
    int b[r-p];
    int key = *(a+r); // use the last element in the array as the pivot
    int lt[r-p]; // mark 1 at the position where its element is smaller than the key, else 0
    int gt[r-p]; // mark 1 at the position where its element is bigger than the key, else 0
    int cnt_lt = 0; // count 1 in the lt array
    int cnt_gt = 0; // count 1 in the gt array
    int j=p;
    int k = 0; // the position of the pivot
    // deal with gt and lt array
    #pragma omp parallel for
    for ( j=p; j<r; ++j) {
        b[j-p] = *(a+j);
        if (*(a+j) < key) {
            lt[j-p] = 1;
            gt[j-p] = 0;
        } else {
            lt[j-p] = 0;
            gt[j-p] = 1;
        }
    }
    // calculate the new position of the elements
    for ( j=0; j<(r-p); ++j) {
        if (lt[j]) {
            ++cnt_lt;
            lt[j] = cnt_lt;
        } else
            lt[j] = cnt_lt;
        if (gt[j]) {
            ++cnt_gt;
            gt[j] = cnt_gt;
        } else
            gt[j] = cnt_gt;
    }
    // move the pivot
    k = lt[r-p-1];
    *(a+p+k) = key;
    // move elements to their new positon
    #pragma omp parallel for 
    for ( j=p; j<r; ++j) {
        if (b[j-p] < key)
            *(a+p+lt[j-p]-1) = b[j-p];
        else if (b[j-p] > key)
            *(a+k+gt[j-p]) = b[j-p];
    }
    return (k+p);
}

void ParQuickSort(int *a, int p, int r) {
    int q;
    if (p<r) {
        q = ParPartition(a, p, r);
        #pragma omp parallel sections
        {
        #pragma omp section
        ParQuickSort(a, p, q-1);
        #pragma omp section
        ParQuickSort(a, q+1, r);
        }
    }
}

int main() {
    int a[10] = {5, 3, 8, 4, 0, 9, 2, 1, 7, 6};
    ParQuickSort(a, 0, 9);
    int i=0;
    for (; i!=10; ++i)
        printf("%d\t", a[i]);
    printf("\n");
    return 0;
}

Para el ejemplo de la función principal, el resultado de la ordenación es:

0   9   9   2   2   2   6   7   7   7

Usé gdb para depurar. En la recursividad temprana, todo salió bien. Pero en algunas recursiones, de repente se estropeó para comenzar a duplicar elementos. Luego genera el resultado anterior.

Alguien me puede ayudar a saber donde esta el problema?

Implementé Quicksort paralelo en un entorno de producción, aunque con procesos concurrentes (es decir, fork() y join()) y no OpenMP. También encontré una solución pthread bastante buena, pero una solución de proceso concurrente fue la mejor en términos del tiempo de ejecución en el peor de los casos. Permítanme comenzar diciendo que no parece que esté haciendo copias de su matriz de entrada para cada subproceso, por lo que definitivamente encontrará condiciones de carrera que pueden dañar sus datos.

Esencialmente, lo que está sucediendo es que ha creado una matriz norte en la memoria compartida, y cuando haces una #pragma omp parallel sectionsestá generando tantos subprocesos de trabajo como hay #pragma omp section‘s. Cada vez que un subproceso de trabajo intenta acceder y modificar elementos de a, ejecutará una serie de instrucciones: “lee el valor n de norte de la dirección dada”, “modificar el valor n de norte“,” escribe el valor n de norte volver a la dirección dada”. Dado que tiene varios subprocesos sin bloqueo ni sincronización, las instrucciones de lectura, modificación y escritura pueden ejecutarse en cualquier orden mediante varios procesadores, por lo que los subprocesos pueden sobrescribir las modificaciones de los demás o leer un archivo no actualizado. valor.

La mejor solución que encontré (después de muchas semanas de probar y comparar muchas soluciones que se me ocurrieron) es subdividir la lista registro (n) tiempos, donde norte es el número de procesadores. Por ejemplo, si tiene una máquina de cuatro núcleos (n = 4), subdivida la lista 2 veces (log (4) = 2) eligiendo pivotes que son las medianas del conjunto de datos. Es importante que los pivotes sean medianas, porque de lo contrario puede terminar con un caso en el que un pivote mal elegido haga que las listas se distribuyan de manera desigual entre los procesos. Luego, cada proceso realiza una clasificación rápida en su subarreglo local y luego combina sus resultados con los resultados de otros procesos. Esto se llama “hyperquicksort”, y de una búsqueda inicial en github, encontré este. No puedo responder por el código allí y no puedo publicar nada del código que escribí ya que está protegido bajo un NDA.

Por cierto, uno de los mejores algoritmos de clasificación en paralelo es PSRS (Parallel Sorting by Regular Sampling), que mantiene los tamaños de lista más equilibrados entre los procesos, no comunica innecesariamente claves entre procesos y puede funcionar en un número arbitrario de procesos concurrentes ( no necesariamente tienen que ser una potencia de 2).

  • Esto parece estar mal. El algoritmo divide la matriz que se ordenará en una lista parcial más pequeña de la lista inicial. Siempre que los subprocesos generados simplemente intercambien objetos dentro de su lista parcial “propia”, no pueden surgir condiciones de carrera.

    – Quxflux

    28/10/2014 a las 12:20

  • ¡Gracias! ¿Supongo que es por la matriz b?

    – al azar

    16 de abril de 2013 a las 2:25

  • @randomp, solo puedo decir ‘tal vez’. 🙂

    – MYMNeo

    16 de abril de 2013 a las 2:36

  • No veo ninguna razón por la que esto funcione. En el parallel for, lt_n y gt_n son posiblemente modificados por más de un subproceso sin ninguna sincronización. Tal vez la matriz es tan pequeña que solo un subproceso está trabajando en esa sección.

    – pescado

    3 de febrero de 2015 a las 17:38

  • Actualizar: Ejecuté esto varias veces y, de hecho, vi un resultado incorrecto: 0 1 2 3 5 6 6 7 8 9. Por lo tanto el código es equivocado. @aleatorio

    – pescado

    03/02/2015 a las 17:41


  • @ftfish sí, este código parece incorrecto, publiqué una solución si desea verificar

    – choque de sueños

    21 de marzo de 2021 a las 8:34

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad