algorithm sorting concurrency

algorithm - ¿Qué algoritmo de clasificación en paralelo tiene el mejor rendimiento promedio de casos?



sorting concurrency (4)

La ordenación toma O (n log n) en el caso de serie. Si tenemos procesadores O (n), esperaríamos una aceleración lineal. Existen algoritmos paralelos O (log n) pero tienen una constante muy alta. Tampoco son aplicables en hardware básico que no tiene en ningún lugar cerca de procesadores O (n). Con los procesadores p, los algoritmos razonables deberían tomar el tiempo O (n / p log n).

En el caso de serie, la clasificación rápida tiene la mejor complejidad de tiempo de ejecución en promedio. Un algoritmo de ordenación rápida paralelo es fácil de implementar (ver here y here ). Sin embargo, no funciona bien ya que el primer paso es dividir toda la colección en un solo núcleo. He encontrado información sobre muchos algoritmos de ordenamiento en paralelo, pero hasta ahora no he visto nada que apunte a un ganador claro.

Estoy buscando ordenar listas de 1 millón a 100 millones de elementos en un lenguaje JVM que se ejecuta en 8 a 32 núcleos.

El siguiente artículo (descarga PDF) es un estudio comparativo de algoritmos de clasificación paralelos en varias arquitecturas:

Algoritmos de clasificación paralelos en varias arquitecturas

De acuerdo con el artículo, el tipo de muestra parece ser el mejor en muchos tipos de arquitectura paralelos.

Actualización para abordar la preocupación de edad de Mark:

Aquí hay artículos más recientes que presentan algo más novedoso (de 2007, que, por cierto, todavía se compara con el género de muestra):

Mejoras en el tipo de muestra
AA-Sort

El borde sangrante (alrededor de 2010, algunos solo un par de meses):

Patrón de clasificación paralelo
Clasificación paralela basada en GPU de muchos núcleos
Tipo paralelo híbrido CPU / GPU
Algoritmo de clasificación paralela aleatorizado con un estudio experimental
Clasificación paralela altamente escalable
Clasificación de elementos N utilizando orden natural: un nuevo enfoque de ordenación adaptable

Actualización para 2013: Aquí está el borde de sangrado alrededor de enero de 2013. (Nota: Algunos de los enlaces son para documentos en Citeseer y requieren registro que es gratuito):

Conferencias universitarias:
Partición en paralelo para selección y clasificación
Parallel Sorting Algorithms Lecture
Parallel Sorting Algorithms Conferencia 2
Parallel Sorting Algorithms Conferencia 3

Otras fuentes y documentos:
Un algoritmo de clasificación novedoso para arquitecturas de muchos núcleos basadas en el género bitónico adaptativo
Clasificación paralela altamente escalable 2
Fusión paralela
Paralelo fusionando 2
Sistema paralelo de auto-clasificación para objetos
Comparación de rendimiento de ordenación rápida secuencial y algoritmos de ordenación rápida paralelos
Memoria compartida, paso de mensajes y clases de fusión híbrida para SMP autónomos y en clúster
Varios algoritmos paralelos (clasificación et al) incluyendo implementaciones

Fuentes y documentos híbridos GPU y CPU / GPU:
Un método OpenCL de algoritmos de clasificación paralelos para la arquitectura de GPU
Clasificación de datos usando unidades de procesamiento de gráficos
Algoritmos eficientes para clasificar en GPU
Diseño de algoritmos de clasificación eficientes para GPU de muchos núcleos
Muestra determinista Ordenar por GPU
Clasificación rápida in situ con CUDA basada en el género bitónico
Clasificación GPU paralela rápida usando un algoritmo híbrido
Algoritmos rápidos de ordenamiento paralelo en GPU
Clasificación rápida en CPU y GPU: un caso para el ancho de banda ajeno SIMD
Tipo de muestra GPU
GPU-ABiSort: Clasificación paralela óptima en arquitecturas Stream
GPUTeraSort: ordenación de coprocesador de gráficos de alto rendimiento para una gran gestión de bases de datos
Algoritmo de clasificación basado en comparación de alto rendimiento en GPU de muchos núcleos
Clasificación externa paralela para GPU habilitadas para CUDA con balanceo de carga y baja sobrecarga de transferencia
Clasificación en GPU para conjuntos de datos a gran escala: una comparación exhaustiva

He trabajado tanto con un algoritmo paralelo de Quicksort como con un algoritmo PSRS que combina esencialmente quicksort en paralelo con la fusión.

Con el algoritmo Parallel Quicksort, he demostrado una aceleración casi lineal con hasta 4 núcleos (doble núcleo con hiper-threading), lo que se espera dadas las limitaciones del algoritmo. Un Parallel Quicksort puro se basa en un recurso de pila compartida que dará lugar a una disputa entre hilos, reduciendo así cualquier ganancia en el rendimiento. La ventaja de este algoritmo es que ordena ''in situ'', lo que reduce la cantidad de memoria necesaria. Es posible que desee considerar esto al ordenar más de 100M de elementos como indicó.

Veo que busca ordenar en un sistema con 8-32 núcleos. El algoritmo PSRS evita la contención en el recurso compartido, lo que permite una aceleración en un mayor número de procesos. He demostrado el algoritmo con hasta 4 núcleos como el anterior, pero los resultados experimentales de otros informan una aceleración casi lineal con números mucho mayores de núcleo, 32 y más. La desventaja del algoritmo PSRS es que no está en su lugar y requerirá mucha más memoria.

Si está interesado, puede usar o leer mi código Java para cada uno de estos algoritmos. Puede encontrarlo en github: https://github.com/broadbear/sort . El código pretende ser un reemplazo directo de Java Collections.sort (). Si está buscando la posibilidad de realizar una ordenación en paralelo en una JVM como indica más arriba, el código de mi repositorio puede serle útil. La API está completamente genérica para elementos que implementan Comparable o implementan su propio Comparador.

¿Puedo preguntar para qué busca ordenar tantos elementos? Me interesa saber sobre posibles aplicaciones para mi paquete de clasificación.