¿Qué algoritmo de ordenación paralela tiene el mejor rendimiento promedio de casos?
La ordenación toma O(n log n) en el caso serie. Si tenemos procesadores O(n) esperaríamos una aceleración lineal. O (log n) existen algoritmos paralelos pero tienen una constante muy alta. Tampoco son aplicables en hardware de productos básicos que no tiene procesadores O(n) cercanos. Con los procesadores p, los algoritmos razonables deben tomar O (n / p log n) tiempo.
En el caso serie, quick sort tiene la mejor complejidad de tiempo de ejecución en promedio. Un algoritmo de clasificación rápida paralelo es fácil de implementar (ver aquí y aquí). Sin embargo, no funciona bien ya que el primer paso es particionar toda la colección en un solo núcleo. He encontrado información sobre muchos algoritmos de clasificación paralela, 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.
4 answers
El siguiente artículo (descarga PDF) es un estudio comparativo de algoritmos de ordenación paralela en varias arquitecturas:
Algoritmos de ordenación paralela en varias arquitecturas
Según el artículo, sample sort parece ser el mejor en muchos tipos de arquitectura paralela.
Actualización para abordar la preocupación de Mark por la edad:
Aquí hay artículos más recientes que introducen algo más novedoso (de 2007, que, por cierto, todavía se comparan con la muestra sort):
Mejoras en la ordenación de muestras
AA-Sort
El borde sangrante (circa 2010, algunos solo un par de meses de edad):
Patrón de clasificación paralelo
Clasificación paralela basada en GPU de muchos núcleos
Clasificación paralela de CPU/GPU híbrida
Algoritmo Aleatorizado de Clasificación Paralela con un Estudio Experimental
Ordenación paralela altamente escalable
Ordenar N-Elementos Usando El Orden Natural: Una Nueva Método de Clasificación
Actualización para 2013:
Aquí está el borde sangrante alrededor de enero de 2013. (Nota: Algunos de los enlaces son a documentos en Citeseer y requieren registro que es gratuito):
Conferencias universitarias:
Particionamiento Paralelo para la Selección y Ordenación
Clase de Algoritmos de Ordenación Paralela
Clase de Algoritmos de Ordenación Paralela 2
Clase de Algoritmos de Ordenación Paralela 3
Otras fuentes y papel:
Un nuevo algoritmo de ordenación para arquitecturas de muchos núcleos basado en la ordenación bitónica adaptativa
Ordenación Paralela Altamente Escalable 2
Fusión Paralela
Fusión Paralela 2
Sistema Paralelo de Auto-Clasificación de Objetos
Comparación del Rendimiento de los Algoritmos de Clasificación Rápida Secuencial y de Clasificación Rápida Paralela
La Memoria compartida, el Paso de Mensajes y las Ordenaciones de Combinación Híbridas para Independiente y en clúster SMPs
Varios algoritmos paralelos (clasificación et al), incluyendo implementaciones
Fuentes y documentos híbridos de GPU y CPU/GPU:
Un Método OpenCL de Algoritmos de Ordenación en Paralelo para la Arquitectura de GPU
Clasificación De Datos Mediante Unidades De Procesamiento De Gráficos
Algoritmos eficientes para Ordenar en GPU
Diseño de algoritmos de clasificación eficientes para muchas GPU CORE
Clasificación Determinista De Muestras Para GPU
Rápido ordenación in situ con CUDA basada en la ordenación bitónica
Rápida clasificación paralela por GPU mediante un algoritmo híbrido
Algoritmos de Ordenación Paralela Rápidos en GPU
Clasificación rápida en CPU y GPU: un caso para la clasificación SIMD olvidadiza de ancho de banda
GPU sample sort
GPU-ABiSort: Ordenación Paralela Óptima en Arquitecturas de Flujo
GPUTeraSort: clasificación de coprocesadores de gráficos de alto rendimiento para bases de datos grandes gestión
Algoritmo de clasificación basado en comparaciones de alto rendimiento en GPU de muchos núcleos
Clasificación externa paralela para GPU habilitadas para CUDA con equilibrio de carga y baja sobrecarga de transferencia
Clasificación en GPU para conjuntos de datos a gran escala: una comparación exhaustiva
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-01-10 21:17:52
He trabajado con un algoritmo Quicksort paralelo y un algoritmo PSRS que esencialmente combina quicksort en paralelo con la fusión.
Con el algoritmo Quicksort Paralelo, he demostrado una aceleración casi lineal con hasta 4 núcleos (doble núcleo con hyper-threading), que se espera dadas las limitaciones del algoritmo. Un Quicksort paralelo puro se basa en un recurso de pila compartido que dará lugar a la contención entre los hilos, reduciendo así cualquier ganancia en el rendimiento. El la ventaja de este algoritmo es que ordena 'in-place', lo que reduce la cantidad de memoria necesaria. Es posible que desee considerar esto al ordenar más de 100M elementos como usted ha indicado.
Veo que está buscando ordenar en un sistema con 8-32 núcleos. El algoritmo PSRS evita la contención en el recurso compartido, lo que permite acelerar un mayor número de procesos. He demostrado el algoritmo con hasta 4 núcleos como anteriormente, pero los resultados experimentales de otros reportan una aceleración lineal cercana con mucho mayores números de core, 32 y más allá. La desventaja del algoritmo PSRS es que no está en su lugar y requerirá considerablemente más memoria.
Si está interesado, puede usar o examinar mi código Java para cada uno de estos algoritmos. Puedes encontrarlo en github: https://github.com/broadbear/sort. El código está pensado como un reemplazo directo de las colecciones Java.tipo(). Si usted está buscando la capacidad de realizar la ordenación paralela en una JVM como se indica anteriormente, el código en mi recuperación puede ayudarte. La API está completamente genérica para elementos que implementan Comparables o implementan su propio Comparador.
¿Puedo preguntar para qué está buscando ordenar tantos elementos? Estoy interesado en saber de posibles aplicaciones para mi paquete de clasificación.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-11-24 04:47:31
Echa un vistazo a este documento: Un Algoritmo de Ordenación Paralela Escalable Que Utiliza la División Exacta. Se refiere a muchos más de 32 núcleos. Sin embargo, describe en detalle un algoritmo, que tiene una complejidad de tiempo de ejecución de O(n/p * log(n) + p * log(n)**2) y es aplicable para comparadores arbitrarios.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-11-20 06:55:38
El documento " Comparación de Algoritmos de Ordenación Paralelos en Diferentes Arquitecturas" puede ser un buen lugar para empezar.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2010-10-19 15:12:39