Четность перестановки с параллелизмом

Question

У меня есть целочисленный массив длины N, содержащий значения 0, 1, 2, .... (N-1), представляющий перестановку целочисленных индексов.

Какой самый эффективный способ определить если перестановка имеет нечетную или четную четность, учитывая, что у меня также есть параллельное вычисление O (N)?

Например, вы можете суммировать N чисел в журнале (N) с параллельным вычислением. Я ожидаю найти четность перестановок в log (N), но не могу найти алгоритм. Я также не знаю, как называется этот «порядок сложности с параллельным вычислением».

Answer 1

Число в каждом слоте массива соответствует слоту для этого элемента. Думайте об этом как о прямой ссылке от слота "от" до слота "к". Такой массив очень легко отсортировать за время O (N) на одном процессоре, просто следуя ссылкам, поэтому было бы стыдно использовать общий алгоритм сортировки c для решения этой проблемы. К счастью ...

Вы можете легко сделать это за время O (log N) с Ω (N) CPU.

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

Четность перестановка - это нечетность N-m, где N - длина массива, а m - количество циклов, поэтому мы можем получить ваш ответ, посчитав циклы.

Сначала сделайте массив S длиной N и установите S[i] = i.

Затем:

Repeat ceil(log_2(N)) times:
    foreach i in [0,N), in parallel:
        if S[i] < S[A[i]] then:
            S[A[i]] = S[i]
        A[i] = A[A[i]]

Когда это будет завершено, каждый S[i] будет содержать наименьший индекс в цикл, содержащий i. Первый проход внутреннего l oop распространяет наименьшее S[i] на следующий слот в цикле, следуя ссылке в A[i]. Затем каждая ссылка становится вдвое длиннее, поэтому на следующем проходе она будет распространена на 2 новых слота, et c. Для распространения самого маленького S[i] по циклу требуется не более ceil(log_2(N)) проходов.

Назовем самый маленький слот в каждом цикле «лидером» цикла. Количество лидеров - это количество циклов. Мы можем найти лидеров просто так:

foreach i in [0,N), in parallel:
    if (S[i] == i) then:
        S[i] = 1  //leader
    else
        S[i] = 0  //not leader

Наконец, мы можем просто сложить элементы S, чтобы получить количество циклов в перестановке, из которого мы можем легко вычислить ее четность.

Answer 2

Вы не указали модель машины, поэтому я предполагаю, что мы работаем с EREW PRAM . Мера сложности, о которой вы заботитесь, называется «размахом», количеством раундов, которые требуется вычислить. Есть также «работа» (количество операций, суммированное по всем процессорам) и «стоимость» (диапазон, умноженный на количество процессоров).

С точки зрения теории очевидным ответом является изменение O (log n) -глубинная сортировочная сеть (AKS или Goodrich's Zigzag Sort) для подсчета свопов, затем возврат (количество свопов) по модулю 2. Код очень сложен, а постоянные коэффициенты довольно велики.

A Более практичный алгоритм состоит в том, чтобы вместо этого использовать сеть сортировки bitoni c Batcher, которая увеличивает диапазон до O (log ² n), но имеет разумные постоянные коэффициенты (так что люди фактически используют его на практике для сортировки на графических процессорах ).

Я не могу придумать практического детерминированного c алгоритма с диапазоном O (log n), но вот рандомизированный алгоритм с диапазоном O (log n) с высокой вероятностью. Предположим, что n процессоров и пусть вход (изменяемый) будет Perm. Пусть Coin будет массивом из n логических значений.

В каждом из O (log n) проходов процессоры параллельно выполняют следующие операции, где i ∈ {0… n-1} идентифицирует процессор и меняет местами ← 0 изначально. Переменные в нижнем регистре обозначают локальные переменные процессора.

Coin[i] ← true with probability 1/2, false with probability 1/2
(barrier synchronization required in asynchronous models)
if Coin[i]
    j ← Perm[i]
    if not Coin[j]
        Perm[i] ← Perm[j]
        Perm[j] ← j
        swaps ← swaps + 1
    end if
end if
(barrier synchronization required in asynchronous models)

После этого мы суммируем локальные значения свопов и модов на 2.

Каждый проход уменьшает количество i, так что Perm [ i] ≠ i на 1/4 от текущего результата в ожидании. Благодаря линейности математического ожидания, ожидаемая сумма не превышает n (3/4) ^r , поэтому после r = 2 log _4/3 n = O (log n) проходит , ожидаемая сумма не превышает 1 / n, что, в свою очередь, ограничивает вероятность того, что алгоритм не сходится к тождественной перестановке, как требуется. В случае неудачи мы можем просто переключиться на последовательный алгоритм O (n) -span, не увеличивая ожидаемый диапазон, или просто повторить попытку.