Можете ли вы выполнить параллельный подсчет в O (n/p) времени?

Question

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

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

Я не смог полностью продумать последний шаг в сортировке подсчета, где элементы упорядочены. Если элементы массива count являются атомарными, вы можете назначить n/p-секции исходного массива отдельным процессорам и добиться некоторой распараллеливания, но на отдельных элементах массива count будут возникать разногласия, что потенциально существенно уменьшит распараллеливание. Если входной массив равен всем 10, все процессоры будут сериализоваться на девятом элементе массива 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) времени?

Answer 1

Да, это возможно. Разделите массив в 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). Но параллелизация значительно ускорит ваш алгоритм.)