Algoritmo de Ordenación Paralela

Actualización Ahora logro una aceleración mejor que 1.7 x en una máquina de doble núcleo.

Pensé que intentaría escribir un clasificador paralelo que funcionara en.NET 2.0 (creo, compruébame esto) y que no use nada más que el ThreadPool.

Aquí están los resultados de ordenar un array de 2.000.000 de elementos:

Time Parallel    Time Sequential
-------------    ---------------
2854 ms          5052 ms
2846 ms          4947 ms
2794 ms          4940 ms
...              ...
2815 ms          4894 ms
2981 ms          4991 ms
2832 ms          5053 ms

Avg: 2818 ms     Avg: 4969 ms
Std: 66 ms       Std: 65 ms
Spd: 1.76x

Obtuve un aumento de velocidad de 1.76 x-bastante cerca del 2x óptimo que esperaba - en este entorno:

1. 2,000,000 random Model objetos
2. Ordenar objetos por un delegado de comparación que compara dos propiedades DateTime.
3. Compilador Mono JIT versión 2.4.2.3
4. Max OS X 10.5.8 en 2.4 GHz Intel Core 2 Duo

Esta vez usé el QuickSort de Ben Watson en C#. Cambié su QuickSort bucle interno de:

QuickSortSequential:
    QuickSortSequential (beg, l - 1);
    QuickSortSequential (l + 1, end);

A:

QuickSortParallel:
    ManualResetEvent fin2 = new ManualResetEvent (false);
    ThreadPool.QueueUserWorkItem (delegate {
        QuickSortParallel (l + 1, end);
        fin2.Set ();
    });
    QuickSortParallel (beg, l - 1);
    fin2.WaitOne (1000000);
    fin2.Close ();

(En realidad, en el código hago un poco de equilibrio de carga que parece ayudar.)

He encontrado que ejecutar esta versión paralela solo vale la pena cuando hay más de 25,000 elementos en una matriz (aunque, un mínimo de 50,000 parece dejar que mi procesador respire más).

He hecho tantas mejoras como se me ocurre en mi pequeña máquina de doble núcleo. Me encantaría probar algunas ideas en 8-way monster. Además, este trabajo se realizó en un pequeño MacBook de 13" con Mono. Tengo curiosidad por saber cómo les va a otros en una instalación normal de. NET 2.0.

El código fuente en toda su fea gloria está disponible aquí: http://www.praeclarum.org/so/psort.cs.txt. Puedo limpiarlo si hay algún interés.

Para el registro aquí hay una versión sin expresiones lamda que se compilará en Extensiones paralelas C#2 y.Net 2+. Esto también debería funcionar con Mono con su propia implementación de Extensiones Paralelas (de Google Summer of code 2008):

/// <summary>
/// Parallel quicksort algorithm.
/// </summary>
public class ParallelSort
{
    #region Public Static Methods

    /// <summary>
    /// Sequential quicksort.
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr"></param>
    public static void QuicksortSequential<T>(T [] arr) where T : IComparable<T>
    {
        QuicksortSequential(arr, 0, arr.Length - 1);
    }

    /// <summary>
    /// Parallel quicksort
    /// </summary>
    /// <typeparam name="T"></typeparam>
    /// <param name="arr"></param>
    public static void QuicksortParallel<T>(T[] arr) where T : IComparable<T>
    {
        QuicksortParallel(arr, 0, arr.Length - 1);
    }

    #endregion

    #region Private Static Methods

    private static void QuicksortSequential<T>(T[] arr, int left, int right) 
        where T : IComparable<T>
    {
        if (right > left)
        {
            int pivot = Partition(arr, left, right);
            QuicksortSequential(arr, left, pivot - 1);
            QuicksortSequential(arr, pivot + 1, right);
        }
    }

    private static void QuicksortParallel<T>(T[] arr, int left, int right) 
        where T : IComparable<T>
    {
        const int SEQUENTIAL_THRESHOLD = 2048;
        if (right > left)
        {
            if (right - left < SEQUENTIAL_THRESHOLD)
            {
                QuicksortSequential(arr, left, right);
            }
            else
            {
                int pivot = Partition(arr, left, right);
                Parallel.Invoke(new Action[] { delegate {QuicksortParallel(arr, left, pivot - 1);},
                                               delegate {QuicksortParallel(arr, pivot + 1, right);}
                });
            }
        }
    }

    private static void Swap<T>(T[] arr, int i, int j)
    {
        T tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private static int Partition<T>(T[] arr, int low, int high) 
        where T : IComparable<T>
    {
        // Simple partitioning implementation
        int pivotPos = (high + low) / 2;
        T pivot = arr[pivotPos];
        Swap(arr, low, pivotPos);

        int left = low;
        for (int i = low + 1; i <= high; i++)
        {
            if (arr[i].CompareTo(pivot) < 0)
            {
                left++;
                Swap(arr, i, left);
            }
        }

        Swap(arr, low, left);
        return left;
    }

    #endregion
}

Me viene a la mente una ordenación merge basada en el tamaño de la caché del procesador, con los bloques divididos entre los procesadores.

La etapa de fusión podría hacerse dividiendo la fusión en n bits con cada procesador comenzando a fusionar los bloques desde el desplazamiento correcto en los bloques.

No he intentado escribir esto.

(Como la velocidad relativa de la caché de la CPU y la ram principal, no está tan lejos de la velocidad relativa de la RAM y la cinta como el momento en que se descubrió la ordenación de fusión, tal vez deberíamos empezar a usar merge sorts de nuevo)

Divida la lista que necesita ordenarse en sublistas de igual tamaño, dependiendo de cuántos procesadores tenga, y luego cuando se hagan dos partes, combínelas en una nueva parte, hasta que solo quede una y se completen todos los subprocesos. Muy simple debería ser capaz de implementarlo usted mismo, y la ordenación de las listas dentro de cada hilo se puede hacer utilizando cualquier algoritmo de ordenación existente (como en la biblioteca).