Równoległy algorytm sortowania

Question

Poszukuję prostej implementacji algorytmu sortowania równoległego (wielowątkowego) w języku C#, który może działać na List<T> lub tablicach i prawdopodobnie przy użyciu rozszerzeń równoległych, ale ta część nie jest bezwzględnie konieczna.

Edytuj: Frank Krueger zapewnia dobrą odpowiedź, jednak chcę przekonwertować ten przykład na taki, który nie używa LINQ. Zauważ też, że Parallel.Do() został zastąpiony przez Parallel.Invoke().

Dzięki.

Answer 1

od „Darkside” w swoim artykule Parallel Extensions to the .Net Framework mamy ten równoległy Rozszerzenia wersji quicksort:

(Edit: Ponieważ link jest teraz martwy, zainteresowani czytelnicy mogą znaleźć archiwum nim w 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)); 
     } 
    } 
} 

Zauważ, że on wraca do sekwencyjnego rodzaju, gdy liczba elementów jest mniejsza niż 2048.

Answer 2

Divide lista trzeba podzielić na równych rozmiarach podlist, w zależności od tego, ile procesorów masz, i następnie za każdym razem, gdy są wykonywane dwie części, łącz je ze sobą do nowej części, aż pozostanie tylko jeden i wszystkie wątki zostaną ukończone. Bardzo proste, możesz samemu go zaimplementować, a sortowanie list w każdym wątku można wykonać przy użyciu dowolnego istniejącego algorytmu sortowania (takiego jak w bibliotece).

Answer 3

Tutaj zapis jest wersją bez wyrażeń lamda, która będzie kompilowana w C# 2 i .Net 2 + Parallel Extensions. Powinno to również pracować z mono z własnej realizacji Parallel Extensions (z 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

Aktualizacja teraz osiągnąć lepsze niż 1,7x SpeedUp na podwójnej maszynie rdzenia.

Pomyślałem, że spróbuję napisać równoległy sorter, który działał w .NET 2.0 (myślę, sprawdź mnie na tym) i że nie używa niczego innego niż ThreadPool.

Oto wyniki sortowania tablicy 2000000 element:

 
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 

mam przyspieszenie 1.76x - dość bliskie optymalnemu 2x miałem nadzieję - w tym środowisku:

1. 2 000 000 losowych obiektów
2. Sortowanie obiektów przez delegata porównania, który porównuje dwie właściwości: DateTime.
3. kompilator JIT Mono wersja 2.4.2.3
4. Max OS X 10.5.8 na 2,4 GHz Intel Core 2 Duo

Tym razem użyłem Ben Watson's QuickSort in C#.I zmienił QuickSort wewnętrzną pętlę od:

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

do:

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

(. Właściwie w kodzie zrobić trochę równoważenie obciążenia, które nie wydają się pomóc)

mam Okazało się, że uruchomienie tej równoległej wersji opłaca się tylko wtedy, gdy w tablicy znajduje się więcej niż 25 000 elementów (chociaż minimum 50 000 wydaje się pozwolić na większy oddech procesora).

Zrobiłem tyle ulepszeń, ile mogę wymyślić na mojej małej maszynie dwurdzeniowej. Chciałbym wypróbować kilka pomysłów na potwora w 8-way. Również ta praca została wykonana na małym 13-calowym MacBooku z systemem Mono Ciekawi mnie, jak inni radzą sobie na normalnej instalacji .NET 2.0. go oczyścić, jeśli jest jakiś interes.

Answer 5

scalania sortowania na podstawie rozmiaru pamięci podręcznej procesora, przy czym bloki są podzielone pomiędzy procesorami przychodzi do głowy.

etap seryjnej można zrobić poprzez podział scalanie na n bitów, przy czym każdy procesor zaczyna scalać bloki z właściwego przesunięcia w blokach.Nie próbowałem tego pisać.

(jako względna szybkość pamięci podręcznej procesora i główny barana, nie jest tak daleko od względnej prędkości RAM i taśmę jako czas sortowania seryjnej została odkryta, może powinniśmy zacząć używać ponownie scalić rodzaju)