Ordenación de muestras - Samplesort

Samplesort es un algoritmo de clasificación que es un algoritmo de división y conquista que se utiliza a menudo en sistemas de procesamiento en paralelo. Los algoritmos de clasificación convencionales para dividir y conquistar dividen la matriz en subintervalos o depósitos. Luego, los cubos se clasifican individualmente y luego se concatenan juntos. Sin embargo, si la matriz no se distribuye de manera uniforme, el rendimiento de estos algoritmos de clasificación puede reducirse significativamente. Samplesort aborda este problema seleccionando una muestra de tamaño s de la secuencia de n elementos y determinando el rango de los cubos clasificando la muestra y eligiendo p −1 < s elementos del resultado. Estos elementos (llamados divisores) luego dividen la matriz en p cubos de aproximadamente el mismo tamaño. Samplesort se describe en el artículo de 1970, "Samplesort: A Sampling Approach to Minimal Storage Tree Sorting", de WD Frazer y AC McKellar.

Algoritmo

Samplesort es una generalización de quicksort . Donde quicksort divide su entrada en dos partes en cada paso, basándose en un único valor llamado pivote, samplesort toma una muestra más grande de su entrada y divide sus datos en cubos en consecuencia. Al igual que la ordenación rápida, luego ordena de forma recursiva los cubos.

Para diseñar una implementación de samplesort, es necesario decidir el número de cubos p . Cuando se hace esto, el algoritmo real opera en tres fases:

1. Muestra p −1 elementos de la entrada (los divisores ). Ordene estos; cada par de divisores adyacentes define un cubo .
2. Recorra los datos, colocando cada elemento en el depósito correspondiente. (Esto puede significar: envíelo a un procesador, en un sistema multiprocesador ).
3. Ordena cada uno de los cubos.

La salida ordenada completa es la concatenación de los depósitos.

Una estrategia común es hacer que p sea igual al número de procesadores disponibles. Luego, los datos se distribuyen entre los procesadores, que realizan la clasificación de cubos utilizando algún otro algoritmo de clasificación secuencial.

Pseudocódigo

La siguiente lista muestra el algoritmo de tres pasos mencionado anteriormente como pseudocódigo y muestra cómo funciona el algoritmo en principio. A continuación, A son los datos sin clasificar, k es el factor de sobremuestreo, que se analiza más adelante, yp es el número de divisores.

function sampleSort(A[1..n], k, p)
    // if average bucket size is below a threshold switch to e.g. quicksort
    if ${\displaystyle n/k<}$ threshold then smallSort(A) 
    /* Step 1 */
    select ${\displaystyle S=[S_{1},\dots ,S_{(p-1)k}]}$ randomly from // select samples
    sort S // sort sample
    ${\displaystyle [s_{0},s_{1},\dots ,s_{p-1},s_{p}]\leftarrow [-\infty ,S_{k},S_{2k},\dots ,S_{(p-1)k},\infty ]}$ // select splitters
    /* Step 2 */
    for each ${\displaystyle a\in A}$
        find j such that ${\displaystyle s_{j-1}<a\leq s_{j}}$
        place a in bucket ${\displaystyle b_{j}}$
    /* Step 3 and concatenation */
    return ${\displaystyle {\texttt {concatenate}}({\texttt {sampleSort}}(b_{1}),\dots ,{\texttt {sampleSort}}(b_{k}))}$

El pseudocódigo es diferente del algoritmo original de Frazer y McKellar. En el pseudocódigo, samplesort se llama de forma recursiva. Frazer y McKellar llamaron a samplesort solo una vez y usaron quicksort en todas las iteraciones siguientes.

Complejidad

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

Encuentra los divisores.

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

Enviar a cubos.

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

${\ Displaystyle O (\ log (p))}$ para transmitir

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

${\ Displaystyle O \ left ({\ frac {n} {p}} \ right)}$ enviar llaves al cubo

Clasificar cubos.

${\ Displaystyle O \ left (c \ left ({\ frac {n} {p}} \ right) \ right)}$donde es la complejidad del método de clasificación secuencial subyacente. A menudo .${\ Displaystyle c (n)}$${\ Displaystyle c (n) = n \ log (n)}$

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

Muestrear los datos

Los datos se pueden muestrear a través de diferentes métodos. Algunos métodos incluyen:

1. Elija muestras espaciadas uniformemente.
2. Elija muestras seleccionadas al azar.

Sobremuestreo

La relación de sobremuestreo determina cuántas veces más elementos de datos extraer 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, ya que no hay muchos valores duplicados, una pequeña proporción de muestreo es suficiente. En otros casos en los que hay muchos duplicados en la distribución, será necesario un índice de sobremuestreo mayor. En el caso ideal, después del paso 2, cada depósito contiene elementos. En este caso, ningún depósito tarda más en clasificarse que los demás, porque todos los depósitos son del mismo tamaño. ${\ Displaystyle n / p}$

Después de extraer veces más muestras de las necesarias, las muestras se clasifican. A partir de entonces, los divisores utilizados como límites de cubos son las muestras en la posición de la secuencia de muestras (junto con y 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 divisores al azar. ${\ Displaystyle k}$${\ Displaystyle k, 2k, 3k, \ dots, (p-1) k}$${\ Displaystyle - \ infty}$${\ Displaystyle \ infty}$${\ Displaystyle p}$

Estimación del tamaño de la cuchara

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

Para mostrar esto, sea ​​la entrada como una secuencia ordenada. Para que un procesador obtenga más de elementos, tiene que existir una subsecuencia de la entrada de longitud , de la cual se seleccionan un máximo de S muestras. Estos casos constituyen la probabilidad . Esto se puede representar como la variable aleatoria: ${\ Displaystyle \ langle e_ {1}, \ dots, e_ {n} \ rangle}$${\ Displaystyle (1+ \ epsilon) \ cdot n / p}$${\ Displaystyle (1+ \ epsilon) \ cdot n / p}$${\ Displaystyle P _ {\ text {fail}}}$

${\ 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 {de lo contrario}} \ end {cases}}, X: = \ sum _ {i = 0} ^ {S \ cdot p-1} X_ {i}}$

Para el valor esperado de las reservas: ${\ Displaystyle X_ {i}}$

${\ Displaystyle E (X_ {i}) = P (X_ {i} = 1) = {\ dfrac {1+ \ epsilon} {p}}}$

Esto se utilizará para estimar : ${\ Displaystyle P_ {fail}}$

${\ Displaystyle P (X <S) \ approx P (X <(1- \ epsilon ^ {2}) S) = P (X <(1- \ epsilon) E (X))}$

Usando ahora el límite de chernoff , se puede mostrar:

${\ 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 {para}} S \ geq {\ dfrac {4} {\ epsilon ^ {2}}} \ ln n }$

Muchas llaves idénticas

En el caso de muchas claves idénticas, el algoritmo pasa por muchos niveles de recursividad en los que se ordenan las secuencias, porque toda la secuencia consta de claves idénticas. Esto se puede contrarrestar introduciendo depósitos de igualdad. Los elementos iguales a un pivote se ordenan en su respectivo grupo de igualdad, que se puede implementar con solo una rama condicional adicional. Los grupos de igualdad no se clasifican más. Esto funciona, ya que es probable que las claves que se produzcan más de una vez se conviertan en pivotes. ${\ Displaystyle n / k}$

Usos en sistemas paralelos

Ejemplo de ordenación de muestras en paralelo en procesadores y un factor de sobremuestreo de .${\ Displaystyle p = 3}$${\ Displaystyle k = 3}$

Samplesort se utiliza a menudo en sistemas paralelos, incluidos sistemas distribuidos como máquinas paralelas síncronas masivas . Debido a la cantidad variable de divisores (en contraste con un solo pivote en Quicksort ), Samplesort es muy adecuado e intuitivo para la paralelización y el escalado. Además, Samplesort también es más eficiente en caché que las implementaciones de, por ejemplo, quicksort.

La paralelización se implementa dividiendo la clasificación para cada procesador o nodo, donde el número de cubos es igual al número de procesadores . Samplesort es eficiente en sistemas paralelos porque cada procesador recibe aproximadamente el mismo tamaño de depósito . Dado que los depósitos se clasifican al mismo tiempo, los procesadores completarán la clasificación aproximadamente al mismo tiempo, por lo que no habrá un procesador que espere a otros. ${\ Displaystyle p}$${\ Displaystyle n / p}$

En los sistemas distribuidos , los divisores se eligen tomando elementos en cada procesador, clasificando los elementos resultantes con un algoritmo de clasificación distribuido, tomando cada elemento y transmitiendo el resultado a todos los procesadores. Esto cuesta la clasificación de los elementos en los procesadores, así como la distribución de los divisores elegidos a los procesadores. ${\ Displaystyle k}$${\ displaystyle kp}$${\ Displaystyle k}$${\ Displaystyle T _ {\ text {sort}} (kp, p)}$${\ displaystyle kp}$${\ Displaystyle p}$${\ Displaystyle T _ {\ text {allgather}} (p, p)}$${\ Displaystyle p}$${\ Displaystyle p}$

Con los divisores resultantes, cada procesador coloca sus propios datos de entrada en depósitos locales. Esto se lleva con la búsqueda binaria . A partir de entonces, los depósitos locales se redistribuyen a los procesadores. El procesador obtiene los depósitos locales de todos los demás procesadores y los clasifica localmente. La distribución lleva tiempo, donde está el tamaño del cubo más grande. La clasificación local toma . ${\ Displaystyle {\ mathcal {O}} (n / p \ log p)}$${\ Displaystyle i}$${\ Displaystyle b_ {i}}$${\ Displaystyle T _ {\ text {todos a todos}} (N, p)}$${\ Displaystyle N}$${\ Displaystyle T _ {\ text {localsort}} (N)}$

Los experimentos realizados a principios de la década de 1990 en supercomputadoras Connection Machine mostraron que la ordenación de muestras es particularmente buena para clasificar grandes conjuntos de datos en estas máquinas, porque incurre en una pequeña sobrecarga de comunicación entre procesadores. En las GPU de los últimos días , el algoritmo puede ser menos efectivo que sus alternativas.

Implementación eficiente de Samplesort

Ejemplo animado de Super Scalar Samplesort. En cada paso, los números que se comparan se marcan en azul y los números que de otro modo se leen o escriben se marcan en rojo.

Como se describió anteriormente, el algoritmo de ordenación de muestras divide los elementos de acuerdo con los divisores seleccionados. En el documento "Super Scalar Sample Sort" se propone una estrategia de implementación eficiente. La implementación propuesta en el documento utiliza dos arreglos de tamaño (el arreglo original que contiene los datos de entrada y uno temporal) para una implementación eficiente. Por lo tanto, esta versión de la implementación no es un algoritmo in situ. ${\ Displaystyle n}$

En cada paso de recursividad, los datos se copian en la otra matriz de forma particionada. Si los datos están en la matriz temporal en el último paso de recursividad, los datos se vuelven a copiar a la matriz original.

Determinando cubos

En un algoritmo de clasificación basado en comparación, la operación de comparación es la parte más crítica para el rendimiento. En Samplesort, esto corresponde a determinar el depósito para cada elemento. Esto necesita tiempo para cada elemento. ${\ Displaystyle \ log k}$

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 se almacena en y el sucesor derecho se almacena en . Dado el árbol de búsqueda t , el algoritmo calcula el número de cubo j del elemento de la siguiente manera (asumiendo que se evalúa como 1 si es verdadero y 0 en caso contrario): ${\ Displaystyle t_ {i}}$${\ Displaystyle t_ {2i}}$${\ Displaystyle t_ {2i + 1}}$${\ Displaystyle a_ {i}}$${\ Displaystyle a_ {i}> t_ {j}}$

${\displaystyle j\leftarrow 1}$
${\displaystyle {\texttt {repeat}}\log _{2}p\ {\texttt {times}}}$
    ${\displaystyle j\leftarrow 2j+(a>t_{j})}$
${\displaystyle j\leftarrow j-p+1}$

Dado que el número de depósitos 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 errores de predicción en las ramas , lo que ralentizaría significativamente la operación de comparación.

Fraccionamiento

Para una partición eficiente de los elementos, el algoritmo necesita conocer los tamaños de los cubos de antemano. Para dividir los elementos de la secuencia y ponerlos en la matriz, necesitamos saber el tamaño de los cubos de antemano. Un algoritmo ingenuo podría contar la cantidad de elementos de cada depósito. Luego, los elementos podrían insertarse en la otra matriz en el lugar correcto. Con esto, uno tiene que determinar el depósito para cada elemento dos veces (una vez para contar el número de elementos en un depósito y una vez para insertarlos).

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

Ordenación de muestras en el lugar

Una desventaja clave de la implementación eficiente de Samplesort que se muestra arriba es que no está en el lugar y requiere una segunda matriz temporal del mismo tamaño que la secuencia de entrada durante la clasificación. Existen implementaciones eficientes de, por ejemplo, clasificación rápida y, por lo tanto, más eficientes en cuanto al espacio. Sin embargo, Samplesort también se puede implementar in situ.

El algoritmo in situ se divide en cuatro fases:

1. Muestreo equivalente al muestreo en la implementación eficiente antes mencionada.
2. Clasificación local en cada procesador, que agrupa la entrada en bloques de modo que todos los elementos de cada bloque pertenezcan al mismo depósito, pero los depósitos no son necesariamente continuos en la memoria.
3. La permutación de bloques coloca los bloques en el orden globalmente correcto.
4. La limpieza mueve algunos elementos en los bordes de los cubos.

Una desventaja obvia de este algoritmo es que lee y escribe cada elemento dos veces, una en la fase de clasificación y otra en la fase de permutación de bloques. Sin embargo, el algoritmo funciona hasta tres veces más rápido que otros competidores in situ de última generación y hasta 1,5 veces más rápido que otros competidores secuenciales de última generación. Como el muestreo ya se discutió anteriormente, las tres etapas posteriores se detallarán más a continuación.

Clasificación local

En un primer paso, la matriz de entrada se divide en franjas de bloques del mismo tamaño, uno para cada procesador. Cada procesador asigna además búferes que son del mismo tamaño que los bloques, uno para cada depósito. A partir de entonces, cada procesador escanea su franja y mueve los elementos al búfer del depósito correspondiente. Si un búfer está lleno, el búfer se escribe en la franja del procesador, comenzando por el frente. Siempre hay al menos un tamaño de búfer de memoria vacía, porque para que se escriba un búfer (es decir, el búfer está lleno), se tuvo que escanear al menos un tamaño de búfer completo de elementos más que elementos escritos de nuevo. Por lo tanto, cada bloque completo contiene elementos del mismo depósito. Mientras se escanea, se realiza un seguimiento del tamaño de cada cubo. ${\ Displaystyle p}$${\ Displaystyle k}$

Permutación de bloque

En primer lugar, se realiza una operación de suma de prefijo que calcula los límites de los depósitos. 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 depósito. A partir de entonces, se establece un puntero de escritura en el inicio del subconjunto de cubos para cada cubeta y un puntero de lectura se establece en el último bloque no vacío en el subarreglo de cubos para cada cubeta. ${\ Displaystyle w_ {i}}$${\ Displaystyle b_ {i}}$${\ Displaystyle r_ {i}}$${\ Displaystyle b_ {i}}$

Para limitar la contención de trabajo, a cada procesador se le asigna un depósito principal diferente 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 reduce el puntero de lectura de su cubo principal, lee el bloque y lo coloca en uno de sus búferes de intercambio. Después de determinar el segmento de destino del bloque clasificando el primer elemento del bloque, aumenta el puntero de escritura , lee el bloque en el otro búfer de intercambio y escribe el bloque en su segmento de destino. Si , los búferes de intercambio están vacíos nuevamente. De lo contrario, el bloque que queda en los búferes de intercambio debe insertarse en su depósito de destino. ${\ displaystyle b_ {prim}}$${\ displaystyle r_ {prim}}$${\ Displaystyle r_ {prim-1}}$${\ displaystyle b_ {dest}}$${\ displaystyle w_ {dest}}$${\ Displaystyle w_ {dest-1}}$${\ Displaystyle w_ {dest}> r_ {dest}}$

Si todos los bloques del subconjunto del depósito principal de un procesador están en el depósito correcto, se elige el siguiente depósito como depósito principal. Si un procesador elige todos los depósitos como depósito principal una vez, el procesador finaliza.

Limpiar

Dado que solo se movieron bloques completos en la fase de permutación de bloques, es posible que algunos elementos aún se coloquen incorrectamente alrededor de los límites del depósito. Dado que debe haber suficiente espacio en la matriz para cada elemento, esos elementos colocados incorrectamente se pueden mover a espacios vacíos de izquierda a derecha, considerando finalmente el búfer de desbordamiento.

Ver también

• Flashsort
• Ordenación rápida

Referencias

enlaces externos

Muestras y derivados de Frazer y McKellar:

• Documento original de Frazer y McKellar
• DOI.org
• DOI.org

Adaptado para su uso en equipos paralelos:

• http://citeseer.ist.psu.edu/91922.html
• http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.214