Clasificador bitónico

El algoritmo de ordenación por fusión bitónica es un algoritmo paralelo para la ordenación. También se utiliza como método de construcción para crear una red de ordenación . El algoritmo fue ideado por Ken Batcher . ^{[ 3 ]} Las redes de ordenación resultantes consisten en: ${\mathcal {O}}(n(\log n)^{2})$ comparadores y tienen un retraso de ${\mathcal {O}}((\log n)^{2})$ , dónde $n$ es el número de elementos a ordenar. ^{[ 1 ]}^{[ 2 ]} Esto lo convierte en una opción popular para ordenar grandes cantidades de elementos en una arquitectura que contiene una gran cantidad de unidades de ejecución paralelas que se ejecutan en sincronía , como una GPU típica .

Una secuencia ordenada es una secuencia monótona , es decir, una secuencia que no es decreciente ni creciente. Una secuencia es bitónica cuando consta de una secuencia no decreciente seguida de una secuencia no creciente, es decir, cuando existe un índice $m$ para qué $x_{0}\leq \cdots \leq x_{m}\geq \cdots \geq x_{n-1}.$ ^{[ 3 ]}

Un clasificador bitónico solo puede clasificar entradas que sean bitónicas. Los clasificadores bitónicos se pueden usar para construir una red de clasificación bitónica que puede clasificar secuencias arbitrarias mediante el uso del clasificador bitónico con un esquema de clasificación por fusión, en el que las soluciones parciales se fusionan usando clasificadores más grandes.

Las siguientes secciones presentan el algoritmo en su formulación original, que requiere una secuencia de entrada cuya longitud $n$ es una potencia perfecta de dos. Por lo tanto, dejaremos $k=\log _{2}(n)$ sea el número entero para el cual $n=2^{k}$ , lo que significa que los clasificadores bitónicos pueden enumerarse en orden de tamaño creciente considerando los valores sucesivos. $k=1,2,3,\ldots$ .

Clasificador bitónico

Esta imagen muestra un comparador con dos entradas etiquetadas como X e Y, y dos salidas como H y L. — Un comparador normal con dos entradas

Un clasificador bitónico para $k=1$ $(n=2)$ es simplemente un comparador. ^{[ 3 ]} Esto se ilustra con el diseño de la caja dado, en el que X e Y representan las entradas, mientras que H y L representan las salidas más alta y más baja, respectivamente.

Con el clasificador para $k=1$ Podemos crear recursivamente un clasificador de orden superior. Por ejemplo, consideremos lo siguiente: $k=2$ $(n=4)$ clasificador bitónico. ^{[ 3 ]}

Esta imagen muestra un clasificador de fusión bitónico con 4 entradas. A la izquierda se encuentran las entradas x1 a x4. Estas están conectadas a dos comparadores: x1 y x3 a uno, y x2 y x4 al otro. Todas las salidas bajas van a un comparador y todas las salidas altas al otro. — A $n=4$ $(k=2)$ clasificador de fusión bitónico

{\displaystyle n=4} — A $n=4$ $(k=2)$ clasificador de fusión bitónico

El clasificador bitónico consta de dos capas: una capa de recombinación, que recombina las entradas bitónicas en dos nuevas secuencias bitónicas que tienen cada una la mitad de la longitud de la secuencia original, y una capa de clasificación bitónica que consta de dos clasificadores bitónicos de orden $k-1$ , cada una de las cuales ordena una de las dos secuencias bitónicas producidas por la capa anterior. Esta estructura puede extenderse recursivamente para valores más altos de $k$ Al garantizar que cada comparador siempre acepte una entrada de cada una de las dos mitades de la secuencia bitónica que se supone que debe ayudar a ordenar. La siguiente ilustración muestra estas conexiones esquemáticamente. ^{[ 3 ]}

Como puede observarse, los elementos de la primera mitad de la secuencia de entrada se comparan por pares con los elementos correspondientes de la segunda mitad. La comparación de cada elemento de la subsecuencia ( verde ) con el elemento de la otra subsecuencia ( naranja ) en el índice correspondiente genera dos subsecuencias bitónicas. Estas dos series bitónicas ( azul y roja , respectivamente) pueden introducirse en el siguiente clasificador bitónico de orden inferior. Esto es posible porque se garantiza que todos los elementos de la secuencia roja son mayores que todos los elementos de la serie azul. ^{[ 3 ]}

Corrección del clasificador bitónico

Ken Batcher proporcionó un esbozo de demostración matemática en su artículo. ^{[ 3 ]} Sin pérdida de generalidad, se supone que la secuencia de entrada bitónica es $a_{1}\leq a_{2}\leq \dots \leq a_{j-1}\leq a_{j}\geq a_{j+1}\geq \dots \geq a_{2n}$ con $1\leq j\leq 2n$ Sin pérdida de generalidad, la secuencia puede invertirse; por lo tanto, podemos asumir $n\leq j\leq 2n$ .

Caso 1 : Si $a_{n}\leq a_{2n}$ entonces cada elemento de las dos subsecuencias es menor. En este caso $d_{i}=a_{i}$ y $e_{i}=a_{n+i}$ con $1\leq i\leq n$ y por lo tanto $d_{i}$ y $e_{i}$ son trivialmente bitónicos.

Caso 2 : De lo contrario existe un $k$ de tal manera que el elemento $a_{k}$ de la primera subsecuencia es mayor que $a_{k}$ de la segunda subsecuencia, mientras que es lo opuesto para $a_{k+1}$ Esto significa que $a_{k}\leq a_{k+n}$ y $a_{k+1}>a_{k+n+1}$ son ciertas para un caso específico $k$ Por lo tanto, ahora sabemos que:

1. Para $1\leq i\leq k$ las secuencias son $d_{i}=a_{i}$ y $e_{i}=a_{n+i}$

2. Para $k<i\leq 2n$ Las secuencias se definen como lo opuesto a 1, con $d_{i}=a_{n+i}$ y $e_{i}=a_{i}$

En el artículo original, afirma que las siguientes desigualdades resultan de esas definiciones: ^{[ 3 ]}

Continuando desde 1 :

Para $1\leq i\leq k$ eso $d_{i}\leq d_{i+1}$
Para $jn\leq i\leq k$ eso $e_{i}\geq e_{i+1}$
Para $1\leq i\leq jn$ eso $e_{i}\leq e_{i+1}$

Continuando desde 2 :

Para $k<i\leq 2n$ eso $d_{i}\geq d_{i+1}$
Para $k<i\leq 2n$ eso $e_{i}\leq e_{i+1}$

De ambos: $e_{n}\leq e_{1}$

Del artículo se desprende que las secuencias $d_{i}$ y $e_{i}$ son de hecho bitónicos. ^{[ 3 ]}

Redes de ordenación bitónica (ordenación por fusión bitónica)

Una red de ordenación bitónica se crea utilizando varios clasificadores bitónicos. Estos clasificadores bitónicos se utilizan recursivamente para crear dos secuencias monótonas, una decreciente y otra creciente, que luego se colocan en la siguiente etapa. Esto crea una serie bitónica para la siguiente etapa, que luego puede usar esta serie bitónica como una serie monótona para la siguiente etapa. Considere el siguiente ejemplo para una $n=4$ red de ordenación bitónica. ^{[ 3 ]}

La red de clasificación bitónica para $k=2$ se puede crear utilizando un $k=2$ clasificador bitónico y dos $k=k_{prev}-1$ clasificadores. Los dos clasificadores crean una secuencia ordenada de forma decreciente o creciente para generar una entrada bitónica para el clasificador bitónico. Las redes de clasificación bitónica de orden inferior se utilizan principalmente para los dos preclasificadores; por lo tanto, se puede describir una definición recursiva de una red de clasificación bitónica a partir de clasificadores bitónicos. En el ejemplo anterior, las dos redes de clasificación bitónica son: $k=1$ redes; por lo tanto, son solo un comparador. ^{[ 3 ]} La siguiente figura muestra el esquema general.

Este esquema general requiere que el clasificador reciba como entrada una secuencia que sea potencia de dos. Sin embargo, existen maneras de mitigar este problema, por ejemplo, utilizando valores centinela.

Pseudocódigo

El siguiente pseudocódigo describe el proceso de ordenación. En el código, aes el arreglo que se va a ordenar, lowes el índice del primer elemento del subarreglo que se va a ordenar, ky countes el número de elementos del subarreglo que se están ordenando en esta llamada a la función. directiones un valor booleano que determina si el subarreglo se está ordenando en orden ascendente o descendente.

La llamada a la función bitonicSort(a, 0, n, 1)se utiliza para ordenar a(de forma ascendente), donde nes el número de elementos en a.

La función bitonicMerge( a , low , count , direction ) es si count > 1 ENTONCES k ← count / 2 // Comparar e intercambiar elementos entre las mitades para i ← bajo a bajo + k hacer // determinar si dos elementos de a están fuera de orden en relación con la dirección de ordenación. si ( dirección == 1 Y a [i] > a [i + k]) O ( dirección == 0 Y a [i] < a [i + k]) ENTONCES intercambiar a [i] con a [i + k] // Fusionar recursivamente ambas mitades bitonicMerge ( a , baja , k, dirección ) bitonicMerge ( a , baja + k, k, dirección ) // Esto solo funciona cuando el tamaño de entrada es una potencia de 2. La función bitonicSort( a , low , count , direction ) es si count > 1 ENTONCES k ← count / 2 // Ordenar la primera/segunda mitad en orden ascendente/descendente bitonicSort ( a , low , k, 1) bitonicSort ( a , low + k, k, 0) // Combinar toda la secuencia en el orden deseado bitonicMerge ( a , low , count , direction )

Complejidad

En esta sección asumimos que nuestro clasificador tiene $n=2^{k}$ elementos de entrada como antes.

Cada recursión en una red de ordenación bitónica agrega un clasificador de orden $k_{next}=k_{prev}-1$ , que consiste en bitónico $k_{next}$ clasificador y la siguiente recursión. Como ambos subclasificadores se pueden realizar en paralelo, solo se agrega un nivel por cada nivel en ambos subclasificadores. Cada clasificador bitónico tiene, por lo tanto, una capa de recombinación y un clasificador bitónico de orden inferior para su recursión. Esto da como resultado $k$ niveles por clasificador bitónico. Por lo tanto, podemos describir los niveles de esta construcción como la siguiente suma: $\sum _{i=1}^{k}i$ .

Esta suma se puede reducir utilizando la fórmula de suma de Gauss. $\sum _{i=1}^{k}i={\dfrac {1}{2}}k(k+1)$

Por lo tanto, el número de niveles en los que cada comparación puede realizarse en paralelo viene dado por ${\dfrac {1}{2}}k(k+1)$ . ^{[ 3 ]} Lo que nos da ${\mathcal {O}}(k^{2}+k)={\mathcal {O}}(k^{2})={\mathcal {O}}((\log _{2}n)^{2})$ arrogante $n$ Las comparaciones pueden realizarse en paralelo.

Aunque el número absoluto de comparaciones suele ser mayor que en la ordenación par-impar de Batcher , muchas de las operaciones consecutivas en una ordenación bitónica conservan una localidad de referencia , lo que hace que las implementaciones sean más amigables con la caché y, por lo general, más eficientes en la práctica. ^{[ 3 ]}

Véase también

Referencias

1 2 3 4 5 Megha, Jain; Sanjay, Kumar; VK, Patle (marzo de 2015). "Algoritmo de ordenación bitónica: una revisión" . Revista internacional de aplicaciones informáticas . 113 (13): 40– 43. Bibcode : 2015IJCA..113m..40J . doi : 10.5120/19890-1930 . Recuperado el 14 de mayo de 2025 .
1 2 3 4 5 Rankovic, Vukašin; Cos, Antón; Milutinović, Veljko (julio de 2013). "Implementación de Bitonic Merge Sort en el sistema de supercomputación Maxeler Dataflow" (PDF) . Las transacciones IPSI BGD sobre investigación en Internet . 9 (2) : 5–10 . Consultado el 14 de mayo de 2025 .
1 2 3 4 5 6 7 8 9 10 11 12 13 Batcher, KE (30 de abril de 1968). "Redes de clasificación y sus aplicaciones". Actas de la conferencia conjunta de computación de primavera del 30 de abril al 2 de mayo de 1968 - AFIPS '68 (Primavera) . págs. 307–314 . doi : 10.1145/1468075.1468121 .

Enlaces externos

Una discusión sobre este algoritmo
Código de referencia en NIST
Tutorial con imágenes animadas y código funcional.

[bitonicReview-1] 1 2 3 4 5 Megha, Jain; Sanjay, Kumar; VK, Patle (marzo de 2015). "Algoritmo de ordenación bitónica: una revisión" . Revista internacional de aplicaciones informáticas . 113 (13): 40– 43. Bibcode : 2015IJCA..113m..40J . doi : 10.5120/19890-1930 . Recuperado el 14 de mayo de 2025 .

[bitonicImplSuperComputer-2] 1 2 3 4 5 Rankovic, Vukašin; Cos, Antón; Milutinović, Veljko (julio de 2013). "Implementación de Bitonic Merge Sort en el sistema de supercomputación Maxeler Dataflow" (PDF) . Las transacciones IPSI BGD sobre investigación en Internet . 9 (2) : 5–10 . Consultado el 14 de mayo de 2025 .

[:0-3] 1 2 3 4 5 6 7 8 9 10 11 12 13 Batcher, KE (30 de abril de 1968). "Redes de clasificación y sus aplicaciones". Actas de la conferencia conjunta de computación de primavera del 30 de abril al 2 de mayo de 1968 - AFIPS '68 (Primavera) . págs. 307–314 . doi : 10.1145/1468075.1468121 .

[ 1 ]

[ 2 ]