Алгоритм Параллельной Сортировки

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

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

Спасибо.

5 25
c# .net sorting parallel-processing parallel-extensions

5 ответов:

Из "темной стороны" в своей статье параллельные расширения для .Net Framework мы имеем эту версию параллельных расширений quicksort:

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

Обновление теперь я достигаю лучшего, чем 1.7 x ускорение на двухъядерной машине.

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

Вот результаты сортировки массива из 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

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

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

На этот раз я использовал QuickSort Бена Уотсона в 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-way monster. Кроме того, эта работа была сделана на маленьком 13" MacBook, работающем моно. Мне любопытно, как другие справляются с обычной установкой .NET 2.0.

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

7

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

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

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

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

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

6

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

0