He estado haciendo un montón de ingeniería de software, y me siento intrigado por la implementación del hardware de las cosas en la medida en que me gustaría trasladar uno de mis algoritmos recientes a un FPGA. Tratar de aprender FPGAs, que parece más fácil de lo que solía, pero todavía me deja en la oscuridad para los patrones / soluciones habituales. Así que aquí está mi problema:
Digamos que puse muchos (~ 100) "núcleos" en un FPGA que calcula las posibles coincidencias. Cada coincidencia posible es un valor de 64 bits, y supongamos que la computación dice que las posibles coincidencias son caras (~ 35k ciclos de reloj).
Ahora, una vez que se han calculado las coincidencias, quiero ver si alguna coincide con una lista precomputada de aproximadamente 15k posibles valores de 64 bits. La probabilidad de que se encuentre una posible coincidencia es muy pequeña (~ 1e-8).
¿Cuál sería / debería ser un diseño para calcular si se encuentran posibles coincidencias en mi lista original? Puedo asumir que mi lista original es fija (y presumiblemente clasificada).
En software, he estado utilizando una búsqueda binaria, pero me pregunto sobre el acceso a la RAM en ese caso. Si tuviera 100 núcleos, cada uno de ellos con una coincidencia posible cada 35k ciclos de reloj, significa que (suponiendo que tuviera algún tipo de búfer disponible) podría tener un componente de búsqueda binario siempre que se necesitaran menos de 350 ciclos de reloj para ver si algo coincide (y suponiendo 14 comparaciones para una búsqueda binaria entre elementos de 15k, parece casi factible).
Entonces, ¿alguna idea? ¿Es la búsqueda binaria el camino a seguir (y debería modificarse? ¿Usar un montón para ayudar con el almacenamiento en caché de las líneas de memoria RAM o la búsqueda k-ary? ¿Mirar los mapas de hash o los filtros de floración para un descarte más rápido?) ¿Existe alguna forma "estándar"? para hacer este tipo de cosas?