Ordenar usando verilog

En primer lugar, no pienses demasiado en "Big O". Tienes una entrada de tamaño fijo pequeño.

En segundo lugar, piense si está más preocupado por el rendimiento o la latencia.

En tercer lugar, tenga en cuenta que el diseño HDL siempre tiene que ver con compensaciones de espacio-tiempo, ¿realmente necesita que sea "lo más rápido posible"? o tienes restricciones de espacio también.

Si el número de valores posibles es pequeño, entonces la clasificación radix puede tener una complejidad algorítmica del peor de los casos (un caso peor en los sistemas en tiempo real es lo que le interesa) que cualquier "clasificación de comparación", pero es difícil paralelizar .

La propuesta en enlace tiene una latencia mucho más baja Que la propuesta de radix de dave. También es probablemente más fácil de implementar, ya que los bancos tienen un montón de casos de esquina para tratar con respecto a la década de quince y la puesta en común de la etapa intermedia.

¿Por qué? No es porque el algoritmo requiera menos operaciones, de hecho, requiere considerablemente más. Sin embargo esas operaciones son altamente paralelizadas. Básicamente es una ordenación por inserción, pero en lugar de verificar las posibles inserciones una a la vez y luego cambiar los valores uno por uno si se encuentra una coincidencia, realiza esas comprobaciones y cambios en paralelo.

La desventaja es que va a consumir más lógica. En lugar de ubicaciones en blockram, tiene una parte relativamente compleja de lógica para cada valor en el clasificador.

Sí, una clasificación de radix tendría mucho sentido para datos de 8 bits. Funcionaría en tres fases y requeriría dos pequeños bloques de memoria.

El primer bloque de memoria tendría 256 ubicaciones. Se usaría para contar cuántas veces aparece cada valor de datos en el grupo de píxeles que se están ordenando. Si está clasificando 64 píxeles a la vez, entonces esta memoria debería tener 7 bits de ancho. (En realidad, para una operación continua, querrá que esta memoria tenga doble búfer, por lo tanto, 2 × 256 ubicaciones).

El segundo bloque de memoria se opera como FIFO. Cada entrada en este FIFO es un par de valor: cuenta , donde el valor tiene 8 bits de ancho y el cuenta tiene 7 bits de ancho, para una Ancho total de 15 bits. Este FIFO debe tener una profundidad de al menos 64 palabras para manejar el caso en el que cada valor de entrada solo aparecía una vez.

Comience por borrar los contadores del primer grupo de píxeles. Después de eso, las tres fases son:

• A medida que llegan los píxeles, incremente el contador correspondiente.

• Escanee los contadores y, cuando tenga un conteo distinto de cero, transfiera el par value: count al FIFO. Además, borre los contadores en este momento para el próximo pase. Tenga en cuenta que aquí es donde elige la dirección del orden, por la cual escanea los contadores.

• Lea los pares value: count fuera de FIFO y genere count copias de cada valor en la salida.

Acabo de darme cuenta de que hay un problema aquí en términos de tiempo: la primera y la tercera fase requieren 64 relojes cada una, mientras que la fase media requiere 256 relojes. Esto significa que para la operación continua, la primera memoria tendrá que ser 4 memorias separadas con 256 ubicaciones cada una, deberá tener cuatro copias intercaladas de la fase media, cada una alimentando su propio FIFO, y la tercera fase tendrá que cambiar secuencialmente entre las salidas FIFO. (Tenga en cuenta que este problema no se presenta si el número de píxeles en cada grupo es al menos tan grande como el número de valores).

Esta implementación podría procesar píxeles de entrada y salida continuamente, y la latencia total desde la entrada a la salida sería 64 + 256 = 320 relojes.