Resumen - Clasificación de la Hora: Un nuevo algoritmo de clasificación paralela y su implementación

Clasificación de la Hora: Un nuevo algoritmo de clasificación paralela y su implementación

2025-07-22 08:08:29

{"Daniel Bascones","Borja Morcillo"}

{cs.AR,B.5.0}

El Algoritmo de Clasificación de la Forma de Reloj (Hourglass Sorting) es un algoritmo de clasificación paralelo innovador diseñado para ordenar eficientemente grandes conjuntos de datos con entrada paralela y salida serial. Logra una latencia de log(n) para la salida del primer elemento, con un tiempo total de clasificación de n + log(n). Este algoritmo es particularmente útil para aplicaciones que requieren una clasificación rápida de grandes conjuntos de datos, como la decodificación LDPC cuántica. El algoritmo de Clasificación de la Forma de Reloj se basa en una estructura de comparadores similar a un árbol, con cada nodo que tiene dos registros de salida para evitar el efecto de "burbuja" que puede ocurrir en los algoritmos de clasificación tradicionales. Esto permite que el algoritmo mantenga una trayectoria crítica constante con respecto al tamaño de la entrada, resultando en un diseño altamente escalable. El algoritmo ha sido implementado en un FPGA y se ha integrado con éxito en una implementación de BP-OSD (Propagación de la Fe - Decodificador de Estadísticas Ordenadas) para la codificación LDPC cuántica. La implementación demuestra las capacidades del algoritmo en aplicaciones reales, como la decodificación en tiempo real de códigos correctores de errores. Las características clave del algoritmo de Clasificación de la Forma de Reloj incluyen: - Complejidad en hardware de O(n) - Latencia de log(n) para la salida del primer elemento - Tiempo total de clasificación de n + log(n) - Diseño escalable con trayectoria crítica constante - Eficiencia para ordenar grandes conjuntos de datos con entrada paralela y salida serial El algoritmo de Clasificación de la Forma de Reloj representa un progreso significativo en los algoritmos de clasificación paralelos, ofreciendo una solución altamente eficiente y escalable para aplicaciones que requieren una clasificación rápida de grandes conjuntos de datos.