Algoritmo Preparado

El algoritmo de Preparata es un algoritmo recursivo divide y vencerás en el que se calcula el rango de cada clave de entrada y las claves se emiten de acuerdo con sus rangos.

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

En el procedimiento anterior, la memoria global O(N ³ ) se usa usando las variables m[i, j] para 1 ≤ i, j ≤ N y q[i, j, k] para 1 ≤ i, j, k ≤ N .

• Inicializando m[ ] que toma tiempo O(N ² ).
• El paso 1 del algoritmo anterior toma O (1) tiempo mientras usa 3 procesadores.
• En el paso 2, se calculan N ² números de m[i, j] diferentes.

El cálculo de un único m[z, j] implica calcular un mínimo de N números y, por lo tanto, puede completarse en O(1) tiempo utilizando N2 procesadores ^CRCW PRAM . De hecho, este mínimo también se puede calcular en tiempo O(1) usando n ^{(1 + e)} ​​procesadores para cualquier e > 0 fijo .

El paso 2 se puede completar en tiempo O(1) utilizando n ^{(3 + e)} ​​procesadores PRAM CRCW comunes . Por lo tanto, el ciclo for se ejecuta en tiempo O (log N) . El cómputo final de M también se puede hacer en tiempo O(1) usando N ² procesadores.

La corrección del algoritmo anterior se puede probar por inducción en R . Se puede demostrar que el valor de m[i, j] al final de la r ^-ésima iteración del bucle for es min, y el mínimo se toma sobre todas las secuencias de elementos de {1, 2, …, N} tal que k < 2R . El algoritmo anterior se puede especializar para resolver varios problemas, incluido el cierre transitivo, los componentes conectados, el árbol de expansión mínimo, etc.

Sea k1, k2, …, kn la secuencia de entrada. El algoritmo de Preparata divide la entrada en log N partes K1, K2, …, si log N; donde hay claves N/log N en cada parte.
Si k es cualquier clave en la entrada, su rango en la entrada se calcula de la siguiente manera. Primero, el rango Ri de k se calcula para cada i , 1< i < log N . Luego, el rango total de k se calcula como  . Uno de los resultados que hacen el uso del algoritmo anterior. 

Los detalles del algoritmo de Preparata se dan a continuación.

Considere que T(N) es el tiempo de ejecución del algoritmo de Preparata utilizando procesadores N*log N. Claramente, el paso 1 toma el tiempo T(N/log N) y los pasos 2 y 3 juntos toman el tiempo O(log(log N)) . Por lo tanto, hay

T(n) = T(N/log N) + O(log(log N))

que se puede resolver mediante sustitución repetida para obtener T(N) = O(log N). Además, el número de procesadores utilizados en cada paso es N*log N.

Algoritmo de clasificación de Preparata

A continuación se muestran los pasos para el algoritmo de clasificación de Preparata:

• Si N es una constante pequeña, ordene las claves usando cualquier algoritmo y salga.
• Particionar las N claves dadas en log N partes, con N/(log N) claves en cada parte.
• Ordene cada parte de forma recursiva y por separado en paralelo, asignando N procesadores a cada parte. Sean S ₁ , S ₂ , …, S _{log N} las secuencias ordenadas.
• Combinar S _i con S _j para 1< i, j < log N en paralelo. Esto se puede hacer asignando procesadores N / (log N) a cada par (i, j). Es decir, utilizando procesadores N*log N , este paso se puede realizar en tiempo O(log(log N)) con el algoritmo. Como subproducto de este paso de fusión, se calcula el rango de cada clave en cada uno de los S _i ‘s (1 < i < log N ).
• Asigne procesadores log N para calcular el rango de cada clave en la entrada original. Esto se hace en paralelo para todas las claves agregando los rangos de log N calculados (para cada clave) en el paso 2. Esto se puede hacer en tiempo O (log (log N)) usando el algoritmo de cálculo de prefijo.
• Finalmente, las claves se escriben en el orden de sus rangos.

A continuación se muestra la implementación del enfoque anterior:

# Python program to implement Preparata's
# a time-optimal parallel algorithm
  
  
class func:
    def __init__(self, x, y):
        self.x = x
        self.y = y
  
# Function to find the left index of
# the given set of points
def Left_index(points):
      
    # Finding the point on plane
    minn = 0
      
    # Traverse the given points
    for i in range(1, len(points)):
        
          # Update the value of minn
        if points[i].x < points[minn].x:
            minn = i
        elif points[i].x == points[minn].x:
            if points[i].y > points[minn].y:
                minn = i
                  
    # Return the value of min
    return minn
  
# Function to perform the parallel
# process in the preparata's algorithm
# according to the value of p, q, r
def parallel(p, q, r):
  
    # For the three-dimensional
    val = (q.y - p.y) * (r.x - q.x) - \
        (q.x - p.x) * (r.y - q.y)
  
    if val == 0:
        return 0
    elif val > 0:
        return 1
    else:
        return 2
  
# Function to perform the parallel
# process in the preparata's algorithm
def preparata(points, n):
  
    # There must be at least 3 points
    if n < 3:
        return
  
    # Find the leftmost point
    l = Left_index(points)
  
    pre = []
  
    p = l
    q = 0
    while(True):
  
        # Add current point to result
        pre.append(p)
  
        q = (p + 1) % n
  
        for i in range(n):
  
            # If i is more counterclockwise
            # than current q, then update q
            if(parallel(points[p],
                        points[i], points[q]) == 2):
                q = i
  
        p = q
  
        # While it doesn't come to first point
        if(p == l):
            break
  
    # Print Result
    for each in pre:
        print(points[each].x, points[each].y)
  
# Driver Code
  
  
algo = []
algo.append(func(0, 3))
algo.append(func(2, 2))
algo.append(func(1, 1))
algo.append(func(2, 1))
algo.append(func(3, 0))
algo.append(func(0, 0))
algo.append(func(3, 3))
  
# Function Call
preparata(algo, len(algo))

0 3
0 0
3 0
3 3