Алгоритм параллельной сортировки

Question

Я ищу простую реализацию параллельного (многопоточного) алгоритма сортировки в C#, который может работать с List<T> или массивами и, возможно, с использованием параллельных расширений, но эта часть не является абсолютно необходимой.

Редактировать: Фрэнк Крюгер дает хороший ответ, однако я хочу преобразовать этот пример в тот, который не использует LINQ. Также обратите внимание, что Parallel.Do() похоже на Parallel.Invoke().

Спасибо.

Answer 1

От «Darkside» в своей статье Parallel Extensions to the .Net Framework мы имеем эту Parallel Extensions версию быстрой сортировки:

(Edit: Так как связь теперь мертв, заинтересованные читатели могут найти архив его в 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)); 
     } 
    } 
} 

Обратите внимание, что он возвращается к последовательному то, когда число элементов меньше, чем 2048.

Answer 2

Разделить список вам нужно рассортированы подсписками одинакового размера, в зависимости от того, сколько процессоров у вас есть, и затем, когда выполняются две части, объедините их вместе с новой частью, пока не останется только один левый и все потоки завершены. Очень просто вы сможете реализовать его самостоятельно, и сортировка списков в каждом потоке может быть выполнена с использованием любого существующего алгоритма сортировки (например, в библиотеке).

Answer 3

Для записи здесь приведена версия без выражений lamda, которые будут скомпилированы в C# 2 и .Net 2 + Parallel Extensions. Это также должно работать с Mono с его собственной реализации параллельного расширения (от Google Summer кода 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

Update я теперь достичь лучше, чем 1.7x форсировки по двухъядерным машине.

Я думал, что попробую написать параллельный сортировщик, который работал в .NET 2.0 (я думаю, провери меня), и это не использует ничего, кроме ThreadPool.

Вот результаты сортировки массива 2000000 элемента:

 
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 

я получил 1.76x - довольно ускорение близко к оптимальному 2x я надеялся - в этой среде:

1. 2 000 000 случайных Model объектов
2. Сортировка объектов делегатом сравнения, который сравнивает два свойства DateTime.
3. Mono JIT компилятор версии 2.4.2.3
4. Max OS X 10.5.8 на 2,4 ГГц Intel Core 2 Duo

На этот раз я использовал Ben Watson's QuickSort in C#.Я изменил свой QuickSort внутренний цикл из:

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

к:

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

(. На самом деле, в коде я немного балансировки нагрузки, что делает, кажется, помогает)

Я что эта параллельная версия работает только при наличии более 25 000 элементов в массиве (хотя, как минимум, 50 000, как мне кажется, позволяют моему процессору больше дышать).

Я сделал так много улучшений, как я могу думать о своей маленькой двухъядерной машине. Я хотел бы попробовать некоторые идеи по 8-стороннему монстру. Кроме того, эта работа была выполнена на небольшом 13-дюймовом MacBook, работающем под управлением Mono. Мне любопытно, как другие платят за обычную установку .NET 2.0.

Исходный код во всей его уродливой славе доступен здесь: http://www.praeclarum.org/so/psort.cs.txt. очистить его, если есть какой-либо интерес.

Answer 5

сортировки слияние на основе размера кэша процессора, с блоков, которые разделены между процессорами приходит на ум.

этап слияния может быть сделан путем разделения слияния в n бит с каждым процессором, начинающим слияние блоков с правильным смещением в блоки.

Я не пробовал написать это.

(как относительная скорость кэша процессора и основной памяти, не так далеко от относительной скорости оперативной памяти и ленты, как время, была обнаружена сортировка слиянием, может быть, мы должны начать использовать сливать сорта снова)