Ordenación de muestras

El siguiente listado muestra el algoritmo de tres pasos mencionado anteriormente como pseudocódigo y muestra cómo funciona el algoritmo en principio. ^{[ 5 ]} A continuación, A son los datos sin ordenar, k es el factor de sobremuestreo, que se analizará más adelante, y p es el número de divisores.

función sampleSort(A[1..n], k , p ) // Si el tamaño promedio del cubo está por debajo de un umbral, cambia a, por ejemplo, ordenación rápida Si n / k < umbral , entonces smallSort(A) /* Paso 1 */ seleccionar S = [ S 1 , ..., S ( p −1) k ] aleatoriamente de // seleccionar muestras ordenar S // ordenar muestra [ s 0 , s 1 , ..., s p −1 , s p ] <- [-∞, S k , S 2 k , ..., S ( p −1) k , ∞] // seleccionar divisores /* Paso 2 */ Para cada a en A, encuentra j tal que s j −1 < a <= s j coloca a en el cubo b j /* Paso 3 y concatenación */ return concatenar(sampleSort( b 1 ), ..., sampleSort( b k ))

El pseudocódigo difiere del algoritmo original de Frazer y McKellar. ^{[ 3 ]} En el pseudocódigo, se llama a samplesort de forma recursiva. Frazer y McKellar llamaron a samplesort solo una vez y utilizaron quicksort en todas las iteraciones siguientes.

La complejidad, dada en notación Big O , para una implementación paralela con${\displaystyle p}$procesadores:

Encuentra los divisores.

${\displaystyle O\left({\frac {n}{p}}+\log(p)\right)}$

Enviar a los contenedores.

${\displaystyle O(p)}$para leer todos los nodos

${\displaystyle O(\log(p))}$para radiodifusión

${\displaystyle O\left({\frac {n}{p}}\log(p)\right)}$para búsqueda binaria para todas las claves

${\displaystyle O\left({\frac {n}{p}}\right)}$enviar claves al bucket

Clasificar los cubos.

${\displaystyle O\left(c\left({\frac {n}{p}}\right)\right)}$dónde${\displaystyle c(n)}$es la complejidad del método de ordenación secuencial subyacente. ^{[ 1 ]} A menudo${\displaystyle c(n)=n\log(n)}$.

El número de comparaciones realizadas por este algoritmo se aproxima al óptimo teórico de la información.${\displaystyle \log _{2}(n!)}$para secuencias de entrada grandes. En experimentos realizados por Frazer y McKellar, el algoritmo necesitó un 15 % menos de comparaciones que quicksort.

La relación de sobremuestreo determina cuántas veces más elementos de datos se extraen como muestras, antes de determinar los divisores. El objetivo es obtener una buena representación de la distribución de los datos. Si los valores de los datos están ampliamente distribuidos, es decir, no hay muchos valores duplicados, entonces una relación de muestreo pequeña es suficiente. En otros casos donde hay muchos duplicados en la distribución, será necesaria una relación de sobremuestreo mayor. En el caso ideal, después del paso 2, cada cubo contiene${\displaystyle n/p}$elementos. En este caso, ningún cubo tarda más en ordenarse que los demás, porque todos los cubos tienen el mismo tamaño.

Después de tirar${\displaystyle k}$veces más muestras de las necesarias, las muestras se clasifican. Posteriormente, los divisores utilizados como límites de cubeta son las muestras en la posición${\displaystyle k,2k,3k,\dots ,(p-1)k}$de la secuencia de muestras (junto con${\displaystyle -\infty }$y${\displaystyle \infty }$como límites izquierdo y derecho para los cubos más a la izquierda y más a la derecha respectivamente). Esto proporciona una mejor heurística para buenos divisores que simplemente seleccionar${\displaystyle p}$divisores aleatoriamente.

Con el tamaño de muestra resultante, se puede estimar el tamaño esperado del cubo y, especialmente, la probabilidad de que un cubo supere un cierto tamaño. A continuación se mostrará que para un factor de sobremuestreo de${\displaystyle S\in \Theta \left({\dfrac {\log n}{\epsilon ^{2}}}\right)}$la probabilidad de que ningún cubo tenga más de${\displaystyle (1+\epsilon )\cdot {\dfrac {n}{p}}}$elementos es mayor que${\displaystyle 1-{\dfrac {1}{n}}}$.

Para demostrar esto, dejemos que${\displaystyle \langle e_{1},\dots ,e_{n}\rangle }$sea ​​la entrada como una secuencia ordenada. Para que un procesador obtenga más de${\displaystyle (1+\epsilon )\cdot n/p}$elementos, debe existir una subsecuencia de la entrada de longitud${\displaystyle (1+\epsilon )\cdot n/p}$de las cuales se selecciona un máximo de S muestras. Estos casos constituyen la probabilidad${\displaystyle P_{\text{fail}}}$Esto puede representarse como la variable aleatoria: $${\displaystyle X_{i}:={\begin{cases}1,&{\text{if }}s_{i}\in \left\langle e_{j},\dots ,e_{j}+(1+\epsilon )\cdot {\dfrac {n}{p}}\right\rangle \\0,&{\text{otherwise}}\end{cases}},X:=\sum _{i=0}^{S\cdot p-1}X_{i}}$$

Para el valor esperado de${\displaystyle X_{i}}$contiene: $${\displaystyle E(X_{i})=P(X_{i}=1)={\dfrac {1+\epsilon }{p}}}$$

Esto se utilizará para estimar${\displaystyle P_{\text{fail}}}$: $${\displaystyle P(X<S)\approx P(X<(1-\epsilon ^{2})S)=P(X<(1-\epsilon )E(X))}$$

Utilizando ahora la cota de Chernoff , se puede demostrar que: $${\displaystyle P_{\text{fail}}=n\cdot P(X<S)\leq n\cdot \exp \left({\dfrac {-\epsilon ^{2}\cdot S}{2}}\right)\leq n\cdot {\dfrac {1}{n^{2}}}{\text{ for }}S\geq {\dfrac {4}{\epsilon ^{2}}}\ln n}$$

En un algoritmo de ordenación basado en comparaciones, la operación de comparación es la parte más crítica en términos de rendimiento. En Samplesort, esto corresponde a determinar el cubo para cada elemento. Esto requiere${\displaystyle \log k}$tiempo para cada elemento.

El algoritmo Super Scalar Sample Sort utiliza un árbol de búsqueda equilibrado que se almacena implícitamente en una matriz t . La raíz se almacena en 0, el sucesor izquierdo de${\displaystyle t_{i}}$se almacena en${\displaystyle t_{2i}}$y el sucesor correcto se almacena en${\displaystyle t_{2i+1}}$Dado el árbol de búsqueda t , el algoritmo calcula el número de cubeta j del elemento${\displaystyle a_{i}}$de la siguiente manera (suponiendo${\displaystyle a_{i}>t_{j}}$se evalúa como 1 si es verdadero y 0 en caso contrario):

j := 1 repetir log 2 ( p ) veces j := 2 j + ( a > t j ) j := j − p + 1

Dado que el número de cubetas k se conoce en tiempo de compilación, el compilador puede desenrollar este bucle. La operación de comparación se implementa con instrucciones predicadas . Por lo tanto, no se producen predicciones erróneas de bifurcación , lo que ralentizaría significativamente la operación de comparación.

Para una partición eficiente de los elementos, el algoritmo necesita conocer de antemano el tamaño de los cubos. Para particionar los elementos de la secuencia e insertarlos en el array, necesitamos conocer el tamaño de los cubos con anticipación. Un algoritmo simple podría contar el número de elementos de cada cubo. Luego, los elementos podrían insertarse en el otro array en el lugar correcto. De esta manera, es necesario determinar el cubo para cada elemento dos veces (una vez para contar el número de elementos en un cubo y otra para insertarlos).

Para evitar esta duplicación de comparaciones, Super Scalar Sample Sort utiliza una matriz adicional.${\displaystyle o}$(llamado oráculo) que asigna cada índice de los elementos a un cubo. Primero, el algoritmo determina el contenido de${\displaystyle o}$determinando el cubo para cada elemento y los tamaños de los cubos, y luego colocando los elementos en el cubo determinado por${\displaystyle o}$. La matriz${\displaystyle o}$también genera costos de almacenamiento, pero como solo necesita almacenar${\displaystyle n\cdot \log k}$bits, estos costos son pequeños en comparación con el espacio del arreglo de entrada.

En un primer paso, la matriz de entrada se divide en${\displaystyle p}$franjas de bloques de igual tamaño, una para cada procesador. Cada procesador asigna además${\displaystyle k}$Se utilizan búferes del mismo tamaño que los bloques, uno para cada cubeta. Posteriormente, cada procesador escanea su franja y mueve los elementos al búfer de la cubeta correspondiente. Si un búfer está lleno, se escribe en la franja del procesador, comenzando desde el principio. Siempre hay al menos un búfer vacío, ya que para que se escriba en un búfer (es decir, que esté lleno), se debe escanear al menos un búfer completo con más elementos que los que se han escrito. Por lo tanto, cada bloque completo contiene elementos de la misma cubeta. Durante el escaneo, se mantiene un registro del tamaño de cada cubeta.

En primer lugar, se realiza una operación de suma de prefijos que calcula los límites de los cubos. Sin embargo, dado que solo se mueven bloques completos en esta fase, los límites se redondean a un múltiplo del tamaño del bloque y se asigna un único búfer de desbordamiento. Antes de comenzar la permutación de bloques, es posible que algunos bloques vacíos deban moverse al final de su cubo. Posteriormente, se asigna un puntero de escritura.${\displaystyle w_{i}}$está configurado al inicio del cubo${\displaystyle b_{i}}$submatriz para cada cubo y un puntero de lectura${\displaystyle r_{i}}$está configurado en el último bloque no vacío del cubo.${\displaystyle b_{i}}$submatriz para cada cubo.

Para limitar la contención de trabajo, a cada procesador se le asigna un depósito primario diferente.${\displaystyle b_{prim}}$y dos búferes de intercambio que pueden contener un bloque cada uno. En cada paso, si ambos búferes de intercambio están vacíos, el procesador decrementa el puntero de lectura.${\displaystyle r_{prim}}$de su cubo principal y lee el bloque en${\displaystyle r_{prim-1}}$y lo coloca en uno de sus búferes de intercambio. Después de determinar el cubo de destino${\displaystyle b_{dest}}$del bloque al clasificar el primer elemento del bloque, incrementa el puntero de escritura${\displaystyle w_{dest}}$, lee el bloque en${\displaystyle w_{dest-1}}$en el otro búfer de intercambio y escribe el bloque en su cubo de destino. Si${\displaystyle w_{dest}>r_{dest}}$Los búferes de intercambio vuelven a estar vacíos. De lo contrario, el bloque que queda en los búferes de intercambio debe insertarse en su depósito de destino.

Si todos los bloques del subconjunto del cubo principal de un procesador se encuentran en el cubo correcto, se elige el siguiente cubo como cubo principal. Si un procesador ya ha elegido todos los cubos como cubo principal una vez, el procesador ha finalizado.

Dado que en la fase de permutación de bloques solo se movieron bloques completos, es posible que algunos elementos aún se encuentren mal ubicados cerca de los límites de los cubos. Como debe haber suficiente espacio en el arreglo para cada elemento, estos elementos mal ubicados se pueden mover a espacios vacíos de izquierda a derecha, considerando finalmente el búfer de desbordamiento.