Параллельная сортировка слиянием

Question

Я пытаюсь получить интуитивное понимание того, насколько я мог бы ускорить сортировку слиянием, если я распараллеливаю ее.

Мои мысли пока:

Если N - это количество элементовв массиве, который нужно отсортировать, тогда log (base 2) N - наибольшее количество ядер, которое мне нужно.Я полагаю, что это так, потому что есть 2 * log (база 2) N + 1 уровней в слиянии.Сначала вы разбиваете его, деля его на два снова и снова, затем вы снова и снова объединяете два отсортированных массива, пока у вас снова не появится массив из N элементов (а теперь он отсортирован).

Япытаясь выяснить, насколько это на самом деле улучшит производительность.Я думаю, что увеличение производительности за счет дополнительных ядер будет увеличиваться по мере продвижения к середине алгоритма, потому что мы можем использовать больше ядер.Скажем, у меня есть 16 элементов в несортированном массиве.Мне нужно использовать только одно ядро, чтобы разбить его на два массива по 8 элементов, а затем я могу использовать два ядра, чтобы разбить их на четыре массива по 4 элемента и т. Д.

Таким образом, производительность увеличится в несколько раздва для каждого уровня разделения, а затем уменьшиться на два для каждого уровня слияния ... верно?Я на правильном пути?

Кроме того, почему мы не можем просто начать с объединения первых двух элементов в несортированном массиве, затем следующих двух и так далее.В основном избавиться от первой половины алгоритма?

Мысли?

Должен ли я спросить об этом на math.stackexchange.com вместо этого?Извините, если так ... Я действительно не знал

Answer 1

1) Параллельно каждый последовательный процессор сортирует n / p массива.

2) Для i = 1 до log_2 (p) Вы должны объединить два массива с 2 ^ i процессорами. За время O (log 2 ^ i) один процессор выполняет двоичный поиск, используя среднюю точку наибольшего раздела массива (из которого мы разбиваемся на две части) в другой массив, чтобы найти, где он совпадает, и сформировать там другой раздел.

Пример:

A = 12345 6789

B = 1234 567 89

Самый большой раздел - 12345, средняя точка - 3. Используйте двоичный поиск, чтобы найти, где это 3, в другом массиве и разбить его. Новые массивы:

А = 12 345 6789 B = 12 34 567 89

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

После того, как вы разбили массивы A и B на секции O (p), вы можете выполнять последовательное слияние параллельно для каждого из этих небольших кусков. Чтобы получить смещение того, куда выводится каждая пара, вы можете сделать параллельную сумму префикса перед раздачей.

O (n / p log n / p) // последовательная сортировка, только O (n / p), если вы можете радикально отсортировать

O (log (p) * (log (p) + (n / p)) = O (log (p) ^ 2 + log (p) (n / p)) // параллельное объединение

Answer 2

Dual Pivot QuickSort, как известно, превзошел Сортировку слиянием в серийных версиях.Я думаю, что параллельная форма DPQ действительно может быть самым быстрым алгоритмом сортировки из когда-либо созданных.Причина в том, что он имеет низкие постоянные коэффициенты, чем MergeSort, и его сложность во времени в наихудшем случае имеет вероятность возникновения только 1 / (n!).Если N большое, предпочтите DPQ, возможно многопоточность, если это возможно.Но параллелизм имеет опору или предел, ниже предела он медленный из-за управления потоками.За пределом это намного быстрее.В случае, если вы заинтересованы, последовательный код ниже (как по возрастанию, так и по убыванию)

protected static void ASC(int[]a, int left, int right, int div)
{
    int len = 1 + right - left;
    if (len < 27)
    {
        // insertion sort for small array
        int P1 = left + 1;
        int P2 = left;
        while ( P1 <= right )
        {
            div = a[P1];
            while(( P2 >= left )&&( a[P2] > div ))
            {
                a[P2 + 1] = a[P2];
                P2--;
            }
            a[P2 + 1] = div;
            P2 = P1;
            P1++;
        }
        return;
    }
    int third = len / div;
    // "medians"
    int P1 = left + third;
    int P2 = right - third;
    if (P1 <= left)
    {
        P1 = left + 1;
    }
    if (P2 >= right)
    {
        P2 = right - 1;
    }
    int temp;
    if (a[P1] < a[P2])
    {
        temp = a[P1]; a[P1] = a[left]; a[left] = temp;
        temp = a[P2]; a[P2] = a[right]; a[right] = temp;
    }
    else
    {
        temp = a[P1];  a[P1] = a[right];  a[right] = temp;
        temp = a[P2];  a[P2] = a[left];  a[left] = temp;
    }
    // pivots
    int pivot1 = a[left];
    int pivot2 = a[right];
    // pointers
    int less = left + 1;
    int great = right - 1;
    // sorting
    for (int k = less; k <= great; k++)
    {
        if (a[k] < pivot1)
        {
            temp = a[k];  a[k] = a[less];  a[less] = temp;
            less++;
        }
        else if (a[k] > pivot2)
        {
            while (k < great && a[great] > pivot2)
            {
                great--;
            }
            temp = a[k];  a[k] = a[great];  a[great] = temp;
            great--;
            if (a[k] < pivot1)
            {
                temp = a[k];  a[k] = a[less];  a[less] = temp;
                less++;
            }
        }
    }
    int dist = great - less;
    if (dist < 13)
    {
        div++;
    }
    temp = a[less-1];  a[less-1] = a[left];  a[left] = temp;
    temp = a[great+1];  a[great+1] = a[right];  a[right] = temp;
    // subarrays
    ASC(a, left, less - 2, div);
    ASC(a, great + 2, right, div);
    // equal elements
    if (dist > len - 13 && pivot1 != pivot2)
    {
        for (int k = less; k <= great; k++)
        {
            if (a[k] == pivot1)
            {
                temp = a[k];  a[k] = a[less];  a[less] = temp;
                less++;
            }
            else if (a[k] == pivot2)
            {
                temp = a[k];  a[k] = a[great];  a[great] = temp;
                great--;
                if (a[k] == pivot1)
                {
                    temp = a[k];  a[k] = a[less];  a[less] = temp;
                    less++;
                }
            }
        }
    }
    // subarray
    if (pivot1 < pivot2)
    {
        ASC(a, less, great, div);
    }
}

protected static void DSC(int[]a, int left, int right, int div)
{
    int len = 1 + right - left;
    if (len < 27)
    {
        // insertion sort for large array
        int P1 = left + 1;
        int P2 = left;
        while ( P1 <= right )
        {
            div = a[P1];
            while(( P2 >= left )&&( a[P2] < div ))
            {
                a[P2 + 1] = a[P2];
                P2--;
            }
            a[P2 + 1] = div;
            P2 = P1;
            P1++;
        }
        return;
    }
    int third = len / div;
    // "medians"
    int P1 = left + third;
    int P2 = right - third;
    if (P1 >= left)
    {
        P1 = left + 1;
    }
    if (P2 <= right)
    {
        P2 = right - 1;
    }
    int temp;
    if (a[P1] > a[P2])
    {
        temp = a[P1]; a[P1] = a[left]; a[left] = temp;
        temp = a[P2]; a[P2] = a[right]; a[right] = temp;
    }
    else
    {
        temp = a[P1];  a[P1] = a[right];  a[right] = temp;
        temp = a[P2];  a[P2] = a[left];  a[left] = temp;
    }
    // pivots
    int pivot1 = a[left];
    int pivot2 = a[right];
    // pointers
    int less = left + 1;
    int great = right - 1;
    // sorting
    for (int k = less; k <= great; k++)
    {
        if (a[k] > pivot1)
        {
            temp = a[k];  a[k] = a[less];  a[less] = temp;
            less++;
        }
        else if (a[k] < pivot2)
        {
            while (k < great && a[great] < pivot2)
            {
                great--;
            }
            temp = a[k];  a[k] = a[great];  a[great] = temp;
            great--;
            if (a[k] > pivot1)
            {
                temp = a[k];  a[k] = a[less];  a[less] = temp;
                less++;
            }
        }
    }
    int dist = great - less;
    if (dist < 13)
    {
        div++;
    }
    temp = a[less-1];  a[less-1] = a[left];  a[left] = temp;
    temp = a[great+1];  a[great+1] = a[right];  a[right] = temp;
    // subarrays
    DSC(a, left, less - 2, div);
    DSC(a, great + 2, right, div);
    // equal elements
    if (dist > len - 13 && pivot1 != pivot2)
    {
        for (int k = less; k <= great; k++)
        {
            if (a[k] == pivot1)
            {
                temp = a[k];  a[k] = a[less];  a[less] = temp;
                less++;
            }
            else if (a[k] == pivot2)
            {
                temp = a[k];  a[k] = a[great];  a[great] = temp;
                great--;
                if (a[k] == pivot1)
                {
                    temp = a[k];  a[k] = a[less];  a[less] = temp;
                    less++;
                }
            }
        }
    }
    // subarray
    if (pivot1 > pivot2)
    {
        DSC(a, less, great, div);
    }
}

Answer 3

Если вы хотите повысить производительность MergeSort с помощью распараллеливания, вам следует распараллелить разбиение (часть, которую вы выполняете до объединения результатов).Я предполагаю, что у вас есть несколько узлов ЦП.

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

Базовый случай: Когда данные представляют собой один элемент, текущий узел ЦП отправляет их обратно на родительский узел.Родительские узлы будут ждать, пока дочерние узлы передадут данные, прежде чем выполнять любое объединение.

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

Это должно ускорить сортировку слиянием.

Однако эта статья в Википедии http://en.wikipedia.org/wiki/Merge_sort#Parallel_processing показывает, что вы можете ускорить шаг слияния до O (1) распараллеливая и специализируя его (а также добавляя сортировку вставкой, когда размер данных <11) </p>

Мне любопытно, почему вы не используете Quicksort.Он прекрасно подходит для распараллеливания!

Edit:

Кроме того, почему мы не можем просто начать с объединения первых двух элементов в несортированном массиве, затем следующих двух и так далее?на.В основном избавиться от первой половины алгоритма?

И ответить на ваш вопрос:

Вот что делает сортировка слиянием, это слияниепервые 2, следующие 2 и так далее, но чтобы добраться до них, он использует рекурсию.Что делает время выполнения O (n * 2log (n)), потому что есть 2 дерева (одно создано при разбиении и одно создано при объединении в один большой список).Это относится к O (nlog (n)).

Возьмите свою идею, начните снизу, возьмите 2 на 2 числа и отсортируйте их.Затем увеличьте границы, чтобы охватить 2 блока (каждый w 2 номера) 4 номера ... и так далее.Вы строите дерево, от листьев до корня.Это похоже на алгоритм турнира (хотя там у вас может быть только один победитель - корень дерева).

Время выполнения: сначала у вас есть n чисел.Вы зацикливаетесь, поэтому устанавливаете границы для каждых 2 чисел O (n / 2), следующего уровня O (n / 4), следующего O (n / 8) и так далее.Для построения этого дерева требуется O (log (n)).Но вы все равно должны объединить другие номера в список.Поскольку у вас есть n чисел, то есть n * O (nlogn), что дает вам то же время выполнения, что и сортировка слиянием nlogn.

Резюме: Итак, я пытаюсь сказать, что ваша идеяслияния снизу еще долго.Вы избавляетесь от одного из деревьев, поэтому ускорение незначительно.