Алгоритм препарата
Алгоритм Препараты представляет собой рекурсивный алгоритм «разделяй и властвуй», в котором вычисляется ранг каждого входного ключа, а ключи выводятся в соответствии с их рангами.
C++
m[i, j] := M[i, j]for 1 <= i, j <= n in parallel; for r : = 1 to logn do { Step 1. In parallel set q[i, j, k] := m[i, j] + m[j, k] for 1 <= i, j, k <= n. Step 2. In parallel set m[i, j] := min { q[i, l, j], q[i, 2, j], ..., q[i, n, j] } for 1 <= i, j <= n. }Put M(i)(i):=0 for all i and M(i)(j):=m[i, j] for i≠j |
В приведенной выше процедуре используется глобальная память O(N 3 ) с использованием переменных m[i, j] для 1 ≤ i, j ≤ N и q[i, j, k] для 1 ≤ i, j, k ≤ N. .
- Инициализация m[ ], которая занимает O(N 2 ) времени.
- Шаг 1 вышеприведенного алгоритма занимает время O(1) при использовании 3 процессоров.
- На шаге 2 вычисляется N 2 различных значений m[i, j] .
Вычисление одного m[z, j] включает в себя вычисление минимум N чисел и, следовательно, может быть выполнено за время O(1) с использованием N 2 процессоров CRCW PRAM . На самом деле, этот минимум также можно вычислить за время O(1) с использованием n (1 + e) процессоров для любого фиксированного e > 0 .
Шаг 2 может быть выполнен за время O(1) с использованием n (3 + e) обычных процессоров CRCW PRAM . Таким образом, цикл for выполняется за время O(log N) . Окончательное вычисление M также может быть выполнено за время O(1) с использованием N 2 процессоров.
Корректность приведенного выше алгоритма можно доказать индукцией по R . Можно показать, что значение m[i, j] в конце r -й итерации цикла for равно min, и минимум берется по всем последовательностям элементов {1, 2, …, N} . такое, что k < 2R . Приведенный выше алгоритм может быть специализирован для решения нескольких задач, включая транзитивное замыкание, связанные компоненты, минимальное остовное дерево и т. д.
Пусть k1, k2, …, kn — входная последовательность. Алгоритм Препараты разбивает вход на log N частей K1, K2, …, если log N; где в каждой части N/log N ключей.
Если k — любой ключ во входных данных, его ранг во входных данных вычисляется следующим образом. Во-первых, ранг Ri для k вычисляется для каждого i , 1< i < log N . Затем общий ранг k вычисляется как 
. Один из результатов, которые делают использование вышеописанного алгоритма.
Детали алгоритма Препараты приведены ниже.
Считайте T(N) временем выполнения алгоритма Препараты с использованием N*log N процессоров. Ясно, что шаг 1 занимает T(N/log N) времени , а шаги 2 и 3 вместе занимают время O(log(log N)) времени . Таким образом, есть
T(n) = T(N/log N) + O(log(log N))
которое можно решить повторной подстановкой, чтобы получить T (N) = O (log N). Кроме того, количество процессоров, используемых на каждом шаге, равно N*log N.
Алгоритм сортировки Препараты
Ниже приведены шаги алгоритма сортировки Препарата:
- Если N — небольшая константа, отсортируйте ключи по любому алгоритму и выйдите.
- Разделите данные N ключей на log N частей, по N/(log N) ключей в каждой части.
- Отсортируйте каждую часть рекурсивно и отдельно параллельно, назначив каждой части N процессоров. Пусть S 1 , S 2 , …, S log N — отсортированные последовательности.
- Объедините S i с S j для 1< i, j < log N параллельно. Это можно сделать, выделив N / (log N) процессоров каждой паре (i, j). То есть, используя процессоры N*log N , этот шаг можно выполнить за время O(log(log N)) алгоритма. В качестве побочного продукта этого этапа слияния ранг вычисляется для каждого ключа в каждом из S i (1 < i < log N ).
- Выделите log N процессоров для вычисления ранга каждого ключа в исходном вводе. Это делается параллельно для всех ключей путем сложения log N рангов, вычисленных (для каждого ключа) на шаге 2. Это можно сделать за время O(log(log N)) с использованием алгоритма вычисления префикса.
- Наконец, ключи записываются в порядке их рангов.
Ниже приведена реализация вышеуказанного подхода: