Paralleler Sortieralgorithmus

Question

Ich bin auf der Suche nach einer einfachen Implementierung eines parallelisierten (multi-threaded) Sortieralgorithmus in C#, der auf List<T> oder Arrays arbeiten kann und möglicherweise parallele Erweiterungen verwendet, aber dieser Teil ist nicht unbedingt notwendig.

Edit: Frank Krüger bietet eine gute Antwort, aber ich möchte dieses Beispiel zu einem konvertieren, das nicht LINQ verwendet. Beachten Sie auch, dass Parallel.Do() durch Parallel.Invoke() ersetzt wurde.

Danke.

Answer 1

Von "The Darkside" in seinem Artikel Parallel Extensions to the .Net Framework wir haben diese parallele Erweiterungen Version von quicksort:

(Edit: Da der Link jetzt tot ist, interessierte Leser kann ein Archiv es bei the Wayback Machine finden)

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)); 
     } 
    } 
} 

Beachten Sie, dass er auf eine sequentielle Art kehrt, sobald die Anzahl der Elemente weniger als 2048.

Answer 2

Teilen Sie die Liste, die Sie in gleich große Teillisten sortiert benötigen, je nachdem, wie viele Prozessoren Sie haben, und dann, wenn zwei Teile fertig sind, füge sie zu einem neuen Teil zusammen, bis nur noch einer übrig ist und alle Fäden fertig sind. Ganz einfach, Sie sollten in der Lage sein, es selbst zu implementieren, und das Sortieren der Listen in jedem Thread kann mit jedem vorhandenen Sortieralgorithmus erfolgen (wie in der Bibliothek).

Answer 3

Für den Datensatz hier ist eine Version ohne Lambda-Ausdrücke, die in C# 2 und .Net 2 + Parallel Extensions kompiliert werden. Dies sollte auch mit Mono mit einer eigenen Implementierung von Parallel Extensions (von Google Summer of Code 2008) arbeiten:

/// <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

aktualisiert erreiche ich jetzt besser als 1.7x Speedup auf einer Dual-Core-Maschine.

Ich dachte, ich würde versuchen, einen parallelen Sortierer zu schreiben, der in .NET 2.0 arbeitete (ich denke, überprüfen Sie mich dazu), und das nichts anderes als die ThreadPool verwendet.

Hier sind die Ergebnisse eines 2.000.000 Elementanordnung Sortierung:

 
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 

ich einen 1.76x Speedup bekam - ziemlich nah an der optimalen 2x ich hatte gehofft, dass - in diesem Umfeld:

1. 2.000.000 zufällig Model Objekte
2. Sortieren von Objekten durch einen Vergleichsdelegaten, der zwei DateTime Eigenschaften vergleicht.
3. Mono JIT-Compiler Version 2.4.2.3
4. Max OS X 10.5.8 auf 2,4 GHz Intel Core 2 Duo

Dieses Mal habe ich Ben Watson's QuickSort in C# verwendet.Ich änderte seine QuickSort innere Schleife aus:

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

zu:

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

(. Eigentlich in dem Code, den ich ein wenig zu Load-Balancing, die zu helfen scheinen)

Ich habe Es wurde festgestellt, dass sich die Ausführung dieser parallelen Version nur auszahlt, wenn sich mehr als 25.000 Elemente in einem Array befinden (obwohl ein Minimum von 50.000 den Prozessor wahrscheinlich mehr atmen lässt).

Ich habe so viele Verbesserungen vorgenommen, wie ich an meine kleine Dual-Core-Maschine denken kann. Ich würde gerne einige Ideen auf 8-Wege-Monster ausprobieren. Auch diese Arbeit wurde auf einem kleinen 13 "MacBook mit Mono ausgeführt. Ich bin gespannt, wie andere auf einer normalen .NET 2.0-Installation abschneiden.

Der Quellcode in all seiner hässlichen Pracht ist hier erhältlich: http://www.praeclarum.org/so/psort.cs.txt. Ich kann reinigen sie es, wenn es irgendein Interesse ist.

Answer 5

A Mergesort basierend auf der Größe des Prozessor-Cache, wobei die Blöcke zwischen den Prozessoren in den Sinn kommt unterteilt ist.

die merge Stufe durch Aufspalten des Merge getan werden könnte, in n Bits, wobei jeder Prozessor beginnt, die Blöcke von dem korrekten Versatz in die Blöcke zu mischen

Ich habe nicht versucht, dies zu schreiben.

(Da die relative Geschwindigkeit des CPU-Cache und Haupt ram, nicht das war weit weg von der relativen Geschwindigkeit von RAM und Band als die Zeit, der Mergesort entdeckt, vielleicht sollten wir Sorten mit beginnen wieder fusionieren)