Algoritmo de ordenación paralela

Question

Estoy buscando una implementación simple de un algoritmo de ordenamiento paralelo (de múltiples subprocesos) en C# que pueda operar en List<T> o Arrays, y posiblemente utilizando extensiones paralelas, pero esa parte no es estrictamente necesaria.

Editar: Frank Krueger ofrece una buena respuesta; sin embargo, deseo convertir ese ejemplo en uno que no utilice LINQ. También tenga en cuenta que Parallel.Do() parece haber sido reemplazado por Parallel.Invoke().

Gracias.

Answer 1

De "El lado oscuro" en su artículo Parallel Extensions to the .Net Framework tenemos esta versión extensiones paralelo de ordenación rápida:

(Edit: Ya que el enlace está ahora muerto, los lectores interesados ​​pueden encontrar un archivo de la misma en the Wayback Machine)

private 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 void QuicksortParallelOptimised<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.Do(
       () => QuicksortParallelOptimised(arr, left, pivot - 1), 
       () => QuicksortParallelOptimised(arr, pivot + 1, right)); 
     } 
    } 
} 

Aviso que vuelve a una ordenación secuencial una vez que el número de elementos es inferior a 2048.

Answer 2

Divide la lista que necesita ordenados en sublistas de igual tamaño, dependiendo del número de procesadores que tiene, y luego, cada vez que dos partes estén hechas, unirlas a una nueva parte, hasta que quede solo una y todos los hilos terminados. Muy simple, debería poder implementarlo usted mismo, y ordenar las listas dentro de cada hilo se puede hacer usando cualquier algoritmo de ordenamiento existente (como en la biblioteca).

Answer 3

Para el registro aquí hay una versión sin expresiones lamda que se compilará en C# 2 y .Net 2 + Parallel Extensions. Esto también se debe trabajar 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 
} 

Answer 4

actualización ahora lograr una mejor aceleración de 1,7 veces en una máquina de doble núcleo.

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

Éstos son los resultados de la clasificación de un conjunto de elemento de 2.000.000:

 
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 

Tengo una aceleración 1.76x - muy cerca de la óptima 2x que esperaba - en este entorno:

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

Esta vez utilicé Ben Watson's QuickSort in C#.He cambiado 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 no parece ayudar)

tengo descubrí 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 permitir que mi procesador respire más).

He hecho tantas mejoras como puedo pensar en mi pequeña máquina de doble núcleo. Me encantaría probar algunas ideas sobre el monstruo de 8 vías. Además, este trabajo se realizó en una pequeña MacBook de 13 "que ejecutaba Mono. Tengo curiosidad por cómo les va a otros en una instalación .NET 2.0 normal.

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

Answer 5

una combinación de tipo basado en el tamaño de la caché del procesador, con los bloques se dividen entre los procesadores viene a la mente.

la etapa de combinación se podría hacer mediante la división de la fusión en n bits con cada procesador comenzando a fusionar los bloques del desplazamiento correcto en los bloques.

No he intentado escribir esto.

(A medida que la velocidad relativa de caché de la CPU y la memoria RAM principal, no está tan lejos de la velocidad relativa de la memoria RAM y la cinta como el tiempo de la clase de combinación fue descubierto, tal vez deberíamos empezar a utilizar combinar las clases de nuevo)