Un algoritmo de clasificación es un algoritmo que pone elementos de una lista en un cierto orden. Las órdenes más utilizadas son orden numérica y orden lexicográfico. Clasificación eficiente es importante para optimizar el uso de otros algoritmos (como los algoritmos de búsqueda y fusión) que requieren listas ordenadas para trabajar correctamente; también es a menudo útil para canonicalizing datos y para la producción de salida legibles. Más formalmente, la salida debe satisfacer dos condiciones:
1. la salida es en no disminuir orden (cada elemento es no más pequeño que el elemento anterior según el orden deseado de total);
2. la salida es una permutación (reordenación) de la entrada.
-Clasificación es una de las funciones claves
para muchos usos tales como decodificadores para la comunicación digital, procesamiento digital de señales, VLSI CAD etc.. Como consecuencia, hay gran interés en acelerar clasificación en software como en hardware.
-El tiempo en la clasificación dependiendo del número de palabras en el caso de algoritmos de software la mejora que estamos tratando de hacer en este proyecto es que el tiempo depende de la cantidad de bits por palabra k y no el número de palabras
Declaración del problema:
Clase de algoritmos de clasificación tradicionales como burbuja, ordenamiento por inserción, tipo de combinación y muchos más tienen una base que requiere el intercambio de elementos de dos datos en un momento. Incluso mientras que usa una combinación de dos algoritmos de ordenación como el uso de quick sort y merge tipo juntos para ordenar una matriz de números, el caso base todavía implica el intercambio de elementos de dos datos en un momento dado. Por lo tanto, la motivación para explorar algoritmos de clasificación implementado vía hardware tiene su origen en el hecho de que a través de hardware uno es capaz de explotar mejor el paralelismo, de tal modo clasificar muchos números simultáneamente.
Paralelismo no sólo asegura la concurrencia sino también pretende reducir la complejidad del tiempo de los algoritmos. Por lo tanto, el problema es diseñar un nuevo algoritmo de clasificación e implementar en hardware que extrae paralelismo.
