Параллельный алгоритм сортировки

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

Divide the list you need sorted into equal sized sublists, depending on how many processors you have, and then whenever two parts are done, merge them together to a new part, until there is only one left and all threads completed. Very simple you should be able to implement it yourself, and sorting the lists within each thread can be done using any existing sort algorithm (like in the library).

Обновление Теперь я достигаю более чем 1,7-кратного ускорения на двухъядерном компьютере.

Я подумал, что могу попробовать написать параллельный сортировщик, который работал бы в .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 раза - довольно близко к оптимальное 2x, на которое я надеялся - в этой среде:

1. 2 000 000 случайных объектов модели
2. Сортировка объектов делегатом сравнения, который сравнивает два свойства DateTime .
3. Mono JIT-компилятор версии 2.4.2.3
4. 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-стороннем монстре. Кроме того, эта работа была проделана на маленьком 13-дюймовом MacBook с Mono. Мне любопытно, как обстоят дела у других с обычной установкой .NET 2.0.

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

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

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

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

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

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

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

Мне интересно, как обстоят дела у других с обычной установкой .NET 2.0.

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

Мне интересно, как обстоят дела у других с обычной установкой .NET 2.0.

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

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

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

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

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

{{ 1}}