Блог

Возможно ли выполнить сортировку с параллельным подсчетом и достичь O (n / p) времени выполнения?

Возьмем пример, в котором у нас есть массив с миллионами элементов в диапазоне от 1 до 10. Сортировка слиянием будет выполняться не быстрее, чем за O (nlogn) время. Сортировка с подсчетом, примененная к этой задаче, будет выполняться за O (n) время. Распараллеливание сортировки с подсчетом может быть интересным. Если мы назначаем подмассив с n / p элементами каждому процессору, и у каждого процессора есть свой собственный массив подсчета размером 9, начальный шаг, на котором накапливается количество элементов, должен занимать O (n / p) времени. Объединение всех массивов count в один массив должно занять O (p) времени, поскольку вы повторяете только p массивов count, каждый из которых имеет постоянный размер.

Я не смог полностью продумать последний шаг сортировки подсчета, где элементы располагаются по порядку. Если элементы массива count являются атомарными, вы можете назначить n / p разделов исходного массива отдельным процессорам и добиться некоторого распараллеливания, но в отдельных элементах массива count возникнут разногласия, что потенциально существенно снизит распараллеливание. Если входной массив состоит из всех 10, все процессоры будут сериализованы на 9-м элементе массива count, что снизит алгоритмическую эффективность до O (n).

Вы можете назначить подмассивы массива count каждому из p процессоров, и вы вернетесь к O (n / p) времени выполнения, но только если элементы распределены достаточно равномерно. И в нашем примере вы были бы ограничены 10 процессорами. Если элементы распределены неравномерно, один или несколько процессоров могут выполнять большую часть работы. Например, если половина элементов во входном массиве равна 10, одному процессору придется пройти половину массива. В худшем случае массив состоит из 10 элементов, и одному процессору пришлось бы проходить через весь массив, передавая время выполнения O (n).

Возможно, вы могли бы разделить отдельные элементы массива count между несколькими процессорами. Например, если во входном массиве 50 10, элемент 9 массива count будет отражать это. У вас может быть 5 процессоров, которые записывают 10 10 каждый в соответствующие позиции в выходном массиве. Это снова переходит к O (n) времени выполнения, если в каждом местоположении индекса массива count меньше p элементов, но это позволяет избежать проблемы, когда распределение значений элементов неравномерно.

Возможно ли выполнить сортировку с подсчетом за O (n / p) время?

Да, это возможно. Разделите свой массив на p части равной длины. Затем создайте массив подсчета ‘c’ для каждого процесса. Пусть каждый процесс подсчитывает количество элементов и сохраняет их c . Это займет O(n/p) . Теперь добавьте все массивы подсчета c вместе и сделайте массив общим для всех процессов. Это займет O(p*b) , где b число возможных значений. Пока это именно ваш подход. Теперь вы можете воссоздать массив в p процессах, поскольку вы можете вычислить первый и последний индекс значения c . Для каждого значения i его первый индекс является суммой всех предыдущих значений c . Его последний индекс равен его первому индексу плюс c[i] . Это вычисление может быть выполнено в O(i) том, где i тогда b меньше, поэтому оно меньше O(b) . Теперь каждый процесс может повторно заполнить свою часть. Это снова требуется O(n/p) . Подводя итог, у вас есть n/p p*b b n/p . Если p*b << n это приведет O(2*n/p) к. (Поскольку 2/p это постоянный фактор, у вас все еще есть класс O(n) . Но распараллеливание значительно ускорит ваш алгоритм.)