Tengo un conjunto fijo de 9 valores que deben ordenarse en un FPGA.
¿Cuál sería un algoritmo de clasificación óptimo para implementar?
Tengo un conjunto fijo de 9 valores que deben ordenarse en un FPGA.
¿Cuál sería un algoritmo de clasificación óptimo para implementar?
La clasificación en un FPGA se realiza normalmente utilizando una Red de clasificación . Un buen ejemplo de una red de clasificación es Clasificación Bitónica . Una red de clasificación es una red fija de comparadores donde el orden de las operaciones no depende de los datos. La ordenación bitónica tiene una complejidad de O (n * log (n) ^ 2), aunque no es O (n * log (n), como los algoritmos de clasificación que se utilizan popularmente en implementaciones de software, a menudo es más eficiente de implementar en un FPGA. Debido a su estructura fija.
Para arreglos pequeños como sus valores de 9, puede tener una red de clasificación fija con un rendimiento de 9 valores ordenados por ciclo de reloj. Si tiene arreglos más grandes o requisitos de rendimiento más bajos, la operación de clasificación se puede calcular en diferentes pases como una FFT en la que se aplica una red de clasificación bitónica de entrada k fija a los datos varias veces. Por lo general, k se elige lo suficientemente grande para minimizar el número de pases y mantener el tamaño de la ruta de datos factible. La red de ordenación bitónica más pequeña es una red de 2 entradas donde una salida es el valor mínimo y la otra el valor máximo.